Subject: [RRG] Routers in DFZ

From: Peter Sherbin <[email-masked]>
Date: Thu, 2 Aug 2007 11:40:46 -0700 (PDT)

Folks,

How many routers are in DFZ? Is there a ratio that ties the number prefixes in RIB
to the number of DFZ routers? to the total number of routers on the Internet?

Thank you,

Peter

      ____________________________________________________________________________________
Luggage? GPS? Comic books? 
Check out fitting gifts for grads at Yahoo! Search
http://search.yahoo.com/search?fr=oni_on_mail&p=graduation+gifts&cs=bz

--
to unsubscribe send a message to [email-masked] with the
word 'unsubscribe' in a single line as the message text body.
archive: <http://psg.com/lists/rrg/> & ftp://psg.com/pub/lists/rrg

---

From: "Ricardo V. Oliveira" <[email-masked]>
Date: Thu, 2 Aug 2007 15:02:06 -0400

I don't think you can get such number. You can however get a counting  
on the number of autonomous systems. But the level of abstraction  
depends on your final goal.

--Ricardo

---

From: Peter Sherbin <[email-masked]>
Date: Thu, 2 Aug 2007 12:19:08 -0700 (PDT)

The current ratio is about 8.9 routes per AS. Will it hold if the number of AS
increases four times to 100,000?

The goal is to estimate the theoretical maximum size of the global routing table
that under the current processor speed would perform core routing with the delay not
exceeding 100ms.

Thanks,

Peter 

       
____________________________________________________________________________________
Choose the right car based on your needs.  Check out Yahoo! Autos new Car Finder tool.
http://autos.yahoo.com/carfinder/

---

From: Geoff Huston <[email-masked]>
Date: Fri, 03 Aug 2007 07:20:24 +1000

Peter Sherbin wrote:
> The current ratio is about 8.9 routes per AS. 

This is a Very Fine Number (:-)). How did it come about?

    Geoff

---

From: Robin Whittle <[email-masked]>
Date: Fri, 03 Aug 2007 11:32:08 +1000

The iPlane project:

  http://iplane.cs.washington.edu/data.html

has a file "Lists of alias clusters", where each line is a router,
with the IP addresses of its one or more interfaces.

I wrote to them earlier this week about trying to use this data to
infer the number of single-homed routers and multihomed/transit
routers.  My analysis of the current file didn't match their
statement in November last year:

  This clustering algorithm, when executed on a typical traceroute
  output, clusters 762,701 interfaces into 54,530 clusters. 653,455
  interfaces are in 10,713 clusters of size greater than 10, while
  21,217 interfaces are in singleton clusters.

When I looked the other day, there were very few single IP address
lines.

They said they would get back to me soon with proper information on
the number of singlehomed and multihomed/border routers, because at
present their data doesn't enable this to be determined.

I will post whatever I find out to this list and to the RAM list.

  - Robin

---

From: Peter Sherbin <[email-masked]>
Date: Fri, 3 Aug 2007 06:10:57 -0700 (PDT)

draft-narten-radir-problem-statement-00.txt shows the number of AS at 25,836 and the
number of routes at 229,789.

229,789/25,836 = 8.9 routes per AS

Thanks,
Peter

      ____________________________________________________________________________________
Fussy? Opinionated? Impossible to please? Perfect.  Join Yahoo!'s user panel and lay it on us. http://surveylink.yahoo.com/gmrs/yahoo_panel_invite.asp?a=7

---

From: Geoff Huston <[email-masked]>
Date: Sat, 04 Aug 2007 07:59:00 +1000

my mistake - I thought you were referring to the subject line of routeRs 
rather than routes

The routers per AS is interesting.. in early 2001 it was around 9.8, and 
it dropped to around 7.9 in mid 2004 and its on the way back up now

http://bgp.potaroo.net/cgi-bin/plota?file=%2fvar%2fdata%2fbgp%2fas2%2e0%2fbgp%2dentries%2das%2etxt&descr=Average%20entries%20per%20origin%20AS&ylabel=Average%20entries%20per%20origin%20AS&with=step

Either the big guys are getting bigger (and the distribution is a long 
tail distribution) or the growth of single entry edge ASs at the edge 
(multi-homers) is dropping

The first is somewhat expected  - the second is potentially interesting.

    Geoff

---

From: Peter Sherbin <[email-masked]>
Date: Fri, 10 Aug 2007 07:29:54 -0700 (PDT)

Here is a good comment on the recent RRG discussion about routers in DFZ and
relationship between number of prefixes and the processing power. Details are below
and here is the essence:

> 	so, one might presume that w/o a change in algorithm, and unlimited
> 	memory, that the CPU would run out of cycles to compute convergence
> 	at ~ 10x the current size of the routing table (abt 250,000 prefixes).
> 
> 	so putting a stake in the ground, BGP will stop working @ around
> 	2,500,000 routes - can't converge...  regardless of IPv4 or IPv6.
> 	unless the CPU's change or the convergence algorithm changes.

