A Method for Designing
Proximity-aware Routing Algorithms
for Structured Overlays
Takehiro Miyao, Hiroya Nagao, Kazuyuki Shudo
Tokyo Institute of Technology
2-12-1 Ookayama, Meguro-ku, Tokyo, JAPAN
Email: {miyao8, hiroya.nagao, shudo}@is.titech.ac.jp

Abstract—In many structured overlays, nodes strictly maintaintheir routing tables using node identifiers. However, building
routing tables while taking account of the physical network is difficult. We propose proximity-aware flexible routing tables (PFRT)in this paper as a method to systematically design proximityaware routing algorithms for structured overlays. PFRT wasdeveloped by extending the flexible routing tables (FRT) method
such that network proximity is considered. Routing tables in FRTand PFRT-based algorithms are updated according to the orderof the set of all routing table patterns. FRT-based algorithms
define a total order based on node identifiers, whereas PFRTbased algorithms define two total orders based on node identifiers
and network proximity. Because PFRT is a simple extension of
FRT, PFRT-based algorithms also have many of the advantageous
features of FRT. We extended Chord to design PFRT-Chord,which is a PFRT-based algorithm. Experimental results showedthat PFRT-Chord preserves the expected FRT-derived properties
and it could take account of network proximity.

I. I NTRODUCTION
Today, many peer-to-peer (P2P) systems are available foruse over the Internet, such as Gnutella, BitTorrent, and Skype.
These P2P systems have several important characteristics,
including high scalability and fault tolerance. A P2P system
operates by building a virtual network, called an overlay
network, over a physical network at the application layer. The
overlay network is a directed graph in which nodes merely
maintain pointers to neighbor nodes. Therefore, P2P systems
are decentralized.
Although the topology of overlay networks can be arbitrary,
they are classified into two types: unstructured and structured.
The type of overlay network affects how a request message
reaches its destination node. In unstructured overlay networks,
the message is diffused like flooding to ensure that it arrives
at its destination node. In structured overlay networks, thearrangement of nodes is systematic, and a route from a source
to destination node is determined under a logical rule in orderto reduce route lengths and traffic volume.
A distributed hash table (DHT) is a P2P technology thatenables management of an associative array by numerous
This work was supported by MEXT KAKENHI (24650025), and “Newgeneration network R&D program for innovative network virtualization platform and its applications”, the Commissioned Research of National Instituteof Information and Communications Technology (NICT).

computers. Many routing algorithms for structured overlays
have been proposed for DHTs [1]–[6].
Often routing algorithms do not consider the physicalnetwork. However, nodes are located worldwide in real P2P
systems, and so their network proximity—measured in termsof communication latency, bandwidth, jitter, and so on—is not
uniform. Therefore, the overlay network is built as a weighted
graph in which each weight represents the network proximity
between two nodes.
Rules in structured overlays usually employ node identifiers.
Since these identifiers take random values, they determine theroute from a source to destination node without considering
network proximity. Consequently, a chosen route typically
includes many edges with high weights. In contrast, if therule utilizes not only the node identifiers but also network
proximities, the routing algorithm can select routes in which
the weights of the edges are low.
There are three policies to consider network proximity instructured overlays [7]: proximity neighbor selection (PNS)[8]–[11], proximity route selection (PRS) [12], [13], andproximity identifier selection (PIS) [9], [11]. In PNS, eachnode selects its neighbors based on network proximity. In
PRS, the selection of an edge for a route from a source todestination node is dependent on network proximity. In PIS,
a node identifier is determined based on network proximity.
These methods are, in general, independent of one another;that is, a structured overlay based on one method can also
consider network proximity by another method [9], [11].
Various proximity-aware routing algorithms have been proposed for structured overlays [8]–[13]. However, they are
so ad-hoc extensions that each of them depends on specificrouting algorithms. An extension targets only one or a few
algorithms. In LPRS-Chord [8], which is one of proximityaware routing algorithms, LPRS is nearly independent froma base algorithm (e.g., Chord [1]), but it needs modification to be applied to Pastry [4] and Tapestry [6]. Thus we
propose Proximity-aware Flexible Routing Tables (PFRT), a
methodology to design proximity-aware routing algorithms,
that introduces network proximity into Flexible Routing Tables(FRT) [14]. It does PNS.
FRT is a methodology to design a routing algorithm for

