IEEE ISCC 2017
July 2017

Message Bundling on
Structured Overlays
Kazuyuki Shudo
Tokyo Institute of Technology

首藤 一幸
東京工業大学Tokyo TechBackground:

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

Responsible node
for the requested
data item

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

192.168.0.2
192.168.0.3
192.168.0.4

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

1/8

Contribution:Collective Forwarding• A message bundling technique A large amount of data
for structured overlays.
…
…

…
…

– combines multiple messages into asingle message.
– mitigates

…
…

…
…

…
…

…
…

…
…
…
…

Put and get• the load of nodes on the overlay network.
• the load of Internet routers on anunderlay network by reducing # ofpacket transmission.

– Results• # of packet transmission: 34 % ~ 12 %• Data loading time: 13.0 % ~ 9.5 %Structured overlay
with many number of nodes

Problem:

Delivery time and underlay loadOverlay
Message delivery

1:• Message delivery on astructured overlay takes
much time.

2– 10,000 get operations on a DHT Message forwarding
took 40 ~ 700 sec (Section IV.C) .
Packet delivery (transmission)– A message delivery requires
multiple …

:• An overlay imposes aburden on an underlay.

2
5

RouterPacket forwarding

UnderlayProposed technique:Collective forwarding• combines multiple messages whose next hops are
the same node, and forward collectively.
– A requesting node has a large number of requests. e.g. DB backup

9 times# of forwarding 15 times
3 hops x 5 routes

3rd hop
2nd hopwith collective forwarding
FGHICDENode

1st hopBRoute0 hop

Node AJ

Proposed technique:Collective forwarding•Bundle– Messages with the same next hop.

3rd hop
2nd hop
1st hop

ID1

ID2

ID3

ID4ID5

Node FG

HI

J

ID1

ID2

ID3

ID4

ID5

Node CID1

ID2

DID3

EID4

ID1

ID2

ID3

ID4

2. Divides a bundle
based on the next hops

ID5

Next hop is node B

0 hop

1. Looks up next hops
on routing table

ID55 messages with each target ID

3. Forwards the bundles
to their next hops

Effects• On an overlay– Throughput improvement• by handling multiple messages
Parallel processing of multiple messages– Load reduction of nodes• by reducing message forwarding operations.
e.g. message decode/encode, routing table lookup, …

• On an underlay– Packet transmission reduction
Load reduction• cf. Performance of Internet routers is shown in pps (packets per second)

Initial bundle grouping• A bundle is continuously divided once
forwarding starts.
• How does the technique compose initialbundles?
– It is not good to combine all the millions of messages.
e.g. should be < MTU with UDP• Policy• In our experiments– 10– Size
– Target ID‐clustered and random– Grouping– When? Who? – Before routing, outside an overlay

Experiments
1. # of packet transmission on an underlay
IP packet delivery from a node to another node

2. Message delivery time on an overlay• Conditions– 1000 nodes simulated on a single PC.
– Overlay Weaver [Shudo 2008]• runs structured overlay routing algorithms and• simulates a distributed environment. E.g. comm. Latency– Target IDs are randomly determined.
– Routing algorithms: Chord, Koorde, Pastry, Tapestry and Kademlia– Forwarding styles: iterative and recursive

# of packet transmission• Ratio to # without the technique.
serial• Initial bundle
grouping
better– “serial”: the technique
not applied.
– “random”– “clustered”: target ID‐
based clustering• Consideration

Note: the forwarding style is recursive– The # was reduced toaround the theoreticallimit 0.1.
– In Kademlia, a k‐bucket was fulfilled
and the node sends
PING msg many times.

• Put and then got 50,000 data items on 1,000 nodes.
• Measured the # of packet transmission on an underlay, e.g. Internet.

Message delivery time
• Elapsed time to get 10,000 data items from 1,000 nodes• 1 ms of comm. latency is simulated by Overlay Weaver.
• Two techniques forparallel processing

secbetter– Collective forwarding– Multiple (10) clients,
send requests in parallel• Considerationwith
10 clientswith10 clients# of messages that can be processed concurrentlyBundle size (10) x # of clients, that get data from a DHT– With concurrency 10,delivery speeded up 7.5~ 8.5 times.
– Effects of the two techs
are comparative: 7.9 sec
vs. 6.9 sec.
– Effects of the two techs
are cumulative.

Related work
• Message bundling– A common technique for networks.
– Investigated for various networks:
wireless sensor network, DTN, virtual machines, …

• MARIF [Mizutani 2013]– Bulk data transfer technique over a DHT– MARIF is dedicated to DHT, but collective forwarding works
with structured overlays and supports multicast, for example.

• Techniques to improve efficiency of single
message delivery– Proximity routing– 1‐hop DHT

Summary• Collective forwarding– combines multiple messages into a bundle andforwards it to the next hop.

• Effects– Improves throughput of an overlay– Reduces # of packet transmission on an underlay• Experimental results• # of packet transmission: 34 % ~ 12 %• Data loading time: 13.0 % ~ 9.5 %– With 10 clients, 7.03 % 〜 3.12 %Tokyo Tech