Message Bundling on Structured Overlays
Kazuyuki Shudo
Tokyo Institute of Technology
Tokyo, Japan

Abstract—A structured overlay running as the base of a
DHT or ALM occasionally receives a large number of messages collectively. Those cases are opportunities for an overlay
to bundle multiple different messages into a single message
and achieve extraordinarily effective message deliveries. Suchmessage bundling reduces the number of packet transmissions
on an underlay network such as an IP network. This paper
presents Collective Forwarding, a message bundling technique
for structured overlays. The technique not only reduces thenumber of packet transmissions but also improves throughput
of message forwarding. In experiments, the number of packet
transmissions and the time to get items were reduced to 12%
and 9.7% respectively at best. Theoretical analysis matches andthen supports the experimental results.
Keywords-peer-to-peer, structured overlays, DHT, message
bundling

I. I NTRODUCTION
A structured overlay is an application-level network, bywhich autonomous nodes perform ID-based message delivery
without central servers. On top of it, higher-level services suchas distributed hash tables (DHTs), application-layer multicast(ALM) are built and work [1]. Those services are steadybases of highly scalable and resilient distributed systems. For
example, their application to DNS [2] has been throughly
studied and content delivery systems with DHTs [3], [4] havebeen deployed.
A message delivery on a structured overlay with N nodes
generally requires O(logN ) times message forwarding. Eachforwarding is a packet delivery on an underlay network such as
an IP network. A message delivery on an overlay is heavier
and takes more time than a packet delivery on an underlay
because it consists of multiple packet deliveries.
A structured overlay supporting a DHT or ALM occasionally receives a large number of messages collectively. A DHT
generates a large number of messages at a time when it is filled
up for its initial use, backed up and restored. For example,
DNS [2], RFID databases [5], [6], [7] and other IoT cases store
millions or more data items. Those cases are opportunities
for an overlay to achieve extraordinarily effective message
deliveries by bundling multiple different messages into a single
message.
This paper presents Collective Forwarding, a message
bundling technique for structured overlays. It alleviate an underlay network such as an IP network and improve efficiencyof message delivery on structured overlays. Assume that anode delivers multiple different messages to their responsible
nodes. If delivery routes of those messages overlap each other,
the number of message forwarding is reduced by bundlingsuch messages into a single message. Such bundling improves
network throughput and mitigates the load of nodes on an
overlay that forwards messages. It also reduces the number ofpacket transmissions and alleviates routers on an underlay.
It is possible to promote such route overlaps not only just
expecting unintentional overlaps to happen. We can increase
overlapping opportunities by grouping messages into sets ofmessages that possibly share their routes (Section IV-A).
This paper is an extended version of our previous work[8]. The extension includes theoretical analysis (Section III),new experimental results and detailed analysis of the results(Section IV-B).
The rest of this paper is organized as follows. Section II
describes the proposed technique, Collective Forwarding. Section III shows theoretical analysis of effect of the technique. In
Section IV, we evaluate the technique by experiments. Section
V shows related work and we conclude in Section VI.
II. C OLLECTIVE F ORWARDING
In this section, we describe Collective Forwarding, a message bundling technique for structured overlays.
A structured overlay delivers a message to responsible nodes
that are responsible for the target ID of the message. Each nodeon the delivery route determines a next hop by referring to its
routing table. And the node forwards the message to the next
hop by requesting its underlay network such as an IP network
to do it. With the iterative style of forwarding (Figure 1c) [9],a node on a route does not directly forward a message to thenext hop and instead the originating node 0 communicates withall nodes. In this paper, we also call such redirections fromnode 1 to node 2, and from node 2 to node 3 in Figure 1c
forwarding.
Assume that a node has multiple messages to be delivered.
Each message has its own target ID. A node can forward themessages at a time if the next hops of those messages are
the same node. With the proposed technique, a node groups
such messages into a single combined message and forwards
it to the common next hop. Such bundling reduces the number of message forwarding. The bundling improves network
throughput by combining multiple fine-grained messages intoa coarse bundle. It mitigates the load of nodes on an overlaythat forwards messages by reducing the number of forwarding.
As for an underlay network, the technique reduces the numberof packet transmissions and alleviates routers. We call the
proposed technique Collective Forwarding.
Figure 2 summarizes forwarding processes with the proposed technique. The left figure is a case without the proposed

