Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Current Hot Topics

This topic was archived on February 5, 2013, and is therefore closed to future updates.

  Overlay Networks: Networking on Top of the Network  

David G. Andersen
Carnegie Mellon University
Pittsburgh, Pennsylvania


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:

Routing overlays attempt to enhance or replace the routing performed by the underlying Internet, to provide new functionality or improved service.

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--like Akamai, Chord, and many popular peer-to-peer systems--focus on techniques to harness the power of large, distributed collections of machines.

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.

Figure 1: An overlay network routes data between end-hosts on the Internet. In this figure, an Internet failure prevents the host in Boston from communicating with the host in Seattle. The RON overlay detects this outage by measuring the quality of paths between its nodes. RON then sends the data to a peer host (for instance, the Houston node), which relays it around the failure. The clouds in this figure represent some of the large ISPs that make up the Internet backbone.

Another benefit of overlays is that they avoid burdening the underlying network with features better performed at higher layers. For example, content routing requires that the content routers “understand” the application protocols that run through them. Augmenting core routers with application-specific knowledge would burden them with processing needed only by a small fraction of the traffic that passed through them, and force them to undergo frequent updates.

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

  Web pages

GENI: a new National Science Foundation (NSF) initiative that will combine new architectures (such as new wireless and optical technologies) with overlay routing to explore and deploy a broad spectrum of new networking technologies.

Project IRIS: a multi-university National Science Foundation (NSF) project that aims to use overlay networks to increase the resilience of the Internet to failures and malice.

TOR: a publicly accessible overlay network that provides anonymity to its users by encrypting and routing their requests through a number of peer nodes to disguise the real origin of the traffic.

PlanetLab: a large network of Internet-connected hosts that provides an environment in which to test—and deploy—large-scale network services. Much current overlay network research is conducted on top of PlanetLab.


Resilient overlay networks Andersen, D., Balakrishnan, H., Kaashoek, F., Morris, R. SOSP ’01

A layered naming architecture for the Internet Balakrishnan, H., Lakshiminarayanan, K., Ratnasamy, S., Shenker, S., Stoica, I., Walfish, M. SIGCOMM ’04

Technology challenges for virtual overlay networks Birman, K.P. IEEE Transactions On Systems Man And Cybernetics Part A-Systems And Humans

Tor: the second-generation onion router Dingledine, R., Mathewson, N., Syverson, P. USENIX Security Symposium ’04

Mbone: the multicast backbone Eriksson, H. Communications of the ACM

The case for separating routing from routers. Feamster, N., Balakrishnan, H., Rexford, J., Shaikh, A., Van der Merwe, K. SIGCOMM ’04

A case for end system multicast Hua Chu, Y., Rao, S. G., Zhang, H. SIGMETRICS ’00

Chord: a scalable peer-to-peer lookup service for Internet applications Stoica, I., Morris, R., Karger, D., Kaashoek, M. F., Balakrishnan, H. ACM SIGCOMM ’01


Computer networks: a systems approach (3rd ed.) Peterson L., Davie B.S., 2003.


Internet Measurement Conference is an annual event sponsored by ACM SIGCOMM, in cooperation with USENIX.

USITS is a regular USENIX Symposium on Internet Technologies and Systems.

IPTPS is an annual conference that focuses on the state-of-the-art in peer-to-peer computing.


Resilient overlay networks Andersen D., Balakrishnan H., Kaashoek F., Morris R. ACM SIGOPS Operating Systems Review 35(5): 131-145, 2001

Service overlay networks: SLAs, QoS, and bandwidth provisioning Duan Z., Zhang Z., Hou Y. IEEE/ACM Transactions on Networking 11(6): 870-883, 2003.

1) Andersen, D. G., Balakrishnan, H., Kaashoek, M. F., Morris, R. Resilient overlay networks. In Proc. 18th ACM Symposium on Operating Systems Principles (SOSP) (Banff, Canada, Oct. 2001), pp. 131–145.
2) Dingledine, R., Mathewson, N., Syverson, P. Tor: The second-generation onion router. In Proc. of the 13th USENIX Security Symposium (August 2004), pp. 303—320.
3) Hua Chu, Y., Rao, S. G., Zhang, H. A case for end system multicast. In Proc. ACM SIGMETRICS ’00 (Santa Clara, CA, June 2000), pp. 1–12.
4) Stoica, I., Morris, R., Karger, D., Kaashoek, M. F., Balakrishnan, H. Chord: A scalable peer-to-peer lookup service for Internet applications. In Proc. ACM SIGCOMM ’01 (San Diego, CA, Aug. 2001), pp. 149--160.
5) Feamster, N., Balakrishnan, H., Rexford, J., Shaikh, A., Van der Merwe, K. The case for separating routing from routers. In ACM SIGCOMM ’04 Workshop on Future Directions in Network Architecture (Portland, OR, Sept. 2004), 5--12.
6) Balakrishnan, H., Lakshiminarayanan, K., Ratnasamy, S., Shenker, S., Stoica, I., Walfish, M. A layered naming architecture for the Internet. In Proc. ACM SIGCOMM ’04 (Portland, OR, Aug. 2004), pp. 343–352.
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2017 ThinkLoud, Inc.
Terms of Use
| Privacy Policy