J. Cent. South Univ. Technol. (2010) 17: 1258-1263

DOI: 10.1007/s11771-010-0629-7

A coarse-grained differentiated routing algorithm in multi-protocol label switching traffic engineering

DU Li(杜荔), YU Jun-xiang(于军相), WANG Xiao-jing(王晓静)

College of Information Science and Engineering, Northeastern University, Shenyang 110004, China

? Central South University Press and Springer-Verlag Berlin Heidelberg 2010

Key words:

multi-protocol label switching (MPLS); traffic engineering; constraint-based routing; explicit routing；

1 Introduction

Internet has brought revolutionary changes for the world, the emerging voice, video and other multimedia services on the network have put forward higher requirements. It is hard to meet these demands just by adding more infrastructures to extend the capacity of the network. Hence, it is more important to improve the current transmission technology while adding the network resource. Multi-protocol label switching  (MPLS) technology [1] is proposed based on the needs of network development as well as the applicable experience of many mature technologies. It makes full use of the advantage of the switch function and traffic management of the second layer and the flexible routing function of the third layer. The traffic engineering based on MPLS is generally regarded as the mainstream technology, which will be used in the next generation network. The combination of MPLS and traffic engineering makes it possible to provide connection- oriented service in traditional connectionless IP network [2]. Traffic engineering [3-4] has attracted much attention of researchers since it has been proposed, and its implementation can be directly used to relieve the network congestion and distribute the network resource reasonably. In addition, it can achieve the quality of service (QoS) [5] guarantee indirectly. Dynamic routing algorithm in traffic engineering is the most important part of the traffic engineering routing module [6-7]. The thesis deploys around traffic engineering, explores the advantage of MPLS to realize traffic engineering (TE) combined with existing routing algorithms [8] and the contribution that MPLS TE improves the network performance and satisfies the QoS.

In this work, a new routing algorithm with DiffServ-Aware, coarse-grained differentiated least interference routing algorithm (CDLI) was presented via analyzing minimum interference routing algorithm (MIRA) [9-10], dynamic online routing algorithm (DORA) [11], profile based routing algorithm (PBR) [12] and least interference path algorithm (LIP) [13] in depth [14-15]. This algorithm is composed of off-line and on-line stages, adding regular amendment of link criticality.

2 Specific description of CDLI algorithm

2.1 Off-line stage

Off-line stage is executed whenever the network is initialized or a topology change occurs. In the off-line stage, the key operation is to assign the optimal path set DP database for real-time traffic using the flow characteristic information of real-time traffic for each source-destination pair, and to assign link critical value (LCV) for online routing.

Step 1 For each ingress-egress pair (S_i, D_i), measure the real-time traffic profile, each traffic profile is defined by a quadruple, that is (classID, S_i, D_i, F_i), where classID is the traffic class, S_i and D_i are the ingress node and egress node respectively, and F_i is the aggregate traffic to be measured for real-time traffic between S_i and D_i over a period of time. W_i is aggregate predictive bandwidth of real-time traffic between (S_i, D_i). Suppose there are r real-time traffic. Using the following equation to obtain W_i:

                                 (1)

where δ₁, δ₂, …, δ_r are grading coefficients, transforming the forecast bandwidth of different levels into indistinctive congeneric bandwidth through grading coefficients. If the request bandwidth is general, δ₁= δ₂=…=δ_r.

Step 2 For each ingress-egress pair (S_i, D_i), let ||W_i|| be equal to the normalized value of traffic profile, and using the following equation to obtain ||W_i||:

                              (2)

Step 3 For each ingress-egress pair (S_i, D_i), construct the link critical value (LCV) array LCV (S_i,  D_i), and initialize all entries to zero. The size of the array is equal to the number of network links.

Step 4 For each ingress-egress pair (S_i, D_i), determine a disjointed paths database to store paths that are likely to be selected between (S_i, D_i), and the number of the paths in  is no more than K.

Step 5 For each ingress-egress pair (S_i, D_i), run Dijsktra’s algorithm to find the shortest path (in terms of number hops) for (S_i, D_i), add this path to and then remove a link with the largest link critical value in the resulting path, and repeat these steps until D_i is no longer reachable from S_i or there are K paths in

Step 6 For each ingress-egress pair (S_i, D_i):

