🚀 go-pugleaf

Network Working Group                                         C. Hedrick
Request for Comments: 1058                            Rutgers University
                                                               June 1988


                      Routing Information Protocol


Status of this Memo

   This RFC describes an existing protocol for exchanging routing
   information among gateways and other hosts.  It is intended to be
   used as a basis for developing gateway software for use in the
   Internet community.  Distribution of this memo is unlimited.

                             Table of Contents

   1. Introduction                                                     2
        1.1. Limitations of the protocol                               4
        1.2. Organization of this document                             4
   2. Distance Vector Algorithms                                       5
        2.1. Dealing with changes in topology                         11
        2.2. Preventing instability                                   12
             2.2.1. Split horizon                                     14
             2.2.2. Triggered updates                                 15
   3. Specifications for the protocol                                 16
        3.1. Message formats                                          18
        3.2. Addressing considerations                                20
        3.3. Timers                                                   23
        3.4. Input processing                                         24
             3.4.1. Request                                           25
             3.4.2. Response                                          26
        3.5. Output Processing                                        28
        3.6. Compatibility                                            31
   4. Control functions                                               31

Overview

   This memo is intended to do the following things:

      - Document a protocol and algorithms that are currently in
        wide use for routing, but which have never been formally
        documented.

      - Specify some improvements in the algorithms which will
        improve stability of the routes in large networks.  These
        improvements do not introduce any incompatibility with
        existing implementations.  They are to be incorporated into



Hedrick                                                         [Page 1]

RFC 1058              Routing Information Protocol             June 1988


        all implementations of this protocol.

      - Suggest some optional features to allow greater
        configurability and control.  These features were developed
        specifically to solve problems that have shown up in actual
        use by the NSFnet community.  However, they should have more
        general utility.

   The Routing Information Protocol (RIP) described here is loosely
   based on the program "routed", distributed with the 4.3 Berkeley
   Software Distribution.  However, there are several other
   implementations of what is supposed to be the same protocol.
   Unfortunately, these various implementations disagree in various
   details.  The specifications here represent a combination of features
   taken from various implementations.  We believe that a program
   designed according to this document will interoperate with routed,
   and with all other implementations of RIP of which we are aware.

   Note that this description adopts a different view than most existing
   implementations about when metrics should be incremented.  By making
   a corresponding change in the metric used for a local network, we
   have retained compatibility with other existing implementations.  See
   section 3.6 for details on this issue.

1. Introduction

   This memo describes one protocol in a series of routing protocols
   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.  It has become a
   de facto standard for exchange of routing information among gateways
   and hosts.  It is implemented for this purpose by most commercial
   vendors of IP gateways.  Note, however, that many of these vendors
   have their own protocols which are used among their own gateways.

   This protocol is most useful as an "interior gateway protocol".  In a
   nationwide network such as the current Internet, it is very unlikely
   that a single routing protocol will used for the whole network.
   Rather, the network will be organized as a collection of "autonomous
   systems".  An autonomous system will in general be administered by a
   single entity, or at least will have some reasonable degree of
   technical and administrative control.  Each autonomous system will
   have its own routing technology.  This may well be different for
   different autonomous systems.  The routing protocol used within an
   autonomous system is referred to as an interior gateway protocol, or
   "IGP".  A separate protocol is used to interface among the autonomous



Hedrick                                                         [Page 2]

RFC 1058              Routing Information Protocol             June 1988


   systems.  The earliest such protocol, still used in the Internet, is
   "EGP" (exterior gateway protocol).  Such protocols are now usually
   referred to as inter-AS routing protocols.  RIP was designed to work
   with moderate-size networks using reasonably homogeneous technology.
   Thus it is suitable as an IGP for many campuses and for regional
   networks using serial lines whose speeds do not vary widely.  It is
   not intended for use in more complex environments.  For more
   information on the context into which RIP is expected to fit, see
   Braden and Postel [3].

   RIP is one of a class of algorithms known as "distance vector
   algorithms".  The earliest description of this class of algorithms
   known to the author is in Ford and Fulkerson [6].  Because of this,
   they are sometimes known as Ford-Fulkerson algorithms.  The term
   Bellman-Ford is also used.  It comes from the fact that the
   formulation is based on Bellman's equation, the basis of "dynamic
   programming".  (For a standard introduction to this area, see [1].)
   The presentation in this document is closely based on [2].  This text
   contains an introduction to the mathematics of routing algorithms.
   It describes and justifies several variants of the algorithm
   presented here, as well as a number of other related algorithms.  The
   basic algorithms described in 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 (see [4]) 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.  (See [7].)
   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 IP 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 gateways.  The
   networks may be either point-to-point links or more complex networks
   such as Ethernet or the ARPANET.  Hosts and gateways are presented
   with IP datagrams addressed to some host.  Routing is the method by
   which the host or gateway 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 gateway.  However, the interesting case is when the
   destination is not directly reachable.  In this case, the host or
   gateway attempts to send the datagram to a gateway that is nearer the
   destination.  The goal of a routing protocol is very simple: It is to



