About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SIAM Journal on Computing
Paper
Greedy packet scheduling
Abstract
Scheduling packets to be forwarded over a link is an important subtask of the routing process in both 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 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 Ω(d √k + k, and even for d = Ω (n).