Greedy Packet Scheduling
Israel Cidon Shay Kutten Yishay Mansour David Peleg
Abstract
Scheduling packets to be forwarded over a link is an important subtask of the routing process both in parallel
computing and in communication networks. This paper investigates the simple class of greedy scheduling algorithms,
namely, algorithms that always forward a packet if they can. It is first proved that for various "natural" classes of
routes, the time required to complete the transmission of a set of packets is bounded by the number of packets, k, and
the maximal route length, d, for any greedy algorithm (including the arbitrary scheduling policy). Next, tight time
bounds of d + k - 1 are proved for a specific greedy algorithm on the class of shortest paths in n-vertex
networks. Finally it is shown that when the routes are arbitrary, the time achieved by various "natural" greedy
algorithms can be as bad as \Omega (d*(sqrt(k)) + k), for any k, and even for d = \Omega (n).