Share This Article:

A Mathematical Model for Managing the Distribution of Information Flows for MPLS-TE Networks under Critical Conditions

Full-Text HTML XML Download Download as PDF (Size:1014KB) PP. 31-42
DOI: 10.4236/cn.2018.102003    305 Downloads   586 Views  


The optimal load distribution over a set of independent paths for Multi-Protocol Label Switching for Traffic Engineering (MPLS-TE) networks is regarded as important issue; accordingly, this paper has developed a mathematical method of optimal procedures for choosing the shortest path. As a criterion for choosing the number of paths, a composite criterion is used that takes into account several parameters such as total path capacity and maximum path delay. The mathematical analysis of using the developed method is carried out, and the simulation results show that there are a limited number of the most significant routes that can maximize the composite quality of service indicator, which depends on the network connectivity and the amount of the traffic. The developed technological proposals allow increasing the utilization factor of the network by 20%.

1. Introduction

The telecommunication network traffic is regarded as casual and non-stationary, accordingly, the network becomes overloaded in certain elements and areas and less overloaded in others. This leads to critical situations that require measures to re-distribute the traffic over the network which is not sufficiently investigated, and the available technologies do not provide effective solutions for network restoration.

In [1] , mathematical model was proposed for Multi-Protocol Label Switching for Traffic Engineering (MPLS-TE) to improve the Quality of Service (QoS) providing the mathematical limits when optimum traffic distribution is assumed. In [2] , the optimum number of routing paths was investigated for MPLS-TE, as a result, the optimum number of the shortest independent paths was theoretically determined, while in [3] , the parameters to develop the routing performance are investigated.

In [4] , both of multipath routing and traffic distribution were investigated and optimum solution is proposed to find the shortest path using Dijkstra and Bellman-Ford algorithm. Interesting and useful comparative analysis for various routing strategies is produced in [5] with the relative proposed framework models.

More important and useful resent published work in this field is shown in [6] [7] and the references there in.

When the network becomes in a critical situation in term of traffic limit and hence the network performance; there are two ways to solve this obstacle which are:

・ Load limiting technique, and

・ Load redistribution technique which takes into account the availability of the network resources.

The load redistribution technique is directed linked to the QoS allowed in the network and usually it is recommended for practical use.

The task of network recovery in critical situations, due to its non-stationarity, can be solved based on the management of the corresponding resources, using the procedure of recursive estimation of the traffic state. The control algorithm in this case can be constructed using the results of the separation theorem that is with the possibility of a linear solution and the Gaussian nature of the estimated process of traffic changes. This algorithm is implemented in the form of a sequence of two separate procedures which are: Optimal stochastic estimation of the network state and the deterministic linear control of network resources, taking into consideration that the obtained stochastic estimation is considered as the control parameter. In this paper, the qualitative characteristics of the evaluation, the structure of control algorithms are obtained and recommendations are given on the choice of the parameters of these algorithms.

As evaluation algorithms, it is recommended to select Kalman-Bucy filtration procedures that are optimal in the sense of the minimum mean-square error of the estimate. However, the direct use of these algorithms due to the non-stationary nature of the situation is unacceptable, because the use of model identification and adaptation procedures will lead to an excessively cumbersome task (curse of dimension) and will require additional channel resources. A more rational solution is to choose a higher rate of processing the observation results, so that the convergence time of the procedure is significantly less than the interval of the quasi-stationary nature of the estimated process, which is estimated to be parts of seconds. Calculated data on the feasibility of computing devices of the required productivity are obtained in this paper.

The rest of the paper is arranged to be presented in four sections, where in Section 2, the mechanism of MPLS-TE optimizing load balance is produced. In

Section 3, selecting the information distribution flow method is proposed. In 4, the load control model for the proposed work is shown before concluding the paper work in 5.

2. The Mechanisms of Optimizing the Load Balance in MPLS-TE Networks

The recovery procedures are offered in most modern transport technologies such as the Automatic Protection Switching in SDH, however, only MPLS-TE has a possibility of resource optimization after network recovery. The applicable types of optimization nowadays are:

1) Periodic optimization;

2) On-demand optimization;

3) Event-based optimization.

