Flexible Routing Tables:
Designing Routing Algorithms for Overlays
Based on a Total Order on a Routing Table Set
Hiroya Nagao, Kazuyuki Shudo
Tokyo Institute of Technology, Tokyo, Japan
Email: {hiroya.nagao, shudo}@is.titech.ac.jp

Abstract—This paper presents Flexible Routing Tables (FRT),a method for designing routing algorithms for overlay networks.
FRT facilitates extending routing algorithms to reflect factors
other than node identifiers.
An FRT-based algorithm defines a total order on the set of
all patterns of a routing table, and performs identifier-based
routing according to that order. The algorithm gradually refines
its routing table along the order by three operations: guaranteeof reachability, entry learning, and entry filtering.
This paper presents FRT-Chord, an FRT-based distributedhash table, and gives proof that it achieves O(log N )-hop lookups.
Experiments with its implementation show that the routing tablerefining process proceeds as designed.
Grouped FRT (GFRT), which introduces node groups into
FRT, is also presented to demonstrate FRT’s flexibility. GFRTChord resulted in a smaller numbers of routing hops between
node groups than both Chord and FRT-Chord.

I. I NTRODUCTION
Numerous distributed hash tables (DHTs) have been proposed and actively researched over the last decade [1]–[7] .
DHT routing algorithms provide scalability, fault tolerance,and reliability to overlay networks. Here, we focus on two
features lacking in the routing algorithms of existing DHTs.
The first feature is dynamic routing table size. Existing
DHTs limit routing table size, in other words the maximum
number of routing table entries, to tens or hundreds. DHTs set
the limitation because DHTs assume an unreliable, large-scale
network such as the Internet, and it is difficult for nodes tomaintain all of the millions of other nodes on such a network.
Routing algorithms that achieve shorter path lengths with asmall routing table have therefore been considered to be better
algorithms. It is not always true, however, that the routing tablesize must be kept small. In OneHop [8] and EpiChord [9], forinstance, routing table sizes are large and each routing table
maintains a list of all nodes in the network. Moreover, it isdifficult to estimate a suitable routing table size because theoptimal size depends on node lifespan, node availability, andthe number of nodes, all of which may change dynamicallywhile the overlay network evolves and operates. It is therefore
necessary to design a routing algorithm that can adapt to any
routing table size and can change dynamically.
This work was supported by MEXT KAKENHI (22680005).

The second feature is a node identifier consideration that
does not restrict routing table candidates. Each node has a node
identifier, an address in an overlay network, and messages areforwarded according to those identifiers. Routing tables are
therefore constructed using node identifiers. Existing routing
algorithms reflect node identifiers by restricting routing table
candidates to a subset of routing tables with some desirable
property, such as O(log N )-hop lookup performance in an N node network. For instance, Chord [1] restricts node identifiersin a routing table at a node s to those nodes that most closely
follow s + 2i . Kademlia [5] restricts the number of nodes
whose identifiers are [2i , 2i+1 ) away from s, based on XOR
metrics, to be less than a constant k. Such restrictions arecomprehensible and make data structures and construction
processes simple, and are suitable to reflect only node identifiers. Such restrictions cause problems, however, not onlyin that routing tables do not know all nodes, despite thesmall number of nodes present, but also in that they eliminate
opportunities to consider factors other than node identifiers,
making extension of the routing algorithm problematic.
Algorithm extension is a promising approach to overcoming
inherent problems in overlays, such as a number of relay
nodes and insufficient consideration of network proximity. For
instance, LPRS-Chord [10] and Coral [11] reflect network
latency in routing tables, and Diminished Chord [12] and GTap[13] reflect node groups. Extendibility is a key property of
DHTs and determines what extensions can be implemented. As
mentioned above, however, the existing method of considering
node identifiers interferes with constructing routing tables
that are desirable in terms of such factors. The restriction
on routing table candidates poses difficulty in consideringfactors other than node identifiers. It is difficult to achieve abalance between node identifier considerations and other factor
considerations. A scheme of reflecting node identifiers without
such restrictions is important for future applications.
As a solution we propose flexible routing tables (FRT), a
method for designing routing algorithms for overlay networks.
An FRT-based algorithm defines a total order ≤ID as an indicator of the relative merits between node identifier combinations
in a routing table, and continuously refines a routing table inaccordance with the order. By doing so, the algorithm is able
to dynamically change the routing table size and reflect nodeProc. 11th IEEE Int'l Conf. on Peer-to-Peer Computing (IEEE P2P'11), pp.72-81, August 2011

identifiers in a routing table without restriction on routing table
candidates.
FRT has the following features.
Broadening of target domain: A node can route a
message in O(1)-hop if the node can hold all nodes in an
overlay. Otherwise, the algorithm routes messages as multihop lookups. The algorithm is also able to continuously change
between those lookup styles without knowledge of the numberof nodes.
Improved extendability: FRT supports simultaneous consideration of node identifiers and other factors because routing
table construction does not restrict candidates for node identifier combinations in a routing table.
Effective utilization of entry information: In existing
DHTs, routing tables tend to obtain only entry informationneeded for an eventual routing table, where entry information
is knowledge needed to construct entries. Entry informationthat is not required, therefore, get ignored. An FRT-basedalgorithm does not ignore any entry information, and thus isable to construct better routing tables by evaluating all entry
information.
Flexibility: An FRT-based algorithm is able to constructsituation-dependent routing tables, based on, for example,
the number of nodes in the system, node lifespan, node
availability, performance requirements, without restriction on
routing table size since the routing table is able to be resized
dynamically.
Facilitation of node identifier considerations: An FRTbased algorithm expresses the relative merits of node identifier
combinations in a routing table by a total order ≤ID , andthus the algorithm can consider node identifiers by referring
only to an order on the routing table set. As a result, thealgorithm is able to easily choose a routing table with moredesirable node identifier combinations from among routing
table candidates fulfilling complex restrictions on factors otherthan node identifiers.
Continual extension: FRT is able to continuously extend and improve existing routing algorithms for overlay
networks by inserting additional entries into routing tablesin the algorithms according to their order, which is definedin advance. FRT-based routing table construction protocols
can be designed as extensions of existing algorithms while
retaining all entries in the original routing table, and thus, atthe least, we can retain the routing efficiency and other featuresof the original algorithm.
We describe a concrete FRT algorithm by taking FRTChord, a DHT we designed based on FRT, as an example.
We also implement the proposed algorithm, and perform
experiments.
In Section IV, we discuss how to design DHTs for future
extension, and the extendibility of DHTs based on FRT.
II. R ELATED W ORK
A. Chord
Chord is a distributed hash table (DHT), where node identifiers are represented as a circle of natural numbers from 0

