_{1}

^{*}

Multipath Protocol Label Switching (MPLS) is a routing mechanism (technology) used in modern telecommunication networks, which is built as a multi-service network with a certain Quality of Service (QoS). To maintain the required QoS in such complicated networks, the Traffic Engineering (TE) should be equipped with optimum traffic management, routing mechanism, and switching operations, which are what this paper tackles, where the TE is identified as the optimal distribution of flows in the existing network. In this paper, an effective multipath routing mathematical model is developed based on several previous mechanisms to ensure the guaranteed desired QoS and loading balance according to the Telecommunication Network Systems (TCS) resources, to achieve the optimum TE, and hence improving the network usage efficiency. Moreover, the obtained mathematical optimization algorithm results are provided through the relative equations. Indeed the developed routing mathematical model in this paper is suitable for the dynamic distribution of information flows, which is the main improvement in the TE achieved in this work.

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 [

In [

However, the network performance was improved in different ways than the routing methods, such as applying network coding as in [

In [

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.

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 [

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.

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

proposed such as Bellman-Ford, Dijkstra and Floyd-Warshall as applied recently in [

The basic idea of the Bellman-Ford algorithm is to find the first path length [

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 ( h ) = ∞ for all i ≠ 1 and D 1 ( h ) = 0 (1)

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

D i ( h ) = min [ D j ( h − 1 ) ( h − 1 ) + D i j ] for all i ≠ 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 [_{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 ∉ 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 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 [

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) [

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.

According to the algorithm ROAM [

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.

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 [

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 [

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 [

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. https://doi.org/10.4236/jcc.2017.514009