Subject: [rrg] BGP scaling limit?

From: "William Herrin" <[email-masked]>
Date: Wed, 31 Dec 2008 16:40:54 -0500

On Wed, Dec 31, 2008 at 1:30 AM, Tony Li <[email-masked]> wrote:
> |<[email-masked]> wrote:
> |> It is not known with any scientific or engineering accuracy when
> |> vanilla BGP4 will reach an economic or technical scaling limit
>
> |And what's the justification for maintaining
> |the IETF recommendation that the RIRs impose artificial restrictions
> |on the minimum allocation size? Or for that matter any restrictions at
> |all on IPv6 assignment in multihomed environments?
>
> Adding more prefixes will hasten the inevitable.

If it isn't justified quantitatively then it's just FUD.

Do the folks on this group clearly understand the harm that the
Regional Internet Registries do by denying number resources to
multihomed registrants based on our assurance that it's a necessary
evil in order to keep BGP stable?

If we still can't reliably quantify a BGP scaling limit then our
request that the RIRs suppress BGP growth by suppressing resource
assignment is simply unconscionable.

> We know of no hard upper bound to BGP or (more importantly)
> the routing architecture as it currently exists.  It is apparent that unless
> there is some significant progress somehow, the cost and/or complexity of
> running the current architecture is going to start to climb.

Climb to what?

Assume a $2k COTS PC purchased 12/31/08 with component choice
optimized for routing.

Assume the ratio between BGP routes and updates per second will follow
whatever growth pattern has been demonstrated in the ratio of routes
to updates over the last 10 years. I expect this ratio is constant or
near constant.

Assume the PC builds a trie-based FIB from the BGP RIB. Trie based
FIBs are known to exhibit a growth in resource consumption which is
linear relative to the traffic switched, regardless of the size of the
trie.

How many routes can we pack in before we either fill memory, can no
longer sustain both the 500mbps routing rate and keep up with BGP
updates? Surely we can answer this question with engineering accuracy!

Can we not compute the same for a $2k PC 5 and 10 years ago? If we
can, then we can with scientific accuracy project where that limit
will be for the foreseeable future.

At worst, a high-speed router consists of parallel units of lower
speed routers, a linear increase in cost tied to the data rate but not
the table size. So if the above can be done we will have, with
scientific accuracy, deduced a function which yields an upper bound
for BGP scalability.

Regards,
Bill Herrin

-- 
William D. Herrin ................ [email-masked]  [email-masked]
3005 Crane Dr. ...................... Web: <http://bill.herrin.us/>
Falls Church, VA 22042-3004
_______________________________________________
rrg mailing list
[email-masked]
https://www.irtf.org/mailman/listinfo/rrg

---

From: "Christopher Morrow" <[email-masked]>
Date: Wed, 31 Dec 2008 17:27:21 -0500

> evil in order to keep BGP stable?

There's a fairly constant swing between the RIR folks saying: "Please
send out some guidance (/48, /56, /35, /32... pick pls) and the IETF
saying: "Well, we don't want to make something in stone/rfc else it'll
be a PITA to change later, and we KNOW it'll have to change
(ala-cidr-switch)"

I think folks, in general, get that hampering resource allocation ==
hampering network-growth == slowing the goodness that IP/Internet
is/could-be.  That said, there's pressure to make sure that we don't
blow up while trying to get to the end-state.

> assignment is simply unconscionable.

In 2005-ish at the IAB Workshop in AMS there was a good several
presenations on scaling/growth (one by Tony Li about hardware and why
moores-law doesn't apply to the gear in backbone networks).

>> running the current architecture is going to start to climb.

'more expensive'.. I really don't think anyone can put a hard number
on this, but the running theory is that network devices will start
costing significantly more per device than they do today for the same
performance envelop PPS-wise, to handle a much larger routing
table/FIB.

(Keep in mind that not only is RIB size important but RIB
stability/rate-of-change is as well, and these two things hit two
different parts of the device today...)

> Assume a $2k COTS PC purchased 12/31/08 with component choice

you can't make this assumption as 2k cots devices can't forward at
+100gbps, a core backbone device today can, and do in several
networks.

> to updates over the last 10 years. I expect this ratio is constant or

it's actually not constant, there are a number of factors (I think
Geoff Huston has some reasons/numbers here as well) involved. One
factor being 'laziness/incompetence/bad-actors' another being a
business model which is essentially arbitration of inbound traffic
costs via route updates...  Some of these reasons perhaps are constant
pains, some are new pains.

