`Request for Comments: 2453 Bay Networks
`Obsoletes: 1723, 1388 November 1998
`STD: 56
`Category: Standards Track
`
` RIP Version 2
`
`Status of this Memo
`
` This document specifies an Internet standards track protocol for the
` Internet community, and requests discussion and suggestions for
` improvements. Please refer to the current edition of the "Internet
` Official Protocol Standards" (STD 1) for the standardization state
` and status of this protocol. Distribution of this memo is unlimited.
`
`Copyright Notice
`
` Copyright (C) The Internet Society (1998). All Rights Reserved.
`
`Abstract
`
` This document specifies an extension of the Routing Information
` Protocol (RIP), as defined in [1], to expand the amount of useful
` information carried in RIP messages and to add a measure of security.
`
` A companion document will define the SNMP MIB objects for RIP-2 [2].
` An additional document will define cryptographic security
` improvements for RIP-2 [3].
`
`Acknowledgements
`
` I would like to thank the IETF RIP Working Group for their help in
` improving the RIP-2 protocol. Much of the text for the background
` discussions about distance vector protocols and some of the
` descriptions of the operation of RIP were taken from "Routing
` Information Protocol" by C. Hedrick [1]. Some of the final editing on
` the document was done by Scott Bradner.
`
`Malkin Standards Track [Page 1]
`
`Petitioner Apple Inc. - Exhibit 1063, p. 1
`
`
`
`RFC 2453 RIP Version 2 November 1998
`
`Table of Contents
`
` 1. Justification . . . . . . . . . . . . . . . . . . . . . . . . 3
` 2. Current RIP . . . . . . . . . . . . . . . . . . . . . . . . . 3
` 3. Basic Protocol . . . . . . . . . . . . . . . . . . . . . . . . 3
` 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . 3
` 3.2 Limitations of the Protocol . . . . . . . . . . . . . . . . 5
` 3.3. Organization of this document . . . . . . . . . . . . . . . 6
` 3.4 Distance Vector Algorithms . . . . . . . . . . . . . . . . . 6
` 3.4.1 Dealing with changes in topology . . . . . . . . . . . . 12
` 3.4.2 Preventing instability . . . . . . . . . . . . . . . . . 13
` 3.4.3 Split horizon . . . . . . . . . . . . . . . . . . . . . . 15
` 3.4.4 Triggered updates . . . . . . . . . . . . . . . . . . . . 17
` 3.5 Protocol Specification . . . . . . . . . . . . . . . . . . 18
` 3.6 Message Format . . . . . . . . . . . . . . . . . . . . . . . 20
` 3.7 Addressing Considerations . . . . . . . . . . . . . . . . . 22
` 3.8 Timers . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
` 3.9 Input Processing . . . . . . . . . . . . . . . . . . . . . . 25
` 3.9.1 Request Messages . . . . . . . . . . . . . . . . . . . . 25
` 3.9.2 Response Messages . . . . . . . . . . . . . . . . . . . . 26
` 3.10 Output Processing . . . . . . . . . . . . . . . . . . . . . 28
` 3.10.1 Triggered Updates . . . . . . . . . . . . . . . . . . . . 29
` 3.10.2 Generating Response Messages. . . . . . . . . . . . . . . 30
` 4. Protocol Extensions . . . . . . . . . . . . . . . . . . . . . 31
` 4.1 Authentication . . . . . . . . . . . . . . . . . . . . . . . 31
` 4.2 Route Tag . . . . . . . . . . . . . . . . . . . . . . . . . 32
` 4.3 Subnet Mask . . . . . . . . . . . . . . . . . . . . . . . . 32
` 4.4 Next Hop . . . . . . . . . . . . . . . . . . . . . . . . . . 33
` 4.5 Multicasting . . . . . . . . . . . . . . . . . . . . . . . . 33
` 4.6 Queries . . . . . . . . . . . . . . . . . . . . . . . . . . 33
` 5. Compatibility . . . . . . . . . . . . . . . . . . . . . . . . 34
` 5.1 Compatibility Switch . . . . . . . . . . . . . . . . . . . . 34
` 5.2 Authentication . . . . . . . . . . . . . . . . . . . . . . . 34
` 5.3 Larger Infinity . . . . . . . . . . . . . . . . . . . . . . 35
` 5.4 Addressless Links . . . . . . . . . . . . . . . . . . . . . 35
` 6. Interaction between version 1 and version 2 . . . . . . . . . 35
` 7. Security Considerations . . . . . . . . . . . . . . . . . . . 36
` Appendices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
` References . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
` Author’s Address . . . . . . . . . . . . . . . . . . . . . . . . . 38
` Full Copyright Statement . . . . . . . . . . . . . . . . . . . . . 39
`
`Malkin Standards Track [Page 2]
`
`Petitioner Apple Inc. - Exhibit 1063, p. 2
`
`
`
`RFC 2453 RIP Version 2 November 1998
`
`1. Justification
`
` With the advent of OSPF and IS-IS, there are those who believe that
` RIP is obsolete. While it is true that the newer IGP routing
` protocols are far superior to RIP, RIP does have some advantages.
` Primarily, in a small network, RIP has very little overhead in terms
` of bandwidth used and configuration and management time. RIP is also
` very easy to implement, especially in relation to the newer IGPs.
`
` Additionally, there are many, many more RIP implementations in the
` field than OSPF and IS-IS combined. It is likely to remain that way
` for some years yet.
`
` Given that RIP will be useful in many environments for some period of
` time, it is reasonable to increase RIP’s usefulness. This is
` especially true since the gain is far greater than the expense of the
` change.
`
`2. Current RIP
`
` The current RIP-1 message contains the minimal amount of information
` necessary for routers to route messages through a network. It also
` contains a large amount of unused space, owing to its origins.
`
` The current RIP-1 protocol does not consider autonomous systems and
` IGP/EGP interactions, subnetting [11], and authentication since
` implementations of these postdate RIP-1. The lack of subnet masks is
` a particularly serious problem for routers since they need a subnet
` mask to know how to determine a route. If a RIP-1 route is a network
` route (all non-network bits 0), the subnet mask equals the network
` mask. However, if some of the non-network bits are set, the router
` cannot determine the subnet mask. Worse still, the router cannot
` determine if the RIP-1 route is a subnet route or a host route.
` Currently, some routers simply choose the subnet mask of the
` interface over which the route was learned and determine the route
` type from that.
`
`3. Basic Protocol
`
`3.1 Introduction
`
` RIP is a routing protocol based on the Bellman-Ford (or distance
` vector) algorithm. This algorithm has been used for routing
` computations in computer networks since the early days of the
` ARPANET. The particular packet formats and protocol described here
` are based on the program "routed," which is included with the
` Berkeley distribution of Unix.
`
`Malkin Standards Track [Page 3]
`
`Petitioner Apple Inc. - Exhibit 1063, p. 3
`
`
`
`RFC 2453 RIP Version 2 November 1998
`
` In an international network, such as the Internet, it is very
` unlikely that a single routing protocol will used for the entire
` network. Rather, the network will be organized as a collection of
` Autonomous Systems (AS), each of which will, in general, be
` administered by a single entity. Each AS will have its own routing
` technology, which may differ among AS’s. The routing protocol used
` within an AS is referred to as an Interior Gateway Protocol (IGP). A
` separate protocol, called an Exterior Gateway Protocol (EGP), is used
` to transfer routing information among the AS’s. RIP was designed to
` work as an IGP in moderate-size AS’s. It is not intended for use in
` more complex environments. For information on the context into which
` RIP-1 is expected to fit, see Braden and Postel [6].
`
` RIP uses one of a class of routing algorithms known as Distance
` Vector algorithms. The earliest description of this class of
` algorithms known to the author is in Ford and Fulkerson [8]. Because
` of this, they are sometimes known as Ford-Fulkerson algorithms. The
` term Bellman-Ford is also used, and derives from the fact that the
` formulation is based on Bellman’s equation [4]. The presentation in
` this document is closely based on [5]. This document contains a
` protocol specification. For an introduction to the mathematics of
` routing algorithms, see [1]. The basic algorithms used by this
` protocol were used in computer routing as early as 1969 in the
` ARPANET. However, the specific ancestry of this protocol is within
` the Xerox network protocols. The PUP protocols [7] used the Gateway
` Information Protocol to exchange routing information. A somewhat
` updated version of this protocol was adopted for the Xerox Network
` Systems (XNS) architecture, with the name Routing Information
` Protocol [9]. Berkeley’s routed is largely the same as the Routing
` Information Protocol, with XNS addresses replaced by a more general
` address format capable of handling IPv4 and other types of address,
` and with routing updates limited to one every 30 seconds. Because of
` this similarity, the term Routing Information Protocol (or just RIP)
` is used to refer to both the XNS protocol and the protocol used by
` routed.
`
` RIP is intended for use within the IP-based Internet. The Internet
` is organized into a number of networks connected by special purpose
` gateways known as routers. The networks may be either point-to-point
` links or more complex networks such as Ethernet or token ring. Hosts
` and routers are presented with IP datagrams addressed to some host.
` Routing is the method by which the host or router decides where to
` send the datagram. It may be able to send the datagram directly to
` the destination, if that destination is on one of the networks that
` are directly connected to the host or router. However, the
` interesting case is when the destination is not directly reachable.
`
`Malkin Standards Track [Page 4]
`
`Petitioner Apple Inc. - Exhibit 1063, p. 4
`
`
`
`RFC 2453 RIP Version 2 November 1998
`
` In this case, the host or router attempts to send the datagram to a
` router that is nearer the destination. The goal of a routing
` protocol is very simple: It is to supply the information that is
` needed to do routing.
`
`3.2 Limitations of the Protocol
`
` This protocol does not solve every possible routing problem. As
` mentioned above, it is primary intended for use as an IGP in networks
` of moderate size. In addition, the following specific limitations
` are be mentioned:
`
` - The protocol is limited to networks whose longest path (the
` network’s diameter) is 15 hops. The designers believe that the
` basic protocol design is inappropriate for larger networks. Note
` that this statement of the limit assumes that a cost of 1 is used
` for each network. This is the way RIP is normally configured. If
` the system administrator chooses to use larger costs, the upper
` bound of 15 can easily become a problem.
`
` - The protocol depends upon "counting to infinity" to resolve certain
` unusual situations. (This will be explained in the next section.)
` If the system of networks has several hundred networks, and a
` routing loop was formed involving all of them, the resolution of
` the loop would require either much time (if the frequency of
` routing updates were limited) or bandwidth (if updates were sent
` whenever changes were detected). Such a loop would consume a large
` amount of network bandwidth before the loop was corrected. We
` believe that in realistic cases, this will not be a problem except
` on slow lines. Even then, the problem will be fairly unusual,
` since various precautions are taken that should prevent these
` problems in most cases.
`
` - This protocol uses fixed "metrics" to compare alternative routes.
` It is not appropriate for situations where routes need to be chosen
` based on real-time parameters such a measured delay, reliability,
` or load. The obvious extensions to allow metrics of this type are
` likely to introduce instabilities of a sort that the protocol is
` not designed to handle.
`
`Malkin Standards Track [Page 5]
`
`Petitioner Apple Inc. - Exhibit 1063, p. 5
`
`
`
`RFC 2453 RIP Version 2 November 1998
`
`3.3. Organization of this document
`
` The main body of this document is organized into two parts, which
` occupy the next two sections:
`
` A conceptual development and justification of distance vector
` algorithms in general.
`
` The actual protocol description.
`
` Each of these two sections can largely stand on its own. Section 3.4
` attempts to give an informal presentation of the mathematical
` underpinnings of the algorithm. Note that the presentation follows a
` "spiral" method. An initial, fairly simple algorithm is described.
` Then refinements are added to it in successive sections. Section 3.5
` is the actual protocol description. Except where specific references
` are made to section 3.4, it should be possible to implement RIP
` entirely from the specifications given in section 3.5.
`
`3.4 Distance Vector Algorithms
`
` Routing is the task of finding a path from a sender to a desired
` destination. In the IP "Internet model" this reduces primarily to a
` matter of finding a series of routers between the source and
` destination networks. As long as a message or datagram remains on a
` single network or subnet, any forwarding problems are the
` responsibility of technology that is specific to the network. For
` example, Ethernet and the ARPANET each define a way in which any
` sender can talk to any specified destination within that one network.
` IP routing comes in primarily when messages must go from a sender on
` one network to a destination on a different one. In that case, the
` message must pass through one or more routers connecting the
` networks. If the networks are not adjacent, the message may pass
` through several intervening networks, and the routers connecting
` them. Once the message gets to a router that is on the same network
` as the destination, that network’s own technology is used to get to
` the destination.
`
` Throughout this section, the term "network" is used generically to
` cover a single broadcast network (e.g., an Ethernet), a point to
` point line, or the ARPANET. The critical point is that a network is
` treated as a single entity by IP. Either no forwarding decision is
` necessary (as with a point to point line), or that forwarding is done
` in a manner that is transparent to IP, allowing IP to treat the
` entire network as a single fully-connected system (as with an
` Ethernet or the ARPANET). Note that the term "network" is used in a
` somewhat different way in discussions of IP addressing. We are using
` the term "network" here to refer to subnets in cases where subnet
`
`Malkin Standards Track [Page 6]
`
`Petitioner Apple Inc. - Exhibit 1063, p. 6
`
`
`
`RFC 2453 RIP Version 2 November 1998
`
` addressing is in use.
`
` A number of different approaches for finding routes between networks
` are possible. One useful way of categorizing these approaches is on
` the basis of the type of information the routers need to exchange in
` order to be able to find routes. Distance vector algorithms are
` based on the exchange of only a small amount of information. Each
` entity (router or host) that participates in the routing protocol is
` assumed to keep information about all of the destinations within the
` system. Generally, information about all entities connected to one
` network is summarized by a single entry, which describes the route to
` all destinations on that network. This summarization is possible
` because as far as IP is concerned, routing within a network is
` invisible. Each entry in this routing database includes the next
` router to which datagrams destined for the entity should be sent. In
` addition, it includes a "metric" measuring the total distance to the
` entity. Distance is a somewhat generalized concept, which may cover
` the time delay in getting messages to the entity, the dollar cost of
` sending messages to it, etc. Distance vector algorithms get their
` name from the fact that it is possible to compute optimal routes when
` the only information exchanged is the list of these distances.
` Furthermore, information is only exchanged among entities that are
` adjacent, that is, entities that share a common network.
`
` Although routing is most commonly based on information about
` networks, it is sometimes necessary to keep track of the routes to
` individual hosts. The RIP protocol makes no formal distinction
` between networks and hosts. It simply describes exchange of
` information about destinations, which may be either networks or
` hosts. (Note however, that it is possible for an implementor to
` choose not to support host routes. See section 3.2.) In fact, the
` mathematical developments are most conveniently thought of in terms
` of routes from one host or router to another. When discussing the
` algorithm in abstract terms, it is best to think of a routing entry
` for a network as an abbreviation for routing entries for all of the
` entities connected to that network. This sort of abbreviation makes
` sense only because we think of networks as having no internal
` structure that is visible at the IP level. Thus, we will generally
` assign the same distance to every entity in a given network.
`
` We said above that each entity keeps a routing database with one
` entry for every possible destination in the system. An actual
` implementation is likely to need to keep the following information
` about each destination:
`
`Malkin Standards Track [Page 7]
`
`Petitioner Apple Inc. - Exhibit 1063, p. 7
`
`
`
`RFC 2453 RIP Version 2 November 1998
`
` - address: in IP implementations of these algorithms, this will be
` the IP address of the host or network.
`
` - router: the first router along the route to the destination.
`
` - interface: the physical network which must be used to reach the
` first router.
`
` - metric: a number, indicating the distance to the destination.
`
` - timer: the amount of time since the entry was last updated.
`
` In addition, various flags and other internal information will
` probably be included. This database is initialized with a
` description of the entities that are directly connected to the
` system. It is updated according to information received in messages
` from neighboring routers.
`
` The most important information exchanged by the hosts and routers is
` carried in update messages. Each entity that participates in the
` routing scheme sends update messages that describe the routing
` database as it currently exists in that entity. It is possible to
` maintain optimal routes for the entire system by using only
` information obtained from neighboring entities. The algorithm used
` for that will be described in the next section.
`
` As we mentioned above, the purpose of routing is to find a way to get
` datagrams to their ultimate destinations. Distance vector algorithms
` are based on a table in each router listing the best route to every
` destination in the system. Of course, in order to define which route
` is best, we have to have some way of measuring goodness. This is
` referred to as the "metric".
`
` In simple networks, it is common to use a metric that simply counts
` how many routers a message must go through. In more complex
` networks, a metric is chosen to represent the total amount of delay
` that the message suffers, the cost of sending it, or some other
` quantity which may be minimized. The main requirement is that it
` must be possible to represent the metric as a sum of "costs" for
` individual hops.
`
` Formally, if it is possible to get from entity i to entity j directly
` (i.e., without passing through another router between), then a cost,
` d(i,j), is associated with the hop between i and j. In the normal
` case where all entities on a given network are considered to be the
` same, d(i,j) is the same for all destinations on a given network, and
` represents the cost of using that network. To get the metric of a
` complete route, one just adds up the costs of the individual hops
`
`Malkin Standards Track [Page 8]
`
`Petitioner Apple Inc. - Exhibit 1063, p. 8
`
`
`
`RFC 2453 RIP Version 2 November 1998
`
` that make up the route. For the purposes of this memo, we assume
` that the costs are positive integers.
`
` Let D(i,j) represent the metric of the best route from entity i to
` entity j. It should be defined for every pair of entities. d(i,j)
` represents the costs of the individual steps. Formally, let d(i,j)
` represent the cost of going directly from entity i to entity j. It
` is infinite if i and j are not immediate neighbors. (Note that d(i,i)
` is infinite. That is, we don’t consider there to be a direct
` connection from a node to itself.) Since costs are additive, it is
` easy to show that the best metric must be described by
`
` D(i,i) = 0, all i
` D(i,j) = min [d(i,k) + D(k,j)], otherwise
` k
` and that the best routes start by going from i to those neighbors k
` for which d(i,k) + D(k,j) has the minimum value. (These things can
` be shown by induction on the number of steps in the routes.) Note
` that we can limit the second equation to k’s that are immediate
` neighbors of i. For the others, d(i,k) is infinite, so the term
` involving them can never be the minimum.
`
` It turns out that one can compute the metric by a simple algorithm
` based on this. Entity i gets its neighbors k to send it their
` estimates of their distances to the destination j. When i gets the
` estimates from k, it adds d(i,k) to each of the numbers. This is
` simply the cost of traversing the network between i and k. Now and
` then i compares the values from all of its neighbors and picks the
` smallest.
`
` A proof is given in [2] that this algorithm will converge to the
` correct estimates of D(i,j) in finite time in the absence of topology
` changes. The authors make very few assumptions about the order in
` which the entities send each other their information, or when the min
` is recomputed. Basically, entities just can’t stop sending updates
` or recomputing metrics, and the networks can’t delay messages
` forever. (Crash of a routing entity is a topology change.) Also,
` their proof does not make any assumptions about the initial estimates
` of D(i,j), except that they must be non-negative. The fact that
` these fairly weak assumptions are good enough is important. Because
` we don’t have to make assumptions about when updates are sent, it is
` safe to run the algorithm asynchronously. That is, each entity can
` send updates according to its own clock. Updates can be dropped by
` the network, as long as they don’t all get dropped. Because we don’t
` have to make assumptions about the starting condition, the algorithm
` can handle changes. When the system changes, the routing algorithm
` starts moving to a new equilibrium, using the old one as its starting
` point. It is important that the algorithm will converge in finite
`
`Malkin Standards Track [Page 9]
`
`Petitioner Apple Inc. - Exhibit 1063, p. 9
`
`
`
`RFC 2453 RIP Version 2 November 1998
`
` time no matter what the starting point. Otherwise certain kinds of
` changes might lead to non-convergent behavior.
`
` The statement of the algorithm given above (and the proof) assumes
` that each entity keeps copies of the estimates that come from each of
` its neighbors, and now and then does a min over all of the neighbors.
` In fact real implementations don’t necessarily do that. They simply
` remember the best metric seen so far, and the identity of the
` neighbor that sent it. They replace this information whenever they
` see a better (smaller) metric. This allows them to compute the
` minimum incrementally, without having to store data from all of the
` neighbors.
`
` There is one other difference between the algorithm as described in
` texts and those used in real protocols such as RIP: the description
` above would have each entity include an entry for itself, showing a
` distance of zero. In fact this is not generally done. Recall that
` all entities on a network are normally summarized by a single entry
` for the network. Consider the situation of a host or router G that
` is connected to network A. C represents the cost of using network A
` (usually a metric of one). (Recall that we are assuming that the
` internal structure of a network is not visible to IP, and thus the
` cost of going between any two entities on it is the same.) In
` principle, G should get a message from every other entity H on
` network A, showing a cost of 0 to get from that entity to itself. G
` would then compute C + 0 as the distance to H. Rather than having G
` look at all of these identical messages, it simply starts out by
` making an entry for network A in its table, and assigning it a metric
` of C. This entry for network A should be thought of as summarizing
` the entries for all other entities on network A. The only entity on
` A that can’t be summarized by that common entry is G itself, since
` the cost of going from G to G is 0, not C. But since we never need
` those 0 entries, we can safely get along with just the single entry
` for network A. Note one other implication of this strategy: because
` we don’t need to use the 0 entries for anything, hosts that do not
` function as routers don’t need to send any update messages. Clearly
` hosts that don’t function as routers (i.e., hosts that are connected
` to only one network) can have no useful information to contribute
` other than their own entry D(i,i) = 0. As they have only the one
` interface, it is easy to see that a route to any other network
` through them will simply go in that interface and then come right
` back out it. Thus the cost of such a route will be greater than the
` best cost by at least C. Since we don’t need the 0 entries, non-
` routers need not participate in the routing protocol at all.
`
` Let us summarize what a host or router G does. For each destination
` in the system, G will keep a current estimate of the metric for that
` destination (i.e., the total cost of getting to it) and the identity
`
`Malkin Standards Track [Page 10]
`
`Petitioner Apple Inc. - Exhibit 1063, p. 10
`
`
`
`RFC 2453 RIP Version 2 November 1998
`
` of the neighboring router on whose data that metric is based. If the
` destination is on a network that is directly connected to G, then G
` simply uses an entry that shows the cost of using the network, and
` the fact that no router is needed to get to the destination. It is
` easy to show that once the computation has converged to the correct
` metrics, the neighbor that is recorded by this technique is in fact
` the first router on the path to the destination. (If there are
` several equally good paths, it is the first router on one of them.)
` This combination of destination, metric, and router is typically
` referred to as a route to the destination with that metric, using
` that router.
`
` 4.ne The method so far only has a way to lower the metric, as the
` existing metric is kept until a smaller one shows up. It is possible
` that the initial estimate might be too low. Thus, there must be a
` way to increase the metric. It turns out to be sufficient to use the
` following rule: suppose the current route to a destination has metric
` D and uses router G. If a new set of information arrived from some
` source other than G, only update the route if the new metric is
` better than D. But if a new set of information arrives from G
` itself, always update D to the new value. It is easy to show that
` with this rule, the incremental update process produces the same
` routes as a calculation that remembers the latest information from
` all the neighbors and does an explicit minimum. (Note that the
` discussion so far assumes that the network configuration is static.
` It does not allow for the possibility that a system might fail.)
`
` To summarize, here is the basic distance vector algorithm as it has
` been developed so far. (Note that this is not a statement of the RIP
` protocol. There are several refinements still to be added.) The
` following procedure is carried out by every entity that participates
` in the routing protocol. This must include all of the routers in the
` system. Hosts that are not routers may participate as well.
`
` - Keep a table with an entry for every possible destination in the
` system. The entry contains the distance D to the destination, and
` the first router G on the route to that network. Conceptually,
` there should be an entry for the entity itself, with metric 0, but
` this is not actually included.
`
` - Periodically, send a routing update to every neighbor. The update
` is a set of messages that contain all of the information from the
` routing table. It contains an entry for each destination, with the
` distance shown to that destination.
`
` - When a routing update arrives from a neighbor G’, add the cost
` associated with the network that is shared with G’. (This should
` be the network over which the update arrived.) Call the resulting
`
`Malkin Standards Track [Page 11]
`
`Petitioner Apple Inc. - Exhibit 1063, p. 11
`
`
`
`RFC 2453 RIP Version 2 November 1998
`
` distance D’. Compare the resulting distances with the current
` routing table entries. If the new distance D’ for N is smaller
` than the existing value D, adopt the new route. That is, change
` the table entry for N to have metric D’ and router G’. If G’ is
` the router from which the existing route came, i.e., G’ = G, then
` use the new metric even if it is larger than the old one.
`
`3.4.1 Dealing with changes in topology
`
` The discussion above assumes that the topology of the network is
` fixed. In practice, routers and lines often fail and come back up.
` To handle this possibility, we need to modify the algorithm slightly.
`
` The theoretical version of the algorithm involved a minimum over all
` immediate neighbors. If the topology changes, the set of neighbors
` changes. Therefore, the next time the calculation is done, the
` change will be reflected. However, as mentioned above, actual
` implementations use an incremental version of the minimization. Only
` the best route to any given destination is remembered. If the router
` involved in that route should crash, or the network connection to it
` break, the calculation might never reflect the change. The algorithm
` as shown so far depends upon a router notifying its neighbors if its
` metrics change. If the router crashes, then it has no way of
` notifying neighbors of a change.
`
` In order to handle problems of this kind, distance vector protocols
` must make some provision for timing out routes. The details depend
` upon the specific protocol. As an example, in RIP every router that
` participates in routing sends an update message to all its neighbors
` once every 30 seconds. Suppose the current route for network N uses
` router G. If we don’t hear from G for 180 seconds, we can assume
` that either the router has crashed or the network connecting us to it
` has become unusable. Thus, we mark the route as invalid. When we
` hear from another neighbor that has a valid route to N, the valid
`