In most hardware devices, there is a time interval for optimizing the tunnel. This is done to find a better way to meet traffic restrictions and requirements. In Cisco routers [8] , a default value of this interval is one hour and can be changed in the range of (0 to 604,800) seconds.

On-demand optimization is used very rarely in practice and is only needed in particular cases, such as, after creating several tunnels on a working network, it is necessary to check whether there is a better way to service traffic, which guarantees less delay than the existing one.

Load balancing optimization should be performed whenever there is a better way to send traffic with the specified service parameters. Therefore, in case of event-based optimization, the search for the optimal path is made each time a specified event occurs, such as a new path appears on the network.

Figure 1(a) & Figure 1(b) shows a situation where a failure in the network leads to a non-optimal use of network resources, assuming that all channels in the considered network have the same bandwidth. In the MPLS-TE network; there are two tunnels: A-B-E and A-B-D. To protect the tunnel A-B-E, a bypass B-D-E was created. This virtual path is in a waiting state and is only used if the section between B-E is inoperative. In case of failure of the network section B-E, rerouting procedures will switch traffic to the bypass B-D-E. In general, as a result of network recovery after a failure, using of network resources may not be optimal, because of what some resources will be overloaded, and some will not

Figure 1. Switching to the bypass tunnel in case of failure of the communication channel.

be used at all (Figure 1(b)). Obviously, in this situation, it is necessary to optimize the distribution of network resources, while taking into account the time limitations of the procedure.

It is important to notice that there is no other technique is applied in this network, which makes it possible to improve this technique when applying network coding technique such as used in [9] [10] [11] [12] to improve the network reliability when one or more baths are out of service.

In fact, [11] [12] provided a solution in the case of a dead channel between two nodes.

3. Selecting the Method of Information Flows Distribution

As explained in Section 2; in the case of critical network operation, it is necessary to carry out the load redistribution from separate sites for a limited and predetermined time. In general, the problem of optimal distribution of information flows is NP-complete, and its application in the case of a critical operating mode is regarded as difficult problem to solve. More the constructive and realizable in practice are regarded as rational methods, which fall in two main methods:

・ Traffic limitation method: The method is rather constructive, it is often used, but in many cases, it is unacceptable because of the possible increase in the loss of data packets and the quality of multimedia services deterioration.

・ Traffic redistribution method: This method is implemented in the presence of redundant paths. Modern networks are built in such a way that unused bypasses are always there, and their resources can be used in case of overloading the main paths.

The proposed work in this paper applies the second method as it is more constructive in term of the QoS limitation conditions. In order to circumvent the NP-completeness of the traffic redistribution task; a heuristic algorithm that minimizes network congestion when the specified conditions are met, is proposed.

The idea of the algorithm is as follows: It is intended to use a centralized strategy to manage the whole or a fragment of the network (Figure 2). First, the

Figure 2. Construction of a matrix of given loads in the case of a centralized control strategy.

given values of the load are found, on the basis of which a matrix with a zero diagonal (1) is constructed.

T ^ i j = [ 0 T ^ 12 T ^ 13 T ^ 14 T ^ 21 0 T ^ 23 T ^ 24 T ^ 31 T ^ 32 0 T ^ 34 T ^ 41 T ^ 42 T ^ 43 0 ] (1)

Non-diagonal elements are thus the given load of the corresponding communication direction in the network T ^ i j , which is defined as

T ^ i j = T i j ( t ) v i j , (2)

where T i j is the corresponding load at time t, v i j is the throughput of the communication channel ij. Further, on each subsequent time interval the load is redistributed from the most loaded channels ij to the unloaded bypasses consisting of two sections: ik and kj. There can be more than two such sections. The proposed algorithm can be used both for the case of a fully connected network and for a network of arbitrary connectivity. The constraints on connectivity are not fundamental and do not affect the algorithm as a whole. It should be noted that, in the framework of MPLS-TE technology proposed in [13] [14] [15] where the full connectivity of the network can be achieved on the basis of logical methods, i.e. tunnels (virtual channels) between all inputs and outputs of distributed elements can be formed, which leads to complete connectivity. The great advantage of this method of redistribution is that it allows not only preventing network congestion, but also ensures the restoration of the network operability after failures of individual elements and directions of communication.

