A Structured Overlay
for Non-uniform Node Identifier Distribution
Based on Flexible Routing Tables
Takehiro Miyao, Hiroya Nagao, Kazuyuki Shudo
Tokyo Institute of Technology
2-12-1 Ookayama, Meguro-ku, Tokyo, JAPAN
Email: {takehiro.miyao, hiroya.nagao, shudo}@is.titech.ac.jp

Abstract—A large fraction of structured overlays work efficiently as long as node identifiers follow a uniform distribution
with high probability. There is another kind of structured
overlay supporting non-uniform node identifier distributions andit enables a DHT to support range queries. This paper presents
FRT-Chord# , such a structured overlay for non-uniform node
identifier distributions. It is based on Flexible Routing Tables(FRT), a method for designing structured overlays, and inherits
advantageous features of FRT, that existing overlays do nothold. Such features include extensibility, arbitrary routing tablecapacity.

I. I NTRODUCTION
There are a number of structured overlays, routing algorithms for peer-to-peer, proposed. A large fraction of structured overlays including initially proposed ones [1]–[5] were
designed to achieve efficient lookups in case node identifiers
follow a uniform distribution with high probability. They do
not work efficiently otherwise.
However, there are applications that require structured
overlays for non-uniform node identifier distributions. Range
queries over a Distributed Hash Table (DHT) is one ofsuch applications. Range queries require assigning continuous
identifiers to data with continuous keys to achieve efficient
lookups. Otherwise continuous keys are distributed to numerous nodes, that a range query has to involve. Such a continuous
assignment leads to a non-uniform data identifier distribution.
In case data identifiers are distributed non-uniformly, loadbalance is a problem. Virtual nodes is one of solutions to
the problem. We focus on another promising solution, that is
to make a node identifier distribution follow a data identifier
distribution. To achieve it, node identifiers can be adjusted
by leave and rejoin of nodes. Here a structured overlay
supporting non-uniform node identifier distributions achieves
range queries and load balance.
There are structured overlays for non-uniform node identifier distributions proposed [7], [8]. Such overlays enable a
DHT supporting range queries, and support efficient lookups
with a small number of nodes. With few nodes, consistenthashing [6] and other hashing techniques for determining nodeThis work was supported by JSPS KAKENHI Grant Numbers 25700008
and 24650025.

identifiers leads to non-uniform node identifier distributions.
Furthermore, such overlays enable arbitrary assignments ofnode identifiers. For example, node identifiers can reflect
network proximity.
This paper presents FRT-Chord#, a structured overlay
for non-uniform node identifier distributions. FRT-Chord# isbased on Flexible Routing Tables (FRT) [9], a method fordesigning structured overlays, and thus inherits advantageous
features of FRT, that the existing overlays do not hold. Suchfeatures include extensibility [9], [10], arbitrary routing tablecapacity, and one-hop property [11]. GFRT [9] and PFRT [10]are examples of extensions to FRT-based structured overlays.
GFRT is an extension to consider node groups and PFRT is
for network proximity. FRT-Chord# itself does not perform
exact 1 hop routing, but it achieves the lowest route length,that is 2, in case the number of node is less than routing tablecapacity thanks to the one-hop property of FRT.
Experimental results show that FRT-Chord# works efficiently with non-uniform node identifier distributions as wellas with a uniform distribution.
This paper is structured as follows. Section II presents priorknowledge by introducing related work. Section III describes
FRT-Chord#. Section IV demonstrates the properties of FRTChord# including adaptability to non-uniform node identifier
distributions and arbitrary routing table capacity inherited from
FRT. In Section V, we summarize our contributions.
II. RELATED WORK
A. Chord
Chord [1] is one of initially proposed structured overlays.
Chord was designed to achieve efficient lookups under conditions where node identifiers follow a uniform distribution withhigh probability.
Chord assigns an m-bit identifier to a node by hashing
the node’s address. The identifier space in Chord has a ring
structure, with identifier distance d(x, y) between identifiers x
and y in a clockwise direction in the ring calculated asy − x,
x < y,d(x, y) =(1)
y − x + 2m , y ≤ x.

