By the way, if anyone can help me to implement this (meaning writing
and see how a SUP32 or SUP720 reacts in real world.
route agregator.
Post by Alexander V. ChernikovFor 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
http://dedibox.nicolbolas.org/tmp/prefix-distribution.png
many /24s are stubs or PI space used to multi-home smaller
networks.
Post by Alexander V. ChernikovIt 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.
Post by Alexander V. ChernikovHowever, 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.
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.
