Adaptive Topology for Scalability and Immediacyin Distributed Publish/Subscribe Messaging
Ryohei Banno∗† , Kazuyuki Shudo∗∗ Tokyo Institute of Technology, Tokyo, JAPAN† Kogakuin University, Tokyo, JAPAN

Email: banno@computer.org

Abstract—Publish/subscribe is a communication model for
exchanging messages via a broker while providing loose coupling.
So far, several studies have been conducted to address loadconcentration on the broker by forming distributed brokers.
However, although they achieve higher throughput by load distribution among multiple brokers, these existing studies require an
increased latency for message delivery. In this paper, we propose
a novel method to construct and maintain an adaptive topologythat features both scalability and immediacy in distributed
publish/subscribe messaging. The proposed method is for topicbased publish/subscribe systems and uses a number of brokers
to form an overlay network. Its topology changes dynamically tocompose a subgraph for each topic in a single-hop or multi-hop
manner according to the topic load (i.e., the number of clients).
The experimental results show that compared to existing studies,
the proposed method reduces the delivery path length, which isa principal factor that affects latency. Especially for low load
topics, the reduction rate of the proposed method reaches values
greater than 60%.
Index Terms—Overlay networks, Publish subscribe systems,
Skip graphI. I NTRODUCTION
Publish/subscribe is a communication model for exchanging
messages via a server called a “broker”, thus, it provides
loose coupling [1]; the broker dynamically determines thedata receiver based on the message content, so that the sender(publisher) and the receiver (subscriber) need not care about
the communication target. Topic-based publish/subscribe is
one of publish/subscribe messaging patterns and is widelyused in various information systems. In topic-based publish/subscribe systems, publishers and subscribers exchange
messages via logical channels called “topics” as shown in
Figure 1. Subscribers register their interest in topics to thebroker in advance and subsequently receive messages on theirselected topics of interest.
Because topic-based publish/subscribe is suitable for unstable, i.e., frequently changed, relationships among low powered
devices due to its loose coupling nature, it has attracted muchacademic and industrial interest for use in IoT systems. Indeed,
its well-known protocol MQTT [2] has been introduced invarious IoT platforms [3], [4], in addition to the OPC UA
protocol, which is used in the reference architecture modelThis work was supported in part by JSPS KAKENHI Grant No.19K20253,
in part by SECOM Science and Technology Foundation, and in part by New
Energy and Industrial Technology Development Organization (NEDO).

Publisher

BrokerSubscriber

GPS
Topic A
Topic B

Fig. 1. Topic-based publish/subscribe

for Industry 4.0 and supports topic-based publish/subscribe
functionality [5].
When considering a large-scale system composed of a vast
number of IoT devices, the load concentration on the broker
could cause service disruption or reduce the quality of service(QoS). To solve this problem, several existing studies for
distributed publish/subscribe messaging have utilized multiple
brokers [6]–[9]. In these studies, the brokers comprise an
overlay network and work cooperatively to obtain a superiorload distribution.
However, these approaches also increase the latency formessage delivery despite achieving higher throughput by performing load distribution among multiple brokers. In our preliminary experiment, using Interworking Layer of Distributed
MQTT brokers (ILDM) [10], [11], which enables multiple
MQTT brokers to cooperate with each other, the relationshipbetween throughput and latency is depicted in Figure 2.
Note that in this experiment, we simulated the topology of
SG-TBPS described later in Section II-A. The cooperation
among the five brokers results in an approximately three times
higher throughput compared to a single broker, whereas thelatency increases to approximately six times higher. Although
the experiment was done at a small scale and throughput
and latency generally largely depend on the measurement
environment and implementation quality, the results indicatethat a trade-off exists to some extent between scalability and
immediacy.
Because the result in Figure 2 was done in a LAN using only
five brokers, cooperation among a larger number of brokers(e.g., tens of thousands) in an actual network environment
is considered to be likely to involve latencies of dozens tohundreds of milliseconds. Such an increase in latency impairs

Proc. 44th IEEE Computer Society Int'l Conf. on
Computers, Software and Applications (IEEE COMPSAC 2020), July 2020

Latency [msec]

Single broker

Five brokers

15
10
5
0

0

200,000
400,000
Throughput [msg/sec]

600,000

Fig. 2. Effect on throughput and latency by load distribution

