Multipath Routing Mathematical Model to Solve the Traffic Engineering in Multi-Protocol Label Switching Network

Show more

1. Introduction

Modern telecommunication networks of the new generation, i.e., Next Generation Network (NGN), in accordance with the trend of the global communications industry, should be built as a multi-service network with a certain Quality of Service (QoS) traffic polytypic users. Multipath Protocol Label Switching (MPLS) is a routing mechanism used to achieve the required QoS in the modern telecommunication networks, where the traffic management, routing and switching operations are considered as the main parameters for the Traffic Engineering (TE) concepts [1] [2] , where TE is identified as the matter to optimize the distribution of the network data flow.

In [3] , the QoS for hybrid telecommunication network is achieved by developing an adaptive routing method, where in [4] the optimum utilization for the resources of networks is investigated to achieve communication models accuracy that provides the required performance by improving the routing protocols.

However, the network performance was improved in different ways than the routing methods, such as applying network coding as in [5] [6] [7] , which shows that decreasing the number of the transmitted packets does improve the telecommunication traffic significantly in different applications such as wireless sensor network [5] [6] , and long term evaluation advance mobile communication network [7] . General understanding and analysis for applying network coding in cooperative networks over lossy channels with the improvement of traffic is shown in [8] [9] .

In [10] , the author proposed rateless layered for multiple description video delivery through a relay, and it showed as well how the proposed scenario exploited the path delivery over a mobile network to show the advantages of the relaying when the network is optimized intern of routing and the unequal error detection.

In this paper, an effective multipath routing mathematical model is developed which is derived from different existed multipath routing mechanisms to ensure obtaining the desired QoS and loading balance according to the Tele-Communication Systems (TCS) resources, and hence reaching the most effective TE, which is called the optimum TE. The optimum TE is the main requirement to improve the network usage efficiency. Accordingly, during the wireless communication system where one packet can be simultaneously transmitted along multiple paths, the optimum TE is providing balanced loading and helping to improve the TCR, especially high-speed and associated likelihood-time quality of service indicators.

The rest of the paper is organized as following: in Section 2, the multipath routing solution general requirements is discussed, with the classification of the mathematical models of routing; Section 3 provides the required back ground for Grafokombinatornye routing algorithms and models; Then, the mathematical optimization algorithm is obtained and its theoretical results are provided through the relative equations; and finally, the paper concludes.

2. General Requirements for the Solutions of the Multipath Routing Problems

Multipath routing requirements are listed in two groups of demands: the first group of demands is devoted for any traditional routing algorithms which are assumed to have low computational complexity, fast convergence and minimum volumes of traffic generated by the service; the second group of requirements is needed to ensure the desired QoS and load balancing TCS based on the implementation of the previously mentioned principles for the traffic management concepts. The Classification of mathematical routing models is deduced from the analytical results of [11] , which provide the main approaches to the mathematical modeling and solving the multipath routing tasks.

Figure 1 shows the classifications of the mathematical models and routing algorithm, which is divided in to two models; graph combinatorial (Grafokombinatornye routing) and streaming models.

The basis of the graph models used in the mathematical description of TCS, as a directed or undirected graph, where both are using combinatorial algorithms to search for the shortest paths or multipath between any given pairs of nodes (vertices) in the network. Flow models together with the calculation of the path routs numbers are used to formalize the required user traffic distribution decision problem along these routes.

Due to the fact that the above routing algorithm requirements are regarded as contradictory; it is essentially important to propose a number of approaches for the purposes of formalization and solving multipath routing tasks based on the use of various mathematical modeling and solution algorithms, resulting in one form or another optimization problems, which is the main goal of this paper. As a result, the solution of TE for MPLS-TE networks in the framework of a mathematical model is impossible to be obtained by just one optimum path routing that can be applied for all types of routing algorithms. As a result, a hybrid approach, combining the approaches and algorithms that are typical for different routing models.

3. Grafokombinatornye Routing Algorithms and Models

To solve the problem of finding the shortest path for a given TCR represented as a graph algorithms i.e., Grafokombinatorny, several algorithms have been

Figure 1. Routing algorithms and mathematical models classifications.

proposed such as Bellman-Ford, Dijkstra and Floyd-Warshall as applied recently in [12] [13] in different applications.

The basic idea of the Bellman-Ford algorithm is to find the first path length [14] , while Kratchayshih provided the path that contains not more than one arc in the shortest path length, and then the path that does not contain more than two arcs, etc. The chosen shortest path is the path that contains not more than h arcs will be called the shortest (≤h) means.