Proc. 22nd IEEE Symposium on Computers and Communications(IEEE ISCC 2017), pp.424-431, July 2017

Route

2

(2)

1

(3)

Route
(2)

3

1

(5)

(1)

0

a. Recursive style (short)
Route

1

(3)

3

(4)

(6)

(4)

(1)

2

b. Recursive style (long)2(2)Figure 3 shows how a bundle is divided on each hop ofrouting. Node A, the originating node puts all target IDs intoa single bundle. Node A then determines next hops for all thetarget IDs, sees that it is node B for all the five target IDs,and forwards the bundle to node B without dividing it. NodeB determines that the next hops are node C, D and E, divides
the given bundle into 3 sub-bundles, and forwards the threesub-bundles to each next hop.

3

(4)

(6)

(5)

(3)
(1)

0

0

c. Iterative style
Fig. 1.

Forwarding styles.

Forward 15 times

Forward 9 times

3 hops x 5 routes

with collective forwarding

3rd hopF

2nd hop

Node

G

H

C

D

1st hop

Route

Fig. 2.

I

J

E

B

0 hop

Node A

Reduction in the number of message forwarding.

3rd hop
2nd hop
1st hop
0 hop

ID1

ID2

ID3

ID4

ID1

ID2

ID3

ID4

ID1

ID2

ID3

ID4

ID5

ID2

ID3

ID4

ID5

Node F

G

Node C

ID1

H

D

ID5

I

Next hop is node B.

J

E

ID5

A bundle is partitioned on each hop
according to next hops of target IDs in it.

Fig. 3.

1) The originating node puts all target IDs into a bundle.
2) A node on the route determines next hops for all target
IDs in the bundle.
3) The node divides the bundle into sub-bundles. It meansthat the node puts the target IDs whose next hops are
the same into the same resulting sub-bundle.
4) The node forwards the resulting sub-bundles one by one.
5) Returns to 2.

Bundle partitioning according to next hops.

technique and messages are delivered one by one, and theright figure shows a case with the technique. The originating
node sends 5 messages and the length of the all routes is 3.
The usual and individual deliveries, shown in the left figure,requires 15 times of forwarding. The number of forwarding is
reduced to 9 by the proposed technique.
The procedure of the proposed technique is as follows. We
call the combined message or target IDs of each messages init “bundle”.

The proposed technique improves network throughput andlightens the load of nodes on an overlay that forwards messages. It is generally difficult to achieve high throughput with
fine-grained communications. For example, as long as using
TCP or UDP, throughput benchmarks do not show the peak
performance of the IP network with a small communication
unit such as 40 byte. The reasons include high interruption
rate on a computer and header overhead of TCP and UDP.
The proposed technique improves throughput by combining
messages.
In forwarding, a node on an overlay interprets a received
message and construct a message to be sent. The number oftimes those processes occur is proportional to the number offorwarding. The load of the processes is noticeable though
it depends on the protocol of an overlay and any discussion
on it requires more concrete numbers about it. The proposed
technique lightens the load of nodes by reducing the numberof forwarding, or at least keeps the same load as it without
the technique.
As for underlay network, the technique lightens the loadof routers by reducing the number packet transmissions. For
example, in a forwarding process on an IP network, a router
determines the output port by analyzing the header of an
IP packet. The bottleneck of the forwarding process is suchanalyzing process required for each IP packet. Because ofit, the forwarding performance of a router is represented bypackets per second (pps). The proposed technique lightens theload of routers by reducing the number of packets.
Note that traffic remains the same though the bundling technique reduces the number of packet transmissions. The routeand the traffic of every message on an underlay network do notchange because the messages are just combined. The total sizeof headers except target IDs decreases by the bundling, but its
impact is limited because target IDs and bodies are dominant
in size. But the proposed technique effectively reduces trafficof application-layer multicast (ALM). In ALM, the identicalmessage body is delivered to all receiving nodes. A bundle
has just a single message body for all the receiving nodes.

Proc. 22nd IEEE Symposium on Computers and Communications(IEEE ISCC 2017), pp.424-431, July 2017

k-ary tree(k = 2, binary tree)

Node«
A set of IDs(mostly a range in the ID space)

Fig. 4.

An analytic model of routes originated in a node.

