Detouring Skip Graph:
A Structured Overlay Utilizing Detour Routes
Takeshi Kaneko∗¶ , Ryohei Banno∗ , Kazuyuki Shudo∗ , Yusuke Aoki∗ , Kota Abe†‡ and Yuuichi Teranishi‡§∗ Tokyo Institute of Technology, Tokyo, Japan† Osaka City University, Osaka, Japan‡ National Institute of Information and Communications Technology, Tokyo, Japan§ Osaka University, Osaka, Japan

Email: ¶ kaneko.t.ay@m.titech.ac.jp

Abstract—Skip Graph, one of the structured overlays, provides
a scalable network owing to the routing path lengths of O(log n),
where n denotes the total number of nodes. However, there isa problem that most of the routing paths are quite longer than
the shortest paths because each node in the network knows only
its neighbors, rather than the global topology. In general, longrouting paths lead to long delay times and low fault tolerance.
Herein, we propose Detouring Skip Graph, which shortens thepath lengths through the use of detour routes. It does not
require construction of extra links or modification of its topology;
thereby, it can succeed in shortening them while maintaining
the advantages of Skip Graph. The evaluation experiments showthat the average path length was shortened by approximately
20%–30% in comparison with Skip Graph.
Index Terms—Skip Graph, structured overlay, routing algorithm, detour route

I. I NTRODUCTION
Overlay networks are application-level logical networks
built on existing networks such as the Internet. Speciallystructured overlays construct autonomous distributed networks
according to specific data structures or protocols; thereby
providing reachability to target nodes, high scalability, efficientroutings, and high fault tolerance. Owing to the properties, application to large-scale distributed systems such as distributed
key/value stores [1], video streaming [2], and online games [3]has been proposed. In recent years, application to the fields of
IoT and Blockchain is also expected [4], [5].
Skip Graph [6], one of the structured overlays, is a distributed data structure that provides the capability of range
queries as a result of preserving the order of keys by managing
data without hashing. Over the years, numerous extensions
and improvements of Skip Graph have been proposed, even inrecent studies [7], [8].
However, it is still a challenge that each node cannot takefull advantage of existing links because it knows only its
neighbors, rather than the global topology. Thus, the routing
paths tend to be quite longer than the shortest paths. In
general, overlay networks whose routing paths are long leadto long delay times and low fault tolerance. Since mostapplication mentioned above of overlay networks requires the
responsiveness and the reliability, shortening routing paths isa critical demand for overlays including Skip Graph.

Fig. 1: An example of Skip Graph.

Herein, we propose an extension of Skip Graph which iscalled Detouring Skip Graph. It shortens the path lengths
through the more efficient use of existing links while maintaining the advantages of Skip Graph. Specifically, its routing
algorithm is different from that of Skip Graph in two ways:
each node 1) utilizes detour routes and 2) traverses adjacentnodes from its maximum level.
The rest of this paper is organized as follows. Section II
presents an overview of Skip Graph and the related work on
shortening path lengths. Section III presents Detouring Skip
Graph in detail. Section IV presents the evaluation experiments
for the proposed method and the results. Finally, Section V
presents the conclusion of this study.
II. R ELATED W ORK
A. Skip Graph
Skip Graph is a distributed data structure designed basedon Skip List [9], and each node belongs to multiple sorted
doubly linked lists. Figure 1 shows an example of a topologyof Skip Graph. Each node has a key in a totally ordered set
and a random string called membership vector (MV), whichplays a key role in constructing the topology of Skip Graph.
In the figure, the set of alphabets that are elements of MV isProc. 17th IEEE Consumer Communications & Networking Conference(IEEE CCNC 2020), January 2020

Fig. 3: Should node vcurrent select the detour route?