(1) Go through each link in the network. If a link L is part of any paths in subtract ||W_i|| from  (L).

(2) For all the ingress-egress pair other than (S_i, D_i), inspect each link L and determine the number of times,  X, that L appears inwhere (S_j, D_j) is not equal to (S_i, D_i). Increment(L) by X×||W_i||.

Step 7 Repeat step 6 to step 7 for all the other ingress-egress pairs.

Step 8 For each ingress-egress pair (S_i, D_i), normalize LCV to the range from 0 to 1, with the smallest LCV equal to 0 and the largest LCV equal to 1. Let ||LCV|| be equal to the normalized value of LCV.

2.2 On-line stage

On-line stage is executed whenever a path setup request arrives to the network. Its goal is to select the path with minimum hops in DP database for real-time traffic in order to reduce the latency. If there is no path that meets the requirements in DP database, the algorithm will execute on-line dynamic routing on the basis of available bandwidth and link critical information. For best-effort traffic, the algorithm directly calculates the shortest widest path according to available bandwidth and links critical information for load balancing and increasing the total throughput of the network, instead of selecting path from DP database. When a LSP setup request (classID, I, S_i, D_i, b_i) arrives, the ingress router judges the level of traffic according to ClassID, where I is the request ID, and b_i is the bandwidth requested for the LSP. We assume that each LSP request can be mapped to a unique traffic profile class.

2.2.1 Routing for real-time traffic

Step 1 Remove links with residual bandwidth less than the requested bandwidth b_i.

Step 2 Search from the first path in DP database of the ingress-egress pair (S_i, D_i), if all residual bandwidth of links in the path is more than b_i, terminate calculating and establish LSP. If all paths in DP database do not meet the requirement, go to the next step.

Step 3 For each network link L, determine its residual bandwidth W_R(L). Let ρ_L be equal to the reciprocal of W_R(L) +1. Normalize ρ_L to the range from 0 to 1, with the smallest ρ_L equal to 0 and the largest ρ_L equal to 1. Let ||ρ_L|| be equal to the normalized value of ρ_L.

                               (3)

Step 4 For the ingress-egress pair (S_i, D_i), construct a link weight table cost(L). Use the following equation to obtain cost(L):

××          (4)

where η is a user parameter.

Step 5 Run Dijsktra’s algorithm to compute a link weight-optimized path between (S_i, D_i). If the establishment is not successful, then refuse the request.

Step 6 For each link L in the LSP, update residual bandwidth W_R(L) using the following equation:

W_R(L)=W_R(L)－b_i                             (5)

2.2.2 Routing for best-effort traffic

Step 1 Remove links with residual bandwidth less than the requested bandwidth b_i.

Step 2 Using Eq.(3) to obtain ρ_L and normalize ρ_L to the range from 0 to 1, with the smallest ρ_L equal to 0 and the largest ρ_L equal to 1. Let ||ρ_L|| be equal to the normalized value of ρ_L.

Step 3 For the ingress-egress pair (S_i, D_i), construct a link weight table cost(L). Use the following equation to obtain cost(L).

××          (6)

where ζ is a user parameter.

Step 4 Run Dijsktra’s algorithm to compute a link weight-optimized path between (S_i, D_i). If the establishment is not successful, then refuse the request.

Step 5 For each link L in the LSP, update residual bandwidth W_R(L) using Eq.(5).

2.3 Regular amendment of link criticality

Link criticality is mainly affected by two factors. One is the relative positions of the ingress-egress pairs, link bandwidth and priority of the path. Such factors have been determined whenever the network is initialized or a topology changes. That is to say, such information is suitable to process in the off-line stage. The other is the forecast bandwidth information of real-time traffic in the future, such information may change over time, or may be inaccurate some times. So, it is suitable for such information to process with regular amendment.

Step 1 For ingress-egress pair (S_i, D_i), measure the real-time traffic profile (classID, S_i, D_i, F_i) every interval.

Step 2 Calculate indistinctive forecast bandwidth P_i between (S_i, D_i) in a coming period of time based on traffic profile (classID, S_i, D_i, F_i), and use the following equation to obtain P_i:

                                 (7)

Step 3 Normalize P_i to the range from 0 to 1, let ||P_i|| be equal to the normalized value of P_i, and use the following equation to obtain ||P_i||:

                                (8)

