All of our algorithms are presented in the packet model of computation. In this model time is partitioned into synchronous steps. At each time step, one packet can be transmitted across each edge of the network. The packet model is the natural abstraction for store and forward routing algorithms used on machines such as the NCube, NASA MPP, Intel Hypercube, and Transputer-based machines. It is also robust in the sense that it allows combining, it corresponds nicely to the various PRAM models, and it does not make assumptions about packet lengths. Consequently, it is the most studied model in the literature.
Other models of interest are the circuit switching model [12] and the cut-through or wormhole model [9]. These models arise in practice and are also of theoretical interest, although less is known about them. Although our results have some limited applications in these models, we will primarily concern ourselves with the packet model in this paper.