[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [RRG] Opportunistic Topological Aggregation in the RIB->FIB Calculation?
On Tue, Jul 22, 2008 at 12:32 PM, Lixia Zhang <email@example.com> wrote:
> if I got it right, the above description sounds like a special case of the
> more general "virtual aggregation" scheme by Paul Francis.
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
> 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
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.
William D. Herrin ................ firstname.lastname@example.org email@example.com
3005 Crane Dr. ...................... Web: <http://bill.herrin.us/>
Falls Church, VA 22042-3004
to unsubscribe send a message to firstname.lastname@example.org 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