updated nexthop

[[e-mail]]

Hi,
	Here is a minor tweek on Philips Next Hop paper.  Although Fred has
	added many of these ideas into the existing doc, there are at least two
	other RFCs that reference this paper directly.  Would there be any
	problem w/ sending this on the informational track?



Router Requirements Working Group		Philip Almquist
INTERNET DRAFT					March 25, 1993
						Revised/Updated Jan1995

			Ruminations on the Next Hop

Status of This Memo

This document is an Internet Draft.  Internet Drafts are working
documents of the Internet Engineering Task Force (IETF), its Areas,
and its Working Groups.  Note that other groups may also distribute
working documents as Internet Drafts.
 
Internet Drafts are draft documents valid for a maximum of six months.
Internet Drafts may be updated, replaced, or obsoleted by other
documents at any time.  It is not appropriate to use Internet Drafts
as reference material or to cite them other than as "work in progress."

To learn the current status of any Internet-Draft, please check
the ``1id-abstracts.txt'' listing contained in the Internet-
Drafts Shadow Directories on ftp.is.co.za (Africa),
nic.nordu.net (Europe), munnari.oz.au (Pacific Rim),
ds.internic.net (US East Coast), or ftp.isi.edu (US West Coast).

Distribution of this memo is unlimited.

Summary

This memo discusses how routers do, can, and should decide how to use
the routing information available to them to route packets. It is
particularly concerned with the problems of border routers and other
routers which have to choose from among routes learned from multiple
routing domains, often using different routing protocols.

Although many of the details of this paper are specific to the
problem of forwarding Internet Protocol (IP) packets, I believe that
the problems identified and the general approach to the solution
would also be relevant to those working with CLNP or other
connectionless Network Layer protocols.

Acknowledgments

This memo owes considerable debt to the IETF's Router Requirements
Working Group, which started me to thinking about the issues in this
paper and also reviewed several earlier drafts. I am particularly
indebted to Ross Callon, who helped me understand enough about area
routing to understand why the algorithm in section 4.2 is inadequate,
and also pointed out several errors in my description of Integrated
IS-IS. Vint Cerf and Noel Chiappa provided additional useful
comments.  This memo also owes considerable debt to Stanford
University and BARRNet, my former employers, for supporting much of
the work on this memo.

1. Introduction

