[en] In the context of Multiprotocol Label Switching (MPLS), we look at the problem of organizing the mapping of Label Switched Paths (LSPs) in an optimal way throughout the network on the basis of a given objective function. This problem is highly combinatorial and makes dynamic and real-time features a difficult issue for any LSP routing scheme. For this reason, we propose a computationally efficient, though approximate, on-line scheme adapted to an incremental optimization of the network state. We also propose an integration of a computationally efficient preemption mechanism into this approximation. The efficiency of this algorithm is obtained through a very rigid but seemingly appropriate policy concerning which LSPs are appropriate for preemption. A feedback from preemption on the routing process is proposed, in order to regulate the rate of the reroutings and to tune the balance between stability and continuous reorganization in a network.
Disciplines :
Computer science
Author, co-author :
Blanchy, François; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Réseaux informatiques
Mélon, Laurent; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Réseaux informatiques
Leduc, Guy ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Réseaux informatiques
Language :
English
Title :
A preemption-aware on-line routing algorithm for MPLS networks
P. Aukia, M. Kodialam, P. Koppol, T. Lakshman, H. Sarin and B. Suter, RATES: A server for MPLS traffic engineering, IEEE Network Magazine 2 (March/April 2000) 34-41.
D. Awduche, L. Berger, D. Gan, T. Li, V. Srinivasan and G. Swallow, RSVP-TE: Extensions to RSVP for LSP tunnels, RFC 3209 (December 2001).
G. Banerjee and D. Sidhu, Comparative analysis of path computation techniques for MPLS traffic engineering, Computer Networks 40 (2002) 149-165.
R. Bellman and R. Kalaba, Shortest paths through networks, in: Dynamic Programming and Modern Control Theory (Academic Press, New York, 1965) pp. 50-54.
F. Blanchy, L. Mélon and G. Leduc, Assessment of protocols and algorithms for intra-domain traffic engineering, Deliverable 3.2 for the ATRIUM project funded by the European Commission, available at http: / / run.montefiore.ulg.ac.be/̃blanchy (January 2003).
F. Blanchy, L. Mélon and G. Leduc, An efficient decentralized on-line traffic engineering algorithm for MPLS networks, in: Proc. of 18th Internat. Teletraffic Congress (ITC 18), September 2003, Berlin, Germany.
J. de Oliveira, C. Scoglio, I. Akyildiz and G. Uhl, A new preemption policy for diffserv-aware traffic engineering to minimize rerouting, in: IEEE INFOCOM, Vol. 1, June 2002, pp. 665-704.
E. Rosen, A. Viswanathan and R. Calon, Multiprotocol label switching architecture, RFC 3031 (January 2001).
F. L. Faucheur and W. Lai, Requirements for support of diff-serv-aware MPLS traffic engineering, IETF draft draft-ietf-tewg-diff-te-reqts-06.txt (September 2002).
B. Fortz and M. Thorup, Internet traffic engineering by optimizing OSPF weights, in: IEEE INFOCOM, Vol. 2, 2000, pp. 519-528.
M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, New York, 1979).
B. Jamoussi, ed., L. Andersson, R. Callon, R. Dantu, L. Wu, P. Doolan, T. Worster, N. Feldman, A. Fredette, M. Girish, E. Gray, J. Heinanen, T. Kilty and A. Malis, Constraint-based LSP setup using LDP, RFC 3212 (January 2002).
M. S. Kodialam and T. V. Lakshman, Minimum interference routing with applications to MPLS traffic engineering, in: IEEE INFOCOM, Vol. 2, 2000, pp. 884-893.
L. Mélon, F. Blanchy and G. Leduc, Decentralized local backup LSP calculation with efficient bandwidth sharing, in: Proc. of 10th Internat. Conf. on Telecommunications (ICT '2003), February 2003, Papeete, Tahiti.
M. Peyravian and A.D. Kshemkalyani, Connection preemption: Issues, algorithms, and a simulation study, in: IEEE INFOCOM, April 1997, pp. 143-151.
E. Ricciato, S. Salsano, A. Belmonte and M. Listanti, Offline configuration of a MPLS over WDM network under time-varying offered traffic, in: IEEE INFOCOM, Vol. 1, June 2002, pp. 57-65.
P. Srisuresh and P. Joseph, TELSAs to extend OSPF for traffic engineering, Internet-draft: draft-srisuresh-ospf-te-02.txt (January 2002).
B. Szviatovszki, A. Szentesi and A. Juttner, Minimizing re-routing in MPLS networks with preemption-aware constraint-based routing, Computer Communications 25 (2002) 1076-1083.
