Subject: [RAM] moving a discussion from various I* lists to [email-masked]

From: David Meyer <[email-masked]>
Date: Wed, 20 Dec 2006 09:00:24 -0800

The context here was that Leslie and I (and others) were
	discussing the implications of the fact that vendors are
	telling us that hardware that can hold RIB/FIBs of sizes
	like 1 x 10^6 entries can be built today, and of sizes
	like 1 x 10^7 in the 3-5 year time frame (I think the
	term used was "not scared of 10M entry RIBs" or something
	like that). We're hearing these kinds of numbers from
	most vendors now.

	So I did a calculation based on Geoff's projections (see
	reference below) in an effort to understand what the "not
	scared" numbers would mean for RIB/FIB headroom over the
	next several years. This is what I came up with: 

	Let the "not scared" 3-5 year {R,F}IB size is 1 x 10^7 
	RIB and/or FIB entries. In that case, we have a factor of
	40x headroom in the next 3-5 years at constant RIB
	size. That is, 

	 "the not scared" {R,F}IB size/sizeof(todays DFZ RIB)
	 ~ 1 X 10^7/2.5 x 10^5
	 ~ 40

	(and yeah, the DFZ RIB is more like 200K, but this is
	back of the envelope stuff in any event).

	So do we expect more than 40x growth in the appearance (in
	the DFZ RIB) of prefixes designed to enable multihoming
	(and/or TE) say, in the next 5 years? Geoff predicts
	(again, ATNAC reference, see below) the growth from 2008
	to 2010 to be something like 3.75 x 10^5, so with that
	number (same calculation), you get something like:

	 1 x 10^7/3.75 x 10^5 ~ 27

	So again that would appear that 27x is quite a bit of
	headroom (or maybe not), or so it would seem.

	Of course, this "no problem at 1 x 10^7 RIB/FIB entries"
	analysis is vastly simplified, since it doesn't consider
	many important factors, including:

        - All components of capital cost, including power, all
	  varieties of real estate (ASIC, pin-out, LC, PoP, ...),
	  etc,

	- The need for multiple copies of the RIB, VPN routes,
	  more specifics, other special purpose routes, 

	- The advent of wildcards such as the widespread
	  deployment of IPv6, mobility and its interaction with
	  the routing system, etc.

	- It also assumes that the trends that Geoff identified
	  don't qualitatively change.

	I'll just note here that while RIB/FIB sizes are issues
	to be concerned about, I am equally concerned (or perhaps
	more concerned) about the trend toward carrying
	increasingly fine-grained information in the routing
	system (Geoff has a bit to say about this as well in
	reference cited below). This is because carrying this
	kind of information in the routing system exposes the
	core to dynamics that might not be too attractive. That
	is, the network's dynamics are closely related to how big
	RIBs and FIBs are. BTW, why exactly would you need a RIB
	of size 10^7?

	So the concern is that the RIB/FIBs are growing, addition
	to some organic growth, precisely because we're carrying
	increasingly fine grained information in the routing
	system. This in turn exposes the core of the network to
	"edge burstiness UPDATE stream",  and we have a very poor
	handle on the exact nature of that burstiness. The point
	is that this is a function, at least in part, of our
	protocol design and has deep implications for processing
	resources.  

	In any event, all of that prompted Leslie to ask a few
	questions. The following is my response to Leslie's
	questions. I'd be interested in others reflections on all
	of this.
		 
