Packet Routing in Networks with Long Wires

<p> 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 &varepsilon; &gt; 0, a randomized on-line algorithm for routing any set of <em> N </em> packets in <em> O </em> (( <em> C </em> lg ^&varepsilon; ( <em> Nd </em> ) + <em> D </em> lg( <em> Nd </em> ))/lg lg( <em> Nd </em> )) time, where <em> C </em> is the maximum congestion and <em> D </em> is the length of the longest path, both taking wire delays into account, and <em> d </em> is the longest path in terms of <em> number </em> of wires. We also show that for edge-simple paths, there exists a schedule (which could be found off-line) of length <em> O </em> (( <em> cd </em> _max + <em> D </em> ) (lg( <em> d </em> _max )/lg lg ( <em> d </em> _max ))), where <em> d </em> _max 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.</p>