With Great Speed Come Small Buffers: Space-Bandwidth Tradeoffs for Routing

被引：2

作者：

Miller, Avery ^{[1
]}

Patt-Shamir, Boaz ^{[2
]}

Rosenbaum, Will ^{[3
]}

机构：

[1] Univ Manitoba, Dept Comp Sci, Winnipeg, MB, Canada

[2] Tel Aviv Univ, Sch Elect Engn, Tel Aviv, Israel

[3] Max Planck Inst Informat, Saarbrucken, Germany

来源：

PROCEEDINGS OF THE 2019 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING (PODC '19) | 2019年

基金：

加拿大自然科学与工程研究理事会; 以色列科学基金会;

关键词：

packet networks; adversarial queuing theory; packet forwarding; buffer overflow; multiple destinations; directed paths; directed trees; DELAY;

D O I：

10.1145/3293611.3331614

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We consider the Adversarial Queuing Theory (AQT) model, where packet arrivals are subject to a maximum average rate 0 <= rho <= 1 and burstiness sigma >= 0. In this model, we analyze the size of buffers required to avoid overflows in the basic case of a path. Our main results characterize the space required by the average rate and the number of distinct destinations: we show that O(ld(1/l) + sigma) space suffice, where d is the number of distinct destinations and l = left perpendicular1/rho left perpendicular; and we show that Omega( 1/ld(1/l) + sigma) space is necessary. For directed trees, we describe an algorithm whose buffer space requirement is at most 1+ d' + sigma where d' is the maximum number of destinations on any root-leaf path.

引用

页码：117 / 126

页数：10

共 20 条

[1]

Adler M., 2002, STACS 2002. 19th Annual Symposium on Theoretical Aspects of Computer Science. Proceedings (Lecture Notes in Computer Science Vol.2285), P88

[2]

Aiello W, 2003, SIAM PROC S, P771

[3] General dynamic routing with per-packet delay guarantees of O(distance+1/session rate) [J].