On Nov 20, 2009, at 11:23 AM, John G. Scudder wrote:
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/11Using 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.
John,Thanks for the comments. Xiaohu Xu also expressed similar concerns regarding possible loops.
The forwarding loop is only possible to level-4 aggregation and only to prefixes that are not in the original routing table, i.e., extra routable space. We were aware of the possibility but didn't elaborate it in the draft. Our initial thoughts were that (1) Since it only happens to prefixes not in the RIB, in normal operational conditions, the volume of traffic should be negligible; (2) For an attacker to exploit this, he has to be able to direct traffic of unreachable prefixes to a router that happens to have a loop for that prefix. Since different routers aggregate differently, it is probably very difficult for a remote attacker to achieve this. Likely the attack traffic will be dropped before reaching the target router or use the wrong target prefix.
Now we're also looking into ways to mitigate this problem. For example, add null next-hop to some extra routable space to reduce the size of the extra space without sacrificing too much on aggregation ratio; or don't run level-4 aggregation on a router when a neighbor router has a default route to it (since default route can bring in traffic of unreachable prefixes).
Such a loop may happen even when the next hop is not randomly picked. In your example topology, suppose X announces 3 prefixes and Y announces 2 prefixes, then traffic of unreachable prefixes will flow in the direction of ->B->A->X and no loop. However, if at router X, its 3 prefixes actually each takes a different next-hop to the left, then the unreachable prefixes will be aggregated with the 2 prefixes announced by Y and loop back to A.
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!)
You're right. Basically level 3 and 4 relax the black-box forwarding correctness requirement for unreachable prefixes. The difference between 3 and 4 is that level 3 doesn't have potential loops for the unreachable prefixes. We'll address this in the revision of the draft.
A major reason we classify aggregation into different levels is for operators to be aware of the tradeoff involved in each level and pick the level of aggregation that they're comfortable with for their networks.
--- beichuan
Regards, --John