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]