> >>Thanks -- that helps me understand your point to be that
> >>the easiest thing to measure (DFZ FIB/RIB projections and
> >>ability to accommodate that growth in hardware) 
> >
> >
> >	Well, we definitely can look at what's out there now (and
> >	over the past 8-10 years), and try to see the trends. We
> >	also are hearing that building RIB/FIBs that are sized on
> >	the order 10M entries is also not an issue. So yes, that
> >	seems accurate. 
> >
> >
> >>is not the measure of the ultimate issues:
> >>
> >>	. still don't know if such hardware is deployable
> >>	  [doesn't strike me as an IETF-able problem]
> >
> >
> >	Me either.
> >
> >
> >>	. haven't begun to discuss the impact(s) of the
> >>	  forces driving the FIB/RIB growth (progressively
> >>	  finer-grained information held in the DFZ; impact
> >>	  on computation requirements & convergence times)
> >>	  [do strike me as IETF-able problems]
> >
> >
> >	Yes, and these do seem like protocol issues (combined
> >	with RIR policy, but to some extent, those policies are
> >	driven by what protocols we've built/deployed).
> >
> >
> >>	. apart from what's up in the core, there are other
> >>	  things desired in the routing system, maybe.
> >>	  [does strike me as an IETF-able problem]
> >
> >
> >	Yes. 
> >
> >
> >>And there are no particular studies to measure the above.
> >
> >
> >	Regarding the second point, my sense is that while Geoff
> >	and some others have good work on what is happening *now*
> >	with RIB and UPDATE growth, we don't know too much about
> >	the dynamic nature of UPDATEs. BTW, if folks know about
> >	other work on this topic, I'd appreciate a pointer (or
> >	pointers) to that work. 
> >
> >	thnx,
> >
> >	--dmm
> >

----- End forwarded message -----

<reference anchor="ATNAC2006"
  <front>
    <title Projecting Future IPv4 Router Requirements from
           Trends in Dynamic BGP Behaviour
    </title>
    <author>
       Huston, G. and G. Armitage
    </author>
    <date year=3D"2006"/>
  </front>
 <seriesInfo name="Huston, G.,"
   value="http://www.potaroo.net/papers/phd/atnac-2006/bgp-atnac2006.pdf"/>
</reference>
_______________________________________________
RAM mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ram

---

From: David Meyer <[email-masked]>
Date: Wed, 20 Dec 2006 15:22:01 -0800

Tony,

> If the sole point is to build a large RIB, I can get you one that's  
> extremely large for very, very cheap.  It'll hold about 10^11 entries  
> and it'll cost you about USD $1000.
> 
> It's called a 'disk'.  ;-)

	:-)

> More seriously, the point is that performance and cost play a  
> significant role, and if you do not take those into consideration,  
> then you'll be missing a significant fraction of the problem.  

	Yes, that was (in part) of the point of my note. 

> Please  recall that BGP convergence time, for example, is
> bounded by DRAM access times and that order of magnitude
> improvements in size do not help at all in convergence.  

	Yep.

> An Internet that does not converge does not do anyone any good.

	No, it isn't.

> I think that whether or not the promised technology is deployable is  
> VERY much an IETF problem.  The E is for engineering after all.

	No disagreement at all. These numbers were flying around
	on various I* lists and I wanted to do some trivial math
	to see what they implied, hence my message. We're not
	disagreeing. 

	--dmm

---

From: Tony Li <[email-masked]>
Date: Wed, 20 Dec 2006 15:14:48 -0800

Dave,

More seriously, the point is that performance and cost play a  
significant role, and if you do not take those into consideration,  
then you'll be missing a significant fraction of the problem.  Please  
recall that BGP convergence time, for example, is bounded by DRAM  
access times and that order of magnitude improvements in size do not  
help at all in convergence.  An Internet that does not converge does  
not do anyone any good.

Tony

---

From: David Meyer <[email-masked]>
Date: Wed, 20 Dec 2006 15:22:01 -0800

Tony,

	:-)

	Yep.

	No, it isn't.

	--dmm

---

From: Tony Li <[email-masked]>
Date: Wed, 20 Dec 2006 15:14:48 -0800

Dave,

Tony

---

From: Leslie Daigle <[email-masked]>
Date: Wed, 20 Dec 2006 18:31:24 -0500

Since the "deployable" comment was mine, let me defend it -- it
doesn't have enough context in the bit Dave forwarded.

The specific issue of deployability was whether or not core
network providers would be willing/able to pay for the hardware
vendors can build to accommodate the large sizes (with suitable
speed for convergence, etc). So, it was primarily referring
to economic/business questions of deployability, not E questions.

Leslie.