The fundamental thing that a router does is to receive packets,
examine their headers, and decide where to send them next. I have
chaired several meetings at which a group of experts (the Internet
Engineering Task Force's Router Requirements Working Group) attempted
to reach consensus on a precise description of how routers should
make that decision. Lengthy and often heated debate produced little
concrete agreement. I was rather fascinated to discover that this
seemingly simple process of deciding where to send the packet next is
apparently not well understood, and in fact seems to hide some
difficult open questions.

This memo attempts to carefully examine how a router should use the
routing information available to it to decide how to route packets. A
companion document, "Ruminations on Route Leaking" [1], discusses the
related issue of how a router passes on routes available to it to
other routers.

Readers should be forewarned that the algorithms given in this memo
are rather different than the ones that good router implementor would
use.  The reason for this is that a memo such as this one needs to
describe the actions taken by routers in a way that they is concise,
easy to understand, and relatively independent of the details of the
particular internet and routing protocols being used. A good
implementor, on the other hand, will choose algorithms which produce
the same results as those in this memo but do so more quickly by
sacrificing a certain amount of simplicity or generality.  I believe
that this memo does not recommend anything that could not be
implemented efficiently but (except for the all-too-brief discussion
in Section 8) the art of efficient router implementation is outside
of the scope of this memo.



1.1 Overview of the Routing Function

Each router maintains a "forwarding information base (FIB)", a
conceptual database of all routes known to the router.  In order to
allow the router to choose from among the routes in the FIB, each
route has various attributes associated with it.

In order to maintain its FIB, a router generally belongs to one or
more "routing domains."  A routing domain is a collection of routers
which coordinate their routing information using a routing protocol.
Each router adds routes to and deletes routes from its FIB based on
rules prescribed by the protocol.

Most routers also allow the router's manager to manipulate the
contents of the FIB through configuration or network management
commands. For purposes of this memo, a router whose FIB contains
routes added by such manual means can be thought of as being a member
of its own (degenerate) routing domain, referred to as a "static
routing domain", in addition to any routing domain(s) it may be a
member of by virtue of its use of routing protocols. To facilitate
route leaking [1] and the functions described in Sections 6.2 and
6.5, a router may benefit from an ability to divide its static routes
among multiple static routing domains.

When the router receives a packet to be forwarded, it examines
attributes of the packet and compares them to values of the
attributes of routes in the FIB. This allows the router to determine
the appropriate route for the packet (or to determine that the packet
must be discarded because no matching route is available).

Because the size of the FIB would likely be unwieldy if it contained
a route for each possible combination of attributes a packet might
have, comparing the attributes of the packet to the attributes of the
routes in the FIB is not usually a straightforward equality test of
the attributes.  Instead, the router uses a "route lookup algorithm"
to determine which route best matches the attributes of the packet.

It is important to note that the FIB talked about in this memo is not
exactly the same as the forwarding table found in most routers.  The
FIB contains all of the current routing information which has been
provided to the router by its routing domains. A router can often
determine that its route lookup algorithm would never choose certain
routes, and that it may therefore safely discard them. The fact that
real implementations usually partially precompute the results of the
route lookup algorithm in this manner is an important bit of
implementation-related complexity which is nonetheless ignored
throughout most of this memo.

1.2 The Problem

As I shall discuss in greater detail shortly, there has traditionally
been a consensus on an appropriate route lookup algorithm.
Unfortunately, a number of factors have conspired to render that
algorithm obsolete:

- New routing protocols are being developed which require different,
  incompatible route lookup algorithms. Examples of such protocols in
  the Internet protocol suite include OSPF [6] and Integrated IS-IS [3].

- The traditional route lookup algorithm makes its decision based on
  only one attribute of the packet being forwarded: its destination
  address. There is a growing consensus that the algorithm should also
  consider the Network Layer quality of service (TOS) requested by the
  packet. Some people believe that additional attributes should also be
  considered in the forwarding decision.

- The traditional route lookup algorithm assumes that a router is a
  part of (at most) one routing domain, and therefore contains no
  mechanism for choosing among routes to the same destination learned
  from different routing protocols (or multiple instances of the same
  routing protocol).  To solve this, router implementors have had to
  invent a variety of policy mechanisms.  Unfortunately, these
  mechanisms are highly implementation- dependent, contributing to the
  difficulties of building a network using routers from multiple
  vendors.

1.3 Outline of this Memo

Section 2 briefly recaps the history of this topic and describes the
traditional view of how routers pick routes when routing packets.

Section 3 provides a generic model of how route lookup algorithms
work and describes the component rules from which such algorithms are
constructed.

Section 4 gives concise but fairly precise descriptions of several
route lookup algorithms which are used or have been proposed. It also
discusses the good and bad points of each.

Section 5 considers the lessons we might learn from Section 4. Is
there a single "correct" route lookup algorithm? How could a router
choose an appropriate route when it learns routes from several
routing protocols simultaneously? Several mechanisms are discussed,
and one of them (the "Meta-lookup Algorithm."  approach) is picked as
the most workable alternative.

Sections 6 and 7 considers the Meta-lookup Algorithm approach in
detail. A specific meta-lookup algorithm is proposed, along with some
policy controls.

Section 8 briefly considers efficient implementation.

2. Some Historical Perspective

It is useful to briefly review the history of our topic. beginning
with what I think of as the "classic model" of how a router makes
routing decisions. This model predates IP (see, for example,
reference [9]). Under this model, a router speaks some single routing
protocol such as RIP [4]. 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 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 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 [7] 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 for routers which use the
OSPF or the Integrated IS-IS protocols, which will be discussed
shortly). 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:

- It ignores (although it could be augmented to consider) path
  characteristics such as quality of service and MTU.

- It doesn't support routing protocols (such as OSPF and Integrated
  IS-IS) thatrequire route lookup algorithms different than pure
  longest match.

- 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.

3. Route Lookup Algorithms

A route lookup algorithm chooses the best route (if there is one) for
a packet from those available in the FIB.

Conceptually, any route lookup algorithm starts out with a set of
candidate routes which consists of the entire contents of the FIB.
The algorithm consists of a series of steps which discard routes from
the set. In this memo, 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.

Some steps are mandatory, and must be applied even if the set has
already been reduced to a single route. Some algorithms also contain
optional steps, which may be skipped if the set has already been
reduced to a single route. The steps must generally be applied in
order, since rearranging the steps can change the result.

There are a number of common pruning rules. The route lookup
algorithms in use generally use some combination of these rules.

Basic Match
	This step discards any routes to destinations other than the
	destination of the packet. For example, if a packet was addressed to
	36.144.2.5, this step would discard a route to net 128.12.0.0 but
	would retain any routes to net 36.0.0.0, any routes to subnet
	36.144.0.0, and any default routes.

	More precisely, we assume that each route has a destination
	attribute, which we'll call "route.dest", and a corresponding mask,
	which we'll call "route.mask", to specify which bits of route.dest
	are significant.  We'll call the IP destination address of the packet
	being routed "ip.dest". This step discards all routes from the set of
	candidate routes except those for which (route.dest & route.mask) =
	(ip.dest & route.mask).  This is (logically, at least) the first step
	performed by any route lookup algorithm.

