On-line stream merging in a general setting

被引：6

作者：

Chan, WT ^{[1
]}

Lam, TW ^{[1
]}

Ting, HF ^{[1
]}

Wong, PWH ^{[1
]}

机构：

[1] Univ Hong Kong, Dept Comp Sci, Hong Kong, Hong Kong, Peoples R China

来源：

THEORETICAL COMPUTER SCIENCE | 2003年 / 296卷 / 01期

关键词：

D O I：

10.1016/S0304-3975(02)00430-9

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This paper is concerned with on-line scheduling algorithms for merging streams in a video-on-demand system so as to minimize the server bandwidth. We present the first algorithm that has a constant competitive factor (precisely, 5). Our algorithm, unlike previous ones, is not limited to the scenario where clients are equipped with large buffer and client receiving bandwidth. It remains 5-competitive in all settings of buffer size and receiving bandwidth. Technically speaking, our algorithm is based on a novel observation that the behavior of any schedule can be modeled by a rectilinear (binary) tree on a grid. This observation eases the analysis of our algorithm as well as the optimal algorithm. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：27 / 46

页数：20

共 17 条

[1] On optimal batching policies for video-on-demand storage servers [J].

Aggarwal, CC ;

Wolf, JL ;

Yu, PS .

PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON MULTIMEDIA COMPUTING AND SYSTEMS, 1996, :253-258

[2]

Bar-Noy A, 2001, SIAM PROC S, P364

[3]

Bar-Noy A, 2002, PROC SPIE, V4673, P115

[4]

BORODIN A, 1998, ONLINE COMPUTATIN CO

[5]

CAI Y, 1999, P SPIE ACM C MULT CO, P204

[6] The dyadic stream merging algorithm [J].

Coffman, EG ;

Jelenkovic, P ;

Momcilovic, P .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2002, 43 (01) :120-137

[7] Dynamic batching policies for an on-demand video server [J].

Dan, A ;

Sitaram, D ;

Shahabuddin, P .

MULTIMEDIA SYSTEMS, 1996, 4 (03) :112-121

[8] Minimizing bandwidth requirements for on-demand data delivery [J].

Eager, D ;

Vernon, M ;

Zahorjan, J .

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2001, 13 (05) :742-757

[9]

Eager D, 2000, PROC SPIE, V3969, P206

[10] Optimal and efficient merging schedules for video-on-demand servers [J].

Eager, D ;

Vernon, M ;

Zahorjan, J .

ACM MULTIMEDIA 99, PROCEEDINGS, 1999, :199-202

← 1 2 →