Online multicast routing with bandwidth guarantees: a new approach using multicast network flow

ABSTRACT

This paper presents a new algorithm for on-line routing of bandwidth-guaranteed multicasts where routing requests arrive one-by-one without there being any a priori knowledge of future requests. A multicast routing request consists of a source s, a set of receivers R, and a bandwidth requirement b. This multicast routing problem arises in many contexts. Two applications of interest are routing of point-to-multipoint label-switched paths in Multi-Protocol Label Switched (MPLS) networks, and the provision of bandwidth guaranteed Virtual Private Network (VPN) services under the “hose” service model [17]. Offline multicast routing algorithms cannot be used since they require a priori knowledge of all multicast 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 algorithm is an on-line algorithm and 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 that is 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. The presented algorithm uses link-state information and some auxilliary capacity information for multicast tree selection and is amenable to distributed implementation. 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 and performs very well.

REFERENCES

• 1: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 2: http://home, ascend.com/mktg/library/products/ ipnav igat or/ipnvmpa~, pdf
• 3: M. J. Alexander and G. Robins. New Performance-Driven FPGA Routing Algorithms. 1EEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vo}. 15, No. 12, pp. 1505-1517, December 1996.
• 4: D. O. Awduche, L. Berger, D. Can, T. Li, G. Swallow, V. Srinivas~,. Extensions to RSVP for LSP Tunnels, Internet Dra}t draft- iet}- topis- rsvp-lsp-tunnet- O0.txt, November 1998.
• 5: D. O. Awduche, J. MMcom, J. Agogbua, IV{. O13ell, J. McManus. Requirements for Traffic Engineering over MPLS, Internet Draft draft-ietf-mpls-traffic-eng-OO.txt, October 1998.
• 6: Piotr Berman , Viswanathan Ramaiyer, Improved approximations for the Steiner tree problem, Journal of Algorithms, v.17 n.3, p.381-408, Nov. 1994
• 7: Marshall Bern , Paul Plassmann, The steiner problem with edge lengths 1 and 2,, Information Processing Letters, v.32 n.4, p.171-176, Sept 1, 1989 [doi>10.1016/0020-0190(89)90039-2]
• 8: R. Callon, N. Feldman, A. Fredette, G. Swallow, A. Viswanathan. A Framework for Multiprotocol Label Switching, Internet Draft draft-ietf-mpls-framework-O3.txt, June 1999.
• 9: Moses Charikar , Chandra Chekuri , To-yat Cheung , Zuo Dai , Ashish Goel , Sudipto Guha , Ming Li, Approximation algorithms for directed Steiner problems, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.192-200, January 25-27, 1998, San Francisco, California, United States
• 10: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 11: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 12: R. Guerin, D. Williams, A. Przygiend;t, S. Kamat, A. Orda. QoS Routing Mechanisms and OSPF Extensions. Internet Draft draft-guerin-qos-routing-ospf-O$.txt, December 1998.
• 13: R. Guerin, D. Williams, A. Orda. QoS Routing Mechanisms and OSPF Extensions. Proceedings of Globecom 1997.
• 14: M. Karpinsky and A. Zelikovsky. New approximation algorithms for the Steiner tree problem. Technical Report, Electronic Colloquium on Computational Complexity (ECCC), TR95-030, 1995.
• 15: M. Kodialam, T. V. Lakshman. On-line Routing of Guaranteed Bandwidth Tunnels. Seventh IFIP Workshop on Performance Modelling and Evaluation of A TM/IP Networks, June 1999.
• 16: M. KodiMam, T. V. Lakshman. Minimum Interference Routing with Applications to MPLS Traffic Engineering. To appear Proceedings of IEEE INFOCOM ~-000.
• 17: N. G. Duffield , Pawan Goyal , Albert Greenberg , Partho Mishra , K. K. Ramakrishnan , Jacobus E. van der Merive, A flexible model for resource management in virtual private networks, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.95-108, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 18: D. Ooms, W. Livens, B. Sales, M. Ramalho, A. Acharya, F. Griffoul, F. Ansari. Framework for IP Multicast in MPLS. MPLS Working Group lnternet Draft, June 1999.
• 19: S. Ramanathan, Multicast tree generation in networks with asymmetric links, IEEE/ACM Transactions on Networking (TON), v.4 n.4, p.558-568, Aug. 1996 [doi>10.1109/90.532865]
• 20: E. Rosen, A. Viswa~athan, and R. Callon. Multiprotocol Label Switching Architecture. work ia progress, Internet Draft draft-ietf-rapls-arch-O2.txt, July 1998.
• 21: B. M. Waxman. Performance Evaluation of Multipoint Routing Algorithms. Proc. IEEE INFOCOM, pp, 980-986, 1993.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Access schemes

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Online computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Design, Documentation, Measurement, Performance, Reliability, Theory

Keywords:
Steiner tree, multicast routing, network flow, traffic engineering