rfc1058.txt

xorp源码hg

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