rfc1058.txt

RFC 的详细文档！

   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