Hedrick                                                         [Page 3]

RFC 1058              Routing Information Protocol             June 1988


   supply the information that is needed to do routing.

1.1. 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
   reasonably homogeneous networks of moderate size.  In addition, the
   following specific limitations should be mentioned:

      - The protocol is limited to networks whose longest path
        involves 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.

1.2. Organization of this document

   The main body of this document is organized into two parts, which
   occupy the next two sections:

      2   A conceptual development and justification of distance vector
          algorithms in general.




Hedrick                                                         [Page 4]

RFC 1058              Routing Information Protocol             June 1988


      3   The actual protocol description.

   Each of these two sections can largely stand on its own.  Section 2
   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
   is the actual protocol description.  Except where specific references
   are made to section 2, it should be possible to implement RIP
   entirely from the specifications given in section 3.

2. Distance Vector Algorithms

   Routing is the task of finding a path from a sender to a desired
   destination.  In the IP "Catenet model" this reduces primarily to a
   matter of finding gateways between networks.  As long as a message
   remains on a single network or subnet, any routing problems are
   solved by technology that is specific to the network.  For example,
   the 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
   such network to a destination on a different one.  In that case, the
   message must pass through gateways connecting the networks.  If the
   networks are not adjacent, the message may pass through several
   intervening networks, and the gateways connecting them.  Once the
   message gets to a gateway 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 routing is necessary (as
   with a point to point line), or that routing 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.  A single IP network number may be
   assigned to a collection of networks, with "subnet" addressing being
   used to describe the individual networks.  In effect, we are using
   the term "network" here to refer to subnets in cases where subnet
   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 gateways 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



Hedrick                                                         [Page 5]

RFC 1058              Routing Information Protocol             June 1988


   entity (gateway 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
   gateway 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 gateway 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:

      - address: in IP implementations of these algorithms, this
        will be the IP address of the host or network.

      - gateway: the first gateway along the route to the
        destination.

      - interface: the physical network which must be used to reach
        the first gateway.

      - metric: a number, indicating the distance to the



Hedrick                                                         [Page 6]

RFC 1058              Routing Information Protocol             June 1988


        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 gateways.

   The most important information exchanged by the hosts and gateways is
   that 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 giving 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 gateways 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 gateway 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
   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)



Hedrick                                                         [Page 7]

RFC 1058              Routing Information Protocol             June 1988


   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
   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



Hedrick                                                         [Page 8]

RFC 1058              Routing Information Protocol             June 1988


   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 gateway 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 gateways don't need to send any update messages.  Clearly
   hosts that don't function as gateways (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-
   gateways need not participate in the routing protocol at all.

   Let us summarize what a host or gateway 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
   of the neighboring gateway 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 gateway 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 gateway on the path to the destination.  (If there are



Hedrick                                                         [Page 9]

RFC 1058              Routing Information Protocol             June 1988


   several equally good paths, it is the first gateway on one of them.)
   This combination of destination, metric, and gateway is typically
   referred to as a route to the destination with that metric, using
   that gateway.

   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 gateway 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 gateways in
   the system.  Hosts that are not gateways 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 gateway 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 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 gateway G'.  If G' is the gateway



Hedrick                                                        [Page 10]

RFC 1058              Routing Information Protocol             June 1988


        from which the existing route came, i.e., G' = G, then use
        the new metric even if it is larger than the old one.

