Tuesday, March 15, 2005
4:15 pm
B17 Upson Hall

Nick Feamster
MIT

Robust Internet Routing

 The Internet is composed of thousands of autonomous, competing networks that exchange reachability information using an interdomain routing protocol. Interdomain routing offers each independent network tremendous flexibility in expressing routing policy. These policies, specified in terms of distributed router configurations, play an important role in expressing various economic and performance requirements. Routing configurations are complex, and writing them is similar to writing a distributed program; the (unavoidable) price of configuration complexity is correctness. Network operators writing configurations make mistakes; they may also specify policies that interact in unexpected ways with policies in other networks. These mistakes and unintended interactions lead to routing faults, which disrupt end-to-end connectivity. Our challenge is to ensure globally correct behavior of interdomain routing while preserving the autonomy of each network.

In this talk, I will show several examples of real-world routing faults and present a systematic framework to classify, detect, correct, and prevent them.

I will first describe the design and implementation of rcc ("router configuration checker"), a tool that uses static configuration analysis to detect classes of faults that commonly result from operator mistakes.  rcc enables network operators to debug configurations before deploying them in an operational network, improving on the status quo where most faults are detected only during actual operation. We used rcc to detect faults in 17 different networks, including several nation-wide Internet service providers. To date, rcc has been downloaded by over sixty network operators across the world.

Additionally, using a formal model of today's interdomain routing protocol, I will prove necessary and sufficient conditions on policy to guarantee that certain faults resulting from unintended policy interactions will never occur. I will discuss the implications of these results on operational practice and on the future evolution of the Internet routing infrastructure.