DAS‐P2P 2007, January 16, 2007

Overlay Weaver:
An Overlay Construction Toolkit
Kazuyuki Shudo

http://overlayweaver.sf.net/

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 and
1,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

target– e.g. Network for distributed hashtable (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 Weaver• We see analogies between
structured overlays andweaving.
– Chord, Tapestry, ...

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

WeaverLogotypes of Chord and Tapestry

Overlay Weaver• DHT Library• Properties– supports application‐layer/level– in Java
multicast (ALM), not only DHT.
– about 20,000 steps– supports multiple lookup– licensed under Apache algorithms:• Chord, Kademlia, Koorde, Pastry,
License 2.0• ready to be applied tovarious purpose.

Tapestry, …

– We can conduct experiments
without writing code.
• Operation with sample tools such as
DHT shell and Mcast shells.
• Measurement of # of messages, # ofhops and … with Emulator.

OverlayVisualizer– A DHT is accessible via XML‐RPC‐
based protocol.
• 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 19:00, 14th Jan, 2007)– 4,495 downloads– # of subscribers of mail lists• English: 54, Japanese 71– # of members of the mixi
community: 122• Expected users– Algorithm designers– Application developer• P2P storage of RDF documents byDr. Matono (AIST)Web siteProblems of overlay research• Distance between algorithm research andapplications– Research implementations are often only for
simulation to ensure its scalability.

• Much work to implement an algorithm– At least, 1,000s lines of code.
– hard to debug because of the nature of a large‐scale
distributed system.

• Difficulty in fair and realistic comparison
between algorithm implementations– often simulated. e.g. p2psim.
– But, system behavior is heavily implicated in how it isimplemented. Comparison of real impls is important.

Overlay construction toolkit• Connects algorithm research toapplications directly.
– Once an algorithm is implemented, it can beemulated and also works on a real network.

• In Java, in natural programming: can write new Thread()• 4,000 nodes emulations and 200 nodes experiments on a PC
cluster have been conducted.

– We can design, implement and verify an algorithmwith Emulator and the resulted implementation
works on Internet.

• Related work – different approaches• Bamboo, PIAX: supports both simulation and real‐network,and needs special programming with an event‐driven style.

Overlay construction toolkit• Facilitates algorithm implementation.
– We could implement well‐known 5 algorithms just in
100s steps.
• Chord, Kademlia, Koorde, Pastry and Tapestry.
– And 2 variations of Chord• Chord impl is 619 steps and Pastry impl is 872 steps in Java.

– Rapid development and quality improvement withEmulator, which enables emulation with 1,000s nodes.

• Related work – different approaches• MACEDON: introduces an overlay describing language.
• P2: introduces declarative overlay describing language
OverLog.

Overlay Construction Toolkit• Enables fair and realistic comparison between
algorithm implementations.
– Multiple algorithm implementations share OW
components (e.g. communication).
– Runs both on an emulator and on a real network.

‐> fair and realistic comparison
Approaches to comparison between algorithm implementations(dedicated)
Algo impl.

Application

OW components

NetworkSimulator

NetworkEmulator

Simulator

Emulator

Fair, but not realistic

Algo impl.

RealNetwork

OW’sEmulator

Overlay Weaver (OW)

Appl, not algo, compared

Fair and realistic

Overlay Weaver: Background• Separation of lookup (routing) layer and higher‐levelservices [Dabek03]– Frank Dabek et al., “Towards a common API for Structured Peer‐to‐PeerOverlays”, Proc. IPTPS’03.

• A lookup layer is called key‐based routing layer (KBR).
• Application (Tier 2) and higher‐level services (Tier 1)
can be independent from lookup algorithms (Chord,Pastry, …)
From [Dabek03]
Tier 2

ApplicationCFS

Tier 1Higher‐level services
Tier 0

Lookup (Routing) layer

PASTDHTI3

Scribe SplitStream Bayeux OceanStoreCAST DOLR

Key‐based Routing Layer (KBR)KBR APIDecomposition of lookup layer• Algorithm implementation still needs much work.
– incl. communication and RPC.
• e.g. Chord impl of p2psim has 2,835 steps.

• To be easy
– Not only your algorithm, but also other algos comparedto with your one.

• We factored out common processes to algorithms.
– Further decomposition of KBR layer.

Decomposition of lookup layer• Facilitates algorithm implementation• 2 lookup styles are exchangeable: iterative and recursive
DHTShellContents
sharing

Distributed Grid Info.
File SystemService

McastShell

Application‐level

IP Multicast Contents
distribution
RouterDHT Interface

Mcast Interface