2.1. Dealing with changes in topology

   The discussion above assumes that the topology of the network is
   fixed.  In practice, gateways 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
   gateway 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 gateway
   notifying its neighbors if its metrics change.  If the gateway
   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 gateway that
   participates in routing sends an update message to all its neighbors
   once every 30 seconds.  Suppose the current route for network N uses
   gateway G.  If we don't hear from G for 180 seconds, we can assume
   that either the gateway 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
   route will replace the invalid one.  Note that we wait for 180
   seconds before timing out a route even though we expect to hear from
   each neighbor every 30 seconds.  Unfortunately, messages are
   occasionally lost by networks.  Thus, it is probably not a good idea
   to invalidate a route based on a single missed message.

   As we will see below, it is useful to have a way to notify neighbors
   that there currently isn't a valid route to some network.  RIP, along
   with several other protocols of this class, does this through a
   normal update message, by marking that network as unreachable.  A
   specific metric value is chosen to indicate an unreachable
   destination; that metric value is larger than the largest valid
   metric that we expect to see.  In the existing implementation of RIP,
   16 is used.  This value is normally referred to as "infinity", since
   it is larger than the largest valid metric.  16 may look like a
   surprisingly small number.  It is chosen to be this small for reasons
   that we will see shortly.  In most implementations, the same
   convention is used internally to flag a route as invalid.




Hedrick                                                        [Page 11]

RFC 1058              Routing Information Protocol             June 1988


2.2. Preventing instability

   The algorithm as presented up to this point will always allow a host
   or gateway to calculate a correct routing table.  However, that is
   still not quite enough to make it useful in practice.  The proofs
   referred to above only show that the routing tables will converge to
   the correct values in finite time.  They do not guarantee that this
   time will be small enough to be useful, nor do they say what will
   happen to the metrics for networks that become inaccessible.

   It is easy enough to extend the mathematics to handle routes becoming
   inaccessible.  The convention suggested above will do that.  We
   choose a large metric value to represent "infinity".  This value must
   be large enough that no real metric would ever get that large.  For
   the purposes of this example, we will use the value 16.  Suppose a
   network becomes inaccessible.  All of the immediately neighboring
   gateways time out and set the metric for that network to 16.  For
   purposes of analysis, we can assume that all the neighboring gateways
   have gotten a new piece of hardware that connects them directly to
   the vanished network, with a cost of 16.  Since that is the only
   connection to the vanished network, all the other gateways in the
   system will converge to new routes that go through one of those
   gateways.  It is easy to see that once convergence has happened, all
   the gateways will have metrics of at least 16 for the vanished
   network.  Gateways one hop away from the original neighbors would end
   up with metrics of at least 17; gateways two hops away would end up
   with at least 18, etc.  As these metrics are larger than the maximum
   metric value, they are all set to 16.  It is obvious that the system
   will now converge to a metric of 16 for the vanished network at all
   gateways.

   Unfortunately, the question of how long convergence will take is not
   amenable to quite so simple an answer.  Before going any further, it
   will be useful to look at an example (taken from [2]).  Note, by the
   way, that what we are about to show will not happen with a correct
   implementation of RIP.  We are trying to show why certain features
   are needed.  Note that the letters correspond to gateways, and the
   lines to networks.

            A-----B
             \   / \
              \ /  |
               C  /    all networks have cost 1, except
               | /     for the direct link from C to D, which
               |/      has cost 10
               D
               |<=== target network




Hedrick                                                        [Page 12]

