A routing algorithm establishes an appropriate path from any given source to a destination. The objective of network routing is to maximize network throughput with minimal cost in terms of path length. To maximize throughput, a routing algorithm has to provide as many communication paths as possible. To minimize the cost of paths, the shortest paths have to be provided. However, there is always a trade-off between these two objectives. Most routing algorithms are based on assigning a cost measure to each link in a network. The cost could be a fixed quantity related to parameters such as the link length, the bandwidth of a link, or the estimated propagation delay. Each link has a cost associated with it and in most cases it is assumed that the links have equal cost.

An interconnection network is strictly non-blocking if there exists a routing algorithm to add a new connection without disturbing existing connections [292]. A network is rearrangeable if its permitted states realize every permutation or allowable set of requests; here it is possible to rearrange existing connections if necessary [292]. Otherwise it is blocking.

The store-and-forward operation in packet switching incurs a time delay and causes significant performance degradation. If the algorithm is used in a packet-switching network, the total time delay of a data packet is obtained by summing up the time delay at each intermediate node. Since non-availability of any link along a route causes the route not to be available, the network...