rfc2453.txt

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

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