4. Load Control Model for TCN

To solve load balancing tasks, constant monitoring and control of the load level are carried out, which occurs as follows:

・ Packets sent to the interface n n are counted;

・ The obtained values n n serve to generate averaged data n ^ n about the load for a certain interval of observation time τ n τ к с :

n ^ n = 1 n n = 1 n n n . (3)

The interval τ n = Δ t n should be chosen based on the condition τ n τ к с which is the period of traffic quasi-stationary, which is a few seconds. A recursive estimate, which is more adaptive and consistent with management tasks, can be more adequate in conditions of nonstationarity:

・ Critical mode thresholds are entered, on reaching which re-routing and load re-distribution are implemented.

Since the traffic parameters are monitored with a certain error, the resulting sample n n ( k ) is subject to statistical processing:

n ^ n ( k ) = n n ( k ) ± Δ n n ( k ) . (4)

In addition, the presence of various disturbing random factors such as delays, sampling errors, and no stationary of the load itself, which leads to the fact that the observation results should be interpreted as a sequence of readings x ( k ) observed against a background of random interference n n ( k ) = ν ( k ) :

y ( k ) = x ( k ) + ν ( k ) , (5)

where the dimension of the observation vector dim ( y ( k ) ) corresponds to the number of controlled directions. The level of cumulative errors of random interference ν ( k ) is characterized by the power spectral density V γ . The value V γ is of a formal nature and determines the level of all the interfering factors

that lead to measurement errors. However, in practice, the relative value V x V γ is considered as important, where V x is the power spectral density of the useful estimated signal x ( k ) . The value V x V γ is interpreted in standard communication tasks as the signal-to-noise value P c P ø . In essence, x ( k ) displays the traffic state, and, given that the network processes the traffic, it’s adequately displayed in the network state.

Evaluation of the process x ( k ) = ( x 1 , x 2 , , x k ) can be obtained by the known formula:

x ^ ( k ) = 1 k k = 1 k x ( k ) . (6)

At the same time, this estimate (6) is effective and unbiased only for stationary processes of ergodic type. To estimate non-stationary traffic parameters, a recursive estimate, obtained by the stochastic approximation method [16] or, in the general case, by the Kalman-Bucy filtration method [16] , is more suitable. The time interval Δ t = t ( k + 1 ) t ( k ) between sample values should be chosen so that our interval of quasi-stationarity τ к с Δ t . Practice shows that the ratio Δ t / τ к с = 0.01 0.1 is appropriate, while Δ t should be 0.05 0.5 sec.

Consider the set of nodes in the telecommunications network exchanging information as in Figure 3. Any modern network can function successfully and steadily if the network management system, for example the TMN system, copes with the current traffic changes. Such control of the structure and state can be performed both by the whole and part of the system. In this case, the management u ( t ) itself is a component of the state x ( k ) . A mathematical model that reflects the dynamics of a state can be described by a differential equation [17] :

d x ( k ) d t = F ( t ) x ( t ) + j B j ( t ) u j ( t ) + G ( t ) w ( t ) , (7)

where F(t), B(t), and G(t) are the matrices of state, control, and excitation, respectively, u ( t ) is a vector of controllable parameters, and w ( t ) is a vector of virtual noise with a level E [ w ( k ) w T ( k ) ] = V w . Physically, the interpretation of

Figure 3. Structure of centralized management of distributed network elements.

the matrix coefficients occurring in Equation (7) is as follows: F(t) displays the rate of change of state by elements of the matrix; elements of the matrix F(t) are the inverse of the correlation intervals of random states F i j = 1 / τ к о р . G(t) displays the level of random changes of this traffic. For purely deterministic states with constant loads, G(t) = 0. B(t) determines the level of controlled impacts.

For a discrete system, the analogue of Equation (7), respectively, has the following form:

x ( k + 1 ) = F ( k ) x ( k ) + j B j ( k ) u j ( k ) + G ( k ) w ( k ) . (8)

The optimal solution, which allows obtaining a real-time recursive estimation satisfying the minimum mean-square deviation criterion shown in Equation (9) is the Kalman-Bucy procedure, which is presented in Equation (10)

