ciss06griffin ciss 2006

Metarouting and Network Optimization: 

Metarouting and Network Optimization timothy.griffin@cl.cam.ac.uk CISS 2006 alex.gurney@cl.cam.ac.uk (work in progress)

The Current Situation: 

The Current Situation IP Connectivity is implemented with dynamic routing protocols These protocols are few in number Existing protocols tend to get in the way of network optimization, network analysis

Routing Algebras(Sobrinho): 

Routing Algebras (Sobrinho) 2002: Algebra and Algorithms for QoS Path Computation and Hop-by-Hop Routing in the Internet. 2003: Network Routing and Path Vector Protocols: Theory and Applications. Routing Algebras 1970s 1980s: Path Algebra = Idempotent semiring. Carre’, Gondran & Minoux

Generalized Routing Algebras(Gurney & Griffin, ongoing work): 

Generalized Routing Algebras (Gurney & Griffin, ongoing work) is a semi-group action on S A semi-group This is a pre-order

Big Picture: 

Big Picture Path Algebras Generalized Routing Algebras Routing Algebras

“Best” Routes: 

“Best” Routes For finite, non-empty Total order Partial order Total pre-order Pre-order

Weighted Graph, solution: 

Weighted Graph, solution

Generalized Dijkstra : 

Generalized Dijkstra for all v in V: d[v]  d[s]  Q  V while Q not empty: choose u in Q with d[u] in min{d[v] | v in Q}; Q  Q - {u}; for all v in V with (u, v) in E: if d[v] > (w(u, v) d[u]) then: d[v]  w(u, v) d[u];

Generalized Bellman-Ford: 

Generalized Bellman-Ford for all v in V: d[v]  d[s]  Q  V for i in {1, 2, ..., |V| - 1} for all (u, v) in E if d[v] > (w(u, v) d[u]]) then d[v]  w(u, v) d[u] -- Negative weight cycle detection for (u, v) in E if d[v] > (w(u, v) d[u]) then: return false -- Found “neg-weight” cycle return true -- No “neg-weight” cycle

Some Important Properties : 

Some Important Properties Monotonicity (M) : Strict monotonicity (SM) : Isotonicity (I) : Strict isotonicity (SI) :

What makes these algorithms work (for bounded path algebras)? : 

What makes these algorithms work (for bounded path algebras)? Dijkstra Correctness proof uses monotonicity and isotonicity, Loop-freedom for hop-by-hop forwarding uses strict monontonicity. Bellman-Ford Correctness proof uses monotonicity, Loop-freedom for hop-by-hop forwarding uses strict monotonicity

Metarouting(Griffin & Sobrinho 2005): 

Metarouting (Griffin & Sobrinho 2005) A meta-language for Routing Algebras Base algebras Constructors Property Preservation Rules Properties of base algebras known, Preservation rules for each constructor Can be implemented, standardized

Direct Product : 

Direct Product

Direct Product : 

Direct Product M SM M SM M M SM SM M M M SM I SI I SI I I SI SI I I I SI

Distance x Bandwidth: 

Distance x Bandwidth London Moscow Prague Rome Paris (250, 90) (311, 70) (100, 30) (200, 30) (10, 80) P = Rome  Prague  Moscow = (300, 30) Q = Rome  Paris  London  Moscow = (571, 70) min {w(P), w(Q)} = {(300, 30), (571, 70)}

Lexicographic Product : 

Lexicographic Product

Property Preservation with Lex Product: 

Property Preservation with Lex Product M SM M M SM M SM SM EQ,SI EQ,SI I I SI A design pattern: SI EQ EQ EQ All at least M SM Don’t care! SM

Local Preference, Origin Preference: 

Local Preference, Origin Preference (Always M)

Disjoint Union: 

Disjoint Union

Disjoint Union : Property Preservation: 

Disjoint Union : Property Preservation M SM M SM M M SM SM M M M SM I SI I SI I I SI SI I I I SI

Scoped Product: 

Scoped Product Q : What is a good mathematical framework for the analysis of routing algebra metalanguages? A : CATEGORY THEORY!

Scoped Product: 

Scoped Product

Scoped Product : Monotonicity Preservation: 

Scoped Product : Monotonicity Preservation SM SM M SM M SM

Dependent Lexicographic Product: 

Dependent Lexicographic Product

An application…: 

An application… This can be viewed as an instance of

Operations at the Protocol Level: 

Operations at the Protocol Level A A B B A B A B

…or : 

…or A A A A A B B B Adjacencies of B supported by connectivity of provided by A Think of A = OSPF and B = IBGP ….

OSPF Revisited: 

OSPF Revisited Something like where (shortest paths) Something like

Challenge : 

Challenge If you could “roll your own” routing protocols, what would you do? How does this kind of flexibility change the way you might think about network optimization?