Fig. 2: A searchOp routing from node A to key 15.
{0, 1}. In a linked list at level l, the leading l digits of the MV
of every node is the same as that of all others. Particularly atlevel 0, all nodes belong to one linked list. Therefore, eachnode belongs to O(log n) linked lists. Further, by using thesame method as Skip List, Skip Graph achieves a routing path
length of O(log n) for a query to search a key ktarget . A detailed
explanation of the routing algorithm is presented below, where
it is assumed that the keys in the linked lists are sorted inascending order from left to right.
Herein, suppose node vcurrent in Skip Graph is receiving aquery searchOp to search a node that has a specific key.
The query has three information (vstart , ktarget , lprev ): a startnode vstart , a target key ktarget , and the level lprev at which
the previous node sends the query. If vcurrent .key, which means
the key of vcurrent , equals to ktarget , vcurrent sends a queryfoundOp to vstart since it means that vcurrent is the target
node. If vcurrent .key < ktarget , vcurrent traverses the right adjacentnodes at the levels from lprev in descending order and sends asearch query searchOp to the first adjacent node vnext where
vnext .key ≤ ktarget . If vcurrent .key > ktarget , vcurrent traverses theleft adjacent nodes and sends a search query searchOp to
the next node in a similar manner.
Figure 2 shows a routing process for a query to target
key ktarget = 15 issued at node A on the condition that eachnode follows the above method in the topology shown in
Figure 1. Then, the key sequence of the nodes on the path
is (0, 4, 9, 13, 15), and the path length is 4.
B. Shortening Path Lengths
The path length is 4 in Figure 2, however, there are shorter
paths in reality. For instance, if node A chooses node G atlevel 2 instead of node C at level 1 as the next node, the key
sequence of the nodes on the path would be (0, 18, 15), andthe path length would be 2 (which is shorter than 4). Thus,
the routing of Skip Graph is inefficient in that it cannot fully
utilize the existing links. Therefore, various approaches havebeen proposed for shortening the path lengths.
In the above example, at the route from node A to node G,
the magnitude relationship between the key of the node andthe target key ktarget is reversed. Routes like this are hereinafterreferred to as “detour routes.” The proposed method (describedlater in detail) utilizes detour routes. It is similar to the method
proposed by Higuchi et al. [10] in terms of use of detour
routes. However, the subject of their method is not ordinary
Skip Graph but Skip Graph whose topology is balanced bymeans of using linear hashing preserving the order.
There are already several methods to shorten path lengths ofSkip Graph routings: e.g., methods that involve constructionof extra links in the Skip Graph and appropriate routings on
the topology [11], [12], and methods that reconstruct or refine
the unbalanced topology resulting from randomly generated
MVs into the ideal topology [7], [8], [13], [14]. However,the construction of extra links and the modification of the
topology lead to an increase in necessary transfer messages
and maintenance cost.
III. P ROPOSED M ETHOD
The main idea of Detouring Skip Graph is the utilizationof detour routes. Moreover, the idea can be combined withthe technique traversing from maximum levels. This section
presents these ideas and the details of Detouring Skip Graph
whose routing algorithm combines them.
In the following, let K be a set of keys. To simplify, we
assume that K is a subset of rational numbers1 and multiple
nodes do not have the same key. Thus, arithmetic operations
and absolute values are well-defined on K.
A. Utilizing Detour Routes
The routing algorithm of Detouring Skip Graph utilizes
detour routes. The idea is based on the following argument.
Figure 3 shows a part of the topology of Figure 1. Let vnext
and vlower be the right neighbors of node vcurrent at level 1 and0, respectively. Now, suppose vcurrent is receiving a query totarget key ktarget where 9 ≤ ktarget < 18. In a situation where
it follows the routing algorithm of Skip Graph, it selects vlower
as the next node. If ktarget = 15, the key sequence of the nodes
on the path would be (4, 9, 13, 15), and the path length would
be 3. However, in a situation where it selects vnext as the next
node, i.e., it uses the detour route, the key sequence would be(4, 18, 15), and the path length would be 2. The path length ofthe latter is shorter than that of the former. The effectivenessof such detour routes is dependent on the position of the target
key; if ktarget = 13, the path length of using the detour route
would be longer than that of using the ordinary route.
1 As a mathematical fact, any countable totally ordered set can be orderembedded into the set of rational numbers [15].

Proc. 17th IEEE Consumer Communications & Networking Conference(IEEE CCNC 2020), January 2020