In particular it provides a theoretical limit that can be added to the Problem
Statement draft-narten-radir-problem-statement-00.txt

Thanks,

Peter

--- [email-masked] wrote:

>  I asked this question to a couple of folks:
> 
> 	"at the current churn rate/ration, at what size doe the FIB need to 
>          be before it will not converge?"
> 
>  and got these answers:
> 
> --------- jabber log ---------
> a fine question, has been asked many times, and afaik noone has
> provided any empirically grounded answer.
> 
> a few realities hinder our ability to answer this question.
> 
> (1) there are technology factors we can't predict, e.g.,
>         moore's law effects on hardware development
> (2) there are economics and policy and social factors we
>         can't predict, e.g., how much convegence-capable
>         hardware will providers/vendors be able to afford,
>         how those costs will affect consumer prices,
>         how that will affect consumer uptake, network
>         growth, and industry dynamics, how regulation affects
>         all of the above
> (3) We Don't Have Any Data from providers on the dynamics of BGP
>         and IGP interactions, much less network wide convergence,
>         so the research community can't provide any empirically
>         grounded input into an answer
> 
> {elided}
> -------------------------------
> &
> ------ Forwarded Message ------
> 
> Date: Tue, 07 Aug 2007 
> To: [email-masked]
> Subject: CPU Usage
> 
> Router		      Upstream Uptime		BGP cpu per 1 sec uptime
> Cat6500/SUP720		1	>1yr		53ms/sec
> C7200/NPE-G1		1	158days		15ms/sec
> C7304/NSE100		4+2	177days		55ms/sec
> C7200/NPE-G1		1+2	26days		 8ms/sec
> C7301			1	214days		 7ms/sec
> GR2000			0+1	101days		 6ms/sec
> 
> Upstream: M+N, M is # of EBGP with full route feed , N is # of IBGP
> with full route feed
> 
> Provided if the CPU consumption is propotional to the routing table
> size, the hard limit would be 10 times to the current size, allowing
> other tasks to obtain some CPU cycles.
> 
> ----- End forwarded message -----
> 
> 	so, one might presume that w/o a change in algorithm, and unlimited
> 	memory, that the CPU would run out of cycles to compute convergence
> 	at ~ 10x the current size of the routing table (abt 250,000 prefixes).
> 
> 	so putting a stake in the ground, BGP will stop working @ around
> 	2,500,000 routes - can't converge...  regardless of IPv4 or IPv6.
> 	unless the CPU's change or the convergence algorithm changes.
> 
> --bill	
> _______________________________________________
> PPML
> You are receiving this message because you are subscribed to the ARIN Public
> Policy
> Mailing List ([email-masked]).
> Unsubscribe or manage your mailing list subscription at:
> http://lists.arin.net/mailman/listinfo/ppml Please contact the ARIN Member
> Services
> Help Desk at [email-masked] if you experience any issues.
> 

____________________________________________________________________________________
Take the Internet to Go: Yahoo!Go puts the Internet in your pocket: mail, news, photos & more. 
http://mobile.yahoo.com/go?refer=1GNXIC

---

From: "John G. Scudder" <[email-masked]>
Date: Fri, 10 Aug 2007 17:46:03 -0400

Peter,

I have a few observations on this "stake in the ground".

First and foremost, the notion that linear extrapolation can reveal  
when "the CPU would run out of cycles to compute [BGP] convergence"  
is most likely incorrect.  There are several reasons for this, but  
the principal one is the fact that BGP operates over a flow- 
controlled transport, combined with the "state compression" property  
of BGP.  The former ensures that BGP will only transmit updates as  
fast as its peer can consume them, so any proper BGP implementation  
won't be overrun even if slow -- it'll just apply backpressure to its  
peer by allowing the TCP window to close.  (This is just a natural  
consequence of any application operating over TCP.)  The latter  
provides that when a BGP implementation wishing to send to a peer  
becomes flow-blocked, it'll stop generating update messages (modulo  
what may already have been written to the TCP socket).  When it  
becomes unblocked, it begins generating update messages reflecting  
the current state of its routing table.  To see how this works,  
consider the following pair of examples:

Two fast routers conversing:
- Fast router F talks to fast router G.  The connection to G flows  
freely.
- F receives an update for prefix P from some other peer.  It  
propagates the update to G immediately.
- F receives another update for prefix P from yet another peer.  It  
propagates it immediately.
- F receives yet another such update from still another peer.  It  
propagates it immediately.
Net effect, G has received three updates for P, and has converged to  
P's final state.  CPU consumption on G to converge to P's final state  
is 3 x (cost to process one update).

A fast router conversing with a slow one:
- Fast router F talks to slow router S.
- At some point, S flow-blocks F.
- While flow-blocked, F receives the same set of three updates for P  
as in the example above.  It doesn't propagate them to S since the  
connection is flow-blocked.
- At some later point, S unblocks F's connection.
- At that point, F propagates only the final state of P.
Net effect, S has received only a single update for P, and has also  
converged to P's final state.  CPU consumption on S to converge to  
P's final state is 1 x (cost to process one update).

