Network Working Group Internet-Draft H.Berkowitz E.Davies Nortel Networks L. Andersson Utfors Broadband July 2001 Expires December 2001 Document: draft-berkowitz-tblgrow-00.txt An Experimental Methodology for Analysis of Growth in the Global Routing Table Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026 [ ]. 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." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Abstract Measurements [3,4,5] have shown that the rate of growth of routes and route instances in the default-free table have resumed exponential growth, which had slowed to linear growth after the introduction of CIDR [7]. This memorandum explores some analytical methods, admittedly heuristic in most cases, to understand why growth is faster than the simple rate of allocation. When accelerated growth can be attributed to operational practices or poor understanding, it may be possible to propose approaches to reducing the rate of table explosion without reducing the services delivered to end users. Conventions used in this document The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC-2119 [2]. 1. Introduction When Classless Inter-domain routing (CIDR) [6] was developed almost a decade ago, one of the main aims was to remedy the exponential growth of the routing tables in a default free router. CIDR achieved this aim and the growth rate of routing tables has been close to the allocation rate until quite recently. However, today we see that therouting tables in default free routers have again started to grow at a rate that is nearing exponential. In this memorandum we investigate some hypotheses that might explain why this routing table growth is taking place. In future work we will also try to verify the extent of the contribution to the growth from each cause. To do this we sample routing tables from default-free routers at several points. To the samples we apply various analyses to attempt to quantify the contribution from various hypothetical explanations for growth. 2. Identifying Prefixes Multihomed to Multiple Providers The basic algorithm for identifying a possible multihomed prefix is to examine prefix P of length L (i.e., P/L) originated by the same Autonomous System (AS). If we can find at least two route instances originated by ASx: *...ASy ASx P/L *...ASz ASx P/L where x, y, and z are different AS numbers, we define prefix P/L to be multihomed. The list of AS numbers (..., ASn, ASm) is called an AS path, an attribute to BGP, and describes the path over which the route has been learnt. The normal case is that traffic is forwarded over the shortest AS path. We will count the number of multihomed prefixes, and the number of adjacent AS to which they are multihomed. Multihoming may exist for a number of different reasons, e.g. a recognized traffic engineering policy. It might also exist because customers demand it without thinking through a complete fault tolerance strategy. One of the authors had a customer who demanded dual-ring SONET connectivity to two independent ISPs, but had only one application server. A subsequent step may be to verify whether or not a routing policy showing this multihoming exists in a routing registry. 3. Inconsistent AS Advertising and Possible Multihoming RFC 1771 states that only one AS should originate a given prefix. While this practice is generally followed, some multihoming scenarios, either deliberately or inadvertently, allow more than one AS to originate the same prefix. One scenario in which the prefix is valid, admittedly a preferred one, involves an end routing domain that does not have its own AS number but advertises routes using an IGP or static definition to multiple ISPs. The ISPs inject those routes into their own routing systems and advertise them to the general Internet. A more likely scenario is that the end routing domain uses a private AS number for BGP connectivity to more than one AS, but the ISP(s) simply strip the private AS number and appear to originate the route. Again, as a later step, we'd like to use registry data as a possible explanation. Whilst the extent of this type of advertisement is not known, for cases where it is allowed/preferred they should be made explicit. 4. Inexperienced ISPs 4.1 Inappropriate De-aggregation BGP is a protocol that requires, comparatively, a great deal of experience to use it safely and effectively, another area causing route table growth may be inexperienced staff in ISPs. Since it is unlikely that all of an ISP's customers require the same amount of address space, and not all customers will be multihomed and thus require their more-specifics to be advertised, one of the first tests will be to scan through the list of initial address allocations (e.g., /19 or /20), and examine the routing table to see which of these has: 1. All space advertised in equal-length more-specifics (e.g., a case where all 32 /24's of one /20 are advertised separately) 2. More-specifics that are not advertised by any other ISP (i.e. the same ISP advertises both the initial address allocation and a subset of that allocation with the same AS part) 4.2. Advertisement of un-assigned address spaces Another test is to examine SWIP or other registry databases and find address space that is advertised but not assigned. 5. Traffic Engineering with a Single Provider It is possible that certain more-specifics are being generated not for the reasons of inexperience described in the previous section, but to attempt to control how traffic flows to the end enterprise. Unfortunately for measurement purposes, much of this traffic engineering may be invisible outside the initial provider AS. Nevertheless, it may be possible to infer attempts at traffic engineering if we can find route instances with the properties: *... ASy ASx P1/L *... ASz ASx P2/L where there are at least two different shorter prefixes (P1 and P2) with the same length (L ) from ASx's address space. This may simply be due to multihoming, but if the P's could have been aggregated and were not, it is possible that the different instances are present in an attempt to traffic-engineer. 6. References [1] Bradner, S., "The Internet Standards Process - Revision 3", BCP 9, RFC 2026, October 1996. [2] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", RFC 2119, Harvard University, March 1997 [3] Smith,P. Weekly Traffic Summary [4] Bates, T., The CIDR Report. [5] Huston, G. Presentation to IETF Plenary, March 2001 [6] Fuller, V., Li, T., Yu, J. and Varadhan, K., "Classless Inter-Domain Routing (CIDR): an Address Assignment and Aggregation Strategy", RFC 1519, September 1993. 7. Acknowledgments 8. Author's Addresses Howard Berkowitz Nortel Networks 5012 S. 25th St Arlington VA 22206 USA Phone: +1 703 998-5819 (ESN 451-5819) Fax: +1 703 998-5058 EMail: hberkowi@nortelnetworks.com hcb@clark.net Elwyn Davies Nortel Networks Harlow Laboratories London Road Harlow Essex CM17 9NA UK Phone: +44 1279 405498 (ESN 742 5498) Fax: +44 1279 402047 Email: elwynd@nortelnetworks.com Loa Andersson Utfors Bredband AB Box 525 SE-169 29 Solna Sweden Phone: +46 8 5270 5038 Fax: +46 8 5270 2595 Email: loa.Andersson@utfors.se Full Copyright Statement "Copyright (C) The Internet Society (date). All Rights Reserved. This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implmentation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into. Cause Analysis of Growth in the Global Routing Table July 2001 Berkowitz, et al Expires January 2002 5