Document Type

Article

Publication Date

12-1995

Publication Title

Journal of Parallel and Distributed Computing

Volume

31

Issue

2

Pages

153-158

Publisher Name

Elsevier

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 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.

Comments

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).

Creative Commons License

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

Download

Share

COinS