Route aggregation in BIRD - how?

[Ondrej Zajicek]

On Wed, Jan 16, 2013 at 03:50:00PM +0400, Alexander V. Chernikov wrote:
> > (2) If i understand it correctly, your aggregator keeps a copy of all
> > received and aggregated routes in an internal fib, which is useful for
> Actually, not all: only routes which are more-specific for any summary
> or mandatory ones.

Yes, that is why i wrote 'received and aggregated' and not just 'received'.

> > implementing (1), but unnecessarily if you just want to originate an
> > aggregate route if there are some matching routes (or required number of
> > mandatory routes). In that case you just need some counters for summary
> > routes and flags for mandatory routes. Current implementation is especially
> > memory wasteful in the common case 'aggregate full BGP feed to get a default
> > route'.
> Well, aggregating default without any filters is a quick and wrong way
> of generating summary since
> 1) you have at least aggregate RTS_BGP routes only

I thought about aggregating just routes from one BGP feed/uplink.

> 2) If ISP fails probably either session goes down or full-view
> disappears leaving _some_ (IX or provider-own) routes.
> 3) Additionally, sometimes ISP can loose transit to foreign countries
> leaving national routes intact
> 
> So I assume someone to configure filter with several stable prefixes
> (most valuable from user point of view) while doing default aggregation.

In that case it is not so wasteful, but i think that something like
'import all from that uplink, check whether there are at least 100000 routes'
is probably simpler and better.

> In this case, memory usage is not so wasteful. Additionally, copying
> attributes increments their refcount for the most cases (or am I wrong?).

You are right, but for routing tables, attributes consume about half of
used memory, fib nodes and struct rte's is the other half.

> We probably can consider implementing additional something like 'min
> count XXX' summary route attribute to ease aggregating default route.

Yes.

> > If you do not have strong objections, i would remove (1), do some
> > readjustment for (2), fix some minor issues and merge it. Question is
> > whether there is any need to have optional keeping a copy of child
> > routes in (2) for some sophisticated aggregation modes like (1), but
> > without (1), i currently don't see the need.
> The only thing I see is generic FV compression to fit in small FIB, but
> this requires additional amount of work to be done, so I'm not against
> removing.

I think that for FIB compression completely different data structures
and algorithms would be needed, which is probably best handled by
completely different protocol implementation.

> Btw, I can do (1), (2) and implement this 'min count' stuff to further
> move to the review-based approach instead of you constantly fixing my
> mistakes yourself :)

OK. I just feel that some of these issues aren't real mistakes, but more
like me forcing my point of view, but if you doing it OK with you, it is
OK with me.

I have these suggestions/requests:

1) Do not keep copies of child routes, just several counters for a summary
route, updated on rt_notify().

2) Perhaps completely remove fib. Mandatory routes could be kept
in trie, which also allows some more sophisticated mandatory route
matching, like any route for 1.2.3.4/32. As tries have little
overhead, perhaps it could be a separate trie just for mandatory routes
for each aggregate route, that would probaly significantly simplify it.

3) There is no need for nested blocks in aggregator configuration.
thinks like AS and IP for BGP aggregation could be global protocol
options. If someone needs several different kinds of aggregation,
it is natural to just use separate aggregator protocols (which would
be usually already necessary because of different import filters).

4) There are some tricky parts in aggregator reconfiguration.
Configure soft with reload is probably currently unsafe w.r.t.
proper value of 'old' route and could cause counters to be
unsynchronized. Protocol restart is mostly OK, but would cause
unnecessary route flaps. Perhaps some kind of hybrid which resets
internal state before feed like restart, but gracefully
updates generated routes. Something like 'reconfiguration
by hidden restart and refeed', it is natural if most of your
inner state is already stored in tries allocated from config LP.

5) There would be two variants of aggregation, plain and BGP. The
difference is probably just in summary route attributes. Plain
aggregation generates routes with no optional attributes, BGP-style
aggregation generates routes with some BGP attributes (probably
BGP_ORIGIN, empty BGP_PATH, BGP_AGGREGATOR and possibly
BGP_ATOMIC_AGGR). BGP_ORIGIN should obviously depend on aggregated
routes, BGO_ATOMIC_AGGR should be here if at least one aggregated
route has non-zero BGP_PATH. This could be also handled by some
counters for separate classes of aggregated routes (IGP, unknown,
BGP, BGP with non-zero BGP_PATH).

6) Specifying ASN would be needed just for BGP variant. Specifying
IP for BGP_AGGREGATOR is probably unnecessary, could be based on router
ID.

7) As the BGP variant (and possible other future variants) depends on
aggregator data structures, it should be implemented in aggregator code,
not as a protocol callback, *_sumroute callbacks would be removed.

8) Note that there is a problem in bgp_import_control() that calls
bgp_create_attrs() for non-BGP routes, which overwrites BGP attributes
if they are already present. This could be considered a bug, we
should use current attributes if available.

9) It is question whether unreachable routes should be ignored. It makes
sense for BGP routes with unreachable nexthop, but not much for other kinds
of unreachable routes. I feel that perhaps current recursive route
behavior should be changed in a way that routes with unreachable nexthop
would be generaly more ignored, but that is not related to aggregator
issue.

10) Change 'aggregate address' to 'route'. It is shorter and it is essentially
a kind of triggered static route. Not to mention it is not address but prefix.

11) *_mroute symbols should be more like mand_route, _mroute symbols suggest
multicast routes

12) Perhaps change prefix (and filenames) from agg_ to aggr_ ?
Not important, bug aggr_ seems to me like much more fitting.

13) Name in struct protocol should be "Aggregator", like "Static" or "Kernel".

14) There are some remnants of 'summary only' in config.h and agg.h

This is probably all i recall now.

-- 
Elen sila lumenn' omentielvo

Ondrej 'SanTiago' Zajicek (email: santiago at crfreenet.org)
OpenPGP encrypted e-mails preferred (KeyID 0x11DEADC3, wwwkeys.pgp.net)
"To err is human -- to blame it on a computer is even more so."
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 197 bytes
Desc: Digital signature
URL: <http://trubka.network.cz/pipermail/bird-users/attachments/20130116/5dcc5c0c/attachment-0001.asc>