[Search] [txt|pdf|bibtex] [Tracker] [Email] [Nits]

Versions: 00                                                            
Network Working Group                               Steven J. Richardson
Internet Draft                                       Merit Network, Inc.
                                                               June 1996
                                                    Expire in six months


          Vertical Aggregation:  A Strategy for FIB Reduction
                 <draft-richardson-fib-reduction-00.txt>

1. 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 and may be updated, replaced, or obsoleted by other
        documents at any time.  It is inappropriate 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).

2. Abstract

   This document analyzes Network Layer Reachability Information (NLRI)
   flow within a router with emphasis on the Forwarding Information
   Base(s)--FIB(s)--and the effects of currently-implemented aggregation
   schemes on FIB size.  The conditions for reduction of FIB information
   before insertion into the kernel are considered, with preservation of
   routing a primary criteria (essentially deriving in a more structured
   manner the result that one wishes to remove extraneous routing
   information extant in the FIB(s)).  Finally, aggregation algorithms
   consistent with these conditions are presented.













S. J. Richardson                                                ^L[Page 1]


INTERNET-DRAFT                                                March 1996


3. Table of Contents

   1. Status of this Memo
   2. Abstract
   3. Table of Contents
   4. Introduction
   4.1 NLRI Flow and NLRI Interaction with a Router's FIB(s) and Conceptual RIBs
   4.1.1 NLRI Flow Between Routers
   4.1.2 NLRI Flow Within a Router
   4.1.3 NLRI Flow in Relation to Router's Conceptual RIBs and FIB(s)
   4.2 Horizontal and Vertical NLRI Flows
   4.3 Horizontal Aggregation
   5. Vertical Aggregation
   5.1 Character of the Current FIB Filter Function f()
   5.2 New FIB Filter Function--General Character and Constraints
   5.3 Implications of the Constraint
   5.3.1 CIDR-Related Implications of the Constraint
   5.3.2 BGP4-Related Implications of the Constraint
   5.3.3 Related Considerations
   5.4 Solution of f()
   5.4.1 FIB Representation
   5.4.2 Solution of f()--Simple Case
   5.4.3 Solution of f()--General Case
   6. Conclusion and Next Steps
   7. Security Considerations
   8. Acknowledgements
   9. Author's  Address
   10. Notes
   11. References






















S. J. Richardson                                                ^L[Page 2]


INTERNET-DRAFT                                                March 1996


4. Introduction

   In order to better understand the proposed FIB reduction scheme, we
   will first review

           - the RIB and FIB structure and interaction in a typical router,
           - the different flows of Network-Layer Reachability Information
             (NLRI), and
           - the type of aggregation ("horizontal aggregation") currently
             implemented.

4.1 NLRI Flow and NLRI Interaction with a Router's FIB(s) and Conceptual
RIBs

4.1.1 NLRI Flow Between Routers

   It is important to clearly have in mind the flow of NLRI both between
   different routers and also within a single router.  Diagram 1 depicts
   the flow of NLRI in the former case, which we will label "horizontal"
   flow of NLRI, in part because we speak of routers as being "peers"
   and so, by implication, being of equal standing.  (Note that NLRI and
   packet flow, though both bidirectional in nature, have an opposite
   sense in that packets flow in the reverse direction of NLRI.)

         +----------+   NLRI   +----------+   NLRI   +----------+
         |          |<========>|          |<========>|          |
         | Router X |          | Router Y |          | Router Z |
         |          |<-------->|          |<-------->|          |
         +----------+ Packets  +----------+ Packets  +----------+

                             Diagram 1
                   Flow of NLRI Between Different Routers
                        ("Horizontal" Flow of NLRI)

   The entire traffic of NLRI which flow on the Internet can be
   considered to be a stream of NLRI into which routers are placed; the
   routers can act to modify this stream via policy, including adding to
   the stream.













S. J. Richardson                                                ^L[Page 3]


INTERNET-DRAFT                                                March 1996


