1

FRT-2-Chord: A DHT Supporting Seamless
Transition between One-hop and Multi-hop Lookups
with Symmetric Routing Table
Yasuhiro Ando, Hiroya Nagao, Takehiro Miyao and Kazuyuki Shudo Tokyo Institute of Technology
2-12-1 Ookayama, Meguro-ku, Tokyo 152-8552 Japan
Email: {yasuhiro.ando, hiroya.nagao, takehiro.miyao, shudo}@is.titech.ac.jp

Abstract—FRT-2-Chord is a DHT based on Flexible Routing
Tables, a method for designing routing algorithms for overlays.
DHTs should consider the following factors when constructing
overlay topologies: the number of nodes, identifier distance,
network proximity and node groups. Existing DHTs either do
not adapt to those factors or focus on only some of them. FRT2-Chord is more adaptable and achieves efficient routing undera variety of conditions of those factors. Theoretical analysis andexperimental results show the efficiency of FRT-2-Chord.
Keywords—overlay network, structured overlay, peer-to-peer,
DHTs, routingI.

I NTRODUCTION

Overlay networks offer scalability and fault tolerance forpeer-to-peer systems.They are classified into two types: unstructured and structured. In unstructured overlay networks,
requests are flooded or randomly routed to find data items. In
structured overlay networks, the overlay topology is organizedbased on constraints and a request is routed efficiently to data
items by a set of logical rules. Structured overlays are usedprimarily by distributed hash tables (DHTs).
Many peer-to-peer systems impose requirements such as
low latency, low bandwidth utilization and lookup correctness.
To satisfy these requirements, DHTs should consider thefollowing factors when constructing their overlay topologies:
the number of nodes, identifier distance, network proximity,
node groups and so on. If a DHT could not adapt to changes inthese factors, it could not offer scalability and fault tolerance.
At a minimum, DHTs should meet the following requirements
for adaptability.
1) Routing efficiency independent of the number ofnodes. In peer-to-peer systems, the number of nodes
and the rate of joins and leaves change dynamically anddepend on applications.
1-a) Short path length. When the number of nodes
is larger than the maximum number of neighbors
per node, a query reaches its destination node inmultiple hops. In a DHT, a query is routed inO(log N )-hops by using only O(log N ) neighbors
per node, where N is the number of nodes. As an
example of the importance of this point, the numberThis work was supported by MEXT KAKENHI (24650025 and 25700008).

of nodes in the structured overlay network which isconstructed by BitTorrent [1] [2] clients reaches 10
millions [3].
1-b) Ability to route a query in one-hop. If the numberof nodes is less than or equal to the size of therouting table, an node should forward a query toits destination directly, that is, in a one-hop lookup.
For example, distributed storage systems such as
Amazon Dynamo [4] and Apache Cassandra [5] [6]use a DHT to provides one-hop lookups. Using sucha DHT, responsibility for data items is distributed
among the nodes without centralized control anddata access latency is reduced.
2) Handling of factors that affect neighbor selection. A
DHT should take account of network proximity and nodegroups in addition to short path length. If network proximity is ignored, a lookup may be routed through nodes
that are far away in the physical network. For example,
proximity-aware routing tables enable file sharing systems
to reduce data access latency. When node groups is notconsidered, hops across Internet service providers or data
centers may occur frequently. For example, distributed
storage systems account for node groups in the same rack
or in the same datacenter when placing and accessing
replicas [5] [6] [7]. A DHT should consider those independent factors when constructing routing tables.
2-a) Flexibility of a routing table construction. A DHT
is designed to consider identifier distance when constructing routing tables. Extensions to a DHT may
consider other factors. Each extension focuses ona single factor because the factors are independent.
Hence, flexibility of a routing table construction isrequired for a DHT to be able to consider each ofthese factors.
2-b) Symmetry of routing tables. Symmetry of routing
tables is the following property: when the routing
table of node x contains node y, the routing tableof node y tends to contain node x. Symmetry ofrouting tables reinforces consideration to network
proximity and node groups. The consideration takes
effect on the nodes in a pair because those factors
are symmetric between them. Moreover, symmetryof routing tables reduces routing table maintenanceProc. Int'l Conference on Information Netwoking 2014 (ICOIN 2014), February 2014

2

TABLE I.

DHT S AND REQUIREMENTS .