the immediacy of publish/subscribe messaging and narrows
its application range. For example, 100 milliseconds delay
is said to substantially degrade the user experience (UX) forweb contents [12] and reduces the product volumes sold in ecommerce systems [13]. In IoT systems especially those that
require high immediacy, such as real-time device control, thelatency requirements are expected to be more severe.
In this paper, we propose a novel method to construct andmaintain an adaptive topology that features both scalability
and immediacy in distributed topic-based publish/subscribe
messaging. The proposed method focuses on the delivery path
length based on the multi-hop forwarding schemes in existingstudies, which is the primary factor that increases latency.
Composing broker topology in a single-hop manner obviously
reduces latency, but it also degrades throughput because multihop forwarding contributes to load distribution. To address
this trade-off and obtain both scalability and immediacy, thetopology of the proposed method is changed dynamically tocompose a subgraph for each topic in a single-hop or multi-hop
manner based on the topic load (i.e., the number of clients).
The remainder of this paper is organized as follows. Section II introduces related studies on distributed topic-based
publish/subscribe messaging. Section III explains some elemental techniques, while Section IV describes the proposed
method. Section V presents the experimental evaluation. Conclusions and suggestions for future work are provided in
Section VI.
II. R ELATED WORK
Several existing studies have utilized multiple brokers for
topic-based publish/subscribe messaging.
Scribe [6] is a method for handling multicast groups using
Pastry [14] which is one of the Distributed Hash Table(DHT) algorithms. In Scribe, a delivery tree is formed on theoverlay network of Pastry for each multicast group. The node
responsible for the group name key becomes the root node forthe group. Reverse paths of routing from the group member
nodes to the root node on the Pastry network compose thetree of the group. When a participant node sends a message
to the root node, the message is forwarded along the tree andeventually delivered to all the group members. By creating agroup for each topic, Scribe can be utilized for topic-based
publish/subscribe messaging.
Bayeux [7] is similar to Scribe, but is based on
Tapestry [15], another DHT algorithm that utilizes forward
paths from the root node to form a delivery tree. Compared to
Scribe, this method has a disadvantage that a root node must
maintain information about all the group members.
CAN-MC [8] is also a multicast method based on a DHT
algorithm called CAN [16]. Different from Scribe and Bayeux,
CAN-MC uses two kinds of overlay networks: a global CAN
network for finding a group and smaller CAN networks fordisseminating a message within a group. Although CAN-MC
has the advantage that a message is forwarded among only
the corresponding group members, its overlay networks haverelatively high maintenance costs.
A. SG-TBPS
Although the above existing studies achieve high scalability,
they possess several inefficiencies. For example, for Scribe
and Bayeux, the path length from a publisher to a subscriberis O(log N ) where N is the number of nodes. Note that
here and hereafter we call a broker connected to a publisher
client of topic t “a publisher of topic t”, as well as wecall a broker connected to a subscriber client of topic t “asubscriber of topic t”. Even when the number of subscribersof the corresponding topic is quite small (e.g., only one), eachmessage is forwarded by O(log N ) nodes; thus, the latency
increases, and network resources are wasted. In addition,for either method, a published message will be wastefully
forwarded even when no corresponding subscriber exists.
These problems become more serious when considering the“data exhaust” in IoT [17]. Namely, IoT data has low value
density; it consists of a small amount of valuable data and alarge amount of less-valuable data. Considering this IoT data,
topics with no or few subscribers are dominant like power-law,
and the above problems become prominent.
To overcome this, a method using Skip Graph [18] wasproposed [9]. Hereafter, we call this method Skip Graphbased topic-based publish/subscribe (SG-TBPS). In SG-TBPS,
a number of brokers are placed at the edge of a wide area
network as shown in Figure 3, composing a Skip Graph
topology. SG-TBPS lets publishers and subscribers of a topic
form connected subgraphs, and the two subgraphs of a topic
are also connected. Accordingly, the following features are
obtained.
The path length from a publisher to a subscriber isO(log M ) where M is the number of nodes interested
in the corresponding topic.
• Publishers can suspend publishing by detecting the absence of the corresponding subscribers.
•

We explain the topological details of SG-TBPS in detail laterin Section III-C.
Although SG-TBPS is more suitable for IoT data comparedto the other above mentioned methods, it still has a problem
of increasing latency as shown in Figure 2.

Proc. 44th IEEE Computer Society Int'l Conf. on
Computers, Software and Applications (IEEE COMPSAC 2020), July 2020

Level 3

10

Level 2

Edge
brokers

13

13

27

27

29

Publishers or Subscribers

Level 0

40

45
45

47
47

36
13

10
10
Node A
000

40

29

10
Level 1

36

29
27

13
Node B
100

27
Node C
010

40
36

29
Node D110

36
Node E
001

47
45

40
Node F
101

45
Node G
011

47
Node H111

Fig. 3. Architecture of SG-TBPS
Level 3

10

13

Level 2

27

27

13

29

Level 0
Key

40

29
40

45
45

47
47

36

10
Level 1

36

13

29

10

27

10
Node A000

13
Node B
100

27
Node C
010

40
36

29
Node D110

36
Node E
001

47
45

40
Node F
101

45
Node G
011

47
Node H111

Fig. 5. Routing range query by SFB

and processed recursively. Figure 5 shows an example. If nodeA issues a range query with a target range from 10 to 40, therange is divided by the keys of the neighbors of node A. Each
subrange is forwarded to the neighbors and processed in thesame manner.
SFB has a shorter path length and a smaller number ofmessages than do other methods, such as MRF [22] orsequential traversing and broadcasting [23].

Membership vector

C. Topology of SG-TBPS
Fig. 4. Example of Skip Graph

