Computer Science Department
School of Computer Science, Carnegie Mellon University


Theory and new Primitives for
Interconnecting Routing Protocol Instances

Franck Le*, Geoffrey G. Xie**, Hui Zhang

May 2009


Keywords: Routing corrections, multi-instances, route selection, route redistribution

Recent studies have shown that the primitives, that govern the interactions between routing protocol instances, are pervasively deployed in enterprise networks and the Internet but are extremely vulnerable to routing anomalies, including route oscillations and forwarding loops. In this paper, we propose a general theory for reasoning about routing properties across multiple routing instances. The theory is directly applicable to both link-state and vector routing protocols. Each routing protocol still makes independent routing decisions and may consider a variety of routing metrics, such as bandwidth, delay, cost, and reliability. While the theory permits a range of solutions, we focus on a design that requires no changes to existing routing protocols such as OSPF, RIP, EIRGP, and BGP. Guided by the theory, we derive a new set of primitives which are safe and more expressive than the current version, i.e., they can support operational goals not achievable today. We provide a detailed description of the new primitives in the form of IOS configuration commands and implemented them in the XORP routing software.

36 pages

*Department of Electrical and Computer Engineering, Carnegie Mellon
**Department of Computer Science, Naval Postgraduate School, Monterey, CA

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by