14-th IEEE International Conference on Peer-to-Peer Computing

Routing Table Construction Method Solely Based on
Query Flows for Structured Overlays
Yasuhiro Ando, Hiroya Nagao, Takehiro Miyao and Kazuyuki Shudo
Tokyo Institute of Technology
Abstract—In structured overlays, nodes forward a query hop
by hop to deliver it to the responsible node for the query. Eachnode maintains its routing table and determines the next hop byreferring to the routing table. Each node has its node identifierand determines which other nodes to be on its routing table basedon node distance, that is defined by difference of node identifiersor the number of nodes between two nodes in identifier order.
In existing structured overlays, routing table construction andmaintenance based on node distance enable efficient lookup, thatis a small number of hop counts to the responsible node.
We found out that efficient lookup does not require node
distance in routing table construction and maintenance. As an
example, this paper presents Flow-based Flexible Routing Tables(FFRT), a routing table construction method solely based onquery flows. In an FFRT-based overlay, a node calculates queryflows, that is the amount of queries forwarded to each node
on its routing table. And the node maintains its routing tabletoward a state in which all nodes on the table have equal queryflows. FFRT also provides such a practical merit as it performs
efficient lookups though node and queries’ target identifiers are
distributed nonuniformly. The merit enables range query support.

I.

I NTRODUCTION

A structured overlay constructs an application-level networkand enables higher level services such as Distributed Hash
Table and message delivery. Nodes in an overlay forward aquery hop by hop to deliver it to the responsible node for thequery. Each node in an overlay maintains its routing table anddetermines the next hop by referring to the routing table.
In existing structured overlays, routing tables are constructed
and maintained based on node distance. Each node has its own
node identifier (ID), that is a number or a set of numbers. Nodedistance is defined by difference of the node IDs in Chord[1], XOR of the node IDs in Kademlia [2], or the numberof other nodes between the nodes in ID order in Chord# [3].
A node determines which other nodes to be on its routing
table based on the node distances to them from itself. Bychoosing the nodes along the rules prescribed by a structured
overlay, responsible node lookup is efficiently performed, inother words, a query reaches the responsible node in a small
number of hops such as O(log N ) hops with N nodes.
We found out that efficient lookup does not require node
distance in routing table construction and maintenance. This
paper presents Flow-based Flexible Routing Tables (FFRT),a routing table construction method and FFRT-Chord, an
FFRT-based structured overlay. FFRT-based overlays maintainrouting tables solely based on query flows without considering
node distance. A query flow is defined as the amount ofqueries forwarded between two nodes. A node in an FFRTbased overlay calculates query flows for all nodes on its routing
table. The node refines its routing table toward a state in which

all nodes on the table have equal query flows. FFRT is anapplication of Flexible Routing Tables (FRT) [4]. FFRT definesa total order ≤FL based on query flows instead of a total order≤ID that FRT-based overlays define based on node IDs. FFRT
inherits features of FRT including extensibility and arbitraryrouting table size.
FFRT-Chord is an FFRT-based overlay, which adopts Chordstyle ID space and distance. The ID space and distance arejust used to determine the responsible node for the target
ID of a query, and not used for routing table maintenance.
Experimental results showed that FFRT-Chord achieved higher
efficiency with nonuniform target ID distributions and nonuniform node ID distributions. Its efficiency is comparable toexisting structured overlays even with uniform node ID andtarget ID distributions. Here efficiency means smaller numberof hops, in other words, shorter path length.
This paper is organized as follows. Section II presents priorknowledge by introducing related work. Section III describes
FFRT and FFRT-Chord. Section IV demonstrates the properties
of FFRT-Chord including efficient lookups with nonuniform
target ID and node ID distributions. In Section V, we summarize our contributions.
II. R ELATED W ORK
A. Chord
Distributed Hash Table (DHT) is a higher level service
constructed on a structured overlay. It stores key-value pairs
on decentralized nodes. Both nodes and data have their IDs.
The responsible node, a node that holds a key-value pair, isdetermined according to the node and data IDs.
Chord [1] is a DHT, in which IDs are represented as a ringof numbers from 0 to 2m − 1. A node ID is m bits long anddetermined by hashing the node’s IP address. A data ID isgenerated from a key by a hashing function. A data item isstored at the responsible node, whose ID is equal to the data
ID or immediately follows it.
ID distance plays an important role in Chord. A routing tableis maintained based on it and then a query is routed according
to it. ID distance from x to y, d(x, y) is defined as follows.
Definition 1:
y−x(x < y)(x = y)2mdchord (x, y) =(1)
y − x + 2m (x > y)Chord achieves O(log N )-hop lookup performance with N
nodes.
B. Flexible Routing Tables
Flexible Routing Tables (FRT) [4] is a method of designing routing algorithms for structured overlays. An algorithmc978-1-4799-6201-3/14/$31.00 2014
IEEE