Longest Match
	This step was described on page 5.

	The precise definition of Longest Match is a refinement of Basic
	Match, described above. After Basic Match pruning is performed, the
	remaining routes are examined to determine the maximum number of bits
	set in any of their route.mask attributes. The step then discards
	from the set of candidate routes any routes which have fewer than
	that maximum number of bits set in their route.mask attributes.

Weak TOS

	There is a growing consensus that routers should consider quality
	of service requested when making their routing decisions. This could
	be done in a number of ways, but the one used in IP is the one I
	refer to as Weak T OS. Under this method, a route which has the exact
	TOS requested is used if there is one; otherwise, a route with the
	default (0000) TOS is used if there is one. Routes which have other
	TOS values are never used, even when they are the only available
	routes to the packet's destination.

	More precisely, we assume that each route has a type of service
	attribute, which we'll call "route.tos", whose possible values are
	assumed to be identical to those used in the TOS field of the IP
	header. Routing protocols which distribute TOS information fill in
	route.tos appropriately in routes they add to the FIB; routes from
	other routing protocols are treated as if they has the default TOS.
	We'll call the TOS field in the IP header of the packet being routed
	"ip.tos". The set of candidate routes is examined to determine if it
	contains any routes for which route.tos = ip.tos. If so, all routes
	except those for which route.tos = ip.tos are discarded. If not, all
	routes except those for which route.tos = 0000 are discarded from the
	set of candidate routes. Additional discussion of routing based on
	Weak TOS may be found in [2].

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.

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.

Best Metric
	Routes have metrics which allow a router to compare the relative
	goodness of otherwise equally attractive candidate routes. However ,
	since metrics are meaningful only within a routing domain, it makes
	no sense to compare the metrics of routes learned from different
	routing domains.

	More precisely, we assume that each route has a metric attribute,
	called route.metric, and a routing domain identifier, called
	route.domain. Each member of the set of candidate routes is compared
	with each other member of the set. If route.domain is equal for the
	two routes and route.metric is strictly "inferior" for one than the
	other, the one with the inferior metric is discarded from the set.
	The determination of "inferior" is usually by a simple arithmetic
	comparison, though some protocols may have structured metrics
	requiring more complex comparisons.

Policy
	Policy is sort of a catch-all to make up for the fact that the
	previously listed rules are often inadequate to chose from among the
	possible routes. Policy pruning rules are extremely vendor-specific.

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) [8] 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.


4  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 enumerated. 

4.1 The Revised Classic Algorithm

The Revised Classic Algorithm is the current version of the
traditional algorithm which was discussed on page 5. The steps of
this algorithm are:

1.  Basic match
2.  Longest match
3.  Best metric
4.  Policy

Some implementors 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.

As I pointed out in Section 1.2, 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 mechanismsficult to create
	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.

4.2 The Router Requirements Algorithm

The IETF Router Requirements Working Group has produced a number of
draft versions of an RFC-1009 replacement. The early drafts mandated
a route lookup algorithm which I will call the "Router Requirements
Algorithm." This algorithm is similar to the Revised Classic
Algorithm, with two important differences.  The first is that it
includes support for type of service routing. The second is that it
attempts to extend the Revised Classic Algorithm to explicitly
support routers which are in more than one routing domain, primarily
by standardizing the policy mechanisms (but allowing implementors to
supplement the standard mechanisms with proprietary ones).

The steps in the Router Requirements Algorithm are:
1.  Basic match
2.  Longest match
3.  Weak TOS
4.  Best metric
5.  Policy

This model 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.  Partial standardization of the policy step (hopefully) would make
	life a lot easier for managers of those parts of the Internet where
	routing is complex.

However, this algorithm retains some of the disadvantages of the
Revised Classic Algorithm:
1.  It does not handle IS-IS or OSPF route classes, and therefore
	cannot be used for Integrated IS-IS or OSPF.
2.  Path properties other than type of service (e.g. MTU) are ignored.

It is also worth noting a deficiency in the way that TOS is
supported: 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.

4.3 The Variant Router Requirements Algorithm

Some Router Requirements Working Group members have proposed a slight
variant of the algorithm described in the previous section. 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 the previous section 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 are described in the previous
section, except that pruning on W eak TOS before pruning on Longest
Match makes this algorithm less compatible with OSPF and Integrated
IS-IS than the standard Router Requirements Algorithm.

4.4 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.  Also, although I have listed a Policy
step in the algorithm, the OSPF specification does not admit to the
existence of such a step.

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 optional; if disabled, 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 Policy step is left to the discretion of the implementor.

