The DLG-Hypertree Middleware

The DLG-Hypertree Middleware

Hypertree [1] is a novel interconnection structure which assures low diameter as well as low degree. We utilize the DLG technique [2] on hypertree to implement an overlay middleware, DLG-Hypertree (DH), for our Owlet language. The use of DH is the same as the other two overlays (Chord and FissionE). Users can double-click HyperTree_0-31.bat to test DH on the local machine with 32 nodes (i.e. processes).

The hypertree structure

According to ref [1], let the maximum number of nodes be N = 64, the initial number of nodes be n = 8, and the base be b = 2. Then the depth of the virtual tree is log_bN = 6. And the virtual tree of n = 8 nodes should look like the following figure.

Then, the routing tables of the 8 nodes are:

000000:		100000:
000000	100000	000000	100000
000000	010000	100000	110000
000000	001000	100000	101000
010000:		110000:
010000	110000	010000	110000
000000	010000	100000	110000
010000	011000	110000	111000
001000:		101000:
001000	101000	001000	101000
001000	011000	101000	111000
000000	001000	100000	101000
011000:		111000:
011000	111000	011000	111000
001000	011000	101000	111000
010000	011000	110000	111000

The initial hypertree graph of eight nodes looks like the following figure (a). Clearly it is a 3-regular graph. Then according to ref [2], the initial graph with renaming nodes is depicted in the following figure (b).

DH topology stabilization

Suppose that a new node joins. According to ref [2], the JOIN message would initiate from a seed node (e.g. 0) and stop at the responsible node (e.g. 2). The new topology is shown in figure (c). And the processing for node leaves is an inverse operation of that for node joins. It can be proved that DH has a fixed constant out-degree 3 and a bounded in-degree 1~6.

Topology display

We implemented a display service for presenting an overall view of the DH topology. The topology of a 128-node DH is depicted in the following figure (a).

(a)

DH identifies a node by its IP address and its port. Thus it can also run on a single node with minimum modifications. As depicted in the above figure (b), we run DH with at most 32 processes on a single node of 2GB RAM and Intel P8600 2.4G CPU. At each console for a process we can see the routing table by typing “ht” and “go”, and route to any node by typing “dht.route ‘destination ID’” and “go”. The routing path would be displayed in blue lines, like 620->101->015->154 in the above figure.

Thanks Dr. Dawei Feng for providing the display framework.

(b)

References

[1] S.i Dolev and R. I. Kat, “HyperTree for self-stabilizing peer-to-peer systems,” Distrib. Comput., vol. 20, no. 5, pp. 375–388, Feb. 2008.

[2] Y. Zhang, L. Liu, D. Li, and X. Lu, “Distributed Line Graphs: A Universal Framework for Building DHTs Based on Arbitrary Constant-Degree Graphs,” in Proc. ICDCS 2008.