Paths Limit for Multiple Paths in BGP

[Maria Matejka]

>> After reading the draft, I understand that the actual algorithm on how
>> to choose the set of paths to be sent, is outside the scope of the
>> document. I consider this a major problem which may lead to hard-to-fix
>> long-term traffic loops between differing implementations.
>
>That mostly depends on usage pattern, and if the set of announced paths
>contains the best path, then routing loops would be transient, like
>if you send just one path.

… until the best path gets discarded by a filter on the receiving side, and then the result is completely random.

>> There are thoughts on actually implementing this in BIRD. 
>> Regarding the current development priorities, this is expected to be
>> implemented (if it actually happens) in BIRD 3 only, and only after we
>> implement some more structural changes in the route storage. Otherwise,
>> this is going to be a performance nightmare.
>
>Well, it is not really much different from 'secondary' option - have some
>ordering of available paths, announce the first N paths vs. announce the
>first path that pass filters.

There is already a performance problem if the total number of paths is too big, as reloading one single path has avg linear cache misses in the number of other paths for that prefix just to find the old record. And adding R paths for one prefix to the sorted table is now avg O(R²) in comparisons.

With exports, let's consider the best route flap slowly. This induces one withdraw, one update from the tail in O(R) cache misses, and then one update (the best one being added) and one withdraw from the tail, again with O(R) cache misses.

If, instead of a flap, ROA status changes and all the export filters have to be recalculated, we are in the quadratic orders again.

I'm not saying it's impossible, i'm concerned about implementing this in v2, and would prefer an efficient implementation for v3 later.

Maria


-- 
Maria Matejka (she/her) | BIRD Team Leader | CZ.NIC, z.s.p.o.