Route aggregation in BIRD - how?

[Jérôme Nicolle]

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

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/

iEYEARECAAYFAlAsyB8ACgkQbt+nwQamihvMVACgj1RcbrjPh74XoNYBGLJhPKbd
RbkAoIep00fWGJzFBM0DGQWrVJB1aTq5
=bPKd
-----END PGP SIGNATURE-----