J = min E ( x ( k ) x ^ ( k ) ) 2 , (9)

x ^ ( k ) = x ^ ( k | k 1 ) + K ( k ) [ y ( k ) H ( k ) x ^ ( k | k 1 ) ] , (10)

where K ( k ) = V x ˜ ( k | k 1 ) H T ( H V x ˜ ( k | k 1 ) H ( t ) V ν ( k ) ) 1 and

V x ˜ ( k | k 1 ) = O ^ ( k ) [ I K ( k ) H ] V x ˜ ( k | k 1 ) O ^ T ( k ) + V W ( k ) is an a posteriori variance of the prediction error, V x ˜ ( k ) is an a posteriori variance of the estimation error, and V x ˜ ( k ) = [ I K ( k ) H ( k ) ] V x ˜ ( k | k 1 ) . The direct use of the estimate (10) is not always possible for telecommunication networks that are distributed, since delays in the control loop τ з а д can reach values that commensurate with the selected sample intervals Δ t or even exceed them. Under these conditions, management can be synthesized according to the forecast only. The forecast value is:

x ^ ( k | k 1 ) = O ^ ( k , k 1 ) x ^ ( k ) + j B j u j ( k ) , (11)

where B j determines the control value in the j direction of the communication.

The estimation error V x ˜ ( k ) and a one-step ahead forecast error are respectively determined by the relations V x ˜ ( k ) = E [ x ( k ) x ^ ( k ) ] [ x ( k + 1 ) x ^ ( k ) ] T and V x ˜ ( k | k 1 ) = E [ x ( k ) x ^ ( k | k 1 ) ] [ x ( k + 1 ) x ^ ( k | k 1 ) ] T .

It is characteristic that the forecast x ^ ( k | k 1 ) is determined at the same steps of discrediting. Obviously, the forecast is always less accurate than the estimate. It follows from the definition that the errors of this forecast are determined by the values

O ^ ( k , k 1 ) = e Δ t τ к о р , (12)

where Δ t is the step of discrediting, τ к о р is the interval of the process correlation x ( k ) . It’s obvious that for the less inertial state changes x ( t ) , for which τ к о р i > τ к о р j at the same Δ t , the forecast error will be greater than for the more inertial ones. Accordingly, the estimate (10) will also be worsened. Figure 4 shows the dependence of the relative forecast error (11) on the delay value in the control loop. Since the forecast accuracy decreases with increasing τ з а д , in cases where delays in the network reach significant values, the control procedures may prove ineffective. In these cases, it is needed to switch to a management that operates on the mean of traffic changes or equips the network with more resources. In practice, the delay value τ з а д commensurate or exceeds the correlation interval τ к о р rarely. Note that for time-invariant states x ( t ) = const the estimate and, accordingly, the forecast can also be obtained asymptotically, with absolute accuracy while t . Unfortunately, this situation is not real in communication practice.

Figure 4. Graph of the dependence of the relative forecast error on the delay value in the control loop.

Consider other dependencies related to the accuracy of estimation and prediction. This accuracy can be determined by a ratio of the a priori and a posteriori variance of the estimates V x ˜ ( k ) / V w ( k ) and is determined by the variance of the process x ( k ) itself or by the value V w .

At a known ratio of signal-to-noise ( P c / P ø ) levels in the observation channel, the ratio of the a posteriori and a priori variances is calculated by the formula:

E k = ( N 1 ) ( N 2 ) 2 + 3 N 2 + N 10 2 + 6 N ( N 2 ) + 3 N ( N 1 ) 2

V x ˜ ( k ) V w = 2 1 + 1 + P c P ø . (13)

It is logical to consider the relation (13) for the case of a steady state when the transient processes are completed, that is when V x ˜ ( k ) V x ˜ ( ) . The graph of (13) dependence is presented in Figure 5.

Let us find the optimal control law for the u ( k ) . It is known from the optimal control theory [17] that the value u o p t ( k ) is found by minimizing the Hamiltonian along the optimal trajectory. The optimal control for the i-th node is given by the criterion

