he arc due to the assumption of the positivity of the arc lengths. The next shortest among Kratchayshih ways must be a way from one arc to the next nearest neighbor node i, or the shortest route from the two arcs passing through the node selected in the first step, etc. To describe this process formally in the form of the algorithm, we assume that each node i is labeled as Di, meaning estimate the length of the shortest path from node i. when the score becomes constant, we assume that the final node is marked.

Formally, the algorithm operates as follows:

Initially, P = {1}, D1 = 0 and Dj = D1j for j ≠ 1.

Steps 1 (to find the next nearest node). Find i P , such that

D i = min j P D j (3)

put P: = P È {i}. If P contains all the nodes, then the work in the algorithm ends.

Step 2 (labels update) to put all j P

D j : = min [ D j , D i + d i j ] (4)

Go to step 1.

Since the number of operations performed by the Dijkstra’s algorithm at each step in proportion to N, where N is the number of the network nodes, and the steps iterated N-1 times, the amount of computation in the worst case is equal to N2, instead of N3, like Bellman-Ford algorithm.

The advantages of these algorithms are relatively the low computational complexity and ease of implementation. In the classical formulation of the algorithms presented problems are mainly the shortest path from the source node to any intermediating node till reaching the recipient, taking into consideration that the problem of ET routing strategy is needed, which would enable to balance the load on the network and to take into account the requirements for QoS of the processed streams. In addition, one of the requirements for routing protocols in the MPLS-TE networks is the possibility remarshrutizatsii traffic for a time not exceeding 50 ms, which implies a preliminary finding of circumvention, and (backup) paths.

As a result, the ideas contained in the Bellman-Ford algorithms and Deyktry, were developed in the mathematical models and multipath routing algorithms. Multipath routing strategies have been developed, which are based on graph-laid combinatorial algorithms to find the shortest paths. The most famous practical implementation are the algorithm for ECMP (Equal Cost Load Balancing), expanding the capabilities of RIP (Routing Information Protocol) and OSPF (Open Shortest Path First), plus load balancing algorithms along paths with different value presented in the company’s proprietary protocols IGRP (Interior Gateway Routing Protocol) developed by CISCO and EIGRP (Extended Interior Gateway Routing Protocol). In each of these protocols; it is implemented the same approach to solve the routing problem, which is generally reduced to an algorithm of three actions as follows:

1) Finding the set of shortest paths;

2) Selecting routes for handling loads with the same or different value; and

3) The load distribution on the selected paths are usually proportional to the matric.

A further development of the idea of using Grafokombinatornyh models are algorithms for finding the set of shortest paths to address multipath routing problem. For example, the idea of a distributed algorithm for multipath routing M-path [15] is to find the routing graph that does not contain loops and presented the set of arcs are given in Equation (5):

S G i = { ( m , n ) | n S j m , m M } (5)

where M is the plurality of network nodes, M i is the plurality of nodes neighborin, i is the node, and S j m is the variety of options subsequent packets from node i to node k.

The shortest multipath, according M-path, is given by Equation (6):

S j i = { k M i | D j k i < D j i } (6)

where D j k i is the local value of the shortest path tree from node i to k.

Then the eliminated loops are achieved by making the following conditions which are given in Equation (7) and Equation (8):

F D j i ( t ) D j i k ( t ) , k M i (7)

S j i ( t ) = { k M i | D j k i ( t ) < F D j i ( t ) } , (8)

where F D j i is the calculation of the allowable distance set S j i .

M-path algorithm ensures that the achievement of equality is given in Equation (9):

F D j i = D j i = D j i k , i , j , k M i (9)

An alternative approach to solve the problem of multi-path routing algorithm is implemented in DASM (Multipath Distance-Vector Algorithm) [16] [17] . This algorithm assumes that each intermediate router contains the record routing table, which includes a set of parameters for each destination host. In addition, each such record consists of several parameters that determine the next router on the path to the destination node and the distance along the path that does not contain loops. According to the algorithm, each router can be in one of two states: either active or passive. The router is regarded as passive when all paths S j i derived from the exchange, which means that all its neighbors are listed in the routing table. Otherwise, the router becomes active; and hence starts trying to find a path to the node j by sending query messages to neighbors.