4.1.2 NLRI Flow Within a Router

   Internal to a router, a portion of this stream of NLRI is cached off
   to one side; this is the FIB(s) of the router, the actual routing
   table(s) used in packet forwarding.  Since this flow of NLRI is
   orthogonal to the peer-to-peer or horizontal flow, we will call this
   the "vertical" flow of NLRI.  This is shown in Diagram 2, which
   presents a simplified view of NLRI flow within a router--e.g., Router
   Y of Diagram 1--and which points out the difference between the
   "horizontal" flow "through" the router versus the "vertical" NLRI
   flow from this stream to the local FIB(s).


               Horizontal NLRI Flow --->

                 +------------------+
                 |     ________     |
                 |    / Cloud  \    |
 Inbound NLRI ==>|==>(    of    )==>|==> Outbound NLRI
                 |    \  RIBs  /    |
                 |     --------     |
                 |        ||        |  |
                 |        ||        |  | Vertical NLRI Flow
                 |        \/        |  V
                 |      +------+    |
                 |     +------+|    |
                 |     |      ||    |
                 |     |FIB(s)||    |
                 |     |      |+    |
                 |     +------+     |
                 +------------------+
                        Router

                       Diagram 2
          Flow of NLRI Within a Single Router
               ("Vertical" Flow of NLRI)

4.1.3 NLRI Flow in Relation to Router's Conceptual RIBs and FIB(s)

   Note that Diagram 2 has lumped the internal RIB structure of the
   router into a cloud (well, OK, it's some sort of cheesy ASCII lump
   ;-).  In order to better model the internal flow of NLRI in a single
   router, one must consider the detailed conceptual structure of a
   router's RIB(s) and the relation of the RIB(s) to the FIB(s); this is
   depicted in Diagram 3, below.[2]






S. J. Richardson                                                ^L[Page 4]


INTERNET-DRAFT                                                March 1996


        +-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- +
        |Adj-RIBs-In                            Adj-RIBs-Out|
            +----+                                  +----+
        |  +----+|                I                +----+|  |
Peer 1 ==> |    || ==>-\  +- - - - - - - - ->/-==> |    || ==> Peer 1
        |  |    |+    ||  |                  ||    |    |+  |
           +----+     ||                     ||    +----+
        |             ||  |                  ||             |
            +----+    ||                     ||     +----+
        |  +----+|    ||  |       I          ||    +----+|  |
Peer 2 ==> |    || ==>||  +- - - - - - - - ->||==> |    || ==> Peer 2
        |  |    |+    ||  |                  ||    |    |+  |
           +----+     ||                     ||    +----+
        |             ||  |                  ||             |
        .     .       .                      .        .     .
        .     .       .                      .        .     .
        .     .       .                      .        .     .
        |             ||  |                  ||             |
            +----+    ||                     ||     +----+
        |  +----+|    ||  |       I          ||    +----+|  |
Peer N ==> |    || ==>||  +- - - - - - - - ->||==> |    || ==> Peer N
        |  |    |+    ||  |                  ||    |    |+  |
           +----+     ||                     ||    +----+
        |             ||  |I                 ||             |
               Import ||                     || Export
        |    Policies ||  |    Loc-RIBs      || Policies    |
             (Inbound ||        +----+   |   || (Outbound
        |    Filters) ||  |    +----+|   |   || Filters)    |
                      \+==+==> |    || =====>+/
        |                      |    |+   |                  |
                               +----+    |
        |                        ||     A()                 |
                                 ||
        |   RIB(s)               ||                         |
        +-- -- -- -- -- -- -- -- ||- -- -- -- -- -- -- -- --+
                                 ||
                            -----||----- f()
                                 ||
                                 \/
                                FIBs
                               +----+
                              +----+|
                              |    ||
                              |    |+
                              +----+

                  RIBs and FIBs in a Single Router
                             Diagram 3



S. J. Richardson                                                ^L[Page 5]