As shown in Figure 3, it can be determined from the centerof the node sequence at the lower level (level 0 in Figure 3)
whether vcurrent should select vnext or vlower to shorten the path
length. This section presents the routing algorithm that eachnode determines the next node based on a detour criterion ateach level.
Algorithm 1: searchDROp in node vcurrent/* utilizing Detour Routes*/
upon receiving hsearchDROp, vstart , ktarget , lprev i then2
if vcurrent .key = ktarget then3
send hfoundOp, vcurrent i to vstart ;4
return;5else if vcurrent .key < ktarget then6
for lcurrent ← lprev downTo 0 do
7
vnext ← vcurrent .neighbors[R][lcurrent ];8
if vnext .key ≤ ktarget then9
send hsearchDROp, vstart , ktarget , lcurrent i tovnext ;
10
return;11
else if lcurrent > 0 then12vlower ← vcurrent .neighbors[R][lcurrent − 1];13
if closeToRight(ktarget , vlower .key, vnext .key) then14
send hsearchDROp, vstart , ktarget , lcurrent i tovnext ;
15
return;
1

16
17
18
19
20
21
22
23
24
25
26

27

else
for lcurrent ← lprev downTo 0 do
vnext ← vcurrent .neighbors[L][lcurrent ];if vnext .key ≥ ktarget thensend hsearchDROp, vstart , ktarget , lcurrent i tovnext ;
return;else if lcurrent > 0 thenvlower ← vcurrent .neighbors[L][lcurrent − 1];
if ¬ closeToRight(ktarget , vnext .key, vlower .key) thensend hsearchDROp, vstart , ktarget , lcurrent i tovnext ;
return;Fig. 4: A searchDROp routing from node A to key 15 where2
mid(k1 , k2 ) = k1 +k
2 .
equal for the set V of all participating nodes at any point intime and any k1 , k2 ∈ K (k1 ≤ k2 ).
1) # k ∈ K | k1 ≤ k ≤ mid(k1 , k2 ) ∧∃ v ∈ V, v.key = k2) # k ∈ K | mid(k1 , k2 ) ≤ k ≤ k2 ∧∃ v ∈ V, v.key = k
We give some examples of defining mid. Let v.key, the keyof a node v, be regarded as a random variable. If
K = {0, 1, . . . , n − 1} and P {v.key = k} =thenmid(k1 , k2 ) :=function closeToRight(ktarget , kleft , kright )29kmid ← mid(kleft , kright );30
return kmid < ktarget ;Algorithm 1 is a pseudocode of this algorithm. Herein,vcurrent traverses adjacent nodes in the same way as Skip Graphwhen node vcurrent receives a query searchDROp. However,if vcurrent judges that using a detour route is better than notusing it, vcurrent selects the end node of the detour route as
the next node. Function closeToRight(ktarget , kleft , kright ) can beused to make this judgment. Let Iright be {k ∈ K | k ≥ kright }.
The function returns true if the signed distance from ktarget to
Iright is smaller than that from mid(kleft , kright ) to Iright , i.e.,kright − ktarget < kright − mid(kleft , kright ); otherwise, it returns
false. Intuitively, it means that ktarget is closer to kright thanmid(kleft , kright ). Further, mid is a design parameter that can be
defined as a function before the construction of the topology
where it satisfies that the following 1) and 2) are approximately

k1 + k2.
2If k+1
1
K = {0, 1, . . .} and P {v.key = k} =
,
2
then

send hnotFoundOp, vcurrent i to vstart ;

28

1
,
n

mid(k1 , k2 ) := − log2

2


1 k1
+
2


1 k2
2

3

!
.

By defining mid in this way, mid(vlower .key, vnext .key) ormid(vnext .key, vprev .key) refers to key estimation of the centerof the lower-level node sequence. Thus, closeToRight plays
the appropriate role of a detour judgment.
In practice, it is difficult to obtain the distribution of thekeys beforehand. However, from the evaluation experiment
presented in Section IV, we observed that it is effective inmany cases for shortening path lengths by defining mid as:
mid(k1 , k2 ) :=k1 + k2.
2

