Direct routing is the special case of
bufferless routing where
N packets, once injected into the network, must be delivered to their destinations without collisions. We give a general treatment
of three facets of direct routing:
| 1. |
Algorithms. We present a polynomial-timegreedy direct algorithm which is worst-case optimal. We improve the bound of the greedy algorithm for special cases, by applying
variants of this algorithm to commonly used network topologies. In particular, we obtainnear-optimal routing time for thetree, mesh, butterfly, andhypercube.
|
| 2. |
Complexity. By a reduction from Vertex Coloring, we show that optimal Direct Routing is inapproximable, unless P=NP.
|
| 3. |
Lower Bounds for Buffering. We show that certain direct routing problems cannot be solved efficiently; in order to solve these problems,any routing algorithm needs buffers. We give non-trivial lower bounds on such buffering requirements for general routing algorithms.
|
Key Words Communication algorithms - Direct routing - Bufferless routing - Congestion - Dilation
A preliminary version of this paper appears in theProceedings of the 12th Annual European Symposium on Algorithms (ESA 2004) [11].
Partially supported by the EU within the 6th Framework Programme under Contract 001907 “Dynamically Evolving, Large Scale
Information Systems” (DELIS).