INTERNET-DRAFT                                                March 1996


   Although Diagram 3 is considerably more complex than Diagram 2, it is
   basically a more detailed enhancement of the RIB cloud and FIBs shown
   in the latter figure; in particular:

        - the dashed bounding box of Diagram 3 represents the
          RIB cloud of Diagram 2, and it contains the various
          component RIBs (Adj-RIBs-In/Out and the Loc-RIB) which
          comprise the complete RIB(s) of the router[3] (in other
          words, a complete RIB for a router has its Loc-RIB and
          a set of Adj-RIBs-In and Adj-RIBs-Out);

        - the RIBs associated with inbound and outbound NLRI
          (i.e., the Adj-RIBs-In and Adj-RIBs-Out) are split up
          on a per-peer basis with the former on the left side i
          of the diagram and the latter on the right side;

        - multiple RIB and FIB layers are indicated in order to
          account for the fact that there may be protocols which
          support Type-of-Service (ToS)/Quality-of-Service (QoS)
          differentiation of different routes to the same
          destination, resulting in one layer of RIB/FIB per set
          of RIB-Attributes (RIB-Atts) which define a given ToS/QoS
          (i.e., one RIB/FIB layer per ToS/QoS).

   There are a few lines which the reader should locate, all near the
   Loc-RIB(s) in Diagram 3; they are labelled "A()" and "f()".  The
   importance of these lines is that they show places where aggregation
   of NLRI can occur.  They are named as functions because aggregation
   policies essentially are functions which modify the flow of NLRI, the
   stream of routing information which passes through a router or is
   cached in the router.

   Since there are two directions of NLRI flow, there are also two
   distinct aggregation policies:

        - "horizontal" aggregation policy (see sec. 4.3, below)--
          aggregation which affects only the horizontal flow of NLRI--
          conceptually occurs at the line labelled "A()" (i.e., it is
          a part of the process of creating the Adj-RIBs-Out[4]), while

        - "vertical" aggregation (see sec. 5, below)--aggregation which
           affects only the horizontal flow of NLRI--conceptually occurs
          at the line labelled "f()".

   (Note that any internal peers of the local router--i.e., those peers
   which are in the same Routing Domain (RD) as the local router--will
   receive routing updates via the path labelled "I" in Diagram 3; note
   that this path circumvents the Loc-RIB(s) and export filter process.



S. J. Richardson                                                ^L[Page 6]


INTERNET-DRAFT                                                March 1996


   External peers (those which are in a different RD) are updated via
   the right-hand path labelled "Export Policies (Outbound
   Filters)."[5])

   Horizontal aggregation is the form of aggregation familiar to most
   readers and is very widely-discussed at the present time,
   particularly in the context of CIDR and it helpfulness both at the
   point of allocating IP address space and at the point of announcing
   routing destinations.

