Overlay Networks

1.

2.

A logical network built on top of a physical network

• Overlay links are tunnels through the underlying network

Many logical networks may coexist at once

• Over the same underlying network
• And providing its own particular service

Nodes are often end hosts

• Acting as intermediate nodes that forward traffic
• Providing a service, such as access to files

Who controls the nodes providing service?

• The party providing the service (e.g., Akamai)
• Distributed collection of end users (e.g., peer-to-peer)

Overlays

P2P systems possess some degree of self-organization 

• each node finds its peers and helps maintain the system structure

Two types of overlays connect most P2P systems

Unstructured

• No infrastructure set up for routing
• Random walks, flood search

Structured

• Small World Phenomenon: Kleinberg
• Set up enough structure to get fast routing
• We will see O(log n)
• For special tasks, can get O(1)

Overlays: Unstructured

From Gribble

• a common unstructured overlay
• look at connectivity
• more structure than it seems at first

Gossip: state synchronization technique

• Instead of forced flooding, share state
• Do so infrequently with one neighbor at a time
• Original insight from epidemic theory

Convergence of state is reasonably fast

• with high probability for almost all nodes
• good probabilistic guarantees

Trivial to implement

• Saves bandwidth and energy consumption

Overlays: Structured

Need to build up long distance pointers

• think of routing within levels of a namespace
• eg. namespace is 10 digit numbers base 4
  • 0112032101
• then you can hop levels to find other nodes

This is the most common structure imposed