Efficient Bufferless Routing on Leveled Networks Costas Busch Shailesh Kelkar Malik Magdon-Ismail Bufferless Routing Hot-potato Routing Congestion We study bufferless packet routing in which packets, once injected, cannot be buffered at nodes. Given a set of preselected packet paths, a well known lower bound on the routing time is [omega](C + D), where D is the dilation (maximum path length) and C the congestion (maximum number of times an edge is used). We show that for leveled networks, one can obtain bufferless routing that is at most one or two logarithmic factors from the lower bound: i. We give a centralized bufferless algorithm with routing time O(C · log(DN) + D), where N is the number of packets. ii. We convert the centralized algorithmto a distributed bufferless algorithmwith routing time O(C · log2(DN) + D · log(DN)). The heart of our approach is a new technique, reverse- simulation, which constructs an efficient (at most logarithmic extra cost) distributed em- ulation of the centralized algorithm. Our algorithms improve the best previously known result specialized for leveled networks by multiple logarithmic factors. Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY 08/24/2004 cs-04-13
Efficient Bufferless Routing on Leveled Networks
Costas Busch
Shailesh Kelkar
Malik Magdon-Ismail
Bufferless Routing
Hot-potato Routing
Congestion
We study bufferless packet routing in which packets, once injected, cannot be buffered at nodes. Given a set of preselected packet paths, a well known lower bound on the routing time is [omega](C + D), where D is the dilation (maximum path length) and C the congestion (maximum number of times an edge is used). We show that for leveled networks, one can obtain bufferless routing that is at most one or two logarithmic factors from the lower bound: i. We give a centralized bufferless algorithm with routing time O(C · log(DN) + D), where N is the number of packets. ii. We convert the centralized algorithmto a distributed bufferless algorithmwith routing time O(C · log2(DN) + D · log(DN)). The heart of our approach is a new technique, reverse- simulation, which constructs an efficient (at most logarithmic extra cost) distributed em- ulation of the centralized algorithm. Our algorithms improve the best previously known result specialized for leveled networks by multiple logarithmic factors.
Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY
08/24/2004
cs-04-13