4.2 Horizontal and Vertical NLRI Flows

   As we've noted, Diagram 3 represents two different flows of Network-
   Layer Reachability Information (NLRI):  the horizontal flow (the
   peer-to-peer flow, including the flow "through" a router as the NLRI
   pass through it on the way from one peer to another), and the
   vertical flow (the flow from Loc-RIB(s) to FIB(s) within a router.
   These flows within a router can be detailed as follows (refer to
   Diagram 3):

        Horizontal NLRI flow:

        - incoming NLRI and associated path attributes from peers
          1, 2, .. N are stored in the Adjacent-RIB(s)-In (Adj-RIBs-In)
          associated with the peer announcing the NLRI;

        - all Adj-RIBs-In are filtered via the local router's
          import policy, which determines which NLRI in these
          Adj-RIBs-In end up in the local router's Loc-RIB(s);

        - a "best route" to each destination in the Loc-RIB(s) is
          selected via both protocol-specified criteria (see, e.g.,
          section 9.1 of RFC1771--and its subsections--for the
          BGP4 decision process) and, possibly, implementation-
          specific criteria (e.g., GateD's use of a second internal
          metric, "preference2"[6]);

        - the Loc-RIB's/Loc-RIBs' best routes are filtered via
          the local router's export policy, which determines which
          NLRI will end up in the router's Adjacent-RIBs-Out, which
          are also arranged on a per-peer basis (just as the Adj-RIBs-
          In).

        Vertical NLRI flow:

        - "best routes" selected in the Loc-RIB(s) are filtered
          via a function f()--described below--into the local
          router's FIB(s).



S. J. Richardson                                                ^L[Page 7]


INTERNET-DRAFT                                                March 1996


   Note that these two information flows only intersect at the Loc-
   RIB(s) in the form of the "best routes" selected for each destination
   stored in the Loc-RIB(s); therefore, a change in the FIB filter
   function f() only affects the "vertical" NLRI flow, and has no effect
   on the "horizontal" NLRI flow (i.e., it has no effect on existing
   routing protocol implementations).  Also, as the NLRI flow across the
   Internet, while the horizontal flow is some continuous flow
   (modified, of course, by policy and outages), the vertical flow is
   internal to each router (it does not cross router boundaries).

4.3 Horizontal Aggregation

   Classless Inter-Domain Routing (CIDR; RFC1519) aids in the reduction
   of routing information by making possible

      a) "right-sizing" of IPv4 address allocations--so that fewer
      destinations need be announced (aggregation at the source of
      routing announcements), and

      b) hierarchical addressing schemes which promote aggregation at
      intermediate points in the routing topology (topologically-based
      aggregation).

   It is to be noted that both of these schemes represent reductions in
   the number of destinations exchanged between routers; one can view
   this as "horizontal aggregation" in that it affects the amount of
   routing information exchanged between BGP4 peers in the routing
   topology.

   Though these aggregation actions, which reduce the total number of
   destinations announced, clearly reduce local Forwarding Information
   Bases (FIBs, the forwarding tables or routing tables of routers),
   this effect is rather indirect, since most routing information is not
   generated at any given local router.  Any reduction of the FIB(s) of
   a given router via these forms of aggregation are therefore primarily
   due to distant actions rather than local actions; the FIB of a given
   router has a size primarily dependent upon the decisions of other RDs
   (in the absence of vertical aggregation).

   Currently, there are on the order of 35,000 total destinations
   announced in the "default-free" worldwide Internet.[1]  However, even
   the most well-connected border router (at, e.g., MAE-East in the
   United States) might have only on the order of 40-50 peers; if we
   approximate one next hop per peer, the ratio of destinations to next
   hops suggests that there is a potential for substantial savings of a
   very important resource:  the number of slots in the FIBs of
   "default-free" routers.  The potential for savings is even better for
   non-border routers of a "default-free" backbone:  with about 35,000



S. J. Richardson                                                ^L[Page 8]


INTERNET-DRAFT                                                March 1996


   total destinations and around 5 next hops, there is another order of
   magnitude in the ratio of destinations to next hops.

5. Vertical Aggregation

   It is precisely this niche which vertical aggregation occupies.  The
   aggregation is "vertical" because the aggregation occurs within a
   single router and does not affect the flow of routing information to
   peers of the router implementing the FIB aggregation.  The FIB
   entries produced by this procedure will generally consist of a subset
   of the destinations available to the router, but FIB aggregation has
   no affect on the destinations placed in Adj-RIBs-Out (Adjacent-RIBs-
   Out; see Diagram 3, above) for announcement to routing peers.  FIB
   aggregation acts locally and directly on the "candidate" FIB; hence,
   the potential for reduction of the local FIB looms much larger than
   that achievable through manipulation of the local FIB via remote,
   indirect means.

   In order to understand how this might work, we need to examine the
   specifics of this proposal.  The proposal will be developed by

           - considering the FIB filtering currently used, and
           - developing the design criteria for the desired FIB filter;
           - proposing a solution algorithm which fulfills these criteria.

5.1 Character of the Current FIB Filter Function f()

   Currently, the selection function indicated by f() in Diagram 3 is a
   unity filter which acts on either:

        - the only Loc-RIB (this is the common case in which there is
          only one layer of RIBs in Diagram 3, above; i.e., there is
          only one ToS/QoS for all announced destinations), or

        - a "chosen" Loc-RIB corresponding to the particular ToS/QoS
          which will be supported by the router as its single FIB (i.e.,
          f() is a unity filter for one Loc-RIB and discards/ignores
          all other Loc-RIBs).