The shortest path between nodes i and j in DASM will be determined by the expression proposed in the distributed Bellman-Ford algorithm as given in Equation (10):

D min i j = min { D j k i + l k i | k M i } (10)

where l k i is the length (cost) of the transition towards a neighbor k; if k is the neighbor is no longer available l k i , use the value ∞. The resulting multipath S j i is given by Equation (11):

S j i = { k M i | D ˜ j k i * < min ( F D j i , D min i j ) } (11)

where D ˜ j k i * is the upper limit of the neighbor k to the node with distance j, and F D j i is the allowable distance from the router i to router j. Accordingly, resulting multipath contains loops S j i the condition becomes as in Equation (12):

S j i ( t ) = { k M i | D j k i ( t ) < F D j i ( t ) } (12)

It should be noted that, despite of the fact that the algorithms and MPATH DASM for finding shortest paths using different approaches (in the first case, it is Dijkstra’s algorithm, while the second case is the distributed algorithm of Bellman-Ford), the conditions of the loops absence in the above algorithms are still identical.

Another development of the multipath algorithm of Bellman-Ford is the ROAM (Routing On-Demand Acyclic Multipath). The feature of this algorithm is its ability to store the router information only about the paths to the purpose of the currently produced transmission packet. This minimizes the amount of information stored in the intermediate device, which is particularly important in the case of large networks. Path to the remote nodes are determined “on demand” when receiving a packet from a node which has no direct path with node i.

Table of distances in the router i is a matrix contains the distance to each destination node D j k i from a neighboring node k, and the response status flag S T j k i . Table routing i is a vector comprising for each destination node that is located in j distance to the destination, the allowable distance F D j i , “message” distance R D j i ,used route s j i , the requester and the flag o j i timestamp T j i . Table values channel includes the cost of channels to known neighbors k for assembly i is l k i .

According to the algorithm ROAM [18] , the router becomes in one of the following three states:

1) Passive: The information about the existence of the recipient j is either known or unknown;

2) Active: The waiting for information on j in the process of creating a route; or

3) Active-waiting: Active and waiting for a response from the neighbors of the most recommended or expected destination j.

In the passive state; the router takes the shortest route only from all available nodes, accordingly, the alternative routes via neighbor q M i can be selected as the primary under the conditions of Equation (13), and Equation (14):

D j q i ( t ) + l q i ( t ) = min { D j x i ( t ) + l x i , x M i } (13)

D j q i ( t ) < F D j i ( t ) , where F D j i ( t ) = D j * i ( t ) (14)

The algorithm guarantees the absence of loops in the selection of alternative routes to node j, when the topology router can be set to switch into an active state, in which updates are exchanged by diffusion in order to find the main route.

Along with the aforementioned advantages Grafokombinatornyh models and algorithms, it is worth noting a number of important shortcomings, greatly limiting their practical implementation in today’s multi-TCS, which are: First: The agreed solution of problems of load balancing, QoS routing and security in the framework of graph models and combinatorial algorithms, optimized for single-commodity-pole network, the increasing number of traffic (products) on the network faces a number of serious difficulties descriptive and computational nature, since it is assumed that all network resources are allocated one under consideration traffic. Second: The main advantage of the models considered, consisting in simplicity and predictable computational complexity of implementation, with the number of parameters taken into account QoS (three or more), it is reduced to zero, because the task of finding even one of the shortest path in this case becomes completed.

It should be noted that the decision to route tasks originally did not fit into the framework of Grafokombinatornyh models, since they do not allow the correct mathematical description of the dynamics of the processes status, providing multiple services and guaranteed quality of communication over the two indicators. In modern conditions the search for the shortest path (multipath) for each of the serviced traffic is not always even necessary, but the more sufficient, condition for the successful solution of routing problems, since, still remains an open question of the allocation of resources along each of the routes. At a time when the decision block of problems is difficult, and sometimes almost impossible to cover a countable number of options; the use of combinatorial algorithms becomes impractical, or use them in conjunction with other search methods. This is particularly true for applications in which, the network settings is expected, so, it is needed to consider many external factors, such as the parameters of the information flows.