The OSPF Algorithm also has a further disadvantage (which is not
shared by the Revised Classic Algorithm):
1.  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 the same deficiency noted at the end of Section 4.2.

4.5 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. Lonhgest 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 (defined in Section
3.5 of [3] and amended by Appendix A.4 of [2]) 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 is left to the discretion of the
	implementor.
3.  It doesn't work with OSPF because of the dif ferences 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):

1.  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 at the end of Section
4.2.

5. The Problem Revisited

In the previous section, we examined the routing algorithms used in
the Internet, as well as a couple of proposed alternative ones. Among
other things, we noted that OSPF and Integrated IS-IS each require a
specialized route lookup algorithm that doesn't work with any other
Internet routing protocol. This is certainly unfortunate for
implementors, since those who want to support both the new routing
protocols and the traditional ones have to implement three different
route lookup algorithms.  However, things become even more
problematic when a router wishes to simultaneously use multiple
routing protocols. Unfortunately, the growing complexity of the
Internet is requiring more and more routers to do just that.

Suppose, for example, that a router is simultaneously using RIP and
Integrated IS-IS, and a packet arrives at the router, waiting to be
forwarded. Does the router use Integrated IS-IS's route lookup
algorithm, or the Revised Classic Algorithm that is commonly used
with RIP? Does it try both, and hope that they both give the same
answer? The rest of this section looks at several ways out of this
dilemma that have been proposed.

5.1 The "Master Protocol" Approach

In the "master protocol" approach, a single routing protocol is given
responsibility for maintaining the routing table. A route lookup
algorithm appropriate for use with that routing protocol is used.
Routes learned from other routing protocols are "redistributed" into
the master protocol, which generally considers these routes to be
"external" (where the meaning of "external" depends on the particular
master protocol in use).

The obvious advantage to this approach is that it requires no change
to whatever route lookup algorithm is already being used. However,
there are a number of substantial drawbacks:

1.  If the master protocol used is one which automatically treats
	"external" routes as inferior, the protocol's own routes will always
	be considered better than routes learned from other routing
	protocols, even in cases where the protocol's own route matches fewer
	bits of the destination address and doesn't provide the requested
	type of service. This is a policy decision which may not be
	appropriate in all cases.

2.  Redistributing routes into the master protocol can be non-trivial
	if the protocol whose routes are being redistributed uses a route
	lookup algorithm different than that used by the master protocol(1).

----------------------------------------------------------------------
1. I need to think about this some more...
----------------------------------------------------------------------

3.  Most implementations assume that routes redistributed into the
	master protocol ought to be announced to other routers by the master
	protocol. This may or may not be desirable.

5.2  The "Rank Ordering of Routing Protocols" Approach

In this approach, the routing protocols in use are ranked according
to a preference ordering. There is no global FIB; each routing
protocol maintains its own, separate routing database. When a packet
is to be routed, the most preferred routing protocol is queried to
see if it has a route to the destination. That protocol uses a route
lookup algorithm which is appropriate to it to determine whether it
has a route.  If so, that route is used; if not, the second most
preferred routing protocol is queried, and so on, until either a
route is found or all of the routing protocols have been queried.

This approach also has a pleasant simplicity, and avoids some of the
problems of the previous approach. However:
1.  It potentially requires several route table lookups for each
	packet switched.
2.  It is often not possible to rank order the protocols in a
	sensible way. More often, each protocol will supply some routes which
	the router would like to consider primary and some routes which it
	would like to consider to be backup routes.
3.  A route provided by a more preferred routing protocol will be
	chosen even if it matches fewer bits of the destination address than
	a route provided by a less- preferred protocol. This may or may not
	be desirable.

5.3 The "Meta-lookup Algorithm" Approach

As in the Rank Ordering approach, each routing protocol that is being
used maintains its own independent routing database. When a packet is
to be routed, each active routing protocol is asked to submit a
candidate route. Each protocol chooses a route (or determines that it
has no appropriate route) using a route lookup algorithm appropriate
to the particular routing protocol.

After this takes place, the router is left with a set of candidate
routes, containing at most one route suggested by each of the routing
protocols. The router then uses a special route lookup algorithm,
called a "meta-lookup algorithm", to choose from among those routes.

This approach has some obvious disadvantages:
1.  A router running "n" routing protocols has to do "n+1" route
	lookups per packet.
2.  It isn't entirely obvious what the meta-lookup algorithm should
	be.

However, this approach has a number of fairly strong advantages:
1.  Depending on what meta-lookup algorithm is chosen, it can support
	virtually any policy, including those supported by the previously
	listed options.
