《国外计算机类优秀博士答辩ppt-defense-tt》由会员分享，可在线阅读，更多相关《国外计算机类优秀博士答辩ppt-defense-tt（31页珍藏版）》请在金锄头文库上搜索。
1、Foundations ofInter-Domain RoutingPh.D. Dissertation Defense,Vijay Ramachandran,Dissertation Director: Joan FeigenbaumCommittee Members: Jim Aspnes, Paul Hudak,Tim Griffin (University of Cambridge),V. Ramachandran Ph.D. Dissertation Defense,2,April 20, 2005,Overview,This dissertation develops a theo
2、retical 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
3、-vector protocols and inherent trade-offs among desirable protocol properties.,V. Ramachandran Ph.D. Dissertation Defense,3,April 20, 2005,Background: Internet Routing,V. Ramachandran Ph.D. Dissertation Defense,4,April 20, 2005,Apply Policy =filter routes & tweak attributes,BGP Route Processing,Rout
4、ing Table,Apply Import Policies,Best Route Selection,Apply Export Policies,Install forwardingentries for best routes,ReceiveBGPupdates,Storageof routes,TransmitBGP updates,Based onattributevalues,IP Forwarding Table,Apply Policy =filter routes & tweak attributes,Open-ended programming:constrained on
5、ly by vendor configuration language,V. Ramachandran Ph.D. Dissertation Defense,5,April 20, 2005,BGP Route-Selection Procedure,Highest local preferenceShortest AS-path lengthFor each AS next-hop, lowest MED valueeBGP routes over iBGP routesShortest iBGP distance to egress point,V. Ramachandran Ph.D.
6、Dissertation Defense,6,April 20, 2005,Motivation (1),Given certain policy inputs, BGP will oscillate or converge nondeterministically.VGE 00, GSW 02, MGWR 02, Cisco 01These anomalies are difficult for operatorsto debug because the problems traverse autonomously administered networks.New features are
7、 often implemented without testing resulting worst-case scenarios.,V. Ramachandran Ph.D. Dissertation Defense,7,April 20, 2005,Motivation (2),The BGP specification contains no guidance on how to provide “good” routing policies.Policies are unconstrained.Can policies be constrained to guarantee conve
8、rgence, and how can those constraintsbe described?What is lost, if anything?Formal models allow rigorous analysis and design at different levels of abstraction.,V. Ramachandran Ph.D. Dissertation Defense,8,April 20, 2005,Prefer sendingtraffic throughneighbor 2,Prefer sendingtraffic throughneighbor 1
9、,Protocol-Divergence Example,0,1,2,0,20,0,10,20,120,10,210,10,20,120,210,V. Ramachandran Ph.D. Dissertation Defense,9,April 20, 2005,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
10、is NP-hard; solvability convergence.,An SPP instance is a graph in which each node represents one AS and has a policy in the form of a linear preference ordering on paths.,V. Ramachandran Ph.D. Dissertation Defense,10,April 20, 2005,SPP Results GSW 02,DISAGREE (multiple solutions),BAD GADGET (no sol
11、ution),Dispute Wheel,No dispute wheel impliesrobust convergence.,V. Ramachandran Ph.D. Dissertation Defense,11,April 20, 2005,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.Prefer
12、ence and scoping rules apply to routes learned from different types of neighbors.No customer/provider cycles.GGR 01 added an attribute to HBGP to allow safe back-up routing.,Localconstraint,Globalconstraint,V. Ramachandran Ph.D. Dissertation Defense,12,April 20, 2005,The Design Space of Path-Vector
13、Protocols GJR 03,Robustness: Does the protocol predictably converge, even after node and link failures?Expressiveness: What routing policies are permitted?Autonomy: What degree of independence do operators have in local-policy configuration?Policy Opaqueness: Can local route settings be kept private
14、?Transparency: How directly does the protocol apply local-policy transformations to route data?Global Constraint: What network assumptions are needed?,V. Ramachandran Ph.D. Dissertation Defense,13,April 20, 2005,Three Levels of Abstraction JR 05,Path-Vector Algebras Sob. 03A description of the most
15、important criteria involved in determiningbest routes. Does not include implementation details, e.g., a routeadvertisement is considered an atomic action.,Path-Vector Policy Systems (PVPS) GJR 03A combination of message-passing system (protocol), policy language,and global constraint. The underlying
16、 path-vector system modelsimport & export policies, path selection, and route data structures.,Instances of the Stable Paths Problem (SPP) GSW 02A routing configuration, indicating the preference order of permittedpaths on a given network. Solutions are consistent assignments;unique solutions give predictable convergence to a stable assignment.,