A. Initial bundle grouping
A large bundle is prone to cause reliability problems on an
unreliable underlay. On an IP network, a packet larger thanmaximum transmission unit (MTU) is fragmented to multiple
pieces. In that case, loss of one of the pieces causes loss ofthe original large packet holding a large bundle.
The best size of a bundle depends on an underlay. We
choose 10 as the number of messages in a bundle for thefollowing analysis and experiments.
III. T HEORETICAL ANALYSISHow much does the technique reduce the number of packet
transmissions on an underlay? Figure 4 shows an analytic
model. It is a k-ary tree. With a k-ary tree, it is possible
to model message forwarding on structured overlays. For
example, a binary tree (k = 2) suits Chord [10] and otheralgorithms based on it such as Chord# [11] and FRT-Chord[12]. A 2b -ary tree suits algorithms based on Plaxton prefix
routing [13] with the base k = 2b including Pastry [14] andTapestry [15].
The root of a tree corresponds a node sending messages
and leaves of a tree correspond nodes that the messages aredelivered to. A message is forwarded along a path from theroot to a leaf.
To be precise, a vertex of the k-ary tree is a set of IDs. In
Figure 4, ID sets delivered from a node to the node itself are
drawn in the same node. It is the reason why a single node(yellow box) has multiple ID sets (green balls). The ID set
of a vertex with children is the union of ID sets of all thechildren. ID sets of all the children are disjoint. The union of
ID sets of all the leaves covers the entire ID space.
A node on an overlay corresponding to a leaf is responsible
for the set of IDs of the leaf. A node corresponding to avertex also corresponds one of the children of the vertex. In
Figure 4, a leftmost child is such a child. A step downward tosuch a child occurs in the node and does not cause message
forwarding.
Now we start counting the number of packet transmissions
on an underlay. It equals to the number of bundle forwarding
without packet fragmentation (Section II-A). We avoid packet
fragmentation by limiting the size of a bundle. For simplicity,
we assume a perfect k-ary tree, in which all leaf nodes are on

TABLE IR ATIOS OF THE NUMBER OF PACKET TRANSMISSIONS WITH C OLLECTIVEF ORWARDING TO ONE WITHOUT THE TECHNIQUE .

Theoretical ratios (in Figure 5):
Binary tree
Experimental ratios (in Figure 7):
Chord
Theoretical ratios:
16-ary tree
Experimental ratios:
PastryTapestry“random”“clustered”

0.766

0.102

0.78 ∼ 0.80

0.18

0.893

0.102

0.94 ∼ 0.95
0.92

0.32 ∼ 0.34
0.12

the same level. Probabilities of message deliveries to all theleaves are equal.
Figure 5 shows ratios of the number of packet transmissions
with Collective Forwarding to one without the technique. In all
the figures in this paper, “serial” means message forwarding
without the technique, “random” and “clustered” means bundle
forwarding with the technique. “Random” indicates initialbundle grouping (Section II-A) at random and “clustered”
indicates grouping target IDs with the procedure described in
Section IV-A. The size of initial bundles is 10 as well as all
the experiments in Section IV.
We focus on 1000 nodes, that is the same as all theexperiments in Section IV. Table I shows a summary of thefollowing values. Theoretical ratios of a binary tree shown in
Figure 5 a are 0.766 in “random” and 0.102 in “clustered”.
Experimental ratios of Chord, to which a binary tree conforms,
shown in Figure 7 are from 0.78 to 0.80 in “random” and 0.18
in “clustered”. The values of a 16-ary tree, Pastry and Tapestry
are also derived as above.
The theoretical values do not involve messages for overlay
maintenance but the experiments involve them. Such messages
weaken the reduction effect. It is the major reason for theworse values of the experimental ratios than theoretical ratios.
But the number of packet transmissions in “random” is larger
than “clustered” and it hides messages for overlay maintenance. Because of it, in “random”, theoretical ratios provided
better approximations of experimental ratios than “clustered”.
IV. E VALUATION
We evaluate the proposed technique, Collective Forwarding
by measuring number of packet transmissions and time todeliver messages.
We implemented he technique in Overlay Weaver [16], [17]and carried out the experiments with it. Overlay Weaver is
an implementation of structured overlays, which performs IDbased message delivery and provides DHT and ALM functions
on it. The proposed technique is always enabled and works
for every message delivery in Overlay Weaver because it is anatural extension of structured overlays (Section V).
We carried out all experiments with the distributed environment emulator Overlay Weaver provides by running andcontrolling multiple DHT shell instances on it. The emulator
hosts massive nodes on a single computer and controls those

