Re: [RRG] Routers in DFZ: scaling & limits on routes

[Robin Whittle <rw@firstpr.com.au>]

Hi Peter,

You quoted something which I guess from the Cc: people was written
on another mailing list than the Routing Research Group:

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

Here is my understanding of some of the major burdens on the routers
and the BGP system and how they scale.  Hopefully someone with more
knowledge could comment on this.

Scaling is very approximately:

RIB size ~=     (Length of details carried by best path message)
              * (Number of advertised routes)
              * (Number of peers)


Total communication
and computing rate ~=    (Rate of changes to advertised routes)
                       * (Number of peers)


Convergence time ~~=  (Number of routers, or perhaps square root
                       of this number - or average number of hops
                       from one side of the Net to the other)
                    * (Processing time at each router)
                    * (Many other factors, MRAI timer etc.)


A very rough idea of the number of interfaces on BGP routers might
be gained from my analysis of iPlane data at the end of:

  http://psg.com/lists/rrg/2007/msg00253.html


Router CPUs vary in speed, but as far as I know, they are all 32 bit
CPUs.  This places an upper limit of 4 gigabytes on the RAM they
have available, which has to be used for many other purposes than
just handling BGP.  I recall someone writing that the data could be
split among multiple CPUs with their own RAM in a large router, but
this sounds like a nightmare in terms of processing speed and
writing software which works properly.

It is possible to imagine 64 bit CPUs and tens of gigabytes of RAM,
but I guess the bottleneck is the RAM speed and the ability of the
CPU to read and write it.  High capacity RAM, as far as I know,
takes about 40nsec to read or write random data, so the CPU speed is
not necessarily the limiting factor.

PC CPUs have on-chip cache which helps with their repetitive loops
and walking through arrays of data.  However I think the router's
handling of BGP would involve lots of random accesses to memory, so
cache wouldn't help as much.

Most of the time, I guess the update rate is so slow that the CPU
has no trouble keeping up.  The difficulty would arise when a nearby
or distant link or router goes down, and all the nearby routers send
new best-path messages for approximately as many prefixes were being
forwarded through the link or router which went down.  The further
away that is, I guess the lower the impact, unless it is a border
router, in which case the changes would tend to propagate across the
whole system.

So I don't think there is a certain number of prefixes in the global
BGP routing table at which the system stops working.

I guess it just gets worse in terms of convergence as slower routers
struggle with peak update loads, and more expensive to run as
smaller routers need to be replaced to either keep up with the
processing load or to have a large enough RIB and/or FIB to cope.


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



--
to unsubscribe send a message to rrg-request@psg.com 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