An architecture for network path selection

Traditional routing protocols select paths based on static link weights and converge to new paths only when there is an outright reachability failure (such as a link or router failure). This design allows routing scale to hundreds of thousands of nodes, but it comes at the cost of functionality: routing provides only simple, single path connectivity. Networked applications in the wide-area, enterprise, and data center can all benefit from network protocols that allow traffic to be sent over multiple routes en route to a destination. This ability, also called multipath routing, has other significant benefits over single-path routing, such as more efficiently using network resources and recovering more quickly from network disruptions. This dissertation explores the design of an architecture for path selection in the network and proposes a “narrow waist” interface for networks to expose choice in routing traffic to end systems. Because most networks are also business entities, and are sensitive to the cost of routing traffic in their network, this dissertation also develops a framework for exposing paths based on their cost. For this purpose, this dissertation develops a cost model for routing traffic in a network. In particular, this dissertation presents the following contributions: Design of path bits, a “narrow waist” for multipath routing. Our work ties a large number of multipath routing proposals by creating an interface (path bits) for decoupling the multipath routing protocols implemented by the network and end systems (or other network elements) making a choice for path selection. Path bits permit simple, scalable, and efficient implementations of multipath routing protocols in the network that still provide enough expressiveness for end systems to select alternate paths. We demonstrate that our interface is flexible and leads to efficient network implementations by building prototype implementations on different hardware and software platforms. Design of path splicing, a multipath routing scheme. We develop, path splicing, a multipath routing technique, which uses random perturbations from the shortest path to create exponentially large number of paths with only a linear increase in state in a network. We also develop a simple interface to enable end systems to make path selection decisions. We present various deployment paths for implementing path splicing in both intradomain and interdomain routing on the Internet. Design of low cost path-selection framework for a network. Network operators and end systems can have conflicting goals, where the network operators are concerned with saving cost and reducing traffic uncertainty; and end systems favor better performing paths. Exposing choice of routing in the network can thus, create a tension between the network operators and the end systems. We propose a path-selection framework where end systems make path selection decisions based on path performance and networks expose paths to end systems based on their cost to the network. This thesis presents a cost model for routing traffic in a network to enable network operators to reason about “what-if” scenarios and routing traffic on their network.