Figure 4 shows the routing process for a query to target key
ktarget = 15 issued at node A on the condition that each nodefollows Algorithm 1 in the topology shown in Figure 1. The
key sequence of the nodes on the path is (0, 18, 15), and thepath length is 2, which is shorter than that of Figure 2.

Proc. 17th IEEE Consumer Communications & Networking Conference(IEEE CCNC 2020), January 2020

B. Traversing from the Maximum Level
In addition to utilizing detour routes, we can improve theroutings of Skip Graph by making each node to traverse fromthe maximum level.
As discussed in Section II-A, in the routings of Skip Graph,node vcurrent traverses the adjacent nodes at the levels fromreception level lprev in descending order and determines thefirst adjacent node vnext that satisfies the condition as thenext node. The levels are monotonically decreasing for theentire routing. However, there are cases where adjacent nodes
at levels larger than lprev satisfy the condition. Moreover,the larger the sending level, the larger the difference in key
between adjacent nodes. Therefore, the difference between the
key of the next node and the target key ktarget is not larger whentraversing from level vcurrent .maxLevel than when traversing
from level lprev , where v.maxLevel is the maximum level ofnode v. Thus, it is effective in shortening the path lengths thateach node traverses from its maximum level.
Algorithm 2: searchMLOp in node vcurrent/* traversing from Max Level
upon receiving hsearchMLOp, vstart , ktarget i then2
if vcurrent .key = ktarget then3
send hfoundOp, vcurrent i to vstart ;4
return;5else if vcurrent .key < ktarget then6
for lcurrent ← vcurrent .maxLevel downTo 0 do
7
vnext ← vcurrent .neighbors[R][lcurrent ];8
if vnext .key ≤ ktarget then9
send hsearchMLOp, vstart , ktarget i to vnext ;10
return;

*/

1

16

else
for lcurrent ← vcurrent .maxLevel downTo 0 do
vnext ← vcurrent .neighbors[L][lcurrent ];if vnext .key ≥ ktarget thensend hsearchMLOp, vstart , ktarget i to vnext ;return;17

send hnotFoundOp, vcurrent i to vstart

11
12
13
14
15

Algorithm 2 is a pseudocode of this algorithm. Whennode vcurrent receives a query searchMLOp, vcurrent traverses
adjacent nodes from vcurrent .maxLevel and sends a querysearchMLOp to the first node that satisfies the condition.
This routing differs from that of Skip Graph only in the startlevel of traversing. Note that it is possible to use binary search
for finding a next node instead of linear search, which is faster,
but this code uses the latter for simplicity.
Figure 5 shows a routing process for a query to target key
ktarget = 15 issued at node A on the condition that each nodefollows Algorithm 2 in the topology shown in Figure 1. The
key sequence of the nodes on the path is (0, 4, 9, 15), and thepath length is 3, which is shorter than that of Figure 2.
It should be noted that Algorithm 2 has the disadvantage ofincreasing the computation costs incurred between receiving
a query and determining the next node, although it has theadvantage of shortening the path lengths. Let lMAX be theFig. 5: A searchMLOp routing from node A to key 15.

maximum value of the maximum levels of all nodes, whichis O(log n), and let H be the path length, which is O(log n).
Then, the sum of the time required for each node on a routing
path to determine the next node until finishing a rounting
process, except for the communication time and the I/Oprocessing time, is O(lMAX + H) = O(log n) for Skip Graph.
On the other hand, in the case of the following Algorithm 2,
it is O(H · lMAX ) = O(log2 n). Especially when using binary
search, it is O(H log lMAX ) = O(log n · log(log n)). These areinferior to Skip Graph in terms of computational complexity.
However, the time taken for a routing is typically dominatedby the communication time, hence it is more important toshorten path lengths in most cases.
C. Detouring Skip Graph: Combining Two Improvements
Because the two improved routing algorithms describedabove are independent changes from the routing algorithmof Skip Graph, an algorithm combining them can be defined
naturally. We refer an extension of Skip Graph that performs
such routing as Detouring Skip Graph.
When node vcurrent receives a query searchDSGOp, vcurrent
traverses adjacent nodes from vcurrent .maxLevel in the same
way as described in Section III-B and sends a querysearchDSGOp to the first node that satisfies the condition.
In the process, searchDSGOp uses detour routes based on
the detour judgment as described in Section III-A.
From the foregoing, Detouring Skip Graph can bring about
the shortening of path lengths for search queries. Unlike
the existing methods discussed in Section II-B, it does not
require construction of extra links or modification of its
topology. Therefore, there is no increase in message transfer
and management costs. Additionally, it is an extension thatmaintains the good properties of Skip Graph.
D. Reachability of Detouring Skip Graph
Detouring Skip Graph is characterized in that the key
sequences of the nodes on a routing path are not monotonic inorder, which is a property that does not apply to Skip Graph.
You might consider that the routing process may lead to an
infinite loop. However, the reachability is guaranteed, which

