Route aggregation in BIRD - how?

[Jérôme Nicolle]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

By the way, if anyone can help me to implement this (meaning writing
code while I do the testing and debugging), my usual broker (Alturna)
offered me a free test chassis to actually run the agregation process
and see how a SUP32 or SUP720 reacts in real world.

I have 2 to 4 possible transit upstreams to test with in my area, so
basically we have every costy ressources at our disposal, I just
really need a talented developper to finally create a functionnal
route agregator.

Anyone ?

Le 16/08/2012 12:14, Jérôme Nicolle a écrit :
> Le 16/08/2012 09:40, Alexander V. Chernikov a écrit :
>> For 32k or less it seems that several static defaults for
>> outgoing traffic balancing is sufficient, since it is not
>> possible to do fine-grained route selection for all routes. 200k
>> is much more promising: 11:19 [0] bmw# birdc 'show route primary
>> where net.len < 24' | wc -l 198369
> 
> bird> show route count where net.len < 24 197699 of 416648 routes
> for 416648 networks
> 
> confirmed. More on that : 
> http://dedibox.nicolbolas.org/tmp/prefix-distribution.png
> 
> But I wouldn't count that much on prefix-lenght based agregation : 
> many /24s are stubs or PI space used to multi-home smaller
> networks.
> 
>> It is possible to fetch RIPE/APNIC/etc (or RADB) database on
>> route objects, filter more-specific route object, and build long 
>> Aggregator {} configuration with "save attributes" part. It will 
>> probably fit it less than, say, 150k and the rest can be used
>> for IGP and local IX tables. Some (how much?) of the aggregated
>> routes will have different paths resulting in origin AS being
>> hidden in AS_SET attribute. If this number is significant I can
>> improve AS_PATH merging algorithm to save originating AS if
>> possible.
> 
> I wouldn't count on route objects, many are outdated, if any. But 
> cross-checking them could be a nice security feature, appart from 
> aggregation purposes. Could be linked to a developpment targeted
> at full RPKI+ROA validator support in BIRD.
> 
>> However, 1) it needs testing to determine exact number 2) In 
>> future, IPv4 sub-blocks selling between ISPs (and non-ISPs) will 
>> decrease effectiveness of such approach.
> 
> You're right. But I consider it to be of minimal importance in 
> opposition to poorly managed ASes (AS6389 and AS28573 anyone ?)
> 
> On a purely algorithmic approach, I'd propose the following 
> strategies. Keep in mind this happens _after_ the best path
> selection process in BIRD.
> 
> 1) Strip prepending from AS_PATHs while copying routes in a B-tree
> 
> 2) When creating a child in the B-tree, if the more specific has
> the same AS_path (including Origin) than its parent, don't create
> it.
> 
> (note : when creating a child with no direct parent, you'd have to 
> create a virtual parent, hence marked as a non-existent route)
> 
> 3) if a virtual parent has both clildren with the same AS path,
> strip the children (don't get me wrong on that) and move their
> attributes to the virtual parent, making it a "real" route.
> 
> There you get a naturally aggregated B-tree representing all
> routes with a non-destructive FIB approach.
> 
> If the route count is still too high, you could do the following :
> 
> 4) Build a secondary tree (not binary) representing AS
> relationships, each node having a pointer to a list of pointer to
> routes known in the route B-Tree
> 
> 5) For "blacklisted ASes", meaning "known transit ASes with no
> special interest in their customer cone", strip AS paths to make
> routes originating from the listed AS and agregate the routes
> (hence the pointer to list of pointers : way faster than recursing
> the B-tree)
> 
> OR (if you don't want to handle a blacklist, or in addition to it)
> 
> 5bis) Shorten as_path to a maximum hop count, let's say 5 would be
> a reasonable default limit for a well-connected network, and do the
> same than 5). This strategy could be applied locally to large
> non-leaf nodes in the AS-tree (ASes with more than, let's say, a
> few hundreds of customer ASes) for maximum profit. On the contrary,
> it could also be used to force the agregation of ASes with smaller
> customer cone, considering them as marginal.
> 
> 5ter) Same strategy as 5 and 5bis could be applied based on
> AS-sets.
> 
> (at this point it's still not really destructive regarding to
> respect of the routing policy)
> 
> 6) Recursing the AS-tree will let you find ASes with the largest 
> route-pointer lists, hence ASes with the largest route count.
> Counting topmost entries in the B-tree will give you an approximate
> "potential aggregation factor" disregarding the next-hop. There you
> may take the step of overriding the next-hop to maximise agregation
> for that AS. This I consider destructive.
> 
> 7) Discrepency hunting : on a given route-B-tree branch, when two 
> "colors" (I first thought of it as colorizin the tree based on the 
> next-hop attribute) are highly dominant, and both AS groups (given
> the initial best path selection policy), are reachable through
> both "colors" (here again, read "next-hop"), then take the topmost
> node in the route-B-tree and split it in half, each half with one
> hardcoded color. Then mark them with private ASNs and write
> matching AS-sets to the log output for debugging and trafic
> statistics purpose.
> 
> Many other policies could be writtent, I think it'd be all about 
> try-and-errors regarding their aggregation efficiency.
> 
> About the data structures, I thought of a B-tree but it could be 
> quaternary too. The most important thing would be to implement a 
> copy-on-write approach to routes : the initial tree has to be
> built with pointers to the routes as stored in the initial table,
> it'd be faster and more conservative (memory-wise). When a
> modification happens to a route (attribute modification in the
> agregation process), you will have to copy the modified route to a
> ne memory space and rewrite the attribute
> 
> AS_paths attributes might be calculated from the AS-tree rather
> than stored in litteral form. I guess this could be faster than
> stripping prepending from the attribute string.
> 
> At this point, we don't seem to need any other attribute than
> prefix, next-hop and AS_path. Community, MED and extended
> attributes might as well be stripped in the modified instances of
> the routes. Those might be ignored as well, and maybe the size of
> the resulting tree could disqualify the copy-on-write approach due
> to its higher complexity in regard to a lower interest in saving
> memory.
> 
> 
> 
> 
> 

- -- 
Jérôme Nicolle
06 19 31 27 14
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAlAyVTYACgkQbt+nwQamihv1vQCfX2L283xGrzme8A9zv5pbFmid
/KEAnRoEQPfAe9puHDEURdumc1/Mu+y1
=7W0I
-----END PGP SIGNATURE-----