2.  Unlike the previous options, it can support a policy of
	preferring the route from whichever routing protocol has the route
	which best matches the packet's destination address and requested
	TOS. This probably matches most peoples' intuitions about what the
	router ought to do. Given the complexity and difficulty of routing, I
	consider it extremely important that the solution match peoples'
	intuition.
3.  Because the routing protocols operate independently of each other
	and maintain their own routing tables, there is no need to worry that
	interactions between the protocols might make some of the protocols
	act incorrectly.
4.  Likewise, because each routing protocol uses its own route lookup
	algorithm on its own routing table, it is easy to ensure that any
	route chosen by this approach will in fact be the preferred route of
	one of the routing protocols. This greatly reduces the probability of
	routing loops.

Because of its strong advantages, the Meta-lookup Algorithm approach
seems to be the most promising choice. The remainder of this memo
considers this approach in greater detail, and considers how its
disadvantages can be mitigated.

6 The Recommended Policy Pruning Rule

Before examining the Meta-lookup Algorithm approach in detail it is
necessary to take a brief diversion to consider Policy pruning rules.
One common aspect of all of the algorithms examined so far is that
the Policy pruning rule is not specified. As a result, it can differ
vastly among implementations. This has been useful in that it has
allowed the Internet community to experiment with a number of
approaches, but has also lead to diminished interoperability among
different implementations.

In an attempt to improve interoperability without stiffling invention,
this memo does not fully specify the Policy pruning rule. Instead, it
recommends that two specific components be included in any Policy
pruning rule. Taken together, these two components provide what
practical experience has shown to be a very useful set of baseline
capabilities that I think should be common to all implementations.
Implementors would be free to augment these basic capabilities by
adding additional steps of their own devising.

6.1  Step 1: Route Preference Value Pruning

The primary mechanism of the recommended Policy pruning rule is that
each route has associated with it a "preference value", based on
various attributes of the route (specific mechanisms for assignment
of preference values are suggested in section 6.5). This preference
value is an integer in the range [0..255], with zero being the most
preferred and 254 being the least preferred. 255 is a special value
that means that the route should never be used. The first step in the
Policy pruning rule discards all but the most preferable routes (and
always discards routes whose preference value is 255).

It is worth noting that Route Preference Policy is not "safe" in that
it can easily be misused to create routing loops. Since no protocol
ensures that the preferences configured for a router are consistent
with the preferences configured in its neighbors, network managers
must exercise care in configuring preferences.

It is also worth noting the relationship between the special
preference value of 255 and the route filtering features provided by
some implementations. The route filtering features prevent routes
from being installed in the FIB, whereas the preference value of 255
allows a route to be included in the FIB but discards it as one of
the final steps of the meta-lookup algorithm. As a result, the route
filtering features can cause the protocol-specific lookup algorithms
or the earlier steps in the meta-lookup algorithm to choose less
specific routes, whereas the preference vale of 255 can only cause
some (or all) of the routes chosen by the previous steps to be
discarded. Another difference is that a preference value of 255 may
be assigned to any route, whereas route filtering cannot legally
discard routes learned from SPF-based protocols.

6.2 Step 2: Routing Domain Equivalence Pruning

The secondary mechanism of the recommended Policy pruning rule is
"routing domain equivalence".  If a router is configured to treat a
set of routing domains as equivalent then routes from those domains
can be compared based on their TOS and metric values. Since this step
is applied after Route Preference Value pruning, routes are compared
only if they have identical preference values.

The primary utility of this feature is to allow the metrics of static
routes to be compared to those of dynamic routes, but there will also
be other cases where this can be useful because the network manager
knows that the metrics of two routing domains are comparable. For
example, routing in certain parts of the Internet depends on the fact
that the routers used can consider the metrics of routes learned from
different EGP autonomous systems to be comparable.

Routing Domain Equivalence pruning uses a procedure similar to Weak
TOS pruning. The TOS values of the candidate routes are checked. If
any have the requested TOS then any routes which do not are discarded
(unlike W eak TOS pruning, routes which do not have TOS values are
retained rather than discarded).  The metrics of the remaining routes
are then compared, and those with inferior metrics are discarded.

6.3 Other Possible Policy Pruning Steps

Of course, many other policy pruning mechanisms are possible.  For
example:

MTU
	If any of routes in the set of candidate routes have an MTU large
	enough to forward the packet without fragmenting it then all routes
	which would require fragmentation are discarded from the set.

6.4 Load Splitting

At the end of the Policy pruning step multiple routes may still
remain. A router has several options when this occurs. It may
arbitrarily discard some of the routes. It may reduce the number of
candidate routes by comparing metrics of routes from routing domains
which are not considered equivalent. It may retain more than one
route and employ a "load-splitting" mechanism to divide traffic among
them.  Perhaps the only thing that can be said about the relative
merits of the options is that load-splitting is useful in some
situations but not in others, so a wise implementor who implements
load-splitting will also provide a way for the network manager to
disable it.