Proc. 17th IEEE Consumer Communications & Networking Conference(IEEE CCNC 2020), January 2020

is proved in this section. It should be assumed that Detouring
Skip Graph does not separate as a network.
Suppose a search query whose target key is k is being
issued. Then, each variable can be defined as follows.
• Let (a1 , a2 , . . .) be the key sequence of the nodes on therouting path.
• Sk := {x ∈ K | x < k}.
• Tk := {x ∈ K | x > k}.
• Let (as1 , as2 , . . .) be the subsequence of (ai )i , whose
elements are all ai satisfying ai ∈ Sk .
• Let (at1 , at2 , . . .) be the subsequence of (ai )i , whose
elements are all ai satisfying ai ∈ Tk .
• Let binary relation k , ≺k on Sk × Tk be:– k := {(x, y) ∈ Sk × Tk | closeToRight(k, x, y)}– ≺k := {(x, y) ∈ Sk × Tk | ¬closeToRight(k, x, y)}.
Intuitively, x k y implies that y is closer to k than x,
and x ≺k y implies that x is closer to k than y.
The query reaches the target node if and only if (ai )i is a
finite sequence. Thus, it is sufficient to show that (ai )i is finite.
If both (asj )j and (atj )j are strictly approaching k (i.e., they
are strictly increasing and strictly decreasing, respectively),(ai )i converges to the key of the target node in finite steps
and (ai )i is a finite sequence.
Next, to show the strict monotonicity of each subsequence,
the function mid used as the detour judgment must exhibit thefollowing property.
Property 1: ∀ x ∈ Sk ,∀ y ∈ Tk ,(∀ 0
x ∈ Sk , [x0 ≤ x ⇒ x0 ≺k y]• x ≺k y ⇒∀ 0y ∈ Tk , [y 0 ≤ y ⇒ x ≺k y 0 ](∀ 0x ∈ Sk , [x0 ≥ x ⇒ x0 k y]
• x k y ⇒∀ 0y ∈ Tk , [y 0 ≥ y ⇒ x k y 0 ]Property 1 is satisfied whenever mid is defined as the median estimation based on any probability distribution, e.g.,
mid(x, y) := x+y
2 . Then, the following lemma holds.
Lemma 1: ∀ x1 , x2 ∈ Sk ,∀ y1 , y2 ∈ Tk ,∃•x ∈ Sk s.t. (x ≺k y1 ∧ x k y2 ) ⇒ y1 < y2∃•y ∈ Tk s.t. (x1 k y ∧ x2 ≺k y) ⇒ x1 > x2
Proof: Suppose there exists x ∈ Sk such that x ≺k y1
and x k y2 . If y1 ≥ y2 , then x k y1 because of x k y2 andProperty 1, however it contradicts x ≺k y1 . Therefore, we havethat y1 < y2 . The latter proposition can also be established in
the same way.
Lemma 1 derives the following theorem.
Theorem 1: (asj )j and (atj )j are strictly increasing andstrictly decreasing, respectively.
Proof: It is sufficient for each step i to show that:(j > 1 ⇒ asj > asj−1 ( if ∃ j s.t. sj = i)(∗)
j > 1 ⇒ atj < atj−1 ( if ∃ j s.t. tj = i),where step i represents the process on the i-th node in therouting path. This can be shown using mathematical induction.
Suppose (∗) holds at step 1, 2, . . . , i.

TABLE I: Routing algorithms used as the evaluation subjects.
searchOp: Skip Graph(Sec. II-A)

searchDROp: Utilizing detour routes(Sec. III-A)

searchMLOp: Traversing from max level(Sec. III-B)

searchDSGOp: Detouring Skip Graph(Sec. III-C)

1) If ai = k, then step i + 1 does not exist because therouting process is complete.
2) If ai ∈ Sk , then the four cases are considered:(i) ai+1 ∈ Sk , (ii) ai+1 ∈ Tk , (iii) ai+1 = k, and(iv) ai+1 does not exist. In case (i) and (iii), (∗) holds
at step i + 1 because ai < ai+1 and ai+1 ∈/ Sk ∪ Tk ,respectively. In case (iv), step i+1 does not exist because
the routing process is complete. In case (ii), because a
detour route is used, there exist j and x ∈ Sk such thattj = i + 1, x > ai , and x ≺k atj . From Property 1, we
have atj−1 +1 k atj−1 . If j > 1, then it implies that a
detour route was used at step tj−1 and that no detour
route was used at step tj−1 + 1, tj−1 + 2, . . . , i − 1owing to the definition of subsequence (atj0 )j 0 .
Thus, atj−1 +1 , atj−1 +2 , . . . , ai ∈ Sk , and there existsy ∈ Tk such that y < atj−1 and atj−1 +1 k y. From
Property 1, we have atj−1 +1 k atj−1 . In addition,
atj−1 +1 < atj−1 +2 < · · · < ai holds by the induction
hypothesis. From Property 1, we have ai k atj−1 .
Thus, atj < atj−1 holds because of Lemma 1, i.e., (∗)
holds at step i + 1.
3) If ai ∈ Tk , then (∗) holds at step i + 1, which can beshown in the same way as 2).
Therefore, the reachability to the target node is guaranteed
for any search query.
IV. E VALUATION
We evaluated the path length by conducting a simulation
experiment and observed the effect of the proposed method.
We experimented with the following three key generation
methods:• Generated by uniform distribution.
• Generated by power-law distribution.
• Random English titles on Wikipedia.
A. Generated by Uniform Distribution
We used pseudorandom numbers to generate keys so thatthe keys of participating nodes follows a uniform distribution
P {v.key = k} = 2130 (k ∈ {0, 1, . . . , 230 − 1}) where v.key is
the key of a node v regarded as a random variable. Then, thecenter estimation mid for this distribution is
k1 + k2
miduniform (k1 , k2 ) :=.
2
On the topology constructed based on the keys generated
by the above method, every node issued 100 search queries
whose target keys ktarget ∈ {0, 1, . . . , 230 − 1} are generated
by uniform distribution. We plotted the average of all path

