While building an experimental application using a .NET implementation of Chord (link), I wanted to verify that my Chord implementation performed as well as the MIT implementation in terms of number of hop-counts under churn, etc.
Initially, I used a simple tool to generate a text-based map and hopcount table of the system. This worked well for smaller rings (generally where the number of nodes was no more than the number of columns in my console display), and the output table had a somewhat mesmerizing quality to the patterns in outward hop-counts from each node.
To allow for larger rings to be mapped and analyzed, I decided to provide both a text-based and image-based output for the mapping tool. The maps are inspired by both topographic maps and weather radar maps typically seen on television. These maps concentrate information in a way that remains true to the Chord implementation, and in a manner that is familiar and intuitive to human viewers - this combination allows for fast, striking analysis of a Chord ring and provides for compact, meaningful visual comparisons between different experimental implementation variations and techniques.
Below are a few basic examples of the topo maps that were generated on two larger Chord rings with relatively orderly node ID distribution over a 64-bit identifier space (thus a 64-entry finger table) and a successor list size of log(2)(number_of_nodes).
Some example topo maps.
Color
palette for routing maps. Color Hop Count Color Hop Count Color Hop Count black 0 dkblue 5 red 10 ltgray 1 ltgreen 6 maroon 11 dkgray 2 green 7 violet 12 ltblue 3 ltyellow 8 plum 13 blue 4 yellow 9
756-Node System:
The maps above were generated on a 756-node stable Chord ring running on 36 distinct physical 2CPU servers in a single two-sided cabinet. 21 instances of Chord were running on each node in order to demonstrate a 756-node ring.
The maps above were generated on a 5004-node stable Chord ring running on 36 distinct physical 2CPU servers in a single two-sided cabinet. 139 instances of Chord were running on each node in order to demonstrate the 5004-node ring. Clicking on the images above will provide a larger version of the image (Warning: large download).
Software / Downloads / Documentation.
Map generation source/binaries coming soon.
Diagonal (point-to-point) map of 756-node system.
Sideways (relative-offset) map of 756-node system.
5004-Node System:
Diagonal (point-to-point) map of 5004-node system. [14.3MB]
Sideways (relative-offset) map of 5004-node system. [14.5MB]
NChord - C# implementation of Chord distributed hash table (sources/binaries/documentation).
Andrew Cencini
acencini @ gmail dot com