M.Sc Thesis

M.Sc StudentGordon Eyal
SubjectCompetitive Throughput Analysis of Greedy Protocols
on Directed Acyclic Networks
DepartmentDepartment of Computer Science
Supervisor MR Adi Rosen


The combination of the buffer sizes of routers deployed in the Internet, and the Internet traffic itself, leads routinely to the dropping of packets. Motivated by this, we are interested in the problem of maximizing the throughput of protocols that control packet networks. Moreover, we are interested in a setting where different packets have different priorities (or weights), thus taking into account Quality-of-Service considerations.

We first extend the Competitive Network Throughput (CNT) model introduced by Aiello et al. to the weighted packets case. We analyze the performance of online, local-control protocols by their competitive ratio, in the face of arbitrary traffic, using as a measure the total weight of the packets that arrive to their destinations, rather than being dropped en-route. We prove that on directed acyclic graphs (DAGs), any greedy protocol is competitive, with competitive ratio independent of the weights of the packets.  We give two independent upper bounds on the competitive ratio of general greedy protocols on DAGs. We further give lower bounds that show that our upper bounds cannot be improved (other than constant factors) in the general case.  Both our upper and lower bounds apply also to the unweighted case, and they improve previous results for that case. We thus give tight (up to constant factors) upper and lower bounds for both the unweighted and weighted cases.

In the course of proving our upper bounds we prove a lemma that gives upper bounds on the delivery times of packets by any greedy protocol on general DAGs when buffer size is unbounded. We believe that this lemma may be of independent interest and may find additional applications.