DRAGON: Distributed Route Aggregation on the GlObal Network

DRAGON 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%.

DRAGON 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 won an IRTF Applied Networking Research Prize!

The Applied Networking Research Prize (ANRP) is awarded each year for recent results in applied networking research that are relevant for transitioning into shipping Internet products and related standardization efforts.

You can find more information about the award here and the video of the presentation below.

Read the papers Look at the presentations Get the code

Today's interdomain routing does not scale

Today's interdomain routing protocol (BGP) mandates all routers in the Internet to maintain detailed reachability information about all Internet destinations (IP prefixes), putting a lot of stress on the routing and forwarding infrastructure. Recently, the number of Internet destinations surpassed 512,000 which caused many routers to crash, creating Internet-wide instabilities. Like the Year 2000 problem, this event has been heavily covered in the press, see [1], [2] or [3].

Exchanging detailed information about every destination is not necessary as a lot of it is redundant. A good analogy can be found in road networks. Every city does not have (nor does it need) a directional signpost to every other city in the world. Instead, signposts give detailed information about nearby destination and coarse-grained information about far away destinations. Unfortunately, implementing such a system in the Internet is impossible as it is not centrally managed. In particular, figuring out which destination can be filtered out at one location without creating problems elsewhere is known to be hard...until DRAGON.


Filtering, preserving correctness and optimality

DRAGON operates hands-in-hands with BGP. It enables each router to locally compute which IP prefixes can be filtered out without impacting any end-to-end route used to forward data packets under full deployment. In particular, DRAGON filtering primitives enable each router to filter routing information pertaining to longer IP prefixes (e.g., 10.0.0.0/24) and rely on a shorter IP prefixes instead (e.g., 10.0.0.0/16). When a router filters an IP prefix, it removes it from its forwarding table and stops advertising to any neighbor. Doing so, DRAGON reduces both the space required to store the Internet routing table (i.e., the forwarding table size) as well as the time it takes to exchange those information (i.e., the convergence time).

Under the hood, DRAGON is backed up by a strong theoritical framework: algebraic routing, which provably guarantees the absence of routing and forwarding problems.

DRAGON massively reduces routing and forwarding table size

DRAGON enables 80% of the Internet to filter 50% of their forwarding and routing table without changing anything to Internet routing. DRAGON's filtering efficiency is limited to 50% as roughly 50% of the Internet IP prefixes are not covered by a shorter IP prefixes and therefore cannot be filtered. These prefixes are sometimes referred to as Provider Independent (PI) prefixes.

DRAGON promotes the announcement of a few aggregation prefixes to allow filtering of many of the PI prefixes. Each node autonomously determines which aggregation prefixes it can originate, if any. With aggregation prefixes, DRAGON enables close to 80% of the Internet to filter 80% of the forwarding and routing table.

DRAGON speeds up routing convergence

Since DRAGON maintains information about much less destinations than BGP, it also converges much faster.

As an illustration, DRAGON does not generate any messages for 40% of Internet link failures. In contrast, BGP generates messages for more than 98% of them. Moreoever, DRAGON exchanges less routes than BGP in 95% of the cases and less than half those exchanged with BGP in more than 50% of the cases.

Frequently Asked Questions

About the paper

What is isotonicity?

Isotonicity means that if a node prefers one route over another, a neighbor of that node does not have the opposite preference after its local processing of the two routes. Isotonicity enables optimal filtering. Indeed, with isotone routing policies, DRAGON provably attains, in full deployment, an optimal aggregated state that preserves the properties of the paths traversed by data-packets on their way to the destinations.

How does DRAGON behave when routing policies are not isotone?

DRAGON requires isotonicity for optimality, not for correctness. Even with non-isotone routing policies, DRAGON can filter redundant information and still prevents forwarding loops, blackholes, and routing oscillations from happening. DRAGON is indeed guaranted to be correct for any routing policies that ensure the correct operation of BGP.

When non-isotone policies are found in the Internet, some forwarding paths can see some stretch with respect to the paths obtained prior to filtering. However, our preliminary results indicate that this stretch is small.

Does DRAGON work at a per-router level? All the examples of your paper consider abstract entire ASs as single nodes.

Yes! DRAGON can be applied at the router-level to reason about which border routers can filter which prefixes. Also, the concept of consistency and correctness naturally extend to the router-level.

How is DRAGON different from all the previous work about FIB aggregation?

A lot of research has been done in order to compress forwarding tables by aggregating related entries. From the point of view of reducing forwarding table size, these optimizations achieve roughly the same performance as DRAGON. However, unlike DRAGON, they are purely local, do not reduce the size of the routing tables, nor do they reduce the number of BGP messages exchanged (i.e., the convergence time). Another difference lies in how DRAGON and previous work deal with routing changes (see next question).

How does DRAGON deal with routing updates?

DRAGON naturally applies to routing updates as it targets both the forwarding and the routing-plane. Indeed, unlike other proposals, DRAGON does not suffer from mismatch between the forwarding-plane and the routing-plane during convergence event. Upon a routing change, a router simply re-run the DRAGON filtering rules and changes its decision accordingly.

About DRAGON in general

Do I need new routers to run DRAGON?

No. DRAGON only requires a software update and would work on even relatively old router. With respect to normal BGP routers, DRAGON routers require a few more operations, namely the ability to compare routes for different prefixes and changes to the BGP state machine.

What about partial deployment?

DRAGON does not require a flag day and can be deployed progressively. Moreoever, with isotone routing policies (see question above), it is always possible to order the adoption of DRAGON so that all forwarding paths are preserved at all stages of deployment. Interestingly, participation by all nodes is a Nash equilibrium in which no node has an unilateral incentive to not deploy DRAGON.

Does DRAGON apply to anything else than BGP?

Yes! The filtering principles at the core of DRAGON are valid for any prefix-based routing system substantiated on a vector-protocol, including intra-domain routing protocol.

Can I try DRAGON in my network?

We are working on implementing DRAGON directly on routers. In the meantime, why don't you give DRAGON a try using our simulator available on Github?

Publications

Distributed Route Aggregation on the Global Network, ACM CoNEXT 2014, Sydney, Australia, Dec 2014. (bibtex)

by João Luís Sobrinho, Laurent Vanbever, Franck Le and Jennifer Rexford

A Fresh Look at Inter-Domain Route Aggregation, IEEE INFOCOM 2012 mini-conference, Orlando, Florida, March 2012. (bibtex)

by João Luís Sobrinho and Franck Le

Presentations

IETF 93/IRTF presentation (July 2015)

by João Luís Sobrinho

ACM CoNEXT 2014 presentation (December 2014)

by João Luís Sobrinho

ETH Zürich Networking Symposium presentation (March 2014)

by Laurent Vanbever

People

Webmaster: Laurent Vanbever, 2014