The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

An Isaac Newton Institute Programme

Logic and Algorithms

Metarouting: An Algebraic Approach to Defining Routing Protocols.

10th March 2006

Author: Tim Griffin (Cambridge)


Semi-rings have been used in the past thirty years as a general framework in which to describe routing problems and routing algorithms. Some of the semi-ring axioms can be relaxed to arrive at "routing algebras" (Sobrinho 2003), which can model the very complex poilcy-based routing used in the Internet today. Metarouting is centered around defining a meta-language for routing algebras --- a language where algebraic properties (such as monotonicity) needed for convergence guarantees can be automatically derived much like types are derived in programming languages.