Loss-bounded analysis for differentiated services

被引：15

作者：

Kesselman, A ^{[1
]}

Mansour, Y ^{[1
]}

机构：

[1] Tel Aviv Univ, Sch Comp Sci, IL-69978 Tel Aviv, Israel

来源：

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC | 2003年 / 46卷 / 01期

关键词：

competitive analysis; online algorithms; loss-bounded analysis; buffer scheduling; DiffServ;

D O I：

10.1016/S0196-6774(02)00270-5

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We consider a network providing Differentiated Services (DiffServ) which allow network service providers to offer different levels of Quality of Service (QoS) to different traffic streams. We focus on loss and first show that only trivial bounds could be obtained by means of traditional competitive analysis. Then we introduce a new approach for estimating loss of an online policy called loss-bounded analysis. In loss-bounded analysis the loss of an online policy is bounded by the loss of an optimal offline policy plus a constant fraction of the benefit of the online policy. We relate the loss-bounded analysis to the throughput-competitive analysis. We derive tight upper and lower bounds for various settings of DiffServ parameters using the new loss-bounded model. We believe that loss-bounded analysis is an important technique that can complement traditional competitive analysis providing new insight and interesting results. (C) 2002 Elsevier Science (USA). All rights reserved.

引用

页码：79 / 95

页数：17

共 18 条

[1]

Aiello W. A., 2000, Proceedings IEEE INFOCOM 2000. Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (Cat. No.00CH37064), P431, DOI 10.1109/INFCOM.2000.832216

[2]

BERNET Y, 2000, CONCEPTUAL MODEL DIF

[3]

Borodin A, 1998, ONLINE COMPUTATION C

[4]

DOVROLIS C, P ACM SIGCOMM 99

[5]

HAHNE EL, 2001, P SPAA, P53

[6]

KESSELMAN A, 2001, P 33 ANN ACM S THEOR, P520

[7]

KESSELMAN A, 2002, IN PRESS INFOCOM

[8]

MANSOUR Y, 2000, P PODC

[9]

MAY M, 1999, P IEEE INFOCOM MARCH

[10]

Nandagopal T., 2000, Proceedings IEEE INFOCOM 2000. Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (Cat. No.00CH37064), P421, DOI 10.1109/INFCOM.2000.832215

← 1 2 →