(There are a few kernels which support multiple FIBs--i.e., multiple
ToS/QoS values--and which, therefore, have a filter function f() which
sets all [or >1] RIBs' routes for inclusion in the FIBs.  This is merely
a variation on the "all-or-nothing" selection functions mentioned above.)








S. J. Richardson                                                ^L[Page 9]


INTERNET-DRAFT                                                March 1996


   Therefore, the current use of f() is as a very simple transformation;
   if we view the FIB and the Loc-RIB(s) as matrices, then we have
   either:

           FIB = 1 * Loc-RIB
           FIB = Loc-RIBj = 1 * (KD jk) * Loc-RIBk, k = 1, 2, ... m

   where (KD jk) is the author's ASCII attempt to express the Kronecker
   Delta of indices 'j' and 'k' and 'k' varies over the values 1 to 'm'
   (the number of ToS/QoS supported by the router, which therefore
   determines the number of Loc-RIBs).

   It is clear that f() currently depends upon the level of protocol and
   router technology in terms of ToS/QoS support.

5.2 New FIB Filter Function--General Character and Constraints

   For the case of FIB aggregation, however, f() is a more detailed
   function, and it would replace any occurrence of f() where f() is
   currently the unity filter; thus, this vertical or FIB aggregation
   should occur after "best route" selection (update of the Loc-RIB(s))
   has occurred and just prior to insertion of routes into the FIB.

   The function f() is a transformation of the form

           FIB' = f() FIB = f() Loc-RIBj

   i.e., it must produce a transformation of the single Loc-RIB or
   selected Loc-RIB to produce a new FIB, FIB'.  In this document, we
   will consider a transformation f() such that a sole general
   constraint is fulfilled:

           GENERAL-C) Routing of packets must be unaffected by the
                   substitution of FIB' for FIB.

   In other words, the aggregated FIB, FIB', must yield routing
   equivalent to the unaggregated FIB;[7]  GENERAL-C guarantees that
   routing which uses any FIB' produced by f() is as reasonable as that
   experienced by the use of the associated (unaggregated) FIB, so that
   the "reasonableness" of routing is not determined by f(), but is
   determined by the specific NLRI exchanged via routing protocols in
   combination with local policies other than FIB aggregation policies.









S. J. Richardson                                               ^L[Page 10]


INTERNET-DRAFT                                                March 1996


5.3 Implications of the Constraint

5.3.1 CIDR-Related Implications of the Constraint

   The CIDR draft has two fundamental rules[8]:

           CIDR-1) Longest-match routing; routing matches for
                   forwarding decisions are based upon testing
                   the most-specific prefixes in the FIB before
                   less-specific prefixes.

           CIDR-2) Aggregation-related rule; packets bound for
                   non-extant components of a aggregate must
                   be discarded by the aggregating routing
                   domain.

   How do these rules affect the constraint on the FIB transformation
   f()?

   CIDR-2 is easy to deal with; the implementation of this rule has been
   carried out previous to the Loc-RIB finalization which occurs before
   the FIB is handed the "best" routes.  Therefore, CIDR-2 does not
   directly affect the constraint or transformation (though there is a
   tangential effect due to different types of routes which is covered
   in section 5.3.3, below).

   The rule labelled CIDR-1 is more interesting, though, and it means
   that we have an interesting observation in terms of the constraint:

           CIDR-C) In order to satisfy the constraint in view of
                   CIDR-1, it is necessary to maintain the "stratification
                   of next hops".

   What is meant will become clear with the help of a definition.

           "related prefixes" in a FIB are any complete set of
           destination prefixes in the FIB which:

                   - share a portion of IPv4 address space, no
                     matter what the size;

                   - can be arranged in an order such that each
                     new prefix in the set is a strict superset
                     of the previous prefix; and

                   - are ordered in that fashion, with the longest
                     prefix being encountered first.




