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
Author Manuscript
This is a pre-publication author manuscript of the final, published article.