6.5  Assignment of Preference Values

It is important to give network managers adequate flexibility in
assignment of preference values so that they can implement whatever
policies they desire. In practice, this seems to require the ability
to assign preference values at the granularity of individual routes.
However, since a router may have thousands of routes, it is equally
important that the network manager not be required to specify an
individual preference value for each and every route. The following
mechanisms seem to provide adequate expressive power without overly
complicating the configuration process.

The implementor of the router chooses for each routing protocol (and
for static routes) a default preference value. There is no standard
way of choosing these preference values, but a good rule of thumb is
to choose the values in such a way that static routes are preferred
over routes learned from an IGP , and routes learned from an IGP are
in turn preferred over routes learned from an inter-domain routing
protocol (e.g. EGP or BGP [5]). It is probably also wise to choose
the default preference values such that no two routing protocols have
the same default preference value.

The router associates with each routing domain it is a member of a
default preference value, which will be assigned to any routes which
are learned from that routing domain but which do not have their
preference value set by one of the mechanisms below. The router
should allow the network manager to specify for each routing domain
(including static routing domains) the default preference value for
the routing domain. For any routing domain for which the network
manager has not explicitly configured a default preference value, the
default preference value for the routing protocol should be used as
the default preference value for that routing domain.

The above mechanisms are usually adequate to assign preference values
to most routes, but additional mechanism is needed to provide the
fine-grained control.  Although the only remaining mechanism that is
strictly necessary is a mechanism to assign specific preferences to
individual routes, configuration can be considerably simplified if
mechanisms are provided to assign a particular preference value to
the subset of routes from a particular routing domain which share
some common characteristic. The following mechanisms for classifying
routes have proven to be useful (and, conveniently, comprise a
superset of the set of classifications used by the route leaking
mechanisms described in [1]):

Address match
	It is useful to be able to assign a single preference value to
	all routes (learned from the same routing domain) to any of a
	specified set of destinations, where the set of destinations is all
	destinations that match a specified address/mask pair.

Route class
	For routing protocols which maintain the distinction, it is
	useful to be able to assign a single preference value to all routes
	(learned from the same routing domain) which have a particular route
	class (intra-area, inter-area, external with internal metrics, or
	external with external metrics).

Interface
	It is useful to be able to assign a single preference value to all
	routes (learned from a particular routing domain) that would cause
	packets to be routed out a particular logical interface on the router
	(logical interfaces generally map one-to-one onto the router's
	network interfaces, except that any network interface which has
	multiple IP addresses will have multiple logical interfaces
	associated with it).

Source router
	It is useful to be able to assign a single preference value to all
	routes (learned from the same routing domain) which were learned from
	any of a set of routers, where the set of routers are those whose
	updates have a source address which match a specified address/mask
	pair.

Originating AS
	For routing protocols which provide the information, it is useful to
	be able to assign a single preference value to all routes (learned
	from a particular routing domain) which originated in another
	particular routing domain. For BGP routes, the originating AS is the
	first AS listed in the route's AS_PATH attribute. For OSPF external
	routes, the originating AS may be considered to be the low order 16
	bits of the route's external route tag if the tag's Automatic bit is
	set and the tag's PathLength is not equal to 3 [10].

External route tag
	It is useful to be able to assign a single preference value to all
	OSPF external routes (learned from the same routing domain) whose
	external route tags match any of a list of specified values. Because
	the external route tag may contain a structured value [10], it may be
	useful to provide the ability to match particular subfields of the
	tag.

AS path
	It may be useful to be able to assign a single preference value to
	all BGP routes (learned from the same routing domain) whose AS path
	"matches" any of a set of specified values. It is not yet clear
	exactly what kinds of matches are most useful. A simple option would
	be to allow matching of all routes for which a particular AS number
	appears (or alternatively, does not appear) anywhere in the route's
	AS_PATH attribute. A more general but somewhat more difficult
	alternative would be to allow matching all routes for which the AS
	path matches a specified regular expression.

7 The Meta-lookup Algorithm Approach in Detail

So far, this memo has discussed the problem of how a router which
simultaneously uses several routing protocols might choose an
appropriate route to a particular destination. The previous section
described several approaches to solving the problem, and identified
the Meta-lookup Algorithm approach as the most promising.  This
section considers that approach in greater detail.

7.1 The Recommended Meta-lookup Algorithm

One of the features of the Meta-lookup Algorithm approach which gives
it so much flexibility is that any meta-lookup algorithm one wants to
choose will work and will not violate the assumptions of any of the
router's routing protocols. However, it would be undesirable to leave
the algorithm completely to the discretion of the implementor, since
then it would continue to be difficult if not impossible to configure
routers from different vendors in a consistent manner.

