Harnessing Tunnels For Dirty-Slate Network Solutions

The tremendous success of the Internet has been both a boon and bane for networking research. On one hand, Internet growth has led to a plethora of problems and has prompted work towards next-generation network architectures. While very important, the success of the Internet has also meant that such cleanslate proposals are difficult to deploy. Thus, it is imperative that we find practically deployable dirty-slate solutions. In this thesis, we explore the possibility of tackling network problems in the existing framework through the use of tunnels. Tunneling involves encapsulating protocols in each other and we argue that this can serve as an enabler to the use of existing protocols in novel ways. We have found that, in many cases, such an approach can be used to address the root cause of a problem afflicting the network without necessitating protocol changes. Further, the increasing adoption of tunnels in mainstream networks augurs well for the deployability of such tunnels-based solutions. In this thesis, we focus on two important network problems and present tunnel-driven, dirty-slate solutions to address them. The first problem is routing scalability and includes the growing size of the Internet routing table. We note that routing table size is problematic since every router is required to maintain the entire table. Consequently, we propose ViAggre (Virtual Aggregation), a scalability technique that uses tunnels to ensure that individual routers only maintain a fraction of the global routing table. ViAggre is a "configurationonly" approach to shrinking the routing table on routers -- it does not require any changes to router software and routing protocols and can be deployed independently and autonomously by any ISP. We present the design, evaluation, implementation and deployment of ViAggre to show that it can offer substantial reduction in routing table size with negligible overhead. The second part of the thesis delves into IP Anycast. The route-to-closestserver abstraction offered by IP Anycast makes it an attractive primitive for service discovery. Further, the growth of P2P, overlay and multimedia applications presents new uses for IP Anycast. Unfortunately, IP Anycast suffers from serious limitations -- it is difficult to deploy, scales poorly and lacks important features like load balancing. As a result, its use has been limited to a few critical infrastructure services like DNS root servers. Further, despite such deployments, the performance of IP Anycast and its interaction with IP routing practices is not well understood. While these are valid concerns, we also believe that IP Anycast has compelling advantages. Motivated by these, we first conduct a detailed study of IP Anycast that equips us with the knowledge of how to maximize its potential. Building upon this, we present PIAS (Proxy IP Anycast Service), an anycast architecture that uses tunnels and proxies to decouple the anycast service from Internet routing. This allows PIAS to overcome IP Anycast's limitations while largely maintaining its strengths. We present simulations, measurement results, implementation and wide-area deployment details and describe how PIAS supports two important P2P and overlay applications