Substantial effort has been devoted to the study of store-and-forward packet routing algorithms for hypercubic networks. The fastest algorithms are randomized, and can solve any one-to-one packet routing problem on an N-node hypercube in packet steps with high probability [3, 14, 18, 19, 22, 23, 24, 26, 27]. Of the deterministic algorithms [5, 9, 10], the fastest requires packet steps [9]. One drawback to these algorithms, however, is that they all require bit steps when implemented on real parallel machines such as the Connection Machine. The reason is that most parallel machines operate in a bit-serial or byte-serial fashion because of pin limitations on switches. Since packets always contain at least bits of addressing information, a typical packet step really consists of bit steps.
In general, fast bit-serial algorithms are harder to design than store-and-forward algorithms. This is particularly true on a hypercube since the head of a -bit packet should be close to its destination before the tail of the packet leaves the origin. Moreover, while the packet is spread out and moving through the network, it prevents up to wires from being used by other packets. This phenomenon raises issues such as deadlock and livelock [11] that do not arise in the simpler store-and-forward model.
In this paper, we describe an asymptotically optimal randomized algorithm for packet routing on the hypercube. The algorithm solves any permutation routing problem for packets that are M bits long (not including addressing information) in bit steps with high probability. Moreover, the algorithm requires each node of the hypercube to deal with only new packets at each step. The algorithm works in either the wormhole [11] or cut-through [16] models of routing.
The algorithm also solves the problem of on-line circuit switching in an -dilated hypercube, where a b-dilated hypercube is one in which each edge is replaced by a bundle of b edges. Previously, it was known that for any one-to-one routing problem, edge-disjoint paths could be established from the inputs to the outputs of a Benes network [6]. The Benes network can be embedded in a 4-dilated hypercube. However, the only on-line algorithms previously known for finding the paths in a Benes network or hypercube require steps [8, 21]. Our algorithm finds a set of edge-disjoint paths on the -dilated hypercube, on-line, in bit steps.
The algorithm has three essential features: (1) it uses Valiant's paradigm of routing to random intermediate destinations, (2) it uses a new embedding of a -dilated butterfly into the hypercube that is based on 1-error correcting codes, and (3) it implements a bit-serial version of Ranade's algorithm [18, 19, 23] that eliminates the ghost packets and the need for packets to carry -bit ranks.
Most hypercube routing algorithms [15, 18, 19, 23, 26, 27] are oblivious. A deterministic oblivious routing algorithm is one in which the path taken by a packet through the network is a function of the origin and destination of the packet. Deterministic oblivious algorithms have previously been called oblivious algorithms [7]. A randomized oblivious algorithm is one in which each packet independently chooses its path according to a probability distribution which is a function of its origin and destination.
The algorithms described in this paper are not oblivious. In fact, we show that any randomized oblivious algorithm on any N-node network with maximum node degree d requires bit steps, with high probability, for almost all permutations, where M is the packet size (not including addressing information). For routing -bit messages on the hypercube, the lower bound is bit steps. This result extends the Borodin-Hopcroft -packet-step lower bound for deterministic oblivious algorithms [7] to randomized oblivious algorithms. The lower bound for deterministic oblivious algorithms has recently been improved to by Kaklamanis, Krizanc, and Tsantilas [15], who also provide a deterministic oblivious store-and-forward algorithm for routing on the hypercube in steps. Further work on bounds for oblivious routing and trade-offs between time and randomness can be found in [17].
Although our algorithm is the first route permutations on the hypercube in bit steps with high probability, Leighton and Plaxton [20] have subsequently achieved a stronger result. They show how to sort on bounded-degree hypercubic networks in steps (with the caveat that with very small probability the output will not be in sorted order). Their algorithm can be pipelined and hence can achieve permutation routing as well as many-to-one and one-to-many routing on hypercubic networks in bit steps with high probability, using standard reductions of routing to sorting (plus a minor fix to take care of the case when the output is not sorted). Nonetheless, techniques used in this paper have recently been extended by Aiello and Leighton [1] to construct improved embeddings of trees and other structures in a hypercube and to design more efficient and robust algorithms for reconfiguring a hypercube around random or worst-case faults.
A natural open problem is to find a deterministic algorithm for routing (or sorting) in bit steps on a hypercubic network. The only known bounded-degree networks capable of deterministic -bit-step routing are the AKS sorting circuit [2] and the multibutterfly [4, 25]. However, these sorting and routing algorithms rely on expansion properties that the hypercube and its derivatives do not possess.
The remainder of the paper is divided into sections as follows. We start by describing two bit-step algorithms for routing on a -dilated butterfly in Section 2. The first is quite simple, but needs a switch to handle up to new packets at once. The second is more efficient, allowing a switch to handle at most 2 new packets at each step. In Section 3, we show how to implement the algorithms on a hypercube by embedding the -dilated butterfly in the hypercube. The lower bound for randomized oblivious routing is described in Section 4.