RFC 1716
Towards Requirements for IP Routers
5.3.5.1 Limited Broadcasts
Limited broadcasts MUST NOT be forwarded. Limited broadcasts
MUST NOT be discarded. Limited broadcasts MAY be sent and
SHOULD be sent instead of directed broadcasts where limited
broadcasts will suffice.
DISCUSSION:
Some routers contain UDP servers which function by resending
the requests (as unicasts or directed broadcasts) to other
servers. This requirement should not be interpreted as
prohibiting such servers. Note, however, that such servers
can easily cause packet looping if misconfigured. Thus,
providers of such servers would probably be well-advised to
document their setup carefully and to consider carefully the
TTL on packets which are sent.
5.3.5.2 Net-directed Broadcasts
A router MUST classify as net-directed broadcasts all valid,
directed broadcasts destined for a remote network or an
attached nonsubnetted network. A router MUST forward net-
directed broadcasts. Net-directed broadcasts MAY be sent.
A router MAY have an option to disable receiving net-directed
broadcasts on an interface and MUST have an option to disable
forwarding net-directed broadcasts. These options MUST default
to permit receiving and forwarding net-directed broadcasts.
DISCUSSION:
There has been some debate about forwarding or not
forwarding directed broadcasts. In this memo we have made
the forwarding decision depend on the router's knowledge of
the subnet mask for the destination network. Forwarding
decisions for subnetted networks should be made by routers
with an understanding of the subnet structure. Therefore,
in general, routers must forward directed broadcasts for
networks they are not attached to and for which they do not
understand the subnet structure. One router may interpret
and handle the same IP broadcast packet differently than
another, depending on its own understanding of the structure
of the destination (sub)network.
5.3.5.3 All-subnets-directed Broadcasts
A router MUST classify as all-subnets-directed broadcasts all
valid directed broadcasts destined for a directly attached
subnetted network which have all-ones in the subnet part of the
address. If the destination network is not subnetted, the
broadcast MUST be treated as a net-directed broadcast.
A router MUST forward an all-subnets-directed broadcast as a
link level broadcast out all physical interfaces connected to
the IP network addressed by the broadcast, except that:
o A router MUST NOT forward an all-subnet-directed broadcast
that was received by the router as a Link Layer broadcast,
unless the router is forwarding the broadcast in accordance
with [INTERNET:3] (see below).
o If a router receives an all-subnets-directed broadcast over
a network which does not indicate via Link Layer framing
whether the frame is a broadcast or a unicast, the packet
MUST NOT be forwarded to any network which likewise does not
indicate whether a frame is a broadcast.
o A router MUST NOT forward an all-subnets-directed broadcast
if the router is configured not to forward such broadcasts.
A router MUST have a configuration option to deny forwarding
of all-subnets-directed broadcasts. The configuration
option MUST default to permit forwarding of all-subnets-
directed broadcasts.
EDITOR'S COMMENTS:
The algorithm presented here is broken. The working group
explicitly desired this algorithm, knowing its failures.
The second bullet, above, prevents All Subnets Directed
Broadcasts from traversing more than one PPP (or other
serial) link in a row. Such a topology is easily conceived.
Suppose that some corporation builds its corporate backbone
out of PPP links, connecting routers at geographically
dispersed locations. Suppose that this corporation has 3
sites (S1, S2, and S3) and there is a router at each site
(R1, R2, and R3). At each site there are also several LANs
connected to the local router. Let there be a PPP link
connecting S1 to S2 and one connecting S2 to S3 (i.e. the
links are R1-R2 and R2-R3). So, if a host on a LAN at S1
sends a All Subnets Directed Broadcast, R1 will forward the
broadcast over the R1-R2 link to R2. R2 will forward the
broadcast to the LAN(s) connected to R2. Since the PPP does
not differentiate broadcast from non-broadcast frames, R2
will NOT forward the broadcast onto the R2-R3 link.
Therefore, the broadcast will not reach S3.
[INTERNET:3] describes an alternative set of rules for
forwarding of all-subnets-directed broadcasts (called multi-
subnet-broadcasts in that document). A router MAY IMPLEMENT
that alternative set of rules, but MUST use the set of rules
described above unless explicitly configured to use the
[INTERNET:3] rules. If routers will do [INTERNET:3]-style
forwarding, then the router MUST have a configuration option
which MUST default to doing the rules presented in this
document.
DISCUSSION:
As far as we know, the rules for multi-subnet broadcasts
described in [INTERNET:3] have never been implemented,
suggesting that either they are too complex or the utility
of multi-subnet broadcasts is low. The rules described in
this section match current practice. In the future, we
expect that IP multicast (see [INTERNET:4]) will be used to
better solve the sorts of problems that multi-subnets
broadcasts were intended to address.
We were also concerned that hosts whose system managers
neglected to configure with a subnet mask could
unintentionally send multi-subnet broadcasts.
A router SHOULD NOT originate all-subnets broadcasts, except as
required by Section [4.3.3.9] when sending ICMP Address Mask
Replies on subnetted networks.
DISCUSSION:
The current intention is to decree that (like 0-filled IP
broadcasts) the notion of the all-subnets broadcast is
obsolete. It should be treated as a directed broadcast to
the first subnet of the net in question that it appears on.
Routers may implement a switch (default off) which if turned
on enables the [INTERNET:3] behavior for all-subnets
broadcasts.
If a router has a configuration option to allow for
forwarding all-subnet broadcasts, it should use a spanning
tree, RPF, or other multicast forwarding algorithm (which
may be computed for other purposes such as bridging or OSPF)
to distribute the all-subnets broadcast efficiently. In
general, it is better to use an IP multicast address rather
than an all-subnets broadcast.
5.3.5.4 Subnet-directed Broadcasts
A router MUST classify as subnet-directed broadcasts all valid
directed broadcasts destined for a directly attached subnetted
network in which the subnet part is not all-ones. If the
destination network is not subnetted, the broadcast MUST be
treated as a net-directed broadcast.
A router MUST forward subnet-directed broadcasts.
A router MUST have a configuration option to prohibit
forwarding of subnet-directed broadcasts. Its default setting
MUST permit forwarding of subnet-directed broadcasts.
A router MAY have a configuration option to prohibit forwarding
of subnet-directed broadcasts from a source on a network on
which the router has an interface. If such an option is
provided, its default setting MUST permit forwarding of
subnet-directed broadcasts.
5.3.6 Congestion Control
Congestion in a network is loosely defined as a condition where
demand for resources (usually bandwidth or CPU time) exceeds
capacity. Congestion avoidance tries to prevent demand from
exceeding capacity, while congestion recovery tries to restore an
operative state. It is possible for a router to contribute to
both of these mechanisms. A great deal of effort has been spent
studying the problem. The reader is encouraged to read
[FORWARD:2] for a survey of the work. Important papers on the
subject include [FORWARD:3], [FORWARD:4], [FORWARD:5], and
[INTERNET:10], among others.
The amount of storage that router should have available to handle
peak instantaneous demand when hosts use reasonable congestion
policies, such as described in [FORWARD:5], is a function of the
product of the bandwidth of the link times the path delay of the
flows using the link, and therefore storage should increase as
this Bandwidth*Delay product increases. The exact function
relating storage capacity to probability of discard is not known.
When a router receives a packet beyond its storage capacity it
must (by definition, not by decree) discard it or some other
packet or packets. Which packet to discard is the subject of much
study but, unfortunately, little agreement so far.
A router MAY discard the packet it has just received; this is the
simplest but not the best policy. It is considered better policy
to randomly pick some transit packet on the queue and discard it
(see [FORWARD:2]). A router MAY use this Random Drop algorithm to
determine which packet to discard.
If a router implements a discard policy (such as Random Drop)
under which it chooses a packet to discard from among a pool of
eligible packets:
o If precedence-ordered queue service (described in Section
[5.3.3.1]) is implemented and enabled, the router MUST NOT
discard a packet whose IP precedence is higher than that of a
packet which is not discarded.
o A router MAY protect packets whose IP headers request the
maximize reliability TOS, except where doing so would be in
violation of the previous rule.
o A router MAY protect fragmented IP packets, on the theory that
dropping a fragment of a datagram may increase congestion by
causing all fragments of the datagram to be retransmitted by
the source.
o To help prevent routing perturbations or disruption of
management functions, the router MAY protect packets used for
routing control, link control, or network management from being
discarded. Dedicated routers (i.e.. routers which are not also
general purpose hosts, terminal servers, etc.) can achieve an
approximation of this rule by protecting packets whose source
or destination is the router itself.
Advanced methods of congestion control include a notion of
fairness, so that the 'user' that is penalized by losing a packet
is the one that contributed the most to the congestion. No matter
what mechanism is implemented to deal with bandwidth congestion
control, it is important that the CPU effort expended be
sufficiently small that the router is not driven into CPU
congestion also.
As described in Section [4.3.3.3], this document recommends that a
router should not send a Source Quench to the sender of the packet
that it is discarding. ICMP Source Quench is a very weak
mechanism, so it is not necessary for a router to send it, and
host software should not use it exclusively as an indicator of
congestion.
5.3.7 Martian Address Filtering
An IP source address is invalid if it is an IP broadcast address
or is not a class A, B, or C address.
An IP destination address is invalid if it is not a class A, B, C,
or D address.
A router SHOULD NOT forward any packet which has an invalid IP
source address or a source address on network 0. A router SHOULD
NOT forward, except over a loopback interface, any packet which
has a source address on network 127. A router MAY have a switch
which allows the network manager to disable these checks. If such
a switch is provided, it MUST default to performing the checks.
A router SHOULD NOT forward any packet which has an invalid IP
destination address or a destination address on network 0. A
router SHOULD NOT forward, except over a loopback interface, any
packet which has a destination address on network 127. A router
MAY have a switch which allows the network manager to disable
these checks. If such a switch is provided, it MUST default to
performing the checks.
If a router discards a packet because of these rules, it SHOULD
log at least the IP source address, the IP destination address,
and, if the problem was with the source address, the physical
interface on which the packet was received and the Link Layer
address of the host or router from which the packet was received.
5.3.8 Source Address Validation
A router SHOULD IMPLEMENT the ability to filter traffic based on a
comparison of the source address of a packet and the forwarding
table for a logical interface on which the packet was received.
If this filtering is enabled, the router MUST silently discard a
packet if the interface on which the packet was received is not
the interface on which a packet would be forwarded to reach the
address contained in the source address. In simpler terms, if a
router wouldn't route a packet containing this address through a
particular interface, it shouldn't believe the address if it
appears as a source address in a packet read from this interface.
If this feature is implemented, it MUST be disabled by default.
DISCUSSION:
This feature can provide useful security improvements in some
situations, but can erroneously discard valid packets in
situations where paths are asymmetric.
5.3.9 Packet Filtering and Access Lists
As a means of providing security and/or limiting traffic through
portions of a network a router SHOULD provide the ability to
selectively forward (or filter) packets. If this capability is
provided, filtering of packets MUST be configurable either to
forward all packets or to selectively forward them based upon the
source and destination addresses. Each source and destination
address SHOULD allow specification of an arbitrary mask.
If supported, a router MUST be configurable to allow one of an
o Include list - specification of a list of address pairs to be
forwarded, or an
o Exclude list - specification of a list of address pairs NOT to
be forwarded.
A router MAY provide a configuration switch which allows a choice
between specifying an include or an exclude list.
A value matching any address (e.g. a keyword any or an address
with a mask of all 0's) MUST be allowed as a source and/or
destination address.
In addition to address pairs, the router MAY allow any combination
of transport and/or application protocol and source and
destination ports to be specified.
The router MUST allow packets to be silently discarded (i.e..
discarded without an ICMP error message being sent).
The router SHOULD allow an appropriate ICMP unreachable message to
be sent when a packet is discarded. The ICMP message SHOULD
specify Communication Administratively Prohibited (code 13) as the
reason for the destination being unreachable.
The router SHOULD allow the sending of ICMP destination
unreachable messages (code 13) to be configured for each
combination of address pairs, protocol types, and ports it allows
to be specified.
The router SHOULD count and SHOULD allow selective logging of
packets not forwarded.
5.3.10 Multicast Routing
An IP router SHOULD support forwarding of IP multicast packets,
based either on static multicast routes or on routes dynamically
determined by a multicast routing protocol (e.g., DVMRP
[ROUTE:9]). A router that forwards IP multicast packets is called
a multicast router.
5.3.11 Controls on Forwarding
For each physical interface, a router SHOULD have a configuration
option which specifies whether forwarding is enabled on that
interface. When forwarding on an interface is disabled, the
router:
o MUST silently discard any packets which are received on that
interface but are not addressed to the router
o MUST NOT send packets out that interface, except for datagrams
originated by the router
o MUST NOT announce via any routing protocols the availability of
paths through the interface
DISCUSSION:
This feature allows the network manager to essentially turn off
an interface but leaves it accessible for network management.
Ideally, this control would apply to logical rather than
physical interfaces, but cannot because there is no known way
for a router to determine which logical interface a packet
arrived on when there is not a one-to-one correspondence
between logical and physical interfaces.
5.3.12 State Changes
During the course of router operation, interfaces may fail or be
manually disabled, or may become available for use by the router.
Similarly, forwarding may be disabled for a particular interface
or for the entire router or may be (re)enabled. While such
transitions are (usually) uncommon, it is important that routers
handle them correctly.
5.3.12.1 When a Router Ceases Forwarding
When a router ceases forwarding it MUST stop advertising all
routes, except for third party routes. It MAY continue to
receive and use routes from other routers in its routing
domains. If the forwarding database is retained, the router
MUST NOT cease timing the routes in the forwarding database.
If routes that have been received from other routers are
remembered, the router MUST NOT cease timing the routes which
it has remembered. It MUST discard any routes whose timers
expire while forwarding is disabled, just as it would do if
forwarding were enabled.
DISCUSSION:
When a router ceases forwarding, it essentially ceases being
a router. It is still a host, and must follow all of the
requirements of Host Requirements [INTRO: 2]. The router
may still be a passive member of one or more routing
domains, however. As such, it is allowed to maintain its
forwarding database by listening to other routers in its
routing domain. It may not, however, advertise any of the
routes in its forwarding database, since it itself is doing
no forwarding. The only exception to this rule is when the
router is advertising a route which uses only some other
router, but which this router has been asked to advertise.
A router MAY send ICMP destination unreachable (host
unreachable) messages to the senders of packets that it is
unable to forward. It SHOULD NOT send ICMP redirect messages.
DISCUSSION:
Note that sending an ICMP destination unreachable (host
unreachable) is a router action. This message should not be
sent by hosts. This exception to the rules for hosts is
allowed so that packets may be rerouted in the shortest
possible time, and so that black holes are avoided.
5.3.12.2 When a Router Starts Forwarding
When a router begins forwarding, it SHOULD expedite the sending
of new routing information to all routers with which it
normally exchanges routing information.
5.3.12.3 When an Interface Fails or is Disabled
If an interface fails or is disabled a router MUST remove and
stop advertising all routes in its forwarding database which
make use of that interface. It MUST disable all static routes
which make use of that interface. If other routes to the same
destination and TOS are learned or remembered by the router,
the router MUST choose the best alternate, and add it to its
forwarding database. The router SHOULD send ICMP destination
unreachable or ICMP redirect messages, as appropriate, in reply
to all packets which it is unable to forward due to the
interface being unavailable.
5.3.12.4 When an Interface is Enabled
If an interface which had not been available becomes available,
a router MUST reenable any static routes which use that
interface. If routes which would use that interface are
learned by the router, then these routes MUST be evaluated
along with all of the other learned routes, and the router MUST
make a decision as to which routes should be placed in the
forwarding database. The implementor is referred to Chapter
[7], Application Layer - Routing Protocols for further
information on how this decision is made.
A router SHOULD expedite the sending of new routing information
to all routers with which it normally exchanges routing
information.
5.3.13 IP Options
Several options, such as Record Route and Timestamp, contain slots
into which a router inserts its address when forwarding the
packet. However, each such option has a finite number of slots,
and therefore a router may find that there is not free slot into
which it can insert its address. No requirement listed below
should be construed as requiring a router to insert its address
into an option that has no remaining slot to insert it into.
Section [5.2.5] discusses how a router must choose which of its
addresses to insert into an option.
5.3.13.1 Unrecognized Options
Unrecognized IP options in forwarded packets MUST be passed
through unchanged.
5.3.13.2 Security Option
Some environments require the Security option in every packet;
such a requirement is outside the scope of this document and
the IP standard specification. Note, however, that the
security options described in [INTERNET:1] and [INTERNET:16]
are obsolete. Routers SHOULD IMPLEMENT the revised security
option described in [INTERNET:5].
5.3.13.3 Stream Identifier Option
This option is obsolete. If the Stream Identifier option is
present in a packet forwarded by the router, the option MUST be
ignored and passed through unchanged.
5.3.13.4 Source Route Options
A router MUST implement support for source route options in
forwarded packets. A router MAY implement a configuration
option which, when enabled, causes all source-routed packets to
be discarded. However, such an option MUST NOT be enabled by
default.
DISCUSSION:
The ability to source route datagrams through the Internet
is important to various network diagnostic tools. However,
in a few rare cases, source routing may be used to bypass
administrative and security controls within a network.
Specifically, those cases where manipulation of routing
tables is used to provide administrative separation in lieu
of other methods such as packet filtering may be vulnerable
through source routed packets.
5.3.13.5 Record Route Option
Routers MUST support the Record Route option in forwarded
packets.
A router MAY provide a configuration option which, if enabled,
will cause the router to ignore (i.e. pass through unchanged)
Record Route options in forwarded packets. If provided, such
an option MUST default to enabling the record-route. This
option does not affect the processing of Record Route options
in datagrams received by the router itself (in particular,
Record Route options in ICMP echo requests will still be
processed in accordance with Section [4.3.3.6]).
DISCUSSION:
There are some people who believe that Record Route is a
security problem because it discloses information about the
topology of the network. Thus, this document allows it to
be disabled.
5.3.13.6 Timestamp Option
Routers MUST support the timestamp option in forwarded packets.
A timestamp value MUST follow the rules given in Section
[3.2.2.8] of [INTRO:2].
If the flags field = 3 (timestamp and prespecified address),
the router MUST add its timestamp if the next prespecified
address matches any of the router's IP addresses. It is not
necessary that the prespecified address be either the address
of the interface on which the packet arrived or the address of
the interface over which it will be sent.
IMPLEMENTATION:
To maximize the utility of the timestamps contained in the
timestamp option, it is suggested that the timestamp
inserted be, as nearly as practical, the time at which the
packet arrived at the router. For datagrams originated by
the router, the timestamp inserted should be, as nearly as
practical, the time at which the datagram was passed to the
network layer for transmission.
A router MAY provide a configuration option which, if enabled,
will cause the router to ignore (i.e. pass through unchanged)
Timestamp options in forwarded datagrams when the flag word is
set to zero (timestamps only) or one (timestamp and registering
IP address). If provided, such an option MUST default to off
(that is, the router does not ignore the timestamp). This
option does not affect the processing of Timestamp options in
datagrams received by the router itself (in particular, a
router will insert timestamps into Timestamp options in
datagrams received by the router, and Timestamp options in ICMP
echo requests will still be processed in accordance with
Section [4.3.3.6]).
DISCUSSION:
Like the Record Route option, the Timestamp option can
reveal information about a network's topology. Some people
consider this to be a security concern.
6. TRANSPORT LAYER
A router is not required to implement any Transport Layer protocols
except those required to support Application Layer protocols supported
by the router. In practice, this means that most routers implement both
the Transmission Control Protocol (TCP) and the User Datagram Protocol
(UDP).
6.1 USER DATAGRAM PROTOCOL - UDP
The User Datagram Protocol (UDP) is specified in [TRANS:1].
A router which implements UDP MUST be compliant, and SHOULD be
unconditionally compliant, with the requirements of section 4.1.3 of
[INTRO:2], except that:
o This specification does not specify the interfaces between the
various protocol layers. Thus, a router need not comply with
sections 4.1.3.2, 4.1.3.3, and 4.1.3.5 of [INTRO:2] (except of
course where compliance is required for proper functioning of
Application Layer protocols supported by the router).
o Contrary to section 4.1.3.4 of [INTRO:2], an application MUST NOT
be able to disable to generation of UDP checksums.
DISCUSSION:
Although a particular application protocol may require that UDP
datagrams it receives must contain a UDP checksum, there is no
general requirement that received UDP datagrams contain UDP
checksums. Of course, if a UDP checksum is present in a received
datagram, the checksum must be verified and the datagram discarded
if the checksum is incorrect.
6.2 TRANSMISSION CONTROL PROTOCOL - TCP
The Transmission Control Protocol (TCP) is specified in [TRANS:2].
A router which implements TCP MUST be compliant, and SHOULD be
unconditionally compliant, with the requirements of section 4.2 of
[INTRO:2], except that:
o This specification does not specify the interfaces between the
various protocol layers. Thus, a router need not comply with the
following requirements of [INTRO:2] (except of course where
compliance is required for proper functioning of Application Layer
protocols supported by the router):
Section 4.2.2.2:
Passing a received PSH flag to the application layer is now
OPTIONAL.
Section 4.2.2.4:
A TCP MUST inform the application layer asynchronously
whenever it receives an Urgent pointer and there was
previously no pending urgent data, or whenever the Urgent
pointer advances in the data stream. There MUST be a way for
the application to learn how much urgent data remains to be
read from the connection, or at least to determine whether or
not more urgent data remains to be read.
Section 4.2.3.5:
An application MUST be able to set the value for R2 for a
particular connection. For example, an interactive
application might set R2 to ``infinity,'' giving the user
control over when to disconnect.
Section 4.2.3.7:
If an application on a multihomed host does not specify the
local IP address when actively opening a TCP connection, then
the TCP MUST ask the IP layer to select a local IP address
before sending the (first) SYN. See the function
GET_SRCADDR() in Section 3.4.
Section 4.2.3.8:
An application MUST be able to specify a source route when it
actively opens a TCP connection, and this MUST take
precedence over a source route received in a datagram.
o For similar reasons, a router need not comply with any of the
requirements of section 4.2.4 of [INTRO:2].
o The requirements of section 4.2.2.6 of [INTRO:2] are amended as
follows: a router which implements the host portion of MTU
discovery (discussed in Section [4.2.3.3] of this memo) uses 536
as the default value of SendMSS only if the path MTU is unknown;
if the path MTU is known, the default value for SendMSS is the
path MTU - 40.
o The requirements of section 4.2.2.6 of [INTRO:2] are amended as
follows: ICMP Destination Unreachable codes 11 and 12 are
additional soft error conditions. Therefore, these message MUST
NOT cause TCP to abort a connection.
DISCUSSION:
It should particularly be noted that a TCP implementation in a
router must conform to the following requirements of [INTRO:2]:
o Providing a configurable TTL. [4.2.2.1]
o Providing an interface to configure keep-alive behavior, if
keep-alives are used at all. [4.2.3.6]
o Providing an error reporting mechanism, and the ability to
manage it. [4.2.4.1]
o Specifying type of service. [4.2.4.2]
The general paradigm applied is that if a particular interface is
visible outside the router, then all requirements for the
interface must be followed. For example, if a router provides a
telnet function, then it will be generating traffic, likely to be
routed in the external networks. Therefore, it must be able to
set the type of service correctly or else the telnet traffic may
not get through.
7. APPLICATION LAYER - ROUTING PROTOCOLS
7.1 INTRODUCTION
An Autonomous System (AS) is defined as a set of routers all
belonging under the same authority and all subject to a consistent
set of routing policies. Interior gateway protocols (IGPs) are used
to distribute routing information inside of an AS (i.e. intra-AS
routing). Exterior gateway protocols are used to exchange routing
information between ASs (i.e. inter-AS routing).
7.1.1 Routing Security Considerations
Routing is one of the few places where the Robustness Principle
(be liberal in what you accept) does not apply. Routers should be
relatively suspicious in accepting routing data from other routing
systems.
A router SHOULD provide the ability to rank routing information
sources from most trustworthy to least trustworthy and to accept
routing information about any particular destination from the most
trustworthy sources first. This was implicit in the original
core/stub autonomous system routing model using EGP and various
interior routing protocols. It is even more important with the
demise of a central, trusted core.
A router SHOULD provide a mechanism to filter out obviously
invalid routes (such as those for net 127).
Routers MUST NOT by default redistribute routing data they do not
themselves use, trust or otherwise consider invalid. In rare
cases, it may be necessary to redistribute suspicious information,
but this should only happen under direct intercession by some
human agency.
In general, routers must be at least a little paranoid about
accepting routing data from anyone, and must be especially careful
when they distribute routing information provided to them by
another party. See below for specific guidelines.
Routers SHOULD IMPLEMENT peer-to-peer authentication for those
routing protocols that support them.
7.1.2 Precedence
Except where the specification for a particular routing protocol
specifies otherwise, a router SHOULD set the IP Precedence value
for IP datagrams carrying routing traffic it originates to 6
(INTERNETWORK CONTROL).
DISCUSSION:
Routing traffic with VERY FEW exceptions should be the highest
precedence traffic on any network. If a system's routing
traffic can't get through, chances are nothing else will.
7.2 INTERIOR GATEWAY PROTOCOLS
7.2.1 INTRODUCTION
An Interior Gateway Protocol (IGP) is used to distribute routing
information between the various routers in a particular AS.
Independent of the algorithm used to implement a particular IGP,
it should perform the following functions:
(1) Respond quickly to changes in the internal topology of an AS
(2) Provide a mechanism such that circuit flapping does not cause
continuous routing updates
(3) Provide quick convergence to loop-free routing
(4) Utilize minimal bandwidth
(5) Provide equal cost routes to enable load-splitting
(6) Provide a means for authentication of routing updates
Current IGPs used in the internet today are characterized as
either being being based on a distance-vector or a link-state
algorithm.
Several IGPs are detailed in this section, including those most
commonly used and some recently developed protocols which may be
widely used in the future. Numerous other protocols intended for
use in intra-AS routing exist in the Internet community.
A router which implements any routing protocol (other than static
routes) MUST IMPLEMENT OSPF (see Section [7.2.2]) and MUST
IMPLEMENT RIP (see Section [7.2.4]). A router MAY implement
additional IGPs.
7.2.2 OPEN SHORTEST PATH FIRST - OSPF
7.2.2.1 Introduction
Shortest Path First (SPF) based routing protocols are a class
of link-state algorithms which are based on the shortest-path
algorithm of Dijkstra. Although SPF based algorithms have been
around since the inception of the ARPANet, it is only recently
that they have achieved popularity both inside both the IP and
the OSI communities. In an SPF based system, each router
obtains an exact replica of the entire topology database via a
process known as flooding. Flooding insures a reliable
transfer of the information. Each individual router then runs
the SPF algorithm on its database to build the IP routing
table. The OSPF routing protocol is an implementation of an
SPF algorithm. The current version, OSPF version 2, is
specified in [ROUTE:1]. Note that RFC-1131, which describes
OSPF version 1, is obsolete.
Note that to comply with Section [8.3] of this memo, a router
which implements OSPF MUST implement the OSPF MIB [MGT:14].
7.2.2.2 Specific Issues
Virtual Links
There is a minor error in the specification that can cause
routing loops when all of the following conditions are
simultaneously true:
(1) A virtual link is configured through a transit area,
(2) Two separate paths exist, each having the same
endpoints, but one utilizing only non-virtual
backbone links, and the other using links in the
transit area, and
(3) The latter path is part of the (underlying physical
representation of the) configured virtual link,
routing loops may occur.
To prevent this, an implementation of OSPF SHOULD invoke
the calculation in Section 16.3 of [ROUTE:1] whenever any
part of the path to the destination is a virtual link (the
specification only says this is necessary when the first
hop is a virtual link).
7.2.2.3 New Version of OSPF
As of this writing (4/4/94) there is a new version of the OSPF
specification that is winding its way through the Internet
standardization process. A prudent implementor will be aware
of this and develop an implementation accordingly.
The new version fixes several errors in the current
specification [ROUTE:1]. For this reason, implementors and
vendors ought to expect to upgrade to the new version
relatively soon. In particular, the following problems exist
in [ROUTE:1] that the new version fixes:
o In [ROUTE:1], certain configurations of virtual links can
lead to incorrect routing and/or routing loops. A fix for
this is specified in the new specification.
o In [ROUTE:1], OSPF external routes to For example, a router
cannot import into an OSPF domain external routes both for
192.2.0.0, 255.255.0.0 and 192.2.0.0, 255.255.255.0. Routes
such as these may become common with the deployment of CIDR
[INTERNET:15]. This has been addressed in the new OSPF
specification.
o In [ROUTE:1], OSPF Network-LSAs originated before a router
changes its OSPF Router ID can confuse the Dijkstra
calculation if the router again becomes Designated Router
for the network. This has been fixed.
7.2.3 INTERMEDIATE SYSTEM TO INTERMEDIATE SYSTEM - DUAL IS-IS
The American National Standards Institute (ANSI) X3S3.3 committee
has defined an intra-domain routing protocol. This protocol is
titled Intermediate System to Intermediate System Routeing
Exchange Protocol.
Its application to an IP network has been defined in [ROUTE:2],
and is referred to as Dual IS-IS (or sometimes as Integrated IS-
IS). IS-IS is based on a link-state (SPF) routing algorithm and
shares all the advantages for this class of protocols.
7.2.4 ROUTING INFORMATION PROTOCOL - RIP
7.2.4.1 Introduction
RIP is specified in [ROUTE:3]. Although RIP is still quite
important in the Internet, it is being replaced in
sophisticated applications by more modern IGPs such as the ones
described above.
Another common use for RIP is as a router discovery protocol.
Section [4.3.3.10] briefly touches upon this subject.
7.2.4.2 Protocol Walk-Through
Dealing with changes in topology: [ROUTE:3], pp. 11
An implementation of RIP MUST provide a means for timing
out routes. Since messages are occasionally lost,
implementations MUST NOT invalidate a route based on a
single missed update.
Implementations MUST by default wait six times the update
interval before invalidating a route. A router MAY have
configuration options to alter this value.
DISCUSSION:
It is important to routing stability that all routers
in a RIP autonomous system use similar timeout value
for invalidating routes, and therefore it is important
that an implementation default to the timeout value
specified in the RIP specification. However, that
timeout value is overly conservative in environments
where packet loss is reasonably rare. In such an
environment, a network manager may wish to be able to
decrease the timeout period in order to promote faster
recovery from failures.
IMPLEMENTATION:
There is a very simple mechanism which a router may use
to meet the requirement to invalidate routes promptly
after they time out. Whenever the router scans the
routing table to see if any routes have timed out, it
also notes the age of the least recently updated route
which has not yet timed out. Subtracting this age from
the timeout period gives the amount of time until the
router again needs to scan the table for timed out
routes.
Split Horizon: [ROUTE:3], pp. 14-15
An implementation of RIP MUST implement split horizon, a
scheme used for avoiding problems caused by including
routes in updates sent to the router from which they were
learned.
An implementation of RIP SHOULD implement Split horizon
with poisoned reverse, a variant of split horizon which
includes routes learned from a router sent to that router,
but sets their metric to infinity. Because of the routing
overhead which may be incurred by implementing split
horizon with poisoned reverse, implementations MAY include
an option to select whether poisoned reverse is in effect.
An implementation SHOULD limit the period of time in which
it sends reverse routes at an infinite metric.
IMPLEMENTATION:
Each of the following algorithms can be used to limit
the period of time for which poisoned reverse is
applied to a route. The first algorithm is more
complex but does a more complete job of limiting
poisoned reverse to only those cases where it is
necessary.
The goal of both algorithms is to ensure that poison
reverse is done for any destination whose route has
changed in the last Route Lifetime (typically 180
seconds), unless it can be sure that the previous route
used the same output interface. The Route Lifetime is
used because that is the amount of time RIP will keep
around an old route before declaring it stale.
The time intervals (and derived variables) used in the
following algorithms are as follows:
Tu The Update Timer; the number of seconds between
RIP updates. This typically defaults to 30
seconds.
Rl The Route Lifetime, in seconds. This is the
amount of time that a route is presumed to be
good, without requiring an update. This typically
defaults to 180 seconds.
Ul The Update Loss; the number of consecutive updates
that have to be lost or fail to mention a route
before RIP deletes the route. Ul is calculated to
be (Rl/Tu)+1. The +1 is to account for the fact
that the first time the ifcounter is decremented
will be less than Tu seconds after it is
initialized. Typically, Ul will be 7: (180/30)+1.
In The value to set ifcounter to when a destination
is newly learned. This value is Ul-4, where the 4
is RIP's garbage collection timer/30
The first algorithm is:
- Associated with each destination is a counter, called
the ifcounter below. Poison reverse is done for any
route whose destination's ifcounter is greater than
zero.
- After a regular (not triggered or in response to a
request) update is sent, all of the non-zero
ifcounters are decremented by one.
- When a route to a destination is created, its
ifcounter is set as follows:
- If the new route is superseding a valid route, and
the old route used a different (logical) output
interface, then the ifcounter is set to Ul.
- If the new route is superseding a stale route, and
the old route used a different (logical) output
interface, then the ifcounter is set to MAX(0, Ul
- INT(seconds that the route has been stale/Ut).
- If there was no previous route to the destination,
the ifcounter is set to In.
- Otherwise, the ifcounter is set to zero
- RIP also maintains a timer, called the resettimer
below. Poison reverse is done on all routes
whenever resettimer has not expired (regardless of
the ifcounter values).
- When RIP is started, restarted, reset, or otherwise
has its routing table cleared, it sets the
resettimer to go off in Rl seconds.
The second algorithm is identical to the first except
that:
- The rules which set the ifcounter to non-zero values
are changed to always set it to Rl/Tu, and
- The resettimer is eliminated.
Triggered updates: [ROUTE:3], pp. 15-16; pp. 29
Triggered updates (also called flash updates) are a
mechanism for immediately notifying a router's
neighbors when the router adds or deletes routes or
changes their metrics. A router MUST send a triggered
update when routes are deleted or their metrics are
increased. A router MAY send a triggered update when
routes are added or their metrics decreased.
Since triggered updates can cause excessive routing
overhead, implementations MUST use the following
mechanism to limit the frequency of triggered updates:
(1) When a router sends a triggered update, it sets a
timer to a random time between one and five
seconds in the future. The router must not
generate additional triggered updates before this
timer expires.
(2) If the router would generate a triggered update
during this interval it sets a flag indicating
that a triggered update is desired. The router
also logs the desired triggered update.
(3) When the triggered update timer expires, the
router checks the triggered update flag. If the
flag is set then the router sends a single
triggered update which includes all of the changes
that were logged. The router then clears the flag
and, since a triggered update was sent, restarts
this algorithm.
(4) The flag is also cleared whenever a regular update
is sent.
Triggered updates SHOULD include all routes that have
changed since the most recent regular (non-triggered)
update. Triggered updates MUST NOT include routes that
have not changed since the most recent regular update.
DISCUSSION:
Sending all routes, whether they have changed
recently or not, is unacceptable in triggered
updates because the tremendous size of many Internet
routing tables could otherwise result in
considerable bandwidth being wasted on triggered
updates.
Use of UDP: [ROUTE:3], pp. 18-19.
RIP packets sent to an IP broadcast address SHOULD have
their initial TTL set to one.
Note that to comply with Section [6.1] of this memo, a
router MUST use UDP checksums in RIP packets which it
originates, MUST discard RIP packets received with
invalid UDP checksums, but MUST not discard received
RIP packets simply because they do not contain UDP
checksums.
Addressing Considerations: [ROUTE:3], pp. 22
A RIP implementation SHOULD support host routes. If it
does not, it MUST (as described on page 27 of
[ROUTE:3]) ignore host routes in received updates. A
router MAY log ignored hosts routes.
The special address 0.0.0.0 is used to describe a
default route. A default route is used as the route of
last resort (i.e. when a route to the specific net does
not exist in the routing table). The router MUST be
able to create a RIP entry for the address 0.0.0.0.
Input Processing - Response: [ROUTE:3], pp. 26
When processing an update, the following validity
checks MUST be performed:
o The response MUST be from UDP port 520.
o The source address MUST be on a directly connected
subnet (or on a directly connected, non-subnetted
network) to be considered valid.
o The source address MUST NOT be one of the router's
addresses.
DISCUSSION:
Some networks, media, and interfaces allow a
sending node to receive packets that it
broadcasts. A router must not accept its own
packets as valid routing updates and process
them. The last requirement prevents a router
from accepting its own routing updates and
processing them (on the assumption that they were
sent by some other router on the network).
An implementation MUST NOT replace an existing route if
the metric received is equal to the existing metric
except in accordance with the following heuristic.
An implementation MAY choose to implement the following
heuristic to deal with the above situation. Normally,
it is useless to change the route to a network from one
router to another if both are advertised at the same
metric. However, the route being advertised by one of
the routers may be in the process of timing out.
Instead of waiting for the route to timeout, the new
route can be used after a specified amount of time has
elapsed. If this heuristic is implemented, it MUST wait
at least halfway to the expiration point before the new
route is installed.
7.2.4.3 Specific Issues
RIP Shutdown
An implementation of RIP SHOULD provide for a graceful
shutdown using the following steps:
(1) Input processing is terminated,
(2) Four updates are generated at random intervals of
between two and four seconds, These updates contain
all routes that were previously announced, but with
some metric changes. Routes that were being
announced at a metric of infinity should continue to
use this metric. Routes that had been announced with
a non-infinite metric should be announced with a
metric of 15 (infinity - 1).
DISCUSSION:
The metric used for the above really ought to be
16 (infinity); setting it to 15 is a kludge to
avoid breaking certain old hosts which wiretap the
RIP protocol. Such a host will (erroneously)
abort a TCP connection if it tries to send a
datagram on the connection while the host has no
route to the destination (even if the period when
the host has no route lasts only a few seconds
while RIP chooses an alternate path to the
destination).
RIP Split Horizon and Static Routes
Split horizon SHOULD be applied to static routes by
default. An implementation SHOULD provide a way to
specify, per static route, that split horizon should not
be applied to this route.
7.2.5 GATEWAY TO GATEWAY PROTOCOL - GGP
The Gateway to Gateway protocol is considered obsolete and SHOULD
NOT be implemented.
7.3 EXTERIOR GATEWAY PROTOCOLS
7.3.1 INTRODUCTION
Exterior Gateway Protocols are utilized for inter-Autonomous
System routing to exchange reachability information for a set of
networks internal to a particular autonomous system to a
neighboring autonomous system.
The area of inter-AS routing is a current topic of research inside
the Internet Engineering Task Force. The Exterior Gateway
Protocol (EGP) described in Section [7.3.3] has traditionally been
the inter-AS protocol of choice. The Border Gateway Protocol
(BGP) eliminates many of the restrictions and limitations of EGP,
and is therefore growing rapidly in popularity. A router is not
required to implement any inter-AS routing protocol. However, if
a router does implement EGP it also MUST IMPLEMENT BGP.
Although it was not designed as an exterior gateway protocol, RIP
(described in Section [7.2.4]) is sometimes used for inter-AS
routing.
7.3.2 BORDER GATEWAY PROTOCOL - BGP
7.3.2.1 Introduction
The Border Gateway Protocol (BGP) is an inter-AS routing
protocol which exchanges network reachability information with
other BGP speakers. The information for a network includes the
complete list of ASs that traffic must transit to reach that
network. This information can then be used to insure loop-free
paths. This information is sufficient to construct a graph of
AS connectivity from which routing loops may be pruned and some
policy decisions at the AS level may be enforced.
BGP is defined by [ROUTE:4]. [ROUTE:5] specifies the proper
usage of BGP in the Internet, and provides some useful
implementation hints and guidelines. [ROUTE:12] and [ROUTE:13]
provide additional useful information.
To comply with Section [8.3] of this memo, a router which
implements BGP MUST also implement the BGP MIB [MGT:15].
To characterize the set of policy decisions that can be
enforced using BGP, one must focus on the rule that an AS
advertises to its neighbor ASs only those routes that it itself
uses. This rule reflects the hop-by-hop routing paradigm
generally used throughout the current Internet. Note that some
policies cannot be supported by the hop-by-hop routing paradigm
and thus require techniques such as source routing to enforce.
For example, BGP does not enable one AS to send traffic to a
neighbor AS intending that that traffic take a different route
from that taken by traffic originating in the neighbor AS. On
the other hand, BGP can support any policy conforming to the
hop-by-hop routing paradigm.
Implementors of BGP are strongly encouraged to follow the
recommendations outlined in Section 6 of [ROUTE:5].
7.3.2.2 Protocol Walk-through
While BGP provides support for quite complex routing policies
(as an example see Section 4.2 in [ROUTE:5]), it is not
required for all BGP implementors to support such policies. At
a minimum, however, a BGP implementation:
(1) SHOULD allow an AS to control announcements of the BGP
learned routes to adjacent AS's. Implementations SHOULD
support such control with at least the granularity of a
single network. Implementations SHOULD also support such
control with the granularity of an autonomous system,
where the autonomous system may be either the autonomous
system that originated the route, or the autonomous system
that advertised the route to the local system (adjacent
autonomous system).
(2) SHOULD allow an AS to prefer a particular path to a
destination (when more than one path is available). Such
function SHOULD be implemented by allowing system
administrator to assign weights to Autonomous Systems, and
making route selection process to select a route with the
lowest weight (where weight of a route is defined as a sum
of weights of all AS's in the AS_PATH path attribute
associated with that route).
(3) SHOULD allow an AS to ignore routes with certain AS's in
the AS_PATH path attribute. Such function can be
implemented by using technique outlined in (2), and by
assigning infinity as weights for such AS's. The route
selection process must ignore routes that have weight
equal to infinity.
7.3.3 EXTERIOR GATEWAY PROTOCOL - EGP
7.3.3.1 Introduction
The Exterior Gateway Protocol (EGP) specifies an EGP which is
used to exchange reachability information between routers of
the same or differing autonomous systems. EGP is not considered
a routing protocol since there is no standard interpretation
(i.e. metric) for the distance fields in the EGP update
message, so distances are comparable only among routers of the
same AS. It is however designed to provide high-quality
reachability information, both about neighbor routers and about
routes to non-neighbor routers.
EGP is defined by [ROUTE:6]. An implementor almost certainly
wants to read [ROUTE:7] and [ROUTE:8] as well, for they contain
useful explanations and background material.
DISCUSSION:
The present EGP specification has serious limitations, most
importantly a restriction which limits routers to
advertising only those networks which are reachable from
within the router's autonomous system. This restriction
against propagating third party EGP information is to
prevent long-lived routing loops. This effectively limits
EGP to a two-level hierarchy.
RFC-975 is not a part of the EGP specification, and should
be ignored.
7.3.3.2 Protocol Walk-through
Indirect Neighbors: RFC-888, pp. 26
An implementation of EGP MUST include indirect neighbor
support.
Polling Intervals: RFC-904, pp. 10
The interval between Hello command retransmissions and the
interval between Poll retransmissions SHOULD be configurable
but there MUST be a minimum value defined.
The interval at which an implementation will respond to
Hello commands and Poll commands SHOULD be configurable but
there MUST be a minimum value defined.
Network Reachability: RFC-904, pp. 15
An implementation MUST default to not providing the external
list of routers in other autonomous systems; only the
internal list of routers together with the nets which are
reachable via those routers should be included in an Update
Response/Indication packet. However, an implementation MAY
elect to provide a configuration option enabling the
external list to be provided. An implementation MUST NOT
include in the external list routers which were learned via
the external list provided by a router in another autonomous
system. An implementation MUST NOT send a network back to
the autonomous system from which it is learned, i.e. it MUST
do split-horizon on an autonomous system level.
If more than 255 internal or 255 external routers need to be
specified in a Network Reachability update, the networks
reachable from routers that can not be listed MUST be merged
into the list for one of the listed routers. Which of the
listed routers is chosen for this purpose SHOULD be user
configurable, but SHOULD default to the source address of
the EGP update being generated.
An EGP update contains a series of blocks of network
numbers, where each block contains a list of network numbers
reachable at a particular distance via a particular router.
If more than 255 networks are reachable at a particular
distance via a particular router, they are split into
multiple blocks (all of which have the same distance).
Similarly, if more than 255 blocks are required to list the
networks reachable via a particular router, the router's
address is listed as many times as necessary to include all
of the blocks in the update.
Unsolicited Updates: RFC-904, pp. 16
If a network is shared with the peer, an implementation MUST
send an unsolicited update upon entry to the Up state
assuming that the source network is the shared network.
Neighbor Reachability: RFC-904, pp. 6, 13-15
The table on page 6 which describes the values of j and k
(the neighbor up and down thresholds) is incorrect. It is
reproduced correctly here:
Name Active Passive Description
-----------------------------------------------
j 3 1 neighbor-up threshold
k 1 0 neighbor-down threshold
The value for k in passive mode also specified incorrectly
in RFC-904, pp. 14 The values in parenthesis should read:
(j = 1, k = 0, and T3/T1 = 4)
As an optimization, an implementation can refrain from
sending a Hello command when a Poll is due. If an
implementation does so, it SHOULD provide a user
configurable option to disable this optimization.
Abort timer: RFC-904, pp. 6, 12, 13
(next page on part 5)
