Network Working Group D. Meyer, Ed.
Internet-Draft L. Zhang, Ed.
Intended status: Informational K. Fall, Ed.
Expires: June 18, 2007 December 15, 2006
Report from the IAB Workshop on Routing and Addressing
draft-iab-raws-report-00.txt
Status of this Memo
By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of BCP 79.
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.
This Internet-Draft will expire on June 18, 2007.
Copyright Notice
Copyright (C) The Internet Society (2006).
Abstract
This document reports the outcome of the Routing and Addressing
Workshop which the Internet Architecture Board (IAB) held on October
18-19, 2006 in Amsterdam, Netherlands. The primary goal of the
workshop was to develop a shared understanding of the problems that
the large backbone operators are facing regarding the scalability of
today's Internet routing system. The key workshop findings include
an analysis of the major factors that are driving routing table
growth, constraints in router technology, and the limitations of
Meyer, et al. Expires June 18, 2007 [Page 1]
Internet-Draft IAB Workshop on Routing & Addressing December 2006
today's Internet addressing architecture. It is hoped that these
findings will serve as input to the IETF community and help identify
next steps towards effective solutions.
Note that this document is a report on the proceedings of the
workshop, and it is not an IAB document. The views and positions
documented in this report are those of the workshop participants and
not the IAB.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
2. Key Findings from the Workshop . . . . . . . . . . . . . . . . 4
2.1. Problem #1: The Scalability of the Routing System . . . . 5
2.1.1. Implications of DFZ RIB Growth . . . . . . . . . . . . 5
2.1.2. Implications of DFZ FIB Growth . . . . . . . . . . . . 6
2.2. Problem #2: The Overloading of IP Address Semantics . . . 7
2.3. Other Concerns . . . . . . . . . . . . . . . . . . . . . . 8
2.4. How Urgent are these Problems? . . . . . . . . . . . . . . 8
3. Current Stresses on the Routing and Addressing System . . . . 9
3.1. Major Factors Driving Routing Table Growth . . . . . . . . 9
3.1.1. Avoiding Renumbering . . . . . . . . . . . . . . . . . 10
3.1.2. Multihoming . . . . . . . . . . . . . . . . . . . . . 10
3.1.3. Traffic Engineering . . . . . . . . . . . . . . . . . 11
3.2. IPv6 and its potential impact on routing table size . . . 12
4. Implications of Moore's Law on the Scaling Problem . . . . . . 12
4.1. Integrated Circuits . . . . . . . . . . . . . . . . . . . 12
4.2. Heat and Power . . . . . . . . . . . . . . . . . . . . . . 13
5. What is on the Horizon . . . . . . . . . . . . . . . . . . . . 13
5.1. Continual Growth . . . . . . . . . . . . . . . . . . . . . 14
5.2. Large Numbers of Mobile Networks . . . . . . . . . . . . . 14
5.3. Orders of magnitude increase in mobile edge devices . . . 14
6. What Approaches Have Been Investigated . . . . . . . . . . . . 15
6.1. Lessons from MULTI6 . . . . . . . . . . . . . . . . . . . 15
6.2. SHIM6: Pros and Cons . . . . . . . . . . . . . . . . . . . 16
6.3. GSE/indirection solutions: Costs and Benefits . . . . . . 17
6.4. Futures for Indirection . . . . . . . . . . . . . . . . . 18
7. Problem Statements . . . . . . . . . . . . . . . . . . . . . . 19
7.1. Problem 1: Routing Scalability . . . . . . . . . . . . . . 19
7.2. Problem 2: The overloading of IP address semantics . . . . 20
7.2.1. Definition of Locator and Identifier . . . . . . . . . 20
7.2.2. Consequence of Locator and Identifier Overloading . . 21
7.2.3. Traffic Engineering and IP Address Semantics
Overload . . . . . . . . . . . . . . . . . . . . . . . 21
7.3. Routing Convergence . . . . . . . . . . . . . . . . . . . 22
7.4. Misaligned Costs and Benefits . . . . . . . . . . . . . . 23
7.5. Other Issues . . . . . . . . . . . . . . . . . . . . . . . 23
Meyer, et al. Expires June 18, 2007 [Page 2]
Internet-Draft IAB Workshop on Routing & Addressing December 2006
7.6. Problem Recognition . . . . . . . . . . . . . . . . . . . 24
8. Criteria for Solution Development . . . . . . . . . . . . . . 24
8.1. Criteria on Scalability . . . . . . . . . . . . . . . . . 24
8.2. Criteria on Incentives and Economics . . . . . . . . . . . 25
8.3. Criteria on Timing . . . . . . . . . . . . . . . . . . . . 26
8.4. Consideration on Existing Systems . . . . . . . . . . . . 26
8.5. Consideration on Security . . . . . . . . . . . . . . . . 27
8.6. Other Criteria . . . . . . . . . . . . . . . . . . . . . . 27
8.7. Understanding the Tradeoff . . . . . . . . . . . . . . . . 27
9. Workshop Recommendations . . . . . . . . . . . . . . . . . . . 28
10. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 29
11. Security Considerations . . . . . . . . . . . . . . . . . . . 29
12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Appendix A. Suggestions for Specific Steps . . . . . . . . . . . 31
Appendix B. Workshop Participants . . . . . . . . . . . . . . . . 32
Appendix C. Workshop Agenda . . . . . . . . . . . . . . . . . . . 33
Appendix D. Presentations . . . . . . . . . . . . . . . . . . . . 34
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 34
Intellectual Property and Copyright Statements . . . . . . . . . . 35
Meyer, et al. Expires June 18, 2007 [Page 3]
Internet-Draft IAB Workshop on Routing & Addressing December 2006
1. Introduction
It is commonly recognized that today's Internet routing and
addressing system is facing serious scaling problems. The ever
increasing user population, as well as multiple other factors
including multi-homing, traffic engineering, and policy routing, have
been driving the growth of Default Free Zone (DFZ) routing table size
at an alarming rate [DFZ]. While it has been long recognized that
the existing routing architecture may have serious scalability
problems, effective solutions have yet to be identified, developed,
and deployed.
As a first step towards tackling these long standing concerns, the
IAB held a "Routing and Addressing Workshop" in Amsterdam,
Netherlands on October 18-19, 2006. The main objectives of the
workshop were to identify existing and potential factors that have
major impacts on routing scalability, and to develop a concise
problem statement that could serve as input to a set of follow-on
activities. This document reports on the outcome from that workshop.
The remainder of the document is organized as follows: Section 2
captures the high level findings from the workshop. Section 3
describes the sources of stress in the current global routing and
addressing system. Section 4 discusses the relationship between
Moore's law and our ability to build large routers. Section 5
describes some of the factors that could exacerbate the current
problems outlined in Section 2. Section 6 describes previous work in
this area. Section 7 describes the problem statements in more
detail, and Section 8 discusses the criteria that constrain the
solution space. Finally, Section 9 summarizes the recommendations
made by the workshop participants.
The workshop participant list is attached in Appendix B. The agenda
can be found in Appendix C, and Appendix D provides pointers to the
presentations from the workshop.
Finally, note that this document is a report on the outcome of the
workshop, not an official document of the IAB. Any opinions
expressed are those of the workshop participants and not the IAB.
2. Key Findings from the Workshop
This section provides a concise summary of the key findings from the
workshop. While many other aspects of a routing and addressing
system were discussed, the findings described here were deemed most
important by the workshop participants.
Meyer, et al. Expires June 18, 2007 [Page 4]
Internet-Draft IAB Workshop on Routing & Addressing December 2006
The clear highest priority takeaway from the workshop was the need to
devise a scalable routing and addressing system, one which is
scalable in the face of multihoming, and which facilitates a wide
spectrum of traffic engineering (TE) requirements. While several
scalability features of the routing and addressing systems were
discussed, most related to the size of the DFZ routing table
(frequently referred to as the Routing Information Base, or RIB) and
its implications. Those implications included (but were not limited
to) the sizes of the DFZ RIB and FIB (the Forwarding Information
Base), the cost of recomputing the FIB, concerns about the BGP
convergence times in the presence of growing RIB and FIB sizes, and
the costs and power (and hence heat dissipation) properties of the
hardware needed to route traffic in the core of the Internet.
2.1. Problem #1: The Scalability of the Routing System
The shape of the growth curve of the DFZ RIB has been the topic of
much research and discussion since the early days of the Internet
[DFZ]. There have been various hypotheses regarding the sources of
this growth. The workshop consensus is that the following factors
are the main driving forces behind the rapid growth of the DFZ RIB:
o Multihoming,
o Traffic engineering,
o Suboptimal RIR address allocations, and
o Business events such as mergers and acquisitions.
All of the above factors can lead to prefix de-aggregation and/or the
injection of unaggregatable prefixes into the DFZ RIB. This de-
aggregation leads to routing scalability problem because, absent some
non-topologically based routing technology (for example, Routing On
Flat Labels [ROFL], or Compact Routing [CNIR]), topological
aggregation is the only known practical approach to control the
growth of the DFZ RIB. The following section reviews the workshop
discussion of the implications of the growth of the DFZ RIB.
2.1.1. Implications of DFZ RIB Growth
Presentations made at the workshop showed that the DFZ RIB has been
growing at greater than linear rates for several years [DFZ]. While
this has the obvious effects on the requirements for RIB and FIB
memory sizes, the growth driven by prefix de-aggregation also exposes
the core of the network to the dynamic nature of the edges.
One particularly troublesome result of prefix de-aggregation is that
Meyer, et al. Expires June 18, 2007 [Page 5]
Internet-Draft IAB Workshop on Routing & Addressing December 2006
it leads to an increased number of BGP UPDATE messages injected into
the DFZ (frequently referred to as "UPDATE churn") and consumes the
corresponding processing resources. This additional processing is
required to maintain state for the longer prefixes and to compute the
FIB. Note that, although the size of the RIB is bounded by the given
address space size (i.e. O(m*2^32) for IPv4, where <m> is a slow
moving function that describes the interconnection mesh of the
Internet), the dynamic nature of the edges is not. As a result, the
amount of BGP UPDATE churn that the network can experience is
essentially unbounded. It was also noted that the UPDATE churn, as
currently measured, is heavy-tailed [ATNAC2006]. That is, a
relatively small number of Autonomous Systems (ASes) are responsible
for a disproportionately large fraction of the UPDATE churn that we
observe today. Furthermore, much of the churn may turn out to be
unnecessary information, possibly injected to arbitrage some
bandwidth pricing model or the like (see [GIH], for example, or the
discussion of the behavior of AS 9121 in [BGP2005]).
Finally, it was noted by the workshop participants that the UPDATE
churn situation may be exacerbated by the current Regional Internet
Registry (RIR) policy in which end sites are allocated Provider
Independent (PI) addresses. These addresses are not topologically
aggregatable, and as such bring the churn problem described above
into the core routing system. Of course, as noted by several
participants, the RIRs have no real choice in this matter, as many
enterprises demand PI addresses which allow them to multihome without
the "provider lock" that Provider Allocated (PA) [PIPA] address space
creates. Some enterprises also find the renumbering cost associated
with PA address assignments unacceptable.
2.1.2. Implications of DFZ FIB Growth
[Editor's note: The conclusions reviewed in this section have been
the subject of considerable debate since the workshop. As such, more
exploration of these topics is indicated.]
Perhaps the most surprising outcome of the workshop was the
observation made by Tony Li about the relation between "Moore's Law"
[ML] and our ability to build large scale routers. "Moore's Law" is
the empirical observation that the transistor density of integrated
circuits doubles roughly every 24 months, and many people believe
that Moore's Law solves the problem of scaling core router hardware.
However Li pointed out that Moore's Law does not necessarily apply to
building high-end routers. In particular, Moore's Law applies
specifically to on-chip transistor density and is applicable only to
high-volume processors. It is not necessarily applicable to the low-
volume, custom processors needed to forward traffic at the rates
commonly found in the core of the Internet. Furthermore, Moore's Law
Meyer, et al. Expires June 18, 2007 [Page 6]
Internet-Draft IAB Workshop on Routing & Addressing December 2006
does not apply to the clock speeds of the chip. While DRAM capacity
has grown in accordance with Moore's law (at a rate of approximately
2.4 times every 2 or so years), memory clock rates have grown at a
much lower rate (roughly 1.2 times every two years according to Tony
Li's presentation; see Appendix D).
2.2. Problem #2: The Overloading of IP Address Semantics
One of the fundamental assumptions underlying the scalability of
routing systems was eloquently stated by Yakov Rekhter (and is
sometimes referred to as "Rekhter's Law"), namely that, in general:
"Addressing can follow topology or topology can follow
addressing. Choose one."
The same idea was expressed by Mike O'Dell in his design of GSE
(formerly 8+8) [GSE], where the address structure was designed
explicitly to scale the routing system by providing for "aggressive
topological aggregation". Noel Chiappa has also written extensively
on this topic (see, e.g., [EID]).
There is, however, a difficulty in creating (and maintaining) the
kind of congruency envisioned by Rekhter's Law in today's Internet.
The difficulty arises from the overloading of addressing with the
semantics of both "who" (endpoint identifier for the transport layer)
and "where" (locators for the routing system); some might also add
that IP addresses are also overloaded with "how" [GIH]. In any
event, this kind of overloading is felt to have had deep implications
for the scalability of the global routing system.
A refinement to Rekhter's Law, then, is that for a routing system to
scale, the locator part of IP address must be assigned in such a way
that it is congruent with the Internet's topology. However, as
identifiers are typically assigned based upon organizational (not
topological) structure and have stability as a desirable property, a
"natural incongruence" arises. As a result, it is difficult (if not
impossible) to make a single number space serve both purposes
efficiently. Of course this conclusion assumes, as mentioned above,
that no effective "non-topological routing system" exists.
Following the logic of the previous paragraphs, workshop participants
concluded that the so-called "locator/identifier overload" of the IP
address semantics one of the causes of the routing scalability
problem as we see today. Thus such a "split" seems necessary to
scale the routing system, although how to actually architect and
implement such a split was not explored in detail.
Meyer, et al. Expires June 18, 2007 [Page 7]
Internet-Draft IAB Workshop on Routing & Addressing December 2006
2.3. Other Concerns
In addition to the issues described in Section 2.1 and Section 2.2,
the workshop participants identified several pressing issues that
were considered "second tier" issues. These included
o General concerns with IPv6 deployment,
o Slow routing convergence, and
o Misalignment of costs and benefits in the current routing system.
The primary issue with IPv6 deployment was that, in the absence of a
scalable routing strategy, IPv6 has the potential to exacerbate
today's problems simply by the virtue of its much larger address
space. The only routing paradigm available today for IPv6 is a
combination of CIDR [RFC4632] and provider independent (PI) address
allocation strategies [PIPA] (and possibly SHIM6 [SHIM6] when that
technology is developed and deployed). Thus the opportunity exists
to create a "swamp" (unaggregatable address space) that can be many
orders of magnitude larger than what we faced with IPv4. Of course,
this is not independent of the concerns raised in both Section 2.1
and Section 2.2. The key takeaway was that the advent of IPv6 and
its larger address space has the potential to make these problems
much worse if a solution isn't found.
Routing convergence was also seen to be an issue that the workshop
participants felt needed attention. In particular, the concern was
that the growth in the number of routes that service providers must
carry will cause routing convergence to become a significant problem.
Finally, the workshop participants felt that the costs and benefits
in today's routing system are misaligned. While the IETF does not
typically consider the "business model" impacts various technology
choices directly, many participants felt that perhaps the time has
come to review that philosophy.
2.4. How Urgent are these Problems?
There was a fairly universal agreement among the workshop
participants that the problems outlined in Section 2.1 and
Section 2.2 need immediate attention. This need was not because the
participants perceived a looming, well-defined "hit the wall" date,
but rather because these are difficult problems that to date have
resisted solution, that are likely to get more unwieldy as IPv6
deployment proceeds, and that the development and deployment of an
effective solution will necessarily take at least a few years.
Meyer, et al. Expires June 18, 2007 [Page 8]
Internet-Draft IAB Workshop on Routing & Addressing December 2006
3. Current Stresses on the Routing and Addressing System
The primary concern voiced by the workshop participants regarding the
state of the current Internet routing system was the rapid growth of
the DFZ RIB. The number of entries in 2005 ranged from about 150,000
entries to 175,000 entries [BGP2005]; this number has reached 200,000
today [CIDRRPT], and is projected to increase to 370,000 or more
within 5 years. Some workshop participants projected that the DFZ
could reach 2 million entries within 15 years, and with as many as 10
million multihomed sites by 2050.
Another related concern was the number of prefixes changed, added,
and withdrawn as a function of time (i.e., BGP UPDATE churn). This
has a detrimental impact on routing convergence, since UPDATEs
frequently necessitate a re-computation and download of the FIB. For
example, in August 2005 alone some 400,000 changes were recorded
[BGP2005]. Such UPDATE churn problems are not limited to DFZ routes;
indeed, the number of internal routes carried by large ISPs also
threatens convergence times, given that such internal routes include
more specifics, VPN routes, and other routes that do not appear in
the DFZ [ATNAC2006].
Furthermore, some of the properties of BGP were seen as problematic.
Although BGP routing updates are propagated between AS neighbors, the
number of elements in a RIB or FIB is determined by the total number
of IP prefixes being routed in the Internet, and not by the number of
ASes or length of AS paths. It was noted that a number of large ASes
advertise over 1000 prefixes each [BGP2005].
3.1. Major Factors Driving Routing Table Growth
The growth of the DFZ RIB results from the addition of more prefixes
to the table. Although some of this growth is organic (i.e., results
simply from growth of the Internet), a large portion of the growth
results from de-aggregation of address prefixes (i.e., more specific
prefixes). In this section, we discuss in more detail why this
alarming trend is accelerating.
An increasing fraction of the more-specific prefixes found in the DFZ
are due to deliberate action on the part of operators [ATNAC2006].
Motivations to advertise these more-specifics include:
o Traffic Engineering, where load is balanced across multiple links
through selective advertisement of more-specific routes on
different links to adjust the amount of traffic received on each;
and
Meyer, et al. Expires June 18, 2007 [Page 9]
Internet-Draft IAB Workshop on Routing & Addressing December 2006
o Attempts to prevent prefix-hijacking by other operators who might
advertise more-specifics to steer traffic toward them; there are
several known instances of this behavior today.
3.1.1. Avoiding Renumbering
The workshop participants noted that customers generally prefer to
have PI address space. Doing so gives them additional agility in
selecting ISPs and helps them avoid the need to renumber. Many end-
systems use DHCP to assign addresses, so a cursory analysis might
suggest renumbering might involve modification of a modest number of
routers and servers (perhaps rather than end hosts) at a site that
was forced to renumber.
In reality, however, renumbering can be more cumbersome because IP
addresses are often used for other purposes such as access control
lists. They are also sometimes hard-coded into applications used in
environments where failure of the DNS would be catastrophic (e.g.
some remote monitoring applications). Although renumbering may be a
mild inconvenience for some sites and guidelines have been developed
for renumbering a network without a flag day [RFC4192], for others
the necessary changes are sufficiently difficult that makes
renumbering effectively impossible.
For these reasons, PI address space is sought by a growing number of
customers. Current RIR policy reflects this trend, and their policy
is to allocate PI prefixes to all customers who claim a need.
Routing PI prefixes requires additional entries in the DFZ routing
and forwarding tables. At present, ISPs do not typically charge to
route PI prefixes. Therefore, the "costs" of the additional
prefixes, in terms of routing table entries and processing overhead,
is not born directly by the users of PI space; rather the cost is
borne by the global routing system as a whole. Finally, workshop
participants observed that no strong disincentive exists to
discourage the increasing use of PI address space.
3.1.2. Multihoming
Multihoming refers generically to the case in which a site is served
by more than one ISP [RFC4116]. There are several reasons for the
observed increase in multihoming, including the increased reliance on
the Internet for mission and business-critical applications and the
general decrease in cost to obtain Internet connectivity.
Multihoming provides backup routing-- Internet connection redundancy;
in some circumstances multihoming is mandatory due to contract or
law. Multihoming can be accomplished using either PI or PA address
space, and multihomed sites generally have their own AS numbers
(although some do not; this generally occurs when such customers are
Meyer, et al. Expires June 18, 2007 [Page 10]
Internet-Draft IAB Workshop on Routing & Addressing December 2006
statically routed).
A multihomed site using PI address space has its prefixes present in
the forwarding and routing tables of each of its providers. For PA
space, each prefix allocated from one provider's address allocation
will be aggregatable for that provider but not the others. If the
addresses are allocated from a 'primary' ISP (i.e. one that the site
uses for routing unless a failure occurs), then the additional
routing table entries only appear during path failures to that
primary ISP. A problem with multihoming arises when a customer's PA
IP prefixes are advertised by AS(es) other than their 'primary' ISPs,
as the longest-match forwarding rule would force the primary ISPs to
de-aggregate its prefixes.
3.1.3. Traffic Engineering
Traffic engineering (TE) is the act of arranging for certain Internet
traffic to use or avoid certain network paths (that is, TE puts
traffic where capacity exists, or where some set of parameters of the
path is more favorable to the traffic being placed there). TE is
performed by both ISPs and customer networks, for three primary
reasons:
o First, as mentioned above, to match traffic with network capacity,
or spreading the traffic load across multiple links (frequently
referred to as "load balancing").
o Second, to reduce the cost by shifting traffic to lower cost paths
or by balancing the incoming and outgoing traffic volume to
maintain appropriate peering relations.
o Finally, TE is sometimes deployed to enforce certain forms of
policy (e.g., Canadian government traffic is not permitted to
transit through the United States).
BGP and the common IGPs (OSPF, IS-IS) provide few tools for traffic
engineering, so network operators usually achieve traffic engineering
by "tweaking" the processing of routing protocols to achieve desired
results. At the BGP level, if the address range requiring TE is a
portion of a larger PA address aggregate, network operators
implementing TE are forced to de-aggregate otherwise aggregatable
prefixes in order to steer the traffic of the particular address
range to specific paths.
In today's highly competitive environment, the use of TE is mandatory
for providers to keep good performance and low cost for each one's
own network. However the resulting increase of the DFZ RIB leads to
the increased cost of the Internet routing infrastructure as a whole.
Meyer, et al. Expires June 18, 2007 [Page 11]
Internet-Draft IAB Workshop on Routing & Addressing December 2006
3.2. IPv6 and its potential impact on routing table size
Due to the increased IPv6 address size over IPv4, a full immediate
transition to IPv6 is estimated to lead to the RIB and FIB sizes
increasing by a factor of about four. The size of the routing table
based on a more realistic assumption, that of parallel IPv4 and IPv6
routing for many years, is less clear. An increasing amount of
allocated IPv6 address prefixes is in PI space. ARIN [ARIN] has
relaxed their policy for allocation of such space and has been
allocating /48 prefixes when customers request for PI prefixes.
Thus, the same pressures affecting IPv4 address allocations also
affect IPv6 allocations.
4. Implications of Moore's Law on the Scaling Problem
[Editor's note: The information in this section is gathered from
presentations given at the workshop. The presentation slides can be
retrieved from the pointer provided in Appendix D. It is worth
noting that this information has generated quite a bit of discussion
since the workshop, and as such requires further community input.]
The workshop heard from Tony Li about the relationship between
Moore's law and the ability to build cost-effective high-performance
routers. Routers are generally required to hold a data structure to
encode the FIB in fast memory in a way convenient to execute the
longest prefix match (LPM) lookup algorithm. In executing LPM,
dedicated hardware will access relatively large fast memories (SRAM)
containing the required data structures (e.g. radix tries [RADIX]).
[Editor's note: The exact implementation of a high-performance
router's RIB and FIB memories is the subject of much debate.]
4.1. Integrated Circuits
In 1965 Gordon Moore projected that the density of transistors in
integrated circuits could double every two years, with respect to
minimum component cost. The period was subsequently adjusted to be
between 18-24 months and this conjecture became known as Moore's Law
[ML]. The semiconductor industry has been following this density
trend for the last 40 or so years.
This technology performance trend can, in principal, be achieved by
anyone involved in the design and production of integrated circuits.
However, the costs are not equal to all players. It is much easier
for large-volume manufacturing to track the technology trend at
reasonable cost. In particular, large-volume Integrated Circuits
(ICs) such as CPUs have been aggressively doing so, sometimes
Meyer, et al. Expires June 18, 2007 [Page 12]
Internet-Draft IAB Workshop on Routing & Addressing December 2006
improving over the 24 month prediction of Moore's Law. However
smaller volume devices (i.e. custom-built router forwarding engine
ASICs) cannot ride the same cost curve.
In earlier times, high volume production of SRAM was more common due
to its use as off-chip cache for supporting commodity CPUs. With the
migration of most cache memories to on-chip implementations, the
relative cost of off-chip SRAMs has increased due to their decreased
volumes. For DRAM, which is used to store RIB data for BGP and IGPs,
the speed only improves about 10%/year. Routing performance (i.e.
route computation time) scales as approximately T/D where T is the
table growth rate and D is the speed improvement of DRAM, and the
performance degrades when the value of T is greater than that of D.
See [ATNAC2006] for a discussion of some metrics around routing
performance. [Editor's note: [ATNAC2006] was not input to the
workshop, and is being cited by the editors as additional information
for the reader.]
4.2. Heat and Power
Transistors consume power both when idle ("leakage current") and when
switching. The smaller the transistors, the larger the leakage
current. The overall power consumption is not linear with the
density increase. Thus, as the need for more powerful routers
increases, cooling technology grows more taxed. At present, the
existing air cooling system is starting to be a limiting factor for
scaling high-performance routers.
A key metric for system evaluation is now the unit of forwarding
bandwidth per Watt-- [(Mb/s)/W]. About 60% of the power goes to the
forwarding engine circuits, with the rest divided between the
memories, route processors, and interconnect. Using parallelization
to achieve higher bandwidths can aggravate the situation, due to
increased power and cooling demands.
[Editor's note: Many in the community have commented that heat power
utilization and the attendant heat dissipation, along with size
limitations of fabrication processes are the current limiting
factors.]
5. What is on the Horizon
Routing and addressing are two fundamental pieces in the Internet
architecture, thus any changes to them will likely impact almost all
of the "IP stack", from applications to packet forwarding. In
resolving the routing scalability problems, as agreed upon by the
workshop attendees, we should aim at a long term solution. This
Meyer, et al. Expires June 18, 2007 [Page 13]
Internet-Draft IAB Workshop on Routing & Addressing December 2006
requires a clear understanding of various trends in the foreseeable
future: the growth in Internet user population, the applications, and
the technology.
5.1. Continual Growth
The backbone operators expect that the current Internet user
population base will continue to expand, as measured by the traffic
volume, the number of hosts connected to the Internet, the number of
customer networks, and the number of regional providers.
5.2. Large Numbers of Mobile Networks
Boeing's Connexion service pioneered the deployment of mobile
networks that may change their attachment points to the Internet in a
global scale. It is believed that such in-flight Internet
connectivity would likely become commonplace in the not-too-distant
future. When that happens, there can be multiple thousands of
airplane networks in the air at any given time.
Given today's DFZ RIB already handles over 200,000 prefixes
[CIDRRPT], several thousands of mobile networks, each represented by
a single prefix announcement, may not necessarily raise serious
routing scalability or stability concerns. However there is an open
question regarding whether this number can become substantially
larger, if other types of mobile networks, such as networks on
trains, come into play. If such mobile networks become commonplace,
then their impact on the global routing needs to be assessed.
5.3. Orders of magnitude increase in mobile edge devices
Today's technology trend indicates that billions of hand-held gadgets
may come on-line in the next several years. There were different
opinions regarding whether this would, or would not, bring a
significant impact on the global routing scalability. The current
solutions for mobile hosts, namely Mobile IP (e.g., [RFC3775]),
handle the mobility by one-level of indirection through home agents,
thus mobile hosts do not appear any different from a routing
perspective than stationary hosts. If we follow the same approach,
new mobile devices should not present challenges beyond the increase
in the size of the network.
The workshop participants recognized that the increase in the number
of mobile devices can be significant, and that the introduction of a
scalable routing system supporting generic identity-locator
separation would enable the support for these billions of mobile
gadgets without bringing undue impact on the global routing
scalability and stability.
Meyer, et al. Expires June 18, 2007 [Page 14]
Internet-Draft IAB Workshop on Routing & Addressing December 2006
Further investigation is needed to gain a complete understanding of
the implications on the global routing system of connecting many new
hand-held devices and sensor networks to the Internet.
6. What Approaches Have Been Investigated
Over the years there have been many efforts designed to investigate
scalable inter-domain routing for the Internet
[I-D.irtf-routing-history]. To benefit from the insights obtained
from these past results, the workshop reviewed several major previous
and ongoing efforts:
1. The MULTI6 working group's exploration of the solution space and
the lessons learned,
2. The solution to multihoming being developed by the SHIM6 Working
Group and its pro's and con's,
3. The GSE proposal made by O'Dell in 1997 and its pro's and con's,
and
4. Map-and-Encap [RFC1955], a general indirection-based solution to
scalable multihoming support.
6.1. Lessons from MULTI6
The MULTI6 working group was chartered to explore the solution space
for scalable support of IPv6 multihoming. The numerous proposals
collected by MULTI6 Working group generally fell into one of two
major categories: resolving the above mentioned conflict by provider-
independent address assignments, or by assigning multiple address
prefixes to multihomed sites, one for each of its providers, so that
all the addresses can be topologically aggregatable.
The first category includes proposals of (1) simply allocating
provider independent address space, which is effectively the current
practice, and (2) assigning IP addresses based on customers
geographical locations. The first approach does not scale; the
second approach represents a fundamental change to the Internet
routing system and its economic model, and imposes undue constraints
on ISPs. These proposals were found to be incomplete as they offered
no solutions to the new problems they introduced.
The majority of the proposals fell into the second category--
assigning multiple address blocks per site. Because IP addresses
have been used as identifiers by higher level protocols and
applications, these proposals face a fundamental design decision
Meyer, et al. Expires June 18, 2007 [Page 15]
Internet-Draft IAB Workshop on Routing & Addressing December 2006
regarding which layer should be responsible for mapping the locators
(i.e. the multiple addresses received from ISPs) to an identifier. A
related question involves which nodes are responsible for handling
multiple addresses. One can implement a multi-address scheme at
either each individual host or at edge routers of a site, or even
both. Handling multiple addresses by edge routers provides the
ability to control the traffic flow of the entire site. Conversely,
handling multiple addresses by individual hosts offers each host the
flexibility to choose different policies for selecting a provider; it
also implies changes to all the hosts of a multihomed site.
During the process of evaluating all the proposals, two major lessons
were learned:
o Changing anything in the current practice is hard: for example,
inserting an additional header into the protocol would impact IP
fragmentation processing, and the current congestion control
assumes that each TCP connection follows a single routing path.
In addition, operators ask for the ability to perform traffic
engineering on a per site basis, and specification of site policy
is often interdependent with the IP address structure.
o The IP address has been used as an identifier and has been
codified into many Internet applications that manipulate IP
addresses directly or include IP addresses within the application
layer data stream. Thus changing the semantics of an IP address,
for example using only the last 64-bit as identifiers as proposed
by GSE, will require changes to all such applications.
6.2. SHIM6: Pros and Cons
The SHIM6 working group took the second approach from the MULTI6
working group's investigation, i.e. supporting multihoming through
the use of multiple addresses. SHIM6 adopted a host-based approach
where the host IP stack includes a "shim" that presents a stable
"upper layer identifier" (ULID) to the upper layer protocols, but may
rewrite the IP packets sent and received so that a currently-working
IP address is used in the transmitted packets. When needed, a SHIM6
header is also included in the packet itself, to signal to the remote
stack.
With SHIM6, protocols above the IP layer use the ULID to identify
endpoints (e.g., for TCP connections). The current design suggests
choosing one of the locators as the ULID (borrowing a locator to be
used as an identifier). This approach makes the implementation
compatible with existing IPv6 upper layer protocol implementations
and applications. Many of these applications have inherited the long
time practice of using IP addresses as identifiers.
Meyer, et al. Expires June 18, 2007 [Page 16]
Internet-Draft IAB Workshop on Routing & Addressing December 2006
SHIM6 is able to isolate upper layer protocols from multiple IP layer
addresses. This enables a multihomed site to use provider-allocated
prefixes, one from each of its multiple providers, to facilitate
provider-based prefix aggregation. However this gain comes with
considerable costs. First, SHIM6 requires modifications to all host
stack implementations to support the shim processing. Second, the
shim layer must maintain the mapping between the identifier and the
multiple locators returned from IPv6 AAAA name resolution, and must
take the responsibility to try multiple locators if failures ever
occur during the end-to-end communication. At this time the host has
little information to determine the order of locators it should use
in reaching a multihomed destination, however there is ongoing effort
in addressing this issue.
As a host-based approach, SHIM6 provides little control to the
service provider for effective traffic engineering. At the same
time, it also imposes additional state information on the host
regarding the multiple locators of the remote communication end.
Such state information may not be a significant issue for individual
user hosts, but can lead to larger resource demands on large
application servers which handle hundreds of thousands simultaneous
TCP connections.
Yet another major issue with the SHIM6 solution is the need for
renumbering when a site changes providers. Although a multihomed
site is assigned multiple address blocks, none of them can be treated
as a persistent identifier for the site. When the site changes one
of its providers, it must purge the address block of that provider
from the entire site. The current practice of using the IP address
as both an identifier and a locator has been strengthened by the use
of IP addresses in access control lists present in various types of
policy-enforcement devices (e.g. firewalls). If SHIM6's ULIDs are to
be used for policy enforcement, a change of providers may necessitate
the re-configuration of many such devices.
6.3. GSE/indirection solutions: Costs and Benefits
The use of indirection for scalable multihoming was discussed at the
workshop, including the GSE [GSE] and indirection approaches in
general. The GSE proposal changes the IPv6 address structure to bear
the semantics of both an identifier and a locator. The first n bytes
of the 16-byte IPv6 address are called the Routing Goop (RG), and are
used by the routing system exclusively as a locator. The last 8
bytes of the IPv6 address specify an interface on an end-system. The
middle (16 - n - 8) bytes are used to identify site local topology.
The border routers of a site re-write the source RG of each outgoing
packet to make the source address part of the source provider's
address aggregation; they also re-write the destination RG of each
Meyer, et al. Expires June 18, 2007 [Page 17]
Internet-Draft IAB Workshop on Routing & Addressing December 2006
incoming packet to hide the site's RG from all the internal routers
and hosts.
All identifier/locator split proposals require a mapping service that
can return a set of locators corresponding to a given identifier. In
addition, these proposals must also address the problem of detecting
locator failures and redirecting data flows to remaining locators for
a multihomed site. GSE proposed to use DNS for providing the mapping
service, but it did not offer an effective means for locator failure
recovery. GSE also requires host stack modifications, as the upper
layers and applications are only allowed to use the lower 8-bytes,
rather than the entire, IPv6 address.
Finally, the extent to which GSE could be made compatible with
increasingly-popular cryptographically-generated addresses (CGA)
remains to be determined [dGSE].
6.4. Futures for Indirection
As the saying goes, "There is no problem in computer science that
cannot be solved by an extra level of indirection". The GSE proposal
can be considered a specific instantiation of a class of indirection
based solutions to scalable multihoming. A more general form of this
indirection solution, Map-and-Encap [RFC1955], uses tunneling,
instead of locator rewriting, to cross the DFZ and support provider-
based prefix aggregation. This solution avoids the provider and
customer conflicts regarding PA and PI prefixes by putting each in a
separate name space, so that ISPs can use topologically aggregatable
addresses while customers can have their globally unique and
provider-independent identifiers. Thus it supports scalable
multihoming, and requires no changes to the end systems when the
encapsulation is performed by the border routers of a site. It also
requires no changes to the current practice of both applications as
well as backbone operations.
However, all gains of an effective solution are accompanied with
certain associated costs. As stated earlier in the GSE discussion, a
mapping service must be provided. This mapping service not only
brings with it the associated complexity and cost, but it also adds
another point of failure and is a potential target for malicious
attacks. Any solution to routing scalability is necessarily a cost/
benefit trade-off. Given the high potential of its gains, this
indirection approach deserves special attention in our search for
scalable routing solutions.
Meyer, et al. Expires June 18, 2007 [Page 18]
Internet-Draft IAB Workshop on Routing & Addressing December 2006
7. Problem Statements
The fundamental goal of this workshop was to develop a prioritized
problem statement regarding the scalability problems facing us today,
and the workshop spent a considerable amount of time on reaching that
goal. This section provides a description of the prioritized problem
statement, together with elaborations on both the rationale and open
issues.
The workshop participants noted that there exist different classes of
stakeholders in the Internet community who view today's global
routing system from different angles, and assign different priorities
to different aspects of the scalability problem set. The prioritized
problem statement in this section is the consensus of the
participants in this workshop, which was comprised primarily of large
network operators (and a few vendors). It is likely that a different
group of participants would produce a different list, or with
different priorities. For example, freedom of changing providers
without renumbering might make top of the priority list assembled by
a workshop of end users and enterprise network operators.
7.1. Problem 1: Routing Scalability
The workshop participants believe that routing scalability is the
most important problem facing the Internet today and must be solved
(note that the time frame in which these problems need solutions was
not directly specified). These scalability problems include the size
of the DFZ RIB and FIB, the implications of the growth of the RIB and
FIB on routing convergence times, and the cost, power (and hence heat
dissipation) and ASIC real estate requirements of core router
hardware. Another interesting observation is that the power
requirements of an ASIC are related to the feature set implemented by
that ASIC. [Editor's note: Need citation here?]
The DFZ IPv4 RIB has been growing at what appears to be an
accelerating rate [DFZ]. If/when IPv6 becomes widely deployed, this
problem is expected to get much worse. It is commonly believed that
the limited IPv4 address space has imposed constraints on IPv4 RIB
growth. Given that the IPv6 routing architecture is the same as the
IPv4 architecture (with substantially larger address space), it is
natural to predict that routing table growth for IPv6 will only
exacerbate the situation.
The increasing deployment of VPN/VRF is considered another major
factor driving the routing system growth. However there are
different views regarding whether this factor has, or does not have,
a direct impact to the DFZ RIB. A common practice is to delegate
specific routers to handle VPN connections, thus backbone routers do
Meyer, et al. Expires June 18, 2007 [Page 19]
Internet-Draft IAB Workshop on Routing & Addressing December 2006
not necessarily hold state for individual VPNs. Nevertheless VPNs do
represent a scalability challenges in network operations.
7.2. Problem 2: The overloading of IP address semantics
As we have reported in Section 3, multihoming, along with traffic
engineering, appear to be the major driving factors driving the
growth of the DFZ RIB. As mentioned above, computing the FIB, along
with the power and real estate requirements of core router ASICs, has
become challenging. [Editors note: Need citation]
7.2.1. Definition of Locator and Identifier
[Editor's note: pending approval of the workshop participants, we may
change the "Locator" and "Identifier" to different names.]
Roughly speaking, the Internet comprises a transit backbone network
and a large number of customer networks containing hosts that are
attached to the backbone. Viewing the Internet as a graph, transit
networks have branches and customer networks with hosts hang at the
edges as leaves.
As its name suggests, locators identify locations in the topology and
a network's or host's locator is topologically constrained by its
present position. Identifiers, in principal, should be network-
topology independent. That is, even though a network or host may
need to change its locator because it becomes attached to a different
set of points in the Internet, its identifier should remain constant.
From an ISP's viewpoint, identifiers identify customer networks and
customer hosts. As an example, a non-routable, provider-independent
IP prefix for an enterprise network serves as an identifier for that
enterprise. This block of IP addresses can be used to route packets
inside the enterprise network, however they are are independent from
the DFZ topology, that is why they are not globally routable on the
Internet.
Note that in cases such as the last example, the definition of
locators and identifiers can be context-dependent. Following the
example further, a PI address may be routable in an enterprise but
not the global network. If allowed to be visible in the global
network, such addresses might act as identifiers from a backbone
operator's point of view but locators from an enterprise operator's
point of view.
Meyer, et al. Expires June 18, 2007 [Page 20]
Internet-Draft IAB Workshop on Routing & Addressing December 2006
7.2.2. Consequence of Locator and Identifier Overloading
In today's Internet architecture, IP addresses have been used as both
locators and identifiers. Combined with the use of CIDR to perform
route aggregation, a problem arises for either providers or customers
(or both).
Consider, for example, a campus network C that received prefix
x.y.z/24 from provider P1. When C multi-homes with a second provider
P2, both P1 and P2 must announce x.y.z/24 so that C can be reached
through both providers. In this example the prefix x.y.z/24 serves
both as an identifier for C, as well as a (non-aggregatable) locator
for C's two attachments to the transit system.
As far as the DFZ RIB is concerned, the above example shows that
customer multihoming blurs the distinction between PA and PI
prefixes: although C received a PA prefix x.y.z/24 from P1,
nevertheless C's multihoming forced this prefix to be announced
globally (equivalent to a PI prefix), and forced the prefix's
original owner, provider P1, to de-aggregate. As a result, today's
multihoming practice leads to a growth of the routing table size in
proportion to the number of multihomed customers. The only practical
way to scale a routing system today is topological aggregation, which
gets destroyed by customer multihoming.
Although multi-homing may blur the PA/PI distinction, there exists a
big difference between PA and PI prefixes when a customer changes its
provider(s): if the customer has used a PA prefix from a former
provider P1, the prefix is supposed to be returned to P1 upon
completion of the change. The customer is supposed to get a new
prefix from its new provider, i.e. renumbering its network. It is
necessary for providers to reclaim their PA prefixes from former
customers in order to keep the topological aggregatiblity of their
prefixes. On the other hand, renumbering is considered very painful,
if not impossible, by many Internet users, especially large
enterprise customers. It is not uncommon for IP addresses in such
enterprises to penetrate deeply into variously parts of the
networking infrastructure, ranging from applications to network
management (e.g., policy databases, firewall configurations, etc.).
This shows how fragile the system becomes due to the overloading of
IP address as both locators and identifiers; significant enterprise
operations could be disrupted due to the otherwise simple operation
of switching IP address prefix assignment.
7.2.3. Traffic Engineering and IP Address Semantics Overload
In today's practice, traffic engineering (TE) is achieved by de-
aggregating IP prefixes. One can effectively adjust the traffic
Meyer, et al. Expires June 18, 2007 [Page 21]
Internet-Draft IAB Workshop on Routing & Addressing December 2006
volume along specific routing paths by adjusting the prefix lengths
and the number of prefixes announced through those paths. Thus the
very means of TE practice directly conflicts with constraining the
routing table growth.
On the surface, traffic engineering induced prefix de-aggregation
seems orthogonal to the locator-identifier overloading problem.
However this may not necessarily be true. Had all the IP prefixes
been topologically aggregatable to start with, it would make re-
aggregation possible or easier, when the finer granularity prefix
announcements propagate further away from their origins.
7.3. Routing Convergence
There are two kinds of routing convergence issues, eBGP (global
routing) convergence and IGP (enterprise or provider) routing
convergence. Generally speaking, eBGP convergence is relatively fast
in most cases if one ignores the delay caused by the minimum route
advertisement interval (MRAI) timer [RFC4098], except those cases
when a route is withdrawn. Route withdrawals tend to suffer from
slow convergence; one participant's experience suggests that the
withdrawal delays often last a couple of minutes. One may argue
that, if the destination becomes unreachable, a long convergence
delay would not bring further damage to applications. However, there
are cases where a more specific route (a longer prefix) has failed,
yet the destination can still be reachable through an aggregated
route (a shorter prefix). In these cases the long convergence delay
does impact application performance.
The IGP convergence can also be very slow, which can lead to
intolerable performance problems for real time applications such as
VoIP. The cause for this slow convergence can be due to multiple
factors, including
1. Delays in detecting physical failures,
2. The delay in loading updated information into the FIB, and
3. The large size of the internal RIB, often twice as big as the DFZ
RIB, which can lead to both longer route computation time and the
longer FIB loading time.
The workshop participants hold different views regarding (1) the
severity of the routing convergence problem; and (2) whether it is an
architectural problem, or an implementation issue. However, people
generally agree that if we solve the routing scalability problem,
that will certainly help reduce the convergence delay or make the
problem a much easier one to handle simply by reducing the number of
Meyer, et al. Expires June 18, 2007 [Page 22]
Internet-Draft IAB Workshop on Routing & Addressing December 2006
routes to handle.
7.4. Misaligned Costs and Benefits
Today's rapid growth of the DFZ RIB is driven by several major
factors, including multihoming, traffic engineering, and organic
growth of the Internet's user base. There is a powerful incentive to
deploy each of the above features as they bring direct benefits to
the parties who make use of them. However, the beneficiaries may not
bear the direct costs of the resulting routing table size increase,
and there is no measurable or enforceable constraint to limit such
increase.
For example, suppose that a service provider bandwidth-constrained
transoceanic links and wants to splits its prefix announcements in
order to fully load each link. The origin AS benefits from
performing the de-aggregation, however if the de-aggregated
announcements propagate globally, the cost is born by all other ASes.
That is, the costs and benefits of this type of TE are not contained.
Multihoming provides a similar example (in this case, the multihomed
site achieves a benefit, but the global Internet incurs the cost of
carrying the additional prefix(es)).
The mis-alignment of cost and benefit in the current routing system
has been a driver for acceleration of the routing system size growth.
7.5. Other Issues
Mobility was among the most frequently mentioned issues at the
workshop. It is expected that billions of mobile gadgets may be
connected to the Internet in the near future. There was also a
discussion on the network connectivity for air travel, such as the
Connexion service provided by Boeing over the last few years.
However, at this time it seems unclear (1) whether the Boeing-like
network mobility support would cause a scaling issue in the routing
system (the number of aircraft in the sky is relatively small
compared to the current routing table size), and (2) exactly what
would be the impact of billions of mobile hosts on the global routing
system. These discussions were covered in Section 5 of this report.
Routing security is another issue that was brought up a number of
times during the workshop. However important routing security may
be, it seems out of scope for this workshop given the workshop's goal
was to produce a problem statement about routing scalability. It was
duly considered that security must be one of the top goals when we
get to a solution development stage. It was also noted that, if we
continue to allow the routing table to grow indefinitely, then it may
be impossible to add security enhancements in the future.
Meyer, et al. Expires June 18, 2007 [Page 23]
Internet-Draft IAB Workshop on Routing & Addressing December 2006
7.6. Problem Recognition
The first step in solving a problem is recognizing its existence.
However, recognizing the severity of the routing scaling issue can be
a challenge by itself. There does not exist a specific hard limit in
the routing system scalability that can be easily demonstrated, nor
is there any specific answer to the question of how much time we may
have in developing a solution. However, a general consensus among
the workshop participants is that we are running out of time. As
explained in Section 4, the current RIB growth trend is leading
towards cost increases at a rate greater than the nominal
depreciation cycle.
[Editor's note: There has been quite a bit of discussion about the
exact effect of Moore's law on the design and cost of high-end
routers. This topic requires more discussion.]
8. Criteria for Solution Development
Any common problem statement may admit multiple different solutions.
This section provides a set of considerations, as identified from the
workshop discussion, over the solution space. Given the
heterogeneity among customers and providers of the global Internet,
and the elasticity of the problem (as mentioned in the previous
section), none of these considerations should inherently preclude any
specific solution. Consequently, although the following
considerations were initially considered as constraints on solutions,
we have instead opted to adopt the term 'criteria' to be used in
guiding solution evaluations.
8.1. Criteria on Scalability
Clearly, any proposed solution must solve the problem at hand, and
our number one problem concerns the scalability of the Internet's
routing and addressing system(s) (as outlined in previous sections).
Under the assumption of continued increases of multihoming and RFC
2547 VPN [RFC2547] deployment, the solution must enable the routing
system to scale gracefully as measured by the number of
o DFZ Internet routes, and
o Internal routes.
In addition, scalable support for traffic engineering (TE) must be
considered as a business necessity, not an option. Capacity planning
involves placing circuits based on traffic demand over a relatively
long time scale, while TE must work more immediately to match the
Meyer, et al. Expires June 18, 2007 [Page 24]
Internet-Draft IAB Workshop on Routing & Addressing December 2006
traffic load to the existing capacity and to match the routing policy
requirements.
It was recognized that different parties in the Internet may have
different specific TE requirements. For example,
o End site TE: based on locally determined performance or cost
policies, end sites may wish to control the traffic volume exiting
to, or entering from specific providers.
o Small ISP to transit ISP TE: operators may face tight resource
utilization and wish to influence the volume of entering traffic
from both customers and providers along specific routing paths to
best utilize the limited resources
o Large ISP TE: given the densely connected nature of the Internet
topology, a given destination normally can be reached through
different routing paths. An operator may wish to be able to
adjust the traffic volume sent to each of its peers based on
business relations with its neighbor ASes.
At this time, it remains an open issue whether a scalable TE solution
would be necessarily inside the routing protocol, or can be
accomplished through means that are external to the routing system.
8.2. Criteria on Incentives and Economics
The workshop attendees concluded that one important reason for
uncontrolled routing growth was the misalignment of incentives. New
entries are added to the routing system to provide benefit to
specific parties, while the cost is born by everyone in the global
routing system. The consensus of the workshop was that any proposed
solutions should strive to provide incentives to reward practices
that reduce the overall system cost, and punish the "bad" behavior
which impose undue burden on the global system. [0]
The consensus of the workshop was that there no longer can (ever) be
a flag day on the Internet. Rather, attendees felt that to bootstrap
the deployment of the new solutions, the solutions should provide
incentives to first movers. That is, even when a single party starts
to deploy the new solution, there should be measurable benefits to
balance the costs.
Independent of what kind of solutions the IETF develops, if any,
attendees felt it was unlikely that the resulting routing system
would stay constant in size. Instead, they believed it will continue
to grow, and that ISPs will continue to go through system and
hardware upgrade cycles. Many attendees expressed a desire that the
Meyer, et al. Expires June 18, 2007 [Page 25]
Internet-Draft IAB Workshop on Routing & Addressing December 2006
scaling properties of the system can allow the hardware to keep up
with the Internet growth at rate comparable to current costs, for
example allowing one to keep a 5-year hardware depreciation cycle, as
opposed to a situation where scaling leads to accelerating cost
increases.
8.3. Criteria on Timing
Although there does not exist a specific hard deadline, the unanimous
consensus among the workshop participants is that the solution
development must start now. That is, even if we can have the
solution specification ready within a 1 - 2 year time frame, that
will be followed by another 2-year certification cycle. As a result,
even in the best case scenario, the workshop participants felt that
we are faced with a 3 - 5 year time frame in getting the solutions
deployed.
8.4. Consideration on Existing Systems
The routing scalability problem is a shared one between IPv4 and
IPv6, as IPv6 simply inherited IPv4's CIDR-style "Provider-based
Addressing." The proposed solutions should, and are also expected
to, solve the problem for both IPv4 and IPv6.
Backwards compatibility with the existing IPv4 and IPv6 protocol
stack is a necessity. Although a wide deployment of IPv6 is yet to
happen, there has been substantial investment into IPv6
implementation and deployment by various parties. IPv6 is considered
a legacy with shipped code. Thus a highly desired feature of any
proposed solution is to avoid imposing backwards incompatible changes
on end hosts (either IPv4 or IPv6).
In the routing system itself, the solutions must allow incremental
changes from the current operational Internet. The solutions should
be backward compatible with the routing protocols in use today,
including BGP, OSPF, IS-IS, and others, possibly with incremental
enhancements. The data path should support IPv4 and IPv6.
The above backward compatibility considerations should not constrain
the exploration of the solution space. We need to first find right
solutions, and look into their backward compatibility issues after
that. This way enables us to gain a full understanding of the
tradeoffs, and what potential gains, if any, that we may achieve by
relaxing the backward compatibility concerns.
As a rule of thumb for successful deployment, for any new design, its
chance of success is higher if it makes fewer changes to the existing
system.
Meyer, et al. Expires June 18, 2007 [Page 26]
Internet-Draft IAB Workshop on Routing & Addressing December 2006
8.5. Consideration on Security
Securing the routing system is not considered a requirement for the
solution development. Security is important; having a working system
in the first place is even more important.
Security should be considered from day one of solution development.
If nothing else, the solutions must not make securing the routing
system any worse than the situation today. It is highly desirable to
have a solution that makes it more difficult to inject false routing
information, and makes it easier to filter out DoS traffic.
8.6. Other Criteria
A number of other criteria were also raised which fall into various
different categories. They are summarized below.
o Site renumbering forced by the routing system should be avoided.
o Site reconfiguration driven by the routing system should be
minimized.
o The solutions should not force ISPs to reveal internal topology.
o Routing convergence delay must be under control.
o End-to-end data delivery paths should be stable enough for good
VoIP performance.
8.7. Understanding the Tradeoff
As the old saying goes, every coin has two sides. If we let the
routing table continue to grow at its present rate, rapid hardware
and software upgrade and replacement cycles for deployed core routing
equipment may become cost prohibitive. In the worst case, routing
table growth may exceed our ability to engineer the global routing
system in an effectively way. On the other hand, solutions for
stopping or substantially slowing down the growth in the Internet
routing table will necessarily bring their own costs, perhaps
elsewhere and in different forms. Examples of such tradeoffs among
approaches are presented in Section 6, where we examined the gains
and costs of a few different approaches to multihoming (SHIM6, GSE,
and a general tunneling approach). A major task in the solution
development is to understand who may have to give up what and whether
that makes a worthy tradeoff.
Before ending this discussion on the solution criteria, it is worth
mentioning the shortest presentation at the workshop, which was made
Meyer, et al. Expires June 18, 2007 [Page 27]
Internet-Draft IAB Workshop on Routing & Addressing December 2006
by Tony Li. He asked a fundamental question: what is at stake? It
is the Internet itself. If the routing system does not scale with
the continued growth of the Internet, eventually the costs might
spiral out of control, the digital divide widen, and the Internet
growth slow down, stop, or retreat. Compared to this problem, he
considered that none of the criteria mentioned so far (except solving
the problem) was important enough to block the development and
deployment of an effective solution.
9. Workshop Recommendations
The workshop attendees would like to make the following
recommendations:
First, the workshop participants noted that the concern over the
scalability of the routing and addressing system has been with us for
a very long time. The factors contributing to these concerns are
outlined in Section 3. Further, the participants expressed concern
that the current growth rate of the DFZ RIB is exceeding our ability
to engineer the routing infrastructure in an economically feasible
way.
Second, because the participants of this workshop consisted of mostly
large service providers and major router vendors, the workshop
participants recommend that IAB/IESG organize additional workshops or
use other venues of communication to reach out to other stakeholders
such as content providers, retail providers, and enterprise
operators, both to communicate to them the outcome of this workshop,
and to solicit the routing/addressing problems they are facing today,
and their requirements on the solution development.
Third, the workshop participants recommend conducting the solution
development in an open, transparent way, with broad ranging
participation from the larger networking community. A majority of
the participants indicated their willingness to commit resources
toward developing a solution. We must also invite the participation
from the research community in this process. The locator-identifier
split represents a fundamental architectural issue and IAB should
lead the investigation into understanding of both how to make this
architectural change and the overall impact of the change.
Fourth, given the goal of developing a long term solution, and the
fact that development and deployment cycles will necessarily take
some time, it may be helpful (or even necessary) to buy some time
through engineering feasible short or intermediate term solutions
(e.g., FIB compression).
Meyer, et al. Expires June 18, 2007 [Page 28]
Internet-Draft IAB Workshop on Routing & Addressing December 2006
Fifth, the workshop participants believe the next step is to develop
a roadmap from here to the solution deployment. The IAB and IESG are
expected to take on the leadership role in this roadmap development,
and to leverage on the momentum from this successful workshop to move
forward quickly. The roadmap should provide clearly defined short,
medium, and long term objectives to guide the solution development
process, so that the community as a whole can proceed in an
orchestrated way, seeing exactly where we are going when engineering
necessary short term fixes.
Finally, the workshop participants also made a number of suggestions
to IETF regarding specific steps towards a quick solution
development. These suggestions are captured in Appendix A.
10. Acknowledgments
Jari Arkko, Vince Fuller, Darrel Lewis, Tony Li, Eric Rescorla, and
Ted Seely made many insightful comments on earlier versions of this
document. Finally, many thanks to Wouter Wijngaards for the fine
notes he took during the workshop.
11. Security Considerations
While the security of the routing system is of great concern, this
document introduces no new protocol or protocol usage and as such
presents no new security issues.
12. References
[RFC1955] Hinden, R., "New Scheme for Internet Routing and
Addressing (ENCAPS) for IPNG", RFC 1955, June 1996.
[RFC2547] Rosen, E. and Y. Rekhter, "BGP/MPLS VPNs", RFC 2547,
March 1999.
[RFC3775] Johnson, D., Perkins, C., and J. Arkko, "Mobility Support
in IPv6", RFC 3775, June 2004.
[RFC4098] Berkowitz, H., Davies, E., Hares, S., Krishnaswamy, P.,
and M. Lepp, "Terminology for Benchmarking BGP Device
Convergence in the Control Plane", RFC 4098, June 2005.
[RFC4116] Abley, J., Lindqvist, K., Davies, E., Black, B., and V.
Gill, "IPv4 Multihoming Practices and Limitations",
RFC 4116, July 2005.
Meyer, et al. Expires June 18, 2007 [Page 29]
Internet-Draft IAB Workshop on Routing & Addressing December 2006
[RFC4192] Baker, F., Lear, E., and R. Droms, "Procedures for
Renumbering an IPv6 Network without a Flag Day", RFC 4192,
September 2005.
[RFC4632] Fuller, V. and T. Li, "Classless Inter-domain Routing
(CIDR): The Internet Address Assignment and Aggregation
Plan", BCP 122, RFC 4632, August 2006.
[I-D.irtf-routing-history]
Doria, A. and E. Davies, "Analysis of IDR requirements and
History Group B contribution",
draft-irtf-routing-history-00 (work in progress),
February 2002.
[ARIN] "American Registry for Internet Numbers",
http://www.arin.net/index.shtml.
[ROFL] "ROFL: Routing on Flat Labels", SIGCOMM 2006, http://
sigcomm06.stanford.edu/discussion-beta/
getpaper.php?paper_id=34&
PHPSESSID=10ece185c9ee5f7e136921fc743b2401, 2006.
[CNIR] "Compact Name-Independent Routing with Minimum Stretch",
ACM Symposium on Parallel Algorithms and
Architectures, http://citeseer.ist.psu.edu/710757.html,
2004.
[GSE] "GSE - An Alternate Addressing Architecture for IPv6",
Internet Draft, http://www.watersprings.org/pub/id/
draft-ietf-ipngwg-gseaddr-00.txt, 1997.
[dGSE] "An Overview of Multihoming and Open Issues in GSE",
http://www.isoc.org/tools/blogs/ietfjournal/
?p=98#more-98, 2006.
[PIPA] "IPv4 Address Allocation and Assignment Policies for the
RIPE NCC Service Region",
RIPE-387 http://www.ripe.net/docs/ipv4-policies.html,
2006.
[SHIM6] "Site Multihoming by IPv6 Intermediation (shim6)",
http://www.ietf.org/html.charters/shim6-charter.html,
2006.
[DFZ] "Growth of the BGP Table - 1994 to Present", Huston,
G., http://bgp.potaroo.net, 2006.
[GIH] "Wither Routing?", Huston,
Meyer, et al. Expires June 18, 2007 [Page 30]
Internet-Draft IAB Workshop on Routing & Addressing December 2006
G., http://www.potaroo.net/ispcol/2006-11/raw.html, 2006.
[ATNAC2006]
"Projecting Future IPv4 Router Requirements from Trends in
Dynamic BGP Behaviour", Huston, G., http://
www.potaroo.net/papers/phd/atnac-2006/bgp-atnac2006.pdf,
2006.
[CIDRRPT] "The CIDR Report", http://www.cidr-report.org, 2006.
[BGP2005] "2005 -- A BGP Year in Review", Huston,
G., http://potaroo.net/presentations/index.html, 2005.
[ML] "Moore's Law",
Wikipedia http://en.wikipedia.org/wiki/Moore's_law, 2006.
[RADIX] "Radix Tree",
Wikipedia http://en.wikipedia.org/wiki/Patricia_trie,
2006.
[EID] "Endpoints and Endpoint Names: A Proposed Enhancement to
the Internet Architecture", Chiappa,
N. http://www.chiappa.net/~jnc/tech/endpoints.txt, 1999.
Appendix A. Suggestions for Specific Steps
At the end of the workshop there was a lively round-table discussion
regarding specific steps that IETF may consider undertaking towards a
quick solution development, as well as potential issues to avoid.
Those steps included:
o Finding a home (mailing list) to continue the discussion started
from the workshop with wider participation. [Editor's note: Done
-- This action has been completed. The list is ram@iab.org.]
o Considering a special process to expedite solution development,
avoiding the lengthy protocol standardization cycles. For example
IESG may charter special design teams for the solution
investigation.
o If a working group is to be formed, care must be taken to ensure
that the scope of the charter is narrow and specific enough to
allow quick progress, and that the WG chair be forceful enough to
keep the WG activity focused. There was also a discussion on
which area this new WG should belong to; both routing area ADs and
Internet area AD are willing to host it.
Meyer, et al. Expires June 18, 2007 [Page 31]
Internet-Draft IAB Workshop on Routing & Addressing December 2006
o It is desirable that the solutions be developed in open
environment and free from any Intellectual property right claims.
Finally, given the perceived severity of the problem at hand, the
workshop participants trust that IAB/IESG/IETF will take prompt
actions. However if that were not to happen, operators and vendors
would be most likely to act on their own and get a solution deployed.
Appendix B. Workshop Participants
Loa Anderson (IAB)
Jari Arkko (IESG)
Ron Bonica
Ross Callon (IESG)
Brian Carpenter (IESG Chair)
David Conrad (IANA)
Leslie Daigle (IAB Chair)
Elwyn Davies (IAB)
Terry Davis
Weisi Dong
Kevin Fall (IAB)
Aaron Falk (IRTF Chair)
Dino Farinacci
Vince Fuller
Vijay Gill
Russ Housely (IESG)
Geoff Huston
Daniel Karrenberg
Dorian Kim
Olaf Kolkman (IAB)
Darrel Lewis
Kurtis Lindqvist (IAB)
Tony Li
Peter Lothberg
David Meyer (IAB)
Christopher Morrow
Dave Oran (IAB)
Phil Roberts (IAB Executive Director)
Jason Schiller
Peter Schoenmaker
Ted Seely
Mark Townsley (IESG)
Iljitsch van Beijnum
Ruediger Volk
Magnus Westerlund (IESG)
Lixia Zhang (IAB)
Meyer, et al. Expires June 18, 2007 [Page 32]
Internet-Draft IAB Workshop on Routing & Addressing December 2006
Appendix C. Workshop Agenda
IAB Routing and Addressing Workshop Agenda
October 18-19
Amsterdam, Netherlands
DAY 1: the proposed goal is to collect, as complete as possible, a
set of scalability problems in the routing and addressing area facing
the Internet today.
0815-0900: Welcome, framing up for the 2 days
Moderator: Leslie Daigle
0900-1200: Morning session
Moderator: Elwyn Davies
Strawman topics for the morning session:
- Scalability
- Multihoming support
- Traffic Engineering
- Routing Table Size: Rate of growth, Dynamics
(this is not limited to DFZ, include iBGP)
- Causes of the growth
- Pains from the growth
(perhaps "Impact on routers" can come here?)
- How big a problem is BGP slow convergence?
1015-1030: Coffee Break
1200-1300: Lunch
1330-1730: Afternoon session: What are the top 3 routing problems
in your network?
Moderator: Kurt Erik Lindqvist
1500-1530: Coffee Break
Dinner at Indrapura (http://www.indrapura.nl), sponsored by Cisco
---------
DAY 2: The proposed goal is to formulate a problem statement
0800-0830: Welcome
0830-1000: Morning session: What's on the table
Moderator: TBD
- shim6
- GSE
Meyer, et al. Expires June 18, 2007 [Page 33]
Internet-Draft IAB Workshop on Routing & Addressing December 2006
1000-1030: Coffee Break
1030-1200: Problem Statement session #1: document the problems
Moderator: David Meyer
1200-1300: Lunch
1300-1500: Problem Statement session # 2, cont;
Moderator: TBD
- Constraints on solutions
1500-1530: Coffee Break
1530-1730: Summary and Wrap-up
Moderator: Leslie Daigle
Appendix D. Presentations
The presentations from the workshop can be found on
http://www.iab.org/about/workshops/routingandaddressing
Authors' Addresses
David Meyer (editor)
Email: dmm@1-4-5.net
Lixia Zhang (editor)
Email: lixia@cs.ucla.edu
Kevin Fall (editor)
Email: kfall@intel.com
Meyer, et al. Expires June 18, 2007 [Page 34]
Internet-Draft IAB Workshop on Routing & Addressing December 2006
Full Copyright Statement
Copyright (C) The Internet Society (2006).
This document is subject to the rights, licenses and restrictions
contained in BCP 78, and except as set forth therein, the authors
retain all their rights.
This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Intellectual Property
The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights
might or might not be available; nor does it represent that it has
made any independent effort to identify any such rights. Information
on the procedures with respect to rights in RFC documents can be
found in BCP 78 and BCP 79.
Copies of IPR disclosures made to the IETF Secretariat and any
assurances of licenses to be made available, or the result of an
attempt made to obtain a general license or permission for the use of
such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository at
http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at
ietf-ipr@ietf.org.
Acknowledgment
Funding for the RFC Editor function is provided by the IETF
Administrative Support Activity (IASA).
Meyer, et al. Expires June 18, 2007 [Page 35]