To me, the most obvious candidate for a meta-lookup algorithm would
be a stripped down version of the Revised Classic Algorithm from
Section 4.1 on page 10. This algorithm is familiar to both
implementors and users, and intuitively does "the right thing" in
most cases.

The Basic Match pruning step can be omitted, since it can be safely
assumed that the none of the routes provided by the protocol-specific
route lookups would be discarded by a Basic Match pruning step.
Likewise, the Best Metric pruning step would never discard any
routes, and can therefore be omitted. The reason for this is that (as
described on page page 9) Best Metric only compares metrics of routes
from the same routing domain.

One major shortcoming of the Revised Classic Algorithm for this
purpose is that it would have to be augmented to include an IDPR
Policy pruning step (described on page 10) in order to support the
IDPR protocol. This can be rectified by replacing the Basic Match
pruning step in the Revised Classic Algorithm with an IDPR Policy
pruning step. The other major shortcoming of the Revised Classic
Algorithm for our purposes is that it leaves the details of the
Policy pruning step unspecified, an omission that would need to be
corrected to ensure easy interoperability among routers from
different vendors. This can be rectified by replacing the generic
Policy pruning rule with the specific pruning steps recommended in
Section 6.

Some people have suggested that the Router Requirements Algorithm
(described in Section 4.2 on page 1 1) ought to be used in place of
the Revised Classic Algorithm, since the former supports TOS while
the latter does not. Using the Router Requirements Algorithm would
make it more likely that a route with the correct TOS would be
chosen, but at the expense of implicitly preferring protocols that
support TOS. Even with the Revised Classic Algorithm, no route would
be chosen that didn't have either the requested TOS or the default
TOS as long as all routing protocols which support TOS continue to
choose Weak TOS over alternative pruning rules to select routes of an
appropriate TOS.

To summarize, the recommended meta-lookup algorithm is:
1.  IDPR policy
2.  Longest match
3.  Route preference policy
4.  Routing domain equivalence policy

where the first step may be omitted by routers which do not support
the IDPR protocol and additional Policy steps may be added at the
discretion of the implementor.

7.2 The Alternative Meta-lookup Algorithm

The meta-lookup algorithm recommended in the previous section applies
Longest Match before applying Route Preference Policy . As a
consequence, the most specific route to a destination is always
chosen even if its preference value is inferior to that of a less
specific route. As a result, the recommended algorithm cannot be
configured to emulate the behavior of the Rank Ordering of Routing
Protocols approach that was discussed in Section 5.2 on page 16.

I believe that this choice is usually the correct one, but some
network managers may wish to be able to configure their routers to
make the opposite choice. Thus, an implementation may wish to include
an option to use the following alternative meta-lookup algorithm:

1.  IDPR policy
2.  Route preference policy
3.  Longest match
4.  Routing domain equivalence policy

where (as before) the first step may be omitted by routers which do
not support the IDPR protocol and additional Policy steps may be
added at the discretion of the implementor.

8 Performance and Implementation Issues

This section briefly considers ways to mitigate the problem that the
Meta-lookup Algorithm approach (conceptually at least) requires "n+1"
route table lookups for each packet forwarded. It assumes that the
meta-lookup algorithm being used is the one from Section 7.1 on page
21, but the general approach is probably applicable to any
meta-lookup algorithm.

8.1 Serialization of the Recommended Algorithm

Although it is conceptually necessary to do several route table
lookups and then afterwards apply the meta-lookup algorithm to the
results, it is possible to do everything necessary in a single pass
through the FIB. The precise algorithm required to do this depends on
which route lookup algorithms are used by the routing protocols that
are supported, but the following algorithm is believed to support all
of the existing IP routing protocols:

1.  Basic match
2.  IDPR policy
3.  Generic route class
4.  Longest match
5.  Generic weak TOS
6.  Best metric
7.  Route preference policy
8.  Routing domain equivalence policy

Most of the steps are pruning rules which have been previously
discussed, but pruning rules 3 and 5 are modified versions of
previously discussed rules, and are defined as follows:

Generic Route Class
	This is simply an agglomeration of the protocol-specific route
	class pruning rules. OSPF route class pruning (which was described on
	page 8) is applied to any OSPF routes (but not any other routes) in
	the set of candidate routes. Likewise, IS-IS route class pruning
	(which was described on page 9) is applied to any Integrated IS-IS
	routes in the set of candidate routes. If any other routing protocol
	are used which also support route classes, protocol-specific route
	class pruning would likewise be applied to those routes.

