Metarouting and Network Optimization (Invited Paper)
Alexander J. T. Gurney, Timothy G. Griffin · 2006
IP routers come with a very small set of unicast routing protocols. Network-wide optimization at the level of the IP is often frustrated by the characteristics of the legacy routing protocols. The current cycle of research, development, deployment, and standardization is a long and complex one, making it difficult to introduce changes to existing protocols. The goal of metarouting (1) is to allow network operators the flexibility of defining their own routing protocols in a high- level and declarative manner. Metarouting in (1) is based on the Routing Algebra formalism of Sobrinho (2), which is expressive enough to capture complex policy-based routing of the kind used with the Border Gateway Protocol (BGP) (3), (4), (5). Routing algebras are equipped with preference orders (total pre- orders) that are used to select best routes. Sobrinho showed that distributed algorithms in the Bellman-Ford family will converge when used with routing algebras that are monotonic He also showed that a strict form of monotonicity will ensure that the resulting forwarding system is loop free. Metarouting defines a metalanguage for the definition of complex routing algebras. A key feature of the metalanguage is that algebraic properties required for correctness guarantees can be automatically derived, much like how types are derived in some programming languages. An alternative approach to algebraic routing can be found in the long tradition of using semirings to provide the basis of generalizations to Dijkstra's shortest path algorithm; see for example (6), (7), (8), (9), (10), (11), (12). The order relation associated with idempotent semirings (called path algebras in Gondran and Minoux (9)) is in general a partial order, and is often a total order. The convergence condition for a path algebra is that it be bounded, which means that the multiplicative identity is also a minimal element with respect to the partial order. We could define a metalanguage for path algebras in the same way that (1) did for routing algebras. The operators of such a metalanguage would then be associated with rules for the preservation of boundedness. However, in this paper we will sketch out the basis of a metalanguage for a hybrid approach — one that encompasses routing algebras, path algebras, and mixed mode algebras that are based on pre-orders that arise from com- binations of partial orders and preference orders. We call these structures action algebras and we present a metalanguage for action algebras together with some of its preservation properties. Among the properties of interest for Dijkstra-like algorithms, Sobrinho (13) identified isotonicity (for convergence) and strict isotonicity (for loop freedom). We study the preservation of these properties in our action algebra metalanguage, which captures the examples studied in (13) as special cases. We believe this raises interesting questions concerning the development of hybrid routing algorithms that use novel combi- nations of Dijkstra and Bellman-Ford algorithms in appropriate regions of a network.