Despite of the limited opportunities Grafokombinatornyh mathematical models; the lack of strict requirements to the quality of decision-route tasks previously contributed to the wide dissemination of such algorithms. In this regard, graph models and algorithms for combinatorial Miller-Morita-Mumford (MMM) can only be viewed as temporary (intermediate) step between realized in practice and promising solutions in meeting the complex demands made to the multiservice TCS.

4. Conclusions

The main task, which is proposed in the traffic engineering (TE) concept is the optimal loading of all sections of the network to improve the efficiency of network usage. This requirement implies the use of traffic through several mechanisms available paths network. Thus, the successful solution of the problem of engineering traffic in multiservice networks depends on the used routing mechanisms. An analysis of multipath routing models [11] [18] highlighted the two-class models graph and streaming. As shown by the analysis, within each class of mathematical models exist multipath models that involve free resources on the network to service the traffic. This allows more efficient use of available network resources.

Analysis of protocol solutions used in modern Tele-Communication System (TCS), showed that the practice received a graph model, implemented in the RIP, OSPF, EIGRP. These models offer the simplicity and low computational complexity. However, the limitations of the solutions obtained and a one-way orientation is not currently allowed effective use of all available network resources. These disadvantages can be overcome with the help of the latest developments [19] [20] in the framework of graph models, allowing you to extend the scope of these algorithms.

Using streaming routing models can distribute traffic over the network and use the resources available. Implementation complexity associated with a large amount of signal information and the potential instability of the routing algorithm for changing traffic characteristics, resulted in the absence to date of protocol implementation decisions based on this class of algorithms. At the same time, despite the lack of implementation of the protocol on the basis of flow routing models, the demands put forward to modern multiservice TCS may meet only with the use of this class of algorithms.

The proposed analysis in this paper shows that the full TE problem cannot be solved using the approaches proposed in only one of the classes, which means that the achieved solutions are either as graph [21] and [22] , although they do not take into account the possibility of flow distribution or streaming [15] and which only solves the problem of flow distribution. Obviously, for the dynamic distribution of information flows, these solutions are not suitable.

Cite this paper
Attar, H. (2017) Multipath Routing Mathematical Model to Solve the Traffic Engineering in Multi-Protocol Label Switching Network. Journal of Computer and Communications, 5, 113-122. doi: 10.4236/jcc.2017.514009.
References

[1]   Awduche, D.O. and Bijan J. (2002) Internet Traffic Engineering Using Multi-Protocol Label Switching (MPLS). Computer Networks, 40, 111-129.
https://doi.org/10.1016/S1389-1286(02)00269-4

[2]   Awduche, D., et al. (2002) Overview and Principles of Internet Traffic Engineering. No. RFC 3272.
https://doi.org/10.17487/rfc3272

[3]   Alhihi, M., Attar, H., Samour, M. and Akulynichev, A. (2017) Researching the Impact of Parameters of the Developed Routing Models on Network Performance. Studies in Engineering and Technology, 4, 61-69.
https://doi.org/10.11114/set.v4i1.2470

[4]   Alhihi, M. (2017) Setting an Optimization Problem of Distributing Traffic across Multiple Independent Paths. Transactions on Networks and Communications, 5, 44.
https://doi.org/10.14738/tnc.54.3346

[5]   Attar, H., Vukobratovic, D., Stankovic, L. and Stankovic, V. (2011) Performance Analysis of Node Cooperation with Network Coding in Wireless Sensor Networks. 4th IFIP International Conference on New Technologies, Mobility and Security, Paris, 7-10 February 2011, 1-4.
https://doi.org/10.1109/NTMS.2011.5721048

[6]   Attar, H., Stankovic, L. and Stankovic, V. (2014) Cooperative Network-Coding System for Wireless Sensor Networks. IET Communications, 6, 344-352.
https://doi.org/10.1049/iet-com.2011.0143

[7]   Attar, H., Stankovic, L., Alhihi, M. and Ameen, A. (2014) Deterministic Network Coding over Long Term Evaluation Advance Communication System. 4th International Conference on Digital Information and Communication Technology and Its Applications (DICTAP), Bangkok, 6-8 May 2014, 56-61.
https://doi.org/10.1109/DICTAP.2014.6821657

