rfc1058.txt

RFC 的详细文档！

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