RFC 1058              Routing Information Protocol             June 1988


   Each gateway will have a table showing a route to each network.

   However, for purposes of this illustration, we show only the routes
   from each gateway to the network marked at the bottom of the diagram.

            D:  directly connected, metric 1
            B:  route via D, metric 2
            C:  route via B, metric 3
            A:  route via B, metric 3

   Now suppose that the link from B to D fails.  The routes should now
   adjust to use the link from C to D.  Unfortunately, it will take a
   while for this to this to happen.  The routing changes start when B
   notices that the route to D is no longer usable.  For simplicity, the
   chart below assumes that all gateways send updates at the same time.
   The chart shows the metric for the target network, as it appears in
   the routing table at each gateway.

        time ------>

        D: dir, 1   dir, 1   dir, 1   dir, 1  ...  dir, 1   dir, 1
        B: unreach  C,   4   C,   5   C,   6       C,  11   C,  12
        C: B,   3   A,   4   A,   5   A,   6       A,  11   D,  11
        A: B,   3   C,   4   C,   5   C,   6       C,  11   C,  12

        dir = directly connected
        unreach = unreachable

   Here's the problem:  B is able to get rid of its failed route using a
   timeout mechanism.  But vestiges of that route persist in the system
   for a long time.  Initially, A and C still think they can get to D
   via B.  So, they keep sending updates listing metrics of 3.  In the
   next iteration, B will then claim that it can get to D via either A
   or C.  Of course, it can't.  The routes being claimed by A and C are
   now gone, but they have no way of knowing that yet.  And even when
   they discover that their routes via B have gone away, they each think
   there is a route available via the other.  Eventually the system
   converges, as all the mathematics claims it must.  But it can take
   some time to do so.  The worst case is when a network becomes
   completely inaccessible from some part of the system.  In that case,
   the metrics may increase slowly in a pattern like the one above until
   they finally reach infinity.  For this reason, the problem is called
   "counting to infinity".

   You should now see why "infinity" is chosen to be as small as
   possible.  If a network becomes completely inaccessible, we want
   counting to infinity to be stopped as soon as possible.  Infinity
   must be large enough that no real route is that big.  But it



Hedrick                                                        [Page 13]

RFC 1058              Routing Information Protocol             June 1988


   shouldn't be any bigger than required.  Thus the choice of infinity
   is a tradeoff between network size and speed of convergence in case
   counting to infinity happens.  The designers of RIP believed that the
   protocol was unlikely to be practical for networks with a diameter
   larger than 15.

   There are several things that can be done to prevent problems like
   this.  The ones used by RIP are called "split horizon with poisoned
   reverse", and "triggered updates".

2.2.1. Split horizon

   Note that some of the problem above is caused by the fact that A and
   C are engaged in a pattern of mutual deception.  Each claims to be
   able to get to D via the other.  This can be prevented by being a bit
   more careful about where information is sent.  In particular, it is
   never useful to claim reachability for a destination network to the
   neighbor(s) from which the route was learned.  "Split horizon" is a
   scheme for avoiding problems caused by including routes in updates
   sent to the gateway from which they were learned.  The "simple split
   horizon" scheme omits routes learned from one neighbor in updates
   sent to that neighbor.  "Split horizon with poisoned reverse"
   includes such routes in updates, but sets their metrics to infinity.

   If A thinks it can get to D via C, its messages to C should indicate
   that D is unreachable.  If the route through C is real, then C either
   has a direct connection to D, or a connection through some other
   gateway.  C's route can't possibly go back to A, since that forms a
   loop.  By telling C that D is unreachable, A simply guards against
   the possibility that C might get confused and believe that there is a
   route through A.  This is obvious for a point to point line.  But
   consider the possibility that A and C are connected by a broadcast
   network such as an Ethernet, and there are other gateways on that
   network.  If A has a route through C, it should indicate that D is
   unreachable when talking to any other gateway on that network.  The
   other gateways on the network can get to C themselves.  They would
   never need to get to C via A.  If A's best route is really through C,
   no other gateway on that network needs to know that A can reach D.
   This is fortunate, because it means that the same update message that
   is used for C can be used for all other gateways on the same network.
   Thus, update messages can be sent by broadcast.

   In general, split horizon with poisoned reverse is safer than simple
   split horizon.  If two gateways have routes pointing at each other,
   advertising reverse routes with a metric of 16 will break the loop
   immediately.  If the reverse routes are simply not advertised, the
   erroneous routes will have to be eliminated by waiting for a timeout.
   However, poisoned reverse does have a disadvantage: it increases the



Hedrick                                                        [Page 14]