Proc. 19th IEEE Symposium on Computers and Communications (IEEE ISCC 2014), June 2014

node snode si th entry of s

i+1 th entry

ei

ei+1

Identifier
spaced(s,ei+1)d(ei,ei+1)
Worst-case reduction ratio ri ( E ) =s+2m-2m-2 th entry

m-1 th entrys+2m-1
Fig. 1.

Finger table

The first node that an identifier reaches while progressing
clockwise is called the successor node.
Each entry in a routing table holds a node’s identifier andits address, but in this paper an entry is sometimes expressedas the node pointed to by the entry. Routing tables in Chord
consist of three parts: a successor list, a predecessor, and afinger table. The successor list of a node contains a certain
number u closest nodes from the node in the identifier space.
The successor list is used for reaching destination nodes. The
predecessor is the farthest node from the node in the identifier
space. The finger table is used to decrease route lengths. The
ith entry (i = 0, 1, 2, . . . m − 1) of the finger table for a nodes contains the successor node of the identifier s.id + 2i (Fig.
1). Thus, if N is the number of nodes, then the number of
entries in a finger table is about log N .
In Chord, stabilize and notify functions guarantee reachability. All nodes periodically execute stabilize to search for theircurrent successors. When a node finds a new successor, it executes notify to instruct the successor to update its predecessor.
A node periodically executes fix fingers function to ensure its
finger table entries are correct. Lookups are performed for
identifier s.id + 2i (i = 0, 1, 2, ..., m − 1) in fix fingers, andthe node updates the ith entry of the finger table.
When routing, a request message arrives at the destination
node by greedy routing, which selects a forwarding nodefrom the routing table as follows. The message is repeatedly
forwarded from each node to the neighbor closest to thedestination identifier in the node’s routing table. Route lengths
in Chord are O(log N )-hops when node identifiers follow a
uniform distribution with high probability.
B. FRT-Chord
Flexible Routing Tables (FRT) [9] is a method for designingstructured overlays. FRT-based algorithms have various advantageous features, such as extensibility, arbitrary routing table

Fig. 2.

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

Worst-case reduction ratio

capacity, and one-hop property.
FRT-Chord [9] uses the same identifier space as Chord does.
However, a node s in FRT-Chord maintains only a single
routing table E containing entries ei (i = 1, 2, . . . |E|),
which are sorted in ascending order of identifier distance froms (i < j ⇒ d(s, ei ) < d(s, ej )). Thus, {ei }i=1,2,...u is the
successor list of s, where e1 is s’s successor, u is the capacityof the successor list, and e|E| is s’s predecessor. Since routing
tables in FRT-based algorithms are maintained by using a totalorder ≤RT on the set of all routing table patterns, designers
need to define the order.
1) Total Order on Routing Table Set: Routing tables are
updated according to ≤RT , which is a total order on the set of
all routing table patterns. E ≤RT F then expresses that routing
table E is better than F , and this determination is based on
identifier distance between nodes. The order in FRT-Chord isdefined as follows.
A node s calculates the worst-case reduction ratio ri (E)(Fig. 2) of a forwarding to a node ei other than its predecessor.
The reduction ratio is the fraction by which the remaining
identifier distance is reduced when s forwards a message toeach entry ei :ri (E) =d(ei , ei+1 )d(n, ei+1 )(i = 1, 2, . . . |E| − 1).

(2)

Let {r(i) (E)} be the list in which ei are ranked in descending order by {ri (E)}. Then,E ≤RT F ⇐⇒ {r(i) (E)} ≤dic {r(i) (F )},(3)

where the lexicographical order ≤dic is defined as follows:{ai } <dic {bi } ⇔ ak < bk(k = min{i|ai = bi }), (4){ai } =dic {bi } ⇔ ai = bi ,{ai } ≤dic {bi } ⇔ (ai <dic bi ) ∪ (ai =dic bi ).

(5)
(6)

2) Guarantee of Reachability: These operations guarantee
reachability in FRT. Guarantee of reachability function in
FRT-Chord relies on the same as stabilize and notify in Chord.
3) Entry Learning: This function obtains a node’s information and inserts it into a routing table in FRT. A node obtains
another node’s information in the following situations.
• When a new node joins the network in FRT-Chord, it
obtains information on its successor and the informationin the successor’s routing table.

