Subject: Re: a response to "A Simple Solution for IPv6 Multihoming"

From: "Steven M. Bellovin" <[email-masked]>
Date: Fri, 17 Sep 1999 20:39:10 -0400

In message <[email-masked]>
, Vijay Gill writes:

> 
> Given a linear (albeit steeper) curve, Moore's law still outstrips prefix
> growth.

Why do you assume that routing table calculation is linear?  I'm fairly 
certain it isn't.

		--Steve Bellovin

--------------------------------------------------------------------
IETF IPng Working Group Mailing List
IPng Home Page:                      http://playground.sun.com/ipng
FTP archive:                      ftp://playground.sun.com/pub/ipng
Direct all administrative requests to [email-masked]
--------------------------------------------------------------------

---

From: Vijay Gill <[email-masked]>
Date: Fri, 17 Sep 1999 22:17:20 -0400 (EDT)

On Fri, 17 Sep 1999, Steven M. Bellovin wrote:

> In message
> <[email-masked]> ,
> Vijay Gill writes: 
> 
> > 

The total time taken before a router has converged and has started
forwarding packets can be broken down into the following time steps

1 - compute the routing table
2 - populate forwarding tables
3 - update neighbors

For this discussion, we are concerned with item #1.

It is trivially obvious that (1) is a function (f) of number of prefixes
(P). 

The O(f(P)) being the running time of BGP for purposes of this discussion
is fairly non trivial to calculate, and is probably implementation
dependent as well, but a BOE using an SPF calculation as a check, gives me
a result that O(f(P)) is very likely a polynomial (N^2) and less than
exponential.

Now, oddly enough, I also happen to have some emperical data points from a
study to determine routing scaling for a promising local ISP, and the
curve fitting to the dataset results in a polynomial in ^2.  

These data were collected from instrumenting two fairly well known
implementations and were measured using prefix injection mechanisms that
generated NLRI and associated attributes that were consistent with the
internal IBGP table data for an ISP. 

This gives a result that given linear growth, and exponential Moore's law,
we might be safe for a while.

/vijay

---

From: Brian E Carpenter <[email-masked]>
Date: Mon, 20 Sep 1999 10:46:58 -0500

Vijay Gill wrote:
...
> we might be safe for a while.

But the only reason we currently have linear growth in the BGP tables
is because of CIDR. 

In any case, "safe for a while" is not very reassuring for the
long term.

  Brian