Direct Routing

Direct Routing Costas Busch Malik Magdon-Ismail Marios Mavronicolas Paul Spirakis Direct routing is a special case of bufferless routing in which packets are not allowed to conflict with each other. The task is to compute the injection times of the packets so that they don’t conflict. A well known lower bound on the routing time of any algorithm is (C + D), where the congestion C is the maximum number of paths that use any edge, and the dilation D is the maximum length of any path. We study the extent to which direct routing algorithms can achieve this lower bound. We present a simple greedy direct routing algorithm for arbitrary routing problems that has routing time O(C · D). We show that this routing time is worst case optimal. In particular, we construct a “hard” routing problem on the mesh, for which any direct routing algorithm has routing time (C ·D), while C + D = [theta]([square root of]C · D). We then consider many interesting routing problems on commonly used network topologies. We show that variants of the simple greedy algorithm achieve optimal routing time. The routing problems and corresponding routing times (rt) are: i. Trees: arbitrary routing problems on arbitrary tree topologies (rt = O(C + D)). ii. Mesh with n nodes: permutations (rt = O(pn)); arbitrary one-bend paths (rt = O(C + D)). iii. Butterfly with n inputs: random destinations and permutations (rt = O(lg n) w.h.p.). iv. Hypercube with n nodes: random destinations and permutations (rt = O(lg n) w.h.p.). Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY 07/11/2003 cs-03-08

Direct Routing

Costas Busch

Malik Magdon-Ismail

Marios Mavronicolas

Paul Spirakis

Direct routing is a special case of bufferless routing in which packets are not allowed to conflict with each other. The task is to compute the injection times of the packets so that they don’t conflict. A well known lower bound on the routing time of any algorithm is (C + D), where the congestion C is the maximum number of paths that use any edge, and the dilation D is the maximum length of any path. We study the extent to which direct routing algorithms can achieve this lower bound. We present a simple greedy direct routing algorithm for arbitrary routing problems that has routing time O(C · D). We show that this routing time is worst case optimal. In particular, we construct a “hard” routing problem on the mesh, for which any direct routing algorithm has routing time (C ·D), while C + D = [theta]([square root of]C · D). We then consider many interesting routing problems on commonly used network topologies. We show that variants of the simple greedy algorithm achieve optimal routing time. The routing problems and corresponding routing times (rt) are: i. Trees: arbitrary routing problems on arbitrary tree topologies (rt = O(C + D)). ii. Mesh with n nodes: permutations (rt = O(pn)); arbitrary one-bend paths (rt = O(C + D)). iii. Butterfly with n inputs: random destinations and permutations (rt = O(lg n) w.h.p.). iv. Hypercube with n nodes: random destinations and permutations (rt = O(lg n) w.h.p.).

Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY

07/11/2003

cs-03-08