Journal of Parallel and Distributed 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 Npackets in O((C lgϵ(Nd) + D lg(Nd))/lg lg(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 off-line) of length O((cdmax + D) (lg(dmax)/lg lg (dmax))), where dmax is the maximum wire delay in the network. These results improve upon previous routing results which assume that unit time suffices to traverse a wire of any length. They also yield improved results for job-shop scheduling as long as we incorporate a technical restriction on the job-shop problem.
Journal of Parallel and Distributed Computing, Volume 31, Issue 2, December 1995, Pages 153–158.
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License.
© Elsevier, 1995.
Author Posting. © Elsevier, 1995. This is the author's version of the work. It is posted here by permission of Elsevier for personal use, not for redistribution.The definitive version was published in Journal of Parallel and Distributed Computing, Volume 31, Issue 2, December, 1995. http://dx.doi.org/10.1006/jpdc.1995.1153
This is a revised version of the conference paper that can be found at http://ecommons.luc.edu/cs_facpubs/165 (along with presentation slides).