Step 4 Go through each link in the network and if a link L is part of any paths insubtract (||P_i||- ||W_i||) from(L). For all the ingress-egress pairs other than (S_i, D_i), inspect each link L and determine the number of times, X, in which L appears in where (S_j, D_j) is not equal to (S_i, D_i). Increment (L) by X.

Step 5 Normalize LCV to the range from 0 to 1, and let ||LCV|| be equal to the normalized value of LCV.

The information of link criticality will be updated regularly with the change of forecast bandwidth information.

3 Parameter setting and performance evaluation

The network topology used in the experiment represents a small Internet Service Provider’s backbone network with 15 nodes and 28 duple-links and is shown in Fig.1. The figure also shows the location of 5 different ingress-egress pairs, identified by (S₁, D₁), (S₂, D₂), (S₃, D₃), (S₄, D₄) and (S₅, D₅). All link capacities in the network are either 48 Mbps or 12 Mbps.

Fig.1 Network topology of KL2

The bandwidth requirement of each path is uniformly distributed among 10, 64, 70, 80 and 90 K, where 64 K is the bandwidth that real-time voice traffic requires, and all the requests with 64 K bandwidth will be treated as real-time traffic, others as best-effort traffic. Static paths resemble long-lived MPLS tunnels and once they are established, they will stay in the network forever. Because all the request bandwidth is general, δ₁=      δ₂ =…=δ_r.

The requests of all the experiments are generated randomly between all the ingress-egress pairs. However, proportion of real-time traffic in all the ingress-egress pairs is different, and the ratio between them is 0.0:0.16:0.15:0.32:0.37. This shows that there is no real-time traffic between (S₁, D₁), and the traffic between (S₂, D₂) and (S₃, D₃) is almost the same, and the proportion of real-time traffic between (S₄, S₄) and (S₅, D₅) is the highest, which indicates that (S₅, D₅) and (S₄, D₄) are obviously more important than other ingress- egress pairs, which means they need more QoS guarantee, and then followed by (S₃, D₃) and (S₂, D₂), and (S₁, D₁) the minimum requirements.

Four different experiment scenarios are considered. The first experiment verifies the advantage of CDLI algorithm adding the traffic profile information. The second experiment focuses on the determination of the optimal number of the critical path K. The third experiment focuses on the determination of the optimal scale factor η and ζ. The last experiment studies CDLI algorithm performance compared with DORA and constrained shortest path first (CSPF) algorithm.

To reflect the network’s ability to receive traffic and different routing performances for different traffic, the paper explicitly mentions reject rate of bandwidth requests and LSP’s average length of real-time traffic in addition to the use of network throughput. Definitions 1 and 2 are the descriptions of the two indicators. At a certain number of requests, the lower the reject rate of bandwidth requests is, the better the optimal use of network resources is.

Definition 1 Reject rate of bandwidth requests: Ratio of the refused bandwidth and total request bandwidth in the case that the number of requests remain unchanged.

Definition 2 LSP’s average length of real-time traffic: Ratio of hops of the LSP for all real-time traffic that exists in the network and the number of path.

3.1 Introduction of traffic profile

CDLI algorithm introduced the flow characteristics information cite of real-time traffic, and the information is the proportion of real-time traffic of each ingress-egress pair, marking the relative importance of all ingress- egress pairs. When CDLI (K=6, η=0.9, ζ=0.1), of which, K is the number of critical path, η and ζ are the scale factors of Eq.(4) and Eq.(6), set up two different kinds of experiments by setting cit1-cit5 the original value and 0 respectively. The results show that the algorithm with the flow characteristics information cite of real-time traffic acquires lower reject rate of bandwidth requests than the one without that information. Therefore, the introduction of the flow characteristics information of real-time traffic can significantly improve CDLI algorithm in reject rate of bandwidth requests.

3.2 Number of critical paths

K is the number of critical paths stored in DP database of each ingress-egress pair. CDLI algorithm defines all the links belonging to these K paths in DP database of all the ingress-egress pairs as the critical links. At the same time, on-line routing for real-time traffic will first select a path among these K paths in DP database, which can affect LSP’s average length of real-time traffic. Therefore, K plays a significant role in the performance of algorithm. In this work, set up experiments with different K values for 40 times in the case that the number of requests is unchanged and factor η=0.9 and ζ=0.1. The experiment results show that when K=6, the new algorithm performance on reject rate of bandwidth requests and LSP’s average length of real-time traffic is the best.