Tony Li wrote:
> significant role, and if you do not take those into consideration, then 
> you'll be missing a significant fraction of the problem.  Please recall 
> that BGP convergence time, for example, is bounded by DRAM access times 
> and that order of magnitude improvements in size do not help at all in 
> convergence.  An Internet that does not converge does not do anyone any 
> good.
>

---

From: "Chris L. Morrow" <[email-masked]>
Date: Thu, 21 Dec 2006 02:08:27 +0000 (GMT)

> help at all in convergence.  An Internet that does not converge does

this seems to be a very real fear, please don't lose track of the fact
that size of RIB/FIB is not the only problem, updates from RIB -> FIB are
also a problem...

> > 	like that). We're hearing these kinds of numbers from

As a customer of some of the vendors I'd ask: "why do I not have that
today? Why does it appear in testing that the 'latest' devices off the
assembly line tip over dramatically at  500k or so routes?" Even setting
this asside vendor engineers have said point-blank to our eng folks that
there are serious problems scaling the current systems (hardware) and
maintaining the current restrictions on convergence speed.

I don't think that modeling the update rate increase/change over time has
happened yet, and I don't think that modeling that against hardware
capabilties has really happened either. So, I don't think that vendor
folks are really in a position to express 'non-fear' about 10M routes in
the table (and the associated churn rates that would come along with that
increase).

-Chris

---

From: vijay gill <[email-masked]>
Date: Wed, 20 Dec 2006 21:45:35 -0800

> 	like that). We're hearing these kinds of numbers from

Of course the vendors can build it, after all, it just results in 
another upgrade cycle analogous to the gsr/jnx core upgrades in the late 
90s timeframe. The question is who all can afford to pay for these? We 
from the operational side are getting strong pushback to amortize 
routers over longer and longer periods from the finance folks.

To be economically viable, we have to upgrade on a scale that lags the 
vendor sales cycle.

/vijay

> ------------------------------------------------------------------------
>

---

From: Jari Arkko <[email-masked]>
Date: Thu, 21 Dec 2006 12:49:02 +0200

Dave,

Thanks for posting this. I would like to see
more work in understanding both the
growth that we are seeing, as well as
the predicted capabilities of routers.
With that in mind, I'm commenting some
of the items that you mentioned you
> 	  deployment of IPv6, mobility and its interaction with
I would like to see better models than we have seen
so far about these parts. Anyone interested on working
on this? I started working on some back-of-the-envelope
calculations. The results are not so interesting at this
stage, but I would be interested in talking about the
the assumptions that would be needed for a model.
For instance, my simple model used these assumptions:

- IPv6 not turned on a single day, but rather grows gradually

- Number of IPv6 prefixes will be smaller than in IPv4, for the
  same number of users, because of more flexible addressing
  architecture.

- IPv4 keeps on growing until a certain day at which point
  all the growth is in IPv6 (even if we run out of Ipv4 addresses,
  we can split the current prefixes in smaller units... so the
  day is far in the future)

- No upper bound on IPv6 growth

- Internal/vpn/external RIBs all have to be in the same device
  (this may not be such a great assumption)

- Mobility is not a significant source of this problem *

But all of this could probably improved, and if I recall
correctly the workshop and plenary assumptions were
even simpler, such as turning on IPv6 immediately.

Thoughts?

Jari

*) None of the large mobile network deployments that
I see are based on reliance on the routing infrastructure
for mobility purposes. There's a scale impact in adding
a few billion new nodes, but I'm not sure this is qualitatively
different from, say, DSL deployment. We also have
Connexion-like designs that DO show up in the routing
system. For that we need to find a solution, as everyone
agrees that taken to a global extreme with a large number
of vehicles this would be a problem. But this is network
mobility, not the same thing as the large cellular network
deployments, for instance. Also, we intend to re-charter
the NEMO working group in the Internet area to look
first into the requirements around this problem and then
later also solutions. So I am relatively confident that
we can do something about it.

---

From: David Meyer <[email-masked]>
Date: Thu, 21 Dec 2006 06:54:32 -0800

> that size of RIB/FIB is not the only problem, updates from RIB -> FIB are

	Yep. BTW, I've been told (I don't have examples) that
	there are architectures in which the RIB->FIB update rate,
	while a factor in convergence times, isn't the dominate
	factor. 

