QoSMIC: quality of service sensitive multicast Internet protocol

ABSTRACT

In this paper, we present, QoSMIC, a multicast protocol for the Internet that supports QoS-sensitive routing, and minimizes the importance of a priori configuration decisions (such as core selection). The protocol is resource-efficient, robust, flexible, and scalable. In addition, our protocol is provably loop-free.Our protocol starts with a resources-saving tree (Shared Tree) and individual receivers switch to a QoS-competitive tree (Source-Based Tree) when necessary. In both trees, the new destination is able to choose the most promising among several paths. An innovation is that we use dynamic routing information without relying on a link state exchange protocol to provide it. Our protocol limits the effect of pre-configuration decisions drastically, by separating the management from the data transfer functions; administrative routers are not necessarily part of the tree. This separation increases the robustness, and flexibility of the protocol. Furthermore, QoSMIC is able to adapt dynamically to the conditions of the network.The QoSMIC protocol introduces several new ideas that make it more flexible than other protocols proposed to date. In fact, many of the other protocols, (such as YAM, PIMSM, BGMP, CBT) can be seen as special cases of QoSMIC. This paper presents the motivation behind, and the design of QoSMIC, and provides both analytical and experimental results to support our claims.

REFERENCES

• 1: A. Ballardie. Core Based Trees (CBT version 2) multicast routing. Internet-Draft: IETF RFC 2201, 1997.
• 2: A. Banerjea, M. Faloutsos, and R. Pankaj. Designing QoS- MIC: a QoS Multicast Internet protocol. Internet Draft: draft-banerjea-qosmic-OO.{ps,txt}, 1998.
• 3: T. Billhartz, J. B. Cain, E. Farey-Goudreau, D. Fieg, and S. G. Batsell. Performance and resource cost comparisons for CBT and PIM mulitcast routing protocols. IEEE Journal oJ Selected Areas in Communications, 15(3):304-315, April 1997.
• 4: Ken Carlberg , Jon Crowcroft, Building shared trees using a one-to-many joining mechanism, ACM SIGCOMM Computer Communication Review, v.27 n.1, p.5-11, Jan. 1997 [doi>10.1145/251007.251008]
• 5: S. Casner. Major MBONE routers and links. Available from ftp.isi.edu:mbone/mbone-topology, ps, 1994.
• 6: S. Deering. Host extensions for IF multicasting, lnternet- Draft: IETF RFC 1112, 1989.
• 7: C. Diot, W. Dabbous, and J. Crowcroft. Multipoint communications: A survey of protocols, filnctions, and mechanisms, iEEE Journal of Selected Areas in Uom~7~unicatior~s, 15(13):277-290, April 1997.
• 8: M. Doar and I. Leslie. How bad is naive multicast routing? Proc. {EEE {NFOUOM, pages 82-89, 1993.
• 9: Hans Eriksson, MBONE: the multicast backbone, Communications of the ACM, v.37 n.8, p.54-60, Aug. 1994 [doi>10.1145/179606.179627]
• 10: D. Estrin, D. Farinacci, A. Helmy, D. Thaler, S. Deering, M. Handley, V. Jacobson, C. Liu, F. Sharma, and L. Wei. Protocol independent multicast-sparse mode (PIM- SM): Protocol specification. Internet-Draft: IETF RFC 2117 available from ftp://ftp.ietf, org/internet-drafts/, 1997.
• 11: D. Estrin, M. Handley, S. Kumar, and D. Thaler. The Multicast Address Set Claim protocol. Internet-Draft:draft-ietfidmr-masc-00.txt, 1997.
• 12: M. Faloutsos, R. Pankaj, and K. C. Sevcik. Bounds for the on-line multicast problem in directed graphs. Proceedings of Jth International Colloquium on Structural Information and Communication Complexity (SIROCCO '97), Monte Verita', Ascona, Switzerland July 2~-~6, pages 81-98, 1997.
• 13: W. Fenner. Domain wide multicast group membership reports. Distributed in the IDMR mailing list. To appear as a Working Draft, 1997.
• 14: M. Handley and V. Jacobson. SDP: Session description protocol. Internet Draft. Work in porgress., 1995.
• 15: M. Imase and B.M. Waxman. Dynamic Steiner tree problem. SIAM Journal on Discrete Mathematics, 4:369-384, 1991.
• 16: M. Parsa and J. J. Garcia-Luna-Aceves. A protocol for scalable loop-free multicast routing. IEEE Journal of Selected Areas in Communications, 15(13):316-331, April 1997.
• 17: H. Takahashi and A. Matsuyama. An approximate solution for the Steiner problem in graphs. Math. Japonica, 24(6):573-577, 1980.
• 18: D. Thaler, D. Estrin, and D. Meyer. Border gateway multicast protocol (BGMP): Protocol specification. Internet- Draft: draft-ietf-idmr-gum-02.txt, 1998.
• 19: D.G. Thaler and C.V. Ravishankar. Distributed centerlocation algorithms. IEEE Journal of Selected Areas in Communications, 15(13):291-303, April 1997.
• 20: B. M. Waxman. Routing of multipoint connections. IEEE Journal of Selected Areas in Communications, pages 1617-- 1622, 1988.
• 21: B. M. Waxman. Performance evaluation of multipoint routing algorithms. Proc. IEEE iNFOCOM, pages 980-986, 1993.
• 22: L, Wei and D. Estrin. The trade-offs of multicast trees and algorithms. International Conference on Computer Communications and Networks, 1994.
• 23: P. Winter, Steiner problem in networks: a survey, Networks, v.17 n.2, p.129-167, Summer 1987 [doi>10.1002/net.3230170203]
• 24: D. Zappala, D. Estrin, and S. Shenker. Alternate path routing and pinning for interdomain multicast routing. Technical Report USC CS TR 97-655, U. of South California, 1997.
• 25: L. Zhang, S. Deering, D. Estrin, S. Shenker, and D. Zappala. RSVP: A new resource reservation protocol. IEEE Network, September 1993.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Internet (e.g., TCP/IP)

General Terms:
Performance