[8]   El-Hihi, M., Attar, H., Solyman, A. and Stankovic, L. (2016) Network Coding Cooperation Performance Analysis in Wireless Network over a Lossy Channel, M Users and a Destination Scenario, Communications and Network, 8, 257-280.
https://doi.org/10.4236/cn.2016.84023

[9]   Attar, H. (2017) Data Combination over Physical Layer Using Network Coding with PUM Turbo Codes. Journal of Computer and Communications, 5, 32-44.
https://doi.org/10.4236/jcc.2017.56002

[10]   Nazir, S., Stankovic, V., Attar, H., Stankovic, L. and Cheng, S. (2013) Relay-Assisted Rateless Layered Multiple Description Video Delivery. IEEE Journal on Selected Areas in Communications, 31, 1629-1637.
https://doi.org/10.1109/JSAC.2013.130824

[11]   Lemeshko, O.V., Hailan, A.M. and Starkova, O.V. (2011) Multi-Level Traffic Management in the MPLS-TE DiffServ Network. 11th International Conference the Experience of Designing and Application of CAD Systems in Microelectronics (CADSM), 118-120.

[12]   Waleed, S., Faizan, M., Iqbal, M. and Anis, M.I. (2017) Demonstration of Single Link Failure Recovery Using Bellman Ford and Dijikstra Algorithm in SDN. International Conference on Innovations in Electrical Engineering and Computational Technologies (ICIEECT), Karachi, 5-7 April 2017, 1-4.
https://doi.org/10.1109/ICIEECT.2017.7916533

[13]   Dela Cruz, J.C., Magwili, G.V., Mundo, J.P.E., Gregorio, G.P.B., Lamoca, M.L.L. and Villasenor, J.A. (2016) Items-Mapping and Route Optimization in a Grocery Store Using Dijkstra’s, Bellman-Ford and Floyd-Warshall Algorithms. IEEE Region 10 Conference (TENCON), Singapore, 22-25 November 2016, 243-246.

[14]   Awerbuch, B., Bar-Noy, A. and Gopal, M. (1994) Approximate Distributed Bellman-Ford Algorithms. IEEE Transactions on Communications, 42, 2515-2517.
https://doi.org/10.1109/26.310604

[15]   Ben-Ameur, W., et al. (2001) Routing Strategies for IP Networks. Telektronikk, 97, 145-158.

[16]   Leduc, G., et al. (2006) An Open Source Traffic Engineering Toolbox. Computer Communications, 29, 593-610.
https://doi.org/10.1016/j.comcom.2005.06.010

[17]   Skivée, F., Balon, S. and Leduc, G. (2006) A Scalable Heuristic for Hybrid IGP/MPLS Traffic Engineering—Case Study on an Operational Network. IEEE International Conference on Networks (ICON), Vol. 2, Singapore, 13-15 September 2006, 572-577.
https://doi.org/10.1109/ICON.2006.302621

[18]   Abu-Ali, N., Mouftah, H.T. and Gazor, S. (2005) Multi-Path Traffic Engineering Distributed VPLS Routing Algorithm. Proceedings of Systems Communications, 14-17 August 2005, Montreal, 275-280.

[19]   Natalie, D., et al. (2003) Inter-Area Traffic Engineering in a Differentiated Services Network. Journal of Network and Systems Management, 11, 427-445.
https://doi.org/10.1023/B:JONS.0000005472.61905.ca

[20]   Chang, L.-H., et al. (2013) QoS-Aware Path Switching for VoIP Traffic Using SCTP. Computer Standards & Interfaces, 35, 158-169.
https://doi.org/10.1016/j.csi.2012.06.003

[21]   Vutukury, S. and Garcia-Luna-Aceves, J.J. (2001) MDVA: A Distance-Vector Multipath Routing Protocol. Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies, Anchorage, AK, 22-26 April 2001, 557-564.

[22]   Vutukury, S. and Garcia-Luna-Aceves, J.J. (2001) MPATH: A Loop-Free Multipath Routing Algorithm. Elsevier Journal of Microprocessors and Microsystems, 24, 319-327.
https://doi.org/10.1016/S0141-9331(00)00086-7

 
 
Top