III. P RELIMINARIESIn this section, we explain some of the elemental techniques
utilized in our proposed method.
A. Skip Graph
Skip Graph [18] is a type of structured overlay network
known for its ability to handle range queries. Each node has
a key and a random sequence called a membership vector. In
this paper, we assume the alphabet Σ = 0, 1 for membership
vectors.
As shown in Figure 4, a Skip Graph topology composesa multiplex structure of skip list [19]. It has a hierarchicalstructure; Level 0 is a doubly linked list containing all thenodes sorted by key, while in Level i, the nodes whose
membership vectors have the same i-digit prefix compose adoubly linked list. Any node can search for another node byspecifying a key. The node search begins from the maximum
level of the start node, then the query is forwarded to thefarthest node that does not exceed the target key and gradually
moves down to Level 0. Thus, the path length is O(log N ) for
N nodes.
B. Range queries in Skip Graph
Since nodes in Skip Graph are sorted by keys, which differsfrom DHTs, any node can search for other nodes by specifying
a key range.
SFB [20], [21] is one of the methods for routing range
queries in Skip Graph. It introduces a divide-and conquer
approach in which the target range is divided into subranges

As described in Section II-A, SG-TBPS is a method for distributed toipc-based publish/subscribe messaging using Skip
Graph. Brokers placed at the edge of a wide area network
compose an overlay network. Each broker generates a key
from its topic name of interest and its node types: publishers
or subscribers. By using this key, the brokers maintain thevirtual nodes of Skip Graph and form a topology, as depicted
in Figure 6.
Thus, the publishers and subscribers of a topic form connected subgraphs respectively, and the two subgraphs of a topic
are also connected. This scheme results in the existence ofa unique publisher node for each topic, called a rendezvous
point, which is placed adjacent to the subgraph of the subscribers of the same topic in Level 0. The rendezvous point can
detect when the corresponding subscribers are absent simply
by checking its right-hand neighbor for Level 0. When therendezvous point detects the absence of subscribers, it notifies
the other publishers of that topic so that they can suspend
publishing.
D. Flexible Routing Tables
Flexible Routing Tables (FRT) [24] is a method for maintaining routing tables flexibly in structured overlay networks.
Generally, in the algorithms of structured overlay networks
such as DHTs [14], [15], [25] and Skip Graph, a node’s routing
table is constructed by adding node information (entries)that satisfy certain conditions defined in each algorithm. For
example, in Skip Graph, each routing table entry satisfies thecondition that the membership vectors have a corresponding
common prefix. In contrast, FRT uses the following two steps
to construct a routing table.
1) Entry learning: add entries without any conditions.

Proc. 44th IEEE Computer Society Int'l Conf. on
Computers, Software and Applications (IEEE COMPSAC 2020), July 2020

Publisher

Level 3

Subscriber

Subgraph of
publishers on topic 𝑡𝑡𝑖𝑖

𝑡𝑡𝑖𝑖

Level 1
Level 0𝑡𝑡𝑖𝑖−1𝑡𝑡𝑖𝑖−1𝑡𝑡𝑖𝑖−1

Topic 𝑡𝑡𝑖𝑖−1

𝑡𝑡𝑖𝑖
𝑡𝑡𝑖𝑖

Subscriber

Subgraph ofsubscribers on topic 𝑡𝑡𝑖𝑖

𝑡𝑡𝑖𝑖

Level 2Publisher

𝑡𝑡𝑖𝑖

𝑡𝑡𝑖𝑖
𝑡𝑡𝑖𝑖

𝑡𝑡𝑖𝑖

𝑡𝑡𝑖𝑖

𝑡𝑡𝑖𝑖

𝑡𝑡𝑖𝑖
𝑡𝑡𝑖𝑖
𝑡𝑡𝑖𝑖

𝑡𝑡𝑖𝑖

𝑡𝑡𝑖𝑖
𝑡𝑡𝑖𝑖
𝑡𝑡𝑖𝑖

Topic 𝑡𝑡𝑖𝑖

Rendezvous pointof topic 𝑡𝑡𝑖𝑖

Level 2𝑡𝑡𝑖𝑖+1

𝑡𝑡𝑖𝑖+1

Topic 𝑡𝑡𝑖𝑖+1

Level 0

𝑡𝑡𝑖𝑖

𝑡𝑡𝑖𝑖

𝑡𝑡𝑖𝑖

Level 1
𝑡𝑡𝑖𝑖+1𝑡𝑡𝑖𝑖

𝑡𝑡𝑖𝑖

Level 3𝑡𝑡𝑖𝑖−1𝑡𝑡𝑖𝑖

𝑡𝑡𝑖𝑖

Node A

𝑡𝑡𝑖𝑖

Node B

𝑡𝑡𝑖𝑖
𝑡𝑡𝑖𝑖
𝑡𝑡𝑖𝑖
𝑡𝑡𝑖𝑖

Node C

𝑡𝑡𝑖𝑖

𝑡𝑡𝑖𝑖

𝑡𝑡𝑖𝑖
𝑡𝑡𝑖𝑖
𝑡𝑡𝑖𝑖
𝑡𝑡𝑖𝑖

Node D

𝑡𝑡𝑖𝑖
𝑡𝑡𝑖𝑖

