On Tue, Jul 22, 2008 at 11:20 PM, Xu Xiaohu <[EMAIL PROTECTED]> 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 ................ [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
