RFC1812 - Requirements for IP Version 4 Routers(6)
However, in performing this router-like function, the host MUST obey
all the relevant rules for a router forwarding source-routed
datagrams [INTRO:2]. This includes the following specific
provisions:
(A) TTL
The TTL field MUST be decremented and the datagram perhaps
discarded as specified for a router in [INTRO:2].
(B) ICMP Destination Unreachable
A host MUST be able to generate Destination Unreachable messages
with the following codes:
4 (Fragmentation Required but DF Set) when a source-routed
datagram cannot be fragmented to fit into the target network;
5 (Source Route Failed) when a source-routed datagram cannot be
forwarded, e.g., because of a routing problem or because the
next hop of a strict source route is not on a connected
network.
(C) IP Source Address
A source-routed datagram being forwarded MAY (and normally will)
have a source address that is not one of the IP addresses of the
forwarding host.
(D) Record Route Option
A host that is forwarding a source-routed datagram containing a
Record Route option MUST update that option, if it has room.
(E) Timestamp Option
A host that is forwarding a source-routed datagram containing a
Timestamp Option MUST add the current timestamp to that option,
according to the rules for this option.
To define the rules restricting host forwarding of source-routed
datagrams, we use the term local source-routing if the next hop will
be through the same physical interface through which the datagram
arrived; otherwise, it is non-local source-routing.
A host is permitted to perform local source-routing without
restriction.
A host that supports non-local source-routing MUST have a
configurable switch to disable forwarding, and this switch MUST
default to disabled.
The host MUST satisfy all router requirements for configurable policy
filters [INTRO:2] restricting non-local forwarding.
If a host receives a datagram with an incomplete source route but
does not forward it for some reason, the host SHOULD return an ICMP
Destination Unreachable (code 5, Source Route Failed) message, unless
the datagram was itself an ICMP error message.
APPENDIX B. GLOSSARY
This Appendix defines specific terms used in this memo. It also
defines some general purpose terms that may be of interest. See also
[INTRO:9] for a more general set of definitions.
Autonomous System (AS)
An Autonomous System (AS) is a connected segment of a network
topology that consists of a collection of subnetworks (with
hosts attached) interconnected by a set of routes. The
subnetworks and the routers are expected to be under the control
of a single operations and maintenance (O&M) organization.
Within an AS routers may use one or more interior routing
protocols, and sometimes several sets of metrics. An AS is
expected to present to other ASs an appearence of a coherent
interior routing plan, and a consistent picture of the
destinations reachable through the AS. An AS is identified by
an Autonomous System number.
Connected Network
A network prefix to which a router is interfaced is often known
as a local network or the subnetwork of that router. However,
these terms can cause confusion, and therefore we use the term
Connected Network in this memo.
Connected (Sub)Network
A Connected (Sub)Network is an IP subnetwork to which a router
is interfaced, or a connected network if the connected network
is not subnetted. See also Connected Network.
Datagram
The unit transmitted between a pair of internet modules. Data,
called datagrams, from sources to destinations. The Internet
Protocol does not provide a reliable communication facility.
There are no acknowledgments either end-to-end or hop-by-hop.
There is no error no retransmissions. There is no flow control.
See IP.
Default Route
A routing table entry that is used to direct any data addressed
to any network prefixes not explicitly listed in the routing
table.
Dense Mode
In multicast forwarding, two paradigms are possible: in Dense
Mode forwarding, a network multicast is forwarded as a data link
layer multicast to all interfaces except that on which it was
received, unless and until the router is instructed not to by a
multicast routing neighbor. See Sparse Mode.
EGP
Exterior Gateway Protocol A protocol that distributes routing
information to the gateways (routers) which connect autonomous
systems. See IGP.
EGP-2
Exterior Gateway Protocol version 2 This is an EGP routing
protocol developed to handle traffic between Autonomous Systems
in the Internet.
Forwarder
The logical entity within a router that is responsible for
switching packets among the router's interfaces. The Forwarder
also makes the decisions to queue a packet for local delivery,
to queue a packet for transmission out another interface, or
both.
Forwarding
Forwarding is the process a router goes through for each packet
received by the router. The packet may be consumed by the
router, it may be output on one or more interfaces of the
router, or both. Forwarding includes the process of deciding
what to do with the packet as well as queuing it up for
(possible) output or internal consumption.
Forwarding Information Base (FIB)
The table containing the information necessary to forward IP
Datagrams, in this document, is called the Forwarding
Information Base. At minimum, this contains the interface
identifier and next hop information for each reachable
destination network prefix.
Fragment
An IP datagram that represents a portion of a higher layer's
packet that was too large to be sent in its entirety over the
output network.
General Purpose Serial Interface
A physical medium capable of connecting exactly two systems, and
therefore configurable as a point to point line, but also
configurable to support link layer networking using protocols
such as X.25 or Frame Relay. A link layer network connects
another system to a switch, and a higher communication layer
multiplexes virtual circuits on the connection. See Point to
Point Line.
IGP
Interior Gateway Protocol A protocol that distributes routing
information with an Autonomous System (AS). See EGP.
Interface IP Address
The IP Address and network prefix length that is assigned to a
specific interface of a router.
Internet Address
An assigned number that identifies a host in an internet. It
has two parts: an IP address and a prefix length. The prefix
length indicates how many of the most specific bits of the
address constitute the network prefix.
IP
Internet Protocol The network layer protocol for the Internet.
It is a packet switching, datagram protocol defined in RFC791.
IP does not provide a reliable communications facility; that is,
there are no end-to-end of hop-by-hop acknowledgments.
IP Datagram
An IP Datagram is the unit of end-to-end transmission in the
Internet Protocol. An IP Datagram consists of an IP header
followed by all of higher-layer data (such as TCP, UDP, ICMP,
and the like). An IP Datagram is an IP header followed by a
message.
An IP Datagram is a complete IP end-to-end transmission unit.
An IP Datagram is composed of one or more IP Fragments.
In this memo, the unqualified term Datagram should be understood
to refer to an IP Datagram.
IP Fragment
An IP Fragment is a component of an IP Datagram. An IP Fragment
consists of an IP header followed by all or part of the higher-
layer of the original IP Datagram.
One or more IP Fragments comprises a single IP Datagram.
In this memo, the unqualified term Fragment should be understood
to refer to an IP Fragment.
IP Packet
An IP Datagram or an IP Fragment.
In this memo, the unqualified term Packet should generally be
understood to refer to an IP Packet.
Logical [network] interface
We define a logical [network] interface to be a logical path,
distinguished by a unique IP address, to a connected network.
Martian Filtering
A packet that contains an invalid source or destination address
is considered to be martian and discarded.
MTU (Maximum Transmission Unit)
The size of the largest packet that can be transmitted or
received through a logical interface. This size includes the IP
header but does not include the size of any Link Layer headers
or framing.
Multicast
A packet that is destined for multiple hosts. See broadcast.
Multicast Address
A special type of address that is recognizable by multiple
hosts.
A Multicast Address is sometimes known as a Functional Address
or a Group Address.
Network Prefix
The portion of an IP Address that signifies a set of systems.
It is selected from the IP Address by logically ANDing a subnet
mask with the address, or (equivalently) setting the bits of the
address not among the most significant <prefix-length> bits of
the address to zero.
Originate
Packets can be transmitted by a router for one of two reasons:
1) the packet was received and is being forwarded or 2) the
router itself created the packet for transmission (such as route
advertisements). Packets that the router creates for
transmission are said to originate at the router.
Packet
A packet is the unit of data passed across the interface between
the Internet Layer and the Link Layer. It includes an IP header
and data. A packet may be a complete IP datagram or a fragment
of an IP datagram.
Path
The sequence of routers and (sub-)networks that a packet
traverses from a particular router to a particular destination
host. Note that a path is uni-directional; it is not unusual to
have different paths in the two directions between a given host
pair.
Physical Network
A Physical Network is a network (or a piece of an internet)
which is contiguous at the Link Layer. Its internal structure
(if any) is transparent to the Internet Layer.
In this memo, several media components that are connected using
devices such as bridges or repeaters are considered to be a
single Physical Network since such devices are transparent to
the IP.
Physical Network Interface
This is a physical interface to a Connected Network and has a
(possibly unique) Link-Layer address. Multiple Physical Network
Interfaces on a single router may share the same Link-Layer
address, but the address must be unique for different routers on
the same Physical Network.
Point to Point Line
A physical medium capable of connecting exactly two systems. In
this document, it is only used to refer to such a line when used
to connect IP entities. See General Purpose Serial Interface.
router
A special-purpose dedicated computer that connects several
networks. Routers switch packets between these networks in a
process known as forwarding. This process may be repeated
several times on a single packet by multiple routers until the
packet can be delivered to the final destination - switching the
packet from router to router to router... until the packet gets
to its destination.
RPF
Reverse Path Forwarding - A method used to deduce the next hops
for broadcast and multicast packets.
Silently Discard
This memo specifies several cases where a router is to Silently
Discard a received packet (or datagram). This means that the
router should discard the packet without further processing, and
that the router will not send any ICMP error message (see
Section [4.3.2]) as a result. However, for diagnosis of
problems, the router should provide the capability of logging
the error (see Section [1.3.3]), including the contents of the
silently discarded packet, and should record the event in a
statistics counter.
Silently Ignore
A router is said to Silently Ignore an error or condition if it
takes no action other than possibly generating an error report
in an error log or through some network management protocol, and
discarding, or ignoring, the source of the error. In
particular, the router does NOT generate an ICMP error message.
Sparse Mode
In multicast forwarding, two paradigms are possible: in Sparse
Mode forwarding, a network layer multicast datagram is forwarded
as a data link layer multicast frame to routers and hosts that
have asked for it. The initial forwarding state is the inverse
of dense-mode in that it assumes no part of the network wants
the data. See Dense Mode.
Specific-destination address
This is defined to be the destination address in the IP header
unless the header contains an IP broadcast or IP multicast
address, in which case the specific-destination is an IP address
assigned to the physical interface on which the packet arrived.
subnet
A portion of a network, which may be a physically independent
network, which shares a network address with other portions of
the network and is distinguished by a subnet number. A subnet
is to a network what a network is to an internet.
subnet number
A part of the internet address that designates a subnet. It is
ignored for the purposes internet routing, but is used for
intranet routing.
TOS
Type Of Service A field in the IP header that represents the
degree of reliability expected from the network layer by the
transport layer or application.
TTL
Time To Live A field in the IP header that represents how long a
packet is considered valid. It is a combination hop count and
timer value.
APPENDIX C. FUTURE DIRECTIONS
This appendix lists work that future revisions of this document may
wish to address.
In the preparation of Router Requirements, we stumbled across several
other architectural issues. Each of these is dealt with somewhat in
the document, but still ought to be classified as an open issue in
the IP architecture.
Most of the he topics presented here generally indicate areas where
the technology is still relatively new and it is not appropriate to
develop specific requirements since the community is still gaining
operational experience.
Other topics represent areas of ongoing research and indicate areas
that the prudent developer would closely monitor.
(1) SNMP Version 2
(2) Additional SNMP MIBs
(7) More detailed requirements for leaking routes between routing
protocols
(8) Router system security
(9) Routing protocol security
(10) Internetwork Protocol layer security. There has been extensive
work refining the security of IP since the original work writing
this document. This security work should be included in here.
(12) Load Splitting
(13) Sending fragments along different paths
(15) Multiple logical (sub)nets on the same wire. Router
Requirements does not require support for this. We made some
attempt to identify pieces of the architecture (e.g., forwarding
of directed broadcasts and issuing of Redirects) where the
wording of the rules has to be done carefully to make the right
thing happen, and tried to clearly distinguish logical
interfaces from physical interfaces. However, we did not study
this issue in detail, and we are not at all confident that all
the rules in the document are correct in the presence of
multiple logical (sub)nets on the same wire.
(15) Congestion control and resource management. On the advice of
the IETF's experts (Mankin and Ramakrishnan) we deprecated
(SHOULD NOT) Source Quench and said little else concrete
(Section 5.3.6).
(16) Developing a Link-Layer requirements document that would be
common for both routers and hosts.
(17) Developing a common PPP LQM algorithm.
(18) Investigate of other information (above and beyond section
[3.2]) that passes between the layers, such as physical network
MTU, mappings of IP precedence to Link Layer priority values,
etc.
(19) Should the Link Layer notify IP if address resolution failed
(just like it notifies IP when there is a Link Layer priority
value problem)?
(20) Should all routers be required to implement a DNS resolver?
(21) Should a human user be able to use a host name anywhere you can
use an IP address when configuring the router? Even in ping and
traceroute?
(22) Almquist's draft ruminations on the next hop and ruminations on
route leaking need to be reviewed, brought up to date, and
published.
(23) Investigation is needed to determine if a redirect message for
precedence is needed or not. If not, are the type-of-service
redirects acceptable?
(24) RIPv2 and RIP+CIDR and variable length network prefixes.
(25) BGP-4 CIDR is going to be important, and everyone is betting on
BGP-4. We can't avoid mentioning it. Probably need to describe
the differences between BGP-3 and BGP-4, and explore upgrade
issues...
(26) Loose Source Route Mobile IP and some multicasting may require
this. Perhaps it should be elevated to a SHOULD (per Fred
Baker's Suggestion).
APPENDIX D. Multicast Routing Protocols
Multicasting is a relatively new technology within the Internet
Protocol family. It is not widely deployed or commonly in use yet.
Its importance, however, is expected to grow over the coming years.
This Appendix describes some of the technologies being investigated
for routing multicasts through the Internet.
A diligent implementor will keep abreast of developments in this area
to properly develop multicast facilities.
This Appendix does not specify any standards or requirements.
D.1 Introduction
Multicast routing protocols enable the forwarding of IP multicast
datagrams throughout a TCP/IP internet. Generally these algorithms
forward the datagram based on its source and destination addresses.
Additionally, the datagram may need to be forwarded to several
multicast group members, at times requiring the datagram to be
replicated and sent out multiple interfaces.
The state of multicast routing protocols is less developed than the
protocols available for the forwarding of IP unicasts. Three
experimental multicast routing protocols have been documented for
TCP/IP. Each uses the IGMP protocol (discussed in Section [4.4]) to
monitor multicast group membership.
D.2 Distance Vector Multicast Routing Protocol - DVMRP
DVMRP, documented in [ROUTE:9], is based on Distance Vector or
Bellman-Ford technology. It routes multicast datagrams only, and
does so within a single Autonomous System. DVMRP is an
implementation of the Truncated Reverse Path Broadcasting algorithm
described in [ROUTE:10]. In addition, it specifies the tunneling of
IP multicasts through non-multicast-routing-capable IP domains.
D.3 Multicast Extensions to OSPF - MOSPF
MOSPF, currently under development, is a backward-compatible addition
to OSPF that allows the forwarding of both IP multicasts and unicasts
within an Autonomous System. MOSPF routers can be mixed with OSPF
routers within a routing domain, and they will interoperate in the
forwarding of unicasts. OSPF is a link-state or SPF-based protocol.
By adding link state advertisements that pinpoint group membership,
MOSPF routers can calculate the path of a multicast datagram as a
tree rooted at the datagram source. Those branches that do not
contain group members can then be discarded, eliminating unnecessary
datagram forwarding hops.
D.4 Protocol Independent Multicast - PIM
PIM, currently under development, is a multicast routing protocol
that runs over an existing unicast infrastructure. PIM provides for
both dense and sparse group membership. It is different from other
protocols, since it uses an explicit join model for sparse groups.
Joining occurs on a shared tree and can switch to a per-source tree.
Where bandwidth is plentiful and group membership is dense, overhead
can be reduced by flooding data out all links and later pruning
exception cases where there are no group members.
APPENDIX E Additional Next-Hop Selection Algorithms
Section [5.2.4.3] specifies an algorithm that routers ought to use
when selecting a next-hop for a packet.
This appendix provides historical perspective for the next-hop
selection problem. It also presents several additional pruning rules
and next-hop selection algorithms that might be found in the
Internet.
This appendix presents material drawn from an earlier, unpublished,
work by Philip Almquist; Ruminations on the Next Hop.
This Appendix does not specify any standards or requirements.
E.1. Some Historical Perspective
It is useful to briefly review the history of the topic, beginning
with what is sometimes called the "classic model" of how a router
makes routing decisions. This model predates IP. In this model, a
router speaks some single routing protocol such as RIP. The protocol
completely determines the contents of the router's Forwarding
Information Base (FIB). The route lookup algorithm is trivial: the
router looks in the FIB for a route whose destination attribute
exactly matches the network prefix portion of the destination address
in the packet. If one is found, it is used; if none is found, the
destination is unreachable. Because the routing protocol keeps at
most one route to each destination, the problem of what to do when
there are multiple routes that match the same destination cannot
arise.
Over the years, this classic model has been augmented in small ways.
With the deployment of default routes, subnets, and host routes, it
became possible to have more than one routing table entry which in
some sense matched the destination. This was easily resolved by a
consensus that there was a hierarchy of routes: host routes should be
preferred over subnet routes, subnet routes over net routes, and net
routes over default routes.
With the deployment of technologies supporting variable length subnet
masks (variable length network prefixes), the general approach
remained the same although its description became a little more
complicated; network prefixes were introduced as a conscious
simplification and regularization of the architecture. We now say
that each route to a network prefix route has a prefix length
associated with it. This prefix length indicates the number of bits
in the prefix. This may also be represented using the classical
subnet mask. A route cannot be used to route a packet unless each
significant bit in the route's network prefix matches the
corresponding bit in the packet's destination address. Routes with
more bits set in their masks are preferred over routes that have
fewer bits set in their masks. This is simply a generalization of
the hierarchy of routes described above, and will be referred to for
the rest of this memo as choosing a route by preferring longest
match.
Another way the classic model has been augmented is through a small
amount of relaxation of the notion that a routing protocol has
complete control over the contents of the routing table. First,
static routes were introduced. For the first time, it was possible
to simultaneously have two routes (one dynamic and one static) to the
same destination. When this happened, a router had to have a policy
(in some cases configurable, and in other cases chosen by the author
of the router's software) which determined whether the static route
or the dynamic route was preferred. However, this policy was only
used as a tie-breaker when longest match didn't uniquely determine
which route to use. Thus, for example, a static default route would
never be preferred over a dynamic net route even if the policy
preferred static routes over dynamic routes.
The classic model had to be further augmented when inter-domain
routing protocols were invented. Traditional routing protocols came
to be called "interior gateway protocols" (IGPs), and at each
Internet site there was a strange new beast called an "exterior
gateway", a router that spoke EGP to several "BBN Core Gateways" (the
routers that made up the Internet backbone at the time) at the same
time as it spoke its IGP to the other routers at its site. Both
protocols wanted to determine the contents of the router's routing
table. Theoretically, this could result in a router having three
routes (EGP, IGP, and static) to the same destination. Because of
the Internet topology at the time, it was resolved with little debate
that routers would be best served by a policy of preferring IGP
routes over EGP routes. However, the sanctity of longest match
remained unquestioned: a default route learned from the IGP would
never be preferred over a net route from learned EGP.
Although the Internet topology, and consequently routing in the
Internet, have evolved considerably since then, this slightly
augmented version of the classic model has survived intact to this
day in the Internet (except that BGP has replaced EGP). Conceptually
(and often in implementation) each router has a routing table and one
or more routing protocol processes. Each of these processes can add
any entry that it pleases, and can delete or modify any entry that it
has created. When routing a packet, the router picks the best route
using longest match, augmented with a policy mechanism to break ties.
Although this augmented classic model has served us well, it has a
number of shortcomings:
o It ignores (although it could be augmented to consider) path
characteristics such as quality of service and MTU.
o It doesn't support routing protocols (such as OSPF and Integrated
IS-IS) that require route lookup algorithms different than pure
longest match.
o There has not been a firm consensus on what the tie-breaking
mechanism ought to be. Tie-breaking mechanisms have often been
found to be difficult if not impossible to configure in such a way
that the router will always pick what the network manger considers
to be the "correct" route.
E.2. Additional Pruning Rules
Section [5.2.4.3] defined several pruning rules to use to select
routes from the FIB. There are other rules that could also be
used.
o OSPF Route Class
Routing protocols that have areas or make a distinction between
internal and external routes divide their routes into classes
by the type of information used to calculate the route. A
route is always chosen from the most preferred class unless
none is available, in which case one is chosen from the second
most preferred class, and so on. In OSPF, the classes (in
order from most preferred to least preferred) are intra-area,
inter-area, type 1 external (external routes with internal
metrics), and type 2 external. As an additional wrinkle, a
router is configured to know what addresses ought to be
accessible using intra-area routes, and will not use inter-
area or external routes to reach these destinations even when
no intra-area route is available.
More precisely, we assume that each route has a class
attribute, called route.class, which is assigned by the routing
protocol. The set of candidate routes is examined to determine
if it contains any for which route.class = intra-area. If so,
all routes except those for which route.class = intra-area are
discarded. Otherwise, router checks whether the packet's
destination falls within the address ranges configured for the
local area. If so, the entire set of candidate routes is
deleted. Otherwise, the set of candidate routes is examined to
determine if it contains any for which route.class = inter-
area. If so, all routes except those for which route.class =
inter-area are discarded. Otherwise, the set of candidate
routes is examined to determine if it contains any for which
route.class = type 1 external. If so, all routes except those
for which route.class = type 1 external are discarded.
o IS-IS Route Class
IS-IS route classes work identically to OSPF's. However, the
set of classes defined by Integrated IS-IS is different, such
that there isn't a one-to-one mapping between IS-IS route
classes and OSPF route classes. The route classes used by
Integrated IS-IS are (in order from most preferred to least
preferred) intra-area, inter-area, and external.
The Integrated IS-IS internal class is equivalent to the OSPF
internal class. Likewise, the Integrated IS-IS external class
is equivalent to OSPF's type 2 external class. However,
Integrated IS-IS does not make a distinction between inter-area
routes and external routes with internal metrics - both are
considered to be inter-area routes. Thus, OSPF prefers true
inter-area routes over external routes with internal metrics,
whereas Integrated IS-IS gives the two types of routes equal
preference.
o IDPR Policy
A specific case of Policy. The IETF's Inter-domain Policy
Routing Working Group is devising a routing protocol called
Inter-Domain Policy Routing (IDPR) to support true policy-based
routing in the Internet. Packets with certain combinations of
header attributes (such as specific combinations of source and
destination addresses or special IDPR source route options) are
required to use routes provided by the IDPR protocol. Thus,
unlike other Policy pruning rules, IDPR Policy would have to be
applied before any other pruning rules except Basic Match.
Specifically, IDPR Policy examines the packet being forwarded
to ascertain if its attributes require that it be forwarded
using policy-based routes. If so, IDPR Policy deletes all
routes not provided by the IDPR protocol.
E.3 Some Route Lookup Algorithms
This section examines several route lookup algorithms that are in
use or have been proposed. Each is described by giving the
sequence of pruning rules it uses. The strengths and weaknesses
of each algorithm are presented
E.3.1 The Revised Classic Algorithm
The Revised Classic Algorithm is the form of the traditional
algorithm that was discussed in Section [E.1]. The steps of this
algorithm are:
1. Basic match
2. Longest match
3. Best metric
4. Policy
Some implementations omit the Policy step, since it is needed only
when routes may have metrics that are not comparable (because they
were learned from different routing domains).
The advantages of this algorithm are:
(1) It is widely implemented.
(2) Except for the Policy step (which an implementor can choose to
make arbitrarily complex) the algorithm is simple both to
understand and to implement.
Its disadvantages are:
(1) It does not handle IS-IS or OSPF route classes, and therefore
cannot be used for Integrated IS-IS or OSPF.
(2) It does not handle TOS or other path attributes.
(3) The policy mechanisms are not standardized in any way, and are
therefore are often implementation-specific. This causes
extra work for implementors (who must invent appropriate
policy mechanisms) and for users (who must learn how to use
the mechanisms. This lack of a standardized mechanism also
makes it difficult to build consistent configurations for
routers from different vendors. This presents a significant
practical deterrent to multi-vendor interoperability.
(4) The proprietary policy mechanisms currently provided by
vendors are often inadequate in complex parts of the
Internet.
(5) The algorithm has not been written down in any generally
available document or standard. It is, in effect, a part of
the Internet Folklore.
E.3.2 The Variant Router Requirements Algorithm
Some Router Requirements Working Group members have proposed a
slight variant of the algorithm described in the Section
[5.2.4.3]. In this variant, matching the type of service
requested is considered to be more important, rather than less
important, than matching as much of the destination address as
possible. For example, this algorithm would prefer a default
route that had the correct type of service over a network route
that had the default type of service, whereas the algorithm in
[5.2.4.3] would make the opposite choice.
The steps of the algorithm are:
1. Basic match
2. Weak TOS
3. Longest match
4. Best metric
5. Policy
Debate between the proponents of this algorithm and the regular
Router Requirements Algorithm suggests that each side can show
cases where its algorithm leads to simpler, more intuitive routing
than the other's algorithm does. This variant has the same set of
advantages and disadvantages that the algorithm specified in
[5.2.4.3] does, except that pruning on Weak TOS before pruning on
Longest Match makes this algorithm less compatible with OSPF and
Integrated IS-IS than the standard Router Requirements Algorithm.
E.3.3 The OSPF Algorithm
OSPF uses an algorithm that is virtually identical to the Router
Requirements Algorithm except for one crucial difference: OSPF
considers OSPF route classes.
The algorithm is:
1. Basic match
2. OSPF route class
3. Longest match
4. Weak TOS
5. Best metric
6. Policy
Type of service support is not always present. If it is not
present then, of course, the fourth step would be omitted
This algorithm has some advantages over the Revised Classic
Algorithm:
(1) It supports type of service routing.
(2) Its rules are written down, rather than merely being a part of
the Internet folklore.
(3) It (obviously) works with OSPF.
However, this algorithm also retains some of the disadvantages of
the Revised Classic Algorithm:
(1) Path properties other than type of service (e.g., MTU) are
ignored.
(2) As in the Revised Classic Algorithm, the details (or even the
existence) of the Policy step are left to the discretion of
the implementor.
The OSPF Algorithm also has a further disadvantage (which is not
shared by the Revised Classic Algorithm). OSPF internal (intra-
area or inter-area) routes are always considered to be superior to
routes learned from other routing protocols, even in cases where
the OSPF route matches fewer bits of the destination address.
This is a policy decision that is inappropriate in some networks.
Finally, it is worth noting that the OSPF Algorithm's TOS support
suffers from a deficiency in that routing protocols that support
TOS are implicitly preferred when forwarding packets that have
non-zero TOS values. This may not be appropriate in some cases.
E.3.4 The Integrated IS-IS Algorithm
Integrated IS-IS uses an algorithm that is similar to but not quite
identical to the OSPF Algorithm. Integrated IS-IS uses a different
set of route classes, and differs slightly in its handling of type of
service. The algorithm is:
1. Basic Match
2. IS-IS Route Classes
3. Longest Match
4. Weak TOS
5. Best Metric
6. Policy
Although Integrated IS-IS uses Weak TOS, the protocol is only capable
of carrying routes for a small specific subset of the possible values
for the TOS field in the IP header. Packets containing other values
in the TOS field are routed using the default TOS.
Type of service support is optional; if disabled, the fourth step
would be omitted. As in OSPF, the specification does not include the
Policy step.
This algorithm has some advantages over the Revised Classic
Algorithm:
(1) It supports type of service routing.
(2) Its rules are written down, rather than merely being a part of
the Internet folklore.
(3) It (obviously) works with Integrated IS-IS.
However, this algorithm also retains some of the disadvantages of the
Revised Classic Algorithm:
(1) Path properties other than type of service (e.g., MTU) are
ignored.
(2) As in the Revised Classic Algorithm, the details (or even the
existence) of the Policy step are left to the discretion of the
implementor.
(3) It doesn't work with OSPF because of the differences between IS-
IS route classes and OSPF route classes. Also, because IS-IS
supports only a subset of the possible TOS values, some obvious
implementations of the Integrated IS-IS algorithm would not
support OSPF's interpretation of TOS.
The Integrated IS-IS Algorithm also has a further disadvantage (which
is not shared by the Revised Classic Algorithm): IS-IS internal
(intra-area or inter-area) routes are always considered to be
superior to routes learned from other routing protocols, even in
cases where the IS-IS route matches fewer bits of the destination
address and doesn't provide the requested type of service. This is a
policy decision that may not be appropriate in all cases.
Finally, it is worth noting that the Integrated IS-IS Algorithm's TOS
support suffers from the same deficiency noted for the OSPF
Algorithm.
Security Considerations
Although the focus of this document is interoperability rather than
security, there are obviously many sections of this document that
have some ramifications on network security.
Security means different things to different people. Security from a
router's point of view is anything that helps to keep its own
networks operational and in addition helps to keep the Internet as a
whole healthy. For the purposes of this document, the security
services we are concerned with are denial of service, integrity, and
authentication as it applies to the first two. Privacy as a security
service is important, but only peripherally a concern of a router -
at least as of the date of this document.
In several places in this document there are sections entitled ...
Security Considerations. These sections discuss specific
considerations that apply to the general topic under discussion.
Rarely does this document say do this and your router/network will be
secure. More likely, it says this is a good idea and if you do it,
it *may* improve the security of the Internet and your local system
in general.
Unfortunately, this is the state-of-the-art AT THIS TIME. Few if any
of the network protocols a router is concerned with have reasonable,
built-in security features. Industry and the protocol designers have
been and are continuing to struggle with these issues. There is
progress, but only small baby steps such as the peer-to-peer
authentication available in the BGP and OSPF routing protocols.
In particular, this document notes the current research into
developing and enhancing network security. Specific areas of
research, development, and engineering that are underway as of this
writing (December 1993) are in IP Security, SNMP Security, and common
authentication technologies.
Notwithstanding all the above, there are things both vendors and
users can do to improve the security of their router. Vendors should
get a copy of Trusted Computer System Interpretation [INTRO:8]. Even
if a vendor decides not to submit their device for formal
verification under these guidelines, the publication provides
Excellent guidance on general security design and practices for
computing devices.
APPENDIX F: HISTORICAL ROUTING PROTOCOLS
Certain routing protocols are common in the Internet, but the authors
of this document cannot in good conscience recommend their use. This
is not because they do not work correctly, but because the
characteristics of the Internet assumed in their design (simple
routing, no policy, a single "core router" network under common
administration, limited complexity, or limited network diameter) are
not attributes of today's Internet. Those parts of the Internet that
still use them are generally limited "fringe" domains with limited
complexity.
As a matter of good faith, collected wisdom concerning their
implementation is recorded in this section.
F.1 EXTERIOR GATEWAY PROTOCOL - EGP
F.1.1 Introduction
The Exterior Gateway Protocol (EGP) specifies an EGP that 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 that limits routers to advertising only
those networks that 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.
F.1.2 Protocol Walk-through
Indirect Neighbors: RFC-888, page 26
An implementation of EGP MUST include indirect neighbor
support.
Polling Intervals: RFC-904, page 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, page 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 that are reachable through 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 that were learned
through 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 through a particular router. If more than 255
networks are reachable at a particular distance through 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 through a particular router, the router's
address is listed as many times as necessary to include all the
blocks in the update.
Unsolicited Updates: RFC-904, page 16
If a network is shared with the peer, an implementation MUST send an
unsolicited update upon entry to the Up state if the source network
is the shared network.
Neighbor Reachability: RFC-904, page 6, 13-15
The table on page 6 that 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, page 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, pages 6, 12, 13
An EGP implementation MUST include support for the abort timer (as
documented in section 4.1.4 of RFC-904). An implementation SHOULD
use the abort timer in the Idle state to automatically issue a Start
event to restart the protocol machine. Recommended values are P4 for
a critical error (Administratively prohibited, Protocol Violation and
Parameter Problem) and P5 for all others. The abort timer SHOULD NOT
be started when a Stop event was manually initiated (such as through
a network management protocol).
Cease command received in Idle state: RFC-904, page 13
When the EGP state machine is in the Idle state, it MUST reply to
Cease commands with a Cease-ack response.
Hello Polling Mode: RFC-904, page 11
An EGP implementation MUST include support for both active and
passive polling modes.
Neighbor Acquisition Messages: RFC-904, page 18
As noted the Hello and Poll Intervals should only be present in
Request and Confirm messages. Therefore the length of an EGP
Neighbor Acquisition Message is 14 bytes for a Request or Confirm
message and 10 bytes for a Refuse, Cease or Cease-ack message.
Implementations MUST NOT send 14 bytes for Refuse, Cease or Cease-ack
messages but MUST allow for implementations that send 14 bytes for
these messages.
Sequence Numbers: RFC-904, page 10
Response or indication packets received with a sequence number not
equal to S MUST be discarded. The send sequence number S MUST be
incremented just before the time a Poll command is sent and at no
other times.
F.2 ROUTING INFORMATION PROTOCOL - RIP
F.2.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. A router
implementing RIP SHOULD implement RIP Version 2 [ROUTE:?], as it
supports CIDR routes. If occasional access networking is in use, a
router implementing RIP SHOULD implement Demand RIP [ROUTE:?].
Another common use for RIP is as a router discovery protocol.
Section [4.3.3.10] briefly touches upon this subject.
F.2.2 Protocol Walk-Through
Dealing with changes in topology: [ROUTE:3], page 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 too 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
to promote faster recovery from failures.
IMPLEMENTATION
There is a very simple mechanism that 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 that 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], page 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 that includes routes learned from
a router sent to that router, but sets their metric to infinity.
Because of the routing overhead that 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 time in which it sends reverse routes
at an infinite metric.
IMPLEMENTATION
Each of the following algorithms can be used to limit the time for
which poisoned reverse is applied to a route. The first algorithm
is more complex but does a more thorough 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.