A 5-Competitive On-line Scheduler for Merging Video Streams

Wun Tat Chan; Tak Wah Lam; Hing Fung Ting; Wai Ha Wong

doi:10.1109/IPDPS.2001.925217

A 5-Competitive On-line Scheduler for Merging Video Streams

Wun Tat Chan
, Tak Wah Lam
, Hing Fung Ting
, Wai Ha Wong

School of Continuing Education

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

4 Citations (Scopus)

Abstract

This paper is concerned with an on-line scheduling problem arising from video-on-demand (VOD) systems that support stream merging. Most previous work on this problem focuses on empirical results; Bar-Noy and Ladner [3] are the first to consider worst-case performance and give an on-line algorithm with competitive ratio bounded by min(log_φ n, log_φ 1/2D) + O(1), where φ = (1 + √5)/2, n is the number of requests, and D < 1 is the guaranteed startup delay measured as a fraction of the time for a full stream. In this paper we give a new on-line algorithm that improves the competitive ratio to a constant (precisely, 5). Our result implies that the performance does not deteriorate in dealing with a large number of requests and a small startup delay.

Original language	English
Title of host publication	Proceedings - 15th International Parallel and Distributed Processing Symposium, IPDPS 2001
Publisher	IEEE
Pages	2165-2172
Number of pages	8
ISBN (Electronic)	0769509908, 0769509916, 0769509924, 9780769509907
DOIs	https://doi.org/10.1109/IPDPS.2001.925217
Publication status	Published - 23 Apr 2001
Event	15th International Parallel and Distributed Processing Symposium, IPDPS 2001 - San Francisco, United States Duration: 23 Apr 2001 → 27 Apr 2001 https://ieeexplore.ieee.org/xpl/conhome/7373/proceeding (Conference Proceedings)

Publication series

Name	Proceedings - International Parallel and Distributed Processing Symposium, IPDPS

Conference

Conference	15th International Parallel and Distributed Processing Symposium, IPDPS 2001
Country/Territory	United States
City	San Francisco
Period	23/04/01 → 27/04/01
Internet address	https://ieeexplore.ieee.org/xpl/conhome/7373/proceeding (Conference Proceedings)

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 9 Industry, Innovation, and Infrastructure

Access to Document

10.1109/IPDPS.2001.925217

Cite this

@inproceedings{5de312928a4a4d5c9b685cc65e41d593,

title = "A 5-Competitive On-line Scheduler for Merging Video Streams",

abstract = "This paper is concerned with an on-line scheduling problem arising from video-on-demand (VOD) systems that support stream merging. Most previous work on this problem focuses on empirical results; Bar-Noy and Ladner [3] are the first to consider worst-case performance and give an on-line algorithm with competitive ratio bounded by min(logφ n, logφ 1/2D) + O(1), where φ = (1 + √5)/2, n is the number of requests, and D < 1 is the guaranteed startup delay measured as a fraction of the time for a full stream. In this paper we give a new on-line algorithm that improves the competitive ratio to a constant (precisely, 5). Our result implies that the performance does not deteriorate in dealing with a large number of requests and a small startup delay.",

author = "Chan, \{Wun Tat\} and Lam, \{Tak Wah\} and Ting, \{Hing Fung\} and Wong, \{Wai Ha\}",

note = "Publisher Copyright: {\textcopyright} 2001 by The Institute of Electrical and Electronics Engineers, Inc.; 15th International Parallel and Distributed Processing Symposium, IPDPS 2001 ; Conference date: 23-04-2001 Through 27-04-2001",

year = "2001",

month = apr,

day = "23",

doi = "10.1109/IPDPS.2001.925217",

language = "English",

series = "Proceedings - International Parallel and Distributed Processing Symposium, IPDPS",

publisher = "IEEE",

pages = "2165--2172",

booktitle = "Proceedings - 15th International Parallel and Distributed Processing Symposium, IPDPS 2001",

address = "United States",

url = "https://ieeexplore.ieee.org/xpl/conhome/7373/proceeding",

}

Chan, WT, Lam, TW, Ting, HF & Wong, WH 2001, A 5-Competitive On-line Scheduler for Merging Video Streams. in Proceedings - 15th International Parallel and Distributed Processing Symposium, IPDPS 2001. Proceedings - International Parallel and Distributed Processing Symposium, IPDPS, IEEE, pp. 2165-2172, 15th International Parallel and Distributed Processing Symposium, IPDPS 2001, San Francisco, California, United States, 23/04/01. https://doi.org/10.1109/IPDPS.2001.925217

A 5-Competitive On-line Scheduler for Merging Video Streams. / Chan, Wun Tat; Lam, Tak Wah; Ting, Hing Fung et al.
Proceedings - 15th International Parallel and Distributed Processing Symposium, IPDPS 2001. IEEE, 2001. p. 2165-2172 (Proceedings - International Parallel and Distributed Processing Symposium, IPDPS).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - A 5-Competitive On-line Scheduler for Merging Video Streams

AU - Chan, Wun Tat

AU - Lam, Tak Wah

AU - Ting, Hing Fung

AU - Wong, Wai Ha

PY - 2001/4/23

Y1 - 2001/4/23

N2 - This paper is concerned with an on-line scheduling problem arising from video-on-demand (VOD) systems that support stream merging. Most previous work on this problem focuses on empirical results; Bar-Noy and Ladner [3] are the first to consider worst-case performance and give an on-line algorithm with competitive ratio bounded by min(logφ n, logφ 1/2D) + O(1), where φ = (1 + √5)/2, n is the number of requests, and D < 1 is the guaranteed startup delay measured as a fraction of the time for a full stream. In this paper we give a new on-line algorithm that improves the competitive ratio to a constant (precisely, 5). Our result implies that the performance does not deteriorate in dealing with a large number of requests and a small startup delay.

AB - This paper is concerned with an on-line scheduling problem arising from video-on-demand (VOD) systems that support stream merging. Most previous work on this problem focuses on empirical results; Bar-Noy and Ladner [3] are the first to consider worst-case performance and give an on-line algorithm with competitive ratio bounded by min(logφ n, logφ 1/2D) + O(1), where φ = (1 + √5)/2, n is the number of requests, and D < 1 is the guaranteed startup delay measured as a fraction of the time for a full stream. In this paper we give a new on-line algorithm that improves the competitive ratio to a constant (precisely, 5). Our result implies that the performance does not deteriorate in dealing with a large number of requests and a small startup delay.

UR - https://www.scopus.com/pages/publications/84981276404

U2 - 10.1109/IPDPS.2001.925217

DO - 10.1109/IPDPS.2001.925217

M3 - Conference proceeding

AN - SCOPUS:84981276404

T3 - Proceedings - International Parallel and Distributed Processing Symposium, IPDPS

SP - 2165

EP - 2172

BT - Proceedings - 15th International Parallel and Distributed Processing Symposium, IPDPS 2001

PB - IEEE

T2 - 15th International Parallel and Distributed Processing Symposium, IPDPS 2001

Y2 - 23 April 2001 through 27 April 2001

ER -

A 5-Competitive On-line Scheduler for Merging Video Streams

Abstract

Publication series

Conference

UN SDGs

Access to Document

Other files and links

Fingerprint

Cite this