Proc. 14th IEEE Int'l Conf. on Peer-to-Peer Computing (IEEE P2P'14), September 2014

14-th IEEE International Conference on Peer-to-Peer Computing
designer can design a structured overlay by defining a totalorder ≤ID on the set of all patterns of a routing table andsticky entries. FRT does not suppose a specific ID space andthe designer chooses an ID space, for example a Chord-stylering or a Kademlia-style XOR space. A node in an FRT-based
structured overlay repeatedly refines its routing table according
the order by entry learning and entry filtering.
1) FRT-Chord: FRT-Chord [4] is an FRT-based structured
overlay. ID space and thus responsible nodes of FRT-Chord
are the same as Chord. In this section, we introduce FRT by
describing how FRT-Chord is designed based on FRT.
Each node maintains a single unified routing table E unlike
Chord, that has three parts as a successor list, a predecessor
and a finger table. A node can dynamically change the size of
its routing table because FRT-Chord inherits the property from
FRT. A routing table E at a node s is a set of entries {ei }which are ordered clockwise from s. Each entry ei consists ofa node ID ei .id and an IP address ei .address. Note that ei isreferred to as ei .id afterward. By this definition e1 and e|E|
correspond to a successor and a predecessor.
2) Total order ≤ID on Routing Table Set: FRT-Chord
defines a total order ≤ID based on node ID distance. A
node refines its routing table according to the total order.
FRT-Chord defines reduction ratio of a query forwarding asd(E.forward(t), t)/d(s, t), where E.forward(t) is an entry
on the routing table E, to which a query for target ID 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 case thetarget is in the interval between ei and ei+1 s forwards a query
to ei . In the case the reduction ratio takes its worst and largest
value when t = ei+1 . The worst-case reduction ratio ri (E) of
the forwarding to a node ei is defined as follows:
Definition 2:
ri (E) =Definition 4:
SiE = log

(3)

Steps in entry filtering are as follows. Let C be the set ofcandidates for a removed entry.
1) Put all entries in E into C
2) Remove sticky entries from C
E3) Select the entry ei in C that minimizes Si−1
+ SiE .
4) Remove e from E.
E
By sorting Si−1
+ SiE in ascending order, the removed entry
can be found efficiently.
III.

F LOW- BASED F LEXIBLE ROUTING TABLES

