rfc1058.txt

283个中文RFC文档

RFC1058 - Routing Information Protocol


Network Working Group C. Hedrick
Request for Comments: 1058 Rutgers University
June 1988

Routing Information Protocol

Status of this Memo

This RFCdescribes an existing protocol for exchanging routing
baidu
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

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

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

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.

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

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