> capabilties has really happened either.

	I've been surveying the research on "BGP UPDATE
	characterization" and haven't found a whole lot of work
	in this area. So our understanding of these dynamics is
	at best weak (my characterization). I'm speculating that
	this is in part because folks have been focused on
	properties of the Internet's AS graph, and the size of
	the DFZ RIB (so far). 

	That being said, IMO the time to study the dynamics of
	BGP UPDATEs seems to have come. We really need a better
	(both qualitative and quantitative) understanding of this.

> So, I don't think that vendor folks are really in a position to
> express 'non-fear' about 10M routes in the table (and the
> associated churn rates that would come along with that increase).

	Don't shoot the messenger? :-)

	--dmm

---

From: Jari Arkko <[email-masked]>
Date: Thu, 21 Dec 2006 17:25:19 +0200

Vijay,
> another upgrade cycle analogous to the gsr/jnx core upgrades in the
> late 90s timeframe. The question is who all can afford to pay for
> these? We from the operational side are getting strong pushback to
> amortize routers over longer and longer periods from the finance folks.
>

Right. One of the basic problems is that everything comes
out of the same silicon & finance budget. For instance,
we need to simultaneously handle line rate growth, new
functions, routing, etc. If you spend everything your
silicon engineers can create on new features, line rate
and routing have no room to increase.

The other side of the same issue is that there may
be other reasons why you must go into an upgrade
cycle, such as line rate increases. Are you saying
that the routing part is what is currently driving
the upgrade cycle, or in danger of becoming the
driver? Or are you saying that finances are pushing
the upgrade cycles to be longer, and the first thing
we will hit is the routing capability?

In any case, I think we all would like to get routing
to scale better. Why this discussion is still important
is attempting to determine where the worst pain
is (e.g., size vs. updates) as that will help us think
what to look for in solutions. Also, the seriousness
of the problem determines how much pain the Internet
community is willing to take in terms the side
effects of a solution. E.g., its typically very easy
to create something that runs between consenting
adults, but it would be harder to create something
that removes pain from one point but also adds
some pain in another point (such as the DNS or
the host).

--Jari

---

From: David Meyer <[email-masked]>
Date: Thu, 21 Dec 2006 07:46:51 -0800

Jari,

> Thanks for posting this. I would like to see

	My pleasure (I think :-).

> on this?

	Obviously I am :)

> I started working on some back-of-the-envelope

	Not turned on a single day would seem a reasonable
	assumption (clearly). However, "grows gradually" is an
	interesting assumption. I could see this go either
	way. If all of a sudden every mobile handset has IPv6 and
	HIP burned into it, is that "gradual"? What about
	Microsoft's bet with Vista?
>   same number of users, because of more flexible addressing

	I don't think you can support that. In fact, recent RIR
	policy argues against this assertion.

>   day is far in the future)

	I agree that the growth in IPv4 RIBs is bounded by some
	O(m*2^32), <m> a description of the meshiness of the
	Internet, and IPv4 FIBs are bounded by something like
	O(2^32). The corresponding update streams have no such
	bounds. So in that sense, if we got to /32 everything in
	v4, it would stop growing. 

	Regarding all the growth being in IPv6, that is a loaded
	assumption. What happenes if there is *no* v6 deployment,
	but rather we see an (further) explosion of NAT (or
	similar technology)?

	All that being said, the assumption is ok for purposes of
	modeling.

> - No upper bound on IPv6 growth

	Meaning? No upper bound on the growth of the RIB? Well,
	that would seem to be O(m*2^128).

>   (this may not be such a great assumption)

	Not sure about this one.

> - Mobility is not a significant source of this problem *

	Huh? Its one of the 3Ms (Multihoming, Mobility, and
	Migration (to v6)). Regarding the note below (*), we do
	need to understand how these technogies (i.e., HIP,
	SHIM6, etc) interact with the routing system.

> even simpler, such as turning on IPv6 immediately.

	How would you suggest moving forward with the modeling
	exercise?

	--dmm

---

From: Jari Arkko <[email-masked]>
Date: Thu, 21 Dec 2006 19:15:24 +0200