Proc. 19th IEEE Symposium on Computers and Communications (IEEE ISCC 2014), June 2014

When node s communicates with node a, s obtains a’s
information.
• Each node periodically executes active learning lookups
function to obtain information on other nodes.
•

node sE \ {er } ≤RT E \ {e},∀e ∈ E.

(8)

By calculating a canonical spacing SiE for each entry ei inE, er can be found efficiently:
SiE = logd(s, ei+1 ).
d(s, ei )(9)E
If SiE −1 + SiE is the minimum value of Si−1
+ SiE for ei ,then er = ei . In FRT, any entry that must not be removed
from the routing tables is called a sticky entry. Sticky entries
in FRT-Chord consist of the successor list and predecessor
entries that are required to reach a destination node.
The steps in entry filtering are as follows. Let C be the setof candidates for er .

1) Add all entries in E to C.
2) Remove the sticky entries from C.
3) When SiE −1 + SiE is found for ei ∈ C, er equals ei andis removed from E.
E
By sorting {Si−1+ SiE } into ascending order, er can be foundin O(1) steps.

C. Chord#
Chord# [7] is a structured overlay. Chord# was designed
to achieve efficient lookups even when node identifiers do notfollow a uniform distribution.
Chord# uses the same identifier space as Chord and uses
greedy routing. Routing tables in Chord# are similar to thosein Chord, but the finger tables are different. Chord builds
finger tables on the basis of identifier distance between any
two nodes. Therefore, the route lengths in Chord are larger
when node density in an identifier range is high. However,
Chord# builds finger tables on the basis of the number ofnodes between any two nodes. Thus, the route lengths in
Chord# are not long, even when node density is high.

i+1 th entry

ei

ei+1

Identifier
space

Obtain from ei
and update i+1 th entry

Active learning lookups in FRT-Chord actively acquires
node information, and is similar to fix fingers in Chord.
When a node s executes active learning lookups, a lookup
is performed for the identifier k calculated by
d(s, e|E| ) rnd
k = s.id + d(s, e1 ),(7)d(s, e1 )where rnd is a random number between 0 and 1. s then obtains
the node information on k’s successor.
4) Entry Filtering: If the number of entries |E| in therouting table E is greater than the capacity L of the routing
table, then some entries should be removed from E. Entry
filtering is the function that removes an entry in FRT. The
function determines the entry for removal er according to ≤RT ,as follows:i th entry of sei.ei

i th entry of ei
Fig. 3.

Finger table in Chord#

An entry ei has not only the entry’s identifier ei .id andaddress ei .addr, but also the ith entry ei .ei of ei ’s finger table.
A finger table consists of entries as follows (Fig.3):successor, i = 0,
ei =
(10)
ei−1 .ei−1 , i > 0.
In Chord#, each node periodically executes stabilize andnotify to guarantee reachability, as in Chord. Each nodeperiodically executes fix fingers to make sure its finger table
entries are correct. Fix fingers in Chord# is different from thatin Chord, in that the node obtains the ith entry of ei ’s finger
table from ei and updates the i + 1th entry of its own finger
table.
III. FRT-C HORD#
We presented FRT-Chord# , which is a structured overlay
for non-uniform node identifier distribution. FRT-Chord# is
an FRT-based algorithm, and so inherits advantageous featuresof FRT.
FRT-Chord# uses the same identifier space as Chord andbuilds routing tables with neighbor nodes’ routing tables, so
an entry e has the entry’s identifier e.id, address e.addr androuting table e.RT.
A. Total Order on Routing Table Set
To design FRT-Chord# , we define a total order ≤RT on arouting table set. First, let ns (x) be the number of entries froms.id to an identifier x. FRT-Chord# uses an identifier spacewith a ring structure. Therefore,ns (x) = max{i|d(s, ei ) ≤ d(s, Es .forward(x)), ei ∈ Es }(11)
holds, where Es .forward(x) is the entry in routing table Es
to which node s forwards the message of destination identifier
x. When node s forwards to an entry ei ,Es .forward(x) = ei

(12)

