Document Type

Article

Publication Date

10-1992

Publication Title

Proceedings of 30th Allerton Conference on Communication, Control, and Computing

Pages

664--673

Abstract

In this paper, we examine the packet routing problem for networks with wires of differing length. We consider this problem in a network independent context, in which routing time is expressed in terms of “congestion” and “dilation” measures for a set of packet paths. We give, for any constant ε > 0, a randomized on-line algorithm for routing any set of N packets in O((Clg^ε(Nd)+Dlg(Nd))/lglg(Nd)) time, where C is the maximum congestion and D is the length of the longest path, both taking wire delays into account, and d is the longest path in terms of number of wires. We also show that for edge-simple paths, there exists a schedule (which could be found offline) of length O (cd_max+D) lg(d_max)/lglg(d_max) , where d_max is the maximum wire delay in the network. These results improve upon those of Leighton, Maggs, and Rao, which assume that unit time suffices to traverse a wire of any length. Our results also improve upon those of Shmoys, Stein, and Wein for job-shop scheduling as long as we incorporate a technical restriction on the job-shop problem.

Creative Commons License

Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License.