Existing structured overlays [1]–[3] achieve efficient lookup
by maintaining routing tables based on node distance. By
contrast, we found out that efficient lookup does not require
node distance based routing table maintenance. As an example,
we present Flow-based Flexible Routing Tables (FFRT), a
routing table construction method and FFRT-Chord, an FFRTbased structured overlay. Their routing table maintenance issolely based on query flows without considering node distance.
FFRT is an application of Flexible Routing Table (FRT)(Section II-B). FFRT defines a total order ≤FL based on queryflows in contrast to FRT-based overlays that define a totalorder based on node IDs. A query flow is defined as theamount of queries forwarded between two nodes. A node in
an FFRT-based overlay calculates query flows for all entries
on its routing table. The total order is defined as uniformityof query flows of all the entries. Each node refines its routing
table toward a state in which all entries on the table have equal
query flows. Each node counts the number of queries that it
forwards to other nodes regardless of whether the query is
originated by the node itself or not. A node calculates queryflows based on the counts.
FFRT defines the total order though FRT itself does notdefine a total order. An FRT-based overlay defines a total order.
An algorithm designer designs a structured overlay based on
FFRT by defining ID distance and sticky entries.
FFRT inherits features of FRT including extensibility andarbitrary routing table size. Proximity-aware FRT (PFRT) [5]and Grouped FRT (GFRT) [4] are examples of extensions to
FRT-based overlays. PFRT is an extension to consider network
proximity and GFRT is for node groups. They and otherextensions can be combined with all FRT-based and FFRTbased overlays. Arbitrary routing table size means that the sizesof routing tables are not fixed by a structured overlay. They
can vary per node and change as time goes on.
FFRT is not just an example of non-node-distance-based
structured overlays, but also provides a practical merit. FFRTbased overlays perform efficient lookups though node IDs andqueries’ target IDs are distributed nonuniformly because they
maintain routing tables solely based on query flows. DHT
introduces such nonuniformity. Queries’ target IDs, that aredata IDs in a DHT, are distributed nonuniformly when accessfrequencies of data are not uniform. For example, in filesharing systems, content popularity is biased. Range queriesd(ei , ei+1 )(i = 1, 2, ..., |E| − 1)d(s, ei+1 )Let {r(i) (E)} be the list of reduction ratios arranged indescending order. Based on {r(i) (E)}, the total order on theset of all patterns of a routing table is defined as follows.
Definition 3:
E ≤ID F ⇔ {r(i) (E)} ≤dic {r(i) (F )}d(s, ei+1 )d(s, ei )(2)where ≤dic is the lexicographical order.
3) Sticky Entry: Sticky entries are routing table entries thatare not removed by entry filtering. An algorithm designer defines sticky entries to guarantee reachability to the responsible
node. In FRT-Chord, sticky entries are a successor list and apredecessor as in Chord.
4) Entry Learning: In FRT-based overlays, a node inserts
other nodes into its routing table whenever the node is aware ofthem. A node notices the others passively by communications
for lookups and it can also perform active learning lookups.
5) Entry Filtering: When the number of entries |E| exceeds
the size of the routing table L, A node removes an entry.
A node refine its routing table by choosing a removed entry
according to the total order ≤ID .
By calculating a canonical spacing SiE for each entry ei inE, the removed entry can be found efficiently.
2

Proc. 14th IEEE Int'l Conf. on Peer-to-Peer Computing (IEEE P2P'14), September 2014

14-th IEEE International Conference on Peer-to-Peer Computing      

fei (E) = 3

sFig. 1.

ei+1

ei

C. Entry Filtering
When the number of entries |E| exceeds the size of a routing
table L, an FFRT-based structured overlay removes one of
the entries to keep |E| ≤ L. The removed node is selectedaccording to the order ≤FL . This operation is called entry
filtering inherited from FRT.
We define removal preference for an entry to determine
which node to be removed. The following ve (E) means how
much the variance of the routing table decreases by removing
an entry e.
Definition 7:



An example of query flow in FFRT-Chord.

also lead to a nonuniform data distribution. Range queriesrequire assigning continuous data IDs 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 nonuniform
data ID distribution. With nonuniform data ID distributions,load imbalance is a problem. Virtual node is one of solutions,but there is another promising solution, that is to make a node
ID distribution follow a data ID distribution. Node IDs canbe adjusted in advance or by leave and join of nodes. Suchadjustment leads to a nonuniform node ID distribution.

ve (E)

E \ {e∗ } ≤FL E \ {e}.
V(FE\{e} ) = V(FE ) − ve (E)ve∗ (E) ≥ ve (E)(4)|Q|/|E|

V(FE\{e∗ } ) ≤ V(FE\{e} ) (12)E \ {e∗ } ≤FL E \ {e} (13)

D. FFRT-Chord
FFRT-Chord is an FFRT-based structured overlay. FFRTChord adopts the ID space and the ID distance of Chord, that isdchord (x, y) (Section II-A). The ID space and ID distance arejust used to determine the responsible node and not used forrouting table maintenance. Responsible nodes in FFRT-Chord
are the same as Chord.
Sticky entries are the same as FRT-Chord. But, entry filtering
is different from existing overlays. It is carried out according
to query-flow-based total order ≤FL .
A routing table E = {ei } satisfies i < j ⇒ dchord (s, ei ) <dchord (s, ej ). By this definition e1 and e|E| correspond to a
successor and a predecessor as in Chord.

(6)

e∈E

=

⇐⇒
⇐⇒