Proc. 18th IEEE Symposium on Computers and Communications (IEEE ISCC'13), July 2013

a structured overlay. An FRT-based algorithm such as FRTChord [14], FRT-2-Chord [15] and one based on Kademlia[2] inherits the identifier spaces of its ancestor (e.g., Chord[1]) and defines a total order ≤ID on the set of all routing
table patterns based on node identifiers. And it works along
the procedure defined by FRT.
To define a PFRT-based algorithm, algorithm designers define two total orders on the the set of all routing table patterns:
an identifier-based order ≤ID , and a proximity-based order≤PR . PFRT then maintains routing tables according to theseorders. Therefore, PFRT facilitates designers to systematicallydesign proximity-aware routing algorithms.
Because PFRT is a simple extension of FRT, it keeps benefits of FRT such as supporting various identifier spaces, compatibility with other extensions. Existing routing algorithms
and extensions can be redesigned based on FRT and work in
consistent with PFRT. The extension for network proximity by
PFRT is independent from properties of the existing algorithms
such as an identifier space because the two total orders are
orthogonal. For example, a PFRT-based algorithm adopting
Kademlia’s identifier space can incorporate with an extensionthat takes account of node’s lifetime. Another benefit of FRT
that PFRT inherits is broadened application domains.
To this end, we have designed the PFRT-based algorithm,
PFRT-Chord, as an extension of Chord. Since PFRT-basedalgorithms can consider several metrics for network proximity, we select communication latency to measure network
proximity in this work. Our simulation results show that the
average routing latency in PFRT-Chord is less than that in not
only Chord but also LPRS-Chord, another proximity-awarerouting algorithm. In addition, our results show that PFRTChord inherits the beneficial features of FRT.
II. RELATED WORK
A. Chord
Chord [1] is one of the most well-known DHT algorithms.
DHT manages an associative array by using a large numberof computers. A datum consisting of a key and value pairis stored in a computer selected by a routing algorithm. The
computer is then called the responsible node of the datum.
When putting or getting data, a request message is sent to the
responsible node of each datum via the other nodes.
Data placement in Chord is managed by consistent hashing(Fig. 1) [16], which assigns an m-bit identifier to a node byhashing the node’s IP address and to a datum by hashing thedatum’s key. The identifier space is like a ring. The identifier
distance d(x, y) from identifiers x and y is the clockwise
distance in the ring:{y − x,
x < y,d(x, y) =(1)my − x + 2 , y ≤ x.
The first node that an identifier reaches while progressing ina clockwise direction is called the successor node, and the
responsible node of a datum is the successor node of thedatum’s identifier.

node’s responsible
identifier space

node

datum

datum’s
responsible node
identifier space

Fig. 1.

Consistent hashing.

To build a structured overlay using Chord, each nodemanages the set of its neighbor nodes in the overlay network.
This set is called a routing table. Each entry in a routing tableholds a node’s identifier and its IP address, but an entry is
1 thesometimes expressed as the node which is pointed to byentry in this paper.
Routing tables in Chord consist of three parts: a successor
list, predecessor, and finger table. The successor list of a nodecontains a certain number u closest nodes from the node in
the identifier space. The successor list is used for reachingdestination nodes. The predecessor contains the farthest nodefrom 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 node n contains the successor node of
the identifier n.id+2i . Thus, if N is the number of nodes, then
the number of entries in a finger table is about log N . Chord
strictly manages these three tables based on node identifiers,
and so route lengths are O(log N )-hops.
When putting or getting a datum, a request message arrives
at the destination node by greedy routing, which selects a forwarding node from the routing table as follows. The message
is repeatedly forwarded from each node to the closest neighborto the datum’s identifier in the node’s routing table. Once themessage arrives at the predecessor p of the destination node,
the message is forwarded to the destination node by using p’s
successor list.
Routing algorithms that use iterative or recursive routing
can be implemented. In iterative routing, a source node sends
a message to all forwarding nodes. In recursive routing, aforwarding node sends a message to the next forwarding node.
Although iterative routing detects failure in a forwarding node,recursive routing requires only about half of the routing latencyof iterative routing because there is no need to wait for a reply
message.
Nodes often join and leave P2P networks, and so eachnode must meticulously maintain its routing table through astabilization protocol. A stabilization protocol consists of fourfunctions: join, stabilize, notify, and fix fingers. When a nodeis added in Chord, it executes a join function to search for its
successors. All nodes periodically execute stabilize functions
to search for their current successors. When a node finds a
new successor, the node executes a notify function to instructProc. 18th IEEE Symposium on Computers and Communications (IEEE ISCC'13), July 2013

the successor to update its predecessor. All nodes periodically
execute a fix fingers function to search for the current rth entry
in its finger table (where r is a random number).

target nodei th entrynei

C. FRT-Chord
FRT [14] is a method of designing routing algorithms forstructured overlays. FRT-based algorithms inherit the identifier
spaces and distances utilized by existing routing algorithms, aswell as gaining the advantageous features of FRT, compatibility with other extensions and broadened application domains.
FRT-Chord [14] is an FRT-based algorithm based on Chord,and thus consistent hashing and greedy routing are employed.
However, a node n in FRT-Chord maintains only a single
routing table E containing entries ei (i = 1, 2, . . . |E|),
which are sorted in ascending order according to the identifier
distances from n (i < j ⇒ d(n, ei ) < d(n, ej )). Thus,{ei }i=1,2,...u is the successor list of n, where e1 is n’s
successor and u is the capacity of successor list, and e|E| is
its predecessor. Since routing tables in FRT-based algorithms
are maintained by using a total order ≤ID on the set of all
routing table patterns, designers need to define ≤ID .

ei+1d( ei , ei + 1)

identifierspaced( n , e i + 1)

B. Proximity-aware Routing Algorithms
Various proximity-aware routing algorithms, such as LPRSChord [8], AChord [9], Quasi-Chord [10], have been proposed
for structured overlays. However, they are so ad-hoc extensions
that each of them depends on specific routing algorithms. An
extension targets only one or a few algorithms. In LPRSChord, LPRS [8] is nearly independent from a base algorithm(e.g., Chord), but it needs modification to be applied to Pastry[4] and Tapestry [6]. Besides, it is difficult to introduce anotherextension considering other view points such as node lifetime
into them. In contrast to them, PFRT is orthogonal to basealgorithms and other extensions.
LPRS-Chord is a proximity-aware routing algorithm basedon PNS, and is an extension of Chord. Therefore, data placement in LPRS-Chord is managed by consistent hashing, and it
employs a greedy routing policy. The main difference between
LPRS-Chord and Chord is the method of building routing
tables. Routing tables in LPRS-Chord are maintained basedon network proximity.
LPRS-Chord utilizes the same successor list and predecessor as used by Chord. However, the ith entry in the finger tableof a node n is the node in [n + 2i , n + 2i+1 ) such that thecommunication latency between the node and n is minimal.
Therefore, the number of entries in a routing table in LPRSChord equals that in Chord.
To search for the ith entry, n randomly selects a few identifiers in [n + 2i , n + 2i+1 ) and measures the communication
latencies between itself and the successors of these identifiers.
Because the nodes in Chord periodically execute the fix fingers
function, whereas the nodes in LPRS-Chord measure communication latencies for only a few nodes, searching for the ith
entry in LPRS-Chord requires slightly heavier traffic than thatin Chord.

(i+1) th entry

worst-cased(ei, ei + 1)
reduction ratio r i ( E ) = d(n, ei + 1)

Fig. 2.

Worst-case reduction ratio1) Total Order on Routing Table Set: Routing tables are
updated according to ≤ID , which is a total order on the set
E of all routing table patterns. E ≤ID F then expresses thatrouting table E is better than F based on the node identifiers.
≤ID in FRT-Chord is defined as follows.
A node n calculates the worst-case reduction ratio1 ri (E)(Fig. 2) of a forwarding to a node ei , other than its predecessor.
A reduction ratio is the fraction that the remaining identifier
distance is reduced by when n forwards a message to eachentry 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 ≤ID F ⇐⇒ {r(i) (E)} ≤dic {r(i) (F )},(3)

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

(6)

Finally, the best routing table Ẽ satisfies the following
equation:Ẽ ≤ID E,∀E ∈ E.
(7)2) Guarantee of Reachability: These operations guarantee
reachability in FRT. The Guarantee of Reachability functionin FRT-Chord is the same as the stabilize function 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.
• When node n communicates with node a, n obtains a’s
information.
• Each node periodically executes an active learning
lookups function to obtain information on other nodes.
Active learning lookups in FRT-Chord actively acquires
node information, and is similar to the fix fingers functionin Chord. When a node n executes an active learning lookups
function, a lookup is performed for identifier k calculated by()rndd(n, e|E| )k = n.id + d(n, e1 ),(8)d(n, e1 )Proc. 18th IEEE Symposium on Computers and Communications (IEEE ISCC'13), July 2013

where rnd is a random number between 0 and 1. n 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 of a routing
table L, entries should be removed from E. Entry filteringis the function that removes an entry in FRT. The function
determines the entry for removal er according to ≤ID as
follows:
E \ {er } ≤ID E \ {e},∀e ∈ E.

(9)

By calculating a canonical spacing SiE for each entry ei inE, er can be found efficiently:d(n, ei+1 )SiE = log.
d(n, ei )(10)E
If SiE′ −1 + SiE′ is the minimum value of Si−1
+ SiE for ei ,er = ei′ . In FRT, any entry that must not be removed from therouting tables is called a sticky entry. Sticky entries in FRTChord consist of the successor list and predecessor entries thatare required in order to reach a destination node.
The step in Entry filtering is 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.

III. PFRT-C HORD
PFRT is a method of designing proximity-aware routing
algorithms for structured overlays. Because PFRT is a simple
extension of FRT, PFRT-based algorithms also have many of
the advantageous features of FRT, compatibility with otherextensions, broadened application domains and so on.
PFRT-Chord is a PFRT-based algorithm designed by extending Chord, and therefore consistent hashing and greedy routing
are employed. We designed PFRT-Chord since Chord is oneof the most well-known algorithms for structured overlays.
The main difference among PFRT-Chord, FRT-Chord, andChord is the method of building routing tables. Routing
tables in FRT-Chord are maintained based on only node
identifiers, whereas routing tables in PFRT-Chord are also
maintained based on not only node identifiers but also network
proximity. PFRT-Chord updates routing tables using various
information, and so an entry e in a routing table of n isgiven an identifier e.id, an address e.address, and a metrice.proximity that measures the network proximity from n to e.
e.proximity < f.proximity then expresses that e has a better
network proximity than the entry f . Although a PFRT-basedalgorithm could consider any metric for network proximity,
we select communication latency in this paper.

A. Two Total Orders on Routing Table Set
PFRT-Chord defines both the identifier-based order ≤ID andthe proximity-based order ≤PR , where ≤ID is the same asin FRT-Chord, in order to update routing tables based on
identifier and network proximity.
E ≤PR F indicates that routing table E is better than F
based on network proximity. If f is an entry in the routing
table F , then we define ≤PR as follows:
E ≤PR F1 ∑1 ∑e.proximity ≤f.proximity. (11)
⇔
|E|
|F |
f ∈F

e∈E

Sticky entry is the set of entries which are necessary forreachability, stabilize, churn tolerance, and so on. Therefore,
PFRT-Chord compares routing tables except sticky entries inorder to find better routing table based on network proximity.
B. Guarantee of Reachability
The Guarantee of Reachability function in PFRT-Chord is
the same as that in FRT-Chord.
C. Entry Learning
Similar to FRT-Chord, this function obtains a node’s information and inserts it into a routing table. However, because
an entry e in the routing table of node n has the metrice.proximity in PFRT, n should also measure e.proximity.
When n obtains e’s information except for e.proximity, nsets e.proximity to its maximum value by default.
Since communication latency is used as the metric for
network proximity, a node n must measure the latency l(n, e)
between n and an entry e. PFRT-Chord uses the round trip
time (RTT) as the measure of communication latency, and n
can measure or obtain the RTT l(n, e) under the following
circumstances.
• n measures l(n, e) in sending a round-trip message.
• When e knows RTT l(e, n) and sends a message to n,l(e, n) is sent with the message.
In order to detect failures, messages in general routing
algorithms are round-trip messages. Thus, PFRT-Chord canmeasure RTTs between nodes without causing heavy traffic.
The last appending entry ea is recorded in order to use in
Entry filtering.
D. Entry Filtering
If the number of entries |E| in the routing table E is greaterthan the capacity of routing table L, entries should be removed
from E. The Entry filtering function in PFRT removes an entry
according to ≤ID and ≤PR .
Let Enext be the next routing table, which is the routing
table after deleting the entry for removal er and let Eprev be
the previous routing table, which is the routing table before
adding ea :Eprev = E \ {ea },Enext = E \ {er }.

Proc. 18th IEEE Symposium on Computers and Communications (IEEE ISCC'13), July 2013

(12)
(13)

Entry filtering provides filters, a proximity filter and an
identifier filter, based on these orders that narrow down thecandidate set for Enext , and nodes in PFRT-Chord can selectEnext which is better than Eprev when ea does not belong to
the sticky entry, which is the set of entries which are necessary
for reachability, stabilize, churn tolerance, and so on.
er can be any entry. Let CE be the set of candidates for
Enext . Then,
CE = {E \ {e}|e ∈ E}.
(14)

Eprev

previous routing tableea...

add appending entry|E| > LE

remove each entry...

candidate set CE
proximity
filterproximity-aware
candidate set CPRE...

identifierfilter

Because (12), ea ∈ E and (14) hold,Eprev ∈ CE .

(15)

The proximity filter is the first filter in Entry filtering and isbased on ≤PR . Any routing table that is better, based on ≤PR ,than Eprev passes through the proximity filter. Therefore, CEPR
is narrowed down to the proximity-aware candidate set CE
throughPR
CE= {E|E ≤PR Eprev , E ∈ CE }.
(16)
Because (15) and (16) holds,
PR
Eprev ∈ CE

(17)

PR
holds. Because CE
is a candidate set for Enext ,PR
Enext ∈ CE

(18)

holds. Because (17) and (18) hold, Enext is better than Eprev
in terms of network proximity or Enext and Eprev are thesame:
Enext ≤PR Eprev .
(19)
The identifier filter is the second filter in Entry filtering andis based on ≤ID . By utilizing the identifier filter, Enext isPRselected as the best routing table from CE
through
Enext ≤ID E,PR∀E ∈ CE.

(20): routing table: entry

Fig. 3.

(21)

By defining ≤ID and ≤PR , algorithm designers can systematically design PFRT-based algorithms where routing tables are
updated to Enext ((19) and (21) hold) (Fig. 3).
The step in Entry filtering is as follows.Let C be a candidate
set for er , let et be a threshold entry of the network proximity
metric, and let u be the capacity of a successor list.
1) Add all entries in E to C.
2) Remove sticky entries from C.
3) Remove {e ∈ C|e.proximity < ea .proximity} from C.
4) When SiE′ −1 + SiE′ is found for ei ∈ C, er equals ei′ andis removed from E.
Steps 1, 2, and 4 are the same as those in FRT-Chord. Thus,
by adding only step 3, FRT-Chord is extended to PFRT-Chord.
The proximity filter is passed in step 3, and the identifier filter
is passed in step 4.

