Folks,
It looks to me as though your level 4A FIB aggregation algorithm has a
bug... at least if you agree that "may create forwarding loops" is a
bug. Two routers aggregating across holes can end up in a forwarding
loop. Here's an example. Consider this network, with X and A in one
AS and B and Y in another:
X --- A --- B --- Y
Router A receives the following routes:
- From X, 10.32/11 and 10.192/11
- From B, 10.0/11 and 10.224/11
Using algorithm 4A, it creates the aggregate 10/8 with nexthop B
(randomly chosen)
Router B receives the following routes:
- From A, 10.32/11 and 10.192/11
- From Y, 10.0/11 and 10.224/11
- Using algorithm 4A, it creates the aggregate 10/8 with nexthop A
(randomly chosen)
Packets to 10/8 other than the listed prefixes will loop (e.g. to
10.64.1.1). Of course, they have to reach A or B first but it's not
difficult to imagine a scenario in which they could.
This problem arises from the case where you randomly pick a next hop.
If two adjacent routers do this, they may end up picking each other.
I haven't worked this through for the 4B algorithm, but considering
that it has a similar random selection step, I would guess the same
problem could arise.
This leads me to reflect that my biggest concern with the draft as it
stands is that the correctness condition as stated ("after longest
match lookup, if a destination address has a non-NULL next-hop in the
un-aggregated FIB, it should have the same next-hop in the aggregated
FIB") is a tad questionable. IMO the base correctness condition is
"has black-box identical behavior to a router not using FIB
compression", which is stronger than what's stated. You'd need to
drop the "has a non-NULL next-hop" caveat. This seems to be what your
Level 1 and 2 algorithms provide (or anyway, are intended to
provide). I think you need to state clearly what the correctness
conditions are for the other levels. (And given a clear statement of
the correctness conditions, proof of correctness would be very
desirable!)
Regards,
--John
_______________________________________________
GROW mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/grow