J i = E { k = 0 N 1 [ x T ( k ) P i x ( k ) + j = 1 M u j T ( k ) Q i j u j ( k ) ] + x T ( N ) P i x ( N ) } . (14)

The terms of (14) functional have an important physical interpretation. The last term ensures the minimum state deviations of x from the optimal trajectory at the final instant of time x ( N ) . The first term in square brackets ensures

Figure 5. Graph of the dependence of the relative error of the random process estimation on the signal-to-noise ratio.

the minimization of the mean-square state spreads along the entire path of the system’s motion. The sum of the terms containing Q i j minimizes management costs. The last term is important in the case when one or another type of energy is spent on the management implementation. When these energy inputs are not important, the middle term can be omitted.

Let for each of the M nodes a solution is obtained minimizing (14) exponent, which is a set of strategies { g 1 * , g 2 * , , g M * } is obtained:

J i ( g 1 * , g 2 * , , g M * ) J j , g j . (15)

Taking into account (14) criterion, the system control trajectory (8) can be analyzed in reverse time, beginning with the last step N 1 , where L i ( N ) = P i :

L i ( k ) = P i + O ^ T [ ( I + j B j B j T L j ( k + 1 ) ) 1 ] T [ L i ( k + 1 ) + j L j ( k + 1 ) B j Q i j B j T L j ( k + 1 ) ] [ I + j B j B j T L j ( k + 1 ) ] 1 O ^ (16)

It can be shown that optimal control is realized in the form of a linear procedure [18] [19] [20] [21] :

u o p t ( k ) = D ( k ) x ^ ( k ) . (17)

An equation satisfying condition (4.15) exists and is unique [17] if for every step k there is an inverse value in the square brackets of the expression:

D ( k ) = B i T L i ( k + 1 ) [ I + j B j ( k ) B j T ( k ) L j ( k + 1 ) ] 1 F ( k ) . (18)

It follows from (18) that the coefficient D i ( k ) does not depend on the results of (8) observation. This can only be when exactly these D i ( k ) quantities should be involved in this control procedure, provided that we have complete information on the load status of neighboring nodes and use closed-loop control strategies without delays in all directions. Thus, the costs J i ( k ) are completely determined by the V w / V x relation, respectively characterizing the a priori variance of the useful estimated signal and the inertial i-th direction, which is characterized by the value O ^ i ( k , k 1 ) enclosed in the state matrix values O ^ ( k ) .

In our linear model (8), leading to the solution of (17), disturbing factors are changes in the real-time traffic. It is obvious that a random process x ( t ) or a discrete-time one x ( k ) can be approximated by the normal probability distribution law w ( x ) N [ m x , σ x 2 ] , since it itself is formed as the sum of many independent factors―communication requests. This allows us to apply the separation theorem [18] to the control implementation. Its essence is that the optimal control itself (16) is a deterministic procedure which includes an optimal mean square estimate x ^ ( t ) .

This number depends on the network connectivity and traffic amount and allows you to maximize the composite quality-of-service indicator. The developed technological proposals allow increasing the network utilization rate by 20%.

5. Conclusion

The procedure for estimating the amount of the redistributed load is obtained, which guarantees the prevention of overloading of network nodes. As the redistribution coefficient, the value 0.2 of the reduced flux is justified. The procedure is a patio-temporal organization of calculations, where redistribution is performed at all ( i x ) directions of communication at each k M step, and then a forecast is given for the k + 1 step. And there is an optimal ratio of redistributed flows across all sections of the network. The state of the controlled section in the transient state is analyzed. Recommendations are given for choosing the sampling step Δ t , which can be within the limits. The proposed heuristic algorithm for the redistribution of information flows can be used for various network configurations

Conflicts of Interest

The authors declare no conflicts of interest.

Cite this paper

Attar, H., Alhihi, M., Samour, M., Solyman, A.A.A., Igorovich,S.S., Georgievna, K.N. and Khalil, F.(2018) A Mathematical Model for Managing the Distribution of Information Flows for MPLS-TE Networks under Critical Conditions. Communications and Network, 10, 31-42. doi: 10.4236/cn.2018.102003.