0
1

7
6

2

3

5

d(1,4) = 3

4

Fig. 1.

Chord ring (m = 3).
: entrye1e2

ei-1 ei

ei+1: sticky entry

e|E|-1 e|E|

to 2m − 1 in a clockwise direction (m is a bit length).
Thed(s,ei)m
identifier
0 space is called a Chord ring. The node 2responsible
for a key issuccessor
that node whose identifierpredecessor
most closely follows
the key, called a successor.
In Chord, each node maintains three routing tables (successor list, predecessor, and finger table). Each entry in therouting tables is a node identifier and IP address pair.
: entryA nodeei
ei+1
is able to send messages to another node with a specified
noded(s,ei)m identifier
identifier,0 because the routing tables convert an node2d(s,ei)d(ei,ei+1)d(ei,ei+1)
to its corresponding
IP address.
ri (E) =d(s,ei+1)d(s,ei+1)
A successor list at node s contains a certain
number of closest nodes from s in the clockwise direction, and a predecessor
contains the closest node from s in the anticlockwise direction.
These two routing tables are maintained by periodicallyrun: entryei
ei+1
ning a stabilization routine,whereinthe node sends messageslog d(s,ei)
to the successor for guaranteeing lookup correctness.
The
i th
m
0
2
entry in a finger
is the firstlognodethatsucceeds s by atlog d(s,eitable)d(s,ei+1)
E
least 2i−1 in the clockwise direction.
Using
thed(s,efingertable
S i = log d(s,ei+1) - logi)significantly reduces the remaining distance.
In Chord, the identifier distance from x to y, d(x, y), is
defined as follows (Fig.1).
an entry to remove: entry: sticky entry
removal candidates for x < y predecessor(1) y − x,e1e2
ei*-1 eim
ei*+1
e|E|-1 e|E|*2 ,for x = y(2)d(x, y) =log d(s,ei)

m
m
y
−
x
+
2
,
for
x
>
y
(3)
0
2
successor

EE

S i*+1i*
A query for a key
identifier t isSforwarded
to a node s′ in the′ SEi*+1+SEi*
routing table for which d(s , t) is minimized among any otherentries. Routing schemes like this one that repeat forwarding
through nearest
to a target
are called
greedy: entry nodes: sticky entry: entry belonging
to the samegroup as s.routing
schemes. Chord achieves O(log N )-hop lookup performance
EG
Efar
near
with N Enodes.
e1 e2

eα−1

eα

eβ eβ+1 e|E|-1 e|E|

B. EpiChord0d(s,ei)m

2
Eleap number of entries
predecessor
EpiChordsuccessor
is a DHT in which thein therouting table is not limited. EpiChord divides the Chord ring
into two symmetric sets of exponentially smaller slices, where
the number of entries is greater than some constant at all times.
This constraint provides an O(log N )-hop guarantee on lookup
path length. Such a constraint, however, also restrict candidates
for node identifier combinations in routing tables. Although
FRT, on the other hand, is able to construct routing tables fromamong all nodes, and FRT reflects node identifiers without
such constraints.

Proc. 11th IEEE Int'l Conf. on Peer-to-Peer Computing (IEEE P2P'11), pp.72-81, August 2011

successor: entrye1e2

ei-1 ei

ei+1: sticky entry

predecessor

ei+1

m

0

d(s,ei)2d(ei,ei+1)
ri (E) =d(s,ei+1)

A routing table E = {ei }i=1,...,|E| .

C. Symphonyei: entryei+1d(s,ei)m

successor

Fig. 2.

ei

e|E|-1 e|E|d(s,ei)0predecessor: entry

Symphony [7] is also a DHT using a Chord ring.d(s,eIn Symi)phony,
eachnode
maintainstwodifferent
entries,m short dis02d(s,ei(SDLs))d(ei,elongi+1) distance linksd(ei,e(LDLs).
tance links
andSDLs arei+1)
ri (E) =)d(s,e)
fixed entriesd(s,emaintainedforreachability,
namelya
successor
i+1
i+1
and a predecessor. Each LDL is determined probabilisticallyaccording to an identifier generated by a specific probability
distribution based on the Small World phenomenon [14]. It
therefore might seem that any node may be selected: entry as anei
ei+1
LDL, and that Symphonydoes not restrict candidates forlog d(s,ei)
node
identifier combinations. However, each LDL
m is selected02deterministicallyaccording tologad(s,eprobabilisticallygenerated
log d(s,ei)
i+1)
E opportunity to reflect factors
identifier, and thus, there is noS i = log d(s,ei+1) - log d(s,ei)
other than node identifiers. FRT differs from Symphony interms of flexibility of entry selections.
III. FRT-C HORD

an entry to remove: entry: sticky entry
removalIn thiscandidates
section we describe FRT-Chord, an FRT-based DHT.
predecessor

In FRT-Chordthespace is a Chorde1e2ei*-1identifier
ei*
ei*+1
e|E|-1ring
e|E| and the nodelog d(s,ei)
responsible for a key is determined as in Chord. FRT-Chord0
also
performs a greedy routing as in Chord, but2m the method
successorof routing table
construction has
some unique features.
EE
S i*+1S i*
In FRT-Chord,each node maintains
a single routing table
E
E
E without distinguishing Sbetween
i*+1+S i* successor list, predecessor,
and finger table because doing so restricts routing tables. The
routing table E is a set of entries {ei }i=1,...,|E| (see Fig.2).
: entry: sticky entry: entry belonging to the same group as s.
Each entry ei consists of a node identifier ei .id and an IP
address
and a port pair eEiG.addr (note that eiEis
Enear
far referred to asei .id).
A
routing
table
{e
}
at
a
node
s
is
alignedclockwiseie1 e2 eα−1 eαeβ eβ+1 e|E|-1 e|E|from s, so it satisfies i < j ⇒ d(s, ei ) < d(s, ej ).d(s,eByi) thismdefinition,
e1 and e|E| correspond with a successor
and a
0
2
successor
leap
predecessor
predecessor,
respectively. We Eassume
that the correctnessofthese entries is guaranteed by the stabilization routine andregard them as sticky entries (Section III-D).
A. ≤ID : Total Order of the Routing Table Set
An FRT-based algorithm defines a total order ≤ID on node
identifier combinations in a routing table. The order represents
the relative merits between routing tables in terms of node
identifiers. The algorithm iteratively refines the routing tableaccording to the order. In this section, we illustrate the designof the order ≤ID in FRT-Chord, and for simplicity we set thelength of the equivalent of the successor list to 1.
1) Definition of the Best Routing Table: Let E.forward(t)be an entry in a routing table E to which a query is
forwarded at a node s toward a target identifier t. The
reduction ratio of a forwarding of the query is defined asd(ei,ei+1)2d(s,ei+1)

