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.
Recommended Citation
Ronald I. Greenberg and H.-C. Oh. Packet routing in networks with long wires. In Proceedings of 30th Allerton Conference on Communication, Control, and Computing, pages 664--673, 1992.
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License.
Copyright Statement
A revised version can be found at http://ecommons.luc.edu/cs_facpubs/98
Presentation slides from 30th Allerton Conference on Communication, Control and Computing
Included in
Other Computer Engineering Commons, Other Operations Research, Systems Engineering and Industrial Engineering Commons, Theory and Algorithms Commons