ns (x) = i(13)holds, soalso holds. When ns (x) = 0 holds, node s is the determination
node of identifier x.
Next, let fs (x) be the reduction value in the number of
entries in [s, x) by a forwarding.
fs (x) = ns (x) − nEs .forward(x) (x)Proc. 19th IEEE Symposium on Computers and Communications (IEEE ISCC 2014), June 2014(14)

node si th entry of s

i+1 th entry

ei

ei+1

D. Entry Filtering
Identifier
space

j th entry of ei
ei.ej

Number of entries : nei (ei + 1) = j
Worst-case reduction value:

Fig. 4.

gi ( E ) = i - j

Worst-case reduction valueholds because (12) and (13) hold. Every forwarding reduces
ns (x) of each self node s so that ns (x) becomes 0. Therefore,
the higher fs (x) is, the better entry ei is.
Finally, let gi (E) be the worst-case reduction value in thenumber of entries when forwarding to entry ei (Fig. 3). A
node evaluates an entry ei by gi (E). gi (E) takes the worstcase value when x = ei+1 .id holds, sogi (E) = fs (ei+1 )(15)

holds. Because (14) holds,
gi (E) = ns (ei+1 ) − nEs .forward(ei+1 ) (ei+1 )(16)

also holds. Since FRT-Chord# uses a cyclic identifier spaceand greedy routing,Es .forward(ei+1 ) = ei

(17)gi (E) = ns (ei+1 ) − nei (ei+1 )(18)

holds. Therefore,

also holds. Because (13) holds,
gi (E) = i − nei (ei+1 )(19)

follows. The entry ei has the routing table of ei so node s cancompute gi (E) for ei .
E ≤RT F expresses that routing table E is better thanF . When gi (E) is higher, the entry ei gets a higher score.
Therefore, we define the total order on a routing table set as
follows:
E ≤RT F ⇔ {g(i) (F )} ≤dic {g(i) (E)}.

(20)

Then, {g(i) (E)} is the list in which ei are ranked in descendingorder by {fi (E)}.
B. Guarantee of Reachability
Guarantee of reachability in FRT-Chord# is the same asthat in FRT-Chord.
C. Entry Learning
Entry learning in FRT-Chord# is the same as that in FRTChord.

If the number of entries |E| in the routing table E is greaterthan the capacity L of the routing table E, then some entries
should be removed from E. Entry filtering removes an entry
according to ≤RT . Sticky entries in FRT-Chord# are the sameas in FRT-Chord.
The steps in entry filtering are as follows. Let C be the setof candidates for er .
1) Add all entries in E to C.
2) Remove the sticky entries from C.
3) When E \ {er } ≤RT E \ {e} holds for each e ∈ C, er
is removed from E.
By sorting {E \{ei }}i=1,2,... into the total order of the routing
table set, er can be found in O(1) steps. The number of{E \ {ei }} is L so sorting {E \ {ei }} has computational
complexity O(L log L). Comparison of two routing tables isin O(L) because of using lexicographical ordering. Therefore,
er can be found in O(L2 log L) steps.
IV. E VALUATIONIn this section, we evaluate FRT-Chord# through simulation. We implemented a DHT using FRT-Chord# in Overlay
Weaver [12], [13], which is an overlay construction toolkit,
and performed experiments on the following machine.
• Simulator: Overlay Weaver 0.10.1• Operating system: Linux 2.6.35.10-74.fc14.x86 64• Central processing unit: Intel Xeon E5620 (2.40 GHz)
• Java virtual machine: Java SE 6 Update 22
Nodes are assigned identifiers so that node identifiers follow
either a Zipf distribution (α = 0.95, 0.7) or a uniform
distribution.
A. Comparison with other algorithms
We measured route length in Chord, FRT-Chord and FRTChord# in simulations configured as follows:• Number of nodes: 10000• Successor list capacity: 4• Capacity of routing tables: 16.
Because the number of nodes is 10000, the number of
entries in a finger table in Chord is about 13; that is, thenumber of entries in all three parts of the routing tables in
Chord is about 18. Therefore, the capacity of a routing tablein FRT-Chord# is set at 16 so that FRT-Chord# does not havean advantage in the number of entries that can be held.
Fig. 5 shows the average and the 99th percentiles of route
length in Chord, FRT-Chord, and FRT-Chord# when node
identifiers follow a Zipf distribution (α = 0.7). Node densityof an identifier range in a Zipf distribution (α = 0.7) is higher
than in a uniform distribution. The average route length in
FRT-Chord# is 7.01, the average in Chord is 7.67 and theaverage in FRT-Chord is 7.33. The 99th percentile of route
length in FRT-Chord# is 12, the 99th percentile in Chord is15, and the 99th percentile in FRT-Chord is 15.
Fig. 6 shows the average and 99th percentiles of route lengthin Chord, FRT-Chord, and FRT-Chord# when node identifiersProc. 19th IEEE Symposium on Computers and Communications (IEEE ISCC 2014), June 2014