Node E

𝑡𝑡𝑖𝑖

𝑡𝑡𝑖𝑖

𝑡𝑡𝑖𝑖

𝑡𝑡𝑖𝑖

𝑡𝑡𝑖𝑖

𝑡𝑡𝑖𝑖
𝑡𝑡𝑖𝑖

𝑡𝑡𝑖𝑖

Node G

Node F

𝑡𝑡𝑖𝑖

𝑡𝑡𝑖𝑖

𝑡𝑡𝑖𝑖
𝑡𝑡𝑖𝑖

Node H

𝑡𝑡𝑖𝑖+1

Fig. 6. Topology of SG-TBPS
Fig. 7. Topology of ATM-TBPS

2) Entry filtering: remove one entry when the number of
entries exceeds the given maximum size L.
Entry learning can be done by actively issuing a search
query for a random target key or by passively using information obtained when forwarding messages from other nodes.
In entry filtering, the entry to be removed is selectedfrom entries other than the mandatory entries called “sticky
entries”. The selection process is conducted by using an orderrelationship ≤F RT among routing tables, which determines
the relative superiority or inferiority among routing tables; forexample, E ≤F RT F means that routing table F is superior
to routing table E. Among all the possible routing tables
creatable by removing one entry from the current routing table,
the best routing table is selected in accordance with ≤F RT andthe corresponding entry will be removed. By defining ≤F RT
appropriately according to each application, we can flexibly
construct a variety of structured overlay networks.
One of the advantages of FRT is that it can construct both
single-hop and multi-hop overlay networks using the samealgorithm. That is, when the number of nodes is equal to orless than the maximum routing table size L, each node canhave the entries of all other nodes in its routing table; thus the
topology becomes single-hop. However, when the number ofnodes exceeds L, the topology becomes multi-hop based on
the entry filtering process. In contrast, in structured overlay
networks without FRT, each node does not possess the entries
of nodes that do not satisfy certain conditions in its routing
table. Therefore, even when the number of nodes is small, thetopology largely remains multi-hop.
IV. P ROPOSED METHODAs described in Section I, the existing methods described in
Section II involve an increase of latency in return for higher
scalability. In this section, we explain the proposed method
for achieving both scalability and immediacy. Hereafter, wecall the proposed method the adaptive topology management
for topic-based publish/subscribe (ATM-TBPS).
A. Order relationship among routing tables
ATM-TBPS introduces the concept of FRT into SG-TBPS.
In ATM-TBPS, ≤F RT is defined so that the routing tablethat includes the subscriber nodes of the same topic becomessuperior to those that do not include the subscriber nodes.
This enables nodes related to a topic with a small number ofsubscribers to form a single-hop, i.e., a full mesh, subgraph.
On the other hand, nodes related to a topic with a large
number of subscribers form a multi-hop subgraph to avoid
concentrating the message delivery load. Using this approach,
we can obtain both scalability and immediacy: low latency for
low-load topics and high throughput for high-load topics.
We define ≤F RT by extending FRT-Skip Graph [26] tokeep the entries of subscribers of the same topic in routing
tables with high priority. Specifically, the following policies
are applied in turn to determine the superiority of routing
tables. Note that entries corresponding to the neighbors forLevel 0 in Skip Graph are sticky entries.
1) Keep entries corresponding to neighbors for each levelin Skip Graph.
2) Keep entries of subscribers of the same topic.
3) Keep the same number of entries for each level.
4) Keep entries of nodes whose membership vectors havea longer common prefix.
5) Keep entries of nodes whose keys are closer.
Consider the example shown in Figure 7. Node A has
preferential entries for nodes B, C, and E in its routing tablebecause they correspond to its neighbors for each level in Skip
Graph. When the maximum routing table size L of node A issufficiently large, there is a possibility that entries for nodes
D, F, G, and H will be added to node A’s routing table. The

Proc. 44th IEEE Computer Society Int'l Conf. on
Computers, Software and Applications (IEEE COMPSAC 2020), July 2020

B1 (E, F )⇔B2 (E, F )⇔ lmax (E) = lmax (F ) ∧ |EM P (E)| = |EM P (F )|lmax (E) < lmax (F ) ∨ (lmax (E) = lmax (F ) ∧ |EM P (E)| > |EM P (F )|)B3 (E, F )⇔ B2 ∧ |SU B(E)| < |SU B(F )|B4 (E, F )⇔ B2 ∧ |SU B(E)| = |SU B(F )|B5 (E, F )⇔ B4 ∧ |M AX(E)| < |M AX(F )|B6 (E, F )⇔B4 ∧ |M AX(E)| = |M AX(F )|B7 (E, F )⇔B6 ∧ min(M AX(E)) < min(M AX(F ))B8 (E, F )⇔B6 ∧ min(M AX(E)) = min(M AX(F ))B9 (E, F )⇔B8 ∧ KEY (SU CC(E)) >dic KEY (SU CC(F ))B10 (E, F )⇔B8 ∧ KEY (P RED(E)) >dic KEY (P RED(F ))

Entry

Level