S. J. Richardson                                               ^L[Page 11]


INTERNET-DRAFT                                                March 1996


   If a given FIB is arranged into a radix trie, then sets of related
   prefixes consist of all of the nodes in the path from any given leaf
   or terminal node in the trie back to the root (in that order).

   The "stratification of next hops" emerges if one considers arbitrary
   sets of related prefixes; when the prefixes are ordered as above and
   listed along with their next hops, it is clear that routing which
   uses the given FIB works in the way that it does because different
   parts of the sequence of related prefixes have different next hops.
   However, adjacent prefixes in any set of related prefixes which have
   the _same_ next hop show that there is an extra route in the FIB--the
   more-specific route does not provide any more routing information
   than does the less-specific route.  Whenever a different next hop is
   encountered in more-specific information, though, it must be
   preserved.

   Therefore, CIDR-C means that this layering of next hops cannot be
   violated; it must be an invariant of the transformation f().
   Conversely, CIDR-C also means that adjacent prefixes in a set of
   related prefixes which have the same next hop can be safely
   aggregated, assuming that any other constraints developed below are
   also enforced; clearly, this will not violate our general constraint
   on f().

5.3.2 BGP4-Related Implications of the Constraint

   RFC1771, the current BGP4 specification, says that a BGP4 speaker

           - must have next hops for all routes in the Loc-RIB
             in its FIB,[9] and

           - cannot advertise routes which it doesn't use.[10]

   How are these to be handled?  The first requirement of RFC1771 will
   be broken in the letter of the rule but will kept in the spirit via
   the constraint on f(), since FIB' will route in the same way that FIB
   routes.  Similarly, the second requirement is kept in spirit via the
   announcement only of "best" routes (the horizontal path doesn't
   change with FIB aggregation) and in routing fact via the
   implementation of the new f(), though, again, not all routes in the
   Loc-RIB are actually used.

5.3.3 Related Considerations

   There is an additional, particularly salient feature of aggregation
   which needs to be considered by any algorithm for aggregation,
   particularly for FIB aggregation; though obvious, it must be
   remembered that only similar kinds of routes can be subjected to



S. J. Richardson                                               ^L[Page 12]


INTERNET-DRAFT                                                March 1996


   aggregation by f() in order to uphold the constraint.  As alluded to
   in section 5.3.1, above, CIDR-2 implies that, along with "normal"
   routes to real destinations (i.e., those routes which have next hops
   that result in furthering the delivery of packets), a router's kernel
   may well support, e.g., "reject" or "blackhole" routes. Clearly,
   these represent different "route types" which cannot be aggregated
   with "normal" routes without causing changes to routing, in violation
   of the invariance of routing which we require of the transformation
   function f().

   Indeed, while NLRI at the peer-session level are often considered to
   consist of triples of the form:

        <destination, next hop, path attributes>

   routing entries in terms of the kernel can be considered to consist
   of the quintuples:

        <destination, next hop, route type, ToS/QoS, other path attributes>

   in that "route type" and ToS/QoS values affect the processing of NLRI
   in actual forwarding decisions (note that "route type" is really
   tagged only at the local router, and therefore varies with local
   policy, as well as being kernel-dependent).

   Just as with "route type", different ToS/QoS values represent
   boundaries across which aggregation cannot occur.  Since the FIB or
   FIBs consist of either an elected ToS/QoS or a set of FIBs (one for
   each value of ToS/QoS supported by the kernel or the routing domain),
   the function f() must be applied to each FIB independently, and
   therefore will not aggregate across different ToS/QoS values.

   In fact, careful consideration of the implication of the existence of
   different types of routes leads to a new criterion:

           TYPE-C) In order to satisfy the constraint in view of the
                   existence of different types of routes, it is necessary
                   to maintain the "stratification of route types".

   TYPE-C is to be understood in the manner analogous to the
   understanding of CIDR-C; if a set of related prefixes which contains
   prefixes of various types is examined, it will become clear that
   differences and layering of route type also have to be kept invariant
   by the transformation f().

   Therefore, to continue the analogy with CIDR-C, TYPE-C also means
   that adjacent prefixes in a set of related prefixes which have the
   same type can be safely aggregated, assuming that CIDR-C is also



