Foundations of
Inter-Domain Routing
Ph.D. Dissertation Defense
Vijay Ramachandran
Dissertation Director: Joan Feigenbaum
Committee Members: Jim Aspnes, Paul Hudak,
Tim Griffin (University of Cambridge)
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.
April 20, 2005
V. Ramachandran — Ph.D. Dissertation Defense
2
Background: Internet Routing
April 20, 2005
V. Ramachandran — Ph.D. Dissertation Defense
3
BGP Route Processing
IP Forwarding Table
Install forwarding
entries for best routes
Apply Import
Policies
Receive
BGP
updates
Apply Policy =
filter routes &
tweak
attributes
Routing
Table
Storage
of routes
Best Route
Selection
Based on
attribute
values
Apply Export
Policies
Apply Policy =
filter routes &
tweak
attributes
Transmit
BGP
updates
Open-ended programming:
constrained only by vendor configuration language
April 20, 2005
V. Ramachandran — Ph.D. Dissertation Defense
4
BGP Route-Selection Procedure
1.
2.
3.
4.
5.
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
April 20, 2005
V. Ramachandran — Ph.D. Dissertation Defense
5
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 operators
to debug because the problems traverse
autonomously administered networks.
 New features are often implemented without
testing resulting worst-case scenarios.

April 20, 2005
V. Ramachandran — Ph.D. Dissertation Defense
6
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 constraints
be described?
 What is lost, if anything?

Formal models allow rigorous analysis and
design at different levels of abstraction.
April 20, 2005
V. Ramachandran — Ph.D. Dissertation Defense
7
Protocol-Divergence Example
120
10
120
20
1
2
10
210
10
Prefer sending
traffic through
neighbor 2
0
April 20, 2005
0
210
20
20
Prefer sending
traffic through
neighbor 1
0
V. Ramachandran — Ph.D. Dissertation Defense
8
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.
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.
April 20, 2005
V. Ramachandran — Ph.D. Dissertation Defense
9
SPP Results [GSW ’02]
DISAGREE (multiple solutions)
Dispute Wheel
BAD GADGET (no solution)
April 20, 2005
No dispute wheel implies
robust convergence.
V. Ramachandran — Ph.D. Dissertation Defense
10
Related Work:
Local and Global Constraints
 [GR
’01] showed that Hierarchical BGP
(HBGP) is robust.
Local
constraint
 Neighbors
are divided into three classes:
customers, providers, and peers.
 Preference and scoping rules apply to routes
learned from different types of neighbors.
Global
 No customer/provider cycles.
constraint
 [GGR ’01] added an attribute to HBGP to
allow safe back-up routing.
April 20, 2005
V. Ramachandran — Ph.D. Dissertation Defense
11
The Design Space of Path-Vector
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?

Transparency: How directly does the protocol apply localpolicy transformations to route data?

Global Constraint: What network assumptions are needed?
April 20, 2005
V. Ramachandran — Ph.D. Dissertation Defense
12
Three Levels of Abstraction [JR ’05]
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.
April 20, 2005
V. Ramachandran — Ph.D. Dissertation Defense
13
Path-Vector Policy Systems [GJR ’03]
Formal model of path-vector routing:
( PV , PL , K )
Path-Vector System:
Global Constraint:
The underlying message-exchange
system for route information. What
is exchanged and how?
What assumptions about the
network must be true to
achieve robustness?
April 20, 2005
Policy Language:
Question:
How can policies be described?
PL acts as a local constraint on the
expressiveness of policies.
What role do these components
play in achieving protocol design
goals?
V. Ramachandran — Ph.D. Dissertation Defense
14
Linear Best-Route Selection Model


Ignore iBGP and MED-attribute values.
Assume that the route-selection procedure,
at each node, for each destination:
1. maps each route to a rank in some totally
ordered set based on its attribute values; and
2. chooses as best the path with minimal rank.

Rank is influenced by local policy, but the
ranking criteria are the same at each node.
April 20, 2005
V. Ramachandran — Ph.D. Dissertation Defense
15
Robustness Condition
[GJR ’03, Sob. ’03]
Conjecture: No path-vector policy system can
exactly capture all robust configurations.
Theorem: A protocol in which a path’s rank
monotonically increases as it is extended
(imported by a neighbor) is robust.
This is the broadest-known sufficient
condition for robustness, equivalent to
dispute-wheel freeness on SPP instances.
April 20, 2005
V. Ramachandran — Ph.D. Dissertation Defense
16
Trade-Offs in Implementation
[GJR ’03]
Theorem. A globally unconstrained PVPS expressive
enough to capture all increasing configurations either
does not support autonomy of neighbor ranking or is
not transparent, or both.
Theorem. A transparent, robust PVPS that supports
autonomy of neighbor ranking and is at least as
expressive as shortest paths must have a non-trivial
global constraint.
April 20, 2005
V. Ramachandran — Ph.D. Dissertation Defense
17
Algebras and PVPSes (1) [JR ’05]
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
April 20, 2005
Both,
primarily
length
Monotone preferences
with length tie-breaking
Strictly
monotone
preferences
V. Ramachandran — Ph.D. Dissertation Defense
Monotone
(or arbitrary)
preferences
18
Algebras and PVPSes (2) [JR ’05]
The expressiveness of an algebra or PVPS
is the set of SPP equivalence classes permitted
as legal routing 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.

