| A primary goal of computer networks is to facilitate communication between interconnected computers. To achieve this objective, routers---the devices responsible for interconnecting computer networks and forwarding traffic to their intended destination---exchange routing information through routing protocols and then use the disseminated information to calculate routes. As such, routing information plays a critical role in Internet routing. Errors in routing information can easily result in failure conditions such as forwarding loops which cause packets to cycle through a sequence of routers without ever reaching their destinations. Consequently, much research has been devoted to making routing protocols safe, i.e., free from failure conditions.;This thesis brings to light the fundamental role of a previously hidden routing design component called "connecting primitives". These primitives are introduced by router vendors to support the essential operational requirement of merging multiple domains that run independent routing protocol instances. Despite their important and distinct role from routing protocols, the connecting primitives received little attention from the research community and were poorly understood prior to this work.;This thesis provides a comprehensive and deep understanding of the connecting primitives. First, using results from an empirical study of 1600+ networks, it shows the prevalent usage of the connecting primitives and explains the phenomenon by discovering two critical requirements that cannot be achieved by current routing protocols alone. Second, I show that despite their importance, the current design is problematic: it is vulnerable to routing failures and too rigid for operators to fulfill their requirements. To address this problem, I developed a theory to reason about routing across multiple routing protocol instances, and from the theory, I derived a new design for the connecting primitives.;The results of this thesis have both theoretical and practical impacts. On the theoretical front, I show that focusing on routing protocols alone is not sufficient. Instead, the connecting primitives play an equally important role in lntemet routing. In addition, I broaden the fundamental understanding of routing beyond a single routing protocol instance. On the practical front, I design connecting primitives that present provable properties and are more expressive than today's. |
