Internet routing: characterization via an algebraic property of cycles and a polynomial-time algorithm

Abstract

Routing algebras provide a formal framework for reasoning about routing problems, algorithms, and protocols. They currently underpin systems that verify the correctness of internet routing protocol configurations prior to deployment. All such protocols—from BGP to IS-IS, OSPF, and EIGRP—can be regarded as solutions to the stable routing problem, namely that of finding an equilibrium choice of forwarding neighbors at each node of a network so as to reach a common destination. To date, only partial conditions for the existence and uniqueness of stable routings have been established. In this paper, we identify an algebraic property of cycles, which we call centripetalism, that characterizes the existence of unique stable routings for all possible destinations in a network and failure scenarios. Building on this characterization, we present the Consistent-Tree algorithm, which either produces a stable routing or reports the presence of a non-centripetal cycle, in O(n2 × m) time, where n and m denote the number of nodes and links in the network, respectively.