Martin Suchara will present his preFPO on Tuesday November 23 at 10AM in Room 402. The members of his committee are: Jennifer Rexford, advisor; Mung Chiang (ELE) and Gordon Wilfong (Bell Labs), readers; Mike Freedman and Ed Felten, nonreaders. Everyone is invited to attend his talk. His abstract follows below. --------------------------------------- Reliable Internet Routing The network routing system is a critical infrastructure that enables communication of hosts connected to the Internet. Despite its importance, the design is vulnerable to hardware faults, routing policy misconfigurations, as well as malicious attacks. Each of these vulnerabilities may either cause loss of availability, or degrade network performance. This thesis provides several complementary mechanisms that address these reliability, security and performance concerns. The design of each of these mechanisms takes into account practical considerations, such as the incentives for adoption, ease of deployment, or computational complexity of the required calculations. Preventing BGP Route Oscillations The Internet consists of tens of thousands of separately administered autonomous systems with independently chosen routing policies. Policy interactions may cause permanent route oscillations in the interdomain routing protocol (BGP), leading to degraded network performance as well as unnecessary message-processing overhead. The first step towards only using "safe" policies is to understand the exact conditions when these policies guarantee convergence, and to provide an efficient algorithm that allows such safety verification. To that end, we develop DPVP, a new theoretical model of routing that is more amenable to analysis. DPVP includes several BGP implementation features that have been omitted in the previous theoretical models. In particular, our model allows "spurious" announcements of less-preferred routes that may be caused by a variety of mechanisms integrated in BGP. In this new, more robust model, we derive the necessary and sufficient condition for safety, which furthermore admits an efficient algorithm for checking BGP safety in most practical circumstances -- two complementary results that have been elusive in the past decade's worth of classical studies of BGP convergence in more simple models. Securing BGP against Attacks Integrity of the interdomain routing system is threatened by compromised routers which announce address prefixes that they do not own. Deployment of the many countermeasures that have been proposed in the past decade is complicated by the requirement for cooperation of all of the independently administered autonomous systems. Instead of requiring unilateral cooperation, we argue that small groups should be the basis for securing interdomain routing, and we offer a new design where routing is secured by a few (e.g., 5--10) participating autonomous systems. We conduct extensive simulations and identify conditions for small groups to be effective. In particular, the participants can achieve remarkable security gains by filtering compromised interdomain routes, cooperating to expose additional path diversity, inducing non-participants to select valid routes, and convincing a few large ISPs to participate. We also propose two novel mechanisms that the group members can employ to achieve these goals, namely secure overlay routing and the cooperative announcement of each other's address space. Our experiments show that combining these two techniques allows small groups to secure interdomain routing. Making Routing Failure Resilient Unexpected hardware failures often result in loss of connectivity or poor performance while the routing system converges to a new set of paths. To enable reliable data delivery and balance load in the presence of failures, this thesis proposes a new mechanism that combines path protection and traffic engineering. The key benefit of our solution is its simplicity, allowing for fast recovery while imposing minimal requirements on the routers. To provide resilience against every failure scenario from a known set, we advocate using a fixed set of parallel end-to-end paths for each traffic demand. Upon detecting a path failure, the ingress router uses a local rule to rebalance the outgoing traffic on the remaining available paths. We describe several candidate rebalancing algorithms, and analyze their performance. Although calculating the optimal set of paths and the path-splitting parameters for each router is NP-hard, our extensive simulations on a tier-1 IP backbone demonstrate that our easy-to-calculate heuristic suffices to achieve nearly optimal load balancing. Planned Work In addition to the above, I plan to answer the following questions: (i) This work uses the DPVP model to study the dynamics of interdomain routing (eBGP). How applicable is the model to intradomain routing (iBGP) and what new insights can we gain? (ii) We provide an algorithm that determines routing safety in polynomial time for virtually all policies that are used by network operators in practice. Is it possible to formalize the conditions under which the algorithm runs in polynomial time?