April 20, 2005
V. Ramachandran — Ph.D. Dissertation Defense
19
Class-Based Systems [JR’ 04]


The PVPS framework can be used to generalize
the HBGP constraints from [GR’ 01, GGR’ 01].
A class-based PVPS is described by:
A
set of classes (types of neighbor assignments, e.g.,
customer/provider/peer) and consistency relationships
 Class relative-preference and scoping rules

These systems are transparent and have “some”
autonomy of neighbor ranking; they require
a nontrivial global constraint.
April 20, 2005
V. Ramachandran — Ph.D. Dissertation Defense
20
Relative Preference and Scope
Relative
Scope:
Preference:
If class i routes
If class ibeis to be
cannot
preferred to
over
exported
a
class j, neighbor,
then node
class-k
v should
then
nodeprefer
u will
routes
from
node
only
learn
about
w over
from
the
paththose
uvxQ.
node x.
April 20, 2005
V. Ramachandran — Ph.D. Dissertation Defense
21
Class-Based Robustness [JR’ 04]

From the class description alone, we can construct a
global constraint involving a check on pairs of class
assignments.
 Networks
obeying this constraint are robust.
 Networks violating this constraint allow nodes to write
policies that induce routing anomalies.

We give two types of enforcement algorithms:
a
centralized algorithm that detects a set of nodes whose
class assignments permit a policy-induced anomaly; and
 a distributed algorithm that detects whether two specific
nodes’ class assignments could induce an anomaly.
April 20, 2005
V. Ramachandran — Ph.D. Dissertation Defense
22
Nonlinear Route-Selection Model

Recent work generalizes the PVPS framework
to include protocols that do not assume linear
route-selection procedures.
 This
permits modeling the MED attribute and
both iBGP and eBGP sessions.
 Because previous convergence constraints depend
on a notion of rank, these do not apply
in the generalized case.
 Relies on generalized SPP [GW ’02].
April 20, 2005
V. Ramachandran — Ph.D. Dissertation Defense
23
Generalized SPP [GW ’02]

Recall BGP selection:
 lowest
MED value from
paths to the same AS; then
 shortest IGP distance.


MED-EVIL (no solution)
April 20, 2005

IGP distances are shown
near intra-domain links.
MED values are shown in
parentheses near interdomain links.
This example oscillates.
V. Ramachandran — Ph.D. Dissertation Defense
24
Independent Route Ranking
MED-EVIL (condensed)
April 20, 2005
V. Ramachandran — Ph.D. Dissertation Defense
25
Generalized Path Relations
April 20, 2005
V. Ramachandran — Ph.D. Dissertation Defense
26
Generalized Dispute Digraphs

Given a GSPP instance,
form its generalized
dispute digraph:
 nodes
are paths;
 edges correspond to the
four relations.

Theorem. If a GSPP is
not robust, this graph
contains a cycle.
April 20, 2005
MED-EVIL Dispute Digraph
V. Ramachandran — Ph.D. Dissertation Defense
27
Proof Method
Cycle in MED-EVIL protocol-selection states.



Given a protocol oscillation, choose a path whose first node
is the last oscillating node on the path.
Follow the oscillation until the selection changes; this change
occurred because of a linear or nonlinear selection. This
corresponds to some relation between two paths; repeat
with the ‘related’ path. Choose a subpath to find the last
oscillating node.
Because the oscillation is finite, we must re-visit a path.
We have just traced a cycle in the dispute digraph.
April 20, 2005
V. Ramachandran — Ph.D. Dissertation Defense
28
Protocol-Design Applications

Multiple-Path Broadcast
 [B+ ’02]
and [MC ’04] propose changing BGP to broadcast
additional routes to avoid MED-induced oscillations.
 We can prove the effect of this behavior using our
formal model.
 Improvement: Detect an IRR violation on-the-fly and
request the needed route.

“Compare-all-MEDs” and “Set AS-distinct local
preferences” [MGWR ’02] can be proven correct.
April 20, 2005
V. Ramachandran — Ph.D. Dissertation Defense
29
Summary

The PVPS framework allows for a study of pathvector-protocol design—most importantly, a
rigorous way to prove:
 what
balance of local and global constraints are
needed for robustness; and
 what else is lost when these constraints are implemented.


The framework has provided concrete and
reasonable guidelines for class-based systems.
The framework has been extended to include
protocols with IRR-violating selection procedures.
April 20, 2005
V. Ramachandran — Ph.D. Dissertation Defense
30
Open Questions
Analogous local constraints for the
generalized case
 Real, deployable policy-configuration languages
 More examples of exact trade-offs between
local and global constraints (to date, only
class-based systems give this)
 Full characterization of robust systems?

April 20, 2005
V. Ramachandran — Ph.D. Dissertation Defense
31
Descargar

Document