EIGRP--A Fast Routing Protocol based on Distance Vectors - eScholarship (1994)

EIGRP{A FAST ROUTING PROTOCOL BASED ON DISTANCE VECTORS Bob Albrightson Cisco Systems Menlo Park, CA 94025 albright@cisco.com J.J. Garcia-Luna-Aceves University of California Santa Cruz, CA 95064 jj@cse.ucsc.edu Joanne Boyle Cisco Systems Menlo Park, CA 94025 boyle@cisco.com Abstract Early routing protocols were based on distance vectors; they were very simple and easy to implement but had the severe drawbacks of counting to innity and routing loops. These problems were reduced using such techniques as split horizon and hold-downs; however, for these techniques to work in practice, long convergence times are introduced. Routing protocols based on link states have been implemented to address the problem of slow convergence in distance-vector protocols, but they add complexity in conguration and troubleshooting. We present a new distance-vector protocol that converges as quickly as current link-state protocols, while maintaining loop freedom at every instant. The protocol is based on three main elements: a transport algorithm that supports the reliable exchange of messages among routers, the diusing update algorithm, which computes shortest paths distributedly, and modules that permit the operation of the new routing protocol in a multiprotocol environment. 1 INTRODUCTION Today's intradomain routing protocols can be classied as distance-vector or link-state protocols. In a distance-vector protocol, a router knows the length of the shortest path from each neighbor node to every network destination, and uses this information to compute the shortest path and next router in the path to each destination. A router sends update messages to its neighbors, who in turn process the messages and send messages of their own, if needed. Each update message contains a vector of one or more entries, each of which species, as a minimum, the distance to a given destination. In contrast, in a link-state protocol a router must receive information about the entire topology to compute the shortest path to each destination using a local shortest-path algorithm such as Dijkstra's algorithm [1]. Each router broadcasts update messages, containing the state of each of the router's adjacent links, to every other router in the network. The distance vector protocols used in the Internet thus far are based on variants of the distributed Bellman-Ford algorithm (DBF) for shortest-path computation [1]. The primary disadvantage of DBF is that incorrect entries in routing tables may form routing-table loops for one or more destinations whenever link costs increase [9]. Because a router chooses as its successor to a destination any neighbor router who appears to oer the shortest path to that destination, the router may choose paths that lead to loops for as long as those neighbor routers with viable paths to the destination oer path lengths longer than those paths leading to loops. The worst case of this problem is rather severe: when routers fail or the network partitions, a router can detect such events only after it has considered all possible path lengths to the one or more destinations that have become unreachable through any of its neighbors. Accordingly, this