A LOOP-FREE EXTENDED BELLMAN-FORD ROUTING PROTOCOL WITHOUT BOUNCING EFFECT Chunhsiang Cheng, Ralph Riley, and Srikanta P.R. &mar* Department of Electrical Engineering and Computer Science Northwestern University Evanston, IL 60208 Tel: (312) 491-7382 JJ. Gar&+Luna-Aceves” * Network Infomuxion Systems Center SRI International 333 Ravenswood Avenue Menlo Park, CA 94025 ABSTRACT: 1. INTRODUCTION Distributed algorithms for shortest-path problems are important in the context of routing in computer communication networks. We present a protocol that maintains the shortest-path routes in a dynamic topology, that is, in an environment where links and nodes can fail and mover at arbitrary times. The novelty of this protocol is that it avoids the bouncing effect and the looping problem that occur in the previous approaches of the distributed implementation of Bellman-Ford algorithm. The bouncing effect refers to the very long duration for convergence when failures happen or weights increase, and the nonterminating exchanges of messages, or counting-to-infinity behavior, in disconnected components of the network resulting from failures. The looping problems cause data packets to circulate and, thus, waste bandwidth.These undesirable effects are avoided without any increase in the overall message complexity of previous approaches required in the connected part of the network The time complexity is better than the distributed Bellman-Ford algorithm encountering failures. The key idea in the implementation is to maintain only loop-free paths, and search for the shortest path only from this set. One of the widely used techniques for routing in communication networks is via distributed algorithms for finding shortest paths in weighted graphs [9,10,13,14]. The well known distributed Bellman-Ford (BF) algorithm (implemented initially in ARPANET [ 141) is simple, and the distance and the routing-tables are easy to maintain [2]. However, this protocol has several major drawbacks. Firstly, the response of this protocol to link oi node failures can be very slow. This is due to the possibility that the distances maintained, and exchanged with neighbors, in the internal distance-table or routing-table of each node, may correspond to paths with loops (“bouncing effect” [20]). Thus, nodes may engage in a prolonged exchange of such distances before converging to the shortest paths. Moreover, if the network is diSCOnneCted, the protocol is not guaranteed to terminate. (This is the so called counting-to-infinity problem, where each node keeps indefinitely increasing its distances to the unreachable destinations.) Another shortcoming of this protocol is that it is not loop-free in the following sense [3,4,9,13,17]: at any moment, the paths implied by the routing-tables of all nodes taken together can have loops (i.e., if a path to a destination is traced going from the routing-table of one node to that of another node, a node may be visited more than once before the destination is reached. If such routing-table loops persist for a long time, looping of data to be routed may occur resulting in considerable overhead. Avoiding the bouncing effect does not necessarily imply that routing-table loops are eliminated. (The looping of data packets may not be completely avoided even if the routing-tables are loop-free at all time [2].) Here, we take a protocol to be loop-free, if it does not have routing-table loops mentioned above [9]. One way to overcome the termination (or counting-to- * This research was sponsored by grants from Bell Northern Research, U.S. West Advanced Technologies, and Ameritech. ** This work was sponsored by SRI International IR&D funds. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permksion. 0 1989 ACM 08979 l-332-9/89/0009/0224 $ I so 224infinity) problem is to use some additional information, such as the size or diameter of the network [20]. However, such information may vary from time to time, if the network topology is dynamic, and in such cases the convergence of the protocol via this approach will be too slow. The new ARPANET routing protocol [2,15] runs the Dijkstra’s algorithm periodically at each node based on the information of the whole network. Although the looping problem is alleviated to some extent, in a slowly varying network, the overhead, in terms of the messages and the local memory required, is too high as each node must gather the information about the whole topology. Merlin and Segall [16] proposed a synchronization approach to achieve loop freedom. In this approach, there is additional overhead due to the cost of the synchronization phase. In addition, the speed of the convergence can be slower than the BF algorithm, when no looping is encountered. In fact, achieving loop-freedom in the distributed BF algorithm is not difficult in networks with uniform weight on each link. Chu [5] proposed the downstream and upstream idea to avoid loops in minimum hop routing. A similar idea was adopted by Shin and Chen [19] for nonuniformly weighted networks to avoid two-node looping. This algorithm can also be extended to a kth order algorithm which avoids all loops with no more than k hops. However, in this case, the size of the control messages and the local memory required grow proportional to k. Jaffe and Moss [13] used the freezing technique to delay the response of a node at the moment the node loses its preferred neighbor to prevent the possibility of looping. Garcia-Luna-Aceves [9] extended the same idea to achieve a lower message complexity, and also presented a formal proof. For a further critique of the previous approaches, see Garcia-Luna-Aceves [9,10]. In this paper, we present a shortest path routing protocol, in which each node maintains information about some simple paths in its local memory. Note that knowing the entire path is subtantial for determining whether a path is simple or non-simple. However, it is
View Full Document
Unlocking...