Entry

Level

Entry

Level

Node B

0

Node B

0

Node B

0

Node C

1

Node C

1

Node C

1

Node D0

Node D0

Node E

2

Node E

2

Node F

0

Node G

1≤𝐹𝐹𝐹𝐹𝐹𝐹

Node E

2

Node F

0

Node G

1≤𝐹𝐹𝐹𝐹𝐹𝐹

Fig. 8. Superiority of routing tables(1)

To define ≤F RT to satisfy the above policies, we first definesome notations for the routing table E of node X as shown in
Table I. Using these notations, we can define the propositions
in Equation (1). Herein, >dic indicates lexicographic order;
then we have{ai } <dic {bi } ⇔ ak < bk

From the above propositions, the order relationship between
routing table E and F in ATM-TBPS is defined as follows:
E ≤F RT F

TABLE IL IST OF NOTATIONS
Notation
lmax (E)
EM P (E)SU B(E)
M AX(E)SU CC(E)
P RED(E)KEY (E)

Description
The maximum level in routing table E.
A set of levels for which routing table E has no
entries. That is, EM P (E) = {li | |Eli | = 0}.
A set of entries of subscribers whose topic is thesame as X in routing table E.
A set of levels for which routing table E has themost entries.
A set of entries on the right hand side of X inrouting table E.
A set of entries on the left hand side of X inrouting table E.
A sequence of entries sorted by key in routing
table E.

(k = min{i | ai 6= bi }).

⇔B1 (E, F ) ∨ B3 (E, F )∨ B5 (E, F ) ∨ B7 (E, F )∨ B9 (E, F ) ∨ B10 (E, F )Reconsidering the example in Figure 8, in the case of
focusing on the part depicted in Figure 7, we can see thatthe order of those three routing tables is following the above
definitions.
Let us say we have the three routing tables R1 ={B, C, D, E, F }, R2 = {B, C, E, F, G}, and R3 ={B, C, D, E, G}. For R1 and R2 , B2 (R1 , R2 ) is true becauselmax (R1 ) = lmax (R2 ) = 3
and|EM P (R1 )| = |EM P (R2 )| = 1.

dotted lines in Figure 7 indicate these potential links from node
A. If the max level of node A is three and L = 8, node A isable to add two entries in addition to the entries corresponding
to its three neighbors on both sides in Skip Graph. If node A
acquires the entries for nodes D, F, and G by the entry learning
process, it must remove one of the three entries by the entry
filtering process. There are three possible routing tables andtheir order by ≤F RT is as shown in Figure 8. To preserve thesame number of entries for each level insofar as possible, theremoval of node G is determined to be inferior because nodes
D and F are both Level 0 entries. Additionally, to keep theentries for nodes whose keys are closer, the removal of node D
is determined to be inferior to the removal of node F, because
the key of node D is closer to that of node A. Therefore,
the entry for node F is removed in this case. Note that if L
were larger than 10, node A could hold information for all
the subscriber nodes of topic ti (i.e., the topic ti subgraphbecomes a single-hop topology).

B4 (R1 , R2 ) is also true because|SU B(R1 )| = |SU B(R2 )| = 5.
Since
|M AX(R1 )| = 1 < |M AX(R2 )| = 2,
B5 (R1 , R2 ) is true and consequently we can find R1 ≤F RT
R2 .
For R2 and R3 , in the same manner, we can find that
B2 (R2 , R3 ), B4 (R2 , R3 ), B6 (R2 , R3 ), and B8 (R2 , R3 ) aretrue becauselmax (R2 ) = lmax (R3 ) = 3,
|EM P (R2 )| = |EM P (R3 )| = 1,
|SU B(R2 )| = |SU B(R3 )| = 5,
|M AX(R2 )| = |M AX(R3 )| = 2,min(M AX(R2 )) = min(M AX(R3 )) = 0.

Proc. 44th IEEE Computer Society Int'l Conf. on
Computers, Software and Applications (IEEE COMPSAC 2020), July 2020

Subranges by original SFB
Level 3

10

Level 2

10

Level 1

10

Level 010Node A000

D. Node join

Subranges by modified SFB

36
27
13
Node B
100

27
Node C010

29
Node D
110

36

45

36
Node E
001

45
Node G
011

Fig. 9. Difference in dividing target range between SFB and modified SFB

