M.Sc Thesis

M.Sc StudentTsirkin Michael
SubjectDelivery Times in Packet Networks under Full Load
DepartmentDepartment 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.