Metarouting Progress Report

-- Tim Griffin

Network programmability demands clean and crisp abstractions.
Yet such abstractions seem to allude us.  We are abstracting in
an environment that has in many ways grown organically, making 
it very difficult to identify and focus on the essential while ignoring
the accidental. Which is which?   We are not sure!  And in the meantime,
the technology continues to change and evolve. Will our abstraction
keep up, or will they prove to be too inflexible?  We loose sleep.

Metarouting [SIGCOMM 2005] suggests a framework for programmability 
in the restricted domain of Internet routing protocols. Since network 
routing has a long and glorious mathematical history, we might expect 
to be flush with ready-made abstractions. Can't we go home early? Oh, if 
only this were the case!   The designers of Internet routing protocols 
surely had routing books on their shelves.  Yet, happily it turns out, 
they seem  to have opened them rarely. Instead they invented new kinds 
of routing that went beyond what the textbooks described, and made the 
Internet an extremely novel place, routing-wise.  Let us take a moment 
here to thank Yakov and company for knowing when to ignore the 
mathematicians!   And let us be humble enough to remember that the 
Internet was founded on ignoring the intimidating certitude of academic 
specialists, most of whom knew that ATM was the only way to go. [It is 
really a shame that so many young people in networking are unaware of 
this history. The Internet represented a full-tilt rebellion against the 
status quo.  Textbooks have already rewritten history and drained the 
blood out of the conflict. The experts were not only wrong, they were 
wrongidy-wrong-wrong. We should never forget this fact.]

New types of routing require new abstractions!  Joao Sobrinho introduced 
his routing algebras [SIGCOMM 2003] to model the novelty of BGP, and 
these algebras formed the basis of the original metarouting proposal. 
I'll argue that Sobrinho's algebras are closely related to nondistributive 
semirings.  But this only drives home the point --- non-distributive 
semirings have been almost entirely ignored in the routing literature, 
save for a footnote here and there. [Please correct me if I'm wrong.]

Metarouting is based on this dogma:

  routing protocol = routing language + routing algorithm + proof,

where a routing language captures how routes are described, how they 
are compared, and how policy is desribed and applied. The routing 
algorithm finds solutions for a network configured using the routing 
language. And the proof tells us that it all works.  From a mathematical 
point of view there is nothing at all remarkable about this equation --- 
this is the way things have always been described! But the "hack now think 
later" [1] approach has blurred the distinction between routing algorithms 
and languages.  Is the areas mechanism of OSPF a part of the routing 
language, or the algorithm? Is the EBGP/IBGP distinction a part of BGP's 
algorithm or language?  We have to do some reverse engineering to clarify 
these issues.  The metarouting approach is to keep algorithms as generic 
and as simple as possible, while shifting as much complexity as possible 
to the routing language.

The key new idea in metarouting is to design a "metalangauge" for the 
specification of routing languages.  A good metalangauge should allow 
for the automatic derivation of "algebraic" properties needed for the 
correctness of specific algorithms.  For example, a generalized Dijkstra 
algorithm requires that policy application distribute over best route 
selection (among other requirements).  But what is a good framework for 
such a metalangauge?  Much of our work over the last year has focused 
on this question. We have found that it is very hard to strike a balance 
between expressive power of the metalanguage and maintaining the ability 
to derive properties automatically. I'll discuss some progress in this area.

We have also been working on a metalanguage compiler, which we hope 
will produce very efficient code to implement routing languages specified 
in the metalanguage (this is mostly the work of John Billings).

I'm very lucky to be working with Alexander Gurney and John Billings, two 
PhD students, as well as Samuel Hym, a post-doc. I'll describe work that 
has been done in collaboration with them.  The work is being funded in 
part by Boeing and Cisco.

[1] BGP at 18: Lessons In Protocol Design. Talk by Yakov Rekhter.
April 17, 2007.
http://video.google.co.uk/videoplay?docid=3363016304060792712&q=BGP.