B9 (R2 , R3 ) is also true because
KEY (SU CC(R2)) >dic KEY (SU CC(R3)),and consequently we can find R2 ≤F RT R3 .
B. Queries in ATM-TBPS
In ATM-TBPS, the queries listed in Table II are used tomaintain the routing tables. Note that both the sender andforwarder information contain the IP address, the membership
vector, and the key of the corresponding node.
The following sections explain the process that occurs eachnode when using these queries1 . Hereafter, we notate the nodecorresponding to the neighbor for Level i in Skip Graph as“Level i neighbor node”.
C. Routing messages
For exchanging messages and management notification
among nodes, ATM-TBPS utilizes SFB described in Section III-B.
Note that we slightly modify the algorithm of SFB for ATMTBPS, because it assumes a normal Skip Graph topology. In
SFB, the key used to divide a target range is chosen in theorder from the top-most level within the range. However, inthe topology of ATM-TBPS, a routing table of a node could
have multiple entries for the same level, unlike Skip Graph.
That is, an entry for a level li could be farther than anotherentry for a level lj even if li < lj . For this reason, in ATMTBPS, the key used to divide a target range is chosen in theorder from the farthest key within the range.
Figure 9 shows an example difference in dividing the target
range between SFB and the modified SFB in the case of
Figure 8, i.e., Node A has entries of Node B, C, D, E, and
G in its routing table. The target range is divided from thefarthest key by using the modified SFB whereas it is divided
from the top-most level neighboring key by using the original
SFB.
1 Note that the processes that are the same as SG-TBPS are omitted fromthis explanation.

When a new node joins a topic as a subscriber, it firstsearches its position by using a normal Skip Graph search
query and adds both sides neighbors for Level 0 to its routing
table as sticky entries. Then, it sends an REXP query withthe search level set to 0 to the Level 0 neighbor nodes
on both sides. This query is intended to collect the entries
corresponding to neighbors for each level of Skip Graph.
After a certain period of time, if the number of entries isless than the maximum size L, the node issues an EEXP query
targeting the range of subscribers of the same topic. If thenumber of entries is still less than L after a certain period oftime, the node repeatedly issues an EEXP query to a randomtarget.
E. Node leave
When a subscriber node leaves a topic, the node issues an
UNSUB query targeted to the range of publishers of the topic.
This query is intended to allow the removal of the entry of
the leaving node from the routing tables of the publishers.
Basically, nodes do not manage information regarding
which nodes have an entry for their own information, because
the routing table construction is asymmetrical in FRT. However, removing disabled entries by using the timeout techniquegreatly impairs immediacy. Therefore, a departing node issues
an UNSUB query as described above.
F. Publish
A publisher node can deliver a PUB query to all thecorresponding subscribers by using SFB as described above.
If the number of entries is less than the maximum size L, an
EEXP query is piggy-backed onto the PUB query, enabling
rapid identification of the subscriber nodes for the given topic.
G. Normal process
Each node sends a REXP query with the search level set
to 0 to its Level 0 neighbor nodes on both sides at regularintervals. This query is intended to allow entries to be updated
corresponding to the neighbors for each level of Skip Graph.
H. Receiving query
When a node receives a REXP query, it sends a NEW queryto the sender node if the list of existing entries in the REXP
query does not include itself. If the search level of the REXP
query is i and the node corresponds to the Level i+1 neighbornode of the sender node, the node increases the search levelby 1 and forwards the query to its Level i + 1 neighbor node.
If the node does not correspond to the Level i + 1 neighbornode of the sender node, the node simply forwards the query
to its Level i neighbor node. When no corresponding node
exists to which to forward to the query, the node terminates
the process.
When a node receives an EEXP query, it sends a NEW
query to the sender node if the list of existing entries in the
EEXP query does not include itself. The node decreases thenumber of wanted entries in the query by 1; then, it forwards

Proc. 44th IEEE Computer Society Int'l Conf. on
Computers, Software and Applications (IEEE COMPSAC 2020), July 2020

TABLE II
Q UERIES FOR MAINTAINING ROUTING TABLES
Description

REXP

Query for regular exploration of entries

EEXP

Query for extra exploration of entries

PUB

Query for publishing a message

UNSUB

Query for notifying unsubscribing from a topic

NEW

Query for notifying a new candidate of entry

Contained information• Sender information (IP address, membership vector, key, etc.)• Forwarder information (IP address, membership vector, key, etc.)• List of existing entries• Search level• Sender information (IP address, membership vector, key, etc.)• Forwarder information (IP address, membership vector, key, etc.)• List of existing entries• Number of wanted entries• Sender information (IP address, membership vector, key, etc.)• Topic• Published message• Forwarder information (IP address, membership vector, key, etc.)• Sender information (IP address, membership vector, key, etc.)• Forwarder information (IP address, membership vector, key, etc.)• Sender information (IP address, membership vector, key, etc.)

the query to the corresponding destination if the number ofwanted entries is still greater than 1.
When a node receives an UNSUB query, it removes theentry of the sender node from its routing table.
For every query received by a node, the node adds the sendernode and the forwarder node to its routing table if they are
not already present; however, the sender node of an UNSUB
query is not added.
V. E VALUATION
We evaluated ATM-TBPS through simulation experiments.
The simulation program was implemented in Java.
The number of brokers was 10, 000. Each broker joined 5
topics on average as either a publisher or a subscriber. We used
one topic for measurement; the topic had one publisher anda variable number of subscribers ranging from 10 to 5, 120.
We measured the average and maximum path lengths. Eachmeasurement was conducted three times for each setting, andthe result was calculated as the average value of those threemeasurements.
We used Scribe and SG-TBPS, described in Section II, as
comparison targets. The value of L, the maximum size of arouting table, was set to 60 or 120. Note that the maximum sizeof routing tables in SG-TBPS was 58. Unlike ATM-TBPS, thesize of a routing table is decided probabilistically in SG-TBPS
and Scribe. This means that each node must be capable of thelargest possible routing table size in the existing methods.
Figure 10 shows the result of the average path length. For
ATM-TBPS, the path length becomes 1 when the number ofsubscribers is small. When executing ATM-TBPS with L set to120, single-hop delivery was achieved for up to 80 subscribers.
Compared to SG-TBPS, the reduction rate of the average path
length of ATM-TBPS with L = 60 is more than 60% for up
to 80 subscribers and more than 20% even for larger numbersof subscribers.
Figure 11 shows the maximum path length. For SG-TBPS
and Scribe, the maximum path length is larger than the averagepath length. For ATM-TBPS, the maximum path length is 1
for small numbers of subscribers.

