| The Internet has become an indispensable communication medium in our society. One consequence of this success is that it has become difficult to change the Internet's underlying architecture, since a change might disrupt service. At the same time, the research community works to provide improved communication services by proposing new network architectures and protocols. This paradox leads researchers to use overlay networks to experiment with potentially disruptive network services with minimal change to the existing Internet infrastructure.; Although overlay networks have become a popular vehicle to implement new network services, researchers also recognize the need to overcome routing scalability. The Internet achieves scalability by organizing the network into a hierarchical structure and by routing to hundreds of millions of hosts. On the other hand, most overlay networks do not scale, mainly because the underlying network structure is invisible to the overlay network. That is, the overlay network often treats the underlying Internet as a black-box, and is unable to use the Internet's topology information to improve scalability in overlay routing.; This thesis proposes and evaluates an infrastructure to expose facts about the topology of the underlying Internet to overlay networks in order to scale routing. It posits that identifying shared routing sub-services and building a shared infrastructure to support them---a so-called routing underlay---is essential to improving routing scalability and resilience in overlay networks.; Toward this end, the thesis makes the following two contributions. First, it presents a design of a routing underlay, called PLUTO, that leverages hierarchical probes---lower layers use inexpensive probes over a large scope and higher layers use more expensive probes in a limited scope. Second, the thesis evaluates PLUTO's impact on routing scalability and resilience by conducting experiments on PlanetLab. Experiments show PLUTO improves the scalability of overlay routing without negatively affecting the quality of the overlay's route selection. Further analysis explores the trade-off between scalability and route quality, showing that the quality degrades gracefully as scalability improves. Additional analysis shows that PLUTO improves the resilience of overlays in the presence of link failures. |
