Layered multicast scheduling for the L∞ objective

ABSTRACT

Layered multicast is a scalable solution to data dissemination over the Internet. The performance of layered multicast hinges upon the transmission schedule. In this paper, we study the scheduling problem in the layered multicast context. This work generalizes the extensively studied multicast scheduling problem (layered and non-layered) by introducing simultaneously the data popularity and the interaction among layers, and addresses the strictest L∞ objective, i.e., to find a schedule which is good for all individual layers. Compared to the previous work, this paper presents a polynomial-time approximation algorithm that uses a different approach and can address the general layered multicast scheduling problem with an arbitrary number of layers. This algorithm is 1.334-approximation for the two-layer case and 1.862-approximation for the general multilayer cases.

REFERENCES

• 1: Mehmet Altinel , Demet Aksoy , Thomas Baby , Michael Franklin , William Shapiro , Stan Zdonik, DBIS-toolkit: adaptable middleware for large scale data delivery, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.544-546, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 2: M. H. Ammar, J. W. Wong: The Design of Teletext Broadcast Cycles. Performance Evaluations. 5:4 (1985) 235--242
• 3: M. H. Ammar, J. W. Wong: On the Optimality of Cyclic Transmission in Teletext Systems. IEEE Transactions on Communications. 35:1 (1987) 68--73
• 4: Shoshana Anily , Celia A. Glass , Refael Hassin, The scheduling of maintenance service, Discrete Applied Mathematics, v.82 n.1-3, p.27-42, March 2, 1998 [doi>10.1016/S0166-218X(97)00119-4]
• 5: Suman Banerjee , Bobby Bhattacharjee , Christopher Kommareddy, Scalable application layer multicast, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 6: Amotz Bar-Noy , Randeep Bhatia , Joseph (Seffi) Naor , Baruch Schieber, Minimizing Service and Operation Costs of Periodic Scheduling, Mathematics of Operations Research, v.27 n.3, p.518-544, August 2002 [doi>10.1287/moor.27.3.518.314]
• 7: A. Bar-Noy, B. Patt-Shamir, I. Ziper: Broadcast Disks with Polynomial Cost Functions. Proc. of IEEE INFOCOM'00. 575--584
• 8: Amotz Bar-Noy , Yaron Shilo, Optimal broadcasting of two files over an asymmetric channel, Journal of Parallel and Distributed Computing, v.60 n.4, p.474-493, April 2000 [doi>10.1006/jpdc.1999.1618]
• 9: Jonathan Beaver , Nicholas Morsillo , Kirk Pruhs , Panos K. Chrysanthis , Vincenzo Liberatore, Scalable dissemination: what's hot and what's not, Proceedings of the 7th International Workshop on the Web and Databases: colocated with ACM SIGMOD/PODS 2004, June 17-18, 2004, Paris, France [doi>10.1145/1017074.1017084]
• 10: Y. Birk, D. Crupnicoff: A Multicast Transmission Schedule for Scalable Multi-Rate Distribution of Bulk Data using Non-Scalable Erasure-Correcting Codes. Proc. of IEEE INFOCOM'03. 1033--1043
• 11: J. Byers, M. Luby, M. Mitzenmacher: Fine-grained Layered Multicast. Proc. of IEEE INFOCOM'01. 1143--1151
• 12: Q. Cai, V. Liberatore: Approximation Algorithms for Layered Multicast Scheduling. Proceedings of the 16th International Symposium on Algorithms and Computation (ISAAC). (2005) 974--983
• 13: Chung-Min Chen , Randeep Bhatia , Rakesh K. Sinha, Multidimensional Declustering Schemes Using Golden Ratio and Kronecker Sequences, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.659-670, March 2003 [doi>10.1109/TKDE.2003.1198397]
• 14: P. A. Chou, A. E. Mohr, A. Wang, S. Mehrotra: Error Control for Receiver-driven Layered Multicast of Audio and Video. IEEE Transactions on Multimedia, Vol. 3, No. 1, 2001.
• 15: M. J. Donahoo, M. H. Ammar, E. W. Zegura: Multiple-Channel Multicast Scheduling for Scalable Bulk-data Transport. Proc. of IEEE INFOCOM'99. 847--855.
• 16: I. El Khayat, G. Leduc: Congestion Control for Layered Multicast Transmission. Networking and Information Systems Journal, vol. 3, 2000. 559--573
• 17: Sally Floyd , Van Jacobson , Ching-Gung Liu , Steven McCanne , Lixia Zhang, A reliable multicast framework for light-weight sessions and application level framing, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.784-803, Dec. 1997 [doi>10.1109/90.650139]
• 18: A. Itai, Z. Rosberg: A golden ratio control policy for a multiple-access channel. IEEE Transactions on Automatic Control. 29:8 (1984) 712--718
• 19: M. Jung, J. Nonnenmacher, E. W. Biersack: Reliable Multicast via Satellite: Uni-directional vs. Bidirectional Communication. Proc. of KiVS, 1999.
• 20: C. Kenyon, N. Schabanel: The Data Broadcast Problem with Non-Uniform Transmission Times. Algorithmica. 35 (2003) 146--175
• 21: Claire Kenyon , Nicolas Schabanel , Neal Young, Polynomial-time approximation scheme for data broadcast, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.659-666, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335398]
• 22: A. Legout , E. W. Biersack, PLM: fast convergence for cumulative layered multicast transmisson schemes, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.13-22, June 18-21, 2000, Santa Clara, California, United States
• 23: X. Li, S. Paul, M. Ammar: Layered Video Multicast with Retransmission (LVMR): Evaluation of Hierarchical Rate Control. Proc. of IEEE INFOCOM'98.
• 24: V. Liberatore: Multicast scheduling for list requests. Proc. of IEEE INFOCOM'02. 1129--1137
• 25: J. Liu, B. Li, Y. Zhang: A Hybrid Adaptation Protocol for TCP-friendly Layered Multicast and its Optimal Rate Allocation. Proc. of IEEE INFOCOM'02. 1520--1529.
• 26: J. Liu, B. Li, Y. Zhang: An End-to-End Adaptation Protocol for Layered Video Multicast Using Optimal Rate Allocation. IEEE Transactions on multimedia, 6 (2004):1. 87--102
• 27: Steven McCanne , Van Jacobson , Martin Vetterli, Receiver-driven layered multicast, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.117-130, August 28-30, 1996, Palo Alto, California, United States
• 28: Anoop Ninan , Purushottam Kulkarni , Prashant Shenoy , Krithi Ramamritham , Renu Tewari, Cooperative leases: scalable consistency maintenance in content distribution networks, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511448]
• 29: L. Peterson, D. Culler, T. Anderson, T. Roscoe: A Blueprint for Introducing Disruptive Technology into the Internet. In Proc. of the 1st Workshop on Hot Topics in Networks (HotNets-I), Princeton, New Jersey, USA, October 2002.
• 30: R. Rummler, A. H. Aghvami: End-to-end IP multicast for software upgrades of reconfigurable user terminals within IMT-2000/UMTS networks. IEEE International Conference on communications, vol. 1, 2002. 502--506
• 31: Nicolas Schabanel, The Data Broadcast Problem with Preemption, Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, p.181-192, February 01, 2000
• 32: Paulo André Silva Gonçalves , José F. Rezende , Otto Carlos Duarte , Guy Pujolle, Improving Feedback Merging for Source-Adaptive Layered Multicast Schemes, Cluster Computing, v.8 n.1, p.77-88, January 2005 [doi>10.1007/s10586-004-4438-3]
• 33: L. Vicisano, J. Crowcroft, L. Rizzo: TCP-like Congestion Control for Layered Multicast Data Transfer. Proc. of IEEE INFOCOM'98.
• 34: W. Zhang, W. Li, V. Liberatore: Application-Perceived Multicast Push Performance. Proc. of IPDPS 2004.