S. J. Richardson                                               ^L[Page 13]


INTERNET-DRAFT                                                March 1996


   kept; as above, this will not violate our general constraint on f().

   Finally, it is important for any implementor of f() to keep in mind
   kernel-specific limitations when attempting to create code for a
   range of machines, some which could have kernels which don't even
   support CIDR routes (and, therefore, for which f() may be essentially
   unimplementable or of extremely little utility).  Though this should
   be obvious, it may make adherence to TYPE-C difficult.

5.4 Solution of f()

5.4.1 FIB Representation

   The FIB aggregation function can be described in terms of any
   convenient basis representation of the FIB; let us consider the
   "candidate FIB"--the FIB to be transformed via application of f() to
   FIB', the aggregated FIB--to be stored in a radix trie (with the
   default route, if any, at the root of the trie, and the longest
   prefixes stored furthest away from the root; prefix length increases
   as one becomes more distant from the root).  The general advantages
   of this representation are numerous; for our purposes, the fact that
   potential aggregate prefixes of the prefix associated with a given
   node will lie on the path to the root is of prime importance.

5.4.2 Solution of f()--Simple Case

   For the case where this candidate FIB is entirely composed of normal,
   active routes (i.e., where there are no reject or other routes which
   are to be interpreted in a manner other than that of a normal, active
   route) to the destinations, the algorithm is simple:

           If
             the next hop for a destination associated with a child node
             is the same as
             the next hop associated with the parent node,
           then
             the destination/next hop associated with the child node
             is EXCLUDED FROM FIB';
           otherwise,
             the destination/next hop associated with the child node
             is INCLUDED IN FIB'.

   Clearly, this will result in a FIB' which upholds the constraint
   expressed in section 5.2 above; child nodes which have the same next
   hop as the parent do not contribute additional information to
   routing.  When differences in next hops are detected, the child's
   information is used, which fulfills the "stratification of next hops"
   criterion CIDR-C from section 5.3.1 above.  (The stratification of



S. J. Richardson                                               ^L[Page 14]


INTERNET-DRAFT                                                March 1996


   types, criterion TYPE-C from section 5.3.3 above, is guaranteed by
   the degenerate nature of the candidate FIB.)

5.4.3 Solution of f()--General Case

   For the more general case of a candidate FIB which contains several
   different types of routes we need only slightly revise the above
   text:

           If
             the next hop and route type for a destination associated
                   with a child node
             are the same as
             the next hop and route type associated with the parent node,
           then
             the destination/next hop associated with the child node
             is EXCLUDED FROM FIB';
           otherwise,
             the destination/next hop associated with the child node
             is INCLUDED IN FIB'.

   Clearly, this solution satisfies both CIDR-C and TYPE-C as well as
   the overriding constraint GENERAL-C.

6. Conclusion and Next Steps

   The algorithms for f() presented above guarantee that the three
   constraints presented in this document (GENERAL-C, CIDR-C, and TYPE-
   C) are all enforced; via the removal of routing information which
   contributes nothing to the actual forwarding decisions made by a
   router, the FIB is transformed to a smaller FIB, FIB', which has the
   same routing characteristics as FIB.

   The measures propounded in this document will, in general, have an
   effect which varies as a function of the number of next hops which a
   given router has, and therefore may not have as much utility in
   border routers as in non-border routers.   However, this scheme will
   certainly aid a given RD to have greater control over the size of its
   own FIBs (reducing the impact of RDs which have done a poor job of
   aggregating their outbound routing announcements) without
   jeopardizing either the consistency of routing information or the
   actual routing of IP packets.

   The actual effects of the implementation and use of f() have yet to
   be measured, and this is the pressing "next step" in the evaluation
   of the usefulness of "vertical"/FIB aggregation.  The author is
   currently implementing f() in GateD and hopes to have concrete
   numbers available shortly; other implementations and results are



