Universal Bufierless Routing
Costas Busch, Malik Magdon‐Ismail, Marios Mavronicolas · 2004
In a routing problem, a set of packets must be routed from their sources to their destinations along specifled paths in a connected network. Given paths with congestion C and dilation D a lower bound on the routing time is ›(C + D). The celebrated result of Leighton, Maggs and Rao (1988) established, non-constructively, the existence of a routing schedule which uses constant size bufiers and routes the packets in optimal time O(C + D). Since then, constructive algorithms, as well as generalizations to distributed, bufiered routing schedules have been developed. A long standing open problem is to give or show the existence of bufierless routing algorithms with optimal performance guarantees. This is the problem we address here. Our main result is a new deterministic technique that constructs a universal bufierless algorithm by emulating a universal bufiered algorithm. The heart of the emulation is to replace packet bufiering with packet circulation on regions of the network. The cost of the emulation on the routing time is proportional to the square of the node bufier size used by the bufiered algorithm. We apply this emulation to a simple randomized universal bufiered algorithm to obtain a distributed, universal bufierless algorithm with routing time the optimal routing time within a poly-logarithmic factor: O i (C + D) ¢ log 3 (n + N) ¢ ;