Re: [RRG] Opportunistic Topological Aggregation in the RIB->FIB Calculation?

["William Herrin" <bill@herrin.us>]

On Tue, Jul 22, 2008 at 5:35 PM, K. Sriram <ksriram@nist.gov> wrote:
> At 02:32 PM 7/22/2008, William Herrin wrote:
>> I haven't crunched any numbers but my guesstimate is that towards the
>> edge you'd get compression down to a few thousand FIB entries while
>> deep in the core you'd get 25% to 50% compression and in the worst
>> case you'd get 1/X compression where X is the number of BGP interfaces
>> on the router.
>
> Do you have some data available regarding distribution of prefixes
> that exit using the same BGP interface? Just looking for some
> empirical support for your guesstimate of 25% to 50% compression
> in the core.

No data. Like I said: purely a SWAG. This is in the "float the idea
and listen to the response" stage.


> X can be quite large for core BGP routers -- 100s of peers or BGP
> interfaces.

What scenario? Peering fabric at Equinix Ashburn kind of thing? What's
the guesstimate on the number of routers in service with >= 100 active
BGP sessions to peers? 20? 200? 2000?


> In that case, the worst case of 1/X would be negligible compression.

The worst case construct comes in to play where you have, let's say
100 BGP sessions and 200,000 routes.  Give each session the best path
for exactly 2000 routes. No more than 10 routes in each session are
from the same /8. In this worst-case scenario, the FIB loses 2000 long
prefixes in exchange for adding about 500 short ones.

Obviously the RIB doesn't look that way. Ever. Instead, you have two
dozen best-path routes from this peer and twenty thousand from that
peer, and subdivisions of the /8's for the various RIRs tend to
cluster with peers who have better connectivity to those regions.


> The other fundamental question would be: Even if it 25% compression,
> given that the total number of FIB entries are projected to increase
> four fold over what we have today (from ~250K to ~1 million or so),
> we would still be seeing an increase (post 25% compression)
> from ~188K to ~750K (assuming that the FIB increases are proportional
> for all BGP interfaces or exits).

That's a fair criticism. But let's flip it around: If 100k of the 150k
BGP routers get a compression ratio bettern than 10:1, 40k get less
than that and 10k get no better than 1.3:1, have we not at least
reduced the scope of the problem? If FIB compression allows 2/3rds of
the BGP routers to keep using 6500 Sup2's even when the RIB passes 2M
entries, is that not at least as significant a cost impact as the
introduction of MPLS these many years past?

Regards,
Bill

-- 
William D. Herrin ................ herrin@dirtside.com bill@herrin.us
3005 Crane Dr. ...................... Web: <http://bill.herrin.us/>
Falls Church, VA 22042-3004

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