respond to it.
For request and response, the rest of the datagram contains a list of
destinations, with information about each. Each entry in this list
contains a destination network or host, and the metric for it. The
packet format is intended to allow RIP to carry routing information
for several different protocols. Thus, each entry has an address
family identifier to indicate what type of address is specified in
that entry. This document only describes routing for Internet
networks. The address family identifier for IP is 2. None of the
RIP implementations available to the author implement any other type
of address. However, to allow for future development,
implementations are required to skip entries that specify address
families that are not supported by the implementation. (The size of
these entries will be the same as the size of an entry specifying an
IP address.) Processing of the message continues normally after any
unsupported entries are skipped. The IP address is the usual
Internet address, stored as 4 octets in network order. The metric
field must contain a value between 1 and 15 inclusive, specifying the
current metric for the destination, or the value 16, which indicates
that the destination is not reachable. Each route sent by a gateway
supercedes any previous route to the same destination from the same
gateway.
The maximum datagram size is 512 octets. This includes only the
portions of the datagram described above. It does not count the IP
or UDP headers. The commands that involve network information allow
information to be split across several datagrams. No special
provisions are needed for continuations, since correct results will
occur if the datagrams are processed individually.
3.2. Addressing considerations
As indicated in section 2, distance vector routing can be used to
describe routes to individual hosts or to networks. The RIP protocol
allows either of these possibilities. The destinations appearing in
request and response messages can be networks, hosts, or a special
code used to indicate a default address. In general, the kinds of
routes actually used will depend upon the routing strategy used for
the particular network. Many networks are set up so that routing
information for individual hosts is not needed. If every host on a
given network or subnet is accessible through the same gateways, then
there is no reason to mention individual hosts in the routing tables.
However, networks that include point to point lines sometimes require
gateways to keep track of routes to certain hosts. Whether this
feature is required depends upon the addressing and routing approach
used in the system. Thus, some implementations may choose not to
support host routes. If host routes are not supported, they are to
be dropped when they are received in response messages. (See section
3.4.2.)
The RIP packet formats do not distinguish among various types of
address. Fields that are labeled "address" can contain any of the
following:
host address
subnet number
network number
0, indicating a default route
Entities that use RIP are assumed to use the most specific
information available when routing a datagram. That is, when routing
a datagram, its destination address must first be checked against the
list of host addresses. Then it must be checked to see whether it
matches any known subnet or network number. Finally, if none of
these match, the default route is used.
When a host evaluates information that it receives via RIP, its
interpretation of an address depends upon whether it knows the subnet
mask that applies to the net. If so, then it is possible to
determine the meaning of the address. For example, consider net
128.6. It has a subnet mask of 255.255.255.0. Thus 128.6.0.0 is a
network number, 128.6.4.0 is a subnet number, and 128.6.4.1 is a host
address. However, if the host does not know the subnet mask,
evaluation of an address may be ambiguous. If there is a non-zero
host part, there is no clear way to determine whether the address
represents a subnet number or a host address. As a subnet number
would be useless without the subnet mask, addresses are assumed to
represent hosts in this situation. In order to avoid this sort of
ambiguity, hosts must not send subnet routes to hosts that cannot be
expected to know the appropriate subnet mask. Normally hosts only
know the subnet masks for directly-connected networks. Therefore,
unless special provisions have been made, routes to a subnet must not
be sent outside the network of which the subnet is a part.
This filtering is carried out by the gateways at the "border" of the
subnetted network. These are gateways that connect that network with
some other network. Within the subnetted network, each subnet is
treated as an individual network. Routing entries for each subnet
are circulated by RIP. However, border gateways send only a single
entry for the network as a whole to hosts in other networks. This
means that a border gateway will send different information to
different neighbors. For neighbors connected to the subnetted
network, it generates a list of all subnets to which it is directly
connected, using the subnet number. For neighbors connected to other
networks, it makes a single entry for the network as a whole, showing
the metric associated with that network. (This metric would normally
be the smallest metric for the subnets to which the gateway is
attached.)
Similarly, border gateways must not mention host routes for hosts
within one of the directly-connected networks in messages to other
networks. Those routes will be subsumed by the single entry for the
network as a whole. We do not specify what to do with host routes
for "distant" hosts (i.e., hosts not part of one of the directly-
connected networks). Generally, these routes indicate some host that
is reachable via a route that does not support other hosts on the
network of which the host is a part.
The special address 0.0.0.0 is used to describe a default route. A
default route is used when it is not convenient to list every
possible network in the RIP updates, and when one or more closely-
connected gateways in the system are prepared to handle traffic to
the networks that are not listed explicitly. These gateways should
create RIP entries for the address 0.0.0.0, just as if it were a
network to which they are connected. The decision as to how gateways
create entries for 0.0.0.0 is left to the implementor. Most
commonly, the system administrator will be provided with a way to
specify which gateways should create entries for 0.0.0.0. However,
other mechanisms are possible. For example, an implementor might
decide that any gateway that speaks EGP should be declared to be a
default gateway. It may be useful to allow the network administrator
to choose the metric to be used in these entries. If there is more
than one default gateway, this will make it possible to express a
preference for one over the other. The entries for 0.0.0.0 are
handled by RIP in exactly the same manner as if there were an actual
network with this address. However, the entry is used to route any
datagram whose destination address does not match any other network
in the table. Implementations are not required to support this
convention. However, it is strongly recommended. Implementations
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 RIP
updates. System administrators should take care to make sure that
routes to 0.0.0.0 do not propagate further than is intended.
Generally, each autonomous system has its own preferred default
gateway. Thus, routes involving 0.0.0.0 should generally not leave
the boundary of an autonomous system. The mechanisms for enforcing
this are not specified in this document.
3.3. Timers
This section describes all events that are triggered by timers.
Every 30 seconds, the output process is instructed to generate a
complete response to every neighboring gateway. When there are many
gateways on a single network, there is a tendency for them to
synchronize with each other such that they all issue updates at the
same time. This can happen whenever the 30 second timer is affected
by the processing load on the system. It is undesirable for the
update messages to become synchronized, since it can lead to
unnecessary collisions on broadcast networks. Thus, implementations
are required to take one of two precautions.
- The 30-second updates are triggered by a clock whose rate
is not affected by system load or the time required to
service the previous update timer.
- The 30-second timer is offset by addition of a small random
time each time it is set.
There are two timers associated with each route, a "timeout" and a
"garbage-collection time". Upon expiration of the timeout, the route
is no longer valid. However, it is retained in the table for a short
time, so that neighbors can be notified that the route has been
dropped. Upon expiration of the garbage-collection timer, the route
is finally removed from the tables.
The timeout is initialized when a route is established, and any time
an update message is received for the route. If 180 seconds elapse
from the last time the timeout was initialized, the route is
considered to have expired, and the deletion process which we are
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 the
current gateway. (See section 3.4.2 for a discussion processing
updates from other gateways.) In either case, the following events
happen:
- The garbage-collection timer is set for 120 seconds.
- The metric for the route is set to 16 (infinity). This
causes the route to be removed from service.
- A flag is set noting that this entry has been changed, and
the output process is signalled to trigger a response.
Until the garbage-collection timer expires, the route is included in
all updates sent by this host, with a metric of 16 (infinity). When
the garbage-collection timer expires, the route is deleted from the
tables.
Should a new route to this network be established while the garbage-
collection timer is running, the new route will replace the one that
is about to be deleted. In this case the garbage-collection timer
must be cleared.
See section 3.5 for a discussion of a delay that is required in
carrying out triggered updates. Although implementation of that
delay will require a timer, it is more natural to discuss it in
section 3.5 than here.
3.4. Input processing
This section will describe the handling of datagrams received on UDP
port 520. Before processing the datagrams in detail, certain general
format checks must be made. These depend upon the version number
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, whose
packet format was machine-specific.
1 Datagrams whose version number is one are to be processed
as described in the rest of this specification. All fields
that are described above as "must be zero" are to be checked.
If any such field contains a non-zero value, the entire
message is to be ignored.
>1 Datagrams whose version number are greater than one are
to be processed as described in the rest of this
specification. All fields that are described above as
"must be zero" are to be ignored. Future versions of the
protocol may put data into these fields. Version 1
implementations are to ignore this extra data and process
only the fields specified in this document.
After checking the version number and doing any other preliminary
checks, processing will depend upon the value in the command field.
3.4.1. Request
Request is used to ask for a response containing all or part of the
host's routing table. [Note that the term host is used for either
host or gateway, in most cases it would be unusual for a non-gateway
host to send RIP messages.] Normally, requests are sent as
broadcasts, from a UDP source port of 520. In this case, silent
processes do not respond to the request. Silent processes are by
definition processes for which we normally do not want to see routing
information. However, there may be situations involving gateway
monitoring where it is desired to look at the routing table even for
a silent process. In this case, the request should be sent from a
UDP port number other than 520. If a request comes from port 520,
silent processes do not respond. If the request comes from any other
port, processes must respond even if they are silent.
The request is processed entry by entry. If there are no entries, no
response is given. There is one special case. If there is exactly
one entry in the request, with an address family identifier of 0
(meaning unspecified), and a metric of infinity (i.e., 16 for current
implementations), this is a request to send the entire routing table.
In that case, a call is made to the output process to send the
routing table to the requesting port.
Except for this special case, processing is quite simple. Go down
the list of entries in the request one by one. For each entry, look
up the destination in the host's routing database. If there is a
route, put that route's metric in the metric field in the datagram.
If there isn't a route to the specified destination, put infinity
(i.e., 16) in the metric field in the datagram. Once all the entries
have been filled in, set the command to response and send the
datagram back to the port from which it came.
Note that there is a difference in handling depending upon whether
the request is for a specified set of destinations, or for a complete
routing table. If the request is for a complete host table, normal
output processing is done. This includes split horizon (see section
2.2.1) and subnet hiding (section 3.2), so that certain entries from
the routing table will not be shown. If the request is for specific
entries, they are looked up in the host table and the information is
returned. No split horizon processing is done, and subnets are
returned if requested. We anticipate that these requests are likely
to be used for different purposes. When a host first comes up, it
broadcasts requests on every connected network asking for a complete
routing table. In general, we assume that complete routing tables
are likely to be used to update another host's routing table. For
this reason, split horizon and all other filtering must be used.
Requests for specific networks are made only by diagnostic software,
and are not used for routing. In this case, the requester would want
to know the exact contents of the routing database, and would not
want any information hidden.
3.4.2. Response
Responses can be received for several different reasons:
response to a specific query
regular updates
triggered updates triggered by a metric change
Processing is the same no matter how responses were generated.
Because processing of a response may update the host's routing table,
the response must be checked carefully for validity. The response
must be ignored if it is not from port 520. The IP source address
should be checked to see whether the datagram is from a valid
neighbor. The source of the datagram must be on a directly-connected
network. It is also worth checking to see whether the response is
from one of the host's own addresses. Interfaces on broadcast
networks may receive copies of their own broadcasts immediately. If
a host processes its own output as new input, confusion is likely,
and such datagrams must be ignored (except as discussed in the next
paragraph).
Before actually processing a response, it may be useful to use its
presence as input to a process for keeping track of interface status.
As mentioned above, we time out a route when we haven't heard from
its gateway for a certain amount of time. This works fine for routes
that come from another gateway. It is also desirable to know when
one of our own directly-connected networks has failed. This document
does not specify any particular method for doing this, as such
methods depend upon the characteristics of the network and the
hardware interface to it. However, such methods often involve
listening for datagrams arriving on the interface. Arriving
datagrams can be used as an indication that the interface is working.
However, some caution must be used, as it is possible for interfaces
to fail in such a way that input datagrams are received, but output
datagrams are never sent successfully.
Now that the datagram as a whole has been validated, process the
entries in it one by one. Again, start by doing validation. If the
metric is greater than infinity, ignore the entry. (This should be
impossible, if the other host is working correctly. Incorrect
metrics and other format errors should probably cause alerts or be
logged.) Then look at the destination address. Check the address
family identifier. If it is not a value which is expected (e.g., 2
for Internet addresses), ignore the entry. Now check the address
itself for various kinds of inappropriate addresses. Ignore the
entry if the address is class D or E, if it is on net 0 (except for
0.0.0.0, if we accept default routes) or if it is on net 127 (the
loopback network). Also, test for a broadcast address, i.e.,
anything whose host part is all ones on a network that supports
broadcast, and ignore any such entry. If the implementor has chosen
not to support host routes (see section 3.2), check to see whether
the host portion of the address is non-zero; if so, ignore the entry.
Recall that the address field contains a number of unused octets. If
the version number of the datagram is 1, they must also be checked.
If any of them is nonzero, the entry is to be ignored. (Many of
these cases indicate that the host from which the message came is not
working correctly. Thus some form of error logging or alert should
be triggered.)
Update the metric by adding the cost of the network on which the
message arrived. If the result is greater than 16, use 16. That is,
metric = MIN (metric + cost, 16)
Now look up the address to see whether this is already a route for
it. In general, if not, we want to add one. However, there are
various exceptions. If the metric is infinite, don't add an entry.
(We would update an existing one, but we don't add new entries with
infinite metric.) We want to avoid adding routes to hosts if the
host is part of a net or subnet for which we have at least as good a
route. If neither of these exceptions applies, add a new entry to
the routing database. This includes the following actions:
- Set the destination and metric to those from the datagram.
- Set the gateway to be the host from which the datagram
came.
- Initialize the timeout for the route. If the garbage-
collection timer is running for this route, stop it. (See
section 3.3 for a discussion of the timers.)
- Set the route change flag, and signal the output process to
trigger an update (see 3.5).
If there is an existing route, first compare gateways. If this
datagram is from the same gateway as the existing route, reinitialize
the timeout. Next compare metrics. If the datagram is from the same
gateway as the existing route and the new metric is different than
the old one, or if the new metric is lower than the old one, do the
following actions:
- adopt the route from the datagram. That is, put the new
metric in, and set the gateway to be the host from which
the datagram came.
- Initialize the timeout for the route.
- Set the route change flag, and signal the output process to
trigger an update (see 3.5).
- If the new metric is 16 (infinity), the deletion process is
started.
If the new metric is 16 (infinity), this starts the process for
deleting the route. The route is no longer used for routing packets,
and the deletion timer is started (see section 3.3). Note that a
deletion is started only when the metric is first set to 16. If the
metric was already 16, then a new deletion is not started. (Starting
a deletion sets a timer. The concern is that we do not want to reset
the timer every 30 seconds, as new messages arrive with an infinite
metric.)
If the new metric is the same as the old one, it is simplest to do
nothing further (beyond reinitializing the timeout, as specified
above). However, the 4BSD routed uses an additional heuristic here.
Normally, it is senseless to change to a route with the same metric
as the existing route but a different gateway. If the existing route
is showing signs of timing out, though, it may be better to switch to
an equally-good alternative route immediately, rather than waiting
for the timeout to happen. (See section 3.3 for a discussion of
timeouts.) Therefore, if the new metric is the same as the old one,
routed looks at the timeout for the existing route. If it is at
least halfway to the expiration point, routed switches to the new
route. That is, the gateway is changed to the source of the current
message. This heuristic is optional.
Any entry that fails these tests is ignored, as it is no better than
the current route.
3.5. Output Processing
This section describes the processing used to create response
messages that contain all or part of the routing table. This
processing may be triggered in any of the following ways:
- by input processing when a request is seen. In this case,
the resulting message is sent to only one destination.
- by the regular routing update. Every 30 seconds, a
response containing the whole routing table is sent to
every neighboring gateway. (See section 3.3.)
- by triggered updates. Whenever the metric for a route is
changed, an update is triggered. (The update may be
delayed; see below.)
Before describing the way a message is generated for each directly-
connected network, we will comment on how the destinations are chosen
for the latter two cases. Normally, when a response is to be sent to
all destinations (that is, either the regular update or a triggered
update is being prepared), a response is sent to the host at the
opposite end of each connected point-to-point link, and a response is
broadcast on all connected networks that support broadcasting. Thus,
one response is prepared for each directly-connected network and sent
to the corresponding (destination or broadcast) address. In most
cases, this reaches all neighboring gateways. However, there are
some cases where this may not be good enough. This may involve a
network that does not support broadcast (e.g., the ARPANET), or a
situation involving dumb gateways. In such cases, it may be
necessary to specify an actual list of neighboring hosts and
gateways, and send a datagram to each one explicitly. It is left to
the implementor to determine whether such a mechanism is needed, and
to define how the list is specified.
Triggered updates require special handling for two reasons. First,
experience shows that triggered updates can cause excessive loads on
networks with limited capacity or with many gateways on them. Thus
the protocol requires that implementors include provisions to limit
the frequency of triggered updates. After a triggered update is
sent, a timer should be set for a random time between 1 and 5
seconds. If other changes that would trigger updates occur before
the timer expires, a single update is triggered when the timer
expires, and the timer is then set to another random value between 1
and 5 seconds. Triggered updates may be suppressed if a regular
update is due by the time the triggered update would be sent.
Second, triggered updates do not need to include the entire routing
table. In principle, only those routes that have changed need to be
included. Thus messages generated as part of a triggered update must
include at least those routes that have their route change flag set.
They may include additional routes, or all routes, at the discretion
of the implementor; however, when full routing updates require
multiple packets, sending all routes is strongly discouraged. When a
triggered update is processed, messages should be generated for every
directly-connected network. Split horizon processing is done when
generating triggered updates as well as normal updates (see below).
If, after split horizon processing, a changed route will appear
identical on a network as it did previously, the route need not be
sent; if, as a result, no routes need be sent, the update may be
omitted on that network. (If a route had only a metric change, or
uses a new gateway that is on the same network as the old gateway,
the route will be sent to the network of the old gateway with a
metric of infinity both before and after the change.) Once all of
the triggered updates have been generated, the route change flags
should be cleared.
If input processing is allowed while output is being generated,
appropriate interlocking must be done. The route change flags should
not be changed as a result of processing input while a triggered
update message is being generated.
The only difference between a triggered update and other update
messages is the possible omission of routes that have not changed.
The rest of the mechanisms about to be described must all apply to
triggered updates.
Here is how a response datagram is generated for a particular
directly-connected network:
The IP source address must be the sending host's address on that
network. This is important because the source address is put into
routing tables in other hosts. If an incorrect source address is
used, other hosts may be unable to route datagrams. Sometimes
gateways are set up with multiple IP addresses on a single physical
interface. Normally, this means that several logical IP networks are
being carried over one physical medium. In such cases, a separate
update message must be sent for each address, with that address as
the IP source address.
Set the version number to the current version of RIP. (The version
described in this document is 1.) Set the command to response. Set
the bytes labeled "must be zero" to zero. Now start filling in
entries.
To fill in the entries, go down all the routes in the internal
routing table. Recall that the maximum datagram size is 512 bytes.
When there is no more space in the datagram, send the current message
and start a new one. If a triggered update is being generated, only
entries whose route change flags are set need be included.
See the description in Section 3.2 for a discussion of problems
raised by subnet and host routes. Routes to subnets will be
meaningless outside the network, and must be omitted if the
destination is not on the same subnetted network; they should be
replaced with a single route to the network of which the subnets are
a part. Similarly, routes to hosts must be eliminated if they are
subsumed by a network route, as described in the discussion in
Section 3.2.
If the route passes these tests, then the destination and metric are
put into the entry in the output datagram. Routes must be included
in the datagram even if their metrics are infinite. If the gateway
for the route is on the network for which the datagram is being
prepared, the metric in the entry is set to 16, or the entire entry
is omitted. Omitting the entry is simple split horizon. Including
an entry with metric 16 is split horizon with poisoned reverse. See
Section 2.2 for a more complete discussion of these alternatives.
3.6. Compatibility
The protocol described in this document is intended to interoperate
with routed and other existing implementations of RIP. However, a
different viewpoint is adopted about when to increment the metric
than was used in most previous implementations. Using the previous
perspective, the internal routing table has a metric of 0 for all
directly-connected networks. The cost (which is always 1) is added
to the metric when the route is sent in an update message. By
contrast, in this document directly-connected networks appear in the
internal routing table with metrics equal to their costs; the metrics
are not necessarily 1. In this document, the cost is added to the
metrics when routes are received in update messages. Metrics from
the routing table are sent in update messages without change (unless
modified by split horizon).
These two viewpoints result in identical update messages being sent.
Metrics in the routing table differ by a constant one in the two
descriptions. Thus, there is no difference in effect. The change
was made because the new description makes it easier to handle
situations where different metrics are used on directly-attached
networks.
Implementations that only support network costs of one need not
change to match the new style of presentation. However, they must
follow the description given in this document in all other ways.
4. Control functions
This section describes administrative controls. These are not part
of the protocol per se. However, experience with existing networks
suggests that they are important. Because they are not a necessary
part of the protocol, they are considered optional. However, we
strongly recommend that at least some of them be included in every
implementation.
These controls are intended primarily to allow RIP to be connected to
networks whose routing may be unstable or subject to errors. Here
are some examples:
It is sometimes desirable to limit the hosts and gateways from which
information will be accepted. On occasion, hosts have been
misconfigured in such a way that they begin sending inappropriate
information.
A number of sites limit the set of networks that they allow in update
messages. Organization A may have a connection to organization B
that they use for direct communication. For security or performance
reasons A may not be willing to give other organizations access to
that connection. In such cases, A should not include B's networks in
updates that A sends to third parties.
Here are some typical controls. Note, however, that the RIP protocol
does not require these or any other controls.
- a neighbor list - the network administrator should be able
to define a list of neighbors for each host. A host would
accept response messages only from hosts on its list of
neighbors.
- allowing or disallowing specific destinations - the network
administrator should be able to specify a list of
destination addresses to allow or disallow. The list would
be associated with a particular interface in the incoming
or outgoing direction. Only allowed networks would be
mentioned in response messages going out or processed in
response messages coming in. If a list of allowed
addresses is specified, all other addresses are disallowed.
If a list of disallowed addresses is specified, all other
addresses are allowed.
REFERENCES and BIBLIOGRAPHY
[1] Bellman, R. E., "Dynamic Programming", Princeton University
Press, Princeton, N.J., 1957.
[2] Bertsekas, D. P., and Gallaher, R. G., "Data Networks",
Prentice-Hall, Englewood Cliffs, N.J., 1987.
[3] Braden, R., and Postel, J., "Requirements for Internet Gateways",
USC/Information Sciences Institute, RFC-1009, June 1987.
[4] Boggs, D. R., Shoch, J. F., Taft, E. A., and Metcalfe, R. M.,
"Pup: An Internetwork Architecture", IEEE Transactions on
Communications, April 1980.
[5] Clark, D. D., "Fault Isolation and Recovery," MIT-LCS, RFC-816,
July 1982.
[6] Ford, L. R. Jr., and Fulkerson, D. R., "Flows in Networks",
Princeton University Press, Princeton, N.J., 1962.
[7] Xerox Corp., "Internet Transport Protocols", Xerox System
Integration Standard XSIS 028112, December 1981.