S. J. Richardson                                               ^L[Page 15]


INTERNET-DRAFT                                                March 1996


   obviously both welcome and useful, too, in order to attempt to
   quantify the benefits of using vertical aggregation.

7. Security Considerations

   Security considerations are not discussed in this document.

8. Acknowledgements

   The author would like to thank Sue Hares of Merit Network, Inc. for
   her encouragement and review of this document.  Additionally, he
   would like to thank both Ms. Hares and Laurent Joncheray (also of
   Merit Network, Inc.) for providing helpful information and
   suggestions related to implementing the algorithm described in this
   document in GateD.  Thanks also to Radia Perlman for her review of
   this work.

9. Author's  Address

   Steven J. Richardson
   Merit Network, Inc.
   4251 Plymouth Rd., Suite C
   Ann Arbor, MI  48105-2785

   email:  sjr@merit.edu
   phone:  (313) 647-4813
     fax:  (313) 647-3185

10. Notes

   [1]  This is taken from information exchanged on the cidrd email list
   in late February/early March 1996.

   [2]  This diagram was inspired by Figure 7., entitled "Routeing
   Information Base," on p. 91 of the reference ISO10747.

   [3]  See, e.g., RFC1771, section 3.2.

   [4]  See, e.g., RFC1771, sections 9.1, 9.1.3, and 9.2.4.2 for BGP4
   aggregation and the decision process, and sections 7.16, 7.16.3,
   7.16.3.1, 7.18.2, 7.18.2.1 - 7.18.2.3 of ISO10747 for IDRP
   aggregation and the decision process.

   [5]  See, e.g., RFC1771, sections 9.1, 9.1.1 and 9.2.1 for the BGP4
   internal update process and its placement in the decision process.

   [6]  This is documented, e.g., in the gated-R3_6Alpha_1 release
   (available at ftp://ftp.gated.org/net-research/gated/gated-



S. J. Richardson                                               ^L[Page 16]


INTERNET-DRAFT                                                March 1996


   R3_6Alpha_1.tar.gz), in the BGP configuration statement.

   [7]  Clearly, as with any routing policy, any FIB aggregation
   function f() which is adopted by a given routing domain should be
   applied consistently across all of its routers, though the
   constraint's requirement that FIB' yield the same routing as that
   generated by FIB means that a routing domain need _not_ implement f()
   in all of its routers.

   [8]  RFC1771, sections 4.2 and 4.3.

   [9]  RFC1771, section 3.1.

   [10]  RFC1771, sections 3.1, 9.1 (esp. the paragraph labelled "c)"),
   and 9.1.3.

11. References

ISO10747   "Information Processing Systems - Telecommunications and Information
           Exchange between Systems - Protocol for Exchange of Inter-domain
           Routeing Information among Intermediate Systems to Support Forwarding
           of ISO 8473 PDUs", Proposed Draft of ISO/IEC 10747, 04/27/1993.

RFC1518    Y. Rekhter, T. Li, "An Architecture for IP Address Allocation with
           CIDR", 09/24/1993.

RFC1519    V. Fuller, T. Li, J. Yu, K. Varadhan, "Classless Inter-Domain
           Routing (CIDR): an Address Assignment and Aggregation Strategy",
           09/24/1993.

RFC1520    Y. Rekhter, C. Topolcic, "Exchanging Routing Information Across
           Provider Boundaries in the CIDR Environment", 09/24/1993.

RFC1771    Y. Rekhter, T. Li, "A Border Gateway Protocol 4 (BGP-4)",
           03/21/1995.

RFC1772    Y. Rekhter, P. Gross, "Application of the Border Gateway Protocol
           in the Internet", 03/21/1995.

RFC1817    Y. Rekhter, "CIDR and Classful Routing", 08/04/1995.











S. J. Richardson                                               ^L[Page 17]