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.
Fig. 1: Components organizing runtime of Overlay Weaver.
Fig. 2: Key-based routing (KBR) (cited from the paper ).
Other components also have multiple implementations.
Fig. 3: Routing styles.
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  and OpenDHT. Accordingly, an application works with Overlay Weaver if it supports Bamboo and OpenDHT.
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 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.