IEEE P2P’14
September 2014

Routing Table Construction Method
Solely Based on Query Flows
for Structured Overlays
Yasuhiro Ando, Hiroya Nagao,
Takehiro Miyao, 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”

1/8

Contribution• Our finding:– Small number of hops does not require node
distance in routing table construction andmaintenance.
• E.g. Chord based on node ID difference and Chord# based on
number of nodes between nodes achieve O(log N) hops.

• Evidence:– Flow‐based FRT (FFRT):
A routing table construction method– FFRT‐Chord: An FFRT‐based structured overlay
2/8

Node distance based
routing table construction• Each node determines which other nodes to be on its
routing table based on• ID difference– in Chord, Kademlia, …
– Responsible nodes for self ID + 1, 2, 4, …, 2^iSelf

NodeID space• Number of nodes between the two nodes– in Chord#– 1, 2, 4, … 2^i nodes away from self
Self
Node 012 3 4

5ID space

3/8

Flow‐based FRT (FFRT)• A routing table maintenance method– Not node distance based– Instead, query flow based• An application of
Flexible Routing Tables (FRT) [P2P’11]– A routing table is just a list of nodes.
– A policy given by an algorithm designer ID
determines which nodes to be kept on a table.
– FFRT specifies a policy based on query flows:

FL

4/8

Query flow
• Query flow
– A node keeps query history: target IDs of therecent H queries including queries it forwards.
– Query flow for an entry in a routing table isthe number of queries in the query history tobe forwarded to the entry.
Target IDs in query history
Self

Nodeeiei+1

3
Query flow

1ei+2

Entries in routing tableID space
5/8

Query flow basedrouting table maintenance• A node refines its routing table to minimize
the variance of query flows of all the entries.
– In other words, towards a state in which all nodes on
the table have equal query flows.
– When Entry Filtering of FRT, A node selects a removed
node to minimize …
–FL : Routing tables with smaller variance precede.
Target IDs in query history
Self

Nodeeiei+1

3
Query flow

1ei+2

Entries in routing table
ID space
6/8

Experiments• Confirmed that an FFRT‐based overlay
achieves comparable hop counts withexisting overlays.
– It works well with nonuniform ID distributions
because its routing maintenance is not besed on IDs,
though comparison with overlays for nonuniform ID
distributions such as Chord# is part of future work.

• FFRT‐Chord implemented on Overlay Weaver[ComCom 2008] and compared with FRT‐Chord.
– FRT‐Chord shows smaller hop counts than Chord withmoderate routing table sizes, 20 or larger.
Refer to the paper for graphs.

7/8

Summary and future work
• In structured overlays,
small number of hops such as O(log N)
does not require node distance in routing
table construction and maintenance.
– Query flow based method, FFRTand FFRT‐Chord presented as an evidence.

• Future work
– Theoretical analysis and reasoning.
• With weighted graph, or so?
8/8