The routing design of today's networks typically requires multiple instances of routing protocols to be configured. The interactions between the protocols are governed by two procedures at border routers: route selection ranks routes from different protocols; and route redistribution moves routes between protocols. The procedures are critical because operators rely on them to achieve important design objectives. However, there has been very little formal investigation into how safe they are. Existing analytical frameworks for studying routing dynamics have focused on individual routing protocols except for a recent paper that examines some anomalies caused by route redistribution. This paper presents the first comprehensive analysis of both route selection and route distribution regarding all three classes of routing instabilities: non-convergence, formation of loop, and non determinism. We show that the route selection procedure by itself can induce permanent route flaps and forwarding loops. We identify the necessary conditions or root causes for the instabilities and derive guidelines for eliminating them. We then present experimental results showing that all tested Cisco, Quagga, and XORP products have incorrectly implemented the dependency between route selection and route redistribution, causing non-deterministic outcomes. We address this problem by proposing a functional model that makes the dependency unambiguous.

33 pages

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

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by [email protected]