Internet DRAFT - draft-almquist-leak
draft-almquist-leak
Network Working Group Philip Almquist
Stanford University/BARRNet
July 1991
Ruminations on Route Leaking
Status of This Memo
status per RFC111, to be filled in by the RFC Editor (This is an
informational document; it does not propose a standard, although the
author hopes that ideas contained herein will influence future
standards)
This is an as yet incomplete draft, dated July 23, 1991 2:32 am. A
final version is (hopefully) forthcoming.
Distribution of this memo is unlimited.
Summary
This memo discusses how routers can "leak" routing information
learned from one routing domain into another routing domain.
Although this memo is not an official product of the Router
Requirements Working Group, it is being published as an INTERNET DRAFT
because it is required reading for those who wish to actively
participate in the Router Requirements sessions during the IETF
meeting in Atlanta.
Acknowledgments
Vince Fuller, Toni Li, and Bob Albrightson provided useful comments
on an early partial draft of this memo.
Almquist * PRELIMINARY DRAFT * [Page 1]
INTERNET-DRAFT Contents July 1991
Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2. Overview of the Issues . . . . . . . . . . . . . . . . . . . . 3
1.3. Overview of this Paper . . . . . . . . . . . . . . . . . . . . 4
2. Models of Route Leaking . . . . . . . . . . . . . . . . . . . . . 4
2.1. Model A: Leaking the Routes in a Routing Domain . . . . . . . . 4
2.2. Model B: Leaking the Forwarding Table . . . . . . . . . . . . . 4
2.3. The Combination Model . . . . . . . . . . . . . . . . . . . . . 5
2.4. Leaking Using Third Party Advertisements . . . . . . . . . . . 5
3. Classification of Routes . . . . . . . . . . . . . . . . . . . . . 5
4. Issues in Route Leaking . . . . . . . . . . . . . . . . . . . . . 6
4.1. Route Summarization . . . . . . . . . . . . . . . . . . . . . . 6
4.2. Controls on Route Leaking . . . . . . . . . . . . . . . . . . . 7
4.3. TOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.4. Route Classes . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.5. Synthesis of Route Attributes . . . . . . . . . . . . . . . . . 8
4.5.1. Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.5.2. Other Route Attributes . . . . . . . . . . . . . . . . . . 9
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Security Considerations . . . . . . . . . . . . . . . . . . . . . . 12
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Almquist * PRELIMINARY DRAFT * [Page 2]
INTERNET-DRAFT Introduction July 1991
1. Introduction
Many times, a router has multiple sources of information about paths
through the network. For example, a router may be simultaneously
learning routes from multiple routing protocols and may also have
static routes configured by the network manager (or, more precisely,
the router may belong to multiple routing domains). A companion paper,
"Ruminations on the Next Hop"[1], discusses how a router picks routes
in such a situation. This paper considers the related issues of how a
router passes on (through its routing protocols) routes that it
learns. I recommend that you read the other paper first.
1.1 Terminology
This paper uses the following technical terms:
Forwarding table A forwarding table is the set of routes which a router
uses for forwarding packets. This is usually a subset
of the routes available to the router, because the
forwarding table contains only the best route to each
destination.
Routing domain A routing domain is a collection of routers which
coordinate their routing knowledge using a single
(instance of) a routing protocol. A degenerate case is
a single router which has some statically configured
routes. The Internet community often uses the term
Autonomous System instead, but I have avoided that term
in this paper because it is often also used to refer to
other similar concepts.
1.2 Overview of the Issues
1. Controls needed
2. Route summarization (e.g. collapsing subnet routes into net routes.)
3. Transformations to account for differences in route lookup algorithms:
- TOS
- Route Classes (intra-area, inter-area, external)
- subnet support (variable length, fixed length, none)
- metric transformation/setting
4. Issues of routing stability (e.g. split horizon) in route leaking.
Almquist * PRELIMINARY DRAFT * [Page 3]
INTERNET-DRAFT Models of Route Leaking July 1991
1.3 Overview of this Paper
2. Models of Route Leaking
There are several ways of looking at exactly what route leaking
is. This section contrasts two extreme views, followed by a third
which seems correct to me.
2.1 Model A: Leaking the Routes in a Routing Domain
Under this view, route leaking consists of the bulk transfer of
routes known in a source routing domain into a destination routing
domain. Although policy mechanisms may restrict which routes are
leaked, routes are leaked without regard as to whether they are in
the router's forwarding table. This might occur, for example, if the
router preferred a route from a third routing domain to the leaked
route, or if the router was prevented by policy mechanisms from
believing (using) the route being leaked.
To me, at least, this view has a certain formal elegance. It also
would seem a good basis for certain sorts of policy-based routing,
since it implicitly recognizes that all routes to a destination may
not be equivalent.
However, this view has some less desirable consequences. One is
what I call "diversion": a router may leak one route to a particular
destination but use an altogether different route to reach the
destination. This may merely result in counterintuitive routing, or it
may have more serious consequences, such as violating the policy of
the network manager. Related but even more serious consequences are
possible if the router is leaking a route but has no route to the
destination in its forwarding table: the router may black hole the
packets or, if it has a default route, may route the packets in a way
that causes looping.
2.2 Model B: Leaking the Forwarding Table
Under this view, route leaking consists of dumping the contents of
the forwarding table into a specified destination routing
domain. Again, there may be controls over the destinations for which
routes may be leaked, but under this view the router doesn't consider
the source routing domain when deciding whether to leak the route.
This view avoids the problems of looping and black holes that can
result from Model A. Likewise, diversion cannot occur because only
routes which the router will actually use are leaked.
However, this view also has less desirable consequences. The most
obvious is that it does not support leaking based on the source of the
route. In situations where policy restricts use of certain paths to
certain communities, routes to the same destination may need to be
treated differently. A related problem is that it may be unsafe to
leak a particular route when it comes from a particular routing domain,
Almquist * PRELIMINARY DRAFT * [Page 4]
INTERNET-DRAFT Classification of Routes July 1991
since leaking it will cause a routing loop through multiple routing
domains. With this view, it is easy for a network manager to set up
routing which appears to work but which creates a persistent routing
loop when the primary path to a particular destination fails.
2.3 The Combination Model
Under this view, route leaking is similar to Model A, except that only
the subset of the routes from the source routing domain which are also
in the router's forwarding table are leaked. This gives this approach
the advantages of Model A, but avoids its pitfalls by advertising only
those routes which the router actually uses.
2.4 Leaking Using Third Party Advertisements
Most routing protocols only allow a router to advertise routes through
the router itself. Some routing protocols (such as EGP [6] and OSPF
[7]) provide mechanisms to allow a router to specify that some other
router should be used as the path to a particular destination. These
mechanisms can be collectively referred to as "third party
advertisements".
The pitfalls of Model A do not affect routes leaked as third party
advertisements. Thus, it is appropriate to leak routes which are not
in the forwarding table in cases where they can be leaked as third
party advertisements(1).
3. Classification of Routes
To use a number of the mechanisms described later in this paper, it is
useful to be able to refer to a collection of routes by specifying
some property that the routes share. Fortunately for implementors,
there are only a very few useful ways of classifying routes, and each
is useful in most of the mechanisms I will be describing:
Address range It is useful to specify all routes to destinations
which fall (numerically) into an address range that
is a member of a specified set of address ranges.
Milo's Number(2) It is useful to specify all OSPF routes which have
in their Milo's Number field any of a set of specified
values.
----------
1. Some people believe that there are cases where third party
advertisements (even of routes that the router believes) can cause
routing loops. I need to think about this some more. Also, it is not
clear how important third party advertisements would be in practice;
maybe this section should go away or discourage third party
advertisements???
2. This is the four octet tag field which OSPF carries with external
routes. Its use is outside of the scope of the OSPF specification; it
is intended for use by border routers to communicate among
themselves. Most commonly, it is used to carry the autonomous system
number of the source of the route. I need to check the OSPF speck to
find the real name of this field.
Almquist * PRELIMINARY DRAFT * [Page 5]
INTERNET-DRAFT Issues in Route Leaking July 1991
AS path It is useful to specify all BGP routes 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 and reasonably useful
option would be to allow matching of all routes
which do (or do not) have a specified AS number
at some point in the AS path. 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.
Route class For routing protocols which maintain the distinction,
it is useful to subdivide the routes into internal
routes and external routes. It is also useful (though
less so) to further subdivide internal routes into
intra-area routes and inter-area routes, and to
subdivide external routes into those that use internal
metrics and those that use external metrics.
4. Issues in Route Leaking
4.1 Route Summarization
Traditionally, routing protocols have carried routes describing paths
to networks. However, as the technology has evolved routing protocols
have sprouted a variety of mechanisms to carry routes describing paths
to individual end systems or to ranges of addresses (called subnets by
the Internet community).
This is a concern in this paper for two reasons. One is that it is
often desirable, in order to keep routing information to a manageable
size, to replace a collection of routes with a single route which
summarizes the information. For example, it may be desirable to invent
and leak a route to a network instead of leaking all of the routes to
that network's component subnets.
The other reason this is a concern of this paper is that different
routing protocols have different subnetting capabilities. Some still
support only routes to networks. Others support routes to subnets,
but assume that all subnets of a network use the same address mask
(which is conveyed to all routers through a mechanism outside of the
routing protocol). The most flexible routing protocols either carry
address ranges or carry for each route an arbitrary bit mask
indicating which bits of the destination of the route are
significant. Most routers which support route leaking will have to
address the issue of how to leak routes between protocols with
different mechanisms and different degrees of capability in this area.
I originally considered addressing this problem by creating a matrix,
where one axis described the capability of the protocol that was the
source of the route, and the other axis described the capability of
the protocol into which the route was being leaked. The cells inthe
matrix described the action the router should take for each
Almquist * PRELIMINARY DRAFT * [Page 6]
INTERNET-DRAFT Issues in Route Leaking July 1991
combination of capabilities. This was an interesting exercise, but I
rapidly rejected that approach because the complexity rapidly got out
of hand. Even if I did succeed in describing all possible cases, and
even if nobody made my list obsolete by inventing a routing protocol
with different mechanisms, It seemed unlikely that most network
managers would be able to guess what their router would really do
without carefully pondering a copy of my matrix.
I therefore opted for a simpler approach, inspired in part by the
route summarization mechanisms in OSPF [7]. This approach also has the
advantage that it handles in a theoreticaaly elegant way the
traditionally difficult question of when a router should generate a
default route (rather than leaking all of the individul routes)(1).
In this approach, a network manager may configure a set of a address
ranges. Associated with each address range is a destination address
(and an address mask). If a router is considering leaking a particular
route, it checks to see if it is a route to a destination which falls
within one of the address ranges. If so, it instead creates and leaks
a route to the destination address associated with the address range
which was matched.
If, on the other hand, the route does not fall within any of the
address ranges, the router does one of two things. If the protocol
into which the route is being leaked has sufficient capabilities that
it can accurately represent the destination of the route, then the
route is leaked. Otherwise, the route is not leaked. Thus, for
example, a route to a subnet would be leaked into OSPF, since it can
represent subnets, but would not be leaked into EGP, since it cannot
carry subnet routes. A subnet route from OSPF would be leaked into RIP
if and only if the mask associated with the OSPF route was the same as
the implicit address mask used by the RIP routing domain
4.2 Controls on Route Leaking
Route leaking is vital part of creating non-local connectivity in the
Internet. However, it is a two-edged sword, and can create numerous
problems if routes are simply leaked with abandon. Thus, any route
which supports route leaking also needs to support mechanisms to allow
the network manager to control which routes go where.
At the very least, a router must not leak any routes from one routing
domain to another unless it has been specifically configured by the
network manager to do so. This prevents a partially-configured router
from causing major havoc.
------
(1) It has been pointed out that although this may be technically elegant,
configuring the route leaking mechanism to generate a default route
may be less intuitive to the uninitiated than the existing "originate
default" commands. However, I suspect that could be fixed though
appropriate user interface design.
Almquist * PRELIMINARY DRAFT * [Page 7]
INTERNET-DRAFT Issues in Route Leaking July 1991
In practice, finer-grained controls are often needed. The system of
classification of routes described in Section 3. on page 5 provides a
useful shorthand to allow the network manager to describe which routes
ought to be leaked from a particular source routing domain to a
particular destination routing domain.
4.3 TOS
TBD - basically:
- When leaking from a protocol which does not support TOS to one that does,
leaked routesare assigned the default TOS.
- When leaking from a protocol which does support TOS to one that does not,
routes which have a TOS other than the default TOS are not leaked.
- When leaking from a protocol which supports all TOS values into Dual IS-IS,
routes which have a TOS not supported by Dual IS-IS are discarded.
4.4 Route Classes
TBD - basically:
- When leaking into a protocol which supports route classes (intra-area,
inter-area, etc.), the protocol specifies rules for choosing the route
class. Where an option is provided, there needs to be a configuration
option (and once again, the route classification system from section 3
is useful here)
- Leaking from a protocol that supports route classes into one that doesn't
presents no special challenges as long as the router follows the rule that
routes not in the forwarding table are never leaked (this rule is
particularly important here since routing protocols which use route classes
don't choose the longest match if there is an acceptable route with a more
preferable route class than the longest match route).
4.5 Synthesis of Route Attributes
4.5.1 Metrics
Metrics pose a particular problem in route leaking, since metrics are
generally meaningful only within a routing domain, and different
routing protocols often have very different types of metrics.
There are two basic approaches to setting metrics in leaked
routes. The first is the "metric translation" approach: the metric
from the source routing domain is passed through a mathematical
function (often represented in practice as a translation table) to
obtain the metric in the destination routing domain. This approach has
some definite advantages if the translation function is well-chosen:
the metric represents on some ways the quality of the route, and
"counting to infinity" can be
Almquist * PRELIMINARY DRAFT * [Page 8]
INTERNET-DRAFT Issues in Route Leaking July 1991
depended upon to suppress routing loops that pass through multiple
routing domains. The disadvantage of this approach is that the
variations in the range and semantics of metrics between the different
routing protocols has left the choice of appropriate translation
functions as an unsolved problem (the major exception I am aware of is
a standard function [9] for translating between the metrics used by
RIP [3] and the metrics used by the now obsolete HELLO protocol [8]).
Therefore, the recommended approach is the "static metric" approach:
the metric used in the destination routing domain is established by a
configuration option. This approach is somewhat dangerous, in that an
incautious network manager can set things up such that stable routing
loops can form, but many network managers have successfully used this
approach.
In many cases, it is important that the network manager be able to
establish different metrics for different routes that are leaked. For
example, the network manager may wish that the destination routing
domain use the some of the leaked routes as primary paths to their
destinations while other of the leaked routes are backup paths to
their destinations. That may be impossible to configure if all of the
routes have to be leaked with the same metric.
Although it is desirable to allow the network manager to establish
metrics individually for each route leaked, it would also be
undesirable to force him or her to do so, since that might require the
network manager to provide a great deal of configuration
information. Therefore, the recommended approach is to allow the
network manager to establish metrics for categories of routes, using
the categories defined in Section 3. on page 5, and also a default
metric for use with routes which don't fall into any of the
categories. This approach allows the network manager to provide only
the bare minimum of configuration information necessary to set the
metrics required by his or her policies. It is probably wise to force
the network manager to explicitly choose the value for the defaut
metric, since the implementor has no way to algorithmically choose a
value which is likely to work correctly in any particular network.
4.5.2 Other Route Attributes
Some routing protocols carry with them various protocol-specific route
attributes. Although this paper tries hard to solve the problems of
route leaking in a generic (non-protocol-specific) manner, this is one
place where discussion of particular protocols cannot be
avoided. Unfortunately, that also means that this section is
incomplete, either immediately because of protocols I haven't thought
about or in time because of new protocols which will undoubtedly be
invented.
The BGP protocol [4],[5] carries with its routes an "AS Path"
attribute, which is a list of the autonomous system numbers of the
routing domains on the path to the destination of the route. When
leaking a route into BGP, it is necessary to create this
attribute. Because it is in general not possible to know the
autonomous system
Almquist * PRELIMINARY DRAFT * [Page 9]
INTERNET-DRAFT Issues in Route Leaking July 1991
numbers of all of the routing domains back to the source of the route,
usually all that is possible is to include in the attribute a single
autonomous system number which is the autonomous system number of the
routing domain from which the route is being leaked. If the source
routing domain is also using the BGP protocol, the AS path attribute
should be copied from the source routing domain and the (autonomous
system number of the source routing domain should be appended(1).
The OSPF protocol [7] also has an attribute to describe the source of
an external route. The contents of this attribute, called "Milo's
Number", are (intentionally) left to local convention in the
specification. Thus, an implementation probably ought to be able to
fill in the Milo's number attribute of a leaked route with the
autonomous system number of the source routing domain. However, in
case another convention is in use in the destination OSPF routing
domain, an implementation should allow static configuration of the
value for this attribute. As with metrics, it may be important to
allow different values to be specified for different groups of routes,
again using the route classification scheme described in Section 3. on
page 5. For the special case where both the source routing domain and
the destination routing domain use OSPF(, the implementation should be
able to copy the value of Milo's Number from the original route into
the leaked route if the source route is also an external route.
------
1. Theoretically, this is not an issue because (according to those who
know more about BGP than I do) it makes no sense for a router to ever
run more than a single instance of BGP.
2. At the Spring `91 IETF meeting there was some discussion of
semi-standard values that could be used for Milo's number when leaking
BGP routes into OSPF. I need to find my notes and perhaps ask Yakov
about the future of that proposal.
Almquist * PRELIMINARY DRAFT * [Page 10]
INTERNET-DRAFT References July 1991
References
[1] P. Almquist "Ruminations on the Next Hop" Paper in progress.
[2] 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.
[3] C.L. Hedrick "Routing Information Protocol" Request for Comments (RFC)
1058, DDN Network Information Center, SRI International, Menlo Park,
California, USA, June 1988.
[4] J.C. Honig, D. Katz, M. Mathis, Y. Rekhter, and J.Y. Yu "Application
of the Border Gateway Protocol in the Internet" Request for Comments
(RFC) 1164, DDN Network Information Center, SRI International, Menlo
Park, California, USA, June 1990.
[5] K. Lougheed and Y. Rekhter "Border Gateway Protocol" (BGP) Request for
Comments (RFC) 1163, DDN Network Information Center, SRI International,
Menlo Park, California, USA, June 1990.
[6] D. Mills "Exterior Gateway Protocol Formal Specification" Request For
Comments (RFC) 904, DDN Network Information Center, SRI International,
Menlo Park, California, USA, April 1984.
[7] J. Moy "OSPF Specification, Version 2", To be published as an RFC;
currently an INTERNET DRAFT dated June 1990.
[8] D.L. Mills "DCN Local-network Protocols", Request for Comments (RFC) 891,
DDN Network Information Center, SRI International, Menlo Park,
California, USA, December 1983.
[9] ??? Gated reference
Almquist * PRELIMINARY DRAFT * [Page 11]
INTERNET-DRAFT Security Considerations July 1991
Security Considerations
Security considerations are not addressed in this memo.
Author's Address
Philip Almquist
214 Cole Street, Suite 2
San Francisco, CA 94117-1916
Phone: 415-752-2427
EMail: almquist@Jessica.Stanford.EDU
Almquist * PRELIMINARY DRAFT * [Page 12]
