Structured and Unstructured
Overlay Networks
Kazuyuki Shudo / 首藤 一幸, Ph.D.
Tokyo Institute of Technology (Tokyo Tech)Overlay• An network constructed overanother network– e.g. Internet over a telephone network– e.g. Networks of file sharing programs

Overlay• FastTrack, eDonkey2K, Gnutella, …
• with more than 1,000,000 nodes.

• Application-level network– constructed in a autonomic anddecentralized way to keep performanceand fault-tolerance with 1,000s and1,000,000s nodes.

• Its topology is independent from theunderlying network (i.e. Internet).
– Then, called Overlay Network orNetwork Overlay.

RouterPhysical Network

Unstructured and Structured• Unstructured overlay– e.g. Gnutella network, Winny network– No (few) constraint imposed on which node to be a neighbor(topology).
– An existing object on it may be found.
– Generally, less-efficient but supports flexible (e.g. range) search.

• Structured overlay– e.g. A network for distributed hash table (DHT)– An algorithm-based constraints imposed on which node to be aneighbor.
– An existing object on it is (almost) certainly found.
– Generally, efficient but it has been said to be weak in flexible
search.

Overlay-related activities
I will demonstrate today• Peer-to-peer live streaming– Application-level/layer multicast (ALM),
Overlay multicast (OM)

– Started at Utagoe in 2006
– Unstructured overlay network• Overlay Weaver: an overlay construction
toolkit– Started at AIST in 2005
– Structured overlay network

Peer-to-peer live streaming
An example of unstructured overlay

P2P Content Delivery• Gathering technologies– Download– On-demand streaming• Playing while downloading.

– Gather parts of contents replicated in advance.
– “Swarming”• Disseminating technologies

Audience

Source– (Live) streaming– Deliver content to massive number ofaudiences in a short time.
– “Application-{level, layer} Multicast (ALM)”,“Overlay Multicast”, “Endsystem multicast(ESM)”
Massive audiences

Dissemination: ALM, OM, ESM

Tree-based vs. Mesh-based
SourceSource(2) Data

Data(1) Request

neosihT

Deliverytree• Tree-based–––––

Data flow along the delivery tree constructed
explicitly.
Push from the root toward leaves.
△ Requires quick repair in node failure○ Data reach all ends, with low latency.
Exploits broadband links.

• Mesh-based–––––Keeps loose relationships with neighbors.
Pull data from neighbors.
○ Robust to node failure by nature△ Delivery to ends not guaranteed.
To be compensated.
Exploits narrowband links.

(Live) streaming• From 90 to 95 % of traffic reduced around the source– With Utagoe’s UG Live software

On Nov 26, 2007,“access talk-about live”

by J-Stream,
Castella (www.castella.jp),
and Utagoe

91-93 %
reduceduser-side
Over 90%
reduction
lastedserver-sideApplication

Nikkei CNBC broadcasting (from March 24 to 28, 2008)delivered by TV Tokyo Broadband Inc. and Utagoe Inc.

Simultaneous with TV

Application

CD quality music
Radio broadcasting (from June 2 to 30, 2008)delivered by NIPPON BROADCASTING SYSTEM, Impress Imageworks, J-Stream and Utagoe

Overlay Weaver:
An Overlay Construction Toolkit

An example of structured overlay

Overlay Weaver• We see analogies between
structured overlays andweaving.
– Chord, Tapestry, ...

• Overlay Weaver– A weaving device of (structured)
overlaysWeaver

Logotypes of Chord and Tapestry

Overlay Weaver• DHT Library• Properties– supports application-layer/level– in Java
multicast (ALM), not only DHT.
– about 23,000 steps– supports multiple routing algorithms:
Chord, Kademlia, Koorde, Pastry, Tapestry,– licensed under Apache • …
License 2.0– We can conduct experiments without• ready to be applied tovarious purpose.

writing code.
• Operation with sample tools such as DHT
shell and Mcast shells.
• Measurement of # of messages, # of hops
and … with Emulator.

150,000 nodes on a single PC.
Overlay
Visualizer– A DHT is accessible via XML-RPC-basedprotocol.
• the same protocol as Bamboo andOpenDHT.

Overlay Weaver as an Open Source Software• http://overlayweaver.sf.net/ (SourceForge)– released on 17th Jan, 2006.
– Apache License 2.0• Statistics (as of 10:10, 5th Dec, 2008)– 11,420 downloads– # of subscribers of mail lists• English: 80, Japanese 86– # of members of the mixi community: 152• As a research platform– Used in Brazil, Russia, UK, Hungary, …
– Third parties implemented routing algos:
Symphony, EpiChord, …

– Many use cases:
RDF DB (AIST), XML search (Tsukuba U.), # of replicas (U Federal do
Rio Grande do Sul), Search over multiple servers (Ochanomizu U.),Web access investigation (TITECH), Replica placement (Waseda U.),
User mgmt server (Hitachi), Multi-attribute range search (NEC), …

Web siteAs a research platform• Evaluation and improvement ofchurn tolerance– Shudo, “Churn Tolerance Improvement
Techniques in an Algorithm-neutral DHT”,
IPSJ ACS journal, March 2008.

• Collective forwarding– Shudo, “Collective Forwarding on StructuredOverlays” (written up)

Operation on PlanetLab• Real experiments are important• As a proof of …
– Just for fun ☺

• PlanetLab: a globe-scale testbed– Currently consists of 931 nodes at452 sites– An user operates 2 PCs and can use
the testbed• 561 Overlay Weaver nodes in 35
countries (at most).

Web interface of a nodeOverlay Visualizer• Shows nodes, message deliveries and delivery
tree for multicast on the fly.
• Works both on a real network and a distributed
environment emulator.

Future work
• Unstructured overlays– Are technologies to select “near” peers consistent
with ISPs and carriers’ interests?
• e.g. P4P, IETF ALTO WG• Utilizes routing information like AS numbers– Install-less peer-to-peer systems• Structured overlays– Cloud backends with structured overlays• e.g. Microsoft’s Azure Services Platform• In-memory cache, pub-sub support, distributed computation– ID/Locator separation with structured overlays• e.g. i3, HIP with DHT, PIAX group’s activity

Spare slides

Web interface of a node
• A node specification

• A routing table for Chord

Web interface• Put, get and remove an item to a distributedhash table (DHT)Web interface• A result of a get request to a DHT

Resources utilization of PlanetLab• CoVisualize