Generic Weak TOS
	This is exactly like Weak TOS, except that is applied separately to
	the routes learned from each routing protocol.  Thus, for example,
	finding an OSPF route whose TOS matched the TOS requested in the
	packet might cause other OSPF routes to be discarded, but would not
	cause RIP or Integrated IS-IS routes to be discarded.

Using this algorithm is more time-consuming than using one of the
traditional route lookup algorithms, but should prove significantly
speedier than performing one route lookup per protocol and then
executing the meta-lookup algorithm on the resultant routes.

8.2 Route Caching

Another way to improve the performance of the route lookup algorithm
is to execute it less often. One way to do this is to maintain a
cache which records the next hop address for each <destination
address, TOS> pair. Since it is usually the case that a packet for a
particular destination will be followed in short order by other
packets for the same destination, the hit rate on the cache is
usually high enough to more than offset the cost of maintaining the
cache. It is necessary to flush the cache whenever the FIB is
changed, but that is a rare event in most networks.

8.3 Precomputation of Routes

Routers typically improve performance by partially precomputing the
results of the route lookup algorithm. The result of this
precomputation is typically a "forwarding table", a data structure
containing only the subset of routes in the FIB which could actually
be chosen by the route lookup algorithm. I believe that it would be
possible to create a forwarding table corresponding to the serialized
algorithm in section 8.1, but the details are beyond the scope of
this memo.



9 Conclusion

This memo looked closely at how routers have traditionally chosen how
to route packets to their destinations, and how that traditional
method of choice is being overrun by changes in routing protocols and
by the ever-increasing complexity of the Internet. The memo then
examined several alternatives to the traditional method, and sketched
out some of the details of a preferred one.

References

[1] P. Almquist Ruminations on Route Leaking Paper in progress.

[2] P. Almquist Type of Service in the Internet Protocol Request for
Comments (RFC) 1349, DDN Network Information Center, SRI
International, Menlo Park, California, USA, July 1992.

[3] R. Callon Use of OSI IS-IS for Routing in TCP/IP and Dual
Environments Request for Comments (RFC) 1195, DDN Network Information
Center, SRI International, Menlo Park, California, USA, December 1990.

[4] C. L. Hedrick Routing Information Protocol Request for Comments
(RFC) 1058, DDN Network Information Center, SRI International, Menlo
Park, California, USA, June 1988.

[5] K. Lougheed and Y. Rekhter A Border Gateway Protocol 3 (BGP-3)
Request for Comments (RFC) 1267, DDN Network Information Center, SRI
International, Menlo Park, California, USA, October 1991.

[6] J. Moy OSPF Version 2 Request for Comments (RFC) 1247, DDN
Network Information Center, SRI International, Menlo Park,
California, USA, July 1991.

[7] L. J. Seamonson and E. C. Rosen "STUB" Exterior Gateway Protocol
Request for Comments (RFC) 888, DDN Network Information Center, SRI
International, Menlo Park, California, USA, January 1984.

[8] M. Steenstrup Inter-Domain Policy Routing Protocol Specification
and Usage: Version 1 Work in progress (INTERNET DRAFT ).

[9] E. Taft Gateway Information Protocol (Revised) Xerox Inter-Office
Memorandum to: Communication Protocols, location: PARC/CSL, file:
[Maxc1]<Pup>GatewayInformation.press, date: May 30, 1979.

[10] K. Varadhan BGP OSPF Interaction Request for Comments (RFC)
1403, DDN Network Information Center, SRI International, Menlo Park,
California, USA, January, 1993.

Security Considerations

The proposals in this memo and its companion document [1] are
intended to facilitate routing which is correct and consistent with
local policies at points in the Internet where routing domains meet
or overlap. To the extent that this memo is successful in its goals,
a net increase in security should result. The proposals in this memo
also provide some minimal guidance on integrating support for the
IDPR protocol into routers which also support more conventional
routing protocols. To the extent that source-demand routing is more
secure than hop-by-hop routing this memo facilitates enhanced
security The proposals in this memo have no other known impacts,
either positive or negative, on security .

In certain environments it would be useful to consider security
labelling of paths and packets when making routing decisions, but the
algorithms in this memo do not do so because current routing
protocols (other than IDPR) do not convey the security labelling of
available paths. It would probably be straightforward to modify the
algorithms in this document to make correct use of such labelling
information if routing protocols which provide it are developed.

Security considerations are not otherwise addressed in this memo.


Author's Address
Philip Almquis
214 Cole Street, Suite 2
San Francisco, CA 94117-1916
Phone: [phone]
EMail: [e-mail]

Working Group Address

Although this document is not the product of an IETF Working Group,
the issues it discusses are within the purview of the IETF's Router
Requirements Working Group.

EMail:  [e-mail]
-- 
--bill