Robust Internet Routing
Nick Feamster
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.
|