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/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.
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
_______________________________________________
GROW mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/grow
