On Tue, Jul 22, 2008 at 12:32 PM, Lixia Zhang <[EMAIL PROTECTED]> 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 ................ [EMAIL PROTECTED] [EMAIL PROTECTED] 3005 Crane Dr. ...................... Web: <http://bill.herrin.us/> Falls Church, VA 22042-3004 -- to unsubscribe send a message to [EMAIL PROTECTED] 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
