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

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

Hi Folks,

Iljitsch's current geoagg plan didn't pan out either, but it gave me
an idea. Your comments are requested.


Suppose when we calculate the FIB from the RIB, we do the following
optimization:


1. Determine which exit has the most routes pointing at it.
2. Add 0.0.0.0/0 pointing at that exit.
3. Mark the routes that point in that direction and aren't cutouts of
a larger route as non-FIB. These won't be imported into the FIB.
4. Mark the rest of the routes for import into the FIB.

5. Look at the routes in the two /1's inside that /0, considering both
the marked and unmarked ones. Do any of the /1's have the majority of
the routes pointing towards a different exit than the /0? If so, add
the /1 and change the markings on the subroutes accordingly.
6. If both /1's point a different direction than the /0, remove the /0.

7. Inside each /1, repeat steps 5 and 6 using /2's.
8. Repeat for /3, /4, ... /8


In theory, this should result in identical routing for all routes
which are actually in the RIB while cutting the FIB size
significantly. In the worst case you should see FIB reduction equal to
1/(number of BGP interfaces) of the RIB table. Near the edge you
should normally get much more.

The obvious weakness of this approach is that packets which would
ordinarily generate a host-unreachable will instead tend to fall into
an odd routing loop until the TTL expires. Other than that, would it
work?


Comments? Criticism? Further thoughts? It is Monday morning and I
haven't thoroughly vetted the idea so it may be DOA.

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