ATM-TBPS (L = 60)

ATM-TBPS (L = 120)

SG-TBPS

Scribe16
14

Average path length

Query

12
10
8
6
4
2
0

10

20

40

80 160 320 640 1280 2560 5120
Number of subscribers

Fig. 10. Average path length

A. Discussion on latency
We compared latency using simple modeling. We assumed
the following delay time:
The communication delay between nodes is 10 milliseconds.
• The processing delay of a node on the message delivery
path is 1 millisecond.
• The processing delay of a node for its each child nodeon the message delivery path is 0.1 millisecond.
•

Figure 12 shows the results. Note that we calculated latency
for a single broker case besides ATM-TBPS, SG-TBPS, andScribe. It was approximated by considering the case that the
number of child nodes was equal to the number of subscribers.
For Scribe and SG-TBPS, the latency becomes worse thana single broker when the number of subscribers is relatively
small, although they achieve better latency with larger numbers

Proc. 44th IEEE Computer Society Int'l Conf. on
Computers, Software and Applications (IEEE COMPSAC 2020), July 2020

40

ATM-TBPS (L = 60)

ATM-TBPS (L = 120)

ATM-TBPS (L = 60)

ATM-TBPS (L = 120)

SG-TBPS

Scribe

SG-TBPS

ScribeSingle broker
500

30

Estimated latency [msec]

Maximum path length

35

25
20
15
10
5
0

10

20

40

80 160 320 640 1280 2560 5120
Number of subscribers

400
300
200
100
0

10

20

40

80 160 320 640 1280 2560 5120
Number of subscribers

Fig. 11. Maximum path length

Fig. 12. Estimated latencyof subscribers. However, this inefficiency for small numbersof subscribers is not desirable for IoT systems, because topics
with no or few subscribers are considered to be dominant, as
described in Section I. In contrast, using ATM-TBPS, it canbe seen that both scalability and immediacy are obtained; thelatency is comparable to that of a single broker for small numbers of subscribers, and remains comparable to the latencies
of previous methods for larger numbers of subscribers.
One thing to be mentioned is throughput performance of
ATM-TBPS. Throughput is affected by various factors such as
bandwidth and RTT among nodes, underlying protocols, andoccurrence of re-transmission. Assuming a single topic and ahomogeneous network environment, the dissemination load ofeach node is considered to be proportional to the number ofchild nodes, i.e., neighbor nodes to be forwarded a message.
In other words, throughput performance is suppressed to thevalue dividing the bandwidth with the number of child nodes.
ATM-TBPS can keep the number of child nodes small by
the entry filtering process even if the number of subscribers
for the topic is quite large. This enables ATM-TBPS to havehigher throughput than a single broker. Although quantitativeevaluation of throughput performance is out of the scope of
this paper, it is one of our future works.

In future work, we plan to conduct an evaluation of throughput performance with actual protocols e.g., MQTT and morepractical experiments such as simulating nodes joining or
leaving.

VI. C ONCLUSION
In this paper, we proposed a novel method called ATMTBPS that achieves both scalability and immediacy for distributed topic-based publish/subscribe messaging. By utilizing the FRT concept, the topology of ATM-TBPS changes
dynamically to compose a subgraph for each topic in eithera single or multi-hop manner based on the topic load (i.e.,
the number of subscribers). The experimental results showthat ATM-TBPS reduces the delivery path length and latency
compared to existing studies, especially for low-load topics.

