Lexicographically optimal smoothing for broadband traffic multiplexing

ABSTRACT

We investigate the problem of smoothing multiplexed network traffic, when either a streaming server transmits data to multiple clients, or a server accesses data from multiple storage devices or other servers. We introduce efficient algorithms for lexicographically optimally smoothing the aggregate bandwidth requirements over a shared network link. In the data transmission problem, we consider the case in which the clients have different buffer capacities but no bandwidth constraints, or no buffer capacities but different bandwidth constraints. For the data access problem, we handle the general case of a shared buffer capacity and individual network bandwidth constraints. Previous approaches in the literature for the data access problem handled either the case of only a single stream or did not compute the lexicographically optimal schedule.Lexicographically optimal smoothing (lexopt smoothing) has several advantages. By provably minimizing the variance of the required aggregate bandwidth, maximum resource requirements within the network become more predictable, and useful resource utilization increases. Fairness in sharing a network link by multiple users can be improved, and new requests from future clients are more likely to be successfully admitted without the need for frequently rescheduling previously accepted traffic. Efficient resource management at the network edges can better meet quality of service requirements without restricting the scalability of the system.

REFERENCES

• 1: Stergios V. Anastasiadis , Kenneth C. Sevcik , Michael Stumm, Server-based smoothing of variable bit-rate streams, Proceedings of the ninth ACM international conference on Multimedia, September 30-October 05, 2001, Ottawa, Canada [doi>10.1145/500141.500165]
• 2: Wu-chi Feng , Jennifer Rexford, A Comparison of Bandwidth Smoothing Techniques for the Transmission of Prerecorded Compressed Video, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.58, April 09-11, 1997
• 3: S. Gringeri, K. Shuaib, R. Egorov, A. Lewis, B. Khasnabish, and B. Basch. Traffic shaping, bandwidth allocation, and quality assessment for mpeg video distribution over broadband networks. IEEE Network, 12(6):94-107, Nov/Dec 1998.
• 4: D. T. Hoang , P. M. Long , J. S. Vitter, Efficient Cost Measures for Motion Compensation at Low Bit Rates, Proceedings of the Conference on Data Compression, p.102, March 31-April 03, 1996
• 5: Dzung Tien Hoang , Jeffrey Scott Vitter, Efficient algorithms for MPEG video comrpession, John Wiley & Sons, Inc., New York, NY, 2002
• 6: Toshihide Ibaraki , Naoki Katoh, Resource allocation problems: algorithmic approaches, MIT Press, Cambridge, MA, 1988
• 7: T. V. Lakshman, A. Ortega, and A. R. Reibman. Vbr video: Tradeoffs and potentials. Proceedings of the IEEE, 86(5):952-973, May 1998.
• 8: D. T. Lee and F. P. Preparata. Euclidean shortest path in the presence of rectilinear barriers. Networks, 14:393-410, 1984.
• 9: Yishay Mansour , Boaz Patt-Shamir , Ofer Lapid, Optimal smoothing schedules for real-time streams (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.21-29, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343511]
• 10: J. McManus and K. Ross. A dynamic programming methodology for managing prerecorded vbr sources in packet-switched networks. Telecommunications Systems, 9:223-247, 1998.
• 11: S. Paek and S.-F. Chang. Video server retrieval scheduling for variable bit rate scalable video. In IEEE Multimedia Computing and Systems, pages 108-112, Hiroshima, Japan, June 1996.
• 12: A. L. N. Reddy and R. Wijayaratne. Techniques for improving the throughput of vbr streams. In ACM/SPIE Multimedia Computing and Networking, pages 216-227, San Jose, CA, Jan. 1999.
• 13: Amy R. Reibman , Arthur W. Berger, Traffic descriptors for VBR video teleconferencing over ATM networks, IEEE/ACM Transactions on Networking (TON), v.3 n.3, p.329-339, June 1995 [doi>10.1109/90.392392]
• 14: J. Rexford, S. Sen, J. Dey, W. Feng, J. Kurose, J. Stankovic, and D. Towsley. Online smoothing of live, variable-bit-rate video. IEEE Trans. on Multimedia, 2(1):37-48, Mar. 2000.
• 15: On the Efficient Retrieval of VBR Video in a Multimedia Server, Proceedings of the 1997 International Conference on Multimedia Computing and Systems (ICMCS '97), p.46, June 03-06, 1997 [doi>10.1109/MMCS.1997.609559]
• 16: James D. Salehi , Shi-Li Zhang , Jim Kurose , Don Towsley, Supporting stored video: reducing rate variability and end-to-end resource requirements through optimal smoothing, IEEE/ACM Transactions on Networking (TON), v.6 n.4, p.397-410, Aug. 1998 [doi>10.1109/90.720873]
• 17: Ion Stoica , Scott Shenker , Hui Zhang, Core-stateless fair queueing: achieving approximately fair bandwidth allocations in high speed networks, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.118-130, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 18: Bülent Yener , Gong Su , Eran Gabber, Smart box architecture: a hybrid solution for IP QoS provisioning, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.36 n.2-3, p.357-375, July 2001 [doi>10.1016/S1389-1286(00)00208-5]
• 19: Wei Zhao , Satish K. Tripathi, Bandwidth-efficient continuous media streaming through optimal multiplexing, Proceedings of the 1999 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.13-22, May 01-04, 1999, Atlanta, Georgia, United States