Enext

decide entry
for removal

next routing table

Entry filtering in PFRT-ChordE
By sorting {Si−1+ SiE } into ascending order, er can be1
found in O(L) steps. In contrast, finding er in FRT-Chord
requires O(1) steps. However, the computations to determine
er are performed by each computer. Therefore, the timerequired to find er is sufficiently less than that to forwarda message.
Because PFRT-based algorithms are based on PNS, a node’s
routing table contains only those entries with a high value ofthe network proximity metric. Therefore, the node directly
forwards messages to the nodes listed in its routing table,
and so recursive routing is more suitable for PFRT-basedalgorithms than iterative routing.
Nodes often join and leave P2P networks so routing algorithms should have churn tolerance. Therefore, PFRT-Chord
has as much churn tolerance as Chord because routing tables
in PFRT-Chord necessarily contain the successor list andpredecessor like Chord.

Because (17) and (20) hold, Enext is better than Eprev in termsof its node identifier:
Enext ≤ID Eprev .

er

IV. E VALUATIONIn this section, we evaluate PFRT-Chord through a simulation. We implemented PFRT-Chord on Overlay Weaver [17],[18], which is an overlay construction toolkit, and performedexperiments 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)
• Memory: 32 GB• Java virtual machine: Java SE 6 Update 22••

