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
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)
 were designed to provide better resilience to network failures
than Internet routing protocols could; yet others have been used
to provide anonymous communication . 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  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 , 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
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 , 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 .
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
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
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.
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.
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.
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.
Measurement Conference is an annual event sponsored by ACM
SIGCOMM, in cooperation with USENIX.
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.
overlay networks Andersen D., Balakrishnan
H., Kaashoek F., Morris R. ACM SIGOPS Operating Systems Review
35(5): 131-145, 2001
overlay networks: SLAs, QoS, and bandwidth provisioning
Duan Z., Zhang Z., Hou Y. IEEE/ACM
Transactions on Networking 11(6): 870-883, 2003.
||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),
||Dingledine, R., Mathewson, N., Syverson, P. Tor: The
second-generation onion router. In Proc. of
the 13th USENIX Security Symposium (August 2004), pp.
||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.
||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),
||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.
||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.