ALCOMFT-TR-03-133

Costas Busch, Malik-Magdon Ismail, Marios Mavronicolas and Paul Spirakis
An Analysis of Direct Routing - Why do we need Buffers?
Patras and Cyprus. Work packages 2 and 4. December 2003.

Abstract: Direct routing is a special ocase of bufferless routing in which N packets must be routed without conflicts along specific paths. We show, by reduction from vertex coloring, that direct routing is NP-complete, and that it is as hard to approximate as coloring. This result shows that buffering is necessary in order to tractably compute routing schhedules. Further, we construct a hard routing problem for which any routing algorithm requires a vast amount of total packet buffering to approximate an optimal routing schedule with good approximation ratio.

We then study algorithms for efficient direct routing. We give a greedy routing algorithm for general direct routing problems with direct routing time that is worst-case optimal. Finally, we consider many interesting routing problems on commonly used network topologies for which variants of the greedy algorithm achieve optimal or near optimal (within logarithmic factors) routing times.

Postscript file: ALCOMFT-TR-03-133.ps.gz (218 kb).