An architecture for network path selection
MetadataShow full item record
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 beneﬁt from network protocols that allow trafﬁc to be sent over multiple routes en route to a destination. This ability, also called multipath routing, has other signiﬁcant beneﬁts over single-path routing, such as more efﬁciently 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 trafﬁc to end systems. Because most networks are also business entities, and are sensitive to the cost of routing trafﬁc 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 trafﬁc 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 efﬁcient 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 ﬂexible and leads to efﬁcient 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 conﬂicting goals, where the network operators are concerned with saving cost and reducing trafﬁc 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 trafﬁc in a network to enable network operators to reason about "what-if " scenarios and routing trafﬁc on their network.