Direct routing: Algorithms and complexity

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-time greedy direct algorithm which is worst-case optimal. We improve the hound of the greedy algorithm for special cases, by applying variants of this algorithm to commonly used network topologies. In particular, we obtain near-optimal routing time for the tree. mesh, butterfly, and hypercube. 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.