too many variables

Mailman List Mirror (Read Only)
1

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}

2

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

3

That is a pretty big "unless" .

Cordially

Patrick Giagnocavo
patrick@zill.net

4

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.

5

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

6

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.

7

> 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)

8

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

9

Sun just released the T2 chip, claimed 60GB/s memory bandwidth, on-board 10GbE interface etc.

Pricing under $1000 for an 8-core chip with 64 "threads".

Cordially

Patrick Giagnocavo
patrick@zill.net

10

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

11

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

Routing Research Group Active Proposals
http://www3.tools.ietf.org/group/irtf/trac/wiki/RoutingResearchGroup

On Compact Routing for the Internet

- Lucy

12

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

13

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.

14

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.

15

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

16

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.

17

And yet people still say the sky is falling with respect to routing convergence and FIB size. Probably a better comparison BTW, would be with a Nintendo or Playstation, as they are MIPS and PowerPC based. Even the latest route processor for a decent peering box is only a 1.2 GHz PowerPC with 2 GB RAM (RSP720) - so basically an old iBook is enough for the BGP control plane load these days? I think this has something to do with the vendors giving you just enough to keep you going, but not so much that you delay hardware upgrades :slight_smile:

There have been big gains in silicon for the fast switched path, but the route processors even on high end routers are still pretty low end in comparison to what’s common on the average desktop.
I would say that when control plane/processor power becomes critical, I would hope to see better processors inside.

With the IETF saying that speed and forwarding path are the bottlenecks now, not FIB size, perhaps there just isn’t enough load to push Core Duo processors in your routers. (If Apple can switch, why not Cisco?) http://www3.ietf.org/proceedings/07mar/slides/plenaryw-3.pdf

I guess people are still spectacularly missing the real point. The point isn’t that the latest generation hardware cpu du jour you can pick up from the local hardware store is doubling processing power every n months. The point is that getting them qualified, tested, verified, and then deployed is a non trivial task. We need to be substantially behind moores observation to be economically viable. I have some small number of route processors in my network and it is a major hassle to get even those few upgraded. In other words, if you have a network that you can upgrade the RPs on every 18 months, let me know.

/vijay

18

In a message written on Fri, Aug 10, 2007 at 11:08:26AM -0700, vijay gill wrote:

   substantially behind moores observation to be economically viable. I
   have some small number of route processors in my network and it is a
   major hassle to get even those few upgraded. In other words, if you
   have a network that you can upgrade the RPs on every 18 months, let me

You're mixing problems.

Even though you may only be able to put in a new route processor
every 3-5 years doesn't mean the vendor shouldn't have a faster
version every 18 months, or even sooner. It's the addition of the
two that's the problem. You're 5 year cycle may come a year before
the vendors 5 year cycle, putting you on 9 year old gear before you
refresh next.

Vendor J got it half right. The RP is a separately replaceable
component based on a commodity motherboard, hooked in with commodity
ethernet, using the most popular CPU and ram on the market. And
yes, I understand needing to pay extra for the sheet metal, cooling
calculations, and other items.

But, they still cost 10x a PC based on the same components, and are
upgraded perhaps every 3 years, at best. They don't even take
advantage of perhaps going from a 2.0Ghz processor to a 2.4, using
the same motherboard, RAM, disk, etc.

But I think the point still stands, I bet Vendor J in particular
could pop out a Core 2 Duo based RP with 8 gig of ram and a 300+
gig hard drive in under 6 months while holding the price point if
BGP convergence demanded it, and their customers made it a priority.

To Bill's original e-mail. Can we count on 2x every 18 months going
forward? No. But betting on 2x every 24 months, and accounting for the
delta between currently shipping and currently available hardware seems
completely reasonable when assessing the real problem.

19

[ vijay]

I guess people are still spectacularly missing the real point. The point
isn't that the latest generation hardware cpu du jour you can pick up from
the local hardware store is doubling processing power every n months.

agreed.

The point is that getting them qualified, tested, verified, and then
deployed is a non trivial task. We need to be substantially behind moores
observation to be economically viable. I have some small number of route
processors in my network and it is a major hassle to get even those few
upgraded. In other words, if you have a network that you can upgrade the RPs
on every 18 months, let me know.

yow. while i agree that routing processors cannot, and have historically not
had to, track moore's law, i am still surprised to see such a heavy focus on
the RP. my (ample) gut feeling on this is that system level (combinatorial)
effects would limit Internet routing long before moore's law could do so.

20

In a message written on Fri, Aug 10, 2007 at 11:08:26AM -0700, vijay gill wrote:

substantially behind moores observation to be economically viable. I
have some small number of route processors in my network and it is a
major hassle to get even those few upgraded. In other words, if you
have a network that you can upgrade the RPs on every 18 months, let me

You’re mixing problems.

Even though you may only be able to put in a new route processor
every 3-5 years doesn’t mean the vendor shouldn’t have a faster
version every 18 months, or even sooner. It’s the addition of the
two that’s the problem. You’re 5 year cycle may come a year before
the vendors 5 year cycle, putting you on 9 year old gear before you
refresh next.

The vendor has to qualify, write code for, and support n versions. This IS a part of the problem. Just blindly swapping out CPUs is non trivial, as any systems engineer can tell you. The support cost will be passed on to the consumer.

/vijay