Proc. 17th IEEE Consumer Communications & Networking Conference(IEEE CCNC 2020), January 2020

Fig. 6: Average path lengths on a topology whose keys weregenerated by uniform distribution.
lengths of the routings for these queries in Figure 6. The
horizontal axis represents the number of participating nodes
in increments of 100, and the vertical axis represents theaverage path length. Each line corresponds to each routing method, where searchDSGOp(mid:uniform) andsearchDROp(mid:uniform) represent routings that involve the use of miduniform as a center estimation for the keys.
Table I is a correspondence table between names of routing
algorithms and the section numbers with their descriptions.
Further, every routing method is executed on the same topology for each number of nodes; and each topology is built byadding nodes to the existing topology, rather than rebuilt fromscratch each time. These conditions are the same for the otherexperiments discussed in the subsequent sections.
As a result, the average path lengths are shorterin the order of searchDSGOp(mid:uniform),
searchDROp(mid:uniform),
searchMLOp,
andsearchOp. Furthermore, Detouring Skip Graph executing
searchDSGOp(mid:uniform) shortens the average path
lengths by about 32% compared to Skip Graph executing
searchOp.
B. Generated by Power-Law Distribution
We converted pseudorandom numbers to generate keys sothat the keys of participating
nodes follow power-law distribuZkf (k)dk (0 ≤ k ≤ 230 ) where v.key