DHTMcastnding
CorrespoPI
to KBR A…

Application
Tier 1Otherservices

Higher‐level services

Routing Service Interface

Tier 0
Lookup (Routing)Routing Driverlayer

Routing Runtime Interface
Directory Service Interface Messaging Service Interface

Directory Service Messaging ServiceStorage

Tier 2Network

Routing Algorithm Interface

Routing Algorithm

2 impls:
iterative /recursive
Just in100s stepsFacilitation of algorithm impl.
• We could implement well‐known 5 lookup algorithms justin 100s lines of code.
• Compared with:– MACEDON: an algo described in the dedicated language andconverted to C++.
– p2psim: in C++. An algo impl does RPC itself ‐> more lines.

Exchangeable lookup styles• Both Iterative / recursive lookup styles workwith each lookup algorithms.
– due to decomposition of lookup layer.
– Each style has its own strengths and weaknesses.
route
(2‐1)

route21

(4)

(2)

(5)

(3)
(1)

3(6)

1(3‐1)

2(3‐2)

3(4‐2)

(2‐2)
(5)

(4‐1)

(1)

00

Iterative lookup

Recursive lookup

Components• Multiple implementations for each component,
can be combined flexibly.
• Routing Driver
DHTShellContents
sharing

Distributed Grid Info.
File SystemService

Mcast
Shell

…

– Iterative– Recursive

Otherservices• Messaging
– UDP
– TCP
– Emulator

Application‐level

IP Multicast Contents
distribution
RouterDHT Interface

Mcast Interface

DHT

Mcast
Routing Service Interface

Routing Driver

3 impls

3 impls

2 impls • Directory

Routing Runtime Interface

Directory Service Interface Messaging Service Interface

Directory Service Messaging Service
StorageNetwork7 impls

Routing Algorithm Interface

Routing Algorithm

Service– On‐memory– checkpointing– Berkeley
DBDistributed Env Emulator• It reads a scenario and invoke and control
multiple application instances.
Write orgenerate
InvokeOutput• Very useful for test anddebug of algorithms.
• Invokes threads for each
instances.

Emulation
Scenario
Parse

Scenario Sequencer
Invoke andControl (Input)

OutputApplication
instance

Inter-NodeCommunication

App.

App.

App. …

Messaging Service (for Emulator)# invoke 1000 instancesclass ow.tool.dhtshell.Mainarg –p 10000
schedule 0 invoke
arg ptp00.hpcc.jp
schedule 500,500,999 invoke# put & getschedule 510000 123 put foo bar 300
schedule 515000 234 get foo

A scenario

Overlay Visualizer• Visualizes nodes, messages and delivery trees for ALM
at runtime.
• Reports of messages are also delivered via MessagingService.
– ‐> Visualizer works both on an Emulator and a real network.

Evaluation• Goals of Overlay Weaver– Connects algorithm research to applications directly.
– Facilitates algorithm implementation.
– Enables fair and realistic comparison between
algorithm implementations.

• Goals broken down
– Algorithm impl facilitated– Supports test of algo impls
with much nodes– Enables fair comparison– Runs on a real network• Means of confirmation– The amount of code
(formerly shown)– 4,000 nodes emulation– 200 nodes experiments
on a PC cluster

4,000 nodes emulation• Possible.
• # of messages measured.
– Scenario: put x 4,000, get x 4,000• Conditions – ancommodity PC––––

3.4 GHz Pentium 41 GB RAM
Linux 2.6.15
Java 2 SE 5.0 Update 6• Note– “Chord (Figure 6)”completes its routing
table when joining.
– Iterative routing.

4,000 nodes emulation• # of hops in lookups measured.
Frequency of each # plotted.
– Scenario: put x 4,000, get x 4,000• Conditions – ancommodity PC––––

1.7 GHz Pentium M
1 GB RAM
Linux 2.6.15
Java 2 SE 5.0 Update 6200 nodes PC cluster• Possible• # of messages measured.
– Scenario: put x 500, get x 500• Conditions – 197 PCsin AIST Super Cluster– 3.06 GHz Xeon
– Linux 2.4.24– Java 2 SE 5.0 Update 6• Note– Graph sways because
measurement interval isshorter.
• Emu: 10 min• PC cluster: 1 min– Iterative routing.

Summary• Overlay Weaver is an overlay construction
toolkit …
– Connects algorithm research to applications
directly.
• Rapid development and tests with Emulator and theresulted implementation runs on a real network.

– Facilitates algorithm implementation.
• Just in 100s steps of code.
• Impls of well‐known 5 algorithm are provided.

– Enables fair and realistic comparison between
algorithm implementations.