(I discussed this property during my Routing Area presentation at the  
Prague IETF, and I think Geoff Huston has touched on it in some of  
his recent articles.)

The example is somewhat simplified, and the dynamics that emerge from  
this are non-obvious but I think you'll agree that a simple linear  
extrapolation doesn't work.  I think the most we can say is that the  
"stake in the ground" provides a lower limit on expectations, not a  
tight bound as the previous author suggests.

A second observation is that the analysis given assumes today's  
(yesterday's, actually) control plane CPUs but extrapolates out to  
years from now.  To paraphrase one of the other (quoted, anonymous)  
authors, although we may not know particulars of future upgrades,  
it's not reasonable to assume that control plane CPUs will never be  
upgraded.

None of this should be construed as an opinion that BGP can't be  
improved or that it will scale infinitely.  But "BGP will stop  
working ... can't converge" is overly pessimistic.

In closing I'll just say that whatever the quoted (2.5M) number may  
be, it's certainly nothing like a "theoretical limit".  It's at best  
a guess, and I've argued above, probably not a very accurate one.

Regards,

--John

---

From: Dino Farinacci <[email-masked]>
Date: Sat, 11 Aug 2007 13:29:05 -0700

> working ... can't converge" is overly pessimistic.

But don't you think we should stop putting more features into BGP  
like VPN stuff and multicast routing? That would be taking us faster  
in the pessimistic direction.

Dino

---

From: "John G. Scudder" <[email-masked]>
Date: Sat, 11 Aug 2007 21:45:14 -0400

On Aug 11, 2007, at 4:29 PM, Dino Farinacci wrote:
> like VPN stuff and multicast routing? That would be taking us  
> faster in the pessimistic direction.

Good point.  Actually I think we should stop making any changes to  
the overall control plane -- just freeze it, it's done.  We should  
also stop adding prefixes to the DFZ.  That should fix any concerns.

Joke, joke!  But I hope you get my drift.

--John

---

From: Robert Raszuk <[email-masked]>
Date: Sun, 12 Aug 2007 00:37:20 -0700

Dino,

What would make BGP different from IGPs in that respect ? And last time 
at least in ISIS WG I heard that there is a proposal to run routing IGP 
separated from non routing uses for IGP ?

Along the same lines we could run two BGP instances ... I guess someone 
could write up MI-BGP draft now.

Cheers,
R.

---

From: Dino Farinacci <[email-masked]>
Date: Sun, 12 Aug 2007 01:36:42 -0700

> What would make BGP different from IGPs in that respect ? And last  
> time at least in ISIS WG I heard that there is a proposal to run  
> routing IGP separated from non routing uses for IGP ?

Just because another working group makes mistakes doesn't mean BGP  
should follow. But to satisfy your question, BGP typically carries a  
much heavier data load than IGPs do.

Now if you said that if all the stuff carried inside of iBGP was  
redistributed into an IGP, then I would make the same claim that too  
much is being put into the IGP.

Dino

---

From: "John G. Scudder" <[email-masked]>
Date: Sun, 12 Aug 2007 12:47:42 -0400

On Aug 12, 2007, at 3:37 AM, Robert Raszuk wrote:
> Along the same lines we could run two BGP instances ... I guess  
> someone could write up MI-BGP draft now.

Done.  draft-ietf-idr-bgp-multisession-03 provides the necessary  
protocol machinery.

--John

---

From: Eliot Lear <[email-masked]>
Date: Sun, 12 Aug 2007 19:36:39 +0200

John,
> Done.  draft-ietf-idr-bgp-multisession-03 provides the necessary 

While that draft looks reasonable for its intended purpose, I think Dino 
was talking about actually shoveling less crap around, router by 
router.  That having been said, I've somewhat lost the plot here.  Is 
the point to allow for priority processing of certain types of 
information in the face of a performance problem?  If so, that's a fine 
*tactical* and incremental approach (although I don't think much of 
using a TCP window as application layer flow control - it leads to bad 
behaviors on both sides when the number of connections increase [See 
RFC-793, Page 42, "Managing the Window").

But to your original point, that one cannot simply assume a linear death 
march, I'd agree.  I think Tony and others' points were that the issue 
here is in cost and development curves, looking many MANY years out.  If 
we can find an even better approach to avoid brute force with acceptable 
trade-offs (and those are a lot of ifs), then we've advanced the state 
of the art and that's a good thing.

Eliot

---

From: Eliot Lear <[email-masked]>
Date: Sun, 12 Aug 2007 19:36:39 +0200

John,

Eliot

______________________________________________________________________
This email has been scanned by the MessageLabs Email Security System.
For more information please visit http://www.messagelabs.com/email 
______________________________________________________________________