(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.
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 FIB. The route
lookup algorithm is trivial: the router looks in the FIB for a route
whose destination attribute exactly matches the network number
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
which match the same destination cannot arise.
Over the years, this classic model has been augmented in small ways.
With the advent 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 advent of variable length subnet masks, the general approach
remained the same although its description became a little more
complicated. We now say that each route has a bit mask associated
with it. If a particular bit in a route's bit mask is set, the
corresponding bit in the route's destination attribute is
significant. A route cannot be used to route a packet unless each
significant bit in the route's destination attribute matches the
corresponding bit in the packet's destination address, and routes
with more bits set in their masks are preferred over routes which
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 which spoke EGP to several "BBN Core Gateways"
(the routers which 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 pretty much
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 which have areas or make a distinction between
internal and external routes divide their routes into classes,
where classes are rank-ordered in terms of preference. 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 via 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 which 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 which had the correct type of service over a network route
which 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. In general, 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 which 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 which support
TOS are implicitly preferred when forwarding packets which 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 which is similar to but not
quite identical to the OSPF Algorithm. Integrated IS-IS uses a
different set of route classes, and also 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 which 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 of 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.
Acknowledgments
O that we now had here
But one ten thousand of those men in England
That do no work to-day!
What's he that wishes so?
My cousin Westmoreland? No, my fair cousin:
If we are mark'd to die, we are enow
To do our country loss; and if to live,
The fewer men, the greater share of honour.
God's will! I pray thee, wish not one man more.
By Jove, I am not covetous for gold,
Nor care I who doth feed upon my cost;
It yearns me not if men my garments wear;
Such outward things dwell not in my desires:
But if it be a sin to covet honour,
I am the most offending soul alive.
No, faith, my coz, wish not a man from England:
God's peace! I would not lose so great an honour
As one man more, methinks, would share from me
For the best hope I have. O, do not wish one more!
Rather proclaim it, Westmoreland, through my host,
That he which hath no stomach to this fight,
Let him depart; his passport shall be made
And crowns for convoy put into his purse:
We would not die in that man's company
That fears his fellowship to die with us.
This day is called the feast of Crispian:
He that outlives this day, and comes safe home,
Will stand a tip-toe when the day is named,
And rouse him at the name of Crispian.
He that shall live this day, and see old age,
Will yearly on the vigil feast his neighbours,
And say 'To-morrow is Saint Crispian:'
Then will he strip his sleeve and show his scars.
And say 'These wounds I had on Crispin's day.'
Old men forget: yet all shall be forgot,
But he'll remember with advantages
What feats he did that day: then shall our names.
Familiar in his mouth as household words
Harry the king, Bedford and Exeter,
Warwick and Talbot, Salisbury and Gloucester,
Be in their flowing cups freshly remember'd.
This story shall the good man teach his son;
And Crispin Crispian shall ne'er go by,
From this day to the ending of the world,
But we in it shall be remember'd;
We few, we happy few, we band of brothers;
For he to-day that sheds his blood with me
Shall be my brother; be he ne'er so vile,
This day shall gentle his condition:
And gentlemen in England now a-bed
Shall think themselves accursed they were not here,
And hold their manhoods cheap whiles any speaks
That fought with us upon Saint Crispin's day.
This memo is a product of the IETF's Router Requirements Working Group.
A memo such as this one is of necessity the work of many more people
than could be listed here. A wide variety of vendors, network managers,
and other experts from the Internet community graciously contributed
their time and wisdom to improve the quality of this memo. The editor
wishes to extend sincere thanks to all of them.
The current editor also wishes to single out and extend his heartfelt
gratitude and appreciation to the original editor of this document;
Philip Almquist. Without Philip's work, both as the original editor and
as the Chair of the working group, this document would not have been
produced.
Philip Almquist, Jeffrey Burgan, Frank Kastenholz, and Cathy Wittbrodt
each wrote major chapters of this memo. Others who made major
contributions to the document included Bill Barns, Steve Deering, Kent
England, Jim Forster, Martin Gross, Jeff Honig, Steve Knowles, Yoni
Malachi, Michael Reilly, and Walt Wimer.
Additional text came from Art Berggreen, John Cavanaugh, Ross Callon,
John Lekashman, Brian Lloyd, Gary Malkin, Milo Medin, John Moy, Craig
Partridge, Stephanie Price, Yakov Rekhter, Steve Senum, Richard Smith,
Frank Solensky, Rich Woundy, and others who have been inadvertently
overlooked.
Some of the text in this memo has been (shamelessly) plagiarized from
earlier documents, most notably RFC-1122 by Bob Braden and the Host
Requirements Working Group, and RFC-1009 by Bob Braden and Jon Postel.
The work of these earlier authors is gratefully acknowledged.
Jim Forster was a co-chair of the Router Requirements Working Group
during its early meetings, and was instrumental in getting the group off
to a good start. Jon Postel, Bob Braden, and Walt Prue also contributed
to the success by providing a wealth of good advice prior to the group's
first meeting. Later on, Phill Gross, Vint Cerf, and Noel Chiappa all
provided valuable advice and support.
Mike St. Johns coordinated the Working Group's interactions with the
security community, and Frank Kastenholz coordinated the Working Group's
interactions with the network management area. Allison Mankin and K.K.
Ramakrishnan provided expertise on the issues of congestion control and
resource allocation.
Many more people than could possibly be listed or credited here
participated in the deliberations of the Router Requirements Working
Group, either through electronic mail or by attending meetings.
However, the efforts of Ross Callon and Vince Fuller in sorting out the
difficult issues of route choice and route leaking are especially
acknowledged.
The previous editor, Philip Almquist, wishes to extend his thanks and
appreciation to his former employers, Stanford University and BARRNet,
for allowing him to spend a large fraction (probably far more than they
ever imagined when he started on this) of his time working on this
project.
The current editor wishes to thank his employer, FTP Software, for
allowing him to spend the time necessary to finish this document.
Editor's Address
The address of the current editor of this document is
Frank J. Kastenholz
FTP Software
2 High Street
North Andover, MA, 01845-2620
USA
Phone: +1 508-685-4000
EMail: kasten@ftp.com