Relating Two Formal Models
of Path-Vector Routing
March 15, 2005: IEEE INFOCOM, Miami, Florida
Aaron D. Jaggard
Tulane University
Vijay Ramachandran
Yale University
[email protected]
[email protected]
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