If a node has few queries in its query history, it may bebetter to select a removed node based on node distance likean FRT-based overlay. But, especially without active learning
lookups, in case the routing table is filled, the query history
should have queries much the same.

(5)

V(FE ) is the variance of query flows for entries in a routing
table E. We define V(FE ) as follows.

V(FE ) =(fe (E) − ave)2
(7)
ave

(11)

holds. V(FE ) is 0 or larger. Because of them, the larger ve (E)gives the smaller V(FE\{e} ). Therefore,

Fig. 1 shows an example of a query flow in FFRT-Chord,that is described in Section III-D. In the figure, fei (E) is 3
because the number of queries to be forwarded to ei is 3. Notethat ID distance of FFRT-Chord is the same as Chord.
We define total order ≤FL on query flow as follows.
Definition 6:
E ≤FL E  ⇐⇒ V(FE ) ≤ V(FE  )(10)

Proof: For e ∈ E,

We define query flow fe (E) as follows.
Definition 5:
fe (E) = |{q ∈ Q | d(e, q) < d(e , q), ∀e ∈ E \ {e}}|(9)Steps in entry filtering in FFRT are as follows. Let C be theset of candidates for a removed entry.
1) Put all entries in E into C.
2) Remove sticky entries from C.
3) Select the entry e in C that maximizes removal preference ve (E). If there are multiple such entries, select theentry e of which query flow fe (E) is the lowest among
them. If there are still multiple such entries, select theentry e of which d(s, e) is largest among them.
4) Remove e from E.
The following theorem holds. It means the routing tableascends according to the total order ≤FL by the entry filtering.
Theorem 1: Let E \ {e∗ } be a routing table filtered byremoving e∗ . For any e which is not a sticky entry,

A. Total Order ≤FL Based on Query Flows
We define query flow as a basis of the definition of totalorder ≤FL . A node in an FFRT-based overlay keeps its query
history Q with the maximum size of the history H. The history
holds the target IDs of queries that the node forwarded to othernodes, not limited to nodes currently on its routing table. Notethat q ∈ Q is referred to as a target ID q.id.
If an ID distance is capable of greedy routing, we can definequery flow for a routing table entry. Capability of greedy
routing means that the ID distance enables a node to determine
uniquely the routing table entry to forward a query.
Let E be the routing table of s, d(x, y) be an ID distancefrom ID x to ID y and fe (E) be the query flow for an entrye ∈ E. fe (E) is the amount of queries that e is responsible forin the query history Q. When an entry e ∈ E is responsiblefor q ∈ Q, s would forward q to e, that is, following formula
holds.
d(e, q) < d(e , q), ∀e ∈ E \ {e}= V(FE ) − V(FE\{e} )(8)

B. Entry Learning
Entry learning is the same as FRT that is described in
Section II-B4.
3Proc. 14th IEEE Int'l Conf. on Peer-to-Peer Computing (IEEE P2P'14), September 2014

14-th IEEE International Conference on Peer-to-Peer Computing       This ve (E) enables efficient entry filtering as follows.
1) put all entries in E into C.
2) Remove sticky entries from C.
3) Select the entry e in C that minimizes fei (E)fei−1 (E).
If there are multiple such entries, select the entry e ofwhich query flow fe (E) is the lowest among them. If
there are still multiple such entries, select the entry eof which d(s, e) is largest among them.
4) Remove e from E.

fei−1 (E) = 7 fei (E) = 10 fei+1 (E) = 5


s

ei−1

ei

ei+1

       

fei−1 ( E ′) = 17

fei+1 ( E ′) = 5

ei−1

ei+1



s
Fig. 2.

Change of query flow in FFRT-Chord

IV.