The experiment results show that, if K is too small, the critical path set DP database will be so small that it cannot reflect more conflict in more links between all ingress-egress pairs. And if K is too large, DP database of each ingress-egress pair will contain too many links, which cannot reflect the importance of each ingress- egress pair, which can increase LSP’s average length of real-time traffic. Therefore, for a particular network, there should be an appropriate value of K, which makes the algorithm achieve the best performance.

3.3 Scale factor

η and ζ are used to adjust the proportion between the residual bandwidth and link criticality. So, the values of η and ζ have some impacts on the performance of the algorithm. We did seven different kinds of experiments by changing the values of η and ζ in the case of K=6. The results show that when η=0.9 and ζ=0.1, the new algorithm performance on reject rate of bandwidth requests and LSP’s average length of real-time traffic is the best.

The experiment shows that when calculating link weight for real-time traffic, we should increase the value of scale factor η, when the algorithm cannot search the required path in DP database. It can try its best to choose the path depending on the link criticality with flow characteristics information calculated in off-line stage. It can avoid potential interferences with other ingress- egress pair, and at the same time, choose the path of minimal hops to achieve the latency that real-time traffic requires. When routing for best-effort traffic, the impact of the bandwidth should be considered as much as possible by reducing scale factor ζ. Links with relatively large bandwidth will be chosen to achieve load balancing and increase the total network throughput while avoiding from occupying the links of the shortest path that real-time traffic chooses.

3.4 Performance evaluation

The optimal parameters of CDLI algorithm have been confirmed through the experiments above. Compared with DORA and CSPF algorithms, we detect CDLI algorithm’s performances in the condition of K=6, η=0.9 and ζ=0.1 through analyzing the reject rate of bandwidth requests, network throughout and LSP’s average length of real-time traffic. In addition, user parameter of the weight equation in DORA algorithm has been chosen as 0.9, which is the best value during the experiment, indicating that link residual bandwidth decides 90% of link weight, while the left 10% is decided by link latent value.

Fig.2 shows the comparison in reject rate of bandwidth requests versus the number of requests among CDLI, DORA and CSPF algorithms. It indicates that there is almost no difference in reject rate of bandwidth requests between DORA and CSPF, while CDLI is a little higher at beginning. Whereas, the reject rate of bandwidth requests of CDLI becomes obviously lower than that of CSPF and DORA along with increasing request numbers.

Fig.3 shows the comparison in network throughout among CDLI, DORA and CSPF algorithms. It can be seen that, when request number is lower, the received bandwidth of network increases by beeline because refused rate is also low. And then, with increasing the request number, many kinds of algorithms begin to refuse services in different grades, and received bandwidth goes up slowly. Finally, network throughout presents a horizontal line when network becomes saturation due to large request number. During the whole process of experiment, the throughout of CDLI algorithm is a bit lower than that of other two algorithms at the beginning, but the situation has changed since saturation to DORA and CSFP algorithms is obtained by increasing request number. On the other hand, CDLI algorithm can still receive new services and network throughout keeps rising until reaching the highest value. In conclusion, in this scenario, CDLI accomplishes high network throughout and resource utilization.

Fig.4 shows LSP’s average length of real-time traffic in the condition of different request numbers among the three algorithms. It can be seen clearly from Fig.4 that CDLI obtains the minimum LSP’s average length of real-time traffic. Thus, this algorithm assures the DP database for real-time traffic in the off-line stage, and the DP database is built by computing minimum hop at an abundant bandwidth. While choosing route in the online stage, firstly, search from the shortest path from DP database, if all of the paths do not satisfy the requirement, start up restriction-based shortest path algorithm using user parameter as 0.9. The description above is the reason why CDLI algorithm is outstanding in LSP’s average length of real-time traffic.

Fig.2 Reject rate of bandwidth requests versus number of requests

Fig.3 Total throughput of network versus number of requests

Fig.4 LSP’s average length of real-time traffic versus number of requests

In the opposite, both DORA and CSPF algorithm do not distinguish services, and take the same response with different grade services, which causes DORA and CSPF algorithms to represent less superiority. CSPF chooses route by computing reciprocal of bandwidth instead of shortest path that causes CSPF to represent the worst performance. For DORA, it considers not only left bandwidth but also link potential value, so DORA is better than CSPF and still worse than CDLI.

