M.Sc Student | Tsirkin Michael |
---|---|

Subject | Delivery Times in Packet Networks under Full Load |

Department | Department of Computer Science |

Supervisor | Mr. Adi Rosen |

We consider packet networks and make use of the “adversarial queuing theory” model introduced by Borodin et al. In this model, packet injection is modeled as being done by an adversary, which is characterized by a ”rate”. The rate can be informally described as the average number of packets injected per time step for any given communication link.

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 rate-1 adversaries was previously posed as an open question.

Among other, we give a queuing policy that guarantees
bounded delivery time whenever the rate-1 adversary itself can deliver all
packets in bounded time and adheres to certain additional conditions. On the
negative side we show that even the adversary itself cannot deliver all packets
in bounded time on all network topologies and for all rate-1 sequences of
packets. We thus answer an open question posed by Gamarnik. We further show
that delivering *all *packets while maintaining a finite upper bound on all
queue sizes (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. Thus any rate-1 adversary can have this property. We demonstrate an
online, distrubuted protocol that achieves bounded delivery time (and hence
reliability) against all rate-$1$ adversaries on all networks that do not
contain cycles of length N >2. We also show that on networks that contain
cycles of length N >2 there is no online protocol (even centralized) that
can achieve reliability against all rate-1 adversaries. We thus answer an open
question of Borodin et al.