(1-a)
(1-b)
(2-a)
(2-b)
Pastry
S
N
N
S
Chord
S
N
N
N
Kademlia
S
N
N
S
S-ChordS
S
N
N
EpiChordN
N
N
OneHopN
S
N
FRT-Chord
S
N
S
N
S
S
S
S
FRT-2-Chord(1-a) : Short path length(1-b) : Ability to route a query in one hop(2-a) : Flexibility of routing table construction(2-b) : Symmetry of routing tables
S : A DHT satisfies a requirement
N : A DHT does not satisfy a requirement

costs, because query messages also serve as heartbeat messages. That is, a node sends a message toanother node in its routing table and the receiving
node knows the sending node is alive.
Numerous DHTs have been proposed over the last decade[8] [9] [10] [11] [12] [13] [14]. However, existing DHTs
do not satisfy all of above requirements or focus on only apart of them; this lack restricts the situations in which those
DHTs offer efficient routing. This paper presents FRT-2-Chord,a DHT based on Flexible Routing Tables (FRT). FRT [14]is a method for designing routing algorithms. FRT-2-Chordsatisfies all of the requirements detailed above.
II.

R ELATED W ORK

Table I lists existing DHTs and FRT-2-Chord and showswhether each satisfies the requirements described in Section
I. Chord [8], Pastry [9], S-Chord [11] and Kademlia [10]achieve O(log N )-hop lookup with O(log N ) neighbors per
node. However, in these DHTs a routing table cannot containall nodes in an overlay even if the routing table size islarger than N . It is due to such constraints imposed by thesealgorithms that a part of a routing table can hold only limited
node identifiers. For example, neither a finger in Chord nor ak-bucket in Kademlia can hold arbitrary node identifiers. This
restriction prevents queries from being routed in one hop. In
EpiChord [12] and OneHop [13], the routing table size is large
enough to contain all nodes in an overlay. However, to achievethis, EpiChord and OneHop do not work when the numberof nodes is larger than expected. In FRT-Chord [14], an FRTbased DHT, a routing table can contain all nodes in an overlay
as long as routing table size is larger than N . However, in
Chord-based DHTs such as FRT-Chord and EpiChord, a queryis forwarded to the destination node after being forwarded toits predecessor. These queries require two or more hops toreach the destination node; that is, those Chord-based DHTs
do not achieve one-hop even when the routing table of thenode that issued the query holds the destination node.
In OneHop and EpiChord, routing tables are naturally
symmetry because they contain all nodes in the overlay. In
Chord and FRT-Chord, routing tables are not symmetic due totheir identifier distance described in Section II-A. In Pastry,
Kademlia and S-Chord, routing tables are symmetic.
A. Chord
Chord is a DHT, in which identifiers are represented as acircle of numbers from 0 to 2m − 1. A node identifier is m
bits long and chosen by hashing the node’s IP address.
In a DHT, data are stored as key-value pairs. A data identifieris produced by hashing the key and the data is stored at a nodeaccording to the data identifier. In Chord, a node is responsible
for a key if the node’s identifier is equal to the identifier of the
key or follows it. A query is routed according to the identifier
distance from ID x to ID y, d(x, y),which is defined as follows.
Definition 1:{
y − x,(x < y)d(x, y) =(1)
y − x + 2m , (y ≤ x)
In Chord, each node maintains three routing tables (successor list, predecessor, and finger table). Each entry in a routing
table is a node identifier and IP address pair. A successor listat node s contains a certain number of the closest nodes froms in the clockwise direction, and the successor is the closest
node of those nodes. A predecessor contains the closest nodefrom s in the anticlockwise direction. A stabilization protocol
is used to guarantee reachability by maintaining the successorof each node.
The ith entry in the finger table is the first node that succeedss by at least 2i−1 (i = 1, 2, ...., m) in the clockwise direction.
In Chord, a query with the target identifier t is forwarded asfollows.
1) Current node c forwards to the entry node e from which
the distance to t is minimal in c’s finger table. By repeating this forwarding, the query reaches the predecessor oft.
2) The predecessor of t forwards to the successor.
Chord achieves O(log N )-hop lookup performance with N
nodes.
B. FRT-Chord
FRT is a method of designing routing algorithms for structured overlays. An FRT-based algorithm defines a total orderon node identifier combinations in a routing table and then,repeatedly refines routing tables on the basis of the order.
FRT-Chord is an FRT-based DHT. In FRT-Chord, the identifier space and forwarding mechanism are the same as in
Chord and the node responsible for a key is determined as in
Chord. Each node maintains a single routing table E without
distinguishing among a successor list, a predecessor, and afinger table, and FRT-Chord can dynamically change the sizeof the routing table. A routing table E at a node s is a set of
entries {ei } which are ordered clockwise from s. Each entry ei
consists of a node identifier ei .id and an IP address ei .address(note that ei is referred to as ei .id). By this definition e1 and
e|E| correspond to a successor and a predecessor.