tion P {v.key ≤ k} =0

is the key of a node v regarded as a random variable, f denotes
a probability density function f (k) = ck 10 (0 ≤ k ≤ 230 ), andZ 230
c denotes a constant that satisfies
f (k)dk = 1. Then, the0center estimation mid for this distribution is 1
 10+1
k1+ k210+1 10+1
midpower (k1 , k2 ) :=.
2
The purpose of using power-law distribution is to evaluate theeffect of the proposed method on biased key distribution.
On the topology constructed based on the keys generated by the above method, every node issued 100

Fig. 7: Average path lengths on a topology whose keys weregenerated by power-law distribution.
TABLE II: Average path lengths on a topology whose
keys were generated by power-law distribution wheren = 100, 1000, 10000.
searchOp
searchDROp (mid:uniform)
searchDROp (mid:power)
searchMLOp
searchDSGOp(mid:uniform)
searchDSGOp(mid:power)

n = 100

1000

10000

4.75
4.46
4.44
4.59
4.35
4.34

9.31
8.38
8.37
7.87
7.14
7.15

11.41
9.76
9.70
10.31
9.05
9.03

search queries whose target keys ktarget ∈ {0, 1, . . . , 230 − 1}
were generated by uniform distribution. We plotted theaverage of all path lengths of the routings for these
queries in Figure 7. searchDSGOp(mid:power) andsearchDROp(mid:power) represent routings that involvethe use of midpower as a center estimation of keys.
As a result, the average path lengths were almost
the same in searchDSGOp(mid:uniform) andsearchDSGOp(mid:power), and we discovered thatusing miduniform as a detour criterion is effective even if the key
distribution is biased. Table II lists the average path lengths
where the number of nodes n is 100, 1000, and 10000. The
numerical values also indicate that the average path lengthsof the routings following searchDSGOp(mid:uniform)and searchDSGOp(mid:power) are almost the same. In
both routings, the average path length of searchOp was
shortened by about 20%.
C. Random English Titles on Wikipedia
We used random English titles obtained on Nov. 8, 2018from API2 published by Wikipedia as keys. Specifically, each
title was considered as a single-byte character string, and weused the string as a 256(= 28 )-based integer key. The purposeof using random titles is to evaluate the effect of the proposed
method in realistic situations.
2 https://www.mediawiki.org/wiki/API:Main page (accessed Jan. 24, 2019)

Proc. 17th IEEE Consumer Communications & Networking Conference(IEEE CCNC 2020), January 2020

R EFERENCES

Fig. 8: Average path lengths on a topology whose keys are
random English titles on Wikipedia.

On the topology constructed based on the keys obtained by
the above method, every node issued search queries whosetarget keys are the keys of all nodes. We plotted the averageof all path lengths of the routings for these queries in Figure 8.
As a result, Detouring Skip Graph executing
searchDSGOp(mid:uniform) shortens the averagepath lengths by about 24% compared to Skip Graph executing
searchOp. Although the detour criterion miduniform is not a
center estimation for this key distribution, it was found to beeffective in shortening the path lengths.
V. C ONCLUSION
In this paper, we proposed Detouring Skip Graph, which
shortens the path lengths by using effectively the topologythat Skip Graph constructs. It introduces two techniques in therouting algorithm of Skip Graph: each node 1) utilizes detour
routes and 2) traverses adjacent nodes from its maximum level.
In addition, we proved the reachability to the target node forany search query.
Detouring Skip Graph does not require construction of
extra links and modification of its topology; thereby, it isan extension that maintains the advantages of Skip Graph.
Through the evaluation experiments conducted, we confirmedthat the average path length was shortened by approximately
20% to 30% compared with the value obtained using Skip
Graph. Further, it was experimentally found that miduniform ,the average of the keys belonging to two nodes, is effective asa detour criterion even for biased or realistic key distribution.
In the future, we plan to address analytical evaluationof shortening path lengths and application of the proposed
algorithm to other extensions of Skip Graph.

