On Delivery Times in Packet Networks under Adversarial Traffic |
| |
Authors: | Adi Rosen Michael S Tsirkin |
| |
Affiliation: | (1) Department of Computer Science, Technion, Haifa 32000, Israel |
| |
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]. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|