Proactive techniques for correct and predictable Internet routing
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, February 2006.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2006
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/34024 |
| _version_ | 1826198599146405888 |
|---|---|
| author | Feamster, Nicholas G. (Nicholas Greer), 1979- |
| author2 | Hari Balakrishnan. |
| author_facet | Hari Balakrishnan. Feamster, Nicholas G. (Nicholas Greer), 1979- |
| author_sort | Feamster, Nicholas G. (Nicholas Greer), 1979- |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, February 2006. |
| first_indexed | 2024-09-23T11:07:17Z |
| format | Thesis |
| id | mit-1721.1/34024 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T11:07:17Z |
| publishDate | 2006 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/340242019-04-10T09:39:00Z Proactive techniques for correct and predictable Internet routing Feamster, Nicholas G. (Nicholas Greer), 1979- Hari Balakrishnan. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, February 2006. This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. Includes bibliographical references (p. 185-193). The Internet is composed of thousands of autonomous, competing networks that exchange reachability information using an interdomain routing protocol. Network operators must continually reconfigure the routing protocols to realize various economic and performance goals. Unfortunately, there is no systematic way to predict how the configuration will affect the behavior of the routing protocol or to determine whether the routing protocol will operate correctly at all. This dissertation develops techniques to reason about the dynamic behavior of Internet routing, based on static analysis of the router configurations, before the protocol ever runs on a live network. Interdomain routing offers each independent network tremendous flexibility in configuring the routing protocols to accomplish various economic and performance tasks. Routing configurations are complex, and writing them is similar to writing a distributed program; the (unavoidable) consequence of configuration complexity is the potential for incorrect and unpredictable behavior. These mistakes and unintended interactions lead to routing faults, which disrupt end-to-end connectivity. Network operators writing configurations make mistakes; they may also specify policies that interact in unexpected ways with policies in other networks. (cont.) To avoid disrupting network connectivity and degrading performance, operators would benefit from being able to determine the effects of configuration changes before deploying them on a live network; unfortunately, the status quo provides them no opportunity to do so. This dissertation develops the techniques to achieve this goal of proactively ensuring correct and predictable Internet routing. The first challenge in guaranteeing correct and predictable behavior from a routing protocol is defining a specification for correct behavior. We identify three important aspects of correctness-path visibility, route validity, and safety-and develop proactive techniques for guaranteeing that these properties hold. Path visibility states that the protocol disseminates information about paths in the topology; route validity says that this information actually corresponds to those paths; safety says that the protocol ultimately converges to a stable outcome, implying that routing updates actually correspond to topological changes. Armed with this correctness specification, we tackle the second challenge: analyzing routing protocol configurations that may be distributed across hundreds of routers. (cont.) We develop techniques to check whether a routing protocol satisfies the correctness specification within a single independently operated network. We find that much of the specification can be checked with static configuration analysis alone. We present examples of real-world routing faults and propose a systematic framework to classify, detect, correct, and prevent them. We describe the design and implementation of rcc ("router configuration checker"), a tool that uses static configuration analysis to enable network operators to debug configurations before deploying them in an operational network. We have used rcc to detect faults in 17 different networks, including several nationwide Internet service providers (ISPs). To date, rcc has been downloaded by over seventy network operators. A critical aspect of guaranteeing correct and predictable Internet routing is ensuring that the interactions of the configurations across multiple networks do not violate the correctness specification. Guaranteeing safety is challenging because each network sets its policies independently, and these policies may conflict. Using a formal model of today's Internet routing protocol, we derive conditions to guarantee that unintended policy interactions will never cause the routing protocol to oscillate. (cont.) This dissertation also takes steps to make Internet routing more predictable. We present algorithms that help network operators predict how a set of distributed router configurations within a single network will affect the flow of traffic through that network. We describe a tool based on these algorithms that exploits the unique characteristics of routing data to reduce computational overhead. Using data from a large ISP, we show that this tool correctly computes BGP routing decisions and has a running time that is acceptable for many tasks, such as traffic engineering and capacity planning. by Nicholas Greer Feamster. Ph.D. 2006-09-28T14:51:39Z 2006-09-28T14:51:39Z 2005 2006 Thesis http://hdl.handle.net/1721.1/34024 71316172 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 193 p. 2205480 bytes 2242457 bytes application/pdf application/pdf application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Feamster, Nicholas G. (Nicholas Greer), 1979- Proactive techniques for correct and predictable Internet routing |
| title | Proactive techniques for correct and predictable Internet routing |
| title_full | Proactive techniques for correct and predictable Internet routing |
| title_fullStr | Proactive techniques for correct and predictable Internet routing |
| title_full_unstemmed | Proactive techniques for correct and predictable Internet routing |
| title_short | Proactive techniques for correct and predictable Internet routing |
| title_sort | proactive techniques for correct and predictable internet routing |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/34024 |
| work_keys_str_mv | AT feamsternicholasgnicholasgreer1979 proactivetechniquesforcorrectandpredictableinternetrouting |