Universal Bufferless Routing Costas Busch Malik Magdon-Ismail Marios Mavronicolas In a routing problem, a set of packets must be routed from their sources to their destinations along specified paths in a connected network. The celebrated result of Leighton, Maggs and Rao (1988) established, non-constructively, the existence of a routing schedule which uses constant size buffers and routes the packets in optimal time. Since then, constructive algorithms, as well as generalizations to distributed, buffered routing schedules have been developed. A long standing open problem is to give or show the existence of bufferless 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 bufferless algorithm by emulating a universal buffered algorithm. The heart of the emulation is to replace packet buffering with packet circulation. The cost of the emulation on the routing time is proportional to the square of the node buffer size used by the buffered algorithm. We apply this emulation to a simple randomized universal buffered algorithm to obtain a distributed, universal bufferless algorithm with routing time rt that is at most a poly-logarithmic factor from optimal: rt = O(rt* · log3(n + N)) , where n is the size of the network, N is the number of packets and rt* is the optimal routing time for the specified paths. Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY 04/16/2004
Universal Bufferless Routing
Costas Busch
Malik Magdon-Ismail
Marios Mavronicolas
In a routing problem, a set of packets must be routed from their sources to their destinations along specified paths in a connected network. The celebrated result of Leighton, Maggs and Rao (1988) established, non-constructively, the existence of a routing schedule which uses constant size buffers and routes the packets in optimal time. Since then, constructive algorithms, as well as generalizations to distributed, buffered routing schedules have been developed. A long standing open problem is to give or show the existence of bufferless 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 bufferless algorithm by emulating a universal buffered algorithm. The heart of the emulation is to replace packet buffering with packet circulation. The cost of the emulation on the routing time is proportional to the square of the node buffer size used by the buffered algorithm. We apply this emulation to a simple randomized universal buffered algorithm to obtain a distributed, universal bufferless algorithm with routing time rt that is at most a poly-logarithmic factor from optimal: rt = O(rt* · log3(n + N)) , where n is the size of the network, N is the number of packets and rt* is the optimal routing time for the specified paths.
Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY
04/16/2004