the worst-case reduction ratio ri (E) of a forwarding to a node ei .

Fig. 3.

: entryei
ei+1 This means that the smaller thed(E.forward(t), t)/d(s,t).
log d(s,ei)
reduction ratio, the more efficient is the forwarding.
Here
m
0
2
we will focus on the worst-case reduction ratio ri (E) of
log d(s,e )log d(s,ei+1)
a forwardingi to a node ei , otherthan its predecessor. The
E= log d(s,ei+1) - log d(s,ei)
reduction ratio of a forwardingS ito
ei takes the worst-case value
when the key identifier t equals ei+1 (see Fig.3), sori (E) =removal candidatesd(ei , ei+1 ),an entry
to remove
d(s,
ei+1
)

(i = 1, . . . , |E| − 1).
: entry(4): sticky entry
predecessor

e1 definee2
ei*+1 table Ẽ = {ẽe|E|-1We
theei*best-1 ei*routing|E| follows.
i } easlog d(s,eDefinition 1: In FRT-Chord, the best routing tableẼ i)=
m2{ẽ0 i } minimizes maxi {ri (E)}.
successor
Lemma 1: EE
S i*+1(S i*) 1|Ẽ|−1EEẽ
)S i*+1+Sd(s,1i*ri (Ẽ) = 1 −(5)d(s, ẽ|Ẽ| )Proof:{ri (E)}takes: entry From: sticky(6),entrymax:ientry
belongingto thethesameminimumgroup as s. value
when all of ri (E) are equal.
EG

Enear

e1 e2
0

Efar

|E|−1

d(s, eeβ1 )eβ+1 e|E|-1 e|E|eα−1∏ eα(1 − ri (E)) =(= const.) d(s,ei) (6)d(s,e|E| )
mi=1

successor

Eleap

2
predecessor

Theorem 1: With high probability (or under standard hardness assumptions), assuming that all nodes have the best
routing table with O(log N ) entries in an N -node network,
path lengths are O(log N ).
Proof: Let Ẽ = {ẽ} be the best routing table at a nodes. With high probability, the distance between two genericconsecutive nodes is at least 2m /N 2 [15], namely
2m.
N2
The distance between any nodes is at most 2m , namelyd(s, ẽ1 ) >(7)d(s, ẽ|E| ) < 2m .

(8)Thus, according to Lemma 1, for any i = 1, . . . , |Ẽ| − 1,( ) 2
1 |Ẽ|−1ri (Ẽ) < 1 −.
(9)N
For |Ẽ| = 1 + 2 log N , the path length needed to reduce theremaining distance to 2m /N or less is at most1
< log N.
(10)N
The path length is therefore O(log N ). When the remaining
distance is at most 2m /N , the number of node identifiers landing in a range of this size is, with high probability, O(log N ).
logri (Ẽ)

Proc. 11th IEEE Int'l Conf. on Peer-to-Peer Computing (IEEE P2P'11), pp.72-81, August 2011

Thus the query reaches the key t within another O(log N )steps, meaning that the entire path length is O(log N ).
2) Definition of ≤ID based on ri (E): In FRT-Chord, theorder ≤ID represents an indicator of closeness to the best
routing table, and is defined as follows.
Definition 2: Let {r(i) (E)} be the list arranged in descending order of {ri (E)},

When the probability distribution is defined as above, letting
rnd produce a random number between 0 and 1, the key isgenerated from the expression:s + ds (e1 )(ds (e|E| )/ds (e1 ))rnd .

(17)

When we define ≤ID as above, Theorem 2 holds.
Theorem 2: Let E be a candidate for a routing table and Ẽ
be a best routing table, Ẽ ≤ID E.
Proof: From Lemma 1 and Definition 2, Ẽ is the minimum routing table candidate according to ≤ID .
We design an algorithm framework to use the order ≤ID in
three parts, guarantee of reachability, entry learning, and entry
filtering. FRT-based algorithms consist of these three parts.

FRT-Chord uses transfers at join. If the need arises, active
learning lookups are performed.
In FRT, new entries learned by the above methods are inserted into the routing table. Through repeated entry learning,a node can forward a query to a closer node to a given key. Asa separate issue, because the number of entries |E| increases
continuously, a node should prune entries at some future time.
FRT-Chord sets a routing table size L, the maximum numberof entries, to prevent the number of entries from increasing
without limit. L is configured dynamically and flexibly, basedon the number of entries that should be retained according tonode lifetime, machine performance, network latency, and soon.
For instance, if the routing table size L is larger than N , thenetwork is stable, routing tables are able to contain all nodes
in the system, and the algorithm achieves O(1)-hop lookup
performance.

B. Guarantee of Reachability

D. Entry Filtering

In FRT, all operations to guarantee reachability are called aguarantee of reachability.
FRT-Chord’s guarantee of reachability is a stabilization
routine like Chord.

If L < N , when |E| exceeds L, FRT-Chord will remove
either the most recently learned new entry or entries in thecurrent routing table in order to retain |E| ≤ L.
In FRT, such entry removal operations are called entry
filtering. Through continuous entry learning and entry filtering, FRT-based algorithms refine routing tables incrementallyaccording to the order ≤ID .
An FRT-based algorithm defines some entries as sticky
entries. FRT excludes sticky entries as removal candidates forentry filtering. For example, short distance links (SDLs) are
one type of sticky entry. By designating sticky entries, we
can easily design a total order ≤ID . Entry filtering in FRT issummarized as follows.
1) Substitute entries in E into C.
2) Remove sticky entries from C.
3) Select an entry from C to refine E according to ≤ID .
In this way, FRT can consider node identifiers without
restrictions on candidate node identifier combinations in arouting table with order ≤ID . We can also extend the algorithmwith good results by introducing consideration of factors otherthan node identifiers when performing entry filtering.
In the rest of this section, we describe FRT-Chord entry
filtering in detail.
Let ei∗ be an entry removed from a routing table E by
FRT-Chord’s entry filtering, and SiE be a canonical spacing
defined as follows (see Fig.4).
Definition 3:

E ≤ID F ⇔ {r(i) (E)} ≤dic {r(i) (F )}.

(11)

