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].

. 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.

. 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.

. 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.


. 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.

. 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.

. References

   []  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.

. Acknowledgments


. 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