Internet Info 1997 December

home *** CD-ROM | disk | FTP | other *** search

/ Internet Info 1997 December / Internet_Info_CD-ROM_Walnut_Creek_December_1997.iso / drafts / draft_n_r / draft-richardson-fib-reduction-00.txt < prev next >

Wrap

Text File | 1996-07-15 | 38KB | 1,017 lines

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]