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

Figure 6. Example of an extended prefix hash tree with n=3 and m=2

of prefix) equals the identifier length for
the entries, then that node cannot split any
further, and its maximum load becomes in-
finite. In the section on evaluation we show
that m =100 is a good value.

all leaf nodes, including the empty ones. Each
element in a list stores the prefix of its predeces-
sor and successor. The linked list is updated upon
the following events:

1. A leaf node splits up into child nodes. In that
case, the old leaf node must leave the linked
lists, the non-empty new child nodes must
join the linked list for non-empty nodes, and
all new leaf nodes must join the linked list
connecting all leaf nodes. The new nodes
learn about their initial successors and pre-
decessors from their parent node.
2. An entry is added to a previously empty
leaf node. In that case, that node must join
the list for non-empty leaf nodes. The node
finds its predecessor and successor using
the list connecting all leaf nodes.

Each node of the tree is stored as a resource
in a DHT, using a hash function operating in the
Random Oracle Model. The keyword to be hashed
is the prefix of that node in the EPHT, i.e. the
sequence of character sets on the path from the
root node to the node to be stored. For example,
the keyword of the leaf node holding the entry
'Gerd Völksen' in Figure 6 would be '[S-Z][I-
R]'. New entries are stored on the leaf node that
has the closest matching prefix for the identifier
of that entry.
Once a node is split, it becomes an inner node.
Inner nodes are kept in the system to indicate the
existence of child nodes, but they do not store
any data. In particular, inner nodes do not need
to store links to their children.

Performing Range Queries

Usually, tree algorithms imply that nodes are
searched starting at the root node and traversing
down the tree to a leaf node. This would mean that
the peer holding the root node becomes a bottle-
neck and single point of failure in a distributed
tree structure. EPHTs allow lookups to address

Maintaining the Linked Lists

In addition to the tree structure itself, two doubly
linked lists are maintained: one for traversing the
non-empty leaf nodes, and the other connecting