> updates? Surely we can answer this question with engineering accuracy!

One point Tony made was that soon, perhaps, you won't be able to make
a lookup across the memory device holding the FIB fast enough to
service a packet on the fastest known interfaces today, presuming the
FIB grows in memory at some set rate (look at the graphs Vince Fuller
or Geoff Huston have for approximations of the rates).

-Chris
(IAB Workshop results RFC:
<http://www.ietf.org/rfc/rfc4984.txt>
workshop contents:
<http://www.iab.org/about/workshops/routingandaddressing/> )
_______________________________________________
rrg mailing list
[email-masked]
https://www.irtf.org/mailman/listinfo/rrg

---

From: "William Herrin" <[email-masked]>
Date: Wed, 31 Dec 2008 18:24:38 -0500

> moores-law doesn't apply to the gear in backbone networks).

Chris,

I think I read that one. It was right before dram bandwidth took a
sharp upward turn from something like 400mhz to I think 1600mhz today.
Prior to that, it exhibited less than half the rate of change,
increasing from 100 mhz in 1998 to 400 mhz in 2005.

> +100gbps, a core backbone device today can, and do in several

Sure I can. My $2k COTS PC can route 500mbps easily. Packet switching
trivially parallelizes, so it follows that for no more than 200 times
the price I can move 200 times the packets. This doesn't tell me what
the actual cost would be, but it allows me to set an upper bound.

> it's actually not constant, there are a number of factors

Whatever it is, we should be able to plot points from years past on a
ratio to date graph and then fit a trend curve to it.

> or Geoff Huston have for approximations of the rates).

If you can move packets across an interface at the given data rate
then you can blindly multiplex and demultiplex packets from and to
lower speed interfaces. This reduces the problem to one previously
solved. There's doubtless a better solution but for conceptual
purposes, that eliminates the data rate boundary condition as an
active factor in the scalability assessment.

Regards,
Bill Herrin

---

From: "Christopher Morrow" <[email-masked]>
Date: Wed, 31 Dec 2008 18:36:39 -0500

> increasing from 100 mhz in 1998 to 400 mhz in 2005.

ah, then... perhaps tony can weigh in with a: "Yea, all good now" or
"well, it's not quite as simple as that... + explanation?" ?? I was
under the impression that DRAM wasn't the issue, but I'm fuzzy now as
to the details.

> Sure I can. My $2k COTS PC can route 500mbps easily. Packet switching

sorry, of course you can make the assumption, I just don't think it
follows as closely to reality as you'd want. that 500mbps isn't doing
anything tough, with a small table, few interfaces, no services, no
acls/filtering/qos ... consumer PC's just aren't a good correlary for
backbone devices.

> the actual cost would be, but it allows me to set an upper bound.

again, I don't think it follows that rational or simple a
process/curve. However, if we wanted to say that 'today' we can buy a
fully decked out 'backbone router' for 2m$/device, and yesterday it
was 2.5M for the same device, and tomorrow it'll be 1.5M (and draw a
set of curves for bw/pps/cost over time then sure... I'm not sure how
accurate it'll be, or useful)

> ratio to date graph and then fit a trend curve to it.

This I agree with, there is some trend, there should be some sort of
function. To date, there hasn't been an effort (that I've seen) to fit
a function to the plots vaf/huston have made from the route-table size
data... I've not seen any useful 'rate of change' graphs since some of
that is location dependent. Dave Meyer was talking, about 1.5 yrs ago,
about trying to find funding to research the dynamics of the table
change, I've not asked if that made headway. That does seem like what
you want though, eh?

> active factor in the scalability assessment.

