A substratum of distributed systems with millions of autonomous computers

Overlay networks employ routing algorithms over an underlying network, such as the Internet. They support advanced features, such as content search, ID-based messaging, and multicasting. Several routing algorithms have been proposed, but few have been implemented on the Internet because of the difficulty of applying practical software.

Tokyo Tech's Kazuyuki Shudo and his colleagues have discovered a software structure that facilitates the implementation of a routing algorithm. And they have deployed the structure in a software framework that they call Overlay Weaver. Their software framework allows for implementing routing algorithms in just a few hundred lines of code. Researchers in at least 15 nations use the software structure and Overlay Weaver.

An algorithm researcher can compare a new algorithm with implementations, included in the software, of well-known algorithms, such as Chord, Kademlia, Koorde, Pastry, and Tapestry. In addition, the researcher can test her or his algorithm with hundreds of thousands of virtual nodes on a single computer, and the algorithm implementation works on the Internet.

K. Shudo, Y. Tanaka, and S. Sekiguchi
Computer Communications, Vol. 31, Issue 2, pp. 402-412 (2008)
Department of Mathematical and Computing Science

• 

  The route on an overlay network portrayed here consists of more than 500 computers

• 

  The diagram shows visualized routes and multicast delivery trees established with the software structure discovered by Shudo and his colleagues.