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_{b}N
= 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
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.