This award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5).
Various studies over the past decade have shown that network availability on the Internet is about 99%, which pales in comparison to other utility services such as power grids and telephone networks. The primary cause of network unavailability today is due to problems related to interdomain routing that are unlikely to go away with technology trends or further growth as they are due to systemic limitations of the protocol architecture. This project is developing techniques towards the design of an interdomain routing architecture that provides high availability under flexible routing policies, link and node failures, and router misconfiguration.
The project has the following thrusts. First, it develops a quantitative foundation for interdomain "X-ities", a term used to describe metrics desired in an interdomain routing protocol such as availability, stability, policy flexibility, accountability, predictability, deployability etc. Second, it develops routing protocols based on insights from the theory of distributed systems, namely, using redundancy to mask failures, and treating consistency as a safety property. Specifically, the project builds upon "multiprocess routing", an approach that runs multiple parallel routing processes that select primary or backup routes to deliver packets with high probability under multiple link and node failures; and "consensus routing", a consistency-first approach to ensure high availability under flexible policies. The project adapts these approaches to tolerate failures as well as to limit the impact of misconfiguration. These new proposals will be compared with existing research proposals for interdomain routing based on the X-ities axes. The protocol designs will be made available to researchers and practitioners through open-source implementations.
