A Decentralized Directory Service for Peer-to-Peer-Based Telephony - Cloud, Grid and High Performance Computing: Emerging Applications - page 341

Table 1. Lookup operations

SCHN* OLPP*

N=5 n=13 n=26 n=5 n=13 n=26

M=50 1068 958 495 99 3 4

M=100 590 670 279 39 3 4

4683 entries, and OLPP* yielding only a single
entry. Of course querying SCHN* is an artificial
example, as real-world applications would prob-
ably abort that query after a certain number of
results is retrieved, and ask the user to formulate
the query more specifically. Table 1 shows the
number of lookup operations. We did not use
any caching.
An increasing maximum load of the root node
m results in less nodes to be looked up. With
regards to the number of children n we found that
more children per node result in a lower number
of lookup operations. For example, if the user
searches for OLPP* in a tree with n=5, the ap-
plication searches all entries matching the prefix
[K-O][K-O] [P-T] [P-T]. People with a last name
starting with Lost would match the same prefix
as Olpp. Altogether, the number of matching
entries in our phone book is 1801, which explains
the overhead of 99 lookups.
These results suggest that the number of chil-
dren per node n should be as large as possible to
reduce the number of lookup operations.

However, even with n =26 we got only 60%
empty nodes, which is still justifiable in the face
of the great reduction of traffic overhead for n =26.

Churn

In peer-to-peer terminology, the continuous ar-
rival and disappearance of peers is called churn.
The stability of DHTs in the face of churn and the
probability of data loss was addressed many times
before (Stutzbach 2006, Kunzmann 2009), and we
refer the reader to these works for experimental
and analytical results on the topic.
The tree nodes of the EPHT are stored as re-
sources on a DHT. DHTs use replication techniques
and stabilization protocols to keep the probability
of data loss very low, even in typical file-sharing
scenarios where the participating peers arrive and
disappear very frequently.
The reliability of the EPHT depends on the
reliability of the underlying DHT. If the node
resources are available on the DHT layer, then
the EPHT remains stable. Assuming that VoIP
telephones have much longer average online times
than file sharing peers, we expect the DHT to be
very stable in the distributed phone book scenario.
However, in order to handle the unlikely event
of data loss, we propose that the peers look up their
own entry on a periodical basis, and re-publish
the entry in case it disappeared.

Empty Nodes

The percentage of empty nodes is shown in Table 2.
As expected, the number of empty nodes
raises with the number of children per node.

Table 2. Empty nodes

CONCLUSION

n=5 n=13 n=26

m=50 6% of 34,821 37% of

94,297

60% of
193,801

In this article, we presented the Extended Prefix
Hash Tree as an infrastructure supporting range

m=100 2% of 18,353 29% of

48,757

53% of
98,501