REVIEW: The Impact of DHT Routing Geometry on Resilience and Proximity

REVIEW: The Impact of DHT Routing Geometry on Resilience and Proximity

The paper assesses the impact of the choice of geometry for a DHT on the
flexibility it provides in terms of neighbour selection and routing
choices as they impact the static resilience and path latency of networks.
It makes a qualitative analysis on the choices available when designing a
DHT. Rather than comparing different DHTs, it dissects these and arranges
into classes based on the geometry of their algorithms and identifies the
properties of interest in each class. The identified geometries are tree,
hypercube, butterfly, ring, XOR and hybrid algorithms.

The paper is unique in its approach as, unlike previous papers, it does
not limit itself to comparing different DHTs but rather identifies and
compares the properties of the DHT's geometry in providing resilience and
routing proximity. It is thus useful for future work in designing new DHTs
as it identifies necessary properties, i.e. it leads to progress in the
area.

The results presented are palpable. The paper identifies the flexibility
provided by each geometry of algorithms as they affect their resilience
and proximity. The tree and XOR algoritms provide much flexibility in
neighbour selection and little flexibility in routing choices, hypercube
provides the opposite, butterfly provides little flexibility in both
selections, and ring algorithms provide both flexibility in neighbour and
routing choices. In addition, the impact of these varying degrees of
flexibility is demonstrated with experimental results. Under node
failures, tree and butterfly, for example, have high path failures. Tree
and hypercube are also shown to increase paths significantly. This shows
that the static resilience of a geometry is largely determined by the
flexibility in routing it offers.

The results also show that proximity in neighbour selection (PNS) is the
most important proximity technique for reducing path latency, regardless
of the geometry of the DHT. In addition, PNS is also important in ensuring
local convergence.

The paper fails to note that the importance of static resilience is
dependent on the available recovery algorithm. With a fast recovery
algorithm static resilience becomes irrelevant.
The origin of the results provided in the discussion of static resilience
(section 3), is not clearly discussed. All we are told is that the authors
"use a 65,536 node network", not knowing whether these are simulation
results and what set up has been used. The credibility of these results is
thus undermined.
Other performance metrics that need to be taken into consideration when
designing a DHT such as communication overhead, storage requirements and
replication techniques should also be compared, and their advantages
identified.
Received on Mon Nov 21 2005 - 10:43:54 EST