In this definition, ≤dic is a lexicographical order, namely{ai } <dic {bi }⇔ ak < bk ,{ai } =dic {bi }⇔ ai = bi(k = min{i|ai ̸= bi }) (12)(13){ai } ≤dic {bi }⇔ ({ai } <dic{bi })∪({ai } =dic{bi }). (14)

C. Entry Learning
We define entry information as information needed to compose an entry including a node identifier, an IP address, and aport number. In FRT, learning entry information and inserting
the entry into a routing table are called entry learning. FRT
does not limit how and when learning occurs so that opportunities to refine a routing table will not be wasted.
The following are examples of how FRT learns entries.
1) When a node first joins an overlay, it learns entries bytransferring a routing table from a closest node from
itself. This transfer is called transfer at join.
2) When a node communicates with another node whenrouting processes, it learns the connected nodes.
3) Nodes actively look up and learn entries with which they
communicates, as in 2). These lookups are called active
learning lookups.
In FRT-Chord, active learning lookups are similar to Symphony [7]. A node looks up a key generated from a probability
distribution based on identifiers in the best routing table. The
probability distribution at a node s is in inverse proportion to
the distance from s. Letting ds (x) = d(s, x), the cumulative
distribution function F(x) is defined asds (x)
 ln ln ds (e1 ),for ds (e1 ) < x < ds (e|E| ) (15)F(x)= ln ds (e|E| )

ln
d
(e
)
s
1

0,
for otherwise.
(16)

SiE = logd(s, ei+1 ),d(s, ei )(i = 1, . . . , |E|−1)

Proc. 11th IEEE Int'l Conf. on Peer-to-Peer Computing (IEEE P2P'11), pp.72-81, August 2011(18)

d(s,eii)d(eii,ei+1
i+1)

eii

d(eii,ei+1
i+1)d(s,ei+1
i+1)

rii (E) =d(s,ei+1
i+1)

Proof: Since (E ∪ {elearn }) \ {elearn } = E,:: entry
entry

ei+1
i+1

log d(s,eii)
m

00

22m

log d(s,eii)

log d(s,ei+1i+1)EES ii = log d(s,ei+1
i+1) - log d(s,eii)anan entry
entry toto remove
remove:: entryentry

removalremoval candidates
candidates

e11

e22

eii**-1-1 eii**eii**+1+1(E ∪ {elearn }) \ {efilter } ≤ID (E ∪ {elearn }) \ {elearn }. (25):: sticky
sticky entry
entry
predecessor
predecessor

e|E|-1|E|-1 e|E||E|

log d(s,eii)
m

00

22m

successor
successor
E

E

SEi*-1
i*+1

SEi*
i*
E

E

SEi*-1+S Ei*
i*+1+Si*

Fig. 5.
:: entry
entry

Enear
near

FRT-Chord Entry filtering.

:: sticky
sticky entry
entry:: entry
entry belonging
belonging toto thethe samesame group
group as
as s.
s.

EGG

Efar
far

When SiE is defined as above, an entry ei∗ is selected frome11 e22 eα−1eαα
eβ+1
e|E|-1 e|E|
β+1 |E|-1
otherthan α−1e1 ande|E| because theseeββentries
are|E|sticky entries,d(s,eii)and(19) holds (see Fig.5).
m
0
2m
0

successor
successor
Eleap
leap
E
+ SiE ,
SiE∗ −1 + SiE∗ ≤ Si−12
predecessor
predecessor(i = 2, . . . , |E|−1)(19)This way FRT-Chord can search for i∗ at low cost byE
maintaining a list in ascending order of Si−1
+ SiE , because
only constant parts of the list need be changed with each entry
learning and entry filtering.
E
Letting {S(i)} be the list arranged in descending order ofE{Si }, the following lemma holds.
Lemma 2:EF
E ≤ID F ⇔ {S(i)} ≤dic {S(i)}(20)

Proof: From the definitions of ri (E) and SiE , we haveri (E) = 1−2−Si .
E(21)Thus, small and large elements in the lists, ri (E) and SiE ,correspond with each other.
Theorem 3: In FRT-Chord, let E \ {ei∗ } be a routing tablefiltered by removing ei∗ . For any ei (i = 2, . . . , |E| − 1),
E \ {ei∗ } ≤ID E \ {ei }.
E−{e ∗ }(22)
E−{e }

Proof: By calculating lists {S(j) i } and {S(j) i },arranged in descending order of the canonical spacings afE
ter entry filtering (note that SiE∗ −1 + SiE∗ ≤ Si−1
+ SiE ),
E\{ei∗ }E\{ei }
the equation {S(j)} ≤dic {S(j)} is derived, andE \ {ei∗ } ≤ID E \ {ei } holds by Lemma 2.
Theorem 4: In FRT-Chord, let (E ∪ {elearn }) \ {efilter } be arouting table after an entry learning process and a succeeding
entry filtering process, where elearn ̸∈ E is a learned entry andefilter ∈ (E ∪ elearn ) is a removed entry in these processes.
(E ∪ {elearn }) \ {efilter } ≤ID E(24)

According to Theorem 3,

The canonical spacing SiE .

Fig. 4.

(E ∪ {elearn }) \ {elearn } ≤ID E.

(23)

Therefore, since ≤ID is a total order, (23) holds.
Theorem 4 means that FRT-Chord repeats to refine a routing
table by entry learning and entry filtering.
In FRT-Chord, it is possible that routing table refinement
through repeated entry learning and entry filtering will stop
when any most recently learned entry is selected as an entry to
remove. Such a routing table E is called a convergent routing
table, and the following theorem holds.
Theorem 5: Assuming that all nodes have convergent routing tables with O(log N ) entries in an N -nodes network, path
lengths are O(log N ) with high probability.
Proof: Let J be a set of i, where a node exists in a range
from ei to ei+1 , and K be a set of i otherwise. From thedefinition of convergent routing tables, for any j ∈ J, whenan entry is inserted between ej and ej+1 , that entry will be
removed, and the following inequality holds.
E
SjE ≤ Si−1
+ SiE ,(j ∈ J, i = 2, . . . , |E|−1)

Thus, by aggregating (26),∑|E|−1 E(Si−1 + SiE )SjE ≤ i=2
|E| − 2∑|E|−1 E() 2d(s, e|E| ) |E|−22( i=1 Si )
≤
.
= log
|E| − 2d(s, e1 )

(26)

(27)
(28)