20
Average16

99th percentile

12
8
4

Route length
R

Route lengthR

20

Average16

99th percentile

12
8
4
0

0

Chord
Fig. 5.

Chord

FRT-Chord
FRT-Chord#
Structured overlays

Route lengths for Zipf distribution (α = 0.7)

Fig. 7.

FRT-Chord
FRT-Chord#
Structured overlays

Route lengths for uniform distribution

Route length

Average16

99th percentile

12
8
4

Averrage route length

8
20

N=100
N=1000N=10000

6
4
2
0
0

0

Chord

50

FRT-Chord
FRT-Chord#
Structured overlays
Fig. 8.

Fig. 6.

100
150
Routing table capacity

200

Route lengths in each routing table size

Route lengths for Zipf distribution (α = 0.95)

B. Advantageous features of FRT
follow a Zipf distribution (α = 0.95). Node density of an
identifier range in a Zipf distribution with α = 0.95 is higher
than in a Zipf distribution with α = 0.7. The average route
length in FRT-Chord# is 6.98, the average in Chord is 8.30,
and the average in FRT-Chord is 8.50. The 99th percentileof route length in FRT-Chord# is 12, the 99th percentile in
Chord is 16, and the 99th percentile in FRT-Chord is 18. Routelength in FRT-Chord# is less than in Chord and FRT-Chordwhen node identifiers follow a Zipf distribution (α = 0.95).
Figs. 5 and 6 show that route lengths in FRT-Chord# are lessthan in Chord and FRT-Chord when node identifier do notfollow a uniform distribution.
Fig. 7 shows the average and 99th percentiles of route lengthin Chord, FRT-Chord and FRT-Chord# when node identifiers
follow a uniform distribution. The average route length in FRTChord# is 6.97, the average in Chord is 7.21, and the averagein FRT-Chord is 6.76. The 99th percentile of route length in
FRT-Chord# is 12, the 99th percentile in Chord is 12, andthe 99th percentile in FRT-Chord is 11. Route length in FRTChord# is only as large as in Chord and FRT-Chord, even if
node identifiers follow a uniform distribution.
Figs. 5, 6 and 7 show that route lengths of FRT-Chord#in a uniform distribution are as large as in a Zipf distribution(α = 0.7, 0.95). Therefore, FRT-Chord# is a structured overlay suitable for non-uniform distributions of node identifiers.

We examined whether FRT-Chord# retains one of beneficial
features of FRT, such as arbitrary capacity of routing tables
and one-hop property. We measured the average route lengthin FRT-Chord# under the following parameter values:• Number of nodes: 100, 1000, and 10000.
• Capacity of each routing table: 20–160.
Fig. 8 shows the simulation results for the average route
length. As the capacity of the routing tables increases, theaverage route length decreases. Therefore, FRT-Chord# canset arbitrary routing table capacities.
When the number of nodes N is less than the capacity L ofeach routing table, for example, when N = 100 and L = 160,
the average route length is 2, which is the lowest route lengthof FRT-Chord# in usual cases. FRT-Chord# inherits the lowest
route length as 2 from Chord. In Chord a route requires 2 hops
at least to reach the responsible node. A route once reaches
the predecessor of the target identifier and then steps to the
responsible node. FRT-Chord# itself does not perform 1 hop
routing, but it achieves the lowest route length thanks to the
one-hop property of FRT.
V. C ONCLUSION
This paper presented FRT-Chord# , an FRT-based structured overlay for non-uniform node identifier distributions.
Structured overlays supporting non-uniform node identifier
distributions enable a DHT supporting range queries, support