It seems that my plan of posting bad assumptions
in an effort to get you figure out the right ones
worked... ;-)

> 	Microsoft's bet with Vista?
Right. Its hard to estimate this, of course. But there
are a number of factors to consider. For instance, as
long as the hosts aren't getting native IPv6 from their
ISP, I'm not sure the global routing table is affected
by hosts that have IPv6 but don't use it or use it via
a tunnel.

In any case, even a new mobile network or a popular
OS version takes some time to actually be deployed
and used. What I did in my model was to set a fairly
aggressive IPv6 growth, in my case assuming 10%
of the network would turn to IPv6 each year, i.e.,
take 10 years for full IPv6 deployment. We could
talk about whether this covers the sudden events.
But is certainly much more aggressive than we are
seeing today.
> 	policy argues against this assertion.
Ok. Can you point to the policy that you were thinking of?
> 	v4, it would stop growing. 
Right.
> 	but rather we see an (further) explosion of NAT (or
Indeed, that's also a possible future. I guess we want to
see the worst scenario (within reasonable bounds)
from the point of view of routing. To me that's the ability
for people to get as much address space as they like.
If it turns that we continue on the NAT path... I guess
we would see somewhat less entries in the table. There
would still be growth in the table, as the IPv4 space
gets broken in smaller pieces. I don't have a good idea
how to model this, do you? Or perhaps we don't need to.
> 	that would seem to be O(m*2^128).
Right. Of course from our router construction point of
view the crucial question is whether _speed_ of the
allocation exceeds the speed of hardware improvement
and whether the improvement stops at some future
time. (Such as running out of steam on Moore's Law, as
has been often predicted.)
> 	Migration (to v6)).
I think we can account for multihoming and provider independence based
on the projected growth in the prefixes. The open question is whether
the currently seen growth will change somehow, e.g., because more
people will suddenly need provider independence. What's our best
estimate for this now?

Migration to Ipv6 is handled as long as we count
both Ipv4 and Ipv6 routes for the same users.

But what I was saying was that I do not see any evidence of
mobility suddenly changing the allocation or update rates,
except for the network mobility part. But as I explained
that it at least for now a very small part of the entire mobile
market, and we might be able to find solutions for that.
>  Regarding the note below (*), we do
The mobility mechanisms for current and all planned mobile
networks that I know of do not interact with the routing
system. They use mechanisms that hide the mobility
either from the Internet or even the host itself.
> 	How would you suggest moving forward with the modeling
Talking some more about the assumptions and growth
predictions on this list would be useful. At some point
the discussion needs to be turned into papers that
have the full picture and which can be reviewed by others
in the IETF and outside. And of course, if you can point
us to existing work that would be great too.

--Jari

---

From: David Meyer <[email-masked]>
Date: Thu, 21 Dec 2006 09:54:24 -0800

:-)

> by hosts that have IPv6 but don't use it or use it via

	So this is the "IPv6 deployment stalls" argument?  

> But is certainly much more aggressive than we are

	Ok, its certainly worth looking at. 

> Ok. Can you point to the policy that you were thinking of?

	http://www.arin.net/policy/proposals/2005_1.html

	(for example)

> > 	v4, it would stop growing. 

	mod whatever dm/dt turns out to be, where dm/dt is (my
	notation for) the rate of change of the interconnection
	meshiness.  

> how to model this, do you? Or perhaps we don't need to.

	I'm not sure we need to either.

> people will suddenly need provider independence. What's our best

	Perhaphs Geoff's current work (the ATNAC2006 paper I've
	been citing)?

	Another issue (re: mobility) is the effect the larger
	effect of the impact of say, HIP, on the routing system.

> both Ipv4 and Ipv6 routes for the same users.

	Can you say a few more words about this? I'm not sure
	what you meant.

> market, and we might be able to find solutions for that.

	Sure.

> system. 

	Right, which many folks think is a problem. So there will
	likely be some pressure to have the routing system become
	more "aware" of all of this. That is where the concern
	is, and where some good thinking will be required.

> They use mechanisms that hide the mobility

	Sure, see my previous comment.