Communication latencies between any two nodes were
calculated by using a topology which simulates a physicalnetwork by using a transit-stub (TS) model [19]. TS models
have two types of nodes: transit and stub. In our simulation,
the communication latencies of the inter-transit node links,
stub-transit node links, and inter-stub node links were set at100, 20, and 5 ms, respectively. The maximum communication
latency is 870 ms and the average is 420 ms. The simulated
communication latency is much higher than communication

Proc. 18th IEEE Symposium on Computers and Communications (IEEE ISCC'13), July 2013

latency over real Internet, but we can evaluate simulation
results by not value but rate correctly.
A. Comparison between PFRT-Chord and Existing Routing
Algorithms
We measured the routing latency—the time required per
request—in Chord, LPRS-Chord, FRT-Chord, and PFRTChord. Parameters values in the simulations were set as
follows.
• Number of nodes: 10 000• Capacity of a successor list: 4• Capacity of a routing table in PFRT-Chord: 16• Number of requests per node: 300• Routing type: recursive
Because the number of nodes is 10 000, the number of
entries in a finger table in Chord and LPRS-Chord is about
13; that is, the number of entries in all three parts of the routing
tables in Chord and LPRS-Chord is about 18. Therefore, thecapacity of a routing table in PFRT-Chord is set at 16 so that
PFRT-Chord does not have an advantage in the number of
entries that can be held.
Fig. 4(a) shows the averages and 99th percentiles of therouting latencies in Chord, LPRS-Chord, FRT-Chord, and
PFRT-Chord. The average routing latency is 2 081 ms in PFRTChord and 2 756 ms in Chord. The average routing latency in
PFRT-Chord is thus about 24.5% less than that in Chord. In
addition, the 99th percentile of the routing latency in PFRTChord is about 22.1% less than that in Chord. Consequently,
PFRT-Chord is verified as an appropriate proximity-awarerouting algorithm.
The average routing latency in FRT-Chord is 2 587 ms; thatis, the average routing latency in PFRT-Chord is about 19.6%
less than that in FRT-Chord. Furthermore, the 99th percentileof the routing latency in PFRT-Chord is about 15.0% less thanthat in FRT-Chord. Therefore, extending FRT to PFRT in order
to consider network proximity improves its performance.
The average routing latency in LPRS-Chord is 2 676
ms; that is, the average routing latency in PFRT-Chord isabout 22.2% less than that in LPRS-Chord. Additionally,
the 99th percentile of the routing latency in LPRS-Chord isapproximately equal to that in Chord. PFRT-Chord is thus abetter proximity-aware routing algorithm than LPRS-Chord.
Furthermore, the capacity of routing tables in PFRT-Chord
can be set to an arbitrary value, and so routing latencies canbe decreased further.
Although FRT-Chord does not consider network proximity,
the average and 99th percentiles of the routing latency in FRTChord are only about 3.3% and 8.7% less than those in LPRSChord, respectively. This indicates that route lengths in LPRSChord are longer than those in FRT-Chord. Thus, we measured
the route lengths in the four algorithms.
The measurements results are given in Fig. 4(b), whichshows the averages and 99th percentiles of the route lengths.
The average route length in LPRS-Chord is longer than in
PFRT-Chord, which may explain why the routing latencies
are greater in LPRS-Chord than in PFRT-Chord. To test thishypothesis, we also calculated the average routing latency
per hop for each algorithm (Fig. 4(c)). The average routing
latency per hop in PFRT-Chord is about 16.0% less than that in
LPRS-Chord. Hence, PFRT-Chord is superior to LPRS-Chord
at utilizing network proximities.
B. Independence of the Number of Nodes
We finally examined whether PFRT-Chord retains the beneficial features of FRT; specifically, broadened application
domains. Since broadening of application domains indicatesthat the routing algorithm is independent of the number ofnodes, and flexibility means that the capacity of each routing
table can be changed, we measured the average route lengthand the average routing latency in PFRT-Chord under thefollowing parameter values.
• Number of nodes: 100, 1000, and 10 000.
• Capacity of each routing table: 20–160.
Figs. 5(a) and 5(b) show the simulation results for the
average route length and the average routing latency. As thecapacity of the routing tables increases, the average route
length and average routing latency both decrease. Therefore,
PFRT-Chord is flexible.
As the number of nodes increases, the average route lengthand average routing latency increase. Although the number ofnodes increases by 10- and 100-fold, the average route length
increases by only about 1.66- and 2.34-fold, respectively, andthe average routing latency increases by only about 1.59and 1.94-fold, respectively. In addition, when the number ofnodes N is less than the capacity of each routing table L, forexample, N = 100 and L = 160, the average route lengthis 2 (incidentally, the average route length in LPRS-Chord is3.28). Hence, each routing table contains the information on
all of the nodes in the network, and a source node forwards a
message to the predecessor of the destination node in the first
hop. PFRT-Chord thus broadens application domains.
V. C ONCLUSION
We proposed Proximity-aware Flexible Routing Tables(PFRT), a methodology to design proximity-aware routing
algorithms for structured overlays. A PFRT-based algorithm
defines two total orders on the set of all routing table patterns: an identifier-based order ≤ID and a proximity-basedorder ≤PR . Therefore, PFRT facilitates algorithm designers
to systematically design proximity-aware routing algorithms.
To this end, we designed a PFRT-based algorithm, PFRTChord, which employs the same data placement method androuting policy as in Chord. The main difference between
PFRT-Chord and Chord is the method of building routing
tables. To build routing tables in PFRT-Chord, we must define≤ID and ≤PR , and so routing tables in PFRT-Chord aremaintained according to not only node identifiers but also
network proximities in the physical network.
We implemented and simulated PFRT-Chord in a set ofexperiments. Routing latencies in PFRT-Chord are less thanthose in not only Chord but also LPRS-Chord, which is anexisting proximity-aware routing algorithm. This performance

Proc. 18th IEEE Symposium on Computers and Communications (IEEE ISCC'13), July 2013

12

averageRouting latency per hop (ms)average

99th percentile

99th percentile

Route length

Routing latency (ms)

6000

4000

2000

0

8

4

0
Chord

LPRS-Chord FRT-Chord PFRT-Chord
Routing algorithm

Chord(a) routing latencies

400
300
200

100
0

(b) route lengths
Fig. 4.

6

LPRS-Chord FRT-Chord PFRT-Chord
Routing algorithm

Routing results in each algorithm
2500

N = 10 000
N = 1 000
N = 100

4Chord(c) routing latency per hop

Routing latency (ms)Route length

LPRS-Chord FRT-Chord PFRT-Chord
Routing algorithm

500

2

N = 10 000
N = 1 000
N = 100

2000
1500
1000

500
0

0
0

40

80
120
Routing table capacity

160(a) route lengths
Fig. 5.

0

40

80
120
Routing table capacity

160(b) routing latencies

Correlation between routing table capacity and routing results

improvement can be achieved even if the number of entries
in PFRT-Chord routing tables is less than that in LPRSChord. Therefore, our experiments showed that PFRT-Chord isverified as an appropriate proximity-aware routing algorithm
for structured overlays.
In addition, we examined whether PFRT-Chord retains thebeneficial features of FRT. Our simulations showed that PFRTChord is independent of the number of nodes and that therouting table capacity can be changed dynamically.
Future work includes design of extensions of FRT considering other real-world metrics such as node lifetime. FRT
can incorporate with those metrics in the same manner as for
PFRT. Combinations of PFRT and other extensions should be
examined. GFRT [14], an extension of FRT takes account ofgroups of nodes and reduces communication between nodes.
It should work with PFRT.
R EFERENCES[1] I. Stoica, R. Morris, D. Karger, F. Kaashoek, and H. Balakrishnan,“Chord: A scalable peer-to-peer lookup protocol for internet applications,” IEEE/ACM Trans. Networking,, 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 Peer-to-Peer Systems (Proc.
IPTPS ’ 02), MA, USA, 2002, pp. 53–65.
[3] 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.
[4] 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.
[5] M. Kaashoek and D. Karger, “Koorde: A simple degree-optimal distributed hash table,” Berkeley, USA, 2003, pp. 98–107.
[6] B. Zhao, L. Huang, J. Stribling, S. Rhea, A. Joseph, and J. Kubiatowicz,“Tapestry: A resilient global-scale overlay for service deployment,”
Selected Areas in Comm., IEEE Journal on, vol. 22, no. 1, pp. 41–53,
2004.

[7] K. Gummadi, R. Gummadi, S. Gribble, S. Ratnasamy, S. Shenker, and
I. Stoica, “The impact of DHT routing geometry on resilience andproximity,” in Proc. ACM SIGCOMM ’03, Karlsruhe, Germany, 2003,
pp. 381–394.
[8] H. Zhang, A. Goel, and R. Govindan, “Incrementally improving lookup
latency in distributed hash table systems,” in Proc. ACM SIGMETRICS’03, CA, USA, 2003, 114–125.
[9] L. H. Dao and J. Kim, “AChord: Topology-aware Chord in anycastenabled networks,” in Proc. ICHIT ’06, Cheju Island, Korea, 2006, pp.
334–341.
[10] S. Mingsong and Z. Zhongqiu, “Quasi-Chord: Physical topology aware
structured P2P network,” in Proc. 11th Joint Conf. Information Sciences,Shenzhen, China, 2008.
[11] N. B. Dang, S. T. VU, and H. S. Nguyen, “Building a low-latency,
proximity-aware DHT-based P2P network,” in Proc. KSE ’09, Hanoi,
Vietnam, 2009, pp. 195–200.
[12] F. Dabek, M. F. Kaashoek, D. Karger, R. Morris, and I. Stoica, “Widearea cooperative storage with CFS,” ACM SIGOPS Oper. Syst. Rev.,
vol. 35, no. 5, pp. 202–215, 2001.
[13] J. Song, S. Park, and J. Yang, “An adaptive proximity route selection
scheme in DHT-based peer to peer systems,” in Parallel and Distributed
Computing: Applications and Technologies (Proc. PDCAT ’04), Singapore, 2005, pp. 143–157.
[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, Kyoto, Japan, 2011, pp. 72–81.
[15] Y. Ando, H. Nagao, T. Miyao, and K. Shudo, “FRT-2-Chord: A DHT
Supporting Seamless Transition between One-hop and Multi-hop with
Symmetric Routing Tables,” in Proc. SACSIS 2012, Kobe, Japan, 2012,
pp. 210–218.
[16] 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
Ann. ACM Symp. Theory Computing, Texas, USA, 1997, pp. 654–663.
[17] K. Shudo, “Overlay Weaver: An overlay construction toolkit,” Available:
http://overlayweaver.sourceforge.net/, 2006.
[18] K. Shudo, Y. Tanaka, and S. Sekiguchi, “Overlay Weaver: An overlay
construction toolkit,” Comput. Comm., vol. 31, no. 2, pp. 402–412, 2008.
[19] E. W. Zegura, K. L. Calvert, and S. Bhattacharjee, “How to model aninternetwork,” in Proc. IEEE INFOCOM ’96, San Francisco, USA, 1996,
pp. 592–602.

Proc. 18th IEEE Symposium on Computers and Communications (IEEE ISCC'13), July 2013