Paths Limit for Multiple Paths in BGP
Hi, I hope this is the right place to ask for feature requests. Would you mind adding this [1]draft to your TODO (/ feature) list? I've heard some [2]people are already missing (= would benefit) this draft. Thanks! [1] - https://datatracker.ietf.org/doc/html/draft-abraitis-idr-addpath-paths-limit [2] - https://ripe88.ripe.net/wp-content/uploads/presentations/23-RIPE88-Community... -- Donatas
Hello Donatas! On Wed, Oct 02, 2024 at 02:29:40PM +0300, Donatas Abraitis wrote:
I hope this is the right place to ask for feature requests.
Yes, it is!
Would you mind adding this [1]draft to your TODO (/ feature) list?
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. With that, there should be _some_ definition of how to choose the paths to send, to avoid getting straightforward implementations sending "just some" N routes they find. One option is like this: - while `N > 0`: - run the standard best route selection algorithm - remove the selected route from the original set - if the selected route passes export filters: - put the selected route into the final set - `N -= 1` This can result in announcing up to N routes when 1 route gets updated, so one has to expect some funny behavior with this feature. But it is stable, can be reasonably tested, and it won't yield random funny network mess dependent on the order of announcement arrival. 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.
I've heard some [2]people are already missing (= would benefit) this draft.
Maybe the first suggestion for them is to reach out to us with the underlying problem which they are trying to solve, as there may be different solutions than implementing a not-well-defined feature. Thank you for your message, have a nice day! Maria -- Maria Matejka (she/her) | BIRD Team Leader | CZ.NIC, z.s.p.o.
With that, there should be *some* definition of how to choose the paths to send, to avoid getting straightforward implementations sending “just some” N routes they find.
Correct, technically (and correctly too) the best path algorithm should be looped as much as numbers of paths is negotiated (same is in FRRouting).
Otherwise, this is going to be a performance nightmare.
For sure this is slower, but the same stuff is already done by Cisco, FRRouting and/or Juniper where they have a knob to send an arbitrary number of paths (without this capability, decided by the sender (not by the receiver)). That's a trade-off between memory, CPU :) Thanks! On Wed, Oct 2, 2024 at 3:42 PM Maria Matejka <maria.matejka@nic.cz> wrote:
Hello Donatas!
On Wed, Oct 02, 2024 at 02:29:40PM +0300, Donatas Abraitis wrote:
I hope this is the right place to ask for feature requests.
Yes, it is!
Would you mind adding this [1]draft to your TODO (/ feature) list?
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.
With that, there should be *some* definition of how to choose the paths to send, to avoid getting straightforward implementations sending “just some” N routes they find. One option is like this:
- while N > 0: - run the standard best route selection algorithm - remove the selected route from the original set - if the selected route passes export filters: - put the selected route into the final set - N -= 1
This can result in announcing up to N routes when 1 route gets updated, so one has to expect some funny behavior with this feature. But it is stable, can be reasonably tested, and it won’t yield random funny network mess dependent on the order of announcement arrival.
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.
I’ve heard some [2]people are already missing (= would benefit) this draft.
Maybe the first suggestion for them is to reach out to us with the underlying problem which they are trying to solve, as there may be different solutions than implementing a not-well-defined feature.
Thank you for your message, have a nice day! Maria
– Maria Matejka (she/her) | BIRD Team Leader | CZ.NIC, z.s.p.o.
-- Donatas
On Wed, Oct 02, 2024 at 02:42:00PM +0200, Maria Matejka via Bird-users wrote:
Hello Donatas!
On Wed, Oct 02, 2024 at 02:29:40PM +0300, Donatas Abraitis wrote:
I hope this is the right place to ask for feature requests.
Yes, it is!
Would you mind adding this [1]draft to your TODO (/ feature) list?
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.
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. -- Elen sila lumenn' omentielvo Ondrej 'Santiago' Zajicek (email: santiago@crfreenet.org) "To err is human -- to blame it on a computer is even more so."
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.
Right. On Wed, Oct 2, 2024 at 4:27 PM Ondrej Zajicek <santiago@crfreenet.org> wrote:
On Wed, Oct 02, 2024 at 02:42:00PM +0200, Maria Matejka via Bird-users wrote:
Hello Donatas!
On Wed, Oct 02, 2024 at 02:29:40PM +0300, Donatas Abraitis wrote:
I hope this is the right place to ask for feature requests.
Yes, it is!
Would you mind adding this [1]draft to your TODO (/ feature) list?
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.
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.
-- Elen sila lumenn' omentielvo
Ondrej 'Santiago' Zajicek (email: santiago@crfreenet.org) "To err is human -- to blame it on a computer is even more so."
-- Donatas
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.
participants (3)
-
Donatas Abraitis -
Maria Matejka -
Ondrej Zajicek