RFC 1058              Routing Information Protocol             June 1988


   size of the routing messages.  Consider the case of a campus backbone
   connecting a number of different buildings.  In each building, there
   is a gateway connecting the backbone to a local network.  Consider
   what routing updates those gateways should broadcast on the backbone
   network.  All that the rest of the network really needs to know about
   each gateway is what local networks it is connected to.  Using simple
   split horizon, only those routes would appear in update messages sent
   by the gateway to the backbone network.  If split horizon with
   poisoned reverse is used, the gateway must mention all routes that it
   learns from the backbone, with metrics of 16.  If the system is
   large, this can result in a large update message, almost all of whose
   entries indicate unreachable networks.

   In a static sense, advertising reverse routes with a metric of 16
   provides no additional information.  If there are many gateways on
   one broadcast network, these extra entries can use significant
   bandwidth.  The reason they are there is to improve dynamic behavior.
   When topology changes, mentioning routes that should not go through
   the gateway as well as those that should can speed up convergence.
   However, in some situations, network managers may prefer to accept
   somewhat slower convergence in order to minimize routing overhead.
   Thus implementors may at their option implement simple split horizon
   rather than split horizon with poisoned reverse, or they may provide
   a configuration option that allows the network manager to choose
   which behavior to use.  It is also permissible to implement hybrid
   schemes that advertise some reverse routes with a metric of 16 and
   omit others.  An example of such a scheme would be to use a metric of
   16 for reverse routes for a certain period of time after routing
   changes involving them, and thereafter omitting them from updates.

2.2.2. Triggered updates

   Split horizon with poisoned reverse will prevent any routing loops
   that involve only two gateways.  However, it is still possible to end
   up with patterns in which three gateways are engaged in mutual
   deception.  For example, A may believe it has a route through B, B
   through C, and C through A.  Split horizon cannot stop such a loop.
   This loop will only be resolved when the metric reaches infinity and
   the network involved is then declared unreachable.  Triggered updates
   are an attempt to speed up this convergence.  To get triggered
   updates, we simply add a rule that whenever a gateway changes the
   metric for a route, it is required to send update messages almost
   immediately, even if it is not yet time for one of the regular update
   message.  (The timing details will differ from protocol to protocol.
   Some distance vector protocols, including RIP, specify a small time
   delay, in order to avoid having triggered updates generate excessive
   network traffic.)  Note how this combines with the rules for
   computing new metrics.  Suppose a gateway's route to destination N



Hedrick                                                        [Page 15]

RFC 1058              Routing Information Protocol             June 1988


   goes through gateway G.  If an update arrives from G itself, the
   receiving gateway is required to believe the new information, whether
   the new metric is higher or lower than the old one.  If the result is
   a change in metric, then the receiving gateway will send triggered
   updates to all the hosts and gateways directly connected to it.  They
   in turn may each send updates to their neighbors.  The result is a
   cascade of triggered updates.  It is easy to show which gateways and
   hosts are involved in the cascade.  Suppose a gateway G times out a
   route to destination N.  G will send triggered updates to all of its
   neighbors.  However, the only neighbors who will believe the new
   information are those whose routes for N go through G.  The other
   gateways and hosts will see this as information about a new route
   that is worse than the one they are already using, and ignore it.
   The neighbors whose routes go through G will update their metrics and
   send triggered updates to all of their neighbors.  Again, only those
   neighbors whose routes go through them will pay attention.  Thus, the
   triggered updates will propagate backwards along all paths leading to
   gateway G, updating the metrics to infinity.  This propagation will
   stop as soon as it reaches a portion of the network whose route to
   destination N takes some other path.

   If the system could be made to sit still while the cascade of
   triggered updates happens, it would be possible to prove that
   counting to infinity will never happen.  Bad routes would always be
   removed immediately, and so no routing loops could form.

   Unfortunately, things are not so nice.  While the triggered updates
   are being sent, regular updates may be happening at the same time.
   Gateways that haven't received the triggered update yet will still be
   sending out information based on the route that no longer exists.  It
   is possible that after the triggered update has gone through a
   gateway, it might receive a normal update from one of these gateways
   that hasn't yet gotten the word.  This could reestablish an orphaned
   remnant of the faulty route.  If triggered updates happen quickly
   enough, this is very unlikely.  However, counting to infinity is
   still possible.

3. Specifications for the protocol

   RIP is intended to allow hosts and gateways to exchange information
   for computing routes through an IP-based network.  RIP is a distance
   vector protocol.  Thus, it has the general features described in
   section 2.  RIP may be implemented by both hosts and gateways.  As in
   most IP documentation, the term "host" will be used here to cover
   either.  RIP is used to convey information about routes to
   "destinations", which may be individual hosts, networks, or a special
   destination used to convey a default route.




Hedrick                                                        [Page 16]