DocumentCode :
770196
Title :
Online multicast routing with bandwidth guarantees: a new approach using multicast network flow
Author :
Kodialam, Murali ; Lakshman, T.V. ; Sengupta, Sudipta
Author_Institution :
Bell Labs., Holmdel, NJ, USA
Volume :
11
Issue :
4
fYear :
2003
Firstpage :
676
Lastpage :
686
Abstract :
We present a new algorithm for online routing of bandwidth-guaranteed multicasts where routing requests arrive one by one without any prior knowledge of future requests. A multicast routing request consists of a source, a set of receivers, and a bandwidth requirement. Two multicast applications of interest are routing of point-to-multipoint label-switched paths in multiprotocol label switched (MPLS) networks, and the provision of bandwidth-guaranteed virtual private network (VPN) services under the "hose" service model. Without prior knowledge of multicast requests, offline multicast routing algorithms cannot be used. Online algorithms are needed to handle requests arriving one by one and to satisfy as many potential future demands as possible. Our new online algorithm is based on the idea that a newly routed multicast must follow a route that does not interfere too much with network paths that may be critical to satisfy future demands. We develop a multicast tree selection heuristic based on the idea of deferred loading of certain critical links. The algorithm identifies them as links that, if heavily loaded, would make it impossible to satisfy future demands between certain ingress-egress pairs. The algorithm uses link-state information and some auxiliary capacity information for multicast tree selection and is amenable to distributed implementation. Unlike previous algorithms, our algorithm exploits any available knowledge of the network ingress-egress points of potential future demands, even though the demands themselves are unknown. It performs very well.
Keywords :
distributed algorithms; multicast communication; multiprotocol label switching; routing protocols; trees (mathematics); virtual private networks; MPLS networks; auxiliary capacity information; bandwidth guarantees; critical links; distributed algorithms; link-state information; multicast network flow; multicast routing; multicast tree selection; multiprotocol label switching; online routing; point-to-multipoint label-switched paths; virtual private network; Associate members; Bandwidth; Hoses; Multicast algorithms; Multiprotocol label switching; Routing; Telecommunication traffic; Traffic control; Unicast; Virtual private networks;
fLanguage :
English
Journal_Title :
Networking, IEEE/ACM Transactions on
Publisher :
ieee
ISSN :
1063-6692
Type :
jour
DOI :
10.1109/TNET.2003.815302
Filename :
1224465
Link To Document :
بازگشت