Relating Two Formal Models of Path-Vector Routing March 15, 2005: IEEE INFOCOM, Miami, Florida Aaron D. Jaggard Tulane University Vijay Ramachandran Yale University adj@math.tulane.edu vijayr@cs.yale.edu Introduction Two formalisms presented at SIGCOMM’03 model the behavior of path-vector protocols, e.g., BGP (the standard Internet inter-domain routing protocol): • Path-Vector Policy Systems (PVPS) [GJR ’03] • Path-Vector Algebras [Sobrinho ’03] Both were used to derive a mixture of local and global constraints that guarantee convergence. This paper establishes the relationship between the models and constraints. 15 March 2005 Jaggard and Ramachandran — INFOCOM 2005 2 Problem: Protocol Divergence BCD BD BCD CD B C BD CBD BD D 15 March 2005 D CBD CD CD D Jaggard and Ramachandran — INFOCOM 2005 3 Method: Formally Model Behavior Goal: Understand the role of input routing policies on convergence. • Can policies be limited to those that guarantee convergence, and how (if at all) can that set of policies be described? • What are the trade-offs? Formal models allow rigorous analysis and design at different levels of abstraction. 15 March 2005 Jaggard and Ramachandran — INFOCOM 2005 4 Three Levels of Abstraction Sets of Protocols Path-Vector Algebras [Sob. ’03] A description of the most important criteria involved in determining best routes. Does not include implementation details, e.g., a route advertisement is considered an atomic action. Protocols Path-Vector Policy Systems (PVPS) [GJR ’03] A combination of message-passing system (protocol), policy language, and global constraint. The underlying path-vector system models import & export policies, path selection, and route data structures. Networks Instances of the Stable Paths Problem (SPP) [GSW ’02] A routing configuration, indicating the preference order of permitted paths on a given network. Solutions are consistent assignments; unique solutions give predictable convergence to a stable assignment. 15 March 2005 Jaggard and Ramachandran — INFOCOM 2005 5 Modeling Protocol Dynamics Route information to be shared Transformations during advertisement Policies affecting what is imported A Policies affecting what is exported C Path-selection procedure B 15 March 2005 Preference settings based on local policy Jaggard and Ramachandran — INFOCOM 2005 6 Model Components and Properties Algebra Signatures Edge Labels Path/Label Operator Weight Function Monotonicity Isotonicity 15 March 2005 PVPS Path Descriptors Policies (import + export) Policy Application Path Selection (by rank) Increasing rank on extension Order-preserving extension Jaggard and Ramachandran — INFOCOM 2005 7 Monotonicity and Isotonicity Path P has signature s1 or descriptor d1 Path Q has signature s2 or descriptor d2 A Edge has label la or policies fain, faout !(P) ≥ !(Q) implies !(tin(fain, tout(faout, P))) ≥ !(tin(fain, tout(faout, Q))) C Path R has signature s3 or descriptor d3 B 15 March 2005 Isotonicity: f(s1) ≥ f(s2) implies f(la + s1) ≥ f(la + s2); or Edge has label lb or policies fbin, fbout Jaggard and Ramachandran — INFOCOM 2005 Strict Monotonicity: f(lb + s3) > f(s3) or !(tin(fbin, tout(fbout, R))) > !(R) 8 Main Convergence Results Path-vector protocols will converge • robustly on network configurations in which all routes can be partially ordered consistent with nodes’ preferences and path extension (strict monotonicity). • optimally on network configurations in which the preference ordering for paths extended along the same network edge is preserved (isotonicity). These results can be translated between the models’ various levels of abstraction. 15 March 2005 Jaggard and Ramachandran — INFOCOM 2005 9 Translating Between Levels BGP Protocols using length Shortest Paths Both, primarily loc. pref. Protocols using local preference For both, some network instances are convergent Robust protocols Shortest Paths with preference tie-breaking 15 March 2005 Both, primarily length Monotone preferences with length tie-breaking Strictly monotone preferences Jaggard and Ramachandran — INFOCOM 2005 Monotone (or arbitrary) preferences 10 Mapping Between Algebras and PVPSes The expressiveness of an algebra or PVPS is the set of SPP equivalence classes representing possible network configurations. Given an algebra, we can construct a canonical PVPS that is exactly as expressive. Given a PVPS, we can construct a canonical algebra that describes the same rank criteria. 15 March 2005 Jaggard and Ramachandran — INFOCOM 2005 11 Trade-offs in Implementation The algebra can be used to study convergence properties at an abstract level and suggest convergence constraints, independent of specific implementation details. The PVPS framework models more implementation details (e.g., built-in route transformations separate from policies). Thus, trade-offs among enforcing the convergence constraints and other desirable properties not modeled at the abstract level (e.g., autonomy and transparency) can be studied. 15 March 2005 Jaggard and Ramachandran — INFOCOM 2005 12 Summary Algebras and PVPSes are models of path-vector protocols at different levels of abstraction. The models have been used to derive equivalent notions of constraints that guarantee certain convergence properties: • Strict monotonicity gives robust convergence. • Isotonicity gives optimal convergence. 15 March 2005 Jaggard and Ramachandran — INFOCOM 2005 13 Sample Applications of our Translation Added notion of expressiveness to algebras Added optimal convergence results to PVPS Can produce canonical representation of one framework in another Demonstrated various methods to implement a convergence constraint Better understanding of the role of path preference orders, in general 15 March 2005 Jaggard and Ramachandran — INFOCOM 2005 14 Open Questions for Future Work Analyzing interaction between eBGP and iBGP (we’re working on it!) More examples of interesting algebras and protocols and their convergence properties • Describe properties using most appropriate formalism • Translate between them for specific problems Necessary conditions for convergence Using constraints and implementation methods to design policy-configuration languages 15 March 2005 Jaggard and Ramachandran — INFOCOM 2005 15

Descargar
# Document