Packet Routing in Networks with Long Wires

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 \u22congestion\u22 and \u22dilation\u22 measures for a set of packet paths. We give, for any constant ϵ \u3e 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