Proc. 22nd IEEE Symposium on Computers and Communications(IEEE ISCC 2017), pp.424-431, July 2017



N 




UDQGRPFOXVWHUHG









Fig. 5.

  

1XPEHURIQRGHV
a. Binary tree

5DWLRWRVHULDO

5DWLRWRVHULDON 

UDQGRPFOXVWHUHG














1XPEHURIQRGHV
b. 16-ary tree



Ratio of the number of message transmissions with Collective Forwarding to the case without the technique.

nodes along the given emulation scenario. The code runningon the emulator also works on a real network. Because of it,
the implementation evaluated in this section run on PCs andInternet as it is.
We used a PC with a 2.8 GHz Intel x86 processor, Linux
2.6.25 for x86-64 and HotSpot Server VM of Java 2 SE
5.0 Update 15. The version of Overlay Weaver is 0.8.7. All
experiments were made 5 times and we adopted the averageof middle 3 values as the result.
A. Initial bundle grouping
The proposed technique takes much effect by grouping theinitial bundles as routes for target IDs in a bundle overlap eachother for the most part (Section II-A).
We gave priority to have good results of the initial groupingover efficiency of the grouping process itself because the purpose of the experiences is to investigate Collective Forwarding.
Along the policy, we adopted a simple grouping procedure as
follows though it takes much time.
1) Provides an empty bundle. Sets the ID last added to theprevious bundle as the mark ID. For the first bundle,
sets 0x00...0 as the mark ID.
2) Takes the ID closest to the mark ID from not-processed
IDs, and moves it to the bundle.
3) Takes the ID whose average distance to all IDs in thebundle is the smallest in not-processed IDs, and moves
it to the bundle
4) Repeats 3. unless the size of the bundle (the number ofIDs) reaches the given limit. Fixes the bundle if the size
reaches the limit.
5) Returns to 1.
This procedure is expected to produce a good grouping result
by choosing the ID which looks the best ID to be added tothe bundle.
Distance here is the numerical distance between IDs, whichis calculated in a way dependent on each routing algorithm.
For example, the distance from 3 to 4 is 1 in Chord, but 3 ⊕4 = 7 in XOR distance of Kademlia. It follows that effective
grouping of initial bundles depends on each routing algorithm
even though the proposed technique and its implementation inOverlay Weaver are neutral to routing algorithms.

Note that known clustering algorithms cannot be applied tothe initial bundle grouping because ID distance on a structured
overlay depends on a direction as shown in the previous
paragraph. Chord is a typical example and the distance from
3 to 4 is 1 but it is 2160 − 1 (in case of 160 bit ID) from 4 to3.
B. Number of packet transmissions
This section shows how many packet transmissions werereduced by the proposed technique. We provided an emulation
scenario which constructs an overlay with 1000 nodes, puts
50000 data items on the overlay and gets them, and run the
scenario with the distributed environment emulator. The sizeof a bundle is 10 and initial bundles were grouped by theprocedure shown in Section IV-A before the experiment.
The emulation scenario is as follows. It takes 1040 seconds
after nodes start joining the overlay.
1) Starts 1000 nodes.
2) Constructs an overlay by letting the nodes join theoverlay every 20 millisecond.
3) Sleeps for 10 seconds.
4) Puts 50000 data items, one every 10 millisecond.
5) Sleeps for 10 seconds.
6) Gets 50000 data items, one every 10 millisecond.
Nodes to which put and get were determined at random when
the scenario is generated. The scenario puts and gets a bundle
every 100 millisecond and it corresponds to putting/getting adata item every 10 millisecond.
Figure 6 shows the number of packet transmissions a second
between nodes on an underlay network. Figure 6 a, b, c, dand e are the results with routing algorithms, Chord [10],Koorde [18], Pastry [14], Tapestry [15] and Kademlia [19]respectively. The size of a digit b in Pastry and Tapestry is 4
bit and then k = 24 = 16. The forwarding style (Figure 1)
here is iterative but experiments with recursive style showedsimilar results.
Figure 7 is about the total number of message transmissions
required to put and get data items. The numbers do not include
messages to construct the overlay because it is not affected by
the proposed technique. The numbers in Figure 7 is ratios of
the number of transmissions with the technique to one without
the technique.

Proc. 22nd IEEE Symposium on Computers and Communications(IEEE ISCC 2017), pp.424-431, July 2017



&KRUG

1.2

VHULDOUDQGRPFOXVWHUHG



