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

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

On Tue, Jul 22, 2008 at 11:20 PM, Xu Xiaohu <xuxh@huawei.com> wrote:
>> 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.
>
> Let me take an example, route 1.1.1.0/24 is pointed to interface A, while
> route 1.1.0.0/16 is pointed to interface B. if most routes are pointed to
> interface A, in your theory, those routes with interface A as exit
> interface, including route 1.1.1.0/24, will be replaced by 0.0.0.0/0 in the
> FIB. This will cause a wrong route for packets to 1.1.1.0/24. Is my
> understanding correct?

Nice try, but no. As I alluded to in an earlier message:

>> In fact, if the router actually has a default route in the RIB,
>> this compression probably won't work.

It won't work because as you rightly point out, this approach only
allows you to compress prefixes that don't overlap. If the router has
a real default route, prefixes that take some other exit can't be
compressed. This holds true at every level, not just /0.

So, in your example 1.1.1.0/24 can't be removed because it overlaps
1.1.0.0/16 and takes a different exit (A instead of B). On the other
hand, if you have 1.1.2.0/24 which takes exit B, that -can- be removed
without changing the results of a lookup. Unless you also have
1.1.0.0/20 pointing to exit A. Then you can remove 1.1.1.0/24 but not
1.1.2.0/24.

Detecting covering routes does add complexity to the algorithm, though
not a whole lot: one radix tree lookup for each entry examined. And no
I haven't attempted to work out the big-oh. I'm just floating an idea
here, looking for fatal flaws.

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