Computer Networks · free preview

Overlay Networks

When the network will not change fast enough, the answer is an overlay, a network built on top of the network, nodes connected by tunnels through the existing Internet running their own routing on top, from virtual private networks that stitch sites together, to resilient overlays that reroute around failures faster than the infrastructure can, to peer-to-peer networks that locate objects and route to nodes with no central server, first by flooding, then by distributed hash tables that assign keys to nodes by consistent hashing and route lookups in logarithmic hops, and finally to content distribution networks, which scatter cached server surrogates near clients and steer requests to them, three ways the application layer reinvented the network without asking it.

1. A Network on Top of a Network

A Network on Top of a Network

2. Finding Things Without a Directory

Finding Things Without a Directory

3. Swarming the Scarce Pieces

Swarming the Scarce Pieces

4. Caching as a Business

Caching as a Business

5. The overlay argument

Why do new network capabilities so often arrive as overlays first?

6. The resilient detour

What does a resilient routing overlay buy its participants?

7. Why flooding failed

Why did flooding-based peer-to-peer search not scale?

8. The circle of keys

In a DHT, what does consistent hashing guarantee as nodes join and leave?

9. The doubling rule

How does a DHT route a lookup in $O(\log n)$ hops?

10. The DNS sleight of hand

How does a CDN steer a client to a nearby surrogate?

11. The encapsulated path

What do overlay nodes call the encapsulated paths through the underlying network that serve as overlay links?

12. The stable mapping

What hashing scheme maps nodes and keys onto one identifier circle so churn disturbs only immediate neighbors?

13. The shortcut table

What per-node structure of doubling shortcuts around the identifier circle gives DHTs logarithmic routing?

14. The renamed cache

What does a CDN call its edge caches that stand in for the origin server?

Practice this interactively

Free account · instant grading · spaced review that schedules itself.

Start this course for free