IEEE ISCC 2014
June 2014

A Structured Overlay
for Non‐uniform Node Identifier Distribution
Based on Flexible Routing Tables
Takehiro Miyao, Hiroya Nagao,Kazuyuki Shudo
Tokyo TechBackground:

Structured Overlay• An application‐level network– routes a query to the responsible node.
Servers /nodes

Responsible node
for the requested
data item

Index range Responsible(digest)node
ab – dzea – gb
gc – …

192.168.0.2
192.168.0.3
192.168.0.4

Routing table– enables scalable data store and messaging.
• e.g. Distributed Hash Tables (DHT)“Shudo” ‘s tel # ?
“+81 3 5734 XXXX”

Contribution• A routing algorithm FRT‐Chord#– supports non‐uniform node ID distribution.
• Range queries require it.
• by Chord# [Schütt 2008] ‐inspired routing table
maintenance.

– has features existing overlays do not provide.
• Extensibility, arbitrary routing table size, and one‐hop property.
• by Flexible Routing Tables (FRT)[Nagao 2011] ‐based design.

Non‐uniform node ID
distribution• Traditional structured overlays– Node and data ID are generated with a hash function such as SHA‐1.
– Nodes in a routing table are selected based on node IDs.
DataSelf

NodeID space• To support range queries– Data are not hashed. Otherwise a query involves almost all nodes.
– Load imbalance is caused.
location, time, temperature, …

Data
Self

NodeID spaceNon‐uniform node IDdistribution• To support range queries– 1) Virtual nodes– 2) Making a node ID distribution follow a data ID distribution
Data
Self

NodeID space

Data
Self

NodeID space– But a non‐uniform node ID distribution leads

larger hop numbers / longer path length.

Non‐uniform node IDdistribution• Node order based routing table maintenance– Chord# [Schütt 2008] does it.
– cf. Node ID based– Efficient lookups = smaller hop numbers / shorter path lengthby having enough number of pointers to dense areas.
DataSelf
Node 01

2 3 4

5ID space– Our algorithm FRT‐Chord# adopts it.
We designed a Flexible Routing Table (FRT) based
described in next pages
algorithm that perform it.

Flexible Routing Tables (FRT)[Nagao 2011]• A unified framework for structured overlays.
– A methodology to design a routing algorithm
Arbitrarycombination

Ad‐hoc extensions toeach algorithm
Conflict

Node group

Proximity

One hop

Chord

Node group

Proximity

DHTalgorithms

One hop

Extensions

Conflict

Kademlia

Designed without
essence recognition

One hop

ID distance,
topology…

Ring(Chord)

Proximity

Nodegroup

XOR distance(Kademlia)…

Flexible Routing Tables(FRT)
Algorithm characteristics andgeneral actions are separated

Flexible Routing Tables (FRT)[Nagao 2011]• Declarative algorithm definition andcommon actions are separated.
• A routing table is just a list of entries.

• Algorithm definition–an algorithm designer provides

RT A total order on the set of all routing table patterns
Better is higher. “Better” means smaller hop numbers / shorter path length.

– Sticky entries
Routing table entries not to be removed from the table.
E.g. successor in Chord• Common actions

FRT provides– Entry learning A node notices another node and put it to the table.
– Entry filtering A table overflows, an entry is selected and removed.

Flexible Routing Tables (FRT)[Nagao 2011]• FRT‐based algorithms • Features of FRT– FRT‐Chord [Nagao 2011]– FRT‐2‐Chord [Ando 2014]– FRT‐XOR, that borrows ID spaceand distance from Kademlia– FRT‐Chord# (this paper)• Extensions– Proximity‐aware FRT(PFRT) [Miyao 2013]– Grouped FRT (GFRT)– Virtual Node Fusion (VNF)– Extensibility• Algorithms and extensions canbe combined arbitrarily.

– Arbitrary routing table size
– One‐hop property• A query reaches the responsible
node in one‐hop if # of nodes
the routing table size.
• Note that FRT‐Chord# itself does
not perform one‐hop lookup, but
2‐hop, that is lowest and thesame as Chord and Chord#.

• FRT‐Chord# achieves efficient lookups with non‐uniform
ID distribution while providing the features of FRT.

Evaluation• Goals: to confirm that
– Path length does not get longer even withnon‐uniform node ID distributions– FRT‐Chord# retains features of FRT• Compared with Chord and FRT‐Chord• Configuration– Routing table size: 16, determined to be fair with Chord– Distributed environment emulator of Overlay Weaver 0.10.1– Java SE 6 Update 22– Linux 2.6.35

Average path length

Node ID distributions andpath length# of nodes: 10,000

10Get longer

8Constant 64Uniform
Zipf: α = 0.7
Zipf: α = 0.95

20Chord

FRT-Chord FRT-Chord#• Path lengths do not depend on node ID distributions.

Node ID distributions andpath length• Zipf distribution with α = 0.95
Average path length1086# of nodes: 10,000
16% decreased  18% decreased 8.30

8.50

6.98

420Chord

FRT-Chord FRT-Chord#• FRT‐Chord# shows shorter path length.

Node ID distributions andpath length• Uniform distribution# of nodes: 10,000

Average path length

1083% decreased

3% increased

7.21

6.76

64

6.97

20Chord

FRT-Chord FRT-Chord#• Comparable with existing algorithms.

Average path length

Arbitrary routing table size
# of nodes
N = 10000
N = 1000
N = 100

864
2

A table holds all the nodes.

0050
100
150
Routing table size

200

One-hop property
FRT provides
Minimum path lengthof Chord-derived
algorithms is 2.

• Larger tables show shorter path lengths.
• FRT‐Chord# retains this feature: arbitrary …

Summary• FRT‐Chord# is a routing algorithm
for structured overlays– supports non‐uniform node ID distributions• Range queries require this feature.

– designed along Flexible Routing Tables (FRT)• Features: extensibility, arbitrary routing table size,and one‐hop property