> us to existing work that would be great too.

	Sure. Have you read Geoff's stuff yet?

	--dmm

---

From: "Chris L. Morrow" <[email-masked]>
Date: Thu, 21 Dec 2006 18:12:03 +0000 (GMT)

> either from the Internet or even the host itself.

it'd sure be nice to fix that wouldn't it? remove some of the complexity,
let the host just migrate gracefully from attachment point to attachment
point...

---

From: Per Heldal <[email-masked]>
Date: Thu, 21 Dec 2006 20:26:16 +0100

David Meyer wrote:
[snip]
> 	http://www.arin.net/policy/proposals/2005_1.html

PI (because of a lack of via alternative for multihoming) with a policy
equal to that of IPv4 only makes the number of potential visible
entities (AS:es in current technology) on the net the same for IPv6. I
believe the reduction Jari referred to was the fact that most
organizations should manage with only one (or very few) V6 assignments
as opposed to an average of more than 8 IPv4 prefixes per AS today
(http://ispcolumn.isoc.org/2006-06/bgpupds.html)

//per

---

From: Jari Arkko <[email-masked]>
Date: Thu, 21 Dec 2006 21:59:14 +0200

Chris,
> let the host just migrate gracefully from attachment point to attachment
I was talking about predictions for the future, based
on what we know about technology today, growth
patterns, etc. The fact is that none of that is done
today or planned to be done in a way that
impacts global routing table. Not even in solutions
that run on top of IP and can migrate from
attachment point to attachment point.

Don't get me wrong. I'm all for having a clean,
generic and simple solution that handles many
of the things that we currently handle with point
solutions or even outside IP stack. And has
direct IP connectivity as opposed to tunnels.
I have worked on that and people in my lab are
working on it as we speak.

But I see this more of an opportunity, as in,
say, id-loc split possibly streamlining the existing
protocols and packet flows. Better architecture.
We just can not claim that the global routing
table is going to see a big effect from the
movement of mobile nodes.

> yup, this gets back to the possible solution (which for now I think we
> can't really talk about until we know there is a problem, or have written
> down that there is a problem and everyone or 'most everyone' agrees to
> that problem.)
I believe the plain is to pursue a number of things in
parallel, including working on the problem definition and
a set of different solutions. Solution discussion is
well within scope.

--Jari

---

From: Tony Li <[email-masked]>
Date: Thu, 21 Dec 2006 12:29:10 -0800

> (http://ispcolumn.isoc.org/2006-06/bgpupds.html)

My impression was that those 8 prefixes per AS included traffic  
engineering prefixes.

I haven't heard anything about IPv6 decreasing or changing the  
pressure for traffic engineering in any way, shape or form.

Tony

---

From: David Meyer <[email-masked]>
Date: Thu, 21 Dec 2006 13:48:04 -0800

Me either.

	--dmm

---

From: Scott Leibrand <[email-masked]>
Date: Thu, 21 Dec 2006 17:49:09 -0500 (EST)

On 12/21/06 at 12:29pm -0800, Tony Li <[email-masked]> wrote:

> > PI (because of a lack of via alternative for multihoming) with a
> > policy equal to that of IPv4 only makes the number of potential
> > visible entities (AS:es in current technology) on the net the same for
> > IPv6. I believe the reduction Jari referred to was the fact that most

Someone else has presented the actual numbers, but IIRC the number of TE
prefixes is less than the number of prefixes announced due to disjoint
allocations.

-Scott

---

From: Per Heldal <[email-masked]>
Date: Thu, 21 Dec 2006 23:50:52 +0100

> My impression was that those 8 prefixes per AS included traffic

True. 8 is excessive.

Yet, according to the most recent CIDR-report:

23906 - Number of ASes in routing system
132190 - CIDR aggregated prefixes

~ 5.5 pfx/as

> 
> I haven't heard anything about IPv6 decreasing or changing the pressure
> for traffic engineering in any way, shape or form.

Certainly not. Requirements for traffic engineering remains one of the
main arguments in parts of the ops community against architectural
changes which involve certain forms of aggregation. (fear loss of control).

//per