Off-line and on-line guaranteed start-up delay for media-on-demand with stream merging

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Off-line and on-line guaranteed start-up delay for media-on-demand with stream merging

Full text

Pdf (220 KB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures table of contents

San Diego, California, USA

SESSION: Networks II table of contents

Pages: 164 - 173

Year of Publication: 2003

ISBN:1-58113-661-7

Authors

Amotz Bar-Noy	Brooklyn College -- CUNY, Brooklyn, NY
Justin Goshi	University of Washington, Seattle, WA
Richard E. Ladner	University of Washington, Seattle, WA

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 13, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/777412.777439 What is a DOI?

ABSTRACT

We address the problem of designing efficient solutions for media-on-demand in systems that use stream merging. In a stream merging system, the receiving bandwidth of clients is larger than the playback bandwidth and clients can buffer parts of the transmission to be played back later. Intelligent use of these resources allows bandwidth usage to be reduced exponentially over traditional unicast delivery of popular media. We design an off-line algorithm that, in O(n) time, computes an optimal off-line stream merging solution for the case when the time horizon n is known ahead of time. In addition, we describe an on-line delay guaranteed solution that operates without knowledge of the time horizon size, and show that it performs asymptotically close to the optimal off-line algorithm. The on-line algorithm is simpler to implement than previously proposed on-line stream merging algorithms, and empirically performs well when the intensity of client arrivals is high.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Y. Cai, K. A. Hua, and K. Vu. Optimizing patching performance. In Proc. of the IS&T/SPIE Conference on Multimedia Computing and Networking (MMCN '99), 204--215, 1999.
	2	Steven W. Carter , Darrell D. E. Long, Video-on-Demand Server Efficiency through Stream Tapping, Proceedings of the 6th International Conference on Computer Communications and Networks, p.200, September 22-25, 1997
	3	Steven W. Carter , Darrell D. E. Long, Improving bandwidth efficiency of video-on-demand servers, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.1-2, p.111-123, Jan. 14, 1999
	4	Wun-Tat Chan , Tak Wah Lam , Hing-Fung Ting , Prudence W. H. Wong, Competitive Analysis of On-line Stream Merging Algorithms, Proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science, p.188-200, August 26-30, 2002
	5	Wun-Tat Chan , Tak-Wah Lam , Hing-Fung Ting , Wai-Ha Wong, A unified analysis of hot video schedulers, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509937]
	6	Wun-Tat Chan , Tak Wah Lam , Hing-Fung Ting , Wai-Ha Wong, Improved On-Line Stream Merging: From a Restricted to a General Setting, Proceedings of the 7th Annual International Conference on Computing and Combinatorics, p.432-442, August 20-23, 2001
	7	T. Chiueh and C. Lu. A periodic broadcasting approach to video-on-demand service. In Proc. of the SPIE Conference on Multimedia Computing and Networking (MMCN '95), 162--169, 1995.
	8	E. G. Coffman Jr., Predrag Jelenkovi'c, and Petar Momvcilovi'c.
	9	Asit Dan , Perwez Shahabuddin , Dinkar Sitaram , Don Towsley, Channel allocation under batching and VCR control in video-on-demand systems, Journal of Parallel and Distributed Computing, v.30 n.2, p.168-179, Nov. 1, 1995 [doi>10.1006/jpdc.1995.1135]
	10	Asit Dan , Dinkar Sitaram, An online video placement policy based on bandwidth to space ratio (BSR), Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.376-385, May 22-25, 1995, San Jose, California, United States
	11	A. Dan , D. Sitaram , P. Shahabuddin, Scheduling policies for an on-demand video server with batching, Proceedings of the second ACM international conference on Multimedia, p.15-23, October 15-20, 1994, San Francisco, California, United States [doi>10.1145/192593.192614]
	12	Asit Dan , Dinkar Sitaram , Perwez Shahabuddin, Dynamic batching policies for an on-demand video server, Multimedia Systems, v.4 n.3, p.112-121, June 1996 [doi>10.1007/s005300050016]
	13	D. L. Eager, M. Ferris, and M. K. Vernon. Optimized regional caching for on-demand data delivery. In Proc. of the Conference on Multimedia Computing and Networking (MMCN '99), 301--316, 1999.
	14	Derek L. Eager , Mary K. Vernon, Dynamic Skyscraper Broadcasts for Video-on-Demand, Proceedings of the 4th International Workshop on Advances in Multimedia Information Systems, p.18-32, September 24-26, 1998
	15	D. L. Eager, M. K. Vernon, and J. Zahorjan. Minimizing bandwidth requirements for on-demand data delivery. In Proc. of the 5-th International Workshop on Advances in Multimedia Information Systems (MIS '99), 80--87, 1999.
	16	Derek Eager , Mary Vernon , John Zahorjan, Optimal and efficient merging schedules for video-on-demand servers, Proceedings of the seventh ACM international conference on Multimedia (Part 1), p.199-202, October 30-November 05, 1999, Orlando, Florida, United States [doi>10.1145/319463.319601]
	17	D. L. Eager, M. K. Vernon, and J. Zahorjan. Bandwidth skimming: a technique for cost-effective video-on-demand. In Proc. of the Conference on Multimedia Computing and Networking (MMCN '00), 25--27, 2000.
	18	L. Gao, J. Kurose, and D. Towsley. Efficient schemes for broadcasting popular videos. In Proc. of the 8-th IEEE International Workshop on Network and Operating System Support for Digital Audio and Video (NOSSDAV '98), 1998.
	19	L. Gao and D. Towsley.
	20	Lixin Gao , Zhi-Li Zhang , Don Towsley, Catching and selective catching: efficient latency reduction techniques for delivering continuous multimedia streams, Proceedings of the seventh ACM international conference on Multimedia (Part 1), p.203-206, October 30-November 05, 1999, Orlando, Florida, United States [doi>10.1145/319463.319603]
	21	Leana Golubchik , John C. S. Lui , Richard Muntz, Reducing I/O demand in video-on-demand storage servers, Proceedings of the 1995 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.25-36, May 15-19, 1995, Ottawa, Ontario, Canada
	22	Leana Golubchik , John C. S. Lui , Richard R. Muntz, Adaptive piggybacking: a novel technique for data sharing in video-on-demand storage servers, Multimedia Systems, v.4 n.3, p.140-155, June 1996 [doi>10.1007/s005300050019]
	23	Ronald L. Graham , Donald E. Knuth , Oren Patashnik, Concrete Math, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
	24	Kien A. Hua , Ying Cai , Simon Sheu, Patching: a multicast technique for true video-on-demand services, Proceedings of the sixth ACM international conference on Multimedia, p.191-200, September 13-16, 1998, Bristol, United Kingdom [doi>10.1145/290747.290771]
	25	Exploiting Client Bandwidth for More Efficient Video Broadcast, Proceedings of the International Conference on Computer Communications and Networks, p.848, October 12-15, 1998
	26	Kien A. Hua , Simon Sheu, Skyscraper broadcasting: a new broadcasting scheme for metropolitan video-on-demand systems, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.89-100, September 14-18, 1997, Cannes, France
	27	L. Juhn and L. Tseng. Harmonic broadcasting for video-on-demand service. IEEE Transactions on Broadcasting, Vol. 43, No. 3, 268--271, 1997.
	28	L. Juhn and L. Tseng. Staircase data broadcasting and receiving scheme for hot video service. IEEE Transactions on Consumer Electronics , Vol. 43, No. 4, 1110--1117, 1997.
	29	Li-Shen Juhn , Li-Ming Tseng, Fast broadcasting for hot video access, Proceedings of the 4th International Workshop on Real-Time Computing Systems and Applications (RTCSA '97), p.237, October 27-29, 1997
	30	L. Juhn and L. Tseng. Enhancing harmonic data broadcasting and receiving scheme for popular video service.IEEE Transactions on Consumer Electronics, Vol. 44, No. 2, 343-346, 1998.
	31	L. Juhn and L. Tseng. Fast data broadcasting and receiving scheme for popular video service. IEEE Transactions on Broadcasting, Vol. 44, No. 1, 100--105, 1998.
	32	D. E. Knuth. Optimum binary search trees. Acta Informatica, Vol. 1, 14-25, 1971.
	33	Donald E. Knuth, The Art of Computer Programming Volumes 1-3 Boxed Set, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
	34	Siu-Wah Lau , John C. S. Lui , Leana Golubchik, Merging video streams in a multimedia storage server: complexity and heuristics, Multimedia Systems, v.6 n.1, p.29-42, Jan. 1998 [doi>10.1007/s005300050074]
	35	A Low Bandwidth Broadcasting Protocol for Video on Demand, Proceedings of the International Conference on Computer Communications and Networks, p.690, October 12-15, 1998
	36	J. Paris, S. W. Carter, and D. D. E. Long. A hybrid broadcasting protocol for video on demand. In Proc. of the IS&T/SPIE Conference on Multimedia Computing and Networking (MMCN '99), 317--326, 1999.
	37	J. Paris and D. D. E. Long. Limiting the receiving bandwidth of broadcasting protocols for video-on-demand. In Proc. of the Euromedia Conference, 107--111, 2000.
	38	Jehan-François Pâris , Darrell D. E. Long , Patrick E. Mantey, Zero-delay broadcasting protocols for video-on-demand, Proceedings of the seventh ACM international conference on Multimedia (Part 1), p.189-197, October 30-November 05, 1999, Orlando, Florida, United States [doi>10.1145/319463.319600]
	39	S. Sen, L. Gao, J. Rexford, and D. Towsley. Optimal patching schemes for efficient multimedia streaming. In Proc. of the 9-th IEEE International Workshop on Network and Operating System Support for Digital Audio and Video (NOSSDAV '99), 1999.
	40	S. Sen, L. Gao, and D. Towsley. Frame-based periodic broadcast and fundamental resource tradeoffs. Technical Report 99--78, University of Massachusetts Amherst.
	41	Y. Tseng, C. Hsieh, M. Yang, W. Liao, and J. Sheu. Data broadcasting and seamless channel transition for highly-demanded videos. In Proc. of the 19-th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '00), pp. 4E-2, 2000.
	42	S. Viswanathan and T. Imielinski. Pyramid broadcasting for video-on-demand service. In Proc. of the SPIE Conference on Multimedia Computing and Networking (MMCN '95), 66--77, 1995.
	43	S. Viswanathan , T. Imielinski, Metropolitan area video-on-demand service using pyramid broadcasting, Multimedia Systems, v.4 n.4, p.197-208, Aug. 1996 [doi>10.1007/s005300050023]