Get Off My Prefix! The Need for Dynamic, Gerontocratic Policies in Inter-domain Routing

Edmund L. Wong and Vitaly Shmatikov

Proceedings of the IEEE Dependable Systems and Networks (DSN) 2011.

View PDF or BibTeX.

Security, Networking

Inter-domain routing in today’s Internet is plagued by security and reliability issues (e.g., prefix hijacking), which are often caused by malicious or Byzantine misbehavior. We argue that route selection policies must move beyond static preferences that select routes on the basis of static attributes such as route length or which neighboring AS is advertising the route. We prove that route convergence in the presence of Byzantine misbehavior requires that the route selection metric include the dynamics of route updates as a primary component. We then describe a class of simple dynamic policies which consider the observed “ages” of routes. These gerontocratic policies can be combined with static preferences and implemented without major infrastructural changes. They guarantee convergence when adopted universally, without sacrificing most of the flexibility that autonomous systems enjoy in route selection. We empirically demonstrate that even if adopted unilaterally by a single autonomous system, gerontocratic policies yield significantly more stable routes, are more effective at avoiding prefix hijacks, and are as responsive to legitimate route changes as other policies.