Proc. Int'l Conference on Information Netwoking 2014 (ICOIN 2014), February 2014

31) Total Order ≤ID of the Routing Table Set: FRT-Chord
defines a total order ≤ID on node identifier combinations
in a routing table. Routing tables are refined according to
the total order ≤ID . In FRT-Chord, the reduction ratio of aquery forward is defined as d(E.forward(t), t)/d(s, t), where
E.forward(t) is the entry in the routing table E, to which
the query for target identifier t is forwarded by node s. A
reduction ratio expresses how close to t the entry E.forward(t)is in comparison to s. In FRT-Chord, the reduction ratio of aforwarding to ei takes its worst-case value when t = ei+1 .
The worst-case reduction ratio ri (E) of forwarding to a nodeei for defining a total order ≤ID is defined as follows:
Definition 2:
ri (E) =d(ei , ei+1 )(i = 1, 2, ..., |E| − 1)d(s, ei+1 )(2)Let {r(i) (E)} be the list of redecution ratios arranged indescending order. The total order of the routing table set basedon {r(i) (E)} is defined as follows.
Definition 3:
E ≤ID F ⇔ {r(i) (E)} ≤dic {r(i) (F )}(3)where ≤dic is the lexicographical order.
2) Guarantee of Reachability: Any operations that guarantees reachability is called a guarantee of reachability. The
stabilization protocol such as Chord realizes the guarantee of
reachability in FRT-Chord. Entries concerning a guarantee of
reachability are called sticky entries. For example, a successor
list and a predecessor are sticky entries.
3) Entry Learning: In FRT, learning a node identifier and IP
address and then inserting them into a routing table are called
entry learning. Whenever one node is informed about anothernode’s identifier and IP address, the node learns them.
4) Entry Filtering: When the number of entries |E| exceeds
the size of a routing table L, FRT-Chord will remove one of theentry from the current routing table in order to keep |E| ≤ L
according to the order ≤ID . This entry removal operation iscalled entry filtering.
C. GFRT-Chord
GFRT-Chord [14] is an extension of FRT-Chord in order
to consider node groups. It reduces hops across different
node groups while keeping path lengths short. Its methods ofguarantee of reachability and entry learning are the same as
FRT-Chord. It is characterized by its entry filtering.
III. FRT-2-C HORD
FRT-2-Chord is an FRT-based DHT. In FRT-2-Chord, theidentifier space is the same as in Chord and entry learning is
the same as in FRT-Chord.
A. Node Responsible for a Key and Forwarding
In FRT-2-Chord, the identifier distance from x to y, d(x, y),is defined as follows.
Definition 4:d(x, y) = min{|x − y|, 2m − |x − y|}(4)