out of order packets aren't a concern? filtering? qos? stream-size
limits? at a gross level it might be comparable, but I'm not sure it
helps cost a device that'll fit in a half-rack and push 1600gbps
(T1600-juniper/ASR9k-cisco).

-chris

---

From: "Tony Li" <[email-masked]>
Date: Wed, 31 Dec 2008 16:00:58 -0800

|> Adding more prefixes will hasten the inevitable.
|
|If it isn't justified quantitatively then it's just FUD.

Please see my RAWS talk, oh so long ago
(http://www.iab.org/about/workshops/routingandaddressing/Router_Scalability.
pdf).  I showed (quantitatively) that the growth in the routing table simply
exceeds the speed improvement of DRAM.  The implication is that unless we
increase cost structures, convergence will suffer.

|Do the folks on this group clearly understand the harm that the
|Regional Internet Registries do by denying number resources to
|multihomed registrants based on our assurance that it's a necessary
|evil in order to keep BGP stable?

AFAIK, the RIRs are, for v4, requiring sane and reasonable justification for
PI prefixes.  For v6, they're effectively giving everyone PI.  Can you be
more specific about the policies that you're objecting to.

|If we still can't reliably quantify a BGP scaling limit then our
|request that the RIRs suppress BGP growth by suppressing resource
|assignment is simply unconscionable.

Do we need to reliably quantify where the Earth will reach the tipping point
into a irreversible greenhouse effect before global warming is relevant?

|> It is 
|apparent that unless
|> there is some significant progress somehow, the cost and/or 
|complexity of
|> running the current architecture is going to start to climb.
|
|Climb to what?

That depends entirely on the continuing prefix growth rate and the level of
additional sophistication and replication necessary to support the rate.