[1] 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.
[2] Alhihi, M., Khosravi, M.R., Attar, H. and Samour, M. (2017) Determining the Optimum Number of Paths for Realization of Multi path Routing in MPLS TE Networks. Telkomnika, 15, 1701-1709.
[3] Alhihi, M., et al. (2017) Researching Impact of Parameters of the Developed Routing Models on Network Performance. Studies in Engineering and Technology, 4, 61-69.
[4] Alhihi, M. (2017) Method of Distribution Network Resources after Restoration, the Networks MPLS-TE Use of Various Telecommunications Technologies to Construct Backbone Networks. International Journal of Communications, Network and System Sciences, 10, 251-260.
[5] Alhihi, M. (2017) Comparative Analysis of Various Routing Strategies in the Framework of the Proposed Models. International Journal of Innovative Research in Computer and Communication Engineering, 5, 10439.
[6] Alhihi, M. (2017) Setting an Optimization Problem of Distributing Traffic Across Multiple Independent Paths. Transactions on Networks and Communications, 5, 40.
[7] Alhihi, M. (2017) Practical Routing Protocol Models to Improve Network Performance and Adequacy. Journal of Computer and Communications, 5, 114-124.
[8] Alwayn, V. (2004) Advanced MPLS Design and Implementation: Translated from English, M. “Williams” Publishing House, Chicago, 480 p.
[9] El-Hihi, M. and 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.
[10] Attar, H. (2017) Data Combination over Physical Layer Using Network Coding with PUM Turbo Codes. Journal of Computer and Communications, 5, 32-44.
[11] Attar, H., Stankovic, L. and Stankovic, V. (2009) Physical-Layer NC Based on PUM Turbo Codes. IEEE Mosharaka International Conference on Communications, Signals and Coding, Amman, 6-8 February 2009.
[12] Attar, H., Vukobratovic, D., Stankovic, L. and Stankovic, V. (2011) Performance Analysis of Node Cooperation with NC in Wireless Sensor Networks. 4th IEEE International Conference on New Technologies, Mobility and Security, Paris, 7-10 February 2011.
[13] Romanov, A.I. and Gol, V.D. (2005) Analysis of Methods for the Accurate Evaluation of the Survivability of Telecommunication Networks. In: All-Ukrainian Interdepartmental Scientific and Technical Collection “Radio Engineering”, KhNURE, Kharkov, No. 144. 80-88.
[14] Apostolopoulos, G., Guerin, R., Kamat, S., et al. (1999) Improving QoS Routing Performance under Inaccurate Link State. Proceedings of the 16th International Teletraffic Congress, Edinburgh, 7-11 June 1999.
[15] Vutukury, S. and Garcia-Luna-Aceves, J.J. (2001) MPATH: A Loop-Free Multipath Routing Algorithm. Journal of Microprocessors and Microsystems, 24, 319-327.
[16] Reklaitis, G., Ravindran, A. and Ragsdell, K. (1986) Engineering Optimization: Translated from English. M.: “Mir” Publishing House, Moscow, 455 p.
[17] Minieka, E. (1981) Optimization Algorithms for Networks and Graphs: Translated from English. M.: “Mir” Publishing House, Moscow, 324 p.
[18] Amosov, A.A. and Kolenechenko, A.М. (1980) Streaming Algorithms for Controlling the Non-Stationary Communication Networks. The 5th All-Union School Seminar on Computer Networks, Part 2, Moscow-Vladivostok, 13-16 February 1980, 13-18.
[19] Alhihi, M. and Khosravi, M.R. (2018) Operating Task Redistribution in Hyperconverged Networks. International Journal of Electrical and Computer Engineering, 8.
[20] Alhihi, M. and Khosravi, M.R. (2018) Formulizing the Fuzzy Rule for Takagi-Sugeno Model in Network Traffic Control. The Open Electrical & Electronic Engineering Journal, 12, 1-11.
[21] Alhihi, M. (2017) Using the Clonal Selection Algorithm for the Synthesis of the Topological Structure for Data Network. Jordan Journal of Electrical Engineering, 3, 260-268.,%20no.%204,%20pp.%20260-268.pdf

comments powered by Disqus

Copyright © 2018 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.