Subscription-Driven Self-Organization in Content-Based Publish/Subscribe
Roberto Baldoni Roberto Beraldi Leonardo Querzoni
Antonino Virgillito
Dipartimento di Informatica e Sistemistica
Universit`a di Roma “La Sapienza”
Via Salaria 113, 00198, Roma, Italy
email: {baldoni, beraldi, querzoni, virgi}@dis.uniroma1.it
Abstract
Recently many scalable and efficient solutions for rout- ing events in content-based systems realized through net- works of brokers have appeared in the literature. These so- lutions usually exhibit nice performance when subscribers with similar interest are physically close to each other (e.g.
in the same LAN, domain or in the same geographical area) and connected to a broker which is also nearby. If these subscribers are dispersed on the Internet, the benefits of such routing strategies significantly decrease. In this pa- per we propose a novel approach for enhancing content- based routing performance through a self-organizing al- gorithm executed by the brokers whose aim is to logically place close (in terms of TCP hops) brokers that manage sub- scribers with similar interests. Metrics for measuring simi- larity of interests are discussed and a self-organizing algo- rithm is presented along with a performance analysis.
1. Introduction
Content-based publish/subscribe (pub/sub) communi- cation systems are a basic technology for many-to-many event diffusion over large scale networks with a poten- tially huge number of clients. Content-based pub/sub [2, 1, 3, 8] is notoriously more flexible than its topic-based counterpart [7, 9, 15], although it is remarkably more diffi- cult to implement: in particular the set of intended receivers for an event cannot be determined a priori but must be com- puted on a per-event basis. This makes content-based pub/sub not immediately scalable to systems with a high number of producers (publishers), consumers (sub- scribers) and a high event publication rate. Scalable solu- tions are obtained considering a network of event brokers linked through transport-level connections and dispatch- ing events from publishers to subscribers [2, 8].
The reference solution for event diffusion in content- based pub/sub is the content-based routing algorithm (CBR), used in [2], [3] and [12]. CBR avoids an event to be diffused in parts of the network where there are no sub- scribers for it. This highly reduces the number of TCP hops experienced by an event e to be diffused to all its in- tended subscribers (TCP hops metric). More specifically, the filtering capabilities of the CBR algorithm perform at its best when each broker presents a high physical simi- larity among its subscriptions (i.e., all subscribers sharing similar interests are physically connected to the same bro- ker). In other words, high physical similarity implies low values of the TCP hops per event diffusion when us- ing a CBR algorithm [6]. On the contrary, when physical similarity is low (i.e., subscribers sharing similar inter- est are connected to a dispersed subset of distinct brokers which are far each other in terms of TCP hops), the per- formance gain obtained using the CBR algorithm, with re- spect to an algorithm that simply floods the network with events, becomes negligible. Hence, such perfor- mance gain depends in general from the distribution of the subscription in the brokers’ network.
In this paper we propose a self-organizing algorithm ex- ecuted by brokers, which dynamically arranges TCP con- nections between pair of brokers in order to maximize an associativity metric among neighbor brokers. Associativity measures the degree of similarity of the subscriptions man- aged by a broker with the ones of its neighbors, where sim- ilar means that most of the events matching subscriptions managed by a broker are also managed by the other. The al- gorithm uses this heuristic to put users sharing similar in- terests as close as possible even though they are connected to distinct brokers. Self-organization induces a high simi- larity among the subscriptions of neighbors brokers: this al- lows the CBR algorithm to works close to its best-case sce- narios creating thus the conditions for a reduction of TCP hops metric per event diffusion. Of course, the heuristic is network aware in the sense that it allows the establish-
ing/tearing down of a TCP connection between two brokers only if it does not harm network level performance in term of either TCP link latency or IP hops.
We performed an extensive simulation study, realized by implementing a full content-based pub/sub system en- hanced with the self-organization algorithm. Experimental results show clearly that, firstly, increasing the associativity produces a reduction in the TCP hops metric and, secondly, the self-organizing algorithm allows to reduce the overall application-level network traffic when the rate of event pub- lications is roughly ten times higher than subscriptions rate (a common situation for pub/sub systems).
The paper is structured as follows. Section 2 presents the background on content-based publish/subscribe and the motivation of our work. Section 3 describes the self-organization algorithm, discussing the concept of sub- scription similarity and presenting the cost metrics and the details of the self-organization algorithm. Sec- tion 4 presents experimental results. Section 5 compares our work with the related works in this research area. Fi- nally, Section 6 concludes the paper.
2. Content-Based Publish/Subscribe: a Sys-
tem Model
Events and subscriptions. In content-based pub/sub sub- scriptions and events are defined over a predetermined event schema, constituted by a set of n attributes, each defined through a name and a type, where the type can be a com- mon basic type such as integer, real or string. An event is a set of n values, one for each attribute, while a subscription is defined by using a set of constraints over the attributes.
Constraints depend on the type of attribute, but in general can be represented as range operators. Events and subscrip- tions can be graphically represented respectively as points and subsets in a n-dimensional event space. We say that an event matches a subscription if the point it represents falls inside the geometrical zone identified by the subscription.
Given the range constraints that can be included in subscrip- tions, a zone is shaped as an n-dimensional hyper-rectangle in the event space1.
Pub/sub model. A publish/subscribe event service is com- posed by a set of event brokers {B1, .., BN} interconnected through transport-level links which form an acyclic topol- ogy. In particular, each broker maintains a set of open con- nections (links) with other brokers (its neighbors), where li,j represents the link connecting brokers Bi and Bj and Nithe set of Bi’s neighbors. A broker can be contacted by clients, that, depending on their role, can be divided in sub- scribers or publishers. Publishers produce information by
1 For simplicity, as far as figures are concerned, we only consider a 2- dimensional event space.
firing events to one of the brokers, while subscribers ex- press their interests for specific events by issuing subscrip- tions to one of the brokers. Each broker stores locally these subscriptions and communicates with other brokers to prop- agate events. We define the zone of interest of a broker Bi, denoted Zi, as the union of all local subscriptions at Bi. Content-based Routing Protocol. In our model, routing of events follows the content-based routing algorithm (CBR) for acyclic peer-to-peer topologies introduced in SIENA [2]. Each broker maintains a routing table, in which each link of a broker is associated to the union of the zones of in- terest of all the brokers reachable from that link. When a new subscription S arrives at a broker Bi, if S is not a sub- set of Zi, Bipropagates S to the other brokers and adds S to Zi. When a broker Bj becomes aware of S through a mes- sage received from one of its incoming TCP links, namely l, it updates its routing table by adding S to the l’s entry in the routing table.
The CBR algorithm for event diffusion works as fol- lows: each time an event e is received by a broker Bieither from its local publishers or from a link, it matches e against all local subscriptions (matching phase) and then forwards e only through links which can lead to potential e’s sub- scribers (diffusion phase). In this case we say that Bi acts as a forwarder for e. Forwarding links are determined from the routing table, by matching the event against the entries contained in it. We denote as pure forwarder for e a broker which has no local subscriptions for e. A pure forwarder in- troduces one useless TCP hop on the event diffusion path and requires two useless matching operations, one for the local subscriptions and one for the forwarding step.
3. A Self-Organizing Algorithm
The basic idea of our approach is to rearrange the topol- ogy of the brokers network in order to directly connect through a TCP link brokers hosting similar subscriptions without affecting network-level metrics. Therefore, the self- organizing algorithm works in synergy with the content- based routing algorithm (i.e., it can read the CBR table whose data triggers the self-organization, and can modify the CBR tables after the self-organization).
The Cost Metric: TCP hops. The main target of the self- organizing algorithm is to do its best to avoid the pres- ence of pure forwarders per event diffusion. This is done through a reorganization of the network of brokers, that has the consequence of minimizing the TCP hops experienced by an event to reach all its intended destinations. Lower- ing the number of such TCP hops has a positive impact on the scalability of the system: each broker has to pro- cess a lower number of messages, both for the matching and for the forwarding operations. However, it is important
to remark that reducing the TCP hops per notification dif- fusion through a topology rearrangement could not neces- sarily lead to a same improvement on network level met- rics such as IP hops, latency and bandwidth, when the route followed by a notification changes. In other words, an ef- ficient topology configuration wrt TCP hops could exhibit very poor performance wrt, for example, IP hops. In Section 4.6, we describe how to address also underlying network metrics. Until that point, we describe a network-oblivious version of the self-organization algorithm, only accounting for the TCP hops metric.
Measuring Subscription Similarity: the Associativity. To measure the similarity between two subscriptions we use an heuristic based on the geometrical intersection of the re- spective hyper-rectangles. However, there could be cases in- deed where the difference between two zones can be much higher than their intersection. Therefore, we define a metric, denoted associativity, which takes the intersection among zones into account by normalizing this intersection against the overall size of one of the zones. More specifically, let Z and Z0be two zones, we define the associativity of Z with respect to Z0, denoted ASZ(Z0) as follows:
ASZ(Z0) .
= |Z|Z|T Z0|
This notion of associativity can be applied to broker’s zone of interests as well as to zones covered by a link. For example, let Biand Bjbe two brokers whose zones of inter- est are Ziand Zj respectively, then the associativity of Bi
with respect to Bjis defined as ASi(Bj) = ASZi(Zj). We also define the associativity of a broker Bi with its neigh- bors, denoted AS(Bi), as follows:
AS(Bi) .
=P
Bj∈NiASi(Bj)
We define the associativity of the pub/sub system as:
AS .
=
P
Bi∈{B1,...,BN }AS(Bi) N
4. Algorithm Behavior
The algorithm follows this basic simple heuristic: each broker B tries to rearrange the network in order to ob- tain an increment of its associativity AS(B) while not de- creasing AS. Practically this is realized as follows: a self- organization is triggered by a broker B when it detects (through the reading of the CBR tables) that there could be some other broker B0, not directly connected to B through a TCP link, that could increase its associativity. The aim of the self-organization is: (i) to connect B to B0 and (ii) to tear down a link in the path between B and B0in order to keep the topology of the network acyclic (a requirement of the CBR algorithm). While point (i) leads to an increment of AS(B), point (ii) can at the same time potentially lead to a decrease of AS. Therefore the algorithm does its best to se- lect the link in the path between B and B0that has the low- est associativity between the two brokers it connects. Self-
organization takes place only if it leads to an increase of AS. Increasing the associativity of the whole pub/sub sys- tem, intuitively means increasing the probability that two brokers with common interests get close to each other.
The algorithm can be split in four phases: triggering, tear-up link discovery, tear-down link selection, and recon- figuration which includes the CBR routing tables update.
During the description of the algorithm we will refer to a running example over the network of brokers depicted in Figures 1 and 2. The right side of Figure 1 shows the zones of interest of each broker, while the cloud indicates a part of the network that does not participate to the self-organization in the example.
4.1. Basic Notions
Maximum number of TCP links. Each broker has a max- imum number F of TCP links active at the same time (F is called the fan-out), and we denote as alB(with 0 ≤ alB <
F ) the number of links available at broker B. For simplic- ity we assume F equal at each broker.
Link weight. Each link li,jbetween two brokers Biand Bj
is associated with a weight w that reflects the associativity between the brokers:
w(li,j) = wi,j= ASi(Bj) + ASj(Bi)
The weight is used to measure the associativity that two brokers gain when a link is created between them and lose when the link is teared down. In figure 1 is shown the weight of each link2. The weight of a link is a measure of the num- ber of events that will pass through that link which are of interest to both brokers connected by it.
Hop sequence. An hop sequence is an or- dered set of pairs (broker id, weight) denoted as HS(B0, B`). More specifically, HS(B0, B`) ≡ {(B0, 0), (B1, w0,1), . . . , (Bi, wi−1,i), . . . (B`, w`−1,`)}
represents the path between B0 and B` with the associ- ated weights. Note that the weight associated to B0is 0 as it is the first broker on the path.
4.2. Triggering
The algorithm is triggered by a broker Bi when it de- tects the possibility of increasing its associativity. Specifi- cally, let Zibe the zone of broker Bi, before the arrival of a new subscription S, and Zi∗= Zi∪ S the Bi’s new zone of interest. The algorithm is triggered if the following pred- icate, namely the Activation Predicate, is verified:
AP : Zi∗⊃ Zi∧ ∃li,j: ASZ∗
i(Zli,j) > ASZi(Zli,j) For each li,j satisfying this predicate, a tearing up link discovery procedure, or simply discovery, is invoked along
2 This was obtained by applying the algorithm for the computation of associativity to the set of zones depicted in Figure 1
B0
B2
B3
B4
B1
B5
B6
B7
DREQ(Z0,S,(B0,0))
S
S Z0
Z7
Z5 Z6
Z3 Z2
Z1
Z0 Z1
Z3
Z2
Z5
Z6
Z7
DREQ(Z0,S,{(B0,0),(B1,0.42)})
DREQ(Z0,S,{(B0,0),(B1,0.05),(B5,0)})
DREQ(Z0,S,{(B0,0),(B1,0.42),(B5,0)}) DREQ(Z0,S,(B0,0))
DREQ(Z0,S,{(B0,0),(B2,1.15)}) 0.42
B8
Z4
0
0.57
0.36 1.22
Z4
1.15
0.26
Z0,8
Z8 0.36
Z8
Figure 1. Tear-up Link Discovery: DREQ Messages.
that link, as Bi suspects that behind it there could be a broker which can increase its associativity. The triggering phase starts k (with k ≥ 1) independent discovery proce- dures, where k is the number of links for which AP is satis- fied. Each of these procedures returns the broker B`with the highest associativity, with respect to Bi, that is located be- hind the link. Note that the value of Zli,jcan be easily read by looking-up Bi’s CBR routing table.
Considering the example in Figure 1, let us assume that broker B0, whose zone of interest is Z0, receives a new subscription S. The self-organization is triggered, by start- ing two independent discovery procedure, corresponding to links l0,1 and l0,2. Link l0,8 does not trigger the self- organization, as the associativity of Z0∗with respect to the zone it covers (Z0,8) is not higher than the associativity of Z0with respect to Z0,8.
4.3. Tear-Up Link Discovery
A single discovery procedure works as follows. A re- quest message DREQ is sent along the link li,j. The mes- sage piggybacks the following information: Zi, the new subscription S, and the hop sequence HS, initialized to {(Bi, 0)}.
When a broker Bj receives DREQ on its link l, it (i) computes ASZ∗
i(Zj)3, i.e., the associativity between the broker Biand Bj; (ii) updates HS by adding (Bj, wl),i.e., HS(Bi, Bj) = HS ∪ (Bj, wl); (iii) computes the follow- ing Forwarding Predicate:
FP : ∃lj,h6= l : ASZi∗(Zlj,h) > ASZi∗(Zj) The predicate indicates whenever there is the possibil- ity that a higher associativity can be discovered with a broker behind lj,h: if no links exist such that FP is sat- isfied, then a Discovery Reply message, DREP, is sent back to B along the path stored in HS. In this case, Bj can offer the highest associativity to Bi com- pared to the ones that could be provided by brokers behind
3 Recall that Zi∗= Zi∪ S
Bj. The DREP message contains the following informa- tion: ASZ∗i(ZBj), ZBj, alj, HS(Bi, Bj).
Referring to Figure 1, note that though B0 has a non- zero associativity with B4, the DREQ message is not for- warded to that broker because, as it is clear from the fig- ure, ASZ∗
0(Zl1,4) < ASZ∗
0(Z1), i.e., the forwarding predi- cate is not satisfied. For each lj,hsatisfying FP, Bjforwards the DREQ and then waits for the corresponding reply mes- sage DREP (ASZi∗(Z`), Z`, al`, HS(Bi, B`)).
When Bj receives the reply from each link, it com- putes the maximum among all the values of the associativity carried in the replies and its own associativity ASZ∗i(Zj), i.e. the associativity it can provide. Let as0 be the maxi- mum and B`0be the corresponding broker; Bjthen sends a DREP (as0, Z`0, al`0, HS(B, B`0)) to Bi. In Figure 2, bro- ker B5 after gathering DREP messages from B6 and B7, determines that the broker with higher associativity with B among itself, B6 and B7 is the latter. Then, it forwards to B1the DREP message received by B7.
B0
B2
B3
B4
B1
B5
B6
B7
DREP6(0.05,Z6,9,{(B0,0),(B1,0.42),(B5,0),(B6,0.36)}) DREP7(0.1,Z7,9,{(B0,0),(B1,0.42),(B5,0),(B7,0.57)})
DREP3(0.03,Z3,9,{(B0,0),(B2,1.15),(B3,0.26)}) DREP7
DREP7
DREP3
B8
0.42 0
0.57
0.36 1.15 1.22
0.26 0.36
Figure 2. Tear-up Link Discovery: DREP Mes- sages.
4.4. Tear-Down Link Selection
The aim of this phase is to select the link that has to be teared down during the reconfiguration phase. The pro- cedure is activated for each DREP message received by the broker Bi that started the self-organization and returns a tear-down candidate link denoted as ltd. If no links ex- ist that can be deleted, ltd= N U LL.
A single selection works as follows: let DREP be the reply to the the DREQ message sent along link l. The re- ply contains the identifier B` of the broker behind l with the highest similarity with Bi, together with the path stored in HS from Bi to B`. Let us denote the link to be po- tentially teared-up between Bi and B` as ltu. Clearly, if al` = 0 ∧ ali = 0 the link ltucannot be created and thus ltd= N U LL. Otherwise, we have two cases:
1. ali > 0 ∧ al` > 0: In this case both Bi and B` have available connections and thus they can establish the link ltu. In this case, ltdis the link with the minimum weight in HS(Bi, B`).
2. al` = 0, ali > 0 (resp. ali= 0, al`> 0): in this case ltd
is the link that connects B`−1 to B`(resp. B0 to B1), i.e.
ltd= l`−1,`(resp. ltd= l0,1); in this way the constraints on the fan-outs are satisfied.
The next phase of the algorithm (i.e, the reconfiguration) takes place only if ltd6= N U LL and w(ltu) − w(ltd) > 0.
In other words a reconfiguration occurs only if ltu is ex- pected to be crossed by a number of events, which inter- est both brokers directly connected to ltu, greater than the ones which cross ltd. This is the heuristic we use in order to ensure that doing the self-organization, the associativity of the whole pub/sub system, AS (see Section 3), does not de- crease.
Considering Figure 2, the convergecast phase of DREP messages to B0selects B7 as the candidate to establish a link (i.e., ltu) with B0, then the algorithm selects l1,5as ltd. The reconfiguration will happen as w(l0,7) is greater than w(l1,5).
4.5. Reconfiguration
Let Biand B`be the two brokers to be connected by ltu
and Bpand Bq be the brokers connected by ltdin the path stored in HS(Bi, B`). We have to avoid that during the tear down of the link ltd, other links in HS(Bi, B`) are teared down by concurrent executions of the self-organization al- gorithm. Otherwise, the network of brokers might partition.
Therefore there is the need of a locking mechanism to en- sure that there is only one tear down operation at a time along the path from Bito B`.
This mechanism works as follows: Bi sends a LOCK message along the path towards B`. A generic broker B in that path executes the following algorithm:
• when receiving a LOCK message: if B is involved in other concurrent reconfiguration phases on the same link it received the LOCK message from, it replies with a NACK message. Otherwise we have two cases:
1. if B = B`, B sends an ACK message to the next node towards Bi;
2. if B 6= B`, B sends a LOCK message to the next node towards B`;
• when receiving an ACK message: B forwards the ACK message to next node towards Bi;
• when receiving a NACK message: B forwards the NACK message to next node towards Biand removes the lock.
Previous algorithm is depicted in Figure 3.a when con- sidering the path from B0to B7of Figure 1 and no concur- rent reconfigurations on links in that path occurs.
B0 B1 B5 B7
B0 B1 B5 B7
lock lock lock ack ack
ack
B0 B1 B5 B7
close close
unlock unlock
a)
b)
c)
Figure 3. Routing Tables Update.
Once the path is locked, B0sends a CLOSE message to Bq along the path to B`identifying the link that has to be teared down, namely ltd4. Figure 1.b shows this operation for the path from B0to B7. At this point the link ltdis ac- tually teared down.
Finally, the routing tables have to be updated and the locks on the path have to be removed. This operation starts from Bpand Bq and follows the reverse path to Biand B`
respectively by using UNLOCK messages as shown in Fig- ure 3.c with respect to the path from B0 to B7. Once the UNLOCK message arrives at Bi, the link ltucan be safely teared up (l0,7in Figure 3.c).
4.6. Addressing Network Awareness
We take network-level into account performance by fol- lowing this simple principle: reconfiguration is enabled only among those brokers whose network-level distance with the
4 This information could also be piggybacked onto ACK messages of previous algorithm. For simplicity, we describe the operation using separate explicit CLOSE messages.
source broker is less than a reference value d. Network dis- tance can be measured indifferently with any metric, either IP hops or latency or bandwidth, depending on the specific requirements of the application.
Adding network awareness brings several modifications to the tear-up and tear-down phases. Each broker involved in the tear-up phase will probe its distance from the source of the self-organization and verify if this distance is higher than d. In this case the broker will simply avoid to propose itself as a candidate, letting the discovery continue as in the ordinary case. In the tear down phase, the link to be cut is the one that (i) has associativity lower than the link se- lected to be teared up and (ii) has the highest distance from the source of the self-organization.
The performance obviously depends from the choice of d. If it is too high, the self-organization algorithm will find brokers that are far in the network, possibly spoiling the ini- tial proximity of broker, if any. If d is too low, the algorithm will choose the new neighbor inside a restricted set of bro- kers, hardly finding one with a good associativity, then, the subsequent reconfiguration will have a negligible effect on the TCP hops metric. In particular if d is equal to zero we get a pure CBR routing. If d = ∞ then we do not take into account network-level metrics.
5. Simulation Study
In the simulation study we observe a prototype pub/sub system subject to a predefined stimuli (e.g., publishing of notifications, issuing of subscriptions, etc.) and compare its performance obtained using a SIENA-like CBR algorithm with and without the self-organization. The values reported in the plots are the mean of 5 independent runs; the confi- dence interval is not shown as its value is always lower than 2% of the mean. The prototype is integrated within J-Sim [5] to simulate the behavior of large networks of brokers.
Each node in our simulatons hosts components that simu- lates the TCP/IP stack, starting from the network level.
We simulate a network composed of N network nodes, with one broker running on each node. The physical-level and application-level topologies are independent (i.e. two nodes connected at physical-level does not necessarily host two brokers connected at application-level). In general, the physical topology is generated as a flat random graph, except where differently indicated. The application-level topology with k + 1 brokers is obtained from a k-brokers topology by starting a new broker process on a node and connecting it to one of the brokers inside the network; this broker is selected randomly. The network-level topology has been generated with the GT-ITM tool [14] and follows the Trasnsit-Stub model.
In the rest of this section, if not differently specified, we consider N = 100 brokers, each with a maximum fan-out
degree F = 10. A broker can have both publishers and sub- scribers attached to it; however, we do not model explicitly the number of attached clients. Simulation scenarios are se- quences of subscriptions changes and notification publica- tions, over a bi-dimensional space with two numerical at- tributes. Each subscription is a rectangle characterized by the center, generated from a Zipf distribution, and the ex- tension over the two dimensions, generated from a uniform distribution. This method simulates the aggregation of sub- scriptions around specific points in the space, that occurs in most real-world applications [13]. Notifications are gener- ated using an uniform distribution over the space.
Publications or subscription changes are injected in ran- domly chosen brokers. The ratio between the number of publications and the number of subscriptions is denoted as R, i.e. a new subscription change occurs every R pub- lish operations. R is a single traffic parameter enclosing the contributions due to the two independent traffic sources of pub/sub systems, i.e. publishers and subscribers. We always consider R > 1, that is publications are injected more fre- quently than subscriptions. This is a common, reasonable assumption in pub/sub systems.
Results are organized as follows: first we evaluate the application-level routing performance (number of TCP hops per event notification) and the associativity metric of the system in the case of pure CBR (d = 0) and CBR with self-organization (SOCBR), without taking into account network-level metrics (i.e., d = ∞). Then, in a specific set- ting, we provide an estimation of a value of d. Finally, we analyze the number of messages per operations (publish or subscribe) exchanged in the system and the average latency of publications.
0 5 10 15 20 25 30 35
255 260 265 270 275 280 285 290 295 300
Subscriptions
TCP hops
without self-organization with self-organization no pure forwarders
Figure 4. Number of TCP hops per notifica- tion as a function of subscriptions for R = 100 : 1.
Routing Performance The main effect we expect from self-organization is a reduction in the number of TCP hops required per notification. Figure 4 shows the average num- ber of TCP hops per notification obtained with d = ∞ and d = 0 (no self-organization). These two values are com- pared with the ideal value obtained when no pure forwarder brokers are involved in the notification routing: in this case each notification is delivered to each recipient in a single TCP hop. This is obviously an ideal situation that repre- sents the minimum number of brokers involved in routing, but it gives a clear reference value for the improvement ob- tained by applying the self-organization algorithm: due to the self-organization the number of pure forwarders is re- duced by a 70% obtaining an average value that is very close to the minimum. Values for this plot are obtained for R = 100 : 1 in a window of 50 subscriptions. Sliding this window does not lead to different results.
0 0,2 0,4 0,6 0,8 1 1,2 1,4 1,6
0 100 200 300 400 500 600 700 800 900 1000
Subscriptions
AS
SOCBR with d=∞ SOCBR with d=0ms
Figure 5.ASvs. subscriptions.
The improvement in the TCP hops follows from the en- hancement of the associativity metric. Figure 5 shows the associativity as a function of the number of subscriptions in the system, with d = ∞ and d = 0. When self-organization is not used, the associativity at a broker B increases anyway because it is higher the probability that B’s neighbors con- tain subscriptions that are “similar”. This is a kind of phys- iological increasing, due to the fixed number of brokers in the system. However, if self-organization is present, a high associativity value is achieved very quickly.
Estimation of d. The value of d greatly affect the number of reconfiguration executed by the SOCBR algorithm, there- fore it is necessary to define a correct value for it in order to obtain a low latency expected for events notification. Figure 6 shows the average latency experienced per notification.
The graph shows how the latency expected for event notifi- cation raises as we increase the distance bound d: due to the
0,0 0,5 1,0 1,5 2,0 2,5 3,0 3,5 4,0 4,5 5,0
Average latency per pub (sec.)
SOCBR with d=0ns SOCBR with d=50ms SOCBR with d=100ms SOCBR with d=150ms SOCBR with d=∞
Figure 6. Average latency per notification.
loosen distance bound, the SOCBR algorithm tends to con- nect brokers with high associativity also if the link connect- ing them shows an higher latency, increasing, as a conse- quence, the total latency experienced during events notifi- cation. This result shows how, for our simulation scenarios, the value d = 100ms lets the SOCBR works without affect- ing too much the notification latency.
15 20 25 30 35 40 45
10 20 30 40 50 60 70 80 90 100
pub/sub ratio
TCP hops
SOCBR with d=0ms SOCBR with d=100ms SOCBR with d=∞
Figure 7. Number of messages per operation (publish or subscribe) as a function of the pub/sub ratioR
Average number of self-organization messages required per subscription. Figure 7 reports the average number of messages per operation (either publication or subscription) against the pub/sub ratio R. Such messages include all the messages generated by the system for notification diffusion, subscription routing and self-organization. For a ratio as low
as R = 10 : 1 the self-organization cost, depicted in the d = ∞ curve, is not outweighed by its benefits. As the ra- tio increases, the cost decreases accordingly, quickly reach- ing a reduction in the overall number of messages of about 30% with respect to the case when no self-organization is performed. The break-even point lays at about R = 12 : 1.
We stress the fact that this ratio is far below the common working conditions assumed for pub/sub systems. The fig- ure shows how the self-organizing algorithm can help the CBR algorithm to scale with respect to increasing load due to publications. In other words, when the publication rate grows, the number of TCP hops per notification decreases.
Let us note that using d = 100ms the break-even with re- spect to the pure CBR moves to a value of about R = 30 : 1, but for R = 100 : 1 the gain over CBR is still a 30% less.
0,0 0,5 1,0 1,5 2,0 2,5 3,0 3,5 4,0 4,5 5,0
10 20 30 40 50 60 70 80 90 100
pub/sub ratio
Average Latency x pub (sec.)
SOCBR with d=0ms SOCBR with d=100ms SOCBR with d=∞
Figure 8. Average latency per notification.
Notification Latency. Figure 8 shows that the notification latency experienced by SOCBR with d = 100ms is almost equal to the one obtained by a pure CBR, while SOCBR with d = 1 introduces a 50% overhead. In summary, cross- ing experimental results shown in Figure 8 and Figure 7, it clearly comes out that by limiting the scope of discovery to a reasonable value (in terms of latency), SOCBR achieves significant improvement on the TCP hop metrics with re- spect to a pure CBR without affecting the notification la- tency.
6. Related Work
Cugola et al. [4], presented an algorithm for topologi- cal reconfiguration in content-based publish/subscribe. Au- thors assume that some link may disappear and others ap- pear elsewhere, due to changes in the underlying connec- tivity (this is the case, for example, of mobile ad-hoc net- works). “Reconfiguration” in this case means fixing routing
tables entries no longer valid after the topology change. In contrast, in our approach we induce a reconfiguration to cre- ate more favorable conditions for event routing.
Peer-to-peer overlay network infrastructures, such as Chord [11], Pastry [10] and Tapestry [16] exploits self-reconfiguration capability for fault-tolerant rout- ing and for adjusting routing paths with respect to metrics of the underlying network.
Our approach to reconfiguration is specific for pub/sub applications and operates on the same level as content-based routing. In other words, rather than basing the reconfigura- tion on metrics of the underlying network, we start from an application-level routing algorithm and add a dynamic be- havior that relies on the algorithm’s own information (i.e., the routing tables) to improve its performance.
Another approach to route events in pub/sub systems, based on event space partitioning, has been presented in [13]; this method is actually limited as there is no way to change dinamically the partitioning of the space.
7. Conclusions
Providing a pub/sub system with self-organizing capabil- ity is a novel approach to the enhancement of the scalabil- ity of systems with a low physical locality. In this paper we introduced a self-organizing algorithm that works in syn- ergy with a content-based routing (CBR) protocol. This al- gorithm is based on a dynamic network of brokers and tries to self-arrange the network so that brokers managing sub- scriptions with high similarity will be as close as possible in the network graph. This means that similar subscriptions will be located on the same part of the network graph and this creates the conditions for the CBR protocol to work at its best, thus, reducing the number of TCP hops per event diffusion.
The simulation study confirms that limiting the scope of neighbor discovery to a reasonable value, (in terms of net- work latency), the self organization algorithm achieves sig- nificant improvement on the TCP hop metrics with respect to a pure CBR without affecting the network latency of no- tifications. Moreover, the overhead of the self-organization can be amortized, with respect to the usage of the CBR algo- rithm alone, only if there are at least, on the average, more than 12 notifications for each subscription (this is actually a daylife working condition for a pub/sub system).
References
[1] G. Banavar, T. Chandra, B. Mukherjee, J. Nagarajarao, R. Strom, and D. Sturman. An Efficient Multicast Protocol for Content-based Publish-Subscribe Systems. In Proceed- ings of International Conference on Distributed Computing Systems, 1999.
[2] A. Carzaniga, D. Rosenblum, and A. Wolf. Design and Eval- uation of a Wide-Area Notification Service. ACM Transac- tions on Computer Systems, 3(19):332–383, Aug 2001.
[3] G. Cugola, E. D. Nitto, and A. Fuggetta. The JEDI Event- Based Infrastructure and its Applications to the Development of the OPSS WFMS. IEEE Transactions on Software Engi- neering, 27(9):827–850, September 1998.
[4] A. L. M. G. P. Picco, G. Cugola. Efficient content-based event dispatching in the presence of topological reconfigura- tion. In 23rd International Conference on Distributed Com- puting Systems (ICDCS 2003), 19-22 May 2003, Providence, RI, USA, pages 234–243, 2003.
[5] J-Sim. http://www.j-sim.org, 2003.
[6] G. Muhl. Large-Scale Content-Based Publish/Subscribe Sys- tems. Phd thesis, Technical University of Darmstadt, 2002.
[7] B. Oki, M. Pfluegel, A. Siegel, and D. Skeen. The Infor- mation Bus - An Architecture for Extensive Distributed Sys- tems. In Proceedings of the 1993 ACM Symposium on Oper- ating Systems Principles, December 1993.
[8] P. Pietzuch and J. Bacon. Hermes: A Distributed Event- Based Middleware Architecture. In Proceedings of the 1st International Workshop on Distributed Event-Based Systems (DEBS’02), 2002.
[9] A. Rowston, A. Kermarrec, M. Castro, and P. Druschel.
SCRIBE: The Design of a Large-Scale Notification Infras- tructure. In 3rd International Workshop on Networked Group Communication (NGC2001), 2001.
[10] A. Rowstron and P. Druschel. Pastry: Scalable, Decentral- ized Object Location and Routing for Large-Scale Peer-to- Peer Systems. In Proceedings of International Conference on Distributed Systems Platforms (Middleware), 2001.
[11] I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Bal- akrishnan. Chord: A Scalable Peer-to-Peer Lookup Ser- vice for Internet Applications. In Proceedings of ACM SIG- COMM, 2001.
[12] W. W. Terpstra, S. Behnel, L. Fiege, A. Zeidler, and A. P.
Buchmann. A Peer-to-Peer Approach to Content-Based Pub- lish/Subscribe. In Proceedings of the 2nd International Workshop on Distributed Event-Based Systems (DEBS’03), 2003.
[13] Y. Wang, L. Qiu, D. Achlioptas, G. Das, P. Larson, and H. J.
Wang. Subscription Partitioning and Routing in Content- based Publish/Subscribe Networks. In 16th International Symposium on DIStributed Computing (DISC’02), October 2002.
[14] E. W. Zegura, K. L. Calvert, and S. Bhattacharjee. How to model an internetwork. In IEEE Infocom, volume 2, pages 594–602, 1996.
[15] S. Q. Zhuang, B. Y. Zhao, A. D. Joseph, R. Katz, and J. Ku- biatowicz. Bayeux: An Architecture for Scalable and Fault- tolerant Wide-area Data Dissemination . In 11th Int. Work- shop on Network and Operating Systems Support for Digital Audio and Video, 2001.
[16] S. Q. Zhuang, B. Y. Zhao, A. D. Joseph, R. Katz, and J. Kubiatowicz. Tapestry: An Infrastructure for Fault- Tolerant Wide-Area Location and Routing. Technical Re- port UCB/CSD-01-1141, University of California at Berke- ley, Computer Science Division, April 2001.
