rfc2453.txt

<VC++网络游戏建摸与实现>源代码

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



Malkin                      Standards Track                    [Page 12]

RFC 2453                     RIP Version 2                 November 1998


   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.

3.4.2 Preventing instability

   The algorithm as presented up to this point will always allow a host
   or router 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
   routers time out and set the metric for that network to 16.  For
   purposes of analysis, we can assume that all the neighboring routers
   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 routers in the
   system will converge to new routes that go through one of those
   routers.  It is easy to see that once convergence has happened, all
   the routers will have metrics of at least 16 for the vanished
   network.  Routers one hop away from the original neighbors would end
   up with metrics of at least 17; routers 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
   routers.

   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 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.  In the following example the letters correspond to
   routers, and the lines to networks.








Malkin                      Standards Track                    [Page 13]

RFC 2453                     RIP Version 2                 November 1998


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

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

   However, for purposes of this illustration, we show only the routes
   from each router 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 routers send updates at the same time.
   The chart shows the metric for the target network, as it appears in
   the routing table at each router.

       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



Malkin                      Standards Track                    [Page 14]

RFC 2453                     RIP Version 2                 November 1998


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