Some Theorems and Procedures for Loop-Free Rooting in Directed Communications Networks

The fundamental problem which besets people concerned with the design of communication networks is how to provide a network which is, at once: (i) Of sufficient routing capability to allow any two users to be connected with a high probability of success. (it) Economical in its use of transmission facilities and switching centers. 465 466 T H E B E L L SYSTEM TECHNICAL JOURNAL, APRIL 1 ! ) ( 3 S (in) Capable of surviving extensive natural or man-made damage. (iv) Adaptable to changing traffic patterns and overload situations. (t>) Capable of being engineered and implemented in small sections, over a period of years, by many different people. This is a problem of such complexity that, with the present state of the theory, it must be attacked piecemeal. This paper deals with a small but important section of the problem. It considers some of the topological properties of communication networks and examines a class of alternate routing strategies from a general point of view. Our purpose is to state rules which will allow the orderly production of routing patterns, for arbitrary networks, by a computer. We approach the problem in three stages: (t) Several simple rules are stated for producing "loop-free" routing patterns. (u) The rules are "generalized" to allow the proof of some theorems about the extent of their application. {Hi) A more limited but practical statement of the rules is presented followed by several heuristic procedures, based on these rules, which can be used to specify "good" routing patterns from the large number which can be generated.