0.8



0.80 0.78

0.70 0.69

0.6



0.34 0.32



0.0

.RRUGH

0.2
forwarding
style




Chord

0.12 0.13

Koorde0.25
0.12 0.12

PastryTapestry

iterative

a. Chord

0.18 0.18

recursiverecursiverecursive
7LPH VHFRQGV

iterativerecursive

iterative

0.4

iterative

7UDQVPLVVLRQVVHFRQG

0.95 0.92 0.92
clustered 0.94

1.0



1.10

randomiterative

7UDQVPLVVLRQVVHFRQGKademlia




VHULDOUDQGRPFOXVWHUHG

Fig. 7.
Experimental ratio of the number of packet transmissions with
Collective Forwarding to the case without the technique.










7LPH VHFRQGV





b. Koorde
7UDQVPLVVLRQVVHFRQG



VHULDOUDQGRPFOXVWHUHG

3DVWU\













7LPH VHFRQGV





c. Pastry

7UDQVPLVVLRQVVHFRQG



7DSHVWU\

VHULDOUDQGRPFOXVWHUHG














7LPH VHFRQGV





d. Tapestry
7UDQVPLVVLRQVVHFRQG.DGHPOLD




VHULDOUDQGRPFOXVWHUHG











7LPH VHFRQGV





e. Kademlia
Fig. 6. Number of packet transmissions on an underlay to deliver messages
on an overlay.

In the figures, meanings of “serial”, “random” and “clustered” are the same as Section III.
The proposed technique with the initial bundle grouping(“clustered”) reduced the number of transmissions to 34% in
Pastry ∼ 12% in Koorde and Tapestry (Figure 7).
In Pastry, a large number of messages to maintain theoverlay weaken the reduction effect. Pastry, at least its implementation for Overlay Weaver involves more messages
to maintain an overlay than other algorithms. Because of
the maintenance messages, the number of transmissions justafter 500 second in Figure 6c decreased but more than 200transmissions / second remained.
The number of transmissions for get operations is smaller
than put operations, except “clustered” in Kademlia. It is due
to Overlay Weaver protocol. An originating node completes a
get operation by receiving a reply from a responsible node.
But in a put operation, an originating node sends another put
request to a responsible node after receiving the reply from it.
The protocol prevents a possibly large value being forwarded
along the route. This difference is conspicuous with Pastry
shown in Figure 6c because it becomes larger with shorterroutes and Pastry tends to result in shorter routes than otheralgorithms Overlay Weaver provides.
The number of transmission decreased with the techniqueeven though the initial bundle grouping is at random (“random”), except Kademlia. It includes the reduction by occasional overlaps of routes in a bundle.
In Kademlia, the number of transmissions increased in“random” from “serial” (Figure 7), and get operations required more number of transmissions than put operations(Figure 6e). It is due to the routing table maintenance protocolof Kademlia. With the protocol, a node knows another nodeby communicating with the another node and try to store theanother node in its routing table. Once part of its routing table,
a k-bucket, is filled, it sends and receives more messages tocheck aliveness of other nodes in its routing table. Becauseof it, much communication on a node yields more communication. The proposed technique concentrates communication
on limited part of nodes. A node initiating a message was

Proc. 22nd IEEE Symposium on Computers and Communications(IEEE ISCC 2017), pp.424-431, July 201735

Get latency (seconds)

30

30.2

196.9

25

Chord (iterative)
24.8

23.5

20

C. Time to deliver messages

14.8

15
10

6.1

5
0
serialserialConcurrency 1

randomclusteredrandomclustered

10

100

a. Chord (iterative)
Get latency (seconds)

20

104.5 18.9

18.9

15

Chord (recursive)
13.6 14.2

10

5.4
5
0
serialserialConcurrency 1

randomclusteredrandom10

clustered

100

b. Chord (recursive)
Get latency (seconds)

10

59.2

7.9

9.7

8

Pastry (iterative)
6.9
6.0

6
4

2.5

2
0
serialserialConcurrency1

randomclusteredrandom10

clustered

100c. Pastry (iterative)
Get latency (seconds)

10

41.6

8

7.6

8.0

Pastry (recursive)
6.5
5.0

6

2.9

4
2
0
serialserialConcurrency 1

random clustered random clustered
10

100

d. Pastry (recursive)80
Get latency (seconds)

70

686.5

60

77.5
58.5

