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

Figure 7. Addressing nodes

2. A node with that prefix exists and is an
empty leaf node. In that case, the issuer of
the query starts traversing the linked list
until a non-empty member is found. If all
prefixes in the range queried are empty, then
the search was unsuccessful.
3. A node with that prefix exists but is an inner
node. In that case, the prefix was underspeci-
fied, and it must be enlarged by one character.
In the example, the next search string might
be OLPPDH.
4. There is no node with that prefix. This means
the prefix was over-specified, and it must be
shortened by one character. In the example,
the shortened prefix would be OLPP.

In order to decrease latency, the search can
be initialized with several different random pad-
dings in parallel. That way, the linked list can be
traversed starting from different positions at the
same time.

arbitrary nodes directly, using the prefix of the
node as the keyword in the DHT.
Range queries are implemented as follows:
First, the issuer of a query finds a random, non-
empty leaf node lying somewhere in the queried
range. Second, the issuer traverses the linked list
of non-empty leaf nodes to the left and to the right,
subsequently querying the predecessors and suc-
cessors, until all matching entries are retrieved.
Figure 7 shows how an initial non-empty leaf
node is found that can be used as a starting point
for traversing the linked list. We exemplify this
using a search for all people with the last name
'Olpp'.
Make Prefix Length 5. The first step is to pad
the search string with random characters, and to
take the first five characters as an initial prefix to
start with. In the example, the initial prefix would
be OLPPD. In the section on evaluation we will
show why 5 is a good initial prefix length.
Lookup. When this prefix is looked up in the
DHT, there are four possible results:

Removing Entries

Entries do not need to be deleted explicitly. Each
entry is associated with a lease time. If it is not
renewed within that time, it is deleted. That way,
users who are no longer part of the system will
be removed after some time.
In EPHTs, once a node has split and become
an inner node, this node stays an inner node for
ever, even if all entries in its sub-tree have timed-
out. That means that the EPHT can only grow, but
never shrink. This property is in accordance with
our use case, as shrinking the tree would only
make sense if the service provider operating the
distributed phone book application would perma-
nently loose a significant number of customers, or
if the distribution of the name's prefixes changes
significantly. Both scenarios happen very slowly,
and it is feasible to roll out a software update in
that case that will built a new tree from scratch.
The persistence of inner nodes enables us to
implement extensive caching.

1. A node with that prefix exists and is a non-
empty leaf node. In that case, the initial node
for traversing the linked list is found.