1. Introduction

During the last six years, overlay networks have become one of the most prominent tools for Internet research and development. Overlays permit designers to implement their own routing and packet management algorithms on top of the Internet. The Internet itself began as an overlay network on top of the telephone network, using long-distance telephone links (that consist of multiple physical links) to connect Internet routers. Modern overlays operate similarly, using the Internet paths between end-hosts as “links” upon which the overlay routes data, building a network on top of the network. As a result, overlays can be used to deploy new functionality almost immediately, instead of requiring years of upgrades to Internet routers; they also present developers with a flexible and powerful platform on which to create new services.

While overlays are at least as old as the Internet, they weren’t generally regarded as an area of research on their own until the late 1990s, when two types of overlays bloomed: routing overlays, and storage and lookup overlays:

Virtual private networks (VPNs) are an example of simple routing overlays that provide better network-level security and authentication. Other routing overlays like the Resilient Overlay Network (RON) [1] were designed to provide better resilience to network failures than Internet routing protocols could; yet others have been used to provide anonymous communication [2]. Figure 1 shows how a RON is able to route around a failure in the Internet that prevented two hosts from communicating.

Storage and lookup overlays have become a substrate upon which a number of large distributed systems projects are based. The line between storage and routing overlays has become blurred over time.

2. Benefits of overlay networks

There is a growing feeling among many Internet researchers that the Internet protocol (IP) and the IP routing infrastructure has become ossified by virtue of its huge success. Changing the hundreds of millions of currently deployed IP-speaking devices poses a considerable challenge—witness the extremely long projected rollout times for IPv6. Overlay networks offer an alternative to modifying Internet protocols or routers, providing a quick and easy deployment path that lacks many of the technical and political hurdles of a router-level deployment. Instead of changing the IP layer, many researchers now design protocols that run on top of IP in an overlay.

Finally, an overlay can take advantage of the large glut of processing, memory, and permanent storage available in commodity hardware to perform tasks that would ordinarily be well beyond the ability of a conventional router, such as expensive cryptographic operations, file caching, or database lookups. Performing these slow and expensive tasks in an overlay keeps them off of routers’ critical paths. The ability to perform these tasks enables the creation of powerful new facilities such as scalable, distributed publish-subscribe systems and content distribution networks.

3. Sample Overlays

Multicast overlays constitute one of the earliest uses of modern routing overlays. They have proven effective at providing wide-area multicast systems; one such system [3] is used to broadcast the annual ACM SIGCOMM conference. End-system multicast systems recruit multicast receivers to rebroadcast their streams to a few other receivers while attempting to create an inter-receiver topology that minimizes the number of duplicate packets sent. End-system multicast successfully demonstrated that overlays could perform some routing functionality nearly as well as the Internet itself—and with a much easier deployment path.

Many peer-to-peer systems, both research and commercial, have an overlay network at their core. Peer-to-peer overlays (for instance, Gnutella) use limited-hop random routing to perform searches on the overlay, whereas structured overlays, like Chord [4], impose a well-defined namespace on the overlay, and use this structure to speed up certain types of queries. Many of these structured overlays present a hash-table-like “get(key) / set(key, value)” interface; they are called distributed hash tables (DHTs).

One focus of my own research is the use of overlay networks to improve the failure resilience of the Internet. A RON can be deployed between a group of cooperating end-hosts, without modification to the underlying Internet. The RON project showed that overlays can not only provide different functionality, but they can also improve upon the performance of the Internet. Our measurements of RONs indicate that about five percent of the time, the end-hosts can find a better route via each other than via the normal path provided by the Internet. Using these techniques, RONs can avoid around 50 percent of Internet outages.

4. Going Forward

Overlays will become firmly entrenched in the toolbox of solutions to networking problems—and we’ve only seen the start of the applications they’ll enable. Researchers have already started to blur the distinction between overlay networks and routing protocols, proposing control overlays that would replace many of the functions currently handled by the border gateway protocol (BGP) backbone routing protocol in today’s Internet [5], enabling new “intelligent” routing capabilities such as automatic detection and squashing of computer worms.

DHT developers hope to scale their systems to hundreds of millions of entries that can be concurrently accessed by millions of clients, providing a massively scalable substrate for building large distributed systems. By exploiting the large, flat namespace provided by DHTs, others have proposed approaches that would allow for persistent naming of objects (Web pages, email addresses, and so on) while “untangling” these objects from the domain name system (DNS) and its attendant political and legal complications. A recent proposal even suggested using a DHT as a new, fundamental basis for managing service naming and connection management [6].

However, overlays create their own set of challenges. Because they do not control the physical links themselves, routing overlays typically probe the network to measure link properties, such as available bandwidth or packet loss rate. It is often difficult to accurately evaluate network properties; improving these techniques is an ongoing focus of the Internet measurement community. More worrisomely, if hundreds of routing overlays coexist on the Internet, we need mechanisms to ensure that they do not overwhelm the network with redundant measurement traffic. Overlays also present new security issues for researchers and security administrators. In the same ways that overlays can be used to circumvent censorship, they can be problematic for firewalls: Can firewalls screen overlay traffic in a way that preserves their utility, while preventing abuse and keeping unwanted traffic out?

The challenges posed by overlays are not limited to routing overlays. Storage and lookup overlays like DHTs present the possibility of huge, communal storage resources. How should DHTs ensure fairness among participants, so that rogue users (termed “freeloaders”) are prevented from using petabytes of storage and providing no value in return? Similar problems are faced by file-sharing overlays like Gnutella, which have yet to find a good solution to the problem of freeloading. Researchers also face an interesting trust barrier for adoption of extremely large-scale overlays: In one project at MIT, even extremely technically savvy users did not trust that their data, no matter how strongly encrypted, could be securely stored on an untrusted network of other people’s machines.

Hopefully, we will see solutions to these problems, along with a host of new applications developed using overlay networks—in diverse areas such as content distribution, conferencing, and gaming—that will improve how we work, travel, and play.

Created: Sep 22 2004 Last updated: Jun 15 2007 Archived: Feb 5 2013