According to the definitions of rj (E) and SjE , we can apply
the proof of Theorem 1:
4( ) |E|−2
1rj (E) < 1 −.
(29)
NWhen we consider the upper limit of path lengths needed
to reduce the remaining distance to 2m /N or less, we must
focus on the case where each node forwards to ej (j ∈ J),
because there is no node between ek and ek+1 and the query
forwarding will stop if the query is forwarded to ek .
From (29), path lengths are O(log N ) by similar reasoning
to the proof of Theorem 1.
When we wish to set the length of successor lists atc(> 1), we need only add the entries as sticky entries. In
this case, an entry to remove will be selected optimally by
the same filtering method, and routing tables will be refinedcontinuously through entry learning and entry filtering.
As a result, we can summarize entry filtering in FRT-Chordas follows.
1) Substitute entries in E into C.
2) Remove sticky entries from C.
3) Select the entry ei∗ from C that minimizes {SiE∗ −1 +SiE∗ }.

Proc. 11th IEEE Int'l Conf. on Peer-to-Peer Computing (IEEE P2P'11), pp.72-81, August 2011

successor
EE

S i*+1

S i*
E

E

S i*+1+S i*: entry

IV. E XTENSIONS OF FRTExisting DHTs consider node identifiers by putting restrictions on candidates for node identifier combination in arouting table to make path lengths short such as O(log N )-hop
lookup performance. To extend these DHTs, we must either
construct routing tables under these restrictions or relax theserestrictions altogether, and thus the restrictions too strongly
limit opportunities to extend algorithms.
On the other hand, an FRT-based algorithm is able toflexibly reflect factors other than node identifiers in routing
table construction, and node identifier consideration follows
naturally because the algorithm manifests policies on how toevaluate each routing table according to node identifiers as anorder ≤ID . The routing table is refined incrementally in termsof node identifiers even under restriction of factors other thannode identifiers. This is the aspect most different from otherDHTs.
A. GFRT-Chord
Grouped FRT (GFRT) is an extension of FRT. GFRT reflects
node groups in routing tables at each node x by adding a policy
to preferentially keep entries belonging to the same groupas x in the routing table. GFRT-Chord achieves reductionof hops between nodes belonging to different node groups
while keeping path lengths short. For instance, we can reduce
communications over ISPs or data centers by configuring themas node groups. In GFRT, each node x belongs to a node groupx.group, and a group identifier is attached to a node identifier,and thus each entry e has node group information as e.group.
Like FRT-Chord, GFRT-Chord also consists of three parts,
guarantee of reachability, entry leaning, and entry filtering. It
uses the same methods for guarantee of reachability and entry
learning, and is characterized by its method for entry filtering.
1) Entry Filtering: GFRT-Chord maintains a group successor list and a group predecessor in a similar way to FRTChord. The group successor list and the group predecessor ata node s means a successor list and a predecessor respectively
in a network limited to nodes belonging to the same group ass. In GFRT-Chord, therefore, sticky entries are a successor list,a predecessor, a group successor list, and a group predecessor.
We define the following variables for the routing table E ={ei } at a node s (see Fig.6).
• EG = {e ∈ E|e.group = s.group}.
• EḠ = {e ∈ E|e.group ̸= s.group}.
• eα is the nearest entry in EG from s.
• eβ is the farthest entry in EG from s.
• Enear = {ei ∈ E|d(s, ei ) < d(s, eα )}.
• Efar = {ei ∈ E|d(s, eα ≤ d(s, ei ) < d(s, e|E| )}.
• Eleap = Efar ∩ EḠ .
Using the variables defined above, GFRT-Chord performs
entry filtering as follows:
1) Substitute EḠ into C if Eleap ̸= ∅, otherwise substituteE into C.
2) Remove sticky entries from C.

: sticky entry: entry belonging to the same group as s.

EG

Enear
e1 e2

eα−1

Efar

eα

eβ eβ+1 e|E|-1 e|E|d(s,ei)0msuccessor

Fig. 6.

Eleap

2predecessor

Variables for GFRT-Chord entry filtering.

3) Select the entry ei∗ from C that minimizes {SiE∗ −1 +SiE∗ }.
As above, entry filtering in GFRT-Chord consists of thefiltering steps in FRT-Chord with the addition of only one step.
The step 1) in particular represents the policy of preferentiallymaintaining entries belonging to the same group. The othertwo steps are the same as those in FRT-Chord, and thesesteps refine the routing table according to the order ≤ID .
Thus, GFRT-Chord reflects node identifiers in routing table
construction after reflecting node groups. In this way, allfiltering steps in GFRT-Chord simultaneously reflect node
identifiers and node groups.
From this, for convenience we set the length of successor
lists and group successor lists as 1. Theorem 6 holds as in
FRT-Chord.
Theorem 6: Let E ∗ = E \ {ei∗ } be a routing table filteredby removing ei∗ according to the filtering operation of GFRTChord. For any entry ei other than sticky entries, (30) and (31)
hold.
∗
∗
|Efar
| − |Eleap||Efar | − |Eleap |≥∗|Efar |
|Efar |
E \ {ei∗ } ≤ID E \ {ei }

(30)
(31)

Proof: We will prove Theorem 6 in two parts.
1) When Eleap = ∅, (30) holds. (31) also holds because
we can apply the proof of Theorem 3.
2) When Eleap ̸= ∅, since GFRT-Chord selects an entryei∗ from Efar if and only if ei∗ ∈ Eleap according to
the first step in entry filtering, |Efar | decreases by one if
and only if |Eleap | decreases by one. So, |Efar | will notdecrease by one without removing an entry from Eleap .
Thus, (30) holds. (31) also holds because we can apply
the proof in Theorem 3 under the restriction of the first
step.
In Theorem 6, each of (30) and (31) means that the entry
filtering reflects both node groups according to the ratioof the entries belonging to the same group as s and node
identifiers according to the order ≤ID . Therefore, Theorem 6
represents a consideration of node groups and node identifiers
simultaneously.
We define a group localized routing table at a node s as
follows:
Definition 4: Let E be a group localized routing table at anode s belonging to a group Gs . When the node forwards a

Proc. 11th IEEE Int'l Conf. on Peer-to-Peer Computing (IEEE P2P'11), pp.72-81, August 2011