By this definition, d(x, y) = d(y, x) holds for any x andy; that is, distance is symmetric. Since routing tables areconstructed according to a total order on identifier distancein FRT-2-Chord, routing tables will also be symmetric. In
FRT-2-Chord, the node responsible for a target identifier t
is the node s that minimizes d(t, s). A node forwards a
message to an entry node e in the routing table, whered(e, t) is minimized among any other entries. When there
exists entries e, e0 satisfying d(e, t) = d(e0 , t) and d(e, t) is
minimized among any other entries, a node forwards a message
to e, where dchord (e, t) < dchord (e0 , t), letting dchord (x, y)be the identifier distance in Chord. The node that terminates
forwarding is the node responsible for t. In contrast to other
Chord-based DHTs, in FRT-2-Chord the node responsible for a
key is the destination node by definition of identifier distance.
Therefore, a node is able to route a query in one hop, if its
routing table contains the node responsible for t. In FRT-2Chord, a node may forward a message in either the clockwise
direction or anticlockwise direction. We call this the two
directions property.
B. Total Order ≤ID of the Routing Table Set
We find the worst-case reduction ratio for defining the totalorder ≤ID in FRT-2-Chord. Let E be the routing table of anode s. A routing table E satisfies i < j ⇒ dchord (s, ei ) <dchord (s, ej ), (ei , ej ∈ E). Here, we will focus on the worstcase reduction ratio of a forward to a node ei . Let mi
be the median value of the path from ei to ei+1 in theclockwise direction. FRT-2-Chord routes a query from ei tot in the clockwise direction or in the anticlockwise direction.
If clockwise, the reduction ratio of a forward to ei takes theworst-case value when t = mi . If anticlockwise, the worst-casevalue occurs when t = mi−1 . Let ricw (E) be the worst-case
reduction ratio of forwarding to a node ei in the clockwise
direction; let riacw (E) be the worst-case reduction ratio of
forwarding to a node ei in the anticlockwise direction. Fig.
1 shows the relation among positions ei−1 , ei , and ei+1 in theclockwise or anticlockwise directions from s.
We define a set of the worst-case reduction ratio {ri (E)}for defining a total order as follows.
Definition 5:{ri (E)} = {ricw (E)} ∪ {riacw (E)}(5)

Let {r(i) (E)} be the list of reduction ratios arranged indescending order. We define a total order ≤ID in FRT-2-Chordas follows.
Definition 6:
E ≤ID F ⇔ {r(i) (E)} ≤dic {r(i) (F )}(6)

In this definition, ≤dic is the lexicographical order operator.
Let ek be the entry that is on the path from s to s + 2m−1 inthe clockwise direction and is the closest to s+2m−1 . Now, we
describe ricw (E) and riacw (E) in detail. The following theorem
holds.
Theorem 1:{ricw (E)} ∪ {riacw (E)} = {ricw (E)}.

Proc. Int'l Conference on Information Netwoking 2014 (ICOIN 2014), February 2014

(7)

4

C. Guarantee of Reachability
FRT-2-Chord and FRT-Chord have different handling ofsticky entries and guarantees of reachability. Because of thetwo directions property, in addition to the successor list andpredecessor, sticky entries include a predecessor list, which isa list containing a certain number of the nodes closest in the
anticlockwise direction.

Fig. 1. Relation among positions of entries in clockwise and anticlockwise
directions from s.

D. Entry Filtering
In FRT-2-Chord, we define the updated worst-case reduction
ratio RiE when ei is removed as follows.
Definition 7:|d(s, ei+1 ) − d(s, ei−1 )|
(i 6= k, i 6= k + 1)d(s, ei+1 ) + d(s, ei−1 )
(11)
RiE =

2m − d(s, ei+1 ) − d(s, ei−1 )(i = k, k + 1)
2m − |d(s, ei+1 ) − d(s, ei−1 )|Entry filtering in FRT-2-Chord is summarized as follows.
1) Substitute entries in E into C
2) Remove sticky entries from C3) Select the entry ei from C that minimizes RiE .
By sorting RiE into ascending order, the entry to be removed
can be found efficiently. The following theorems of FRT-Chord
hold for FRT-2-Chord as well.
Theorem 2: In FRT-2-Chord, let E−{ei∗ } be a routing tablefiltered by removing ei∗ . For any ei which is not a sticky entry,

Fig. 2. Example of relation among positions of s, ek , and ek+1 whered(ek , mk ) 6= d(ek , ek+1 )/2 holds.

Proof: The calculation of d(ei , mi ) when i 6= k isdifferent from the one when i = k. When i 6= k, d(ei , mi ) =d(ei , ei+1 )/2. Otherwise, d(ei , mi ) = 2m − d(s, ei ) −d(s, ei+1 ). Fig. 2 shows an example of the relation between
positions; in this example case, d(ek , mk ) 6= d(ek , ek+1 )/2
holds.
ricw (E) and riacw (E) are defined as follows.
|d(s, ei+1 ) − d(s, ei )|(i 6= k) d(s, e ) + d(s, e )i+1iricw (E) =(8)

2m − d(s, ei+1 ) − d(s, ei )(i = k)2m − |d(s, ei+1 ) − d(s, ei )|riacw (E) =(i 6= k + 1)
2 − d(s, ei ) − d(s, ei−1 )
2m − |d(s, ei ) − d(s, ei−1 )|(i = k + 1)

