Proceedings of 30th Allerton Conference on Communication, Control, and Computing
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.
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.
A revised version can be found at http://ecommons.luc.edu/cs_facpubs/98