Why Origin Validation Can't Help DRAGON Routing

Lachlan Kang <lachlan.kang@student.adelaide.edu.au>, Cristel Pelsser <cristel@iij.ad.jp>, Randy Bush <randy@psg.com>
2015.07.05

DRAGON Routing

Ever increasing BGP routing table size is a well-known issue, driving router costs upward and draining operators' pocketbooks.

DRAGON: Distributed Route Aggregation on the GlObal Network [0] "is a distributed route aggregation technique which works with the current Internet routing system (BGP). It scales the Internet by filtering redundant routing information, reducing routing and forwarding table size by up to 80%." It "is backed up by a strong theory and - when fully deployed - does not have any impact on forwarding paths for a broad class of routing policies."

DRAGON uses two techniques for FIB reduction. The first is suppression of prefixes for which there is a covering prefix. The paper presents safe algorithms for doing this. As 50% of the routing table is known to be deaggregated noise [1], this is a good strategy. It is worth noting that there have been tickets in CTAC and JTAC for many years along this vein. As this part of DRAGON does not alter AS-Paths, origins, etc., it does not interact with RPKI-based Origin Validation [2].

The second part of DRAGON allows a node to aggregate received prefixes. As the result is a new prefix with a new origin, this has serious interaction with RPKI-based Origin Validation.

We really liked DRAGON and had hope that we could hack a way to make it work with RPKI-based Origin Validation. But ...

Why DRAGON Aggregation Won't Work with Origin Validation

If DRAGON aggregated only prefixes with a common origin, one could consider schemes where the owner of the prefixes to be aggregated could create a ROA for the aggregate and authorize the aggregating AS to announce the aggregate.

But even this has problems. If the owner is willing to authorize a remote AS to aggregate its prefixes, why would the owner not just aggregate them itself? And how would the AS which wishes to aggregate signal the owning AS that it wants a ROA? And how many ASs in the Internet would be making such requests? And how would the owner feel assured that these requests were not 'mistakes', exactly what Origin Validation is meant to ameliorate?

Additionally, in DRAGON, if you filter prefixes, it must take the result of route origin validation into consideration in the quality of the route. If you do not do it then a less specific that is NotFound or Invalid may be the only route received by some AS while the origin of the more specific advertises a Valid route.

A further complication arises if the owner received the two (or more) prefixes from disparate ancestors, e.g. multiple upstream ISPs or multiple RIRs. In this case, the prefixes would descend from separate validation chains, meaning mean that the resulting aggregated ROA would have to be multiply signed; and multiple signatures are not supported on the EE cert to create a ROA. We considered exploring multiple signatures, but ...

Even worse, re-reading the paper we found that DRAGON does not require a common origin for aggregation. Therefore multiple owning ASs would have to be signaled and acquiesce. At this point, the story has become pretty far fetched and not realistic.

In the extreme, unsigned origination of aggregates is not a road we would suggest. Why would an AS not advertise 0/0? If every AS does that, forwarding may still work but an AS would not know which ASs are used to forward its traffic. Some ASs filter routes because they do not want to send traffic to some ISPs. This would not be possible anymore.

Sigh

So, with regret, we have dropped this line of research.


[0] - João Luís Sobrinho, Laurent Vanbever, Franck Le, and Jennifer Rexford Distributed Route Aggregation on the Global Network, ACM CoNEXT 2014, Sydney, Australia, Dec 2014.
[1] - Luca Cittadini, Wolfgang Mühlbauer, Steve Uhlig, Randy Bush, Pierre Francois, and Olaf Maennel, Evolution of Internet Address Space Deaggregation: Myths and Reality, in IEEE Journal on Selected Areas in Communications, Vol. 28, No. 8, October 2010.
[2] - P. Mohapatra, J. Scudder, D. Ward, R. Bush, and R. Austein, RFC6811 BGP Prefix Origin Validation.