message for a target identifier t to a node v in EḠ , there isno entry belonging to Gs in the range from v to t.
Definition 5: A fully group localized routing table E at anode s in a group Gs is defined as Eleap = ∅.
Theorem 7: A fully group localized routing table E is agroup localized routing table.
Proof: A forwarded node v ∈ EḠ is in the range from s
to the group successor of s.
Lemma 3: In GFRT-Chord, when a routing table E is aconvergent routing table and Eleap ̸= ∅, all nodes belonging
to Gs are in E.
Proof: We assume a hypothesis that E does not include
a node belonging to Gs . If E learns the node, the entry will
be removed during entry filtering because E is a convergent
routing table. But this contradicts the first step in entry filteringin GFRT-Chord. Therefore, E has all nodes belonging to Gs .
Theorem 8: In GFRT-Chord, when a routing table E is aconvergent routing table, E is a group localized routing table.
Proof: Let s be a node with a convergent routing table
E and belonging to a group Gs , and consider forwarding amessage for a target identifier t to a node v ∈ EḠ . We will
prove Theorem 8 in three parts.
1) When v is e|E| , since e|E| is the predecessor of s, there
is obviously no entry in the range from v to t.
2) When v is in Enear , since v is nearer from s than eα andt is in a range from v to eα , there is no entry belonging
to Gs in a range from v to t.
3) When v is in Efar , since there is at least an entry
belonging to EḠ in Efar , according to Lemma 3 there
is no entry belonging to Gs in the range from v to t.
Theorem 9: Let P = {vi } be a set of nodes in a forwarding
path from the source node s = v0 to the predecessor of the
responsible node vn−1 . In GFRT-Chord, when each node in thepath has a convergent routing table, for any vi , vj ∈ P (i < j),vi .group = vj .group ⇒ i < ∀k < j, vk .group = vi .group.
(32)
Proof: Since Theorem 8 holds, each node in the path has
a group localized routing table. We assume that vi and vj
belong to a group G0 .
If we assume that the proposition is false, there exists k(i <k < j) such that,vk−1 .group = G0 ,vk .group ̸= G0 .

(33)
(34)

Since vk−1 belonging to G0 forwarded a message to vk
belonging to a group other than G0 , then according to thedefinition of the group localized routing table there is no entry
belonging to G0 in the range from vk to t. But this contradicts
the hypothesis that vj belonging to G0 is in the range fromvk to t.
Thus, when all routing tables are sufficiently updated andthey are convergent routing tables, once a node belonging toa group forwards a message to a node belonging to anothergroup, the message will never be forwarded to nodes belonging
to the group (except for the last hop). This is derived fromthe routing table construction of GFRT-Chord to reflect nodegroups.
Theorem 10: With high probability, assuming that all nodes
have a convergent routing table with O(log N ) entries in an
N -node network, path lengths are O(|G| + log N ) in a GFRTChord system composed of groups G = {Gi }.
Proof: We are focusing on a node s and its routing table
E. Let Gs denote a group that s belongs to. Consider a casewhere s forwards a message to a node s′ belonging to Gs′ . If
Gs ̸= Gs′ , then according to Theorem 9 the forwarding takes
at most |G| − 1 times.
If Gs = Gs′ , let s′′ be an entry in either EG or s, where s′′minimizes d(s′ , s′′ ), and consider this situation in three parts.
1) When there is no node in the range from s′ to s′′ , forwarding from s to s′ will be the last one, so forwarding
takes place only once.
2) When there is no node belonging to Gs but a node
belonging to one of the other groups in the range froms′ to s′′ , s′ forwards a message to a node belonging toa group other than Gs . Thus, according to Theorem 9
the forwarding takes at most |G| − 1 times.
3) When there is a node belonging to Gs in the range froms′ to s′′ , let j be an index of ej = s′ and F be a set of
entries in E other than sticky nodes. Then according
to the definition of the convergent routing table thefollowing inequality holds.
E
SjE ≤ Si−1
+ SiE ,(ei ∈ F )(35)

Thus, since sticky entries are e1 , eα , eβ and e|E| ,the following inequalities hold by aggregating theseinequalities (note that the four entries may be equal toeach other).
∑E+ SiE )(Si−1
E
Sj ≤ ei ∈F
(36)
|F |
∑|E|−1() 2d(s, e|E| ) |E|−42( i=1 SiE )
≤
= log
.(37)
|E| − 4d(s, e1 )Thus, the forwarding takes O(log N ) times by similar
logic to the proof of Theorem 5.
Therefore, the path length is O(|G| + log N ).
B. Extendibility of FRT
We can easily design such extended algorithms because
FRT offers us a simple way to reflect node identifiers in thedesign methodology composed of three steps, guarantee of
reachability, entry leaning, and entry filtering, by defining a
total order ≤ID on the routing table set. It is important thatFRT replaces consideration of how we should construct routing
tables with consideration of what entries we should remove
from the routing table. In the rest of this section, we will
demonstrate the extendibility of FRT by taking GFRT-Chordas an example.

Proc. 11th IEEE Int'l Conf. on Peer-to-Peer Computing (IEEE P2P'11), pp.72-81, August 2011

V. E VALUATION
We implemented FRT-Chord on Overlay Weaver [16], [17],an overlay construction toolkit, and performed experiments.
A. Entry Learning and Entry Filtering in FRT-Chord
Here we will show that routing tables will approach thebest routing table by entry learning and entry filtering, andconfirm the effectiveness of transferring at join and active
learning lookups.
In the experiments, the routing table size L is 80 and m is160. We successively sent 105 queries, each query being sent
to a randomly chosen key by a randomly chosen node in asystem with N = 104 nodes. Next, we added a single node to
the system and had it send 102 queries to a randomly chosen
key or according to active learning lookups. We adopted
an iterative style to route queries in all experiments, like
EpiChord [9]. In this method, the first node on a path forwards
queries by repeatedly referring current nodes to next nodes.

Logarithmic distance from node s.
（ = log d(s, ei) ）

160
158
156
154
152
150

Best routing table (reference)
Transfer at join and active learning lookups (proposal)
Transfer at join and random lookups
Active learning lookups
Random lookups

148
146
144

0
s=e
o

10
e

10

20
e

20

30
e

30

40
e

40

50
e

50

60
e

60

70
e

70

e80
80

Routing table entries ei at a node s.