Kademlia(iterative)

66.5

41.3

50

but such a node was chosen randomly 5000 times with thetechnique and a chosen node performed more communication.

40

This section shows how long time it took to get data items
from a DHT. The distributed environment emulator ran anemulation scenario which constructs a DHT with 1000 nodes
and get 10000 data items from the DHT. Emulated communication latency on the underlay network is 1 millisecond.
These parameters emulate a large-scale distributed databaseon a local-area network (LAN) for applications such as RFID
databases [5], [6], [7]. Communication latency of today’s
LAN media such as 10Gb Ethernet and InfiniBand is aroundmicroseconds but software stacks such as TCP/IP stacks and
DHT implementations cause larger latency by one or moreorders of magnitude. Because such software-originated latency
varies and heavily depends on software, we chose uniform
communication latency to investigate solely an impact of the
proposed technique. The unit, millisecond, has no meaning.
Figure 8 shows the time required to get 10000 data items.
As same as Figure 6 and Figure 7 (Section IV-B), meanings of“serial”, “random” and “clustered” are the same as Section III.
Concurrency in the graphs is the number of message delivery(i.e. get) requests which can be processed concurrently onan overlay. Concurrency 10 with “random” and “clustered”
means delivery of bundles one by one while a bundle includes
10 target IDs. In concurrency 10 with “serial”, a scenario
sequencer of the emulator connected to 10 nodes in the
DHT and requested up to 10 delivery requests concurrently.
Concurrency 100 means requesting up to 10 bundles to bedelivered through 10 connections while a bundle includes 10
target IDs. It is not obvious which of concurrency 10 andconcurrency 100 with the proposed technique (“random” and“clustered”) is appropriate to be compared with concurrency
10 without the technique (“serial”). The former is with thesame concurrency but the latter utilizes the same number ofconnections, 10.
The technique with the initial bundle grouping (“clustered”
with concurrency 10) reduced the time to 13.0% in Chordwith recursive style ∼ 9.7% in Kademlia from “serial” withconcurrency 1. These reduction rates are comparable withthose without the technique with concurrent requesting (“serial” with concurrency 10), which are 18.2% in Pastry withrecursive style ∼ 8.5% in Kademlia. The proposed techniquewith concurrent requesting (concurrency 100) could reduced
the time further to 7.03% in Pastry with recursive style ∼3.12% in Chord with iterative style.

22.4

30

V. R ELATED WORK

20
100serialConcurrency 1

serialrandomclusteredrandom10

clustered100

e. Kademlia (iterative)
Fig. 8.

Time to deliver 10000 messages.

chosen randomly 50000 times without the technique (“serial”),

MARIF [20], [21], a message bundling technique for DHTs,
was proposed just after our previous work [8]. Collective
Forwarding is an extension to structured overlays in contrast
with MARIF, that is a data distribution protocol dedicated to
DHTs. A message delivery and forwarding process of a single
message in Collective Forwarding is just the same as a plain
structured overlay while MARIF requires two phases as key

Proc. 22nd IEEE Symposium on Computers and Communications(IEEE ISCC 2017), pp.424-431, July 2017