1) Entry Filtering: We adopt the following removal preference to simplify the calculation.
Definition 8:ve (E) =(fe (E) − ave)2 − V(FE\{e} ) (14)This section demonstrates the following properties of path
length of FFRT-Chord compared with existing structured overlays.
• With uniform node ID and target ID distributions, comparable.
• With nonuniform target ID distributions, shorter.
• With nonuniform node ID distributions, shorter.
Shorter path length, in other words, smaller number of hops
indicates that the structured overlay is efficient. On real networks, efficiency involves network proximity as well not only
path length. Evaluation of FFRT combined with Proximityaware FRT (PFRT) [5] is part of future work.
In the experiments, we compare FFRT-Chord with FRTChord described in Section II-B1. FRT-Chord shows shorter
path length than Chord with the moderate routing table sizes,
that is 20 or larger [4]. Therefore, if it is shorter than
FRT-Chord, it is shorter than Chord. FRT-Chord and Chord
maintains routing tables based on node ID difference and they
do not adapt well to nonuniform node ID distributions. Future
work includes comparison with overlays for nonuniform node
ID distributions such as FRT-Chord# and Chord#.
We implemented FFRT-Chord on Overlay Weaver [6], [7],an overlay construction toolkit and conducted the experimentswith the toolkit. The routing table size L is 20, the successor
list size is 4 and the history size H is 500 in all theexperiments. The lookup style is iterative in all the experiments
but it does not affect the results.

e ∈E

ave

=

|Q|/L

(15)

ve (E) is a variant of ve (E) in Definition 7 and they are not thesame. The number of routing table entries to calculate V(FE )is L, not the precise number L + 1. But ve (E) can select theremoved node correctly. The following theorem holds.
Theorem 2: Let E \ {e∗ } be a routing table filtered byremoving e∗ . For any e which is not a sticky entry,
E \ {e∗ } ≤FL E \ {e}.

(16)Proof: For e ∈ E,
V(FE\{e} ) =(fe (E) − ave)2 − ve (E)

(17)

e ∈E

holds. V(FE ) and the first term of the right side of the formula
are 0 or larger. Because of them, the larger ve (E) gives thesmaller V(FE\{e} ). Therefore,ve∗ (E) ≥ ve (E)⇐⇒⇐⇒V(FE\{e∗ } ) ≤ V(FE\{e} ) (18)E \ {e∗ } ≤FL E \ {e} (19)

We can simplify ve i (E) by the fact that a node removal
affects fe (E) of just one node. In Fig. 2, an entry ei is removed
from a routing table E and only fei−1 (E) changes from 7 to
17.
Theorem 3:ve i (E) = −2fei (E)fei−1 (E) + ave2

A. Uniform Distributions
After N nodes join an overlay, each node sends a query 200
times in random order where each query is sent to a randomly
chosen target ID (N = 102 , 103 , and 104 ).
Fig. 3 shows the average and the 99th percentiles of path
lengths for the last N queries. The average path lengths in
FFRT-Chord were comparable to ones in FRT-Chord. In casesof N = 102 and 103 FFRT-Chord showed shorter average path
lengths. In case of N = 104 FFRT-Chord showed a longer
average path length, but the rate of the increase was 0.7%,
that is small. The 99th percentiles of the path lengths in FFRTChord were equal to ones in FRT-Chord.
These results indicate that FFRT-Chord is comparable to
FRT-Chord in path length with uniform node ID and target ID
distributions.

(20)

Proof: When an entry ei is removed from a routing table
E, only query flow fei−1 (E) changes. Therefore,⎧⎨ fej (E)(1 ≤ j ≤ i − 2)
fei−1 (E) + fei (E) (j = i − 1)fej (E \ {ei }) =⎩ f(i ≤ j ≤ |E| − 1)
ej+1 (E)By Definition 8,ve (E)E VALUATION= (fei−1 (E) − ave)2 − (fei−1 (E) + fei (E) − ave)2+(fe (E) − ave)2(21)
2= −2fei (E)fei−1 (E) + ave .
(22)
4Proc. 14th IEEE Int'l Conf. on Peer-to-Peer Computing (IEEE P2P'14), September 2014

14-th IEEE International Conference on Peer-to-Peer Computing$%%   

#
"
!


%
$
              "'& Fig. 4.

Path lengths with uniform node ID and target ID distributions.

 

B. Nonuniform Target ID Distributions
After 10000 nodes join an overlay, each node sends a query
200 times in random order where each query is sent to target
IDs distributed according to Zipf distributions (α = 0.7, 0.9,
and 1.1).
Fig. 4 shows the average and the 99th percentiles of path
lengths for the last 10000 queries. In cases of α = 0.7 and 0.9
FFRT-Chord showed shorter path lengths. In case of α = 1.1
the average path length in FFRT-Chord was 22% shorter than
one in FRT-Chord, but the 99th percentile of the path lengths
in FFRT-Chord was 1 longer than one in FRT-Chord.
These results indicate that FFRT-Chord adapts to nonuniform target ID distributions and it achieves efficient lookups
with such applications that involve nonuniform target ID
distributions, for example range queries. With heavily biased
target ID distributions, path lengths to a dense area in the ID
space tend to be short but path lengths to a sparse area tend tobe long. As a result, it achieves shorter average path lengths.

   &"& ))   (              
