As per Relevance of the word destination, we have this rfc below:
Network Working Group C.
Request for Comments: 1058 Rutgers
June 1988
Routing Information
Status of this
This RFC describes an existing protocol for exchanging
information among gateways and other hosts. It is intended to
used as a basis for developing gateway software for use in
Internet community. Distribution of this memo is unlimited
Table of
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
This memo is intended to do the following things
- Document a protocol and algorithms that are currently
wide use for routing, but which have never been
documented
- Specify some improvements in the algorithms which
improve stability of the routes in large networks.
improvements do not introduce any incompatibility
existing implementations. They are to be incorporated
Hedrick [Page 1]
RFC 1058 Routing Information Protocol June 1988
all implementations of this protocol
- Suggest some optional features to allow
configurability and control. These features were
specifically to solve problems that have shown up in
use by the NSFnet community. However, they should have
general utility
The Routing Information Protocol (RIP) described here is
based on the program "routed", distributed with the 4.3
Software Distribution. However, there are several
implementations of what is supposed to be the same protocol
Unfortunately, these various implementations disagree in
details. The specifications here represent a combination of
taken from various implementations. We believe that a
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
implementations about when metrics should be incremented. By
a corresponding change in the metric used for a local network,
have retained compatibility with other existing implementations.
section 3.6 for details on this issue
1.
This memo describes one protocol in a series of routing
based on the Bellman-Ford (or distance vector) algorithm.
algorithm has been used for routing computations in computer
since the early days of the ARPANET. The particular packet
and protocol described here are based on the program "routed",
is included with the Berkeley distribution of Unix. It has become
de facto standard for exchange of routing information among
and hosts. It is implemented for this purpose by most
vendors of IP gateways. Note, however, that many of these
have their own protocols which are used among their own gateways
This protocol is most useful as an "interior gateway protocol". In
nationwide network such as the current Internet, it is very
that a single routing protocol will used for the whole network
Rather, the network will be organized as a collection of "
systems". An autonomous system will in general be administered by
single entity, or at least will have some reasonable degree
technical and administrative control. Each autonomous system
have its own routing technology. This may well be different
different autonomous systems. The routing protocol used within
autonomous system is referred to as an interior gateway protocol,
"IGP". A separate protocol is used to interface among the
Hedrick [Page 2]
RFC 1058 Routing Information Protocol June 1988
systems. The earliest such protocol, still used in the Internet,
"EGP" (exterior gateway protocol). Such protocols are now
referred to as inter-AS routing protocols. RIP was designed to
with moderate-size networks using reasonably homogeneous technology
Thus it is suitable as an IGP for many campuses and for
networks using serial lines whose speeds do not vary widely. It
not intended for use in more complex environments. For
information on the context into which RIP is expected to fit,
Braden and Postel [3].
RIP is one of a class of algorithms known as "distance
algorithms". The earliest description of this class of
known to the author is in Ford and Fulkerson [6]. Because of this
they are sometimes known as Ford-Fulkerson algorithms. The
Bellman-Ford is also used. It comes from the fact that
formulation is based on Bellman's equation, the basis of "
programming". (For a standard introduction to this area, see [1].)
The presentation in this document is closely based on [2]. This
contains an introduction to the mathematics of routing algorithms
It describes and justifies several variants of the
presented here, as well as a number of other related algorithms.
basic algorithms described in this protocol were used in
routing as early as 1969 in the ARPANET. However, the
ancestry of this protocol is within the Xerox network protocols.
PUP protocols (see [4]) used the Gateway Information Protocol
exchange routing information. A somewhat updated version of
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
Protocol, with XNS addresses replaced by a more general
format capable of handling IP and other types of address, and
routing updates limited to one every 30 seconds. Because of
similarity, the term Routing Information Protocol (or just RIP)
used to refer to both the XNS protocol and the protocol used
routed
RIP is intended for use within the IP-based Internet. The
is organized into a number of networks connected by gateways.
networks may be either point-to-point links or more complex
such as Ethernet or the ARPANET. Hosts and gateways are
with IP datagrams addressed to some host. Routing is the method
which the host or gateway decides where to send the datagram. It
be able to send the datagram directly to the destination, if
destination is on one of the networks that are directly connected
the host or gateway. However, the interesting case is when
destination is not directly reachable. In this case, the host
gateway attempts to send the datagram to a gateway that is nearer
destination. The goal of a routing protocol is very simple: It is
Hedrick [Page 3]
RFC 1058 Routing Information Protocol June 1988
supply the information that is needed to do routing
1.1. Limitations of the
This protocol does not solve every possible routing problem.
mentioned above, it is primary intended for use as an IGP,
reasonably homogeneous networks of moderate size. In addition,
following specific limitations should be mentioned
- The protocol is limited to networks whose longest
involves 15 hops. The designers believe that the
protocol design is inappropriate for larger networks.
that this statement of the limit assumes that a cost of 1
is used for each network. This is the way RIP is
configured. If the system administrator chooses to
larger costs, the upper bound of 15 can easily become
problem
- The protocol depends upon "counting to infinity" to
certain unusual situations. (This will be explained in
next section.) If the system of networks has
hundred networks, and a routing loop was formed
all of them, the resolution of the loop would
either much time (if the frequency of routing updates
limited) or bandwidth (if updates were sent
changes were detected). Such a loop would consume a
amount of network bandwidth before the loop was corrected
We believe that in realistic cases, this will not be
problem except on slow lines. Even then, the problem
be fairly unusual, since various precautions are taken
should prevent these problems in most cases
- This protocol uses fixed "metrics" to compare
routes. It is not appropriate for situations where
need to be chosen based on real-time parameters such
measured delay, reliability, or load. The
extensions to allow metrics of this type are likely
introduce instabilities of a sort that the protocol is
designed to handle
1.2. Organization of this
The main body of this document is organized into two parts,
occupy the next two sections
2 A conceptual development and justification of distance
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
underpinnings of the algorithm. Note that the presentation follows
"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
are made to section 2, it should be possible to implement
entirely from the specifications given in section 3.
2. Distance Vector
Routing is the task of finding a path from a sender to a
destination. In the IP "Catenet model" this reduces primarily to
matter of finding gateways between networks. As long as a
remains on a single network or subnet, any routing problems
solved by technology that is specific to the network. For example
the Ethernet and the ARPANET each define a way in which any
can talk to any specified destination within that one network.
routing comes in primarily when messages must go from a sender on
such network to a destination on a different one. In that case,
message must pass through gateways connecting the networks. If
networks are not adjacent, the message may pass through
intervening networks, and the gateways connecting them. Once
message gets to a gateway that is on the same network as
destination, that network's own technology is used to get to
destination
Throughout this section, the term "network" is used generically
cover a single broadcast network (e.g., an Ethernet), a point
point line, or the ARPANET. The critical point is that a network
treated as a single entity by IP. Either no routing is necessary (
with a point to point line), or that routing is done in a manner
is transparent to IP, allowing IP to treat the entire network as
single fully-connected system (as with an Ethernet or the ARPANET).
Note that the term "network" is used in a somewhat different way
discussions of IP addressing. A single IP network number may
assigned to a collection of networks, with "subnet" addressing
used to describe the individual networks. In effect, we are
the term "network" here to refer to subnets in cases where
addressing is in use
A number of different approaches for finding routes between
are possible. One useful way of categorizing these approaches is
the basis of the type of information the gateways need to exchange
order to be able to find routes. Distance vector algorithms
based on the exchange of only a small amount of information.
Hedrick [Page 5]
RFC 1058 Routing Information Protocol June 1988
entity (gateway or host) that participates in the routing protocol
assumed to keep information about all of the destinations within
system. Generally, information about all entities connected to
network is summarized by a single entry, which describes the route
all destinations on that network. This summarization is
because as far as IP is concerned, routing within a network
invisible. Each entry in this routing database includes the
gateway to which datagrams destined for the entity should be sent
In addition, it includes a "metric" measuring the total distance
the entity. Distance is a somewhat generalized concept, which
cover the time delay in getting messages to the entity, the
cost of sending messages to it, etc. Distance vector algorithms
their name from the fact that it is possible to compute
routes when the only information exchanged is the list of
distances. Furthermore, information is only exchanged among
that are adjacent, that is, entities that share a common network
Although routing is most commonly based on information
networks, it is sometimes necessary to keep track of the routes
individual hosts. The RIP protocol makes no formal
between networks and hosts. It simply describes exchange
information about destinations, which may be either networks
hosts. (Note however, that it is possible for an implementor
choose not to support host routes. See section 3.2.) In fact,
mathematical developments are most conveniently thought of in
of routes from one host or gateway to another. When discussing
algorithm in abstract terms, it is best to think of a routing
for a network as an abbreviation for routing entries for all of
entities connected to that network. This sort of abbreviation
sense only because we think of networks as having no
structure that is visible at the IP level. Thus, we will
assign the same distance to every entity in a given network
We said above that each entity keeps a routing database with
entry for every possible destination in the system. An
implementation is likely to need to keep the following
about each destination
- address: in IP implementations of these algorithms,
will be the IP address of the host or network
- gateway: the first gateway along the route to
destination
- interface: the physical network which must be used to
the first gateway
- metric: a number, indicating the distance to
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
probably be included. This database is initialized with
description of the entities that are directly connected to
system. It is updated according to information received in
from neighboring gateways
The most important information exchanged by the hosts and gateways
that carried in update messages. Each entity that participates
the routing scheme sends update messages that describe the
database as it currently exists in that entity. It is possible
maintain optimal routes for the entire system by using
information obtained from neighboring entities. The algorithm
for that will be described in the next section
As we mentioned above, the purpose of routing is to find a way to
datagrams to their ultimate destinations. Distance vector
are based on a table giving the best route to every destination
the system. Of course, in order to define which route is best,
have to have some way of measuring goodness. This is referred to
the "metric".
In simple networks, it is common to use a metric that simply
how many gateways a message must go through. In more
networks, a metric is chosen to represent the total amount of
that the message suffers, the cost of sending it, or some
quantity which may be minimized. The main requirement is that
must be possible to represent the metric as a sum of "costs"
individual hops
Formally, if it is possible to get from entity i to entity j
(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
case where all entities on a given network are considered to be
same, d(i,j) is the same for all destinations on a given network,
represents the cost of using that network. To get the metric of
complete route, one just adds up the costs of the individual
that make up the route. For the purposes of this memo, we
that the costs are positive integers
Let D(i,j) represent the metric of the best route from entity i
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.
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
connection from a node to itself.) Since costs are additive, it
easy to show that the best metric must be described
D(i,i) = 0, all
D(i,j) = min [d(i,k) + D(k,j)],
and that the best routes start by going from i to those neighbors
for which d(i,k) + D(k,j) has the minimum value. (These things
be shown by induction on the number of steps in the routes.)
that we can limit the second equation to k's that are
neighbors of i. For the others, d(i,k) is infinite, so the
involving them can never be the minimum
It turns out that one can compute the metric by a simple
based on this. Entity i gets its neighbors k to send it
estimates of their distances to the destination j. When i gets
estimates from k, it adds d(i,k) to each of the numbers. This
simply the cost of traversing the network between i and k. Now
then i compares the values from all of its neighbors and picks
smallest
A proof is given in [2] that this algorithm will converge to
correct estimates of D(i,j) in finite time in the absence of
changes. The authors make very few assumptions about the order
which the entities send each other their information, or when the
is recomputed. Basically, entities just can't stop sending
or recomputing metrics, and the networks can't delay
forever. (Crash of a routing entity is a topology change.) Also
their proof does not make any assumptions about the initial
of D(i,j), except that they must be non-negative. The fact
these fairly weak assumptions are good enough is important.
we don't have to make assumptions about when updates are sent, it
safe to run the algorithm asynchronously. That is, each entity
send updates according to its own clock. Updates can be dropped
the network, as long as they don't all get dropped. Because we don'
have to make assumptions about the starting condition, the
can handle changes. When the system changes, the routing
starts moving to a new equilibrium, using the old one as its
point. It is important that the algorithm will converge in
time no matter what the starting point. Otherwise certain kinds
changes might lead to non-convergent behavior
The statement of the algorithm given above (and the proof)
that each entity keeps copies of the estimates that come from each
its neighbors, and now and then does a min over all of the neighbors
In fact real implementations don't necessarily do that. They
Hedrick [Page 8]
RFC 1058 Routing Information Protocol June 1988
remember the best metric seen so far, and the identity of
neighbor that sent it. They replace this information whenever
see a better (smaller) metric. This allows them to compute
minimum incrementally, without having to store data from all of
neighbors
There is one other difference between the algorithm as described
texts and those used in real protocols such as RIP: the
above would have each entity include an entry for itself, showing
distance of zero. In fact this is not generally done. Recall
all entities on a network are normally summarized by a single
for the network. Consider the situation of a host or gateway G
is connected to network A. C represents the cost of using network
(usually a metric of one). (Recall that we are assuming that
internal structure of a network is not visible to IP, and thus
cost of going between any two entities on it is the same.)
principle, G should get a message from every other entity H
network A, showing a cost of 0 to get from that entity to itself.
would then compute C + 0 as the distance to H. Rather than having
look at all of these identical messages, it simply starts out
making an entry for network A in its table, and assigning it a
of C. This entry for network A should be thought of as
the entries for all other entities on network A. The only entity
A that can't be summarized by that common entry is G itself,
the cost of going from G to G is 0, not C. But since we never
those 0 entries, we can safely get along with just the single
for network A. Note one other implication of this strategy:
we don't need to use the 0 entries for anything, hosts that do
function as gateways don't need to send any update messages.
hosts that don't function as gateways (i.e., hosts that are
to only one network) can have no useful information to
other than their own entry D(i,i) = 0. As they have only the
interface, it is easy to see that a route to any other
through them will simply go in that interface and then come
back out it. Thus the cost of such a route will be greater than
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
in the system, G will keep a current estimate of the metric for
destination (i.e., the total cost of getting to it) and the
of the neighboring gateway on whose data that metric is based.
the destination is on a network that is directly connected to G,
G simply uses an entry that shows the cost of using the network,
the fact that no gateway is needed to get to the destination. It
easy to show that once the computation has converged to the
metrics, the neighbor that is recorded by this technique is in
the first gateway on the path to the destination. (If there
Hedrick [Page 9]
RFC 1058 Routing Information Protocol June 1988
several equally good paths, it is the first gateway on one of them.)
This combination of destination, metric, and gateway is
referred to as a route to the destination with that metric,
that gateway
The method so far only has a way to lower the metric, as the
metric is kept until a smaller one shows up. It is possible that
initial estimate might be too low. Thus, there must be a way
increase the metric. It turns out to be sufficient to use
following rule: suppose the current route to a destination has
D and uses gateway G. If a new set of information arrived from
source other than G, only update the route if the new metric
better than D. But if a new set of information arrives from
itself, always update D to the new value. It is easy to show
with this rule, the incremental update process produces the
routes as a calculation that remembers the latest information
all the neighbors and does an explicit minimum. (Note that
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
been developed so far. (Note that this is not a statement of the
protocol. There are several refinements still to be added.)
following procedure is carried out by every entity that
in the routing protocol. This must include all of the gateways
the system. Hosts that are not gateways may participate as well
- Keep a table with an entry for every possible
in the system. The entry contains the distance D to
destination, and the first gateway G on the route to
network. Conceptually, there should be an entry for
entity itself, with metric 0, but this is not
included
- Periodically, send a routing update to every neighbor.
update is a set of messages that contain all of
information from the routing table. It contains an
for each destination, with the distance shown to
destination
- When a routing update arrives from a neighbor G', add
cost associated with the network that is shared with G'.
(This should be the network over which the update arrived.)
Call the resulting distance D'. Compare the
distances with the current routing table entries. If
new distance D' for N is smaller than the existing value D
adopt the new route. That is, change the table entry for
to have metric D' and gateway G'. If G' is the
Hedrick [Page 10]
RFC 1058 Routing Information Protocol June 1988
from which the existing route came, i.e., G' = G, then
the new metric even if it is larger than the old one
2.1. Dealing with changes in
The discussion above assumes that the topology of the network
fixed. In practice, gateways 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
immediate neighbors. If the topology changes, the set of
changes. Therefore, the next time the calculation is done,
change will be reflected. However, as mentioned above,
implementations use an incremental version of the minimization.
the best route to any given destination is remembered. If
gateway involved in that route should crash, or the
connection to it break, the calculation might never reflect
change. The algorithm as shown so far depends upon a
notifying its neighbors if its metrics change. If the
crashes, then it has no way of notifying neighbors of a change
In order to handle problems of this kind, distance vector
must make some provision for timing out routes. The details
upon the specific protocol. As an example, in RIP every gateway
participates in routing sends an update message to all its
once every 30 seconds. Suppose the current route for network N
gateway G. If we don't hear from G for 180 seconds, we can
that either the gateway has crashed or the network connecting us
it has become unusable. Thus, we mark the route as invalid. When
hear from another neighbor that has a valid route to N, the
route will replace the invalid one. Note that we wait for 180
seconds before timing out a route even though we expect to hear
each neighbor every 30 seconds. Unfortunately, messages
occasionally lost by networks. Thus, it is probably not a good
to invalidate a route based on a single missed message
As we will see below, it is useful to have a way to notify
that there currently isn't a valid route to some network. RIP,
with several other protocols of this class, does this through
normal update message, by marking that network as unreachable.
specific metric value is chosen to indicate an
destination; that metric value is larger than the largest
metric that we expect to see. In the existing implementation of RIP
16 is used. This value is normally referred to as "infinity",
it is larger than the largest valid metric. 16 may look like
surprisingly small number. It is chosen to be this small for
that we will see shortly. In most implementations, the
convention is used internally to flag a route as invalid
Hedrick [Page 11]
RFC 1058 Routing Information Protocol June 1988
2.2. Preventing
The algorithm as presented up to this point will always allow a
or gateway to calculate a correct routing table. However, that
still not quite enough to make it useful in practice. The
referred to above only show that the routing tables will converge
the correct values in finite time. They do not guarantee that
time will be small enough to be useful, nor do they say what
happen to the metrics for networks that become inaccessible
It is easy enough to extend the mathematics to handle routes
inaccessible. The convention suggested above will do that.
choose a large metric value to represent "infinity". This value
be large enough that no real metric would ever get that large.
the purposes of this example, we will use the value 16. Suppose
network becomes inaccessible. All of the immediately
gateways time out and set the metric for that network to 16.
purposes of analysis, we can assume that all the neighboring
have gotten a new piece of hardware that connects them directly
the vanished network, with a cost of 16. Since that is the
connection to the vanished network, all the other gateways in
system will converge to new routes that go through one of
gateways. It is easy to see that once convergence has happened,
the gateways will have metrics of at least 16 for the
network. Gateways one hop away from the original neighbors would
up with metrics of at least 17; gateways two hops away would end
with at least 18, etc. As these metrics are larger than the
metric value, they are all set to 16. It is obvious that the
will now converge to a metric of 16 for the vanished network at
gateways
Unfortunately, the question of how long convergence will take is
amenable to quite so simple an answer. Before going any further,
will be useful to look at an example (taken from [2]). Note, by
way, that what we are about to show will not happen with a
implementation of RIP. We are trying to show why certain
are needed. Note that the letters correspond to gateways, and
lines to networks
A-----
\ / \
\ / |
C / all networks have cost 1,
| / for the direct link from C to D,
|/ has cost 10
|<=== target
Hedrick [Page 12]
RFC 1058 Routing Information Protocol June 1988
Each gateway will have a table showing a route to each network
However, for purposes of this illustration, we show only the
from each gateway 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
adjust to use the link from C to D. Unfortunately, it will take
while for this to this to happen. The routing changes start when
notices that the route to D is no longer usable. For simplicity,
chart below assumes that all gateways send updates at the same time
The chart shows the metric for the target network, as it appears
the routing table at each gateway
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
unreach =
Here's the problem: B is able to get rid of its failed route using
timeout mechanism. But vestiges of that route persist in the
for a long time. Initially, A and C still think they can get to
via B. So, they keep sending updates listing metrics of 3. In
next iteration, B will then claim that it can get to D via either
or C. Of course, it can't. The routes being claimed by A and C
now gone, but they have no way of knowing that yet. And even
they discover that their routes via B have gone away, they each
there is a route available via the other. Eventually the
converges, as all the mathematics claims it must. But it can
some time to do so. The worst case is when a network
completely inaccessible from some part of the system. In that case
the metrics may increase slowly in a pattern like the one above
they finally reach infinity. For this reason, the problem is
"counting to infinity".
You should now see why "infinity" is chosen to be as small
possible. If a network becomes completely inaccessible, we
counting to infinity to be stopped as soon as possible.
must be large enough that no real route is that big. But
Hedrick [Page 13]
RFC 1058 Routing Information Protocol June 1988
shouldn't be any bigger than required. Thus the choice of
is a tradeoff between network size and speed of convergence in
counting to infinity happens. The designers of RIP believed that
protocol was unlikely to be practical for networks with a
larger than 15.
There are several things that can be done to prevent problems
this. The ones used by RIP are called "split horizon with
reverse", and "triggered updates".
2.2.1. Split
Note that some of the problem above is caused by the fact that A
C are engaged in a pattern of mutual deception. Each claims to
able to get to D via the other. This can be prevented by being a
more careful about where information is sent. In particular, it
never useful to claim reachability for a destination network to
neighbor(s) from which the route was learned. "Split horizon" is
scheme for avoiding problems caused by including routes in
sent to the gateway from which they were learned. The "simple
horizon" scheme omits routes learned from one neighbor in
sent to that neighbor. "Split horizon with poisoned reverse
includes such routes in updates, but sets their metrics to infinity
If A thinks it can get to D via C, its messages to C should
that D is unreachable. If the route through C is real, then C
has a direct connection to D, or a connection through some
gateway. C's route can't possibly go back to A, since that forms
loop. By telling C that D is unreachable, A simply guards
the possibility that C might get confused and believe that there is
route through A. This is obvious for a point to point line.
consider the possibility that A and C are connected by a
network such as an Ethernet, and there are other gateways on
network. If A has a route through C, it should indicate that D
unreachable when talking to any other gateway on that network.
other gateways on the network can get to C themselves. They
never need to get to C via A. If A's best route is really through C
no other gateway on that network needs to know that A can reach D
This is fortunate, because it means that the same update message
is used for C can be used for all other gateways on the same network
Thus, update messages can be sent by broadcast
In general, split horizon with poisoned reverse is safer than
split horizon. If two gateways have routes pointing at each other
advertising reverse routes with a metric of 16 will break the
immediately. If the reverse routes are simply not advertised,
erroneous routes will have to be eliminated by waiting for a timeout
However, poisoned reverse does have a disadvantage: it increases
Hedrick [Page 14]
RFC 1058 Routing Information Protocol June 1988
size of the routing messages. Consider the case of a campus
connecting a number of different buildings. In each building,
is a gateway connecting the backbone to a local network.
what routing updates those gateways should broadcast on the
network. All that the rest of the network really needs to know
each gateway is what local networks it is connected to. Using
split horizon, only those routes would appear in update messages
by the gateway to the backbone network. If split horizon
poisoned reverse is used, the gateway must mention all routes that
learns from the backbone, with metrics of 16. If the system
large, this can result in a large update message, almost all of
entries indicate unreachable networks
In a static sense, advertising reverse routes with a metric of 16
provides no additional information. If there are many gateways
one broadcast network, these extra entries can use
bandwidth. The reason they are there is to improve dynamic behavior
When topology changes, mentioning routes that should not go
the gateway as well as those that should can speed up convergence
However, in some situations, network managers may prefer to
somewhat slower convergence in order to minimize routing overhead
Thus implementors may at their option implement simple split
rather than split horizon with poisoned reverse, or they may
a configuration option that allows the network manager to
which behavior to use. It is also permissible to implement
schemes that advertise some reverse routes with a metric of 16
omit others. An example of such a scheme would be to use a metric
16 for reverse routes for a certain period of time after
changes involving them, and thereafter omitting them from updates
2.2.2. Triggered
Split horizon with poisoned reverse will prevent any routing
that involve only two gateways. However, it is still possible to
up with patterns in which three gateways are engaged in
deception. For example, A may believe it has a route through B,
through C, and C through A. Split horizon cannot stop such a loop
This loop will only be resolved when the metric reaches infinity
the network involved is then declared unreachable. Triggered
are an attempt to speed up this convergence. To get
updates, we simply add a rule that whenever a gateway changes
metric for a route, it is required to send update messages
immediately, even if it is not yet time for one of the regular
message. (The timing details will differ from protocol to protocol
Some distance vector protocols, including RIP, specify a small
delay, in order to avoid having triggered updates generate
network traffic.) Note how this combines with the rules
computing new metrics. Suppose a gateway's route to destination
Hedrick [Page 15]
RFC 1058 Routing Information Protocol June 1988
goes through gateway G. If an update arrives from G itself,
receiving gateway is required to believe the new information,
the new metric is higher or lower than the old one. If the result
a change in metric, then the receiving gateway will send
updates to all the hosts and gateways directly connected to it.
in turn may each send updates to their neighbors. The result is
cascade of triggered updates. It is easy to show which gateways
hosts are involved in the cascade. Suppose a gateway G times out
route to destination N. G will send triggered updates to all of
neighbors. However, the only neighbors who will believe the
information are those whose routes for N go through G. The
gateways and hosts will see this as information about a new
that is worse than the one they are already using, and ignore it
The neighbors whose routes go through G will update their metrics
send triggered updates to all of their neighbors. Again, only
neighbors whose routes go through them will pay attention. Thus,
triggered updates will propagate backwards along all paths leading
gateway G, updating the metrics to infinity. This propagation
stop as soon as it reaches a portion of the network whose route
destination N takes some other path
If the system could be made to sit still while the cascade
triggered updates happens, it would be possible to prove
counting to infinity will never happen. Bad routes would always
removed immediately, and so no routing loops could form
Unfortunately, things are not so nice. While the triggered
are being sent, regular updates may be happening at the same time
Gateways that haven't received the triggered update yet will still
sending out information based on the route that no longer exists.
is possible that after the triggered update has gone through
gateway, it might receive a normal update from one of these
that hasn't yet gotten the word. This could reestablish an
remnant of the faulty route. If triggered updates happen
enough, this is very unlikely. However, counting to infinity
still possible
3. Specifications for the
RIP is intended to allow hosts and gateways to exchange
for computing routes through an IP-based network. RIP is a
vector protocol. Thus, it has the general features described
section 2. RIP may be implemented by both hosts and gateways. As
most IP documentation, the term "host" will be used here to
either. RIP is used to convey information about routes
"destinations", which may be individual hosts, networks, or a
destination used to convey a default route
Hedrick [Page 16]
RFC 1058 Routing Information Protocol June 1988
Any host that uses RIP is assumed to have interfaces to one or
networks. These are referred to as its "directly-
networks". The protocol relies on access to certain
about each of these networks. The most important is its metric
"cost". The metric of a network is an integer between 1 and 15
inclusive. It is set in some manner not specified in this protocol
Most existing implementations always use a metric of 1.
implementations should allow the system administrator to set the
of each network. In addition to the cost, each network will have
IP network number and a subnet mask associated with it. These are
be set by the system administrator in a manner not specified in
protocol
Note that the rules specified in section 3.2 assume that there is
single subnet mask applying to each IP network, and that only
subnet masks for directly-connected networks are known. There may
systems that use different subnet masks for different subnets
a single network. There may also be instances where it is
for a system to know the subnets masks of distant networks. However
such situations will require modifications of the rules which
the spread of subnet information. Such modifications raise issues
interoperability, and thus must be viewed as modifying the protocol
Each host that implements RIP is assumed to have a routing table
This table has one entry for every destination that is
through the system described by RIP. Each entry contains at
the following information
- The IP address of the destination
- A metric, which represents the total cost of getting
datagram from the host to that destination. This metric
the sum of the costs associated with the networks
would be traversed in getting to the destination
- The IP address of the next gateway along the path to
destination. If the destination is on one of
directly-connected networks, this item is not needed
- A flag to indicate that information about the route
changed recently. This will be referred to as the "
change flag."
- Various timers associated with the route. See section 3.3
for more details on them
The entries for the directly-connected networks are set up by
host, using information gathered by means not specified in
Hedrick [Page 17]
RFC 1058 Routing Information Protocol June 1988
protocol. The metric for a directly-connected network is set to
cost of that network. In existing RIP implementations, 1 is
used for the cost. In that case, the RIP metric reduces to a
hop-count. More complex metrics may be used when it is desirable
show preference for some networks over others, for example because
differences in bandwidth or reliability
Implementors may also choose to allow the system administrator
enter additional routes. These would most likely be routes to
or networks outside the scope of the routing system
Entries for destinations other these initial ones are added
updated by the algorithms described in the following sections
In order for the protocol to provide complete information on routing
every gateway in the system must participate in it. Hosts that
not gateways need not participate, but many implementations
provisions for them to listen to routing information in order
allow them to maintain their routing tables
3.1. Message
RIP is a UDP-based protocol. Each host that uses RIP has a
process that sends and receives datagrams on UDP port number 520.
All communications directed at another host's RIP processor are
to port 520. All routing update messages are sent from port 520.
Unsolicited routing update messages have both the source
destination port equal to 520. Those sent in response to a
are sent to the port from which the request came. Specific
and debugging requests may be sent from ports other than 520,
they are directed to port 520 on the target machine
There are provisions in the protocol to allow "silent" RIP processes
A silent process is one that normally does not send out any messages
However, it listens to messages sent by others. A silent RIP
be used by hosts that do not act as gateways, but wish to listen
routing updates in order to monitor local gateways and to keep
internal routing tables up to date. (See [5] for a discussion
various ways that hosts can keep track of network topology.)
gateway that has lost contact with all but one of its networks
choose to become silent, since it is effectively no longer a gateway
However, this should not be done if there is any chance
neighboring gateways might depend upon its messages to detect
the failed network has come back into operation. (The 4BSD
program uses routing packets to monitor the operation of point-to
point links.)
Hedrick [Page 18]
RFC 1058 Routing Information Protocol June 1988
The packet format is shown in Figure 1.
Format of datagrams containing network information. Field
are given in octets. Unless otherwise specified, fields
binary integers, in normal Internet order with the most-
octet first. Each tick mark represents one bit
0 1 2 3 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| command (1) | version (1) | must be zero (2) |
+---------------+---------------+-------------------------------+
| address family identifier (2) | must be zero (2) |
+-------------------------------+-------------------------------+
| IP address (4) |
+---------------------------------------------------------------+
| must be zero (4) |
+---------------------------------------------------------------+
| must be zero (4) |
+---------------------------------------------------------------+
| metric (4) |
+---------------------------------------------------------------+
.
.
.
The portion of the datagram from address family identifier
metric may appear up to 25 times. IP address is the usual 4-
Internet address, in network order
Figure 1. Packet
Every datagram contains a command, a version number, and
arguments. This document describes version 1 of the protocol
Details of processing the version number are described in
3.4. The command field is used to specify the purpose of
datagram. Here is a summary of the commands implemented in
1:
1 - request A request for the responding system to send all
part of its routing table
2 - response A message containing all or part of the sender'
routing table. This message may be sent in
to a request or poll, or it may be an update
generated by the sender
3 - traceon Obsolete. Messages containing this command are to
ignored
Hedrick [Page 19]
RFC 1058 Routing Information Protocol June 1988
4 - traceoff Obsolete. Messages containing this command are to
ignored
5 - reserved This value is used by Sun Microsystems for its
purposes. If new commands are added in
succeeding version, they should begin with 6.
Messages containing this command may safely
ignored by implementations that do not choose
respond to it
For request and response, the rest of the datagram contains a list
destinations, with information about each. Each entry in this
contains a destination network or host, and the metric for it.
packet format is intended to allow RIP to carry routing
for several different protocols. Thus, each entry has an
family identifier to indicate what type of address is specified
that entry. This document only describes routing for
networks. The address family identifier for IP is 2. None of
RIP implementations available to the author implement any other
of address. However, to allow for future development
implementations are required to skip entries that specify
families that are not supported by the implementation. (The size
these entries will be the same as the size of an entry specifying
IP address.) Processing of the message continues normally after
unsupported entries are skipped. The IP address is the
Internet address, stored as 4 octets in network order. The
field must contain a value between 1 and 15 inclusive, specifying
current metric for the destination, or the value 16, which
that the destination is not reachable. Each route sent by a
supercedes any previous route to the same destination from the
gateway
The maximum datagram size is 512 octets. This includes only
portions of the datagram described above. It does not count the
or UDP headers. The commands that involve network information
information to be split across several datagrams. No
provisions are needed for continuations, since correct results
occur if the datagrams are processed individually
3.2. Addressing
As indicated in section 2, distance vector routing can be used
describe routes to individual hosts or to networks. The RIP
allows either of these possibilities. The destinations appearing
request and response messages can be networks, hosts, or a
code used to indicate a default address. In general, the kinds
routes actually used will depend upon the routing strategy used
the particular network. Many networks are set up so that
Hedrick [Page 20]
RFC 1058 Routing Information Protocol June 1988
information for individual hosts is not needed. If every host on
given network or subnet is accessible through the same gateways,
there is no reason to mention individual hosts in the routing tables
However, networks that include point to point lines sometimes
gateways to keep track of routes to certain hosts. Whether
feature is required depends upon the addressing and routing
used in the system. Thus, some implementations may choose not
support host routes. If host routes are not supported, they are
be dropped when they are received in response messages. (See
3.4.2.)
The RIP packet formats do not distinguish among various types
address. Fields that are labeled "address" can contain any of
following
host
subnet
network
0, indicating a default
Entities that use RIP are assumed to use the most
information available when routing a datagram. That is, when
a datagram, its destination address must first be checked against
list of host addresses. Then it must be checked to see whether
matches any known subnet or network number. Finally, if none
these match, the default route is used
When a host evaluates information that it receives via RIP,
interpretation of an address depends upon whether it knows the
mask that applies to the net. If so, then it is possible
determine the meaning of the address. For example, consider
128.6. It has a subnet mask of 255.255.255.0. Thus 128.6.0.0 is
network number, 128.6.4.0 is a subnet number, and 128.6.4.1 is a
address. However, if the host does not know the subnet mask
evaluation of an address may be ambiguous. If there is a non-
host part, there is no clear way to determine whether the
represents a subnet number or a host address. As a subnet
would be useless without the subnet mask, addresses are assumed
represent hosts in this situation. In order to avoid this sort
ambiguity, hosts must not send subnet routes to hosts that cannot
expected to know the appropriate subnet mask. Normally hosts
know the subnet masks for directly-connected networks. Therefore
unless special provisions have been made, routes to a subnet must
be sent outside the network of which the subnet is a part
This filtering is carried out by the gateways at the "border" of
subnetted network. These are gateways that connect that network
some other network. Within the subnetted network, each subnet
Hedrick [Page 21]
RFC 1058 Routing Information Protocol June 1988
treated as an individual network. Routing entries for each
are circulated by RIP. However, border gateways send only a
entry for the network as a whole to hosts in other networks.
means that a border gateway will send different information
different neighbors. For neighbors connected to the
network, it generates a list of all subnets to which it is
connected, using the subnet number. For neighbors connected to
networks, it makes a single entry for the network as a whole,
the metric associated with that network. (This metric would
be the smallest metric for the subnets to which the gateway
attached.)
Similarly, border gateways must not mention host routes for
within one of the directly-connected networks in messages to
networks. Those routes will be subsumed by the single entry for
network as a whole. We do not specify what to do with host
for "distant" hosts (i.e., hosts not part of one of the directly
connected networks). Generally, these routes indicate some host
is reachable via a route that does not support other hosts on
network of which the host is a part
The special address 0.0.0.0 is used to describe a default route.
default route is used when it is not convenient to list
possible network in the RIP updates, and when one or more closely
connected gateways in the system are prepared to handle traffic
the networks that are not listed explicitly. These gateways
create RIP entries for the address 0.0.0.0, just as if it were
network to which they are connected. The decision as to how
create entries for 0.0.0.0 is left to the implementor.
commonly, the system administrator will be provided with a way
specify which gateways should create entries for 0.0.0.0. However
other mechanisms are possible. For example, an implementor
decide that any gateway that speaks EGP should be declared to be
default gateway. It may be useful to allow the network
to choose the metric to be used in these entries. If there is
than one default gateway, this will make it possible to express
preference for one over the other. The entries for 0.0.0.0
handled by RIP in exactly the same manner as if there were an
network with this address. However, the entry is used to route
datagram whose destination address does not match any other
in the table. Implementations are not required to support
convention. However, it is strongly recommended.
that do not support 0.0.0.0 must ignore entries with this address
In such cases, they must not pass the entry on in their own
updates. System administrators should take care to make sure
routes to 0.0.0.0 do not propagate further than is intended
Generally, each autonomous system has its own preferred
gateway. Thus, routes involving 0.0.0.0 should generally not
Hedrick [Page 22]
RFC 1058 Routing Information Protocol June 1988
the boundary of an autonomous system. The mechanisms for
this are not specified in this document
3.3.
This section describes all events that are triggered by timers
Every 30 seconds, the output process is instructed to generate
complete response to every neighboring gateway. When there are
gateways on a single network, there is a tendency for them
synchronize with each other such that they all issue updates at
same time. This can happen whenever the 30 second timer is
by the processing load on the system. It is undesirable for
update messages to become synchronized, since it can lead
unnecessary collisions on broadcast networks. Thus,
are required to take one of two precautions
- The 30-second updates are triggered by a clock whose
is not affected by system load or the time required
service the previous update timer
- The 30-second timer is offset by addition of a small
time each time it is set
There are two timers associated with each route, a "timeout" and
"garbage-collection time". Upon expiration of the timeout, the
is no longer valid. However, it is retained in the table for a
time, so that neighbors can be notified that the route has
dropped. Upon expiration of the garbage-collection timer, the
is finally removed from the tables
The timeout is initialized when a route is established, and any
an update message is received for the route. If 180 seconds
from the last time the timeout was initialized, the route
considered to have expired, and the deletion process which we
about to describe is started for it
Deletions can occur for one of two reasons: (1) the timeout expires
or (2) the metric is set to 16 because of an update received from
current gateway. (See section 3.4.2 for a discussion
updates from other gateways.) In either case, the following
happen
- The garbage-collection timer is set for 120 seconds
- The metric for the route is set to 16 (infinity).
causes the route to be removed from service
Hedrick [Page 23]
RFC 1058 Routing Information Protocol June 1988
- A flag is set noting that this entry has been changed,
the output process is signalled to trigger a response
Until the garbage-collection timer expires, the route is included
all updates sent by this host, with a metric of 16 (infinity).
the garbage-collection timer expires, the route is deleted from
tables
Should a new route to this network be established while the garbage
collection timer is running, the new route will replace the one
is about to be deleted. In this case the garbage-collection
must be cleared
See section 3.5 for a discussion of a delay that is required
carrying out triggered updates. Although implementation of
delay will require a timer, it is more natural to discuss it
section 3.5 than here
3.4. Input
This section will describe the handling of datagrams received on
port 520. Before processing the datagrams in detail, certain
format checks must be made. These depend upon the version
field in the datagram, as follows
0 Datagrams whose version number is zero are to be ignored
These are from a previous version of the protocol,
packet format was machine-specific
1 Datagrams whose version number is one are to be
as described in the rest of this specification. All
that are described above as "must be zero" are to be checked
If any such field contains a non-zero value, the
message is to be ignored
>1 Datagrams whose version number are greater than one
to be processed as described in the rest of
specification. All fields that are described above
"must be zero" are to be ignored. Future versions of
protocol may put data into these fields. Version 1
implementations are to ignore this extra data and
only the fields specified in this document
After checking the version number and doing any other
checks, processing will depend upon the value in the command field
Hedrick [Page 24]
RFC 1058 Routing Information Protocol June 1988
3.4.1.
Request is used to ask for a response containing all or part of
host's routing table. [Note that the term host is used for
host or gateway, in most cases it would be unusual for a non-
host to send RIP messages.] Normally, requests are sent
broadcasts, from a UDP source port of 520. In this case,
processes do not respond to the request. Silent processes are
definition processes for which we normally do not want to see
information. However, there may be situations involving
monitoring where it is desired to look at the routing table even
a silent process. In this case, the request should be sent from
UDP port number other than 520. If a request comes from port 520,
silent processes do not respond. If the request comes from any
port, processes must respond even if they are silent
The request is processed entry by entry. If there are no entries,
response is given. There is one special case. If there is
one entry in the request, with an address family identifier of 0
(meaning unspecified), and a metric of infinity (i.e., 16 for
implementations), this is a request to send the entire routing table
In that case, a call is made to the output process to send
routing table to the requesting port
Except for this special case, processing is quite simple. Go
the list of entries in the request one by one. For each entry,
up the destination in the host's routing database. If there is
route, put that route's metric in the metric field in the datagram
If there isn't a route to the specified destination, put
(i.e., 16) in the metric field in the datagram. Once all the
have been filled in, set the command to 