Internet inter-domain routing performs the critical function of gluing together individual networks to create the global packet delivery infrastructure. Despite its importance, current measurements and analysis have not yet led to a basic understanding of its topology evolution, routing dynamics, and stability under stress. In this talk, I will present my recent work on topology discovery and routing stability at inter-domain level.
The Internet topology graph is a key element in protocol evaluation and understanding the structure of the Internet. Conventionally it is derived from a snapshot of routing tables, which only reflects the best routing paths at a time. I will present a new method that takes into account routing updates to discover backup links over time. It not only provides a much more complete topology, but also reveals interesting topology dynamics (birth and death) and long-term growth trends.
With increasingly denser topology and more malicious attacks, the inter-domain routing is expected to withstand unusual surges of routing updates and minimize the damage to global Internet. The current system relies on a mechanism called "route flap damping" to limit the global impact of local instabilities. This talk will show how damping can result in unexpected long convergence time due to previously unknown timer interactions among routers. I propose a solution using explicit notification of a routing update's root cause. Simulations show that it eliminates the negative effects of unintended interactions, and restores the original benefit damping was designed for.