Proc. 19th IEEE Symposium on Computers and Communications (IEEE ISCC 2014), June 2014

efficient lookups with a small number of nodes, and enable
arbitrary assignment of node identifiers, for example, identifierassignment based on network proximity.
FRT-Chord# is based on Flexible Routing Tables (FRT),a method for designing structured overlays, and thus inherits
advantageous features of FRT, that existing overlays do nothold. Such features include extensibility, arbitrary routing tablecapacity, and one-hop property.
Experimental results showed routing efficiency of FRTChord# with uniform and non-uniform node identifier distributions. In the non-uniform cases, FRT-Chord# showed betterroute length than structured overlays for uniform distributions
Even in the uniform case, the results are comparable to theother structured overlays. Another result supports that FRTChord# inherits one of features of FRT, arbitrary routing tablecapacity.
Future work includes comparison with Chord# . In a stablenetwork, without churn, FRT-Chord# and Chord# will show
similar route length. The difference between them is flexibilityof FRT-Chord#, in which a node can hold arbitrary nodes in its
routing table. We expect that flexibility of FRT-based overlays
results in adaptability to churn.
R EFERENCES[1] I. Stoica, R. Morris, D. Liben-Nowell, D. R. Karger, M. F. Kaashoek,
F. Dabek, and H. Balakrishnan, “Chord: A scalable peer-to-peer lookup
protocol for internet applications,” IEEE/ACM Trans. Netw., vol. 11,
no. 1, pp. 17–32, 2003.
[2] P. Maymounkov and D. Mazieres, “Kademlia: A peer-to-peer information systems based on the XOR metric,” in Proc. IPTPS ’02, MA, USA,2002, pp. 53–65.
[3] 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, Heidelberg, Germany, 2001, pp. 329–350.
[4] B. Zhao, L. Huang, J. Stribling, S. Rhea, A. Joseph, and J. Kubiatowicz,“Tapestry,” IEEE J. Sel. Areas Commun., no. 1, pp. 41–53.
[5] S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker,“A scalable content-addressable network,” ACM SIGCOMM Comput.
Comm. Rev., vol. 31, no. 4, pp. 161–172, 2001.
[6] D. Karger, E. Lehman, T. Leighton, R. Panigrahy, M. Levine, andD. Lewin, “Consistent hashing and random trees: Distributed caching
protocols for relieving hot spots on the world wide web,” in Proc. 29th
Annu. ACM Sypm. Theory of Computing. ACM, 1997, pp. 654–663.
[7] T. Schütt, F. Schintke, and A. Reinefeld, “Range queries on structured
overlay networks,” Comput. Commun., vol. 31, no. 2, pp. 280–291, 2008.
[8] A. R. Bharambe, M. Agrawal, and S. Seshan, “Mercury: Supporting
scalable multi-attribute range queries,” in ACM SIGCOMM Comput.
Commun. Rev., vol. 34, no. 4. ACM, 2004, pp. 353–366.
[9] 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, Kyoto, Japan, 2011, pp. 72–81.
[10] T. Miyao, H. Nagao, and K. Shudo, “A method for designing proximityaware routing algorithms for structured overlays,” in Proc. IEEE ISCC
’13, Split, Croatia, 2013.
[11] Y. Ando, H. Nagao, T. Miyao, and K. Shudo, “FRT-2-Chord: A DHT
supporting seamless transition between one-hop and multi-hop lookups
with symmetric routing table,” in Proc. ICOIN 2014, Phuket, Thailand,
2014.
[12] K. Shudo, “Overlay Weaver,” http://overlayweaver.sourceforge.net/.
[13] K. Shudo, Y. Tanaka, and S. Sekiguchi, “Overlay Weaver: An overlay
construction toolkit,” Comput. Comm., vol. 31, no. 2, pp. 402–412, 2008.

Proc. 19th IEEE Symposium on Computers and Communications (IEEE ISCC 2014), June 2014