i−1mTherefore, (7) holds.
Then, we let ri (E) be ricw (E).

l∗ = min{j|RiE∗ > r(j) (E)}(13)

l = min{j|RiE > r(j) (E)}(14)

A list of {r(i) (E − {ei∗ })} from the beginning to l∗ +1 is given by r(1) (E), r(2) (E), ..., r(l∗ −1) (E), RiE∗ , r(l∗ ) (E).
Then, the list of {r(i) (E − {ei∗ })} from the beginning tol∗ − 1 is preserved across entry filtering. Similarly, a list of{r(i) (E − {ei })} from the beginning to l + 1 is given byr(1) (E), r(2) (E), ..., r(l−1) (E), RiE , r(l) (E). For any j,{ri (E − {ej })} = {ri (E)} ∪ {RjE } − {rj (E), rj−1 (E)} (15)holds. Futhermore,(16)

hold. Therefore, a list of {r(i) (E − {ei })} from the beginning(9) to l − 1 is preserved across entry filtering. Since RE∗ ≤ REiiholds by definition of i∗ , l∗ ≥ l also holds. Therefore,r(i) (E − {ei∗ }) = r(i) (E − {ei })(i = 1, 2, ..., l − 1)

Clearly,acw
ricw (E) = ri+1
(E).

(12)

Proof: We are focusing on the updated worst-case reduction ratio. Let l∗ and l be as follows.

RjE > rj (E), RjE > rj−1 (E)|d(s, ei ) − d(s, ei−1 )| d(s, e ) + d(s, e )i

E − {ei∗ } ≤ID E − {ei }.

(10)

(17)

and
r(l) (E − {ei∗ }) ≤ r(l) (E − {ei })hold. Hence, (12) holds.

Proc. Int'l Conference on Information Netwoking 2014 (ICOIN 2014), February 2014

(18)

5

It is possible that routing table refinement through repeatedentry learning and entry filtering will stop when any mostrecently learned entry is selected as the entry to remove. Sucha routing table E is called a convergent routing table, and thefollowing theorem holds.
Theorem 3: In FRT-2-Chord, 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: SiE is defined as follows.
d(s, ei+1 )(i = 1, 2, ..., k − 1)
log d(s, e )
i
E
Si =
(19)

d(s, ei )log(i = k + 1, ..., |E| − 1)d(s, ei+1 )
2m − d(s, ek )log d(s, e
k+1 )
SkE =
m

2 − d(s, ek+1 )logd(s, ek )(d(s, ek+1 ) ≤ d(s, ek ))(20)(d(s, ek+1 ) > d(s, ek ))Let J be a set of indices j, where a node exists in the range
from ej to ej+1 in the clockwise direction; let L be a set ofindices l, where a node exists in the range from el−1 to el inthe clockwise direction; let P be a set of indices p otherwise.
By definition,Eri (E) = 1 − 2/(2Si + 1)

(21)

holds for any i, j = 1, ..., |E| − 1. Therefore, if ri (E) < rj (E)holds, then SiE < SjE holds for i.
E

E

RiE = 1 − 2/(2Si +Si−1 + 1)

(22)

holds for any i, j = 2, 3, ..., k − 1, k + 2, ..., |E| − 1. Therefore,EE
holds for< SjE + Sj−1
if RiE < RjE holds, then SiE + Si−1
any i, j = 2, 3, ..., k −1, k +2, ..., |E|−1. Since all nodes have
convergent routing tables,
rjcw (E) = rj (E) ≤ RiE(23)

for any j ∈ J and for any i = 2, ..., |E| − 1. Similarly,
rlacw (E) = rl−1 (E) ≤ RiE(24)

holds for any l ∈ L and for any i = 2, ..., |E| − 1. Withhigh probability, the distance between two generic consecutive
nodes is at least 2m /N 2 [15]. For any j ∈ J, the following
inequality holds.
∑
EE2≤i≤|E|−1,i6=k,i6=k+1 (Si + Si−1 )
E
Sj ≤
(25)
|E| − 4
8
<
log N
(26)
|E| − 4Thus, for |E| = 4 + (8/ log 3) log N ,rj (E) < 1 −2
1=
2
N 8/|E|−4 + 1(27)

