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

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

On Tue, Jul 22, 2008 at 12:32 PM, Lixia Zhang <lixia@cs.ucla.edu> wrote:
> if I got it right, the above description sounds like a special case of the
> more general "virtual aggregation" scheme by Paul Francis.

Hi Lixia,

No, Paul is on to a very different idea. His idea is: partition the
BGP FIB among multiple routers and then use a few short routes plus
MPLS to move the packet to the router which has the of the FIB for
that destination. I like Paul's idea but I'm chasing a different
track.


> in terms of drawbacks: in addition to what you mentioned above, virtual
> aggregation in general can lead to longer paths (trading path lengths for
> FIB size reduction; in the above, this can happen at step 5).

No, I'm going a different way. *IF* I'm right, the approach I describe
has the property that for all routes actually in the RIB, a FIB lookup
still chooses exactly the same exit that it would if all the RIB
routes were entered into the FIB individually.

Right now routers have an implied default route to the "host
unreachable" virtual interface.  Routes not otherwise expressed in the
FIB are directed to "host unreachable" which generates an ICMP message
back to the source.

What I'm saying is: ditch the implied default route. Instead, treat
unrouted space as "don't care" destinations which may be sent in any
direction. They'll eventually die from TTL expired, and except for the
wasted resources we mostly don't care where they go.

Then, rebuild the FIB based on the assumption that you're going to
compress the RIB entries with the most common exit plus all of the
"don't cares" into a single default route and enter that into the FIB.
All the rest of the RIB routes that point to some other exit will be
cutout routes in the FIB which poke holes in the default and send
their packets in a different direction.

Finally, do that recursively at the /1, /2, ... /8 levels.


This approach should have the property that for all routes actually in
the RIB, a FIB lookup still chooses exactly the same exit that it
would if all the RIB routes were entered into the FIB individually.

The sacrifice is that all routes NOT in the FIB get sent somewhere
too, instead of generating a host unreachable. In fact, if the router
actually has a default route in the RIB, this compression probably
won't work.


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.

Regards,
Bill Herrin

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