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.