Fig. 7.
Logarithmic distance from node s.
（ = log d(s, ei) ）When we designed GFRT-Chord, we first decided to maintain some nodes in the routing table, such as the successor
list, the predecessor, the group successor list, and the grouppredecessor. These are the sticky entries. DHTs often define
exceptional entries to maintain in order not only to guarantee reachability but also to achieve fault tolerance, localize
communications, or replicate data efficiently. FRT is designed
to not interfere with such constraints for a routing table withsticky entries and offers a way to exclude these entries throughentry filtering. No matter what entries we define as sticky
entries, entry filtering can reflect node identifiers because theorder on routing tables can be applied to any subset of therouting table set.
When we designed GFRT-Chord, we adopted the policy that
it is better for a routing table at a given node to maintain morenodes belonging to the same group as that node. Factors wewish to introduce into routing algorithms are often independentof node identifiers because node identifiers are determined
without regard of node characteristics, yet we must integrate
such factors and node identifiers into an algorithm. FRT
facilitates resolution of this difficulty. FRT converts rigid data
structures that are hard to deal with into a single routing tableby defining the order ≤ID on candidates for the routing table.
As a result, we can easily introduce factors other than node
identifiers into routing algorithms by considering not how tokeep better combinations of node identifiers but how nodes
should be maintained based on the factors.
On the other hand, it is not always true that path lengths accurately represent routing efficiency, due to factors other thannode identifiers. Rather, node identifiers should be maximallyreflected in routing tables after sufficient reflection of otherfactors. FRT provides the ability to do this by detachmentof the concerns of node identifiers from data structures, i.e.
routing tables in the form of an order ≤ID . This way, we
can reflect node identifiers in routing tables with sufficientreflection of other factors.

Routing table entries after 25 lookups.

160
158
156
154
152
150

Best routing table (reference)
Transfer at join and active learning lookups (proposal)
Transfer at join and random lookups
Active learning lookups
Random lookups

148
146
144

0
s=e
o

10
e

10

20
e

20

30
e

30

40
e

40

50
e

50

60
e

60

70
e

70

e80
80

Routing table entries ei at a node s.

Fig. 8.

Routing table entries after 100 lookups.

We varied whether each joining node receives an entire
routing table from a successor (transferring at join) or not,and recorded node identifiers of entries in a routing table atthe last joined node. We plotted log d(s, ei ), the logarithmic
distance from the node to each entry in its routing table after
25 queries and 100 queries, using its best routing table as a
guide (Fig.7, Fig.8). The closer the graph of an experimentalrouting table is to the best routing table, the better its learning
method. Fig.7 and Fig.8 show that routing tables approach thebest routing table through repeated entry learning and entry
filtering.
Fig.7 and Fig.8 also show that transferring at join andactive learning lookups perform well because the routing
tables without them are quite different from their best routing
table. By comparing routing table learning only by random
lookups to routing table learning by transferring at join alongwith random lookups, we can see that transferring at join
is effective. This is because the node learns more entries bytransferring from the successor in joining, and the best routing
table for a node is similar to the best routing table of its
successor. On the other hand, we can also see that even if
a routing table does not obtain entries through a transfer atjoin, the routing table can still approach the best routing tablethrough active learning lookups.
When we compare Fig.7 to Fig.8, we can see that routing
tables with active learning lookups approach the best routing
table more quickly than the others. This means that active
leaning lookups are efficient for leaning as compared withrandom lookups.

Proc. 11th IEEE Int'l Conf. on Peer-to-Peer Computing (IEEE P2P'11), pp.72-81, August 2011

These results show that transferring at join and active leaning lookups work efficiently for learning, and entry filtering
also works as expected.
B. Learning and Path Lengths in FRT-Chord
After N nodes join an FRT-Chord system, we repeat sending
a query 50N times, where each query is sent to a randomly
chosen key by a randomly chosen node. This means theaverage number of queries sent by a node is 50. We vary
the number of nodes N and the routing table size L and we
set the length of the successor list as 4.
Fig.9 indicates the average path lengths for every N queries.
This figure shows that repeating lookups shortens the averagepath lengths. The number of lookups shortens the path lengths
at almost the same range for every node, regardless of thenumber of nodes in the system. Thus, under FRT-Chord thesystem is able to scale at entry learning and entry filtering.
C. Path Lengths and the Number of Nodes in FRT-Chord
We varied N and L, and measured how path lengths changewith greatly refined routing tables. Fig.10a and Fig.10b plot
the average and the 99th percentile of path lengths. Thesefigures show that FRT-Chord achieves O(log N )-hop lookup
performance, as described by Theorem 5. We can confirm that
we are able to tune the trade-off between L and path lengths.
When L > N (N = 102 , L = 160), routing tables have allnodes in the system and FRT-Chord achieves O(1)-hop lookup
performance.
D. Path Lengths in GFRT-Chord
We also implemented GFRT-Chord on Overlay Weaver.
Experiments with the implementation showed that averagepath lengths grow slightly as compared with FRT-Chord.
N nodes joined the system and nodes were composed of |G|groups. Each group had N/|G| nodes. Each node repeated an
active learning lookup 500 times. The variables, N , |G|, andL are parameterized. The successor list length and the groupsuccessor list length were set as 4.
Fig.11a and Fig.11b plot average path lengths and averagegroup path length. A group path length is the number of hops
between two nodes belonging to different groups in a path,and thus a group path length is smaller than a path length.
In Fig.11a and Fig.11b, average path lengths in GFRT-Chord
are larger than in FRT-Chord. This is because the routing table
construction in GFRT-Chord is taken with the restriction ofnode groups, unlike FRT-Chord. In every situation, however,they differ slightly from each other, because the restriction ofnode groups in GFRT-Chord is not overly rigid and FRT isable to balance node identifier considerations and node groupconsiderations in parallel. For example, for |G| = 10 and L =20, when N = 102 each node group has only 10 nodes andthe routing table at most includes only 10 nodes belonging
to the same group. GFRT-Chord does not try to maintain theratio of same group entries to other entries, but it uses therest of the routing table at maximum and refines the entries
according to the order ≤ID . GFRT-Chord therefore experiences

