The running times of the algorithms in this paper are described in two
models, the bit model and the word model. In the
bit model, each network node can be thought of as a finite automaton.
In each bit step, the node can receive a single bit of
information along each of its incoming edges (of which
there are at most a constant number), change to a new state, and
output a single bit of information on each of its outgoing edges (of
which there are at most a constant number). In the word model, each
edge in an N-node network can transmit a word consisting of up
to 
bits in a single step.
To simplify the explanation of the algorithms and results in this
paper, we have adopted some conventions that may differ from the way
that this material is treated in the more applied literature. For
example, we generally route paths in a node-disjoint fashion. In
practice, however, it may be desirable to route paths in an
edge-disjoint manner instead. Our definitions and results can also be
applied in this setting, as demonstrated in
Section 5.3.3. Note that node-disjoint paths are
automatically edge-disjoint, and any algorithm for routing
edge-disjoint paths on a degree-d network can be converted into one
for routing node-disjoint paths by replacing each node with a 
complete bipartite graph.