Paper Info
Title
On Delivery Times in Packet Networks under Adversarial Traffic
Abstract
We consider packet networks and make use of the "adversarial queuing theory" model [10]. We are interested in the question of guaranteeing that all packets are actually delivered to destination, and of having an upper bound on the delivery times of all packets. Whether this is possible against all adversarial queuing theory rate-1 adversaries was previously posed as an open question [13],[10]. Among other things, we give a queuing policy that guarantees bounded delivery time whenever the rate-1 adversary injects a sequence of packets for which there exists a schedule with a finite upper bound on the delivery times of all packets, and adheres to certain additional conditions. On the negative side we show that there exist rate-1 sequences of packets for which there is no schedule with a finite upper bound on the delivery times of all packets. We thus answer an open question posed by Gamarnik [13]. We further show that delivering all packets while maintaining stability (we coin the term "reliability" for this property) can be done by an offline scheduler whenever the injection of packets is done at rate of at most 1. However, on the other hand, we also show that there is no online protocol (even centralized) that can achieve that property against all rate-1 adversaries. We thus answer an open question of Borodin et al. [10].
Year
DOI
Venue
2006
10.1007/s00224-006-1248-4
Theory Comput. Syst.
Keywords
Field
DocType
Directed Acyclic Graph,Delivery Time,Control Packet,Queue Size,Simple Path
Out-of-order delivery,Discrete mathematics,Existential quantification,Upper and lower bounds,Computer science,Network packet,Computer network,Queueing theory,Adversarial system,Bounded function,Distributed computing
Journal
Volume
Issue
ISSN
39
6
1432-4350
ISBN
Citations 
PageRank 
1-58113-840-7
7
0.49
References 
Authors
18
2
Name
Order
Citations
PageRank
Adi Rosen1132.08
Michael S. Tsirkin2312.57