Assume that node 1 is the source node, and it is needed to find the length of the shortest paths from this source to the other nodes in the graph. It is known that the arc length (arc parameters) depends on the particular task and it can be both positive or negative. In the proposed scenario; the negative values can be calculated. Additionally, the path column must not be cycles. Let D_{i} to be the length of the shortest path (≤h) from node 1 to node i, assume that D_{i} = 0 for all h. Finding the shortest path consists of several stages. In the first stage of the algorithm; it should be:

${D}_{i}\left(h\right)=\infty \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{for}\text{\hspace{0.05em}}\text{\hspace{0.17em}}\text{all}\text{\hspace{0.17em}}\text{\hspace{0.05em}}i\ne 1\text{\hspace{0.17em}}\text{\hspace{0.05em}}\text{and}\text{\hspace{0.17em}}\text{\hspace{0.05em}}{D}_{1}\left(h\right)=0$ (1)

In the subsequent steps, each time h ≥ 1 iterates Bellman-Ford

${D}_{i}^{\left(h\right)}=\mathrm{min}\left[{D}_{j}^{\left(h-1\right)}\left(h-1\right)+{D}_{ij}\right]\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{for}\text{\hspace{0.17em}}\text{all}\text{\hspace{0.17em}}i\ne 1$ (2)

where D_{ij} is the shortest path between the nodes i and j. The algorithm terminates when h reaches n, where n is the number of nodes in the network, i.e., in the worst case, the tree of shortest routes is given chain with length of n − 1 branches.

The shortest path in the algorithm of Bellman-Ford becomes positive is because when the lengths of all arcs are positive (initial D_{i} conditions for i ≠ 1 may take any non-negative numbers), the iteration Equation (1) may be performed in parallel for different nodes substantially randomly, i.e., both synchronously and asynchronously.

Another widely used graph algorithm for finding the shortest path is Dijkstra’s algorithm [12] [13] which allows building a tree of the shortest distances and paths from a given node to all the others. The algorithm is applicable for oriented, non-oriented and mixed network graphs. According to this algorithm, the shortest among all the shortest paths from node i is one arc length, which connects this node i to the next adjacent node. Since each path consists of several arcs; it will always be longer path than the first length of the 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 D_{i}, 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}, D_{1} = 0 and D_{j} = D_{1j} for j ≠ 1.

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

${D}_{i}=\underset{j\notin P}{\mathrm{min}}{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\notin P$

${D}_{j}:=\mathrm{min}\left[{D}_{j},{D}_{i}+{d}_{ij}\right]$ (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 N^{2}, instead of N^{3}, 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}=\left\{\left(m,n\right)|n\in {S}_{j}^{m},m\in M\right\}$ (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}=\left\{k\in {M}^{i}|{D}_{jk}^{i}<{D}_{j}^{i}\right\}$ (6)

where ${D}_{jk}^{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}\left(t\right)\le {D}_{ji}^{k}\left(t\right),\text{\hspace{0.17em}}\text{\hspace{0.17em}}k\in {M}^{i}$ (7)

${S}_{j}^{i}\left(t\right)=\left\{k\in {M}^{i}|{D}_{jk}^{i}\left(t\right)<F{D}_{j}^{i}\left(t\right)\right\}$ , (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}_{ji}^{k},\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall i,j,k\in {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}_{\mathrm{min}}^{ij}=\mathrm{min}\left\{{D}_{jk}^{i}+{l}_{k}^{i}|k\in {M}^{i}\right\}$ (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}=\left\{k\in {M}^{i}|{\stackrel{\u02dc}{D}}_{jk}^{i*}<\mathrm{min}\left(F{D}_{j}^{i},{D}_{\mathrm{min}}^{ij}\right)\right\}$ (11)

where ${\stackrel{\u02dc}{D}}_{jk}^{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}\left(t\right)=\left\{k\in {M}^{i}|{D}_{jk}^{i}\left(t\right)<F{D}_{j}^{i}\left(t\right)\right\}$ (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}_{jk}^{i}$ from a neighboring node k, and the response status flag $S{T}_{jk}^{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\in {M}^{i}$ can be selected as the primary under the conditions of Equation (13), and Equation (14):

${D}_{jq}^{i}\left(t\right)+{l}_{q}^{i}\left(t\right)=\mathrm{min}\left\{{D}_{jx}^{i}\left(t\right)+{l}_{x}^{i},\forall x\in {M}^{i}\right\}$ (13)

${D}_{jq}^{i}\left(t\right)<F{D}_{j}^{i}\left(t\right)$ , where $F{D}_{j}^{i}\left(t\right)={D}_{j}^{*i}\left(t\right)$ (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.

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