Similarly, rl−1 (E) < 1/2 holds for |E| = 4+(8/ log 3) log N .
We now consider the upper limit of path lengths needed toreduce the remaining distance to 2m /N or less. If the message
is forwarded to ep (p ∈ P ), the responsible node is ep , and therouting will terminate. We focus on the case where each node
forwards to ei (i ∈ J or i ∈ L). Because the remaining distanceis obviously 2m−1 or less, and, the worst-case reduction ratio isunder 1/2 when the message is forwarded to a node in either
the clockwise direction or anticlockwise direction, the path
length is log N − 1. When the remaining distance is at most
2m /N , the number of node identifiers landing in a range ofthis size is O(log N ) with high probability [8]. Thus, the query
reaches the destination node within an additional O(log N )hops. Therefore, the entire path length is O(log N ).
E. GFRT-2-Chord
GFRT-2-Chord is an extension of FRT-2-Chord in order toconsider node groups. Its methods of guarantee of reachability
and entry learning are the same as FRT-Chord. It is characterized by its entry filtering. We define the following variables
for the routing table E = {ei } at a node s.
• EG = {e ∈ E | e.group = s.group}• EḠ = {e ∈ E | e.group 6= s.group}• eα is the closest entry in EG from s in the clockwise
direction.
• eβ is the closest entry in EG from s in the anticlockwise
direction.
• Enear = {e ∈ E | d(s, e) < d(s, eα ) ∨ d(s, e) <d(s, eβ )}• Efar = {e ∈ E | d(s, eα ) ≤ d(s, e)∧d(s, eβ ) ≤ d(s, e)}• Eleap = Efar ∩ EḠ
In GFRT-2-Chord, sticky entries are a successor list, apredecessor list, a group successor list and a group predecessor
list. The group successor list and the group predecessor listat a node s means a successor list and a predecessor list
respectively in a network limited to nodes belonging to thesame group as s.
GFRT-2-Chord performs entry filtering as follows:
1) Substitute entries in EḠ into C if Eleap 6= ∅, otherwise
substitute entries in E into C.
2) Remove sticky entries from C3) Select the entry ei from C that minimizes RiE .
IV. E VALUATION
We implemented FRT-2-Chord on Overlay Weaver [16] [17],an overlay construction toolkit, and performed experiments. In
all experiments the routing table size is 160, the size of thesuccessor list is 4 (FRT-2-Chord and FRT-Chord), and the sizeof the predecessor list is 4 (FRT-2-Chord). We employ queries
for iterative lookup in all experiments.
A. Path Lengths in FRT-2-Chord
After N nodes join a system, each node sends a query
200 times; each query is sent to a randomly chosen key
by a randomly chosen node (N = 102 , 103 , 104 ). Fig. 3
shows the average path length for N queries; these data
reveal that average path lengths and number of lookups are

Proc. Int'l Conference on Information Netwoking 2014 (ICOIN 2014), February 2014

6+,-./0-"1/23"4-5023!

*">?@AB39.=CDE#!!!!F">?@A$AB39.=CDE#!!!!F">?@AB39.=CDE#!!!F">?@A$AB39.=CDE#!!!F">?@AB39.=CDE#!!F">?@A$AB39.=CDE#!!F"

)"
("
'"
&"
%"
$"
#"

R EFERENCES

!"
!"

'!"
#!!"
#'!"
+,-./0-"5678-."9:"499;61<"1-."59=-!

$!!",-./01."2034"5.6134!

Fig. 3. Change of average path length along with the number of lookups per
node.
2034"5.6134"7.38..6"90:."1/;<2"6;=.9">*?@AB$BC4;/=D"2034"5.6134"7.38..6"90:."1/;<2"6;=.9">*?@ABC4;/=D"2034"5.6134"7.38...6"=EF./.63"1/;<29"6;=.9">*?@AB$BC4;/=D"2034"5.6134"7.38..6"=EF./.63"1/;<29"6;=.9">*?@ABC4;/=D"
("
'"
&"
%"
$"
#"
!"
)*)"+"$"

Fig. 4.

V. C ONCLUSION
In this paper, we proposed FRT-2-Chord, an FRT-based
DHT. FRT-2-Chord can adapt factors such as number of nodes,
network proximity, and node groups. Because of this, FRT-2Chord efficiently routes in a wider range of situations thanexisting DHTs do.

)*)"+"'")*)"+"#!")*)"+"$!"