only 1% path length growth, while attaining a 22% grouppath length decrease. Such percentages in path lengths growthand group path length decrease are not particularly important.
This experiment shows that path lengths do not become overly
large due to consideration of node groups in spite of the small
number of nodes belonging to the same group. On the other
hand, when N = 103 each node group has 100 nodes. GFRTChord is therefore able to choose entries belonging to the samegroup from a number of entry candidates according to theorder ≤ID , and it treats entries not belonging to the samegroup like-wise. In this situation, therefore, GFRT-Chord alsoachieves only 6% path length growth, while decreasing grouppath length by 38%.
VI. C ONCLUSION
This paper proposed flexible routing tables (FRT), a method
to design routing algorithms for overlay networks, and proposed FRT-Chord, an FRT-based DHT.
An FRT-based algorithm is able to reflect node identifiers inrouting table construction without restrictions on routing table
candidates by defining and referring to a total order ≤ID on arouting table set.
To analyze FRT-Chord, we implemented and experimented
on the algorithm, and showed that the routing table is efficiently refined as expected, and that the algorithm achieves
O(N )-hop lookup performance in an N -node network andO(1)-hop lookup performance in a small network.
This paper also proposed Grouped FRT (GFRT), an extended method based on FRT to reflect node groups, anddesigned GFRT-Chord, a GFRT-based DHT.
Experiments on GFRT-Chord show that GFRT-Chord reduces the number of hops from one group to another while
avoiding long path. It shows the extendability of FRT-basedalgorithms, in that GFRT-Chord reflects node identifiers andnode groups simultaneously.
We are finishing design of FRT-Kademlia, an FRT-based
DHT with an identifier space based on XOR metrics. In future,
we will design more FRT-based DHTs and extend them to deal
with real world problems in addition to node grouping.
R EFERENCES[1] I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan,“Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications,” in Proc. ACM SIGCOMM ’01, 2001, pp. 149–160.
[2] S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Schenker, “A
Scalable Content-Addressable Network,” in Proc. ACM SIGCOMM ’01,
2001, pp. 161–172.
[3] B. Y. Zhao, J. D. Kubiatowicz, and A. D. Joseph, “Tapestry: An
Infrastructure for Fault-tolerant Wide-area Location and Routing,”
EECS Department, University of California, Berkeley, Tech. Rep.
UCB/CSD-01-1141, Apr 2001. [Online]. Available: http://www.eecs.
berkeley.edu/Pubs/TechRpts/2001/5213.html[4] A. Rowstron and P. Druschel, “Pastry: Scalable, Decentralized Object
Location, and Routing for Large-Scale Peer-to-Peer Systems,” in Proc.
IFIP/ACM Middleware 2001, 2001, pp. 329–350.
[5] P. Maymounkov and D. Mazières, “Kademlia: A Peer-to-Peer Information System Based on the XOR Metric,” in Proc. IPTPS ’02, 2002, pp.
53–65.
[6] M. F. Kaashoek and D. R. Karger, “Koorde: A Simple Degree-OptimalDistributed Hash Table,” in IPTPS ’03, 2003, pp. 98–107.

Proc. 11th IEEE Int'l Conf. on Peer-to-Peer Computing (IEEE P2P'11), pp.72-81, August 2011

9

9
L=40

L=80

6
5
4
3
2

40

3
2

50

20

30

40

FRT-Chord (L=160)

6

Chord

5
4
3
2
1
0

N=10^3
Number of nodes

Fig. 10.

18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0

10

20

30

40

50

FRT-Chord (L=20)
FRT-Chord (L=40)
FRT-Chord (L=80)
FRT-Chord (L=160)
Chord

N=10^3
Number of nodes

N=10^4(b) 99th percentile of path length

Correlation between routing table size and path length.

6
FRT-Chord (L=20)
FRT-Chord (L=40)

FRT-Chord (L=10)

N=10^2

N=10^4

GFRT-Chord (L=20)
GFRT-Chord (L=40)

4
path length growth3
2
1

Average (group) path length

Average (group) path length0

Average number of lookups per node(a) Average path length52(c) N = 104

99th percentile of path lengths

Average path length

FRT-Chord (L=40)
FRT-Chord (L=80)

6

3

Change in average path length with the number of queries per node.

FRT-Chord (L=20)

N=10^2

4

50

FRT-Chord (L=10)

7

L=160

0
10

11

8

L=80

5

(b) N = 103
Fig. 9.

L=40

6

Average number of lookups per node(a) N = 102

9

L=20

7

1
0

Average number of lookups per node

10

8

L=160

4

0
30

L=80

5

0
20

L=40

6

1
10

L=20

7

1
0

9

8

L=160

Average path length

L=20

7

Average path length

Average path length

8

5

FRT-Chord (L=20)
FRT-Chord (L=40)

GFRT-Chord (L=20)
GFRT-Chord (L=40)

4
3
2
1

group path length decrease
0

0
|G|=2

|G|=5

|G|=10(a) N = 102
Fig. 11.

|G|=2

|G|=5

|G|=10(b) N = 103

Average path length with average group path length (shaded portion).

[7] G. S. Manku, M. Bawa, and P. Raghavan, “Symphony: Distributed
Hashing in a Small World,” in Proc. USITS’03, 2003, pp. 127–140.
[8] P. Fonseca, R. Rodrigues, A. Gupta, and B. Liskov, “Full-Information
Lookups for Peer-to-Peer Overlays,” IEEE Trans. Parallel Distrib.
Syst., vol. 20, pp. 1339–1351, September 2009. [Online]. Available:
http://portal.acm.org/citation.cfm?id=1591896.1592267[9] B. Leong, B. Liskov, and E. D. Demaine, “EpiChord: Parallelizing theChord Lookup Algorithm with Reactive Routing State Management,”
Comput. Commun., vol. 29, pp. 1243–1259, May 2006. [Online].
Available: http://portal.acm.org/citation.cfm?id=1646651.1646839[10] H. Zhang, A. Goel, and R. Govindan, “Improving lookup latency in
distributed hash table systems using random sampling,” IEEE/ACM
Trans. Netw., vol. 13, pp. 1121–1134, October 2005.
[11] M. J. Freedman and D. Mazières, “Sloppy Hashing and Self-Organizing
Clusters,” in IPTPS ’03, 2003, pp. 45–55.
[12] D. R. Karger and M. Ruhl, “Diminished Chord: A Protocol for Hetero-geneous Subgroup Formation in Peer-to-Peer Networks,” in IPTPS ’04,
2004, pp. 288–297.
[13] Y. Zhang, D. Li, L. C. 0002, and X. Lu, “Flexible Routing in Grouped
DHTs,” in Proc. 2008 8th Int. Conf. Peer-to-Peer Computing, 2008, pp.
109–118.
[14] J. Kleinberg, “The Small-World Phenomenon: An Algorithmic Perspective,” in Proc. ACM STOC 2000, 2000, pp. 163–170.
[15] G. Cordasco and A. Sala, “2-Chord Halved,” in Proc. HOT-P2P’05. Washington, DC, USA: IEEE Computer Society, 2005, pp. 72–
79. [Online]. Available: http://portal.acm.org/citation.cfm?id=1090948.
1091377[16] K. Shudo, Y. Tanaka, and S. Sekiguchi, “Overlay Weaver: An Overlay
Construction Toolkit,” Comput. Commun., vol. 31, no. 2, pp. 402–412,
2008.
[17] K. Shudo, “Overlay Weaver: An Overlay Construction Toolkit,” http://overlayweaver.sourceforge.net/.

Proc. 11th IEEE Int'l Conf. on Peer-to-Peer Computing (IEEE P2P'11), pp.72-81, August 2011