Means for Peer‐to‐PeerResearch
Kazuyuki Shudo

DAS‐P2P 2007, January 16, 2007

Requirements• Peer‐to‐peer algorithms and systems …
– involve massive number of nodes.
• To 1,000,000s or more.

– required to work in real environment.
• i.e. on Internet, ad‐hoc wireless network, …

• Researchers and developers want/have toconfirm/prove scalability and practicalityof their idea or software. They have …
– a paper to be accepted– software to launchExperiments• Some experiments required to confirm/provescalability and practicality.
– even only to convince a reader, especially a reviewer ☺

• Various means to make experiments have its own
strengths and weaknesses.
– Means: simulation, …
– Properties: scalability, …

• Software design should reflect what we
confirm/prove because it determines (restrict)means.

Means• (With a piece of paper and a pen)
• Simulation– of an algorithm• Emulation– of a distributed environment / network• On a PC cluster / LAN– e.g. StarBED, …

• On a wide‐area testbed– e.g. PlanetLab, XXX Grid, …

• Normal use– by the developer, friends or customers.

Properties of each means• Normal use

PracticalRapid experiments• Wide‐area testbed

Resource‐available• PC cluster / LANControllable• Emulation

Scalable• Simulation

Properties of each means• Simulation• Emulation

PersonalMeans
Professional(difficult for an amateur)• PC cluster / LAN• Wide‐area testbed• Normal use

MeansSimulation vs. Emulation• Simulation of an application / algorithm– A simulated appl / algo generally does not run on areal network.

• Emulation of a distributed environment– An emulated network hosts real applications.
Simulated
Application
Simulated
Network(Real)
Application
Emulated
NetworkSimulation Emulation

RealNetwork

Simulation vs. Emulation• Strength of each means:Simulation

Emulation•Scalability: more nodes / PCs•Reality–with less resources.

–A real app instances run.

•Performance•Natural programming•Rapid / accurate experiments• A simulated appl / algo is more lightweight than real software.
– A real appl is tied to (heavy) OS resources such as processes and threads.

• It is not necessary for a simulated clock to be bound with a real clock.
– Faster experiments and accurate simulation for a longer time.

• But it is difficult for simulation to be compatible with naturalprogramming.

– e.g. A sim. does not allow new Thread() and new Socket() in Java.
– A sim. requires its own dedicated manners to write code for it.

Scalability: Examples• Simulation‐ 1,000,000 nodes– p2psim (MIT): 3,000 nodes on a single PC• “we simulate Chord with 3000 nodes in a very reasonable amount of time.”– OverSim (U. Karlsruhe): 10,000 nodes in a Chord network on a single PC– PIAX: 300,000 nodes on a single PC• implements Skip Graph to support location‐based (2‐D range) search.
• Runs on a real network• Emulation‐ 10,000 nodes– ModelNet (Duke U.): 1,000 DHT nodes on 40 PCs (in a Bamboo paper)• An Internet emulator imposing network topology, wide‐area delay andbandwidth restrictions.

– Overlay Weaver (AIST, Kazuyuki Shudo): 4,000 nodes on a single PC• supports DHT and ALM as services, and Chord, Kademlia, Koorde, Pastry
and Tapestry as overlay algorithms.
• # of nodes limited by # of threads Linux kernel supports.

– peeremu (NEC): 1120 nodes = 80 nodes x 14 PCs• supports packet delay / loss.

Scalability: an open problem• Generally,– 100 nodes run fine but 1000 nodes …
– 1000 nodes run fine but …

• In the first place, what you see with X nodes?
– Is a 1,000,000 nodes experiment better than 1,000
nodes one? What is the difference?
– Is larger better?
– Countermeasures:• Clarify relationships between a scale and its characteristics.
• Set the number based on a real numbers.
– E.g. 40 millions households in Japan.

• Do not mention ☺

Research tools(Usual) Application

Simulator

Emulator

Application

p2psim, PeerSim, OverSim, … ModelNet, peeremu, …

A model of peer‐to‐peer research tools

Simulated
Application
Simulated
Network(Real)
Application
Emulated
Network

Simulation Emulation

RealNetwork

Research tools
Overlay Weaver
Structured overlay
Lightweight
Emulator

A modelSimulated
Application
Simulated
Network(Real)
Application
Emulated
Network

Simulation Emulation

RealNetwork

Messaging
NetworkNatural programming isvery important in OW.

Bamboo DHT, PIAX, …
Distributed hash table
Event‐driven API
Simulator

Internet emu.

Network•Supports both simulation and emulation.
•At the cost of special manners in programming.

Research tools
Simulation

Normal use (and emulation)

BothWhich one is your software?
•Each one has its advantages and disadvantages.
•Fixed at an early stage of software design and to be considered carefully.
A modelSimulated
Application
Simulated
Network(Real)
Application
Emulated
Network

Simulation Emulation

RealNetwork