review of Geometry

This paper aims to explore the relation between DHT routing geometry and
the effects on resilience and proximity properties. Geometry is important
and interesting to study because it captures the routing flexibility which
leads to shorter and reliable paths. The authors review several DHTs,
including Tree, Hypercube, butterfly, Ring, and XOR. They compare all
these approaches in terms of neighbor selection, routing selection and
their support for sequential neighbors.

They draw the conclusions based on their solid evaluations. First, among
all the geometries, The Ring performs the best for static resilience,
which indicates how well the network routes before failures are recovered.
Supporting sequential neighbors could further improve the resilience.
Second, DHTs are designed to provide efficient routing. The goal is to
minimize end-to-end overlay path latency, not just the number of hops. PNS
is more important than PRS to improve the path latency. The performance of
PNS and PRS is independent of geometry. Supporting PNS in geometry is
crucial. Last, local convergence leads to low latency and bandwidth
saving. The result is similar to path latency property. PNS is more
effective than PRS and other properties in geometries could be ignored.

As the authors claim in the paper, their analysis has some limitations.
They do not consider all geometries, they ignore the details of
algorithms, and they only consider latency as performance metric. The
results show that the Ring works well for p2p. It seems that research on
designing more complex and fancy geometry is not urgent and interesting.
Optimizations and more efficient routing algorithms based on the Ring may
be enough for current p2p architecture.

Another problem in DHT routing is how to pick up the entry node. In most
of current DHTs, when a client issues a query, it selects a random (or a
“close”) node and the first node decides the next hop. The potential entry
nodes are not symmetric to a given destination. The selection may affect
the path length and latency. The selection should consider the proximity
properties. When a new node comes, it needs to register in a Bootstrap
node, even though it may be physically close to an existing peer.
Received on Mon Nov 21 2005 - 00:40:55 EST