-----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-----