国外计算机类优秀博士答辩pptdefensett.ppt

April 20, 2005 V. Ramachandran — Ph.D. Dissertation Defense Foundations ofInter-Domain RoutingPh.D. Dissertation Defense Vijay Ramachandran Overview This dissertation develops a theoretical framework for the design and analysis of path-vector protocols primarily used for Internet inter-domain routing. The framework can be used to understand the interactions of local routing policies and their effects on protocol behavior. It can also be used to understand the design space of path-vector protocols and inherent trade-offs among desirable protocol properties. Background: Internet Routing BGP Route Processing BGP Route-Selection Procedure Highest local preference Shortest AS-path length For each AS next-hop, lowest MED value eBGP routes over iBGP routes Shortest iBGP distance to egress point Motivation (1) Given certain policy inputs, BGP will oscillate or converge nondeterministically. [VGE ’00, GSW ’02, MGWR ’02, Cisco ’01] These anomalies are difficult for operatorsto debug because the problems traverse autonomously administered networks. New features are often implemented without testing resulting worst-case scenarios. Motivation (2) The BGP specification contains no guidance on how to provide “good” routing policies. Policies are unconstrained. Can policies be constrained to guarantee convergence, and how can those constraintsbe described? What is lost, if anything? Formal models allow rigorous analysis and design at different levels of abstraction. Protocol-Divergence Example Related Work:Formally Modeling Policy Semantics [GSW ’02] introduced the Stable Paths Problem (SPP) as the underlying theoretical problem that BGP is trying to solve. SPP is NP-hard; solvability ? convergence. SPP Results [GSW ’02] Related Work:Local and Global Constraints [GR ’01] showed that Hierarchical BGP (HBGP) is robust. Neighbors are divided into three classes: customers, providers, and peers. Preference and scoping rules apply to routes learned from different types of neighb