RFC1812 - Requirements for IP Version 4 Routers(3)
DISCUSSION
Previous versions of this document also noted that subnet numbers
must be neither 0 nor -1, and must be at least two bits in length.
In a CIDR world, the subnet number is clearly an extension of the
network prefix and cannot be interpreted without the remainder of
the prefix. This restriction of subnet numbers is therefore
meaningless in view of CIDR and may be safely ignored.
For further discussion of broadcast addresses, see Section [4.2.3.1].
When a router originates any datagram, the IP source address MUST be
one of its own IP addresses (but not a broadcast or multicast
address). The only exception is during initialization.
For most purposes, a datagram addressed to a broadcast or multicast
destination is processed as if it had been addressed to one of the
router's IP addresses; that is to say:
o A router MUST receive and process normally any packets with a
broadcast destination address.
o A router MUST receive and process normally any packets sent to a
multicast destination address that the router has asked to
receive.
The term specific-destination address means the equivalent local IP
address of the host. The specific-destination address is defined to
be the destination address in the IP header unless the header
contains a broadcast or multicast address, in which case the
specific-destination is an IP address assigned to the physical
interface on which the datagram arrived.
A router MUST silently discard any received datagram containing an IP
source address that is invalid by the rules of this section. This
validation could be done either by the IP layer or (when appropriate)
by each protocol in the transport layer. As with any datagram a
router discards, the datagram discard SHOULD be counted.
DISCUSSION
A misaddressed datagram might be caused by a Link Layer broadcast
of a unicast datagram or by another router or host that is
confused or misconfigured.
4.2.3 SPECIFIC ISSUES
4.2.3.1 IP Broadcast Addresses
For historical reasons, there are a number of IP addresses (some
standard and some not) which are used to indicate that an IP packet
is an IP broadcast. A router
(1) MUST treat as IP broadcasts packets addressed to 255.255.255.255
or { <Network-prefix>, -1 }.
(2) SHOULD silently discard on receipt (i.e., do not even deliver to
applications in the router) any packet addressed to 0.0.0.0 or {
<Network-prefix>, 0 }. If these packets are not silently
discarded, they MUST be treated as IP broadcasts (see Section
[5.3.5]). There MAY be a configuration option to allow receipt
of these packets. This option SHOULD default to discarding
them.
(3) SHOULD (by default) use the limited broadcast address
(255.255.255.255) when originating an IP broadcast destined for
a connected (sub)network (except when sending an ICMP Address
Mask Reply, as discussed in Section [4.3.3.9]). A router MUST
receive limited broadcasts.
(4) SHOULD NOT originate datagrams addressed to 0.0.0.0 or {
<Network-prefix>, 0 }. There MAY be a configuration option to
allow generation of these packets (instead of using the relevant
1s format broadcast). This option SHOULD default to not
generating them.
DISCUSSION
In the second bullet, the router obviously cannot recognize
addresses of the form { <Network-prefix>, 0 } if the router has no
interface to that network prefix. In that case, the rules of the
second bullet do not apply because, from the point of view of the
router, the packet is not an IP broadcast packet.
4.2.3.2 IP Multicasting
An IP router SHOULD satisfy the Host Requirements with respect to IP
multicasting, as specified in [INTRO:2]. An IP router SHOULD support
local IP multicasting on all connected networks. When a mapping from
IP multicast addresses to link-layer addresses has been specified
(see the various IP-over-xxx specifications), it SHOULD use that
mapping, and MAY be configurable to use the link layer broadcast
instead. On point-to-point links and all other interfaces,
multicasts are encapsulated as link layer broadcasts. Support for
local IP multicasting includes originating multicast datagrams,
joining multicast groups and receiving multicast datagrams, and
leaving multicast groups. This implies support for all of
[INTERNET:4] including IGMP (see Section [4.4]).
DISCUSSION
Although [INTERNET:4] is entitled Host Extensions for IP
Multicasting, it applies to all IP systems, both hosts and
routers. In particular, since routers may join multicast groups,
it is correct for them to perform the host part of IGMP, reporting
their group memberships to any multicast routers that may be
present on their attached networks (whether or not they themselves
are multicast routers).
Some router protocols may specifically require support for IP
multicasting (e.g., OSPF [ROUTE:1]), or may recommend it (e.g.,
ICMP Router Discovery [INTERNET:13]).
4.2.3.3 Path MTU Discovery
To eliminate fragmentation or minimize it, it is desirable to know
what is the path MTU along the path from the source to destination.
The path MTU is the minimum of the MTUs of each hop in the path.
[INTERNET:14] describes a technique for dynamically discovering the
maximum transmission unit (MTU) of an arbitrary internet path. For a
path that passes through a router that does not support
[INTERNET:14], this technique might not discover the correct Path
MTU, but it will always choose a Path MTU as accurate as, and in many
cases more accurate than, the Path MTU that would be chosen by older
techniques or the current practice.
When a router is originating an IP datagram, it SHOULD use the scheme
described in [INTERNET:14] to limit the datagram's size. If the
router's route to the datagram's destination was learned from a
routing protocol that provides Path MTU information, the scheme
described in [INTERNET:14] is still used, but the Path MTU
information from the routing protocol SHOULD be used as the initial
guess as to the Path MTU and also as an upper bound on the Path MTU.
4.2.3.4 Subnetting
Under certain circumstances, it may be desirable to support subnets
of a particular network being interconnected only through a path that
is not part of the subnetted network. This is known as discontiguous
subnetwork support.
Routers MUST support discontiguous subnetworks.
IMPLEMENTATION
In classical IP networks, this was very difficult to achieve; in
CIDR networks, it is a natural by-product. Therefore, a router
SHOULD NOT make assumptions about subnet architecture, but SHOULD
treat each route as a generalized network prefix.
DISCUSSION The Internet has been growing at a tremendous rate of
late. This has been placing severe strains on the IP addressing
technology. A major factor in this strain is the strict IP
Address class boundaries. These make it difficult to efficiently
size network prefixes to their networks and aggregate several
network prefixes into a single route advertisement. By
eliminating the strict class boundaries of the IP address and
treating each route as a generalized network prefix, these strains
may be greatly reduced.
The technology for currently doing this is Classless Inter Domain
Routing (CIDR) [INTERNET:15].
For similar reasons, an address block associated with a given network
prefix could be subdivided into subblocks of different sizes, so that
the network prefixes associated with the subblocks would have
different length. For example, within a block whose network prefix
is 8 bits long, one subblock may have a 16 bit network prefix,
another may have an 18 bit network prefix, and a third a 14 bit
network prefix.
Routers MUST support variable length network prefixes in both their
interface configurations and their routing databases.
4.3 INTERNET CONTROL MESSAGE PROTOCOL - ICMP
4.3.1 INTRODUCTION
ICMP is an auxiliary protocol, which provides routing, diagnostic and
error functionality for IP. It is described in [INTERNET:8]. A
router MUST support ICMP.
ICMP messages are grouped in two classes that are discussed in the
following sections:
ICMP error messages:
Destination Unreachable Section 4.3.3.1
Redirect Section 4.3.3.2
Source Quench Section 4.3.3.3
Time Exceeded Section 4.3.3.4
Parameter Problem Section 4.3.3.5
ICMP query messages:
Echo Section 4.3.3.6
Information Section 4.3.3.7
Timestamp Section 4.3.3.8
Address Mask Section 4.3.3.9
Router Discovery Section 4.3.3.10
General ICMP requirements and discussion are in the next section.
4.3.2 GENERAL ISSUES
4.3.2.1 Unknown Message Types
If an ICMP message of unknown type is received, it MUST be passed to
the ICMP user interface (if the router has one) or silently discarded
(if the router does not have one).
4.3.2.2 ICMP Message TTL
When originating an ICMP message, the router MUST initialize the TTL.
The TTL for ICMP responses must not be taken from the packet that
triggered the response.
4.3.2.3 Original Message Header
Historically, every ICMP error message has included the Internet
header and at least the first 8 data bytes of the datagram that
triggered the error. This is no longer adequate, due to the use of
IP-in-IP tunneling and other technologies. Therefore, the ICMP
datagram SHOULD contain as much of the original datagram as possible
without the length of the ICMP datagram exceeding 576 bytes. The
returned IP header (and user data) MUST be identical to that which
was received, except that the router is not required to undo any
modifications to the IP header that are normally performed in
forwarding that were performed before the error was detected (e.g.,
decrementing the TTL, or updating options). Note that the
requirements of Section [4.3.3.5] supersede this requirement in some
cases (i.e., for a Parameter Problem message, if the problem is in a
modified field, the router must undo the modification). See Section
[4.3.3.5]).
4.3.2.4 ICMP Message Source Address
Except where this document specifies otherwise, the IP source address
in an ICMP message originated by the router MUST be one of the IP
addresses associated with the physical interface over which the ICMP
message is transmitted. If the interface has no IP addresses
associated with it, the router's router-id (see Section [5.2.5]) is
used instead.
4.3.2.5 TOS and Precedence
ICMP error messages SHOULD have their TOS bits set to the same value
as the TOS bits in the packet that provoked the sending of the ICMP
error message, unless setting them to that value would cause the ICMP
error message to be immediately discarded because it could not be
routed to its destination. Otherwise, ICMP error messages MUST be
sent with a normal (i.e., zero) TOS. An ICMP reply message SHOULD
have its TOS bits set to the same value as the TOS bits in the ICMP
request that provoked the reply.
ICMP Source Quench error messages, if sent at all, MUST have their IP
Precedence field set to the same value as the IP Precedence field in
the packet that provoked the sending of the ICMP Source Quench
message. All other ICMP error messages (Destination Unreachable,
Redirect, Time Exceeded, and Parameter Problem) SHOULD have their
precedence value set to 6 (INTERNETWORK CONTROL) or 7 (NETWORK
CONTROL). The IP Precedence value for these error messages MAY be
settable.
An ICMP reply message MUST have its IP Precedence field set to the
same value as the IP Precedence field in the ICMP request that
provoked the reply.
4.3.2.6 Source Route
If the packet which provokes the sending of an ICMP error message
contains a source route option, the ICMP error message SHOULD also
contain a source route option of the same type (strict or loose),
created by reversing the portion before the pointer of the route
recorded in the source route option of the original packet UNLESS the
ICMP error message is an ICMP Parameter Problem complaining about a
source route option in the original packet, or unless the router is
aware of policy that would prevent the delivery of the ICMP error
message.
DISCUSSION
In environments which use the U.S. Department of Defense security
option (defined in [INTERNET:5]), ICMP messages may need to
include a security option. Detailed information on this topic
should be available from the Defense Communications Agency.
4.3.2.7 When Not to Send ICMP Errors
An ICMP error message MUST NOT be sent as the result of receiving:
o An ICMP error message, or
o A packet which fails the IP header validation tests described in
Section [5.2.2] (except where that section specifically permits
the sending of an ICMP error message), or
o A packet destined to an IP broadcast or IP multicast address, or
o A packet sent as a Link Layer broadcast or multicast, or
o A packet whose source address has a network prefix of zero or is an
invalid source address (as defined in Section [5.3.7]), or
o Any fragment of a datagram other then the first fragment (i.e., a
packet for which the fragment offset in the IP header is nonzero).
Furthermore, an ICMP error message MUST NOT be sent in any case where
this memo states that a packet is to be silently discarded.
NOTE: THESE RESTRICTIONS TAKE PRECEDENCE OVER ANY REQUIREMENT
ELSEWHERE IN THIS DOCUMENT FOR SENDING ICMP ERROR MESSAGES.
DISCUSSION
These rules aim to prevent the broadcast storms that have resulted
from routers or hosts returning ICMP error messages in response to
broadcast packets. For example, a broadcast UDP packet to a non-
existent port could trigger a flood of ICMP Destination
Unreachable datagrams from all devices that do not have a client
for that destination port. On a large Ethernet, the resulting
collisions can render the network useless for a second or more.
Every packet that is broadcast on the connected network should
have a valid IP broadcast address as its IP destination (see
Section [5.3.4] and [INTRO:2]). However, some devices violate
this rule. To be certain to detect broadcast packets, therefore,
routers are required to check for a link-layer broadcast as well
as an IP-layer address.
IMPLEMENTATION+ This requires that the link layer inform the IP layer
when a link-layer broadcast packet has been received; see Section
[3.1].
4.3.2.8 Rate Limiting
A router which sends ICMP Source Quench messages MUST be able to
limit the rate at which the messages can be generated. A router
SHOULD also be able to limit the rate at which it sends other sorts
of ICMP error messages (Destination Unreachable, Redirect, Time
Exceeded, Parameter Problem). The rate limit parameters SHOULD be
settable as part of the configuration of the router. How the limits
are applied (e.g., per router or per interface) is left to the
implementor's discretion.
DISCUSSION
Two problems for a router sending ICMP error message are:
(1) The consumption of bandwidth on the reverse path, and
(2) The use of router resources (e.g., memory, CPU time)
To help solve these problems a router can limit the frequency with
which it generates ICMP error messages. For similar reasons, a
router may limit the frequency at which some other sorts of
messages, such as ICMP Echo Replies, are generated.
IMPLEMENTATION
Various mechanisms have been used or proposed for limiting the
rate at which ICMP messages are sent:
(1) Count-based - for example, send an ICMP error message for
every N dropped packets overall or per given source host.
This mechanism might be appropriate for ICMP Source Quench,
if used, but probably not for other types of ICMP messages.
(2) Timer-based - for example, send an ICMP error message to a
given source host or overall at most once per T milliseconds.
(3) Bandwidth-based - for example, limit the rate at which ICMP
messages are sent over a particular interface to some
fraction of the attached network's bandwidth.
4.3.3 SPECIFIC ISSUES
4.3.3.1 Destination Unreachable
If a router cannot forward a packet because it has no routes at all
(including no default route) to the destination specified in the
packet, then the router MUST generate a Destination Unreachable, Code
0 (Network Unreachable) ICMP message. If the router does have routes
to the destination network specified in the packet but the TOS
specified for the routes is neither the default TOS (0000) nor the
TOS of the packet that the router is attempting to route, then the
router MUST generate a Destination Unreachable, Code 11 (Network
Unreachable for TOS) ICMP message.
If a packet is to be forwarded to a host on a network that is
directly connected to the router (i.e., the router is the last-hop
router) and the router has ascertained that there is no path to the
destination host then the router MUST generate a Destination
Unreachable, Code 1 (Host Unreachable) ICMP message. If a packet is
to be forwarded to a host that is on a network that is directly
connected to the router and the router cannot forward the packet
because no route to the destination has a TOS that is either equal to
the TOS requested in the packet or is the default TOS (0000) then the
router MUST generate a Destination Unreachable, Code 12 (Host
Unreachable for TOS) ICMP message.
DISCUSSION
The intent is that a router generates the "generic" host/network
unreachable if it has no path at all (including default routes) to
the destination. If the router has one or more paths to the
destination, but none of those paths have an acceptable TOS, then
the router generates the "unreachable for TOS" message.
4.3.3.2 Redirect
The ICMP Redirect message is generated to inform a local host that it
should use a different next hop router for certain traffic.
Contrary to [INTRO:2], a router MAY ignore ICMP Redirects when
choosing a path for a packet originated by the router if the router
is running a routing protocol or if forwarding is enabled on the
router and on the interface over which the packet is being sent.
4.3.3.3 Source Quench
A router SHOULD NOT originate ICMP Source Quench messages. As
specified in Section [4.3.2], a router that does originate Source
Quench messages MUST be able to limit the rate at which they are
generated.
DISCUSSION
Research seems to suggest that Source Quench consumes network
bandwidth but is an ineffective (and unfair) antidote to
congestion. See, for example, [INTERNET:9] and [INTERNET:10].
Section [5.3.6] discusses the current thinking on how routers
ought to deal with overload and network congestion.
A router MAY ignore any ICMP Source Quench messages it receives.
DISCUSSION
A router itself may receive a Source Quench as the result of
originating a packet sent to another router or host. Such
datagrams might be, e.g., an EGP update sent to another router, or
a telnet stream sent to a host. A mechanism has been proposed
([INTERNET:11], [INTERNET:12]) to make the IP layer respond
directly to Source Quench by controlling the rate at which packets
are sent, however, this proposal is currently experimental and not
currently recommended.
4.3.3.4 Time Exceeded
When a router is forwarding a packet and the TTL field of the packet
is reduced to 0, the requirements of section [5.2.3.8] apply.
When the router is reassembling a packet that is destined for the
router, it is acting as an Internet host. [INTRO:2]'s reassembly
requirements therefore apply.
When the router receives (i.e., is destined for the router) a Time
Exceeded message, it MUST comply with [INTRO:2].
4.3.3.5 Parameter Problem
A router MUST generate a Parameter Problem message for any error not
specifically covered by another ICMP message. The IP header field or
IP option including the byte indicated by the pointer field MUST be
included unchanged in the IP header returned with this ICMP message.
Section [4.3.2] defines an exception to this requirement.
A new variant of the Parameter Problem message was defined in
[INTRO:2]:
Code 1 = required option is missing.
DISCUSSION
This variant is currently in use in the military community for a
missing security option.
4.3.3.6 Echo Request/Reply
A router MUST implement an ICMP Echo server function that receives
Echo Requests sent to the router, and sends corresponding Echo
Replies. A router MUST be prepared to receive, reassemble and echo
an ICMP Echo Request datagram at least as the maximum of 576 and the
MTUs of all the connected networks.
The Echo server function MAY choose not to respond to ICMP echo
requests addressed to IP broadcast or IP multicast addresses.
A router SHOULD have a configuration option that, if enabled, causes
the router to silently ignore all ICMP echo requests; if provided,
this option MUST default to allowing responses.
DISCUSSION
The neutral provision about responding to broadcast and multicast
Echo Requests derives from [INTRO:2]'s "Echo Request/Reply"
section.
As stated in Section [10.3.3], a router MUST also implement a
user/application-layer interface for sending an Echo Request and
receiving an Echo Reply, for diagnostic purposes. All ICMP Echo
Reply messages MUST be passed to this interface.
The IP source address in an ICMP Echo Reply MUST be the same as the
specific-destination address of the corresponding ICMP Echo Request
message.
Data received in an ICMP Echo Request MUST be entirely included in
the resulting Echo Reply.
If a Record Route and/or Timestamp option is received in an ICMP Echo
Request, this option (these options) SHOULD be updated to include the
current router and included in the IP header of the Echo Reply
message, without truncation. Thus, the recorded route will be for
the entire round trip.
If a Source Route option is received in an ICMP Echo Request, the
return route MUST be reversed and used as a Source Route option for
the Echo Reply message, unless the router is aware of policy that
would prevent the delivery of the message.
4.3.3.7 Information Request/Reply
A router SHOULD NOT originate or respond to these messages.
DISCUSSION
The Information Request/Reply pair was intended to support self-
configuring systems such as diskless workstations, to allow them
to discover their IP network prefixes at boot time. However,
these messages are now obsolete. The RARP and BOOTP protocols
provide better mechanisms for a host to discover its own IP
address.
4.3.3.8 Timestamp and Timestamp Reply
A router MAY implement Timestamp and Timestamp Reply. If they are
implemented then:
o The ICMP Timestamp server function MUST return a Timestamp Reply to
every Timestamp message that is received. It SHOULD be designed
for minimum variability in delay.
o An ICMP Timestamp Request message to an IP broadcast or IP
multicast address MAY be silently discarded.
o The IP source address in an ICMP Timestamp Reply MUST be the same
as the specific-destination address of the corresponding Timestamp
Request message.
o If a Source Route option is received in an ICMP Timestamp Request,
the return route MUST be reversed and used as a Source Route
option for the Timestamp Reply message, unless the router is aware
of policy that would prevent the delivery of the message.
o If a Record Route and/or Timestamp option is received in a
Timestamp Request, this (these) option(s) SHOULD be updated to
include the current router and included in the IP header of the
Timestamp Reply message.
o If the router provides an application-layer interface for sending
Timestamp Request messages then incoming Timestamp Reply messages
MUST be passed up to the ICMP user interface.
The preferred form for a timestamp value (the standard value) is
milliseconds since midnight, Universal Time. However, it may be
difficult to provide this value with millisecond resolution. For
example, many systems use clocks that update only at line frequency,
50 or 60 times per second. Therefore, some latitude is allowed in a
standard value:
(a) A standard value MUST be updated at least 16 times per second
(i.e., at most the six low-order bits of the value may be
undefined).
(b) The accuracy of a standard value MUST approximate that of
operator-set CPU clocks, i.e., correct within a few minutes.
IMPLEMENTATION
To meet the second condition, a router may need to query some time
server when the router is booted or restarted. It is recommended
that the UDP Time Server Protocol be used for this purpose. A
more advanced implementation would use the Network Time Protocol
(NTP) to achieve nearly millisecond clock synchronization;
however, this is not required.
4.3.3.9 Address Mask Request/Reply
A router MUST implement support for receiving ICMP Address Mask
Request messages and responding with ICMP Address Mask Reply
messages. These messages are defined in [INTERNET:2].
A router SHOULD have a configuration option for each logical
interface specifying whether the router is allowed to answer Address
Mask Requests for that interface; this option MUST default to
allowing responses. A router MUST NOT respond to an Address Mask
Request before the router knows the correct address mask.
A router MUST NOT respond to an Address Mask Request that has a
source address of 0.0.0.0 and which arrives on a physical interface
that has associated with it multiple logical interfaces and the
address masks for those interfaces are not all the same.
A router SHOULD examine all ICMP Address Mask Replies that it
receives to determine whether the information it contains matches the
router's knowledge of the address mask. If the ICMP Address Mask
Reply appears to be in error, the router SHOULD log the address mask
and the sender's IP address. A router MUST NOT use the contents of
an ICMP Address Mask Reply to determine the correct address mask.
Because hosts may not be able to learn the address mask if a router
is down when the host boots up, a router MAY broadcast a gratuitous
ICMP Address Mask Reply on each of its logical interfaces after it
has configured its own address masks. However, this feature can be
dangerous in environments that use variable length address masks.
Therefore, if this feature is implemented, gratuitous Address Mask
Replies MUST NOT be broadcast over any logical interface(s) which
either:
o Are not configured to send gratuitous Address Mask Replies. Each
logical interface MUST have a configuration parameter controlling
this, and that parameter MUST default to not sending the
gratuitous Address Mask Replies.
o Share subsuming (but not identical) network prefixes and physical
interface.
The { <Network-prefix>, -1 } form of the IP broadcast address MUST be
used for broadcast Address Mask Replies.
DISCUSSION
The ability to disable sending Address Mask Replies by routers is
required at a few sites that intentionally lie to their hosts
about the address mask. The need for this is expected to go away
as more and more hosts become compliant with the Host Requirements
standards.
The reason for both the second bullet above and the requirement
about which IP broadcast address to use is to prevent problems
when multiple IP network prefixes are in use on the same physical
network.
4.3.3.10 Router Advertisement and Solicitations
An IP router MUST support the router part of the ICMP Router
Discovery Protocol [INTERNET:13] on all connected networks on which
the router supports either IP multicast or IP broadcast addressing.
The implementation MUST include all the configuration variables
specified for routers, with the specified defaults.
DISCUSSION
Routers are not required to implement the host part of the ICMP
Router Discovery Protocol, but might find it useful for operation
while IP forwarding is disabled (i.e., when operating as a host).
DISCUSSION We note that it is quite common for hosts to use RIP
Version 1 as the router discovery protocol. Such hosts listen to
RIP traffic and use and use information extracted from that
traffic to discover routers and to make decisions as to which
router to use as a first-hop router for a given destination.
While this behavior is discouraged, it is still common and
implementors should be aware of it.
4.4 INTERNET GROUP MANAGEMENT PROTOCOL - IGMP
IGMP [INTERNET:4] is a protocol used between hosts and multicast
routers on a single physical network to establish hosts' membership
in particular multicast groups. Multicast routers use this
information, in conjunction with a multicast routing protocol, to
support IP multicast forwarding across the Internet.
A router SHOULD implement the host part of IGMP.
5. INTERNET LAYER - FORWARDING
5.1 INTRODUCTION
This section describes the process of forwarding packets.
5.2 FORWARDING WALK-THROUGH
There is no separate specification of the forwarding function in IP.
Instead, forwarding is covered by the protocol specifications for the
internet layer protocols ([INTERNET:1], [INTERNET:2], [INTERNET:3],
[INTERNET:8], and [ROUTE:11]).
5.2.1 Forwarding Algorithm
Since none of the primary protocol documents describe the forwarding
algorithm in any detail, we present it here. This is just a general
outline, and omits important details, such as handling of congestion,
that are dealt with in later sections.
It is not required that an implementation follow exactly the
algorithms given in sections [5.2.1.1], [5.2.1.2], and [5.2.1.3].
Much of the challenge of writing router software is to maximize the
rate at which the router can forward packets while still achieving
the same effect of the algorithm. Details of how to do that are
beyond the scope of this document, in part because they are heavily
dependent on the architecture of the router. Instead, we merely
point out the order dependencies among the steps:
(1) A router MUST verify the IP header, as described in section
[5.2.2], before performing any actions based on the contents of
the header. This allows the router to detect and discard bad
packets before the expenditure of other resources.
(2) Processing of certain IP options requires that the router insert
its IP address into the option. As noted in Section [5.2.4],
the address inserted MUST be the address of the logical
interface on which the packet is sent or the router's router-id
if the packet is sent over an unnumbered interface. Thus,
processing of these options cannot be completed until after the
output interface is chosen.
(3) The router cannot check and decrement the TTL before checking
whether the packet should be delivered to the router itself, for
reasons mentioned in Section [4.2.2.9].
(4) More generally, when a packet is delivered locally to the router,
its IP header MUST NOT be modified in any way (except that a
router may be required to insert a timestamp into any Timestamp
options in the IP header). Thus, before the router determines
whether the packet is to be delivered locally to the router, it
cannot update the IP header in any way that it is not prepared
to undo.
5.2.1.1 General
This section covers the general forwarding algorithm. This algorithm
applies to all forms of packets to be forwarded: unicast, multicast,
and broadcast.
(1) The router receives the IP packet (plus additional information
about it, as described in Section [3.1]) from the Link Layer.
(2) The router validates the IP header, as described in Section
[5.2.2]. Note that IP reassembly is not done, except on IP
fragments to be queued for local delivery in step (4).
(3) The router performs most of the processing of any IP options. As
described in Section [5.2.4], some IP options require additional
processing after the routing decision has been made.
(4) The router examines the destination IP address of the IP
datagram, as described in Section [5.2.3], to determine how it
should continue to process the IP datagram. There are three
possibilities:
o The IP datagram is destined for the router, and should be
queued for local delivery, doing reassembly if needed.
o The IP datagram is not destined for the router, and should be
queued for forwarding.
o The IP datagram should be queued for forwarding, but (a copy)
must also be queued for local delivery.
5.2.1.2 Unicast
Since the local delivery case is well covered by [INTRO:2], the
following assumes that the IP datagram was queued for forwarding. If
the destination is an IP unicast address:
(5) The forwarder determines the next hop IP address for the packet,
usually by looking up the packet's destination in the router's
routing table. This procedure is described in more detail in
Section [5.2.4]. This procedure also decides which network
interface should be used to send the packet.
(6) The forwarder verifies that forwarding the packet is permitted.
The source and destination addresses should be valid, as
described in Section [5.3.7] and Section [5.3.4] If the router
supports administrative constraints on forwarding, such as those
described in Section [5.3.9], those constraints must be
satisfied.
(7) The forwarder decrements (by at least one) and checks the
packet's TTL, as described in Section [5.3.1].
(8) The forwarder performs any IP option processing that could not be
completed in step 3.
(9) The forwarder performs any necessary IP fragmentation, as
described in Section [4.2.2.7]. Since this step occurs after
outbound interface selection (step 5), all fragments of the same
datagram will be transmitted out the same interface.
(10) The forwarder determines the Link Layer address of the packet's
next hop. The mechanisms for doing this are Link Layer-
dependent (see chapter 3).
(11) The forwarder encapsulates the IP datagram (or each of the
fragments thereof) in an appropriate Link Layer frame and queues
it for output on the interface selected in step 5.
(12) The forwarder sends an ICMP redirect if necessary, as described
in Section [4.3.3.2].
5.2.1.3 Multicast
If the destination is an IP multicast, the following steps are taken.
Note that the main differences between the forwarding of IP unicasts
and the forwarding of IP multicasts are
o IP multicasts are usually forwarded based on both the datagram's
source and destination IP addresses,
o IP multicast uses an expanding ring search,
o IP multicasts are forwarded as Link Level multicasts, and
o ICMP errors are never sent in response to IP multicast datagrams.
Note that the forwarding of IP multicasts is still somewhat
experimental. As a result, the algorithm presented below is not
mandatory, and is provided as an example only.
(5a) Based on the IP source and destination addresses found in the
datagram header, the router determines whether the datagram has
been received on the proper interface for forwarding. If not,
the datagram is dropped silently. The method for determining
the proper receiving interface depends on the multicast routing
algorithm(s) in use. In one of the simplest algorithms, reverse
path forwarding (RPF), the proper interface is the one that
would be used to forward unicasts back to the datagram source.
(6a) Based on the IP source and destination addresses found in the
datagram header, the router determines the datagram's outgoing
interfaces. To implement IP multicast's expanding ring search
(see [INTERNET:4]) a minimum TTL value is specified for each
outgoing interface. A copy of the multicast datagram is
forwarded out each outgoing interface whose minimum TTL value is
less than or equal to the TTL value in the datagram header, by
separately applying the remaining steps on each such interface.
(7a) The router decrements the packet's TTL by one.
(8a) The forwarder performs any IP option processing that could not
be completed in step (3).
(9a) The forwarder performs any necessary IP fragmentation, as
described in Section [4.2.2.7].
(10a) The forwarder determines the Link Layer address to use in the
Link Level encapsulation. The mechanisms for doing this are
Link Layer-dependent. On LANs a Link Level multicast or
broadcast is selected, as an algorithmic translation of the
datagrams' IP multicast address. See the various IP-over-xxx
specifications for more details.
(11a) The forwarder encapsulates the packet (or each of the fragments
thereof) in an appropriate Link Layer frame and queues it for
output on the appropriate interface.
5.2.2 IP Header Validation
Before a router can process any IP packet, it MUST perform a the
following basic validity checks on the packet's IP header to ensure
that the header is meaningful. If the packet fails any of the
following tests, it MUST be silently discarded, and the error SHOULD
be logged.
(1) The packet length reported by the Link Layer must be large enough
to hold the minimum length legal IP datagram (20 bytes).
(2) The IP checksum must be correct.
(3) The IP version number must be 4. If the version number is not 4
then the packet may be another version of IP, such as IPng or
ST-II.
(4) The IP header length field must be large enough to hold the
minimum length legal IP datagram (20 bytes = 5 words).
(5) The IP total length field must be large enough to hold the IP
datagram header, whose length is specified in the IP header
length field.
A router MUST NOT have a configuration option that allows disabling
any of these tests.
If the packet passes the second and third tests, the IP header length
field is at least 4, and both the IP total length field and the
packet length reported by the Link Layer are at least 16 then,
despite the above rule, the router MAY respond with an ICMP Parameter
Problem message, whose pointer points at the IP header length field
(if it failed the fourth test) or the IP total length field (if it
failed the fifth test). However, it still MUST discard the packet
and still SHOULD log the error.
These rules (and this entire document) apply only to version 4 of the
Internet Protocol. These rules should not be construed as
prohibiting routers from supporting other versions of IP.
Furthermore, if a router can truly classify a packet as being some
other version of IP then it ought not treat that packet as an error
packet within the context of this memo.
IMPLEMENTATION
It is desirable for purposes of error reporting, though not always
entirely possible, to determine why a header was invalid. There
are four possible reasons:
o The Link Layer truncated the IP header
o The datagram is using a version of IP other than the standard
one (version 4).
o The IP header has been corrupted in transit.
o The sender generated an illegal IP header.
It is probably desirable to perform the checks in the order
listed, since we believe that this ordering is most likely to
correctly categorize the cause of the error. For purposes of
error reporting, it may also be desirable to check if a packet
that fails these tests has an IP version number indicating IPng or
ST-II; these should be handled according to their respective
specifications.
Additionally, the router SHOULD verify that the packet length
reported by the Link Layer is at least as large as the IP total
length recorded in the packet's IP header. If it appears that the
packet has been truncated, the packet MUST be discarded, the error
SHOULD be logged, and the router SHOULD respond with an ICMP
Parameter Problem message whose pointer points at the IP total length
field.
DISCUSSION
Because any higher layer protocol that concerns itself with data
corruption will detect truncation of the packet data when it
reaches its final destination, it is not absolutely necessary for
routers to perform the check suggested above to maintain protocol
correctness. However, by making this check a router can simplify
considerably the task of determining which hop in the path is
truncating the packets. It will also reduce the expenditure of
resources down-stream from the router in that down-stream systems
will not need to deal with the packet.
Finally, if the destination address in the IP header is not one of
the addresses of the router, the router SHOULD verify that the packet
does not contain a Strict Source and Record Route option. If a
packet fails this test (if it contains a strict source route option),
the router SHOULD log the error and SHOULD respond with an ICMP
Parameter Problem error with the pointer pointing at the offending
packet's IP destination address.
DISCUSSION
Some people might suggest that the router should respond with a
Bad Source Route message instead of a Parameter Problem message.
However, when a packet fails this test, it usually indicates a
protocol error by the previous hop router, whereas Bad Source
Route would suggest that the source host had requested a
nonexistent or broken path through the network.
5.2.3 Local Delivery Decision
When a router receives an IP packet, it must decide whether the
packet is addressed to the router (and should be delivered locally)
or the packet is addressed to another system (and should be handled
by the forwarder). There is also a hybrid case, where certain IP
broadcasts and IP multicasts are both delivered locally and
forwarded. A router MUST determine which of the these three cases
applies using the following rules.
o An unexpired source route option is one whose pointer value does
not point past the last entry in the source route. If the packet
contains an unexpired source route option, the pointer in the
option is advanced until either the pointer does point past the
last address in the option or else the next address is not one of
the router's own addresses. In the latter (normal) case, the
packet is forwarded (and not delivered locally) regardless of the
rules below.
o The packet is delivered locally and not considered for forwarding
in the following cases:
- The packet's destination address exactly matches one of the
router's IP addresses,
- The packet's destination address is a limited broadcast address
({-1, -1}), or
- The packet's destination is an IP multicast address which is
never forwarded (such as 224.0.0.1 or 224.0.0.2) and (at least)
one of the logical interfaces associated with the physical
interface on which the packet arrived is a member of the
destination multicast group.
o The packet is passed to the forwarder AND delivered locally in the
following cases:
- The packet's destination address is an IP broadcast address that
addresses at least one of the router's logical interfaces but
does not address any of the logical interfaces associated with
the physical interface on which the packet arrived
- The packet's destination is an IP multicast address which is
permitted to be forwarded (unlike 224.0.0.1 and 224.0.0.2) and
(at least) one of the logical interfaces associated with the
physical interface on which the packet arrived is a member of
the destination multicast group.
o The packet is delivered locally if the packet's destination address
is an IP broadcast address (other than a limited broadcast
address) that addresses at least one of the logical interfaces
associated with the physical interface on which the packet
arrived. The packet is ALSO passed to the forwarder unless the
link on which the packet arrived uses an IP encapsulation that
does not encapsulate broadcasts differently than unicasts (e.g.,
by using different Link Layer destination addresses).
o The packet is passed to the forwarder in all other cases.
DISCUSSION
The purpose of the requirement in the last sentence of the fourth
bullet is to deal with a directed broadcast to another network
prefix on the same physical cable. Normally, this works as
expected: the sender sends the broadcast to the router as a Link
Layer unicast. The router notes that it arrived as a unicast, and
therefore must be destined for a different network prefix than the
sender sent it on. Therefore, the router can safely send it as a
Link Layer broadcast out the same (physical) interface over which
it arrived. However, if the router can't tell whether the packet
was received as a Link Layer unicast, the sentence ensures that
the router does the safe but wrong thing rather than the unsafe
but right thing.
IMPLEMENTATION
As described in Section [5.3.4], packets received as Link Layer
broadcasts are generally not forwarded. It may be advantageous to
avoid passing to the forwarder packets it would later discard
because of the rules in that section.
Some Link Layers (either because of the hardware or because of
special code in the drivers) can deliver to the router copies of
all Link Layer broadcasts and multicasts it transmits. Use of
this feature can simplify the implementation of cases where a
packet has to both be passed to the forwarder and delivered
locally, since forwarding the packet will automatically cause the
router to receive a copy of the packet that it can then deliver
locally. One must use care in these circumstances to prevent
treating a received loop-back packet as a normal packet that was
received (and then being subject to the rules of forwarding,
etc.).
Even without such a Link Layer, it is of course hardly necessary
to make a copy of an entire packet to queue it both for forwarding
and for local delivery, though care must be taken with fragments,
since reassembly is performed on locally delivered packets but not
on forwarded packets. One simple scheme is to associate a flag
with each packet on the router's output queue that indicates
whether it should be queued for local delivery after it has been
sent.
5.2.4 Determining the Next Hop Address
When a router is going to forward a packet, it must determine whether
it can send it directly to its destination, or whether it needs to
pass it through another router. If the latter, it needs to determine
which router to use. This section explains how these determinations
are made.
This section makes use of the following definitions:
o LSRR - IP Loose Source and Record Route option
o SSRR - IP Strict Source and Record Route option
o Source Route Option - an LSRR or an SSRR
o Ultimate Destination Address - where the packet is being sent to:
the last address in the source route of a source-routed packet, or
the destination address in the IP header of a non-source-routed
packet
o Adjacent - reachable without going through any IP routers
o Next Hop Address - the IP address of the adjacent host or router to
which the packet should be sent next
o IP Destination Address - the ultimate destination address, except
in source routed packets, where it is the next address specified
in the source route
o Immediate Destination - the node, System, router, end-system, or
whatever that is addressed by the IP Destination Address.
5.2.4.1 IP Destination Address
If:
o the destination address in the IP header is one of the addresses of
the router,
o the packet contains a Source Route Option, and
o the pointer in the Source Route Option does not point past the end
of the option,
then the next IP Destination Address is the address pointed at by the
pointer in that option. If:
o the destination address in the IP header is one of the addresses of
the router,
o the packet contains a Source Route Option, and
o the pointer in the Source Route Option points past the end of the
option,
then the message is addressed to the system analyzing the message.
A router MUST use the IP Destination Address, not the Ultimate
Destination Address (the last address in the source route option),
when determining how to handle a packet.
It is an error for more than one source route option to appear in a
datagram. If it receives such a datagram, it SHOULD discard the
packet and reply with an ICMP Parameter Problem message whose pointer
points at the beginning of the second source route option.
5.2.4.2 Local/Remote Decision
After it has been determined that the IP packet needs to be forwarded
according to the rules specified in Section [5.2.3], the following
algorithm MUST be used to determine if the Immediate Destination is
directly accessible (see [INTERNET:2]).
(1) For each network interface that has not been assigned any IP
address (the unnumbered lines as described in Section [2.2.7]),
compare the router-id of the other end of the line to the IP
Destination Address. If they are exactly equal, the packet can
be transmitted through this interface.
DISCUSSION
In other words, the router or host at the remote end of the line
is the destination of the packet or is the next step in the source
route of a source routed packet.
(2) If no network interface has been selected in the first step, for
each IP address assigned to the router:
(a) isolate the network prefix used by the interface.
IMPLEMENTATION
The result of this operation will usually have been computed and
saved during initialization.
(b) Isolate the corresponding set of bits from the IP Destination
Address of the packet.
(c) Compare the resulting network prefixes. If they are equal to
each other, the packet can be transmitted through the
corresponding network interface.
(3) If the destination was neither the router-id of a neighbor on an
unnumbered interface nor a member of a directly connected network
prefix, the IP Destination is accessible only through some other
router. The selection of the router and the next hop IP address
is described in Section [5.2.4.3]. In the case of a host that is
not also a router, this may be the configured default router.
Ongoing work in the IETF [ARCH:9, NRHP] considers some cases such as
when multiple IP (sub)networks are overlaid on the same link layer
network. Barring policy restrictions, hosts and routers using a
common link layer network can directly communicate even if they are
not in the same IP (sub)network, if there is adequate information
present. The Next Hop Routing Protocol (NHRP) enables IP entities to
determine the "optimal" link layer address to be used to traverse
such a link layer network towards a remote destination.
(4) If the selected "next hop" is reachable through an interface
configured to use NHRP, then the following additional steps apply:
(a) Compare the IP Destination Address to the destination addresses
in the NHRP cache. If the address is in the cache, then send
the datagram to the corresponding cached link layer address.
(b) If the address is not in the cache, then construct an NHRP
request packet containing the IP Destination Address. This
message is sent to the NHRP server configured for that
interface. This may be a logically separate process or entity
in the router itself.
(c) The NHRP server will respond with the proper link layer address
to use to transmit the datagram and subsequent datagrams to the
same destination. The system MAY transmit the datagram(s) to
the traditional "next hop" router while awaiting the NHRP reply.
5.2.4.3 Next Hop Address
EDITORS+COMMENTS
The router applies the algorithm in the previous section to
determine if the IP Destination Address is adjacent. If so, the
next hop address is the same as the IP Destination Address.
Otherwise, the packet must be forwarded through another router to
reach its Immediate Destination. The selection of this router is
the topic of this section.
If the packet contains an SSRR, the router MUST discard the packet
and reply with an ICMP Bad Source Route error. Otherwise, the
router looks up the IP Destination Address in its routing table to
determine an appropriate next hop address.
DISCUSSION
Per the IP specification, a Strict Source Route must specify a
sequence of nodes through which the packet must traverse; the
packet must go from one node of the source route to the next,
traversing intermediate networks only. Thus, if the router is not
adjacent to the next step of the source route, the source route
can not be fulfilled. Therefore, the router rejects such with an
ICMP Bad Source Route error.
The goal of the next-hop selection process is to examine the entries
in the router's Forwarding Information Base (FIB) and select the best
route (if there is one) for the packet from those available in the
FIB.
Conceptually, any route lookup algorithm starts out with a set of
candidate routes that consists of the entire contents of the FIB.
The algorithm consists of a series of steps that discard routes from
the set. These steps are referred to as Pruning Rules. Normally,
when the algorithm terminates there is exactly one route remaining in
the set. If the set ever becomes empty, the packet is discarded
because the destination is unreachable. It is also possible for the
algorithm to terminate when more than one route remains in the set.
In this case, the router may arbitrarily discard all but one of them,
or may perform "load-splitting" by choosing whichever of the routes
has been least recently used.
With the exception of rule 3 (Weak TOS), a router MUST use the
following Pruning Rules when selecting a next hop for a packet. If a
router does consider TOS when making next-hop decisions, the Rule 3
must be applied in the order indicated below. These rules MUST be
(conceptually) applied to the FIB in the order that they are
presented. (For some historical perspective, additional pruning
rules, and other common algorithms in use, see Appendix E.)
DISCUSSION
Rule 3 is optional in that Section [5.3.2] says that a router only
SHOULD consider TOS when making forwarding decisions.
(1) Basic Match
This rule discards any routes to destinations other than the
IP Destination Address of the packet. For example, if a
packet's IP Destination Address is 10.144.2.5, this step
would discard a route to net 128.12.0.0/16 but would retain
any routes to the network prefixes 10.0.0.0/8 and
10.144.0.0/16, and any default routes.
More precisely, we assume that each route has a destination
attribute, called route.dest and a corresponding prefix
length, called route.length, to specify which bits of
route.dest are significant. The IP Destination Address of
the packet being forwarded is ip.dest. This rule discards
all routes from the set of candidates except those for which
the most significant route.length bits of route.dest and
ip.dest are equal.