Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Rio, Miguel; Linington, Peter F. (2000)
Publisher: IEEE Computer Society
Languages: English
Types: Unknown
Subjects: T, TK5101, QA75
This paper describes a novel method of building multicast trees for Real Time Traffic with Quality of Service constraints. There is a wide range of heuristics to calculate the optimal multicast distribution trees with bounds on the maximum delay from the source to all members. However these heuristics require all the members to be known in advance and assume the existence of a centralized service. We present a heuristic - Best Cost Individual Join (BCIJ) - that joins members one by one, randomly to the existing tree. The method doesn't need previous knowledge of the group members. Trees are dynamically built when each member arrives in the group. A distributed method - Multiple Metric Broadcast (MMB) - for nodes to obtain the best valid path to the existing tree is also presented. MMB is inspired by Reverse Path Forwarding and broadcasts queries to the network that reach existing on-tree members. Theses reply with the best valid paths to the joining member. The member then selects the best path. This avoids the use of any centralized service and the need for link-state information to be available in any node. Evaluation presented shows that the BCIJ produces trees with better cost than existing centralized heuristics and that MMB doesn't have a major effect on the network if the group participation is sufficiently large.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • [1] Paul Ferguson and Geoff Huston. Quality of Service, delivering QoS in the Internet and in coorporate networks. Wiley, 1998.
    • [2] Hans Eriksson. MBONE: The Multicast Backbone. Communications of the ACM, 37(8):54-60, August 1994.
    • [3] S. Deering. RFC 1112 - Host Extensions for IP Multicasting. 1989.
    • [4] D. Waitzman, S. Deering, and C. Partridge. RFC 1075 - Distance Vector Multicast Routing Protocol. 1995.
    • [5] John Moy. Multicast Routing Extensions for OSPF. Communications of the ACM, 37(8):61-66, August 1994.
    • [6] Tony Ballardie, Paul Francis, and Jon Crowcroft. Core Based Trees (CBT). In Proceedings of SIGCOMM'93, pages 85-95, 1993.
    • [7] Stephen Deering, Deborah Estrin, Dino Farinacci, Mark Handley, Ahmed Helmy, Van Jacobson, Ching gung Liu, Puneet Sharma, David Thaler, and Liming Wei. Protocol Independent Multicast-Sparse Mode(PIM-SM), Motivation and Architecture. 1996.
    • [8] L. Zhang, B. Brandon, D. Estrin, S. Herzog, and S. Jamin. ReSource ReserVation Protocol (RSVP) - Functional Specefication, Internet-Draft. March 1997.
    • [9] Eric Crawley, Raj Nair, Bala Rajagopalan, and Hal Sandick. RFC 2386 - A Framework for QoS-based Routing in the Internet. August 1998.
    • [10] Ian Stewart. Trees, Telephones and tiles. New Scientist, November 1991.
    • [11] L. Kou, G. Markowsky, and L. Berman. A Fast Algorithm for Steiner Trees. Acta Informatica, 15:141- 145, 1981.
    • [12] E.N.Gilbert and H.O. Pollock. Steiner Minimal Trees. SIAM Journal on Applied Mathematics, 16(1), 1968.
    • [13] Vachaspathi P. Kompella, Joseph C. Pasquale, and George C. Polyzos. Multicast Routing for Multimedia Communication. IEEE/ACM Transactions on Networking, 1(3):286-292, June 1993.
    • [14] A. Gill Waters. Multicast provision for high speed networks. In Proceedings of 4th IFIP Conference on High Speed networking (liege, Belgium). Elsevier Science, December 1992.
    • [15] Q. Sun and H. Langendoerfer. Efficient Multicast Routing for Delay-Sensitive Applications. In Proceedings of Second International Workshop os Protocols for Multimedia Systems (PROMS'95), pages 452-458, 1995.
    • [16] Ken Carlberg and Jon Crowcroft. Building Shared Trees Using a One-to-Many Joining Mechanism. Computer Comunication Review, 27(1):5-11, January 1997.
    • [17] Michalis Faloutsos, Anindo Banerjea, and Rajesh Pankaj. QoSMIC: Quality od Service sensitive Multicast Internet Protocol . In Proceedings of SIGCOMM'98, volume 28. ACM, October 1998.
    • [18] Yogen K. Dalal and Robert M. Metcalfe. Reverse Path Forwarding of Broadcast Packets. Communications of the ACM, 21(12):1040-1048, December 1978.
    • [19] Bernard M. Waxman. Routing of Multipoint Connections. IEEE Journal on Selected Areas in Communications, 6(9):1617-1622, December 1988.
    • [20] Kevin Watkins. Discrete Event Simulation in C. McGraw Hill International, 1993.
    • [21] Zheng Wang and Jon Crowcroft. Qality-of-Service Routing for Supporting Multimedia Applications . IEEE Journal on Selected Areas in Communications, 14(2):1228-1234, September 1996.
    • [22] George Apostolopoulos, Roch Guerin, Sanjay Kamat, and Satish K. Tripathi. Quality of Service Routing: A Performance Perspective. In Proceedings of SIGCOMM'98, volume 28, pages 17-28, October 1998.
    • [23] Horst Hodel. Policy Tree Multicast Routing: An extension to Sparse Mode source Tree Delivery. Computer Communication Review, 28(2):78-97, April 1998.
    • [24] Ronny Vogel, Ralf Guido Herrtwich, Winfried Kalfa, Hartmut Wittig, and Lars C. Wolf. QoS R-Based Routing of Multimedia Streams in Computer Networks. IEEE Journal on Selected Areas in Communications, 14(7):1235-1244, September 1996.
    • [25] Aiguo Fei and Mario Gerla. Receiver-Initiated Multicasting with Multiple QoS Constraints. In Proceedings of INFOCOM'2000, March 2000.
    • [26] Satish Kumar, Pavlin Radoslavov, Dave Thaler, Cenzig Alaettinoglu, Deborah Estrin, and Mark Handley. The MASC/BGMP Architecture for Inter-Domain Multicast Routing. In Proceedings of SIGCOMM'98, volume 28, pages 93-104. ACM, August 1998.
    • [27] Whay C. Lee. Topology Aggregation for Hierarchical Routing in ATM Networks. Computer Communication Review, 29(2):82-92, April 1995.
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article