[1] G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman,
A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels, “Dynamo:
Amazon’s Highly Available Key-value Store,” in Proceedings of TwentyFirst ACM SIGOPS Symposium on Operating Systems Principles, ser.
SOSP ’07. New York, NY, USA: ACM, 2007, pp. 205–220.
[2] N. Ramzan, H. Park, and E. Izquierdo, “Video streaming over P2P
networks: Challenges and opportunities,” Signal Processing: Image
Communication, vol. 27, no. 5, pp. 401–411, May 2012.
[3] A. Yahyavi and B. Kemme, “Peer-to-peer Architectures for Massively
Multiplayer Online Games: A Survey,” ACM Comput. Surv., vol. 46,
no. 1, pp. 9:1–9:51, Jul. 2013.
[4] A. Dorri, S. S. Kanhere, and R. Jurdak, “Towards an Optimized
BlockChain for IoT,” in Proceedings of the Second IEEE/ACM International Conference on Internet-of-Things Design and Implementation,
ser. IoTDI ’17. New York, NY, USA: ACM, 2017, pp. 173–178.
[5] Y. Hassanzadeh-Nazarabadi, A. Küpçü, and Ö. Özkasap, “LightChain:
A DHT-based Blockchain for Resource Constrained Environments,”
arXiv:1904.00375 [cs], Mar. 2019.
[6] J. Aspnes and G. Shah, “Skip graphs,” ACM Transactions on Algorithms,
vol. 3, no. 4, pp. 37:1–37:25, Nov. 2007.
[7] S. Huq and S. Ghosh, “Locally Self-Adjusting Skip Graphs,” in 2017
IEEE 37th International Conference on Distributed Computing Systems(ICDCS), Jun. 2017, pp. 805–815.
[8] A. Goyal, S. Batra, N. Kumar, G. S. Aujla, and M. S. Obaidat,“Adaptive Skip Graph Framework for Peer-to-Peer Networks: Search
Time Complexity Analysis,” in 2018 IEEE Global Communications
Conference (GLOBECOM), Dec. 2018, pp. 1–6.
[9] W. Pugh, “Skip lists: A Probabilistic Alternative to Balanced Trees,”
Communications of the ACM, vol. 33, no. 6, pp. 668–676, Jun. 1990.
[10] K. Higuchi, M. Yoshida, T. Tsuji, and N. Miyamoto, “Correctness of
the routing algorithm for distributed key-value store based on orderpreserving linear hashing and skip graph,” in 2017 18th IEEE/ACIS International Conference on Software Engineering, Artificial Intelligence,
Networking and Parallel/Distributed Computing (SNPD), Jun. 2017, pp.
459–464.
[11] M. Naor and U. Wieder, “Know Thy Neighbor’s Neighbor: Better
Routing for Skip-Graphs and Small Worlds,” in Peer-to-Peer Systems
III. Springer, Berlin, Heidelberg, Feb. 2004, pp. 269–277.
[12] A. G. Beltran, P. Sage, and P. Milligan, “Skip Tree Graph: A Distributedand Balanced Search Tree for Peer-to-Peer Networks,” in 2007 IEEE
International Conference on Communications, Jun. 2007, pp. 1881–
1886.
[13] F. Makikawa, T. Tsuchiya, and T. Kikuno, “Balance and ProximityAware Skip Graph Construction,” in 2010 First International Conference
on Networking and Computing, Nov. 2010, pp. 268–271.
[14] T. Kawaguchi, R. Banno, M. Hojo, M. Ohnishi, and K. Shudo, “SelfRefining Skip Graph: Skip Graph Approaching to an Ideal Topology,”
in 2017 14th IEEE Annual Consumer Communications Networking
Conference (CCNC), Jan. 2017, pp. 441–448.
[15] P. Keef and D. Guichard, “Introduction to Higher Mathematics,”
https://www.whitman.edu/mathematics/higher math online/.

ACKNOWLEDGMENT
This work was supported by JSPS KAKENHI Grant Numbers 19K20253, New Energy and Industrial Technology Development Organization (NEDO), and SECOM Science andTechnology Foundation.

Proc. 17th IEEE Consumer Communications & Networking Conference(IEEE CCNC 2020), January 2020