Minimal Order Loop-Free Routing Strategy

Conventional distributed adaptive routing strategies usually work well for packet switching networks only in the absence of link/mode failures. However, they cannot avoid looping messages for an extended period in case of link/node failures. In this paper, we develop a multiorder routing strategy which is loop-free even in the presence of link/node failures. Unlike most conventional methods in which the same routing strategy is applied indiscriminately to all nodes in the network, nodes under the proposed strategy may adopt different routing strategies in accordance with the network structure. We not only develop the formulas to determine the minimal order of routing strategy for each node to eliminate looping completely, but also propose a systematic procedure to strike a compromise between the operational overhead and network adaptability. Several illustrative examples are also presented. © 1990 IEEE