Overview of Overlay Weaver

[English | Japanese]
last-updated: April 17, 2009

Overlay Weaver is an overlay construction toolkit. It enables overlay designers to implement a structured overlay algorithm only in hundreds lines of code and improve it rapidly by iterative testings on a single computer. The designers can make a realistic and fair comparison between new and existing overlay algorithms, since implemented algorithms are pluggable and the provided emulator can host hundreds of thousands of virtual nodes. Additionally, implemented algorithms work on a real network in addition to the emulator. The toolkit brings results of algorithm researches to applications directly.

Table of Contents


The toolkit consists of runtime and the following tools.
Each word between parentheses is a name of a command located under bin directory. The toolkit contains the following sample applications.


Fig. 1 shows components organizing the runtime. The routing layer is corresponding to key-based routing layer (Fig. 2) in a proposal by Dabek and et al [1]. But it has been decomposed into three parts in this toolkit, Routing Driver, Routing Algorithm and Messaging Service. This decomposition enables us to implement a number of well-known overlay algorithms only in hundreds lines of code. The toolkit currently has implementations of Chord, Kademlia, Koorde, Pastry, and Tapestry. Additionally, the decomposition allows multiple implementations of the Routing Driver and the toolkit provides Iterative and Recursive (Fig. 3) [2] Routing Driver.

Fig. 1: Components organizing runtime of Overlay Weaver.

Fig. 2: Key-based routing (KBR) (cited from the paper [1]).

Fig. 3: Routing styles.
Other components also have multiple implementations.
Messaging Service has the following 4 implementations. Directory Service has the following 3 implementations.

Higher-Level Services and Sample Applications

On the routing layer, higher-level services are implemented. Applications usually rely on them. The toolkit provides multicast (Mcast) in addition to distributed hash table (DHT) as higher-level services. The Mcast multicasts over an overlay. It allows a user to join and leave a group specified by an ID, and multicast messages to the group. It can also notify an application of topology of a spanning tree on which a multicast message is transferred. A sample application, IPv4 multicast router uses this function.

DHT shell and Mcast shell are sample applications implemented on corresponding services. They read commands from a character terminal or network and control the underlying services directly. They can be used with the emulator together to test and compare overlay algorithms.

DHT shell also accepts queries in an XML-RPC protocol. The protocol is compatible with Bamboo [4] and OpenDHT. Accordingly, an application works with Overlay Weaver if it supports Bamboo and OpenDHT.

Distributed Environment Emulator

The toolkit provides Distributed Environment Emulator, which can host tens of thousands of nodes on a single computer virtually. Overlay designers can improve rapidly their algorithm implementations by testing them iteratively on the emulator. They can also make a large-scale and fair comparison between new and existing algorithms on the emulator. Additionally, implemented algorithms work on a real network in addition to the emulator. The toolkit brings results of algorithm researches to applications directly.

Fig. 4 shows structure of the emulator. There are two modes in which it runs. In the normal mode, the whole emulator runs on a single computer. In the other mode, multiple computers form a single emulator in cooperation. The emulator reads the same scenario file in both cases and invokes and controls application instances according to the scenario.

Fig. 4: Structure of emulator.

The toolkit has a simple Emulation Scenario Generator and a user can generate a scenario file with it. Of course, the user can write a scenario by hand, or collect a trace from by running an existing application and translate it into a scenario.

Overlay Visualizer

Overlay Visualizer is a tool which visualizes communication between nodes just in time. It works both on an emulator and a real network because it collects communication statistics via Messaging Service itself of the toolkit.

Fig. 5 shows screenshots of this tool and "Screenshots and Demo" page has more images. A node is projected on a circle, a straight line and so on, and its position depends on its ID. When nodes communicate, an arc is drawn between the nodes. Spanning trees constructed by Mcast are also drawn with colored lines.

Fig. 5: Screenshots of Overlay Visualizer.


[1] Frank Dabek, Ben Zhao, Peter Druschel, John Kubiatowicz and Ion Stoica, "Towards a Common API for Structured Peer-to-Peer Overlays", Proc. the 2nd International Workshop on Peer-to-Peer Systems (IPTPS'03), February 2003.
[2] Sean Rhea, Dennis Geels, Timothy Roscoe and John Kubiatowicz, "Handling Churn in a DHT", Proc. 2004 USENIX Technical Conference (USENIX '04), June 2004.
[3] "Berkeley DB Java Edition", http://www.oracle.com/database/berkeley-db/.
[4] "The Bamboo Distributed Hash Table", http://bamboo-dht.org/.

Return to Documents page
Return to Overlay Viewer main page