Minimum interference routing of bandwidth guaranteed tunnels with MPLS traffic engineering applications

被引:173
作者
Kar, K [1 ]
Kodialam, M [1 ]
Lakshman, TV [1 ]
机构
[1] Bell Labs, Lucent Technol, Holmdel, NJ 07733 USA
关键词
maximum flow; MPLS; optimization; quality of service routing; traffic engineering;
D O I
10.1109/49.898737
中图分类号
TM [电工技术]; TN [电子技术、通信技术];
学科分类号
0808 ; 0809 ;
摘要
This paper presents new algorithms for dynamic routing of bandwidth guaranteed tunnels, where tunnel routing requests arrive one by one and there is no a priori knowledge regarding future requests. This problem is motivated by service provider needs for fast deployment of bandwidth guaranteed services. Offline routing algorithms cannot be used since they require a priori knowledge of all tunnel requests that are to be routed. Instead, on-line algorithms that handle requests arriving one by one and that satisfy as many potential future demands as possible are needed. The newly developed algorithms are on-line algorithms and are based on the idea that a newly routed tunnel must follow a route that does not "interfere too much" with a route that may be critical to satisfy a future demand. We show that this problem is NP-hard, We then develop path selection heuristics which are based on the idea of deferred loading of certain "critical" links, These critical links are identified by the algorithm as links that, if heavily loaded, would make it impossible to satisfy future demands between certain ingress-egress pairs. Like min-hop routing, the presented algorithm uses link-state information and some auxiliary capacity information for path selection, Unlike previous algorithms, the proposed algorithm exploits any available knowledge of the network ingress-egress points of potential future demands, even though the demands themselves are unknown. If all nodes are ingress-egress nodes, the algorithm can still be used, particularly to reduce the rejection rate of requests between a specified subset of important ingress-egress pairs. The algorithm performs well in comparison to previously proposed algorithms on several metrics like the number of rejected demands and successful rerouting of demands upon link failure.
引用
收藏
页码:2566 / 2579
页数:14
相关论文
共 16 条
[1]  
AHUJA RK, 1993, NETWORKS FLOWS THEOR
[2]  
AWDUCHE DO, 1999, EXTENSIONS RSVP LSP
[3]  
Callon R., 1999, FRAMEWORK MULTIPROTO
[4]  
Even S., 1976, SIAM Journal on Computing, V5, P691, DOI 10.1137/0205048
[5]  
FRANK H, 1971, COMMUNICATION TRANSM
[6]  
Goldberg A., 1987, ACM Sympos. Theory Comput, P7, DOI 10.1145/28395.28397
[7]   MULTI-TERMINAL NETWORK FLOWS [J].
GOMORY, RE ;
HU, TC .
JOURNAL OF THE SOCIETY FOR INDUSTRIAL AND APPLIED MATHEMATICS, 1961, 9 (04) :551-570
[8]  
GUERIN R, 1997, P GLOB
[9]  
KATZ D, 1999, IN PRESS TRAFFIC ENG
[10]  
KODIALAM M, 1999, P 7 IFIP WORKSH PERF