|[Gedanken experiment with PC's for BGP elided...]
|
|Can we not compute the same for a $2k PC 5 and 10 years ago? If we
|can, then we can with scientific accuracy project where that limit
|will be for the foreseeable future.

You're asking for an absolute hard limit in a situation where there are many
variables that you have not yet quantified.  How many peers does the BGP
speaker have?  What is the number of paths per route?  How long is the
average AS path?  And does this simulation still have any relevance?

And why are we limited to a $2K PC?  Why can't we upgrade to server
architectures?

Because of this complexity, it's far simpler to point out that the
underlying hardware technology (DRAM, for the case of the RIB), simply
cannot keep up with our needs, even given known trends in hardware
scalability.  

|At worst, a high-speed router consists of parallel units of lower
|speed routers, a linear increase in cost tied to the data rate but not
|the table size. 

In a modern router, the FIB is distributed to each line card, and since the
FIB cost is proportional to the table size, the increase in cost is tied to
both the data and size.  This is the fundamental "rate * state" quandry.

|So if the above can be done we will have, with
|scientific accuracy, deduced a function which yields an upper bound
|for BGP scalability.

No, you've only driven towards a simulation that shows what constant cost
might yield for a single data point on a multi-variate surface.

Tony

---

From: "Tony Li" <[email-masked]>
Date: Wed, 31 Dec 2008 16:31:12 -0800

|> I think I read that one. It was right before dram bandwidth took a
|> sharp upward turn from something like 400mhz to I think 
|1600mhz today.
|> Prior to that, it exhibited less than half the rate of change,
|> increasing from 100 mhz in 1998 to 400 mhz in 2005.
|>
|
|ah, then... perhaps tony can weigh in with a: "Yea, all good now" or
|"well, it's not quite as simple as that... + explanation?" ?? I was
|under the impression that DRAM wasn't the issue, but I'm fuzzy now as
|to the details.

DRAM is a clear case in point where our growth exceeds what technology has
delivered.  Thus we simply can't "throw hardware at the problem".

Now I have to confess that I'm certainly not the world's expert on DRAM
technology, but nothing that I've seen so far truly changes the equation.
First, recall that the focus is on commodity DRAM, as that is the segment
that drives volumes and thus prices.  Yes, we can always go off of the
commodity cost curve, but if we're willing to do that we can also just throw
gobs of SRAM at the problem.  Again the point is what we will be able to do
for constant cost.

So far, what I'm seeing is that faster memories are not going to be the
mainstream.  Yes, that may change, but we have yet to see how that is going
to play out.

>From the technology front, my understanding is that these higher bandwidths
are being achieved through more channels (i.e., replication) and by
migrating from DDR2 to DDR3.  This improves the bandwidth to memory, but
does not improve the latency of the underlying memory cells.  (Ref:
http://en.wikipedia.org/wiki/DDR3_SDRAM).  

Unfortunately, BGP has an annoying tendency to do fairly random access (tree
walks) through large data sets and then perform read-modify-write operations
(e.g., adding a path to an existing route and then performing the best-path
computation), certain operations such as caching and pre-fetching have
limited benefits and latency remains the key concern.

In short, unless there's a significant change in the underlying technology
of the single DRAM cell, things aren't going to change significantly.

Regards,
Tony

---

From: Robin Whittle <[email-masked]>
Date: Thu, 01 Jan 2009 14:59:50 +1100

Short version:  Limits on using PC hardware for router FIBs.
                Fast SRAM is needed, not DRAM.

                                       DDR3 DRAM     QDR II+ SRAM

                Access time            13 nsec       0.5 nsec

                Cycle time            ~20? nsec      3.0 nsec

                Read/Write cycles     ~50?           333
                per microsecond

                (All in support of what Tony wrote about DFZ
                growth outpacing DRAM speed improvements.)

                Router RIBs with modern CPUs.
                Fundamental problems with too many prefixes.
                We need a solution to be fully deployed within
                about a decade.

Hi Christopher,

> or Geoff Huston have for approximations of the rates).

While a COTS PC costing $2k or less can have plenty of RAM for
holding a software based FIB, its packet forwarding capacity is
limited by:

1 - Physical interface speeds, including PCI bus speed.

2 - The CPU and memory bandwidth required to implement the packet
    input and output processing.

3 - The CPU and memory bandwidth required to classify each incoming
    packet.

The last point is a major bottleneck for any PC-based approach.  PC
DRAM (Dynamic RAM) has a long access time, but then pumps out a block
of data to fill the CPU's cache.  There are two clock cycles to clock
in the address, then the sense amps swing into action and data
becomes available 20 to 40 nsec later.  Then the sense amps need to
recharge their reference capacitors before the array can be read
again.  (My understanding, which may be out of date, is that DRAM
sense amps compare a fully charged half-size capacitor with the
capacitance of a memory cell, which is a full-sized capacitor either
fully charged or not charged at all.)

Bill referred to higher data rates for DRAM: "400mhz to I think
1600mhz today".  That is the rate at which it pumps out the data
after the initial delays of multiplexing in the address and waiting
for the sense amps to settle.

I will look for a recent DRAM spec sheet:

DDR3 DRAM 800 to 1600 Mbps per pin (!):

http://www.samsung.com/global/business/semiconductor/products/dram/Products_DDR3SDRAM.html

http://www.samsung.com/global/business/semiconductor/support/brochures/downloads/memory/ddr3_datasheet_200807.pdf

"Latency time of only 13 nsec".  13 nsec is way too long.  This
series goes up to 4G bits per chip.

http://www.samsung.com/global/business/semiconductor/products/dram/downloads/ddr3_device_operation_timing_diagram_may_08.pdf

68 pages of timing diagrams.  These are complex beasts.  I don't have
time to decipher all this stuff.

Suffice to say that in an FIB, there needs to be multiple short reads
to various locations in RAM in order to process each packet.  (Except
for IPv4, by doing a single lookup into a 16M word memory, assuming
/24 prefix length limits for most packets.)

For longer IPv6 addresses, the FIB needs to chew its way through the
bits until it arrives at the FIB entry with the Forwarding
Equivalence Class, which is primarily which interface the packet
should be forwarded on, plus which output queue of that interface to
put the packet into.

The delay time in getting those bytes from RAM is crucial.  It
doesn't help that these SDRAMs, which are made for filling CPU
caches, can pump out further data at some extraordinarily high speed.

The best type of RAM would be QDR II+ fast SRAM:
 http://www.samsung.com/global/business/semiconductor/products/sram/Products_HighSpeedSRAM.html

These go up to 72M bit per chip.  The access time (address in to data
out) is as low as 0.5 nsec (26 times faster than the 13nsec noted
above for SDRAM) and the cycle time is 3nsec, since they can do 333M
reads or writes per usec.  SDRAM could probably only do 50 such
cycles per usec.

To some extent, CPU caching might help with an FIB function, by
already having the data needed for packets with the same destination
address as one recently processed.   However, CPU caches can only
hold a limited number of blocks of data.  In a busy router, there
will surely be a greater diversity of destination addresses than
could ever be handled with cached data in the CPU.

I am thinking mainly about IPv6 addresses.  If it is purely IPv4,
with /24 length limits, then an FIB is pretty easy to implement in
specialised hardware with 16M words of fast static RAM, with a single
read cycle (333 a usec).

Generally, it is onerous and slow to have to do multiple RAM lookups
in PC DRAM, as is required to navigate the FIB data in order to
process a single packet.

What is needed is very fast Static RAM: apply the address and then
get the data a few nanoseconds later.  There is no recovery time,
since the sense amps have no capacitors.

SRAM cells involve 6 transistors and are correspondingly less dense
per chip, more expensive and more power hungry than DRAM.  They also
have more pins per chip, since the address is presented in parallel.

I am not sure how practical it would be to string a bunch of PCs or
the like in parallel to form a higher capacity router.  To some
extent a PC could split up the incoming packets to multiple FIB PCs,
and combine their outputs, one such PC for every link to a neighbour.
 However, that would mean half a dozen or dozens of PCs all strung
together in a fragile arrangement.

Except for low data rates, I think DFZ routers are always going to be
"big-iron" (high reliability, not based on consumer electronics - and
priced like mainframe computers) devices.  For the highest data
rates, there will always need to be FIB heroics such as Cisco's
USD$80k MSC board for the CRS-1:

  http://www.firstpr.com.au/ip/sram-ip-forwarding/router-fib/

The FIB of the MSC board is based on a single ASIC with 188 32 bit
CPUs (250MHz), somehow sharing a large amount of (I assume) fast
SRAM, to implement the Tree-Bitmap algorithm.  It dissipates as much
as 375 watts and handles 40Gbps, full duplex.

Implementing large ACLs in software, such as in a PC-based router, is
probably going to be prohibitively slow.  The CRS-1 MSC board uses
TCAM for that.

I guess it would be possible to build a very high performance RIB
with modern PC technology: 4 and 8 core 64 bit CPUs from Intel and
AMD, with 32 gigs etc. of ECC DRAM.  This could probably be done in a
COTS PC, or in a suitably redesigned "big-iron" router.

Maybe a high capacity RIB (for 100 million prefixes and a dozen or
more neighbours) could be done with multiple CPU-RAM systems sharing
the load, but this sounds like a nightmare.

Even with an RIB of arbitrary capacity and great speed, ramping up
the number of prefixes to 10 million, 100 million or whatever becomes
objectionable since even if all DFZ routers could cope with these
numbers of prefixes, the flurry of BGP messages during an outage
would become a problem.  Any one outage is likely to affect some
proportion of the total number of prefixes, and if we have 1000 times
more prefixes, such as 250 million, this is 1000 times more BGP
messages per outage than today.  Surely the delays inherent in
sending and processing these bursts of messages will lead to slower
convergence times and greater chance of instabilities.

Maybe this won't be such a problem with faster links between routers,
but the whole idea of simply throwing expensive hardware at the
problem, for every DFZ router, in order to accommodate the required
number of multihomed end-user networks (100 million, a billion ..?)
ugly and unscalable.

So we need to add a new architectural element to the Net.

My guess is we need to get this fully operational by 2016 to 2018 or
so, which means finalising the design and making it available by 2015
or so - and by making it so attractive to end-user networks, ISPs and
the companies who will run the mapping distribution system, OITRDs
etc. that it will be rapidly adopted by the end of the next decade.

  - Robin              http://www.firstpr.com.au/ip/ivip/