range examination and data transfer. Because of it, Collective
Forwarding works with ALM protocols such as SCRIBE [22]and improves their performance though MARIF does not.
In MARIF, when a node tries to send a large number ofmessages, it examines the key range that another node is
responsible for by asking the another node. Then it sends multiple messages that the another node is responsible for to theanother node. In MARIF, a node can send unlimited numberof messages continuously as a data stream to their responsible
node while Collective Forwarding cannot. It contributes highly
efficient data distribution by MARIF.
Collective Forwarding can be recognized as a multicast
protocol (Section II) such as IP multicast and application-layer
multicast (ALM). Every protocol for IP multicast constructs
a delivery tree that consists of relaying and receiving routers
before actual packet delivery. And a packet is delivered to all
the routers along the tree. Unstructured overlay-based ALM
protocols deliver a message to the whole overlay. They areclassified to push-based and pull-based. Push-based protocols[23] construct a delivery tree. Pull-based protocols [24], [25]can broadcast to any form of an overlay even if it is not a tree.
Structured overlay-based ALM protocols [22], [26] constructa delivery tree for a group of receiving nodes based on a
structured overlay. Our protocol is different from the existing
multicast protocols as it delivers a message to nodes specified
by the sending node. Because of it, our protocol does not
require a delivery tree.
Bundling multiple packets into a single packet is a common
technique to improve communication performance. Bundlingtechniques have been studied, for example, for wireless sensor
networks [27], delay tolerant networks [28], and virtual machines [29]. They do in-network processing in a lower layers
and their concern is efficiency in a specific layer. Our target
is an overlay network, that works over its underlay networkand has an independent topology from the underlay. In caseof an overlay, efficiency heavily involves its underlay and our
proposal and experiments focus on it.
There are techniques to improve efficiency of delivery of asingle message while our target is delivery of multiple messages. Those techniques reduce latency of forwarding or/and
shorten the length of a forwarding path, a route. Proximity
routing [30], [31] is an example of the former attempts. The
latter includes attempts to keep the number of forwarding O(1)times [32] and keep it once [33], [34].
VI. S UMMARY
In this paper, we proposed Collective Forwarding, a message
bundling technique for structured overlays. A node forwards
multiple messages collectively as a bundle if those messages’
next hops are identical. It alleviates an underlay network andimprove throughput of message forwarding. The techniquereduces the number of forwarding on an overlay and consequently the number of transmission on an underlay.
We analyzed the technique theoretically, implemented it
in Overlay Weaver and conducted experiments with various
routing algorithms. The number of packet transmissions andthe time to deliver messages were reduced to 12% and 9.7%
respectively at best. With concurrent requesting, the time todeliver messages could be further reduced to 3.12% at best.
ACKNOWLEDGMENTS
This work was supported by JSPS KAKENHI Grant Numbers 25700008 and 16K12406. This work was also supported
by New Energy and Industrial Technology Development Organization (NEDO) especially in detailed comparison withexisting techniques.
R EFERENCES[1] F. Dabek, B. Zhao, P. Druschel, J. Kubiatowicz, and I. Stoica, “Towards
a common API for structured peer-to-peer overlays,” in Proc. IPTPS’03,
Feb. 2003.
[2] V. Pappas, D. Massey, A. Terzis, and L. Zhang, “A comparative studyof the DNS design with DHT-based alternatives,” in Proc. INFOCOM
2006, Apr. 2006.
[3] “BitTorrent,” http://www.bittorrent.com/.
[4] “Vuse (formerly known as Azureus),” http://www.vuse.com/.
[5] Y. Doi, S. Wakayama, M. Ishiyama, S. Ozaki, and A. Inoue, “Onscalability of DHT-DNS hybrid naming system,” in Proc. AINTEC 2006,
Nov. 2006, pp. 16–30.
[6] Y. Doi, S. Wakayama, and S. Ozaki, “A design for distributed backup
and migration of distributed hash tables,” in Proc. SAINT 2008, Jul.
2008, pp. 213–216.
[7] L. Schmidt, N. Mitton, D. Simplot-Ryl, R. Dagher, and R. Quilez,“DHT-based distributed ALE engine in RFID middleware,” in Proc.
IEEE RFID-TA 2011, Sep. 2011, pp. 319–326.
[8] K. Shudo, “Collective forwarding on structured overlays,” IPSJ Transactions on Advanced Computing Systems, vol. 2, no. 3, pp. 39–46, Sep.
2009 (in Japanese).
[9] S. Rhea, D. Geels, T. Roscoe, and J. Kubiatowicz, “Handling churn ina DHT,” in Proc. USENIX ’04, Jun. 2004.
[10] 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.
[11] T. Schütt, F. Schintke, and A. Reinefeld, “Range queries on structured
overlay networks,” Computer Communications, vol. 31, no. 2, pp. 280–
291, Feb. 2008.
[12] 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, Aug. 2011, pp. 72–81.
[13] C. G. Plaxton, R. Rajaraman, and A. W. Richa, “Accessing nearby copies
of replicated objects in a distributed environment,” Theory of Computing
Systems, vol. 32, no. 3, pp. 241–280, Jun. 1999.
[14] 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, Nov. 2001.
[15] B. Y. Zhao, L. Huang, J. Stribling, S. C. Rhea, A. D. Joseph, andJ. D. Kubiatowicz, “Tapestry: A resilient global-scale overlay for service
deployment,” Journal on selected area in communications, vol. 22, no. 1,
pp. 41–53, Jan. 2004.
[16] K. Shudo, Y. Tanaka, and S. Sekiguchi, “Overlay Weaver: An overlay construction toolkit,” Computer Communications (Special Issue onFoundations of Peer-to-Peer Computing), vol. 31, no. 2, pp. 402–412,
Feb. 2008.
[17] “Overlay Weaver: An overlay construction toolkit,” http://overlayweaver.
sf.net/.
[18] M. F. Kaashoek and D. R. Karger, “Koorde: A simple degree-optimal
distributed hash table,” in Proc. IPTPS’03, Feb. 2003.
[19] P. Maymounkov and D. Mazières, “Kademlia: A peer-to-peer information system based on the XOR metric,” in Proc. IPTPS’02, Mar. 2002.
[20] K. Mizutani, T. Mano, O. Akashi, and K. Fukuda, “Efficient query
bundling mechanism in a DHT network,” in Proc. IEEE GLOBECOM
2012, Dec. 2012, pp. 2695–2700.
[21] ——, “MARIF: Multiple queries look-up architecture using range
information feedback in a DHT network,” IEICE Transactions on
Communications, vol. E96-B, no. 7, pp. 1680–1690, Jul. 2013.

