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: bmanning@karoshi.com 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
the fib in a heavily peered dfz router does not often converge now. the question is when will the router not be able to process the volume of churn, i.e. fall behind further and further? as there is non-trivial headroom in the algorithms, moore's law on the processors, etc. etc., your message is as operationally meaningful as dave and john telling us they can handle 2m prefixes today. randy
On Thu, Aug 09, 2007 at 07:24:58AM -1000, Randy Bush wrote:
the fib in a heavily peered dfz router does not often converge now.
never? or over some predefined period of time?
the question is when will the router not be able to process the volume of churn, i.e. fall behind further and further?
yes. presuming the churn ratio stays the same and:
as there is non-trivial headroom in the algorithms,
the BGP algorithm does not change (BGP-5, BGP-6 etc anyone)
moore's law on the processors, etc. etc.,
yes, yes, yes... too many variables. fixing the processors to what is fielded TODAY, with existing algorithms, etc... if the ONE variable is to allow enough memory to hold prefixen, will BGP fail (a router not being able to process the volume of churn) at what point? (other variables: number of exteranal peers, IGP updates, AS path length, etc... what else needs to be considered?)
your message is as operationally meaningful as dave and john telling us they can handle 2m prefixes today.
well, maybe. the numbers were collected from live boxen. not enough data for anything you might be able to use tho.
randy
the fib in a heavily peered dfz router does not often converge now. never? or over some predefined period of time?
not often
as there is non-trivial headroom in the algorithms, the BGP algorithm does not change (BGP-5, BGP-6 etc anyone)
algorithm != protocol randy
On 8/9/07, Randy Bush <randy@psg.com> wrote:
the fib in a heavily peered dfz router does not often converge now. the question is when will the router not be able to process the volume of churn, i.e. fall behind further and further? as there is non-trivial headroom in the algorithms, moore's law on the processors, etc. etc., your message is as operationally meaningful as dave and john telling us they can handle 2m prefixes today.
Randy, do you have data on this - that a peered dfz router does often not converge now? /vijay randy
_______________________________________________ PPML You are receiving this message because you are subscribed to the ARIN Public Policy Mailing List (PPML@arin.net). Unsubscribe or manage your mailing list subscription at: http://lists.arin.net/mailman/listinfo/ppml Please contact the ARIN Member Services Help Desk at info@arin.net if you experience any issues.
On Aug 9, 2007, at 12:21 PM, bmanning@vacation.karoshi.com wrote:
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.
That is a pretty big "unless" . Cordially Patrick Giagnocavo patrick@zill.net
Yes a very big unless. Multi-core processors are already available that would make very large BGP convergence possible. Change the algorithm as well and perhaps add some multi-threading to it and it's even better. -- Leigh Porter Patrick Giagnocavo wrote:
On Aug 9, 2007, at 12:21 PM, bmanning@vacation.karoshi.com wrote:
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.
That is a pretty big "unless" .
Cordially
Patrick Giagnocavo patrick@zill.net
On Aug 9, 2007, at 12:09 PM, Leigh Porter wrote:
Yes a very big unless. Multi-core processors are already available that would make very large BGP convergence possible. Change the algorithm as well and perhaps add some multi-threading to it and it's even better.
Anyone have a decent pointer to something that covers the current state of the art in algorithms and (silicon) router architecture, and maybe an analysis that shows the reasoning to get from those to realistic estimates of routing table size limits? Cheers, Steve
-- Leigh Porter
Patrick Giagnocavo wrote:
On Aug 9, 2007, at 12:21 PM, bmanning@vacation.karoshi.com wrote:
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.
That is a pretty big "unless" .
Cordially
Patrick Giagnocavo patrick@zill.net
On Thu, 9 Aug 2007, Steve Atkins wrote:
On Aug 9, 2007, at 12:09 PM, Leigh Porter wrote:
Yes a very big unless. Multi-core processors are already available that would make very large BGP convergence possible. Change the algorithm as well and perhaps add some multi-threading to it and it's even better.
Anyone have a decent pointer to something that covers the current state of the art in algorithms and (silicon) router architecture, and maybe an analysis that shows the reasoning to get from those to realistic estimates of routing table size limits?
no, not exactly - but take a look at: Report from the IAB Workshop on Routing and Addressing http://tools.ietf.org/html/draft-iab-raws-report Routing Research Group Active Proposals http://www3.tools.ietf.org/group/irtf/trac/wiki/RoutingResearchGroup On Compact Routing for the Internet http://www.caida.org/publications/papers/2007/compact_routing/compact_routin... - Lucy
Cheers, Steve
-- Leigh Porter
Patrick Giagnocavo wrote:
On Aug 9, 2007, at 12:21 PM, bmanning@vacation.karoshi.com wrote:
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.
That is a pretty big "unless" .
Cordially
Patrick Giagnocavo patrick@zill.net
On Thu, Aug 09, 2007 at 08:09:54PM +0100, Leigh Porter wrote:
Yes a very big unless. Multi-core processors are already available that would make very large BGP convergence possible. Change the algorithm as well and perhaps add some multi-threading to it and it's even better.
i'll be happy to review the data sheets and prices of routers w/ multicore processors. pointers accepted. changing the algorithm might be a bit harder, as i think you'll need to change the BGP core spec for that. --bill
-- Leigh Porter
Patrick Giagnocavo wrote:
On Aug 9, 2007, at 12:21 PM, bmanning@vacation.karoshi.com wrote:
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.
That is a pretty big "unless" .
Cordially
Patrick Giagnocavo patrick@zill.net
On Thu, Aug 09, 2007 at 02:56:31PM -0400, Patrick Giagnocavo wrote:
On Aug 9, 2007, at 12:21 PM, bmanning@vacation.karoshi.com wrote:
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.
That is a pretty big "unless" .
sure... how often do you completely swap out all your router processors? anyone running something other than BGP4? (BGP3 and EGP don't count)
Cordially
Patrick Giagnocavo patrick@zill.net
On Thu, Aug 09, 2007 at 09:08:05PM +0000, bmanning@vacation.karoshi.com wrote:
On Thu, Aug 09, 2007 at 02:56:31PM -0400, Patrick Giagnocavo wrote:
On Aug 9, 2007, at 12:21 PM, bmanning@vacation.karoshi.com wrote:
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.
That is a pretty big "unless" .
sure... how often do you completely swap out all your router processors? anyone running something other than BGP4? (BGP3 and EGP don't count)
See, thats the whole thing here... There will always be legacy equipment in the network. There will always be advances in processors and newer equipment will be able to handle more. The REAL question is wether a threshold will be reached for some popular older equipment before it gets largely cycled out of use. The odd company having a problem on one or two boxes is no big deal. Major carrier A having problems in 6 or 12 (or possibly many more) routers simultaneously is a bit of an issue. Could even cause a cascade to external nodes as routers die and reload. To an extent, this can be dealt with through damping and filtering policies but there will still be a vulnerability. What should be considered is wether or not the curve of route growth will overtake the curve of hardware upgrades and increases in overall base levels of processing power. My personal oppinion is that it's unlikely. Possible, but unlikely. -Wayne --- Wayne Bouchard web@typo.org Network Dude http://www.typo.org/~web/
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
Moore's Law is only half of the equation. It is the part that deals with route churn & the rate at which those can be processed (both peer notification and control-plane programming data-plane in the form of FIB changes). Moore's Law almost has zero relevance to FIB sizes. It doesn't map to growth in SRAM or innovations/mechanisms for how to reduce the requirements for SRAM while growing FIB sizes. cheers, lincoln.
Lincoln Dale 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
Moore's Law is only half of the equation. It is the part that deals with route churn & the rate at which those can be processed (both peer notification and control-plane programming data-plane in the form of FIB changes).
Moore's law just makes an observation that the transistor count feasible for a minimum cost component doubles every 24 months. It actually says nothing about the performance of those components or their speed.
Moore's Law almost has zero relevance to FIB sizes. It doesn't map to growth in SRAM or innovations/mechanisms for how to reduce the requirements for SRAM while growing FIB sizes.
sram components are following their own trajectory and you can fairly easily at this point project how big a cam you'll be able to buy and what it's power consumption will be out a couple years from the products currently in your routers (which are for the most part not state of the art). That said, not all forwarding engines in line cards utilize ternary cams or srams so assumptions that involve sram and sram-like components being the only game in town for fib storage are dangerous.
cheers,
lincoln.
In a message written on Thu, Aug 09, 2007 at 04:21:37PM +0000, bmanning@vacation.karoshi.com wrote:
(1) there are technology factors we can't predict, e.g., moore's law effects on hardware development
Some of that is predictable though. I'm sitting here looking at a heavily peered exchange point router with a rather large FIB. It has in it a Pentium III 700Mhz processor. Per Wikipedia (http://en.wikipedia.org/wiki/Pentium_III) it appears they were released in late 1999 to early 2000. This box is solidly two, perhaps three, and maybe even 4 doublings behind things that are already available at your local best buy off the shelf. Heck, this chip is slower than the original Xbox chip, a $400 obsolete game console. -- Leo Bicknell - bicknell@ufp.org - CCIE 3440 PGP keys at http://www.ufp.org/~bicknell/ Read TMBG List - tmbg-list-request@tmbg.org, www.tmbg.org
participants (11)
-
bmanning＠vacation.karoshi.com -
Joel Jaeggli -
Leigh Porter -
Leo Bicknell -
Lincoln Dale -
Lucy Lynch -
Patrick Giagnocavo -
Randy Bush -
Steve Atkins -
vijay gill -
Wayne E. Bouchard