next up previous
Next: 1.3 The application of Up: 1 Introduction Previous: 1.1 Past work on

1.2 Our approach to routing

One deficiency with the state-of-the-art in packet routing is that aside from Valiant's paradigm of first routing to random destinations, all of the algorithms and their analyses are very specifically tied to the network on which the routing is to take place. For example, the way that the queue size is kept constant in the butterfly routing algorithms is quite different from the way that it is kept constant in the mesh routing algorithms. Moreover, the butterfly and hypercube algorithms are so specific to those networks that no tex2html_wrap_inline1911 -step constant-queue-size algorithm was previously known for the closely related shuffle-exchange network. The lack of a good routing algorithm for the shuffle-exchange network is one of the reasons that the butterfly is preferred to the shuffle-exchange network in practice.

Our approach to the problem differs from previous approaches in that we separate the process of selecting paths for the packets from the process of timing the movements of the packets along their paths. More precisely, we break a routing problem into two stages. In Stage 1, we select a path for each packet from its origin to its destination. In Stage 2, we schedule the movements of the packets along their paths. The focus of this paper is on Stage 2. The goal of Stage 2 is to find a schedule that minimizes both the time for the packets to reach their destinations and the number of packets that are queued at any node. The schedule must satsify the constraint that at each time step each edge in the network can transmit at most one packet.

Of course, there must be some correlation between the performance of the scheduling algorithm and the selection of the paths. In particular, the maximum distance d traveled by any packet is always a lower bound on the time required to route all packets. We call this distance the dilation of the set of paths. Similarly, the largest number of packets that must traverse a single edge during the entire course of the routing is a lower bound. We call this number the congestion c of the paths. In terms of these parameters, the goal of Stage 1 is to select paths for the packets that minimize c and d.

For many networks, Stage 1 is easy. We simply use Valiant's paradigm of first routing each message to a random destination. It is easily shown for meshes, butterflies, shuffle-exchange networks, etc., that this approach yields values of c and d that are within a small constant factor of the diameter of the network. Moreover, this technique also usually works for many-one problems provided that the address space is randomly hashed.

Stage 2 has traditionally been the hard part of routing. Curiously, however, we have found that by ignoring the underlying network and the method of path selection, Stage 2 actually becomes easier to solve! In [20] for example, Leighton, Maggs, and Rao show that for any set of packets whose paths have congestion c and dilation d, in any network, there is a schedule of length tex2html_wrap_inline1929 in which at most one packet traverses each edge at each time step, and in which the maximum queue size required is tex2html_wrap_inline1931 . In this paper, we show that there is an efficient randomized parallel scheduling algorithm for the entire class of bounded-degree leveled networks. In a leveled network, each edge is directed and connects a level i node to a level i+1 node, where the level numbers range from 0 to L. We call L the depth of the network. The algorithm produces a schedule of length tex2html_wrap_inline1943 with high probability, and uses constant-size queues.

By applying the approach just described, we can design fast routing algorithms for the most common fixed-connection networks. The first step is to convert the network at hand into a leveled network. In particular, we create a virtual leveled network that can be efficiently simulated by the existing network, and we figure out how to move packets between the two networks (i.e., we reduce the problem of routing on the given network to the problem of routing on a very similar leveled network). Next, we select paths for the packets so as to minimize the congestion c in the leveled network. Because the network is leveled, the dilation is automatically at most L, which in all of our algorithms is at most a constant factor larger than the diameter of the underlying network. The path selection strategy typically uses some combination of greedy paths and random intermediate destinations. We then conclude by applying the tex2html_wrap_inline1949 -step scheduling algorithm.



next up previous
Next: 1.3 The application of Up: 1 Introduction Previous: 1.1 Past work on



Bruce Maggs
Mon Jul 22 22:57:44 EDT 1996