IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. COM-29, NO. 1, JANUARY 1981 11 Distributed Algorithms for Generating Loop-Free Routes in Networks with Frequently Changing Topology ELI M. GAFNI, STUDENT MEMBER, IEEE, AND DIMITRI P. BERTSEKAS, SENIOR MEMBER, IEEE Abstract-We consider the problem of maintaining communication between the nodes of a data network and a central station in the presence of frequent topological changes as, for example, in mobile packet radio networks. We argue that flooding schemes have sig- nificant drawbacks for such networks, and propose a general class of distributed algorithms for establishing new loop-free routes to the station for any node left without a route due to changes in the network topology. By virtue of built-in redundancy, the algorithms are typically activated very infrequently and, even when they are, they do not involve any communication within the portion of the network that has not heen materially affected by a topological change. I. INTRODUCTION T HERE has been considerable interest recently in mobile packet radio (PR) networks (see, e.g., [l]). In such net- works, it is often necessary to use intermediate PR’s as re- peaters in order to transfer a message from a source to its destination. This gives rise to the usual routing problem en- countered in wire packet switched networks. Moreover, when the PR’s are mobile, the limited broadcast range, multipath interference, changes in shielding factors, etc., induce rapid topological changes. Thus, communication links frequently go down while other links are established. In such an en- vironment, it is a formidable task for a routing algorithm to keep communication going not to mention trying to optimize its transfer. Most of the routing schemes considered for PR networks involve the use of a central station that collects information regarding network connectivity and sets up routes from PR’s to itself. One possibility is to determine routes on the basis of a shortest path algorithm. We refer to such routes estab lished by the station as the primary routes and for the sake of the following discussion we assume that each PR has a single primary route to the station which may be altered periodically. A centralized routing algorithm of the type just described must by necessity deal with topological changes through the station. By this we mean that the station must be informed of the topological changes that have occured in order to maintain up-to-date connectivity information which is in turn the basis for altering primary routes when necessary. One possibility that comes to mind is to require that each PR that becomes aware of a topological change should immedi- Paper approved by the Editor for Computer Communication of the IEEE Communications Society for publication without oral presenta- tion. Manuscript received October 11, 1979; revised May 5, 1980. This work was supported by Grant ONR-N00014-75-C-1183. The authors are with the Laboratory for Information and Decision Systems, Massachusetts Institute ofTechnology, Cambridge, MA 02139. ately send this information to the station which in turn will take appropriate action if necessary. One difficulty with a scheme of this type, when topological changes are frequent, is that a great deal of information is passed on to the station. Thus, the station may find itself swamped with messages even though many of these messages do not convey truly important information since many of the topological changes can be only temporary, lasting, for ex- ample, for only a few seconds. A possible remedy would be for a PR to take a time out before reporting a topological change. This will result in a reduction of topological change messages flowing to the station at the expense of making decisions based on information that may be incomplete. A second and more irritating difficulty results from the fact that the primary routes over which a topological change is to be reported may have been themselves affected by the topo- logical change. Thus, a PR that has lost its primary route to the station due to a topological change must find an alternate route to report this fact to the station. In wire networks, there is a failsafe method for doing this, namely by using a flooding scheme whereby the topological change message is broadcast to all neighbors who in turn broadcast it to all their neighbors and so on until the message reaches the station. For PR net- works, however, a flooding scheme is quite unsuitable. The reason is that it triggers nearly simultaneous bursts of broad- cast messages throughout the network. This results in col- lisions of the type arising when two messages arrive at a PR, simultaneously. Collisions necessitate retransmissions, more collisions occur and the network can be driven to instability and ultimate collapse. We thus arrive at the conclusion that a scheme based on immediate reports of topological changes to the station coupled with some type of flooding scheme when a primary route fails is dubious for PR networks with frequent topo- logical changes. It thus appears to us that it is necessary to have, in addition to the primary routing algorithm operated by the station, a contingency routing algorithm to cope effectively with topological changes affecting primary routes. Desirable properties for such an algorithm are as follows. 1) It should provide some redundancy in the form of ad- ditional routes to the station which can be used when the primary route fails. This has the effect of drastically reducing the frequency with which any particular PR will lose all its routes to the station. 2) It should not rely on instructions from the station in establishing new routes when all the existing routes of any PR fail. 0090-6778/81/0100-0011$00.75 0 1981 IEEE12 IEEE TkANSACTIONS ON COMMUNICATIONS, VOL. COM-29, NO. 1, JANUARY 1981 3) It should not employ flooding or otherwise create 4) It must ensure that each route is loop-free at all times. 5) It