Average path length.

both reduced in FRT-2-Chord and FRT-Chord. FRT-2-Chord
repeatedly refines routing tables by entry learning and entry
filtering, and average path length in FRT-2-Chord is shorter
than in FRT-Chord.
When N is 102 the routing table size is larger than thenumber of nodes. Thus, each node is able to have entries forof all the nodes. In this experiment, after 200 lookups fromeach node, average path length is 1.01 in FRT-2-Chord. After
additional 1000 lookups from each node, average path length
approaches 1.00.

B. Path Lengths in GFRT-2-Chord
We also implemented GFRT-2-Chord on Overlay Weaver.
After N nodes each of which belong to a group chosenrandomly join a system, each node sends a query 200 times.
In the experiments, we set |E| = 20, N = 1000 and size ofthe group successor list and size of the group predecessor list
are 1. Fig. 4 shows average path length average path length
between different group nodes.
The forwarding mechanism in GFRT-2-Chord is able to be
regarded as removing the last hop to the node responsible
for a key in GFRT-Chord. In experiments, path length in
GFRT-2-Chord is more than one hop shorter than in GFRTChord. Therefore, the reduction of path length in GFRT-2Chord derives from not only the forwarding mechanism but
also the routing table construction with the identifier distance.

[1] BitTorrent, http://www.bittorrent.com/.
[2] B. Cohen, “Incentives build robustness in bittorrent,” in 1st Workshop
on Economics of Peer-to-Peer systems, vol. 6, 2003, pp. 68–72.
[3] K. Jünemann, “Dsn research group-live monitoring,” 2011, http://dsn.
tm.uni-karlsruhe.de/english/2936.php.
[4] G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman,
A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels, “Dynamo:
Amazon’s highly available key-value store,” in Proc. SOSP ’07, vol. 41,
no. 6. ACM, 2007, pp. 205–220.
[5] Apache Cassandra, The Apache Software Foundation, http://cassandra.
apache.org/.
[6] A. Lakshman and P. Malik, “Cassandra: a decentralized structured
storage system,” ACM SIGOPS Operating Systems Review, vol. 44,
no. 2, pp. 35–40, 2010.
[7] Apache Hadoop, The Apache Software Foundation, http://hadoop.
apache.org/.
[8] I. Stoica, R. Morris, D. Karger, M. Kaashoek, and H. Balakrishnan,“Chord: A scalable peer-to-peer lookup service for internet applications,” ACM SIGCOMM Computer Communication Review, vol. 31,
no. 4, pp. 149–160, 2001.
[9] A. Rowstron and P. Druschel, “Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems,” Proc.
IFIP/ACM Middleware 2001, pp. 329–350, 2001.
[10] P. Maymounkov and D. Mazieres, “Kademlia: A peer-to-peer information system based on the xor metric,” Proc. IPTPS ’02, pp. 53–65,
2002.
[11] V. Mesaros, B. Carton, and P. Van Roy, “S-chord: Using symmetry to
improve lookup efficiency in chord,” in Proc. PDPTA ’03, 2003.
[12] B. Leong, B. Liskov, and E. Demaine, “Epichord: parallelizing the chord
lookup algorithm with reactive routing state management,” Computer
Communications, vol. 29, no. 9, pp. 1243–1259, 2006.
[13] P. Fonseca, R. Rodrigues, A. Gupta, and B. Liskov, “Full-information
lookups for peer-to-peer overlays,” IEEE Trans. Parallel and Distrib.
Syst., vol. 20, pp. 1339–1351, 2009.
[14] H. Nagao and K. Shudo, “Flexible routing tables: Designing routing
algorithms for overlays based on a total order on a routing table set,”in Proc. IEEE P2P ’11, 2011, pp. 72–81.
[15] G. Cordasco and A. Sala, “2-chord halved,” Proc. HOT-P2P ’05, pp.
72–79, 2005.
[16] K. Shudo, Y. Tanaka, and S. Sekiguchi, “Overlay weaver: An overlay
construction toolkit,” Computer Communications, vol. 31, no. 2, pp.
402–412, 2008.
[17] K. Shudo, Overlay Weaver: An Overlay Construction Toolkit, http://
overlayweaver.sourceforge.net/.

Proc. Int'l Conference on Information Netwoking 2014 (ICOIN 2014), February 2014