4 Conclusions

(1) CDLI algorithm introduces the real-time traffic profile information into link criticality, so that the information that network pre-processes is richer and not limited to the information of ingress-egress pair. At the same time, the mechanism of regular amendment of link criticality ensures the traffic profile information to be more accurate, and the regular amendment mechanism has little time complexity.

(2) CDLI algorithm takes into account both real-time traffic and best-effort traffic, selects short path that meets the bandwidth requirements for real-time traffic to achieve low latency and bandwidth that real-time traffic requires. As for best-effort traffic, choose the links with light load to meet the requirement of network throughput. Therefore, it can achieve load balancing in the network and QoS guarantee for high-priority traffic. The results show that, in terms of reject rate of bandwidth requests, network throughput and LSP’s average length of real-time traffic, the performance of CDLI algorithm is superior to that of other two algorithms.

References

[1] IETF RFC 2702. Requirements for traffic engineering over MPLS [S].

[2] BARAKOVIC J, BAJRIC H, HUSIC A. QoS design issues and traffic engineering in next generation IP/MPLS network [C]// IEEE Telecommunications. Piscataway: Institute of Electrical and Electronics Engineers Computer Society, 2007: 203-210.

[3] IETF RFC 3272. Overview and principles of internet traffic engineering [S].

[4] YOU B S, SEOK S J, YOUM S K, KIM K H, KANG C H. Traffic engineering using a heuristic multi-path routing strategy in MPLS network [C]// Proceedings of 2006 Asia-Pacific Conference on Communication. Busan, 2006: 926-932.

[5] JACOBS P, DAVIE B. Technical challenges in the delivery of interprovider QoS [J]. IEEE Communication Magazine, 2005, 43(6): 112-118.

[6] PASIAS V, KARRAS DA, PAPADEMETRIOU RC. A framework for traffic engineering and routing in survivable multi-service high bit rates optical networks [C]// Proceedings of Multimedia Signal Processing and Communications. Zagreb: Croatian Society Electronics in Marine, 2006: 353-357.

[7] HONG D W, HONG C S, LEE G H. A scalable CSPF routing scheme with multiple QoS constraints for MPLS traffic engineering [J]. ETRI Journal, 2005, 27(6):733-746.

[8] ZHENG Zhi-mei, CUI Yong. Study of minimum interference routing algorithm for MPLS traffic engineering [J]. Journal of Software, 2006, 17(4): 814-821. (in Chinese)

[9] KODIALAM M, LAKSHMAN T V. Minimum interference routing with applications to MPLS traffic engineering [C]// Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies. Piscataway: IEEE, 2000: 884-893.

[10] HENDING K, LOSERT T, HUBER W, JANDL M. Interference minimizing bandwidth guaranteed on-line routing algorithm for traffic engineering [C]// Proceedings of the 12th IEEE International Conference on Networks. Singapore, 2004: 497-503.

[11] SZETO W, BOUTABA R, IRAQI Y. Dynamic online routing algorithm for MPLS traffic engineering [C]// Proceedings of the Networking 2002. Berlin Heidelberg: Springer-Verlag, 2002: 936-946.

[12] SURI S, WALDVOGEL M, WARKHEDE P R. Profile-based routing: A new framework for MPLS traffic engineering [C]// Proceedings of the Second International Workshop on Quality of Future Internet Services. Berlin, 2001: 138-157.

[13] ZHENG Zhi-mei, CUI Yong. A least interference path algorithm for MPLS traffic engineering [J]. Chinese Journal of Computers, 2007, 30(6): 934-944. (in Chinese)

[14] ILIADIS I, BAUER D. A new class of online minimum interference routing algorithm [C]// Proceedings of the Networking 2002. Berlin: Springer-Verlag, 2002: 959-971.

[15] TRAN C H, NGUYEN H T, NGUYEN D T, HEA W J, TEA K, SUNG H K, WOO J Y. Advanced routing algorithms and load balancing on MPLS [C]// Proceedings of IEEE Advanced Communication Technology. New York: Institute of Electrical and Electronics Engineers, 2007: 1886-1891.

(Edited by YANG You-ping)