Proc. 22nd IEEE Symposium on Computers and Communications(IEEE ISCC 2017), pp.424-431, July 2017

[22] M. Castro, P. Druschel, A.-M. Kermarrec, and A. Rowston, “SCRIBE: Alarge-scale and decentralized application-level multicast infrastructure,”
IEEE Journal on Selected Areas in Communications (JSAC), vol. 20,
no. 8, pp. 1489–1499, 2002.
[23] Y. hua Chu, S. G. Rao, S. Seshan, and H. Zhang, “A case for end system
multicast,” IEEE Journal on Selected Areas in Communications (JSAC),
vol. 20, no. 8, pp. 1456–1471, 2002.
[24] X. Zhang, J. Liu, B. Li, and T.-S. P. Yum, “CoolStreaming/DONet: A
data-driven overlay network for efficient live media streaming,” in Proc.
INFOCOM 2005, Mar. 2005.
[25] V. Pai, K. Kumar, K. Tamilmani, V. Sambamurthy, and A. E. Mohr,“Chainsaw: Eliminating trees from overlay multicast,” in Proc. IPTPS
2005, Feb. 2005.
[26] M. Castro, P. Druschel, A.-M. Kermarrec, A. Nandi, A. Rowstron,and A. Singh, “SplitStream: High-bandwidth multicast in a cooperativeenvironment,” in Proc. SOSP’03, Oct. 2003.
[27] J. Heidemann, F. Silva, C. Intanagonwiwat, R. Govindan, D. Estrin, and
D. Ganesan, “Building efficient wireless sensor networks with low-level
naming,” in Proc. SOSP 2001, Oct. 2001, pp. 146–159.
[28] W.-B. Pöttner and L. Wolf, “Opportunistic data aggregation in delay
tolerant networks,” in Proc. IEEE ISCC 2015, Jul. 2015, pp. 840–845.
[29] M. Bourguiba, K. Haddadou, I. E. Korbi, and G. Pujolle, “Improving
network I/O virtualization for cloud computing,” IEEE Transactions on
Parallel and Distributed Systems, vol. 25, no. 3, pp. 673–681, Mar. 2014.
[30] K. Gummadi, R. Gummadi, S. Gribble, S. Ratnasamy, S. Shenker, and
I. Stoica, “The impact of DHT routing geometry on resilience andproximity,” in Proc. SIGCOMM 2003, Aug. 2003.
[31] T. Miyao, H. Nagao, and K. Shudo, “A method for designing proximityaware routing algorithms for structured overlays,” in Proc. IEEE
ISCC’13, 2013.
[32] I. Gupta, K. Birman, P. Linga, A. Demers, and R. van Rennesse, “Kelips:
Building an efficient and stable P2P DHT through increased memory andbackground overhead,” in Proc. IPTPS’03, Feb. 2003.
[33] A. Gupta, B. Liskov, and R. Rodrigues, “Efficient routing for peer-topeer overlays,” in Proc. NSDI ’04, Mar. 2004, pp. 113–126.
[34] Y. Ando, H. Nagao, T. Miyao, and K. Shudo, “FRT-2-Chord: A DHT
supporting seamless transition between one-hop and multi-hop lookups
with symmetric routing table,” in Proc. ICOIN 2014, 2014.

Proc. 22nd IEEE Symposium on Computers and Communications(IEEE ISCC 2017), pp.424-431, July 2017