Atomic Routing Theory: Making an AS Route Like a Single Node

Abstract:

The hierarchical structure of the Internet separates routing into two
subproblems: routing between Autonomous Systems (ASes) and routing within each AS. The first problem has been studied extensively, assuming that the routers in an AS collectively act as a single node, even though there is no such guarantee today. In this paper, we study how an AS as a whole makes interdomain routing decisions. We introduce Atomic Routing Theory (ART)---a model that captures how a distributed collection of routers can correctly realize an AS's routing policy---and analyze the fundamental tradeoff between protocol overhead and policy flexibility. We identify three reasons why today's BGP-speaking ASes are not atomic: (i) a router cannot assign different routes to different links, (ii) route selection is too tightly coupled with route dissemination, and (iii) routers may deflect data packets from the chosen interdomain route. Our proposed solutions to these problems, which result in an enhanced protocol called \emph{atomic BGP}, are easily implementable, introduce minimum overhead, and, since the changes are local to an AS, can be deployed incrementally. Atomic BGP guarantees policy correctness, simplifies router configuration, and closes the gap between interdomain routing assumptions and realities.