R EFERENCES[1] P. T. Eugster, P. A. Felber, R. Guerraoui, and A.-M. Kermarrec, “TheMany Faces of Publish/Subscribe,” ACM Computing Surveys, vol. 35,
no. 2, pp. 114–131, 2003.
[2] Akamai IoT Edge Connect, https://developer.akamai.com/iot-edgeconnect/ (accessed 2020-01-30).
[3] Amazon Web Services, “Designing MQTT Topics for AWS IoT Core,”
May 2019.
[4] MQTT, https://mqtt.org/ (accessed 2020-01-30).
[5] OPC Foundation, “OPC Foundation announces OPC UA PubSub
release as important extension of OPC UA communication platform,”
https://opcfoundation.org/news/press-releases/opc-foundationannounces-opc-ua-pubsub-release-important-extension-opc-uacommunication-platform/ (accessed 2020-01-30), March 2018.
[6] M. Castro, P. Druschel, A.-M. Kermarrec, and A. Rowstron, “Scribe: Alarge-scale and decentralized application-level multicast infrastructure,”
IEEE Journal on Selected Areas in communications, vol. 20, no. 8, pp.
1489–1499, December 2002.
[7] S. Q. Zhuang, B. Y. Zhao, A. D. Joseph, R. H. Katz, and J. D.
Kubiatowicz, “Bayeux : An Architecture for Scalable and Fault-tolerant
Wide-area Data Dissemination,” in Proc. International Workshop on
Network and Operating Systems Support for Digital Audio and Video,
June 2001, pp. 11–20.
[8] S. Ratnasamy, M. Handley, R. Karp, and S. Shenker, “Application-Level
Multicast using Content-Addressable Networks,” in Proc. International
COST264 Workshop on Networked Group Communication, November
2001, pp. 14–29.
[9] R. Banno, S. Takeuchi, M. Takemoto, T. Kawano, T. Kambayashi, and
M. Matsuo, “Designing Overlay Networks for Handling Exhaust Data ina Distributed Topic-based Pub/Sub Architecture,” Journal of Information
Processing, vol. 23, no. 2, pp. 105–116, 2015.
[10] R. Banno, J. Sun, M. Fujita, S. Takeuchi, and K. Shudo, “Disseminationof edge-heavy data on heterogeneous MQTT brokers,” in Proc. IEEE
International Conference on Cloud Networking (CloudNet), September
2017, pp. 1–7.
[11] R. Banno, J. Sun, S. Takeuchi, and K. Shudo, “Interworking Layer ofDistributed MQTT Brokers,” IEICE Transactions on Information and
Systems, vol. E102.D, no. 12, pp. 2281–2294, 2019.

Proc. 44th IEEE Computer Society Int'l Conf. on
Computers, Software and Applications (IEEE COMPSAC 2020), July 2020

[12] Google, “Measure Performance with the RAIL Model,” https://developers.google.com/web/fundamentals/performance/rail/ (accessed2020-01-30).
[13] R. Kohavi and R. Longbotham, “Online Experiments: Lessons Learned,”
IEEE Computer, vol. 40, no. 9, pp. 103–105, September 2007.
[14] A. Rowstron and P. Druschel, “Pastry: Scalable, Decentralized Object
Location, and Routing for Large-Scale Peer-to-Peer Systems,” in Proc.
IFIP/ACM International Conference on Distributed Systems Platforms
and Open Distributed Processing, November 2001, pp. 329–350.
[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,” IEEE Journal on Selected Areas in Communications,vol. 22, no. 1, pp. 41–53, January 2004.
[16] S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker, “Ascalable Content-Addressable Network,” ACM SIGCOMM Computer
Communication Review, vol. 31, no. 4, pp. 161–172, October 2001.
[17] J. Manyika, M. Chui, B. Brown, J. Bughin, R. Dobbs, C. Roxburgh, andA. H. Byers, Big data: The next frontier for innovation, competition, andproductivity. McKinsey Global Institute, 2011.
[18] J. Aspnes and G. Shah, “Skip Graphs,” ACM Transactions on Algorithms(TALG), vol. 3, no. 4, pp. 37:1–37:25, November 2007.
[19] W. Pugh, “Skip Lists : A Probabilistic Alternative to Balanced Trees,”
Communications of the ACM, vol. 33, no. 6, pp. 668–676, June 1990.
[20] R. Banno, T. Fujino, S. Takeuchi, and M. Takemoto, “SFB: A Scalable
Method for Handling Range Queries on Skip Graphs,” IEICE Communications Express, vol. 4, no. 1, pp. 14–19, January 2015.
[21] R. Banno and K. Shudo, “An Efficient Routing Method for Range
Queries in Skip Graph,” IEICE Transactions on Information and Systems, vol. E103.D, no. 3, 2020.
[22] Y. Konishi, M. Yoshida, S. Takeuchi, Y. Teranishi, K. Harumoto, andS. Shimojo, “An Extension of Skip Graph to Store Multiple Keys on
Single Node,” Journal of Information Processing Society of Japan (inJapanese), vol. 49, no. 9, pp. 3223–3233, September 2008.
[23] A. G. Beltran, P. Milligan, and P. Sage, “Range queries over skip
tree graphs,” Computer Communications, vol. 31, no. 2, pp. 358–374,
February 2008.
[24] 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 International Conference on Peer-to-Peer Computing,
August 2011, pp. 72–81.
[25] I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan,“Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications,” SIGCOMM Computer Communication Review, vol. 31, no. 4, pp.
149–160, October 2001.
[26] M. Hojo, R. Banno, and K. Shudo, “FRT-Skip Graph: A Skip Graphstyle structured overlay based on Flexible Routing Tables,” in Proc.
IEEE Symposium on Computers and Communication (ISCC), June 2016,
pp. 657–662.

Proc. 44th IEEE Computer Society Int'l Conf. on
Computers, Software and Applications (IEEE COMPSAC 2020), July 2020