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 inde pendent context, in which routing time is expressed in terms of ''cong estion'' and ''dilation'' measures for a set of packet paths. We give, for any constant epsilon > 0, a randomized on-line algorithm for rout ing any set of N packets in O((C lg(epsilon)(Nd) + D lg(Nd))/lg lg(Nd) ) time, where C is the maximum congestion and D is the length of the l ongest path, both taking wire delays into account, and d is the longes t 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 leng th O((cd(max) + D) (lg(d(max))/lg lg (d(max))), where d(max) is the ma ximum wire delay in the network. These results improve upon previous r outing results which assume that unit time suffices to traverse a wire of any length, They also yield improved results for job-shop scheduli ng as long as we incorporate a technical restriction on the job-shop p roblem. (C) 1995 Academic Press, Inc