Policies in routing

The Internet began as a network under the control of a single organization, ARPA. The initial goals were to provide basic connectivity between end-hosts even in the event of failures, and applications running over the network, such as email, could utilize any path through the network as long as the destination could eventually be reached. The existence of a single administrative entity for the entire network and the lack of a need to distinguish between possible paths as well as packets in the network meant that a simple routing protocol is sufficient to provide connectivity. With its subsequent break up and distributed management, the Internet today needs to distinguish between different kinds of data and control information. For instance, service providers have to decide on which neighboring provider to transit their traffic, or to filter certain packets due to certain accessibility constraints. The type of policies involved vary depending on whether they are applied on an inter or intra-domain basis, and hence also the resulting problems that arise. We address two issues in this dissertation. Firstly, the lack of visibility and independent implementing of policies in inter-domain routing can result in policy disputes causing routing to oscillate forever. We propose the Precedence Solution that enforces shortest path routing only when oscillations resulting from disputes arise. In scenarios where no such disputes exist, all routers are able to select their most preferred paths. This solution provides just enough visibility to obtain the location of routers having policy conflicts thus easing troubleshooting, without revealing additional provider policies. We prove that the Precedence Solution is able to stabilize the network, then show how it can be implemented in practice. Secondly, the high level of access control possible in intra-domain networks has resulted in the proliferation of semantically rich policies, which are realized in the form of packet filters and physical topology manipulations. The multitude of knobs to tune in order to achieve the desired performance increases the configuration complexity of these networks. We show that using the notion of classes embedded within routing, reachability information can be automatically propagated and updated by the routing protocol, hence easing configuration.