& 

Fig. 3.

#"       



%&
%$
*
(
'
&
$

++ 

## 

!  !   !  !   !  !   !  !  
! 
! 
! 
! 

Fig. 5.

")

Path lengths with nonuniform target ID distributions.

$ )$ +

% %Path lengths with nonuniform node ID distributions.

knowledge. But we found out that it is not necessary to consider node distance for efficient lookups. Flow-based Flexible
Routing Tables (FFRT), a routing table construction method isan evidence of the fact. FFRT-Chord, an FFRT-based overlay
performs efficient lookups by maintaining routing tables solely
based on query flows without considering node distance. FFRTChord shows shorter path lengths at least on average even withnonuniform target ID and node ID distributions.
Future work includes theoretical analysis on path length
while the analysis shown in Section IV is experimental.
ACKNOWLEDGMENT
This work was supported by JSPS KAKENHI Grant Numbers 25700008 and 26540161.

C. Nonuniform Node ID Distributions
IDs distributed according to Zipf distributions (α = 0.7,
0.9, and 1.1) are assigned to 10000 nodes. After the 10000
nodes join an overlay, each node sends a query 200 times in
random order where each query is sent to target IDs distributed
according to the same distribution as node IDs. This setting
represents a situation in which load imbalance (Section III)
has been mitigated by making the node ID distribution follow
the nonuniform target ID distribution.
Fig. 5 shows the average and the 99th percentiles of path
lengths for the last 10000 queries. FFRT-Chord showed shorter
path lengths than FRT-Chord in all the cases. FFRT-Chord
also showed shorter path lengths with the nonuniform node
ID distributions than with the uniform node ID distribution.
By contrast, FRT-Chord showed longer path lengths withnonuniform node ID distributions except the average path
length with α = 1.1, that is a relatively heavily biased
distribution.
These results indicate that FFRT-Chord adapts to nonuniform node ID distributions and it achieves efficient lookups
with node ID adjustment for load balance.

R EFERENCES
[1]

[2]
[3]

[4]

[5]

[6]

V. C ONCLUSION
Existing structured overlays have to consider node distancewhen constructing and maintaining routing tables. Otherwise
they cannot perform efficient lookups. It has been common[7]

I. Stoica, R. Morris, D. Liben-Nowell, D. Karger, M. F. Kaashoek,
F. Dabek, and H. Balakrishnan, “Chord: A scalable peer-to-peer lookup
protocol for internet applications,” IEEE/ACM Transactions on Networking, vol. 11, no. 1, pp. 17–32, Feb. 2003.
P. Maymounkov and D. Mazieres, “Kademlia: A peer-to-peer information
system based on the XOR metric,” in Proc. IPTPS’02, 2002, pp. 53–65.
A. Datta, M. Hauswirth, R. John, R. Schmidt, and K. Aberer, “Range
queries in trie-structured overlays,” in Proc. IEEE P2P’05, 2005, pp.
57–66.
H. Nagao and K. Shudo, “Flexible routing tables: Designing routing
algorithms for overlays based on a total order on a routing table set,” inProc. IEEE P2P’11, 2011, pp. 72–81.
T. Miyao, H. Nagao, and K. Shudo, “A method for designing proximityaware routing algorithms for structured overlays,” in Proc. IEEE
ISCC’13, 2013.
K. Shudo, Y. Tanaka, and S. Sekiguchi, “Overlay Weaver: An overlay
construction toolkit,” Computer Communications, vol. 31, no. 2, pp. 402–
412, 2008.
K. Shudo, Overlay Weaver: An Overlay Construction Toolkit,
http://overlayweaver.sourceforge.net/.

5

Proc. 14th IEEE Int'l Conf. on Peer-to-Peer Computing (IEEE P2P'14), September 2014