Georgios Bouloukakis

Ioannis Moscholios

Nikolaos Georgantas
email: nikolaos.georgantas@inria.fr

Probabilistic Event Dropping for Intermittently Connected Subscribers over Pub/Sub Systems

Keywords: Subscribe Middleware, Event Dropping, Response Time, Queueing Networks

Internet of Things (IoT) aim to leverage data from multiple sensors, actuators and devices for improving peoples' daily life and safety. Multiple data sources must be integrated, analyzed from the corresponding application and notify interested stakeholders. To support the data exchange between data sources and stakeholders, the publish/subscribe (pub/sub) middleware is often employed. Pub/sub provides additional mechanisms such as reliable messaging, event dropping, prioritization, etc. The event dropping mechanism is often used to satisfy Quality of Service (QoS) requirements and ensure system stability. To enable event dropping, basic approaches apply finite buffers or data validity periods and more sophisticated ones are informationaware. In this paper, we introduce a pub/sub mechanism for probabilistic event dropping by considering the stakeholders' intermittent connectivity and QoS requirements. We model the pub/sub middleware as a network of queues which includes a novel ON/OFF queueing model that enables the definition of join probabilities. We validate our analytical model via simulation and compare our mechanism with existing ones. Experimental results can be used as insights for developing hybrid dropping mechanisms.

I. INTRODUCTION

Internet of Things (IoT) devices are prevalent in homes, offices, and community spaces such as universities, hospitals, airports, etc [START_REF] Zanella | Internet of things for smart cities[END_REF]. By exploiting the information they gather there are new opportunities to build applications that improve peoples' quality of life. However, IoT devices are often mobile, low-powered and inexpensive which makes them vulnerable to system changes. These changes may occur due to a variety of problems including faulty components, inaccurate sensing, intermittent connectivity and software bugs [START_REF] Su | Decentralized fault tolerance mechanism for intelligent iot/m2m middleware[END_REF].

Such a system behavior prevents the development of resilient IoT applications, especially those that carry missioncritical information to improve public safety [START_REF]Community Seismic Network[END_REF], [START_REF] Cochran | A novel strongmotion seismic network for community participation in earthquake monitoring[END_REF]. For example, during a fire inside a building an emergency dispatch process must be activated. This may result to sending a team of Fire Fighters (FFs) to the building. Data (e.g., high temperature or smoke levels) derived from the building's IoT devices along with static information (e.g, building floor plans) can be leveraged by stakeholders (e.g., FFs, residents) to ensure their safety. However, the key challenge for this unreliable, partially available and congested network environment is to deliver data in a timely manner [START_REF] Hamins | NIST Special Publication 1191 Research Roadmap for Smart Fire Fighting[END_REF].

To manage data flows of IoT applications, an underlying data exchange middleware can be leveraged [START_REF] Ngu | Iot middleware: A survey on issues and enabling technologies[END_REF]. Middleware systems often follow the Publish/Subscribe (pub/sub) interaction paradigm, which supports space and time decoupling between peers [START_REF] Eugster | The many faces of publish/subscribe[END_REF]. This is particularly needed in the case of mobile IoT systems, where intermittent connected peers (e.g., FFs) interact with each other via an intermediary broker [START_REF] Pivotal | RabbitMQ[END_REF]. Pub/sub middleware systems provide multiple features to support data exchange such as reliable messaging, message prioritization, load balancing, message dropping, and others [START_REF] Esposito | Reliable and timely event notification for publish/subscribe services over the internet[END_REF]- [START_REF] John | A survey of distributed message broker queues[END_REF]. These features can be utilized to ensure a certain level of Quality of Service (QoS) for IoT applications. For instance, IoT applications evolve over time: publication rates increase, the network may be congested, the bandwidth may become limited, and peers often connect/disconnect from the network. Hence, to enable the broker's buffer stability and prevent high delays, the feature of message dropping is highly useful.

Several existing efforts support message dropping. In particular, message brokers such as RabbitMQ [START_REF] Pivotal | RabbitMQ[END_REF], ActiveMQ [START_REF] Snyder | ActiveMQ in action[END_REF], mosquitto [START_REF] Light | Mosquitto-an open source mqtt v3. 1 broker[END_REF], set a maximum queue length and drop messages that arrive when the queue is full [START_REF] John | A survey of distributed message broker queues[END_REF]. To ensure message timeliness, message losses occur due to the validity/availability periods that can be assigned to every message through pub/sub protocols and APIs (e.g., the JMS API [START_REF]Sun Microsystems JMS Specifications[END_REF]). More sophisticated approaches support semi-probabilistic delivery [START_REF] Costa | Publish-subscribe on sensor networks: A semi-probabilistic approach[END_REF] or take into account subscribers' preferences [START_REF] Diallo | Leveraging caching for internet-scale content-based publish/subscribe networks[END_REF], [START_REF] Pripužić | Top-k/w publish/subscribe: finding k most relevant publications in sliding time window w[END_REF], [START_REF] Salehi | Popsub: Improving resource utilization in distributed content-based publish/subscribe systems[END_REF] to: (i) satisfy subscribers based on the available bandwidth usage; (ii) deliver the most relevant publications published within a time window; or (iii) deliver most popular publications. In our recent work, we introduced FireDeX [START_REF] Benson | Firedex: a prioritized iot data exchange middleware for emergency response[END_REF], a middleware architecture that enables message prioritization and dropping by considering subscribers' situational awareness requirements and resource constraints.

In this paper, we introduce a pub/sub architecture enabled with probabilistic message dropping. In particular, our pub/sub broker drops messages by considering resource constraints, the subscribers' connectivity and response time requirements. We model the pub/sub broker as a network of queues where messages are transmitted to each subscriber through a dedicated ON/OFF probabilistic queueing model -ON/OFF corre-

II. SYSTEM MODEL

In this section we provide a formal model of our data exchange middleware architecture that supports probabilistic message dropping. Our middleware builds over the pub/sub interaction paradigm and the probabilistic dropping is performed at the broker component.

A. Pub/Sub Interaction Paradigm

The Pub/Sub interaction paradigm, is commonly used for content broadcasting/feeds. Middleware protocols such as MQTT [START_REF] Banks | Mqtt version 3.1. 1[END_REF] and AMQP [START_REF] Godfrey | Oasis advanced message queuing protocol (amqp) version 1.0; oasis standard[END_REF], as well as tools and technologies such as RabbitMQ [START_REF] Pivotal | RabbitMQ[END_REF] and JMS [START_REF]Sun Microsystems JMS Specifications[END_REF] follow the pub/sub paradigm [START_REF] Eugster | The many faces of publish/subscribe[END_REF]. In pub/sub, multiple peers interact via an intermediate broker. Publishers produce events (or messages) characterized by a specific topic to the broker. Subscribers subscribe their interest for specific topics to the broker, who maintains an up-to-date list of subscriptions. The broker matches received events with subscriptions and delivers a copy of each event to each interested subscriber.

B. Pub/Sub Formal Model

To formulate the probabilistic pub/sub middleware we rely on our previous experience [START_REF] Benson | Firedex: a prioritized iot data exchange middleware for emergency response[END_REF], [START_REF] Bouloukakis | Timeliness evaluation of intermittent mobile connectivity over pub/sub systems[END_REF]- [START_REF] Bouloukakis | Queueing network modeling patterns for reliable and unreliable publish/subscribe protocols[END_REF] where we model pub/sub systems with different characteristics as network of queues. In this work, we do not provide the detailed modeling of our pub/sub middleware (can be found in [START_REF] Bouloukakis | Timeliness evaluation of intermittent mobile connectivity over pub/sub systems[END_REF], [START_REF] Gomes | Qos-aware resource allocation for mobile iot pub/sub systems[END_REF])

ƌŽŬĞƌ ŶŽĚĞ ; Ϳ DͬDͬϭ ߤ ݅݊ ݏ ߤ ݐݑ ߣ ܾݑݏ݊ ݏ ݅ ߣ ݕ݂݅ݐ݊ ݏ ݅  1 WƌŽďĂďŝůŝƐƚŝĐ KEͬK&& ݏଵ ߤ ݐݑ ݏ 1 ߣ ݕ݂݅ݐ݊ ܾ ݏ 1 ݏ 1 ߣ ܾݑݏ ݏ ݅ ߣ ܾݑݏ ݎ 1 ݎ ݆  ݅  1 , ݒ 1 ߣ ܾݑ  ݅ , ݒ ݇ ߣ ܾݑ ͙͘͘ ܵ ܾ ݍ ݅݊ ݍ ݐݑ ܾݎ ݂݂/݊ Ͳ ߣ ݅݊ ܾ ݏ 1 ߞ ݏ ݅ ߞ
Fig. 1: Pub/Sub formal model. but only the added characteristics for enabling probabilistic dropping. Refer to Table I for the notations used throughout this section.

As depicted in Fig. 1, every publisher p i publishes events to broker node b at multiple topics (e.g., "smoke") with rate λ pub pi,v k based on Poisson process. On the other side, a subscriber s i subscribes using a subscription r j to b for receiving events (matching r j ) with rate λ sub si . Published events arrive with rate λ in b to b's input M/M/1 queue (q in ) to be processed with rate µ in . Events not matching b's subscriptions are dropped with rate λ nosub and events matching s i 's subscriptions are forwarded to s i 's output queue (q out-prob on/of f ) with rate λ notif y si . Subsequently, events join s i 's output queue with probability ζ si only when s i is not connected to b. Hence, the delivery rate of events for each subscriber s i can be estimated by taking into account s i 's join probability ζ si and its matched events with rate λ notif y si . Finally, events inserted to the output queue during s i 's disconnection periods are buffered because the queueing server is not active. When s i re-connects to the broker, events are served with rate µ out si which represents the network transmission delay between b and s i . Let ∆ si be the average end-to-end response time of events matching s i 's subscriptions from the moment they are published until s i receives them. To estimate ∆ si , we must estimate the delay of events passing through the broker's input and output queues. This is given by:

∆ si = ∆ q in + ∆ q prob on/of f (1)
where ∆ q in and ∆ q prob on/of f are the mean response times for the queues q prob on/of f and q in , respectively. To estimate ∆ q in we leverage existing solutions of the literature [START_REF] Gross | Fundamentals of queueing theory[END_REF]. However, ∆ q prob on/of f cannot be estimated in a similar way; we must take into account the subscribers intermittent connectivity, the join probability during disconnections, as well as the network transmission delay between b and s i .

C. Probabilistic Event Dropping

In this paper, our pub/sub broker estimates the join probability ζ si per subscriber s i , by taking into account the subscriber's connected and disconnected periods T si ON and T si OFF , and its end-to-end response time threshold ∆ T hr si . The latter requires that all events matching s i 's subscriptions must be delivered within ∆ T hr si . This threshold is given to the broker through a subscription which is defined as a tuple r j = (s i , ∆ T hr si ). Note that ∆ T hr si is constant for any r j of s i and it is equivalent to the end-to-end response time ∆ si defined in [START_REF] Zanella | Internet of things for smart cities[END_REF] The above behavior can be modeled as a probabilistic ON/OFF queue (output queue inside the broker -see Fig. 1), which we will analyze in the next section to derive its performance metrics. Note that our probabilistic mechanism drops all incoming events during disconnections -the event's importance is not considered. Such information awareness is handled in our previous work [START_REF] Benson | Firedex: a prioritized iot data exchange middleware for emergency response[END_REF]. III. PROBABILISTIC ON/OFF MODEL An ON/OFF queue represents a system having a single server as depicted in Fig. 2. The server supports an exponentially distributed service rate denoted as µ > 0 (time needed to process an event). The service station operates under the First-Come-First-Serve (FCFS) queueing policy. We also assume that the server is subject to an ON/OFF procedure. That said, it remains in the ON-state for an exponentially distributed time with parameter θ ON , during which it serves events, if any. Let T ON be the time the server is ON -then T ON = 1/θ ON . When this time expires, the server enters the OFF-state during which it stops working for an exponentially distributed time period with rate θ OFF . Let T OFF be the time the server is OFF -then T OFF = 1/θ OFF .

Events arrive in the system according to a Poisson process with rate λ > 0 and if the server is online (ON) then events are placed in a queue waiting to be "served". Otherwise, if the server is offline (OFF) then events join the queue with probability ζ or abandon the system with probability 1 -ζ.

To model the performance of a component that sends events according to the above connectivity, we introduce the "probabilistic ON/OFF queue". A q prob on/of f queue is defined as:

q prob on/of f = (λ, ζ, µ, λ on/of f out , T ON , T OFF ) (2)
where λ is the input rate of events to the queue, ζ is the probability of joining the queue, λ on/of f out is the output rate of events and µ is the service rate for the transmission of events, if any, during T ON . The output process is intermittent, since no events exit the queue during T OFF intervals. Without loss of generality, we assume that: if T ON expires and there is an in-service event, the server interrupts its processing and then continues in the next T ON period.

It is worth noting that if ζ = 1, then all events join the system during OFF periods. This is equivalent with the ON/OFF model presented in [START_REF] Bouloukakis | Performance modeling of the middleware overlay infrastructure of mobile things[END_REF]. Hence, the probabilistic ON/OFF model generalizes the ON/OFF model.

A. The analytical model

The proposed model is described as a 2D Markov chain whose state space diagram is presented in Fig. 3. The states (n,1) and (n,0) refer to the case where there are n events in the system (queue + server) and the server is ON and OFF, respectively. Note that, if the server is always ON then we have an M/M/1 queue and the upper part of the 2D Markov chain does not exist. Based on this chain, the steady state probabilities P n,k (n=0,1,... while k=0,1) of the ON/OFF queue do not have a product-form solution since there are no backward transitions between the states (n,0) and (n-1, 0). This is anticipated since events are not serviced when the server is OFF.

According to Fig. 3, we can write:

θ OFF ∞ n=0 P n,0 = θ ON ∞ n=0 P n,1 (3)
Equation ( 3), based on the normalization condition ∞ n=0 1 k=0 P n,k = 1, leads to the determination of the probability of when the server is ON (see ( 4)) or OFF (see [START_REF] Hamins | NIST Special Publication 1191 Research Roadmap for Smart Fire Fighting[END_REF]), respectively:

P server ON = ∞ n=0 P n,1 = θ OFF θ ON + θ OFF (4)
P server OF F = ∞ n=0 P n,0 = θ ON θ ON + θ OFF (5)
The global balance (GB) equations of the 2D Markov chain are (rate into state (n,k) -rate out of state (n, k) = 0): State(0,0) : θ ON P 0,1 -(λζ + θ OFF )P 0,0 = 0 State(0,1) : The transition (intensity) matrix, Q, of this 2D Markov chain is an infinite block tridiagonal matrix whose structure is repetitive. More precisely, Q can be written in the form:

θ OFF P 0,0 + µP 1,1 -(λ + θ ON )P 0,1 = 0 State(1,0) : λζP 0,0 + θ ON P 1,1 -(λζ + θ OFF )P 1,0 = 0 State(1,1) : λP 0,1 + µP 2,1 + θ OFF P 1,0 -(λ + µ + θ ON )P 1,1 = 0 ...
Q =            B 00 C 0 0 0 . . . C 2 C 1 C 0 0 . . . 0 C 2 C 1 C 0 . . . 0 0 C 2 C 1 . . . . . . . . . . . . . . . . . .            (6)
where submatrices B 00 , C 0 , C 1 and C 2 are square 2x2 matrices with the following form:

B 00 =   -(λζ + θ OFF ) θ OFF θ ON -(λ + θ ON )   (7)
C 0 =   λζ 0 0 λ   (8) 0,0 ͙͘͘ ͙͘͘ ߣ ߞ 1,0 2,0 3,0 3,1 2,1 1,1 0,1 ߣ ߣ ߣ ߣ ߤ ߤ ߤ ߤ ݊ െ 1,0 ݊, 0 ݊, 1 ߣ ߣ ߤ ߤ ݊ 1,0 ݊ െ 1,1 ݊ 1,1 ͙͘͘ ƐƚĂƚĞ KE ƐƚĂƚĞ K&& ߣ ߞ ߣ ߞ ߣ ߞ ߣ ߞ ߣ ߞ ߠ ܱܰ ߠ ܨܨܱ ߠ ܱܰ ߠ ܨܨܱ ߠ ܱܰ ߠ ܨܨܱ ߠ ܱܰ ߠ ܨܨܱ ߠ ܱܰ ߠ ܨܨܱ ߠ ܱܰ ߠ ܨܨܱ ߠ ܱܰ ߠ ܨܨܱ ͙͘͘ Fig. 3: 2D Markov Chain. C 1 =   -(λζ + θ OFF ) θ OFF θ ON -(λ + µ + θ ON )   (9)
C 2 =   0 0 0 µ   (10)
A Markov chain whose transition matrix has the structure of ( 6) belongs to the class of quasi-birth death processes and can be efficiently solved using the matrix-geometric method [START_REF] Neuts | Matrix-geometric solutions in stochastic models: an algorithmic approach[END_REF]. Based on (6), the system of GB equations is described by:

P Q = 0 ( 11
)
where P = [P 0 , P 1 , ..., P n , ...], P n = [P n,0 , P n,1 ] and P n,k is the probability that the system is in state (n, k) at steady state.

Based on [START_REF]Sun Microsystems JMS Specifications[END_REF] we can write the following equations:

P 0 B 00 + P 1 C 2 = 0, for n = 0 (12a) P n-1 C 0 + P n C 1 + P n+1 C 2 = 0, for n ≥ 1 (12b)
The steady-state probability distribution, P n , is matrixgeometric in form, i.e.:

P n = P 0 R n for n = 1, 2, ..., (13)
where R is a constant rate matrix. Thus, the GB equations (12a) and (12b) can be written via (13) as follows:

P 0 B 00 + P 0 RC 2 = 0, for n = 0 (14a)

P 0 R n-1 C 0 + P 0 R n C 1 + P 0 R n+1 C 2 = 0 or P 0 R n-1 C 0 + RC 1 + R 2 C 2 = 0, for n ≥ 1 (14b)
To determine the rate matrix R we follow the logarithmic reduction process proposed in [START_REF] Latouche | Introduction to matrix analytic methods in stochastic modeling[END_REF]. Latouce and Ramaswami introduce a rate matrix G that satisfies:

C 2 + C 1 G + C 0 G 2 = 0 (15)
Having determined G we can compute R via the formula:

R = -C 0 (C 1 + C 0 G) -1 (16)
In our case, we may express C 2 via a column vector v and a row vector u as follows:

C 2 =   0 0 0 µ   =   0 µ   0 1 = v • u (17)
Then:

G = 1 • u =   1 1   0 1 =   0 1 0 1   (18)
Equation ( 16) based on [START_REF] Benson | Firedex: a prioritized iot data exchange middleware for emergency response[END_REF] gives:

R = p   ζ(µ+θ ON ) λζ+θ OFF ζ θ ON λζ+θ OFF 1   ( 19
)
where p=λ/µ.

Having determined R, we can compute P 0 . Based on [27] (Theorem 1.2.1, Chapter 1), we have that the vector P 0 should simultaneously satisfy:

P 0 (B 00 + RC 2 ) = 0 ( 20
)
P 0 (I -R) -1 e = 1 ( 21
)
where e refers to the eigenvalues of R. The solution of ( 20), ( 21) results in:

P 0 = P 0,0 P 0,1 = θ ON λζ+θ OFF θ OFF (1-p)-pζθ ON θ ON +θ OFF θ OFF (1-p)-pζθ ON θ ON +θ OFF (22)
Based on ( 13) and ( 22), we can compute P n for n=1,2,... From P n we calculate the average number of events in the system (server + queue), E(n) on/of f via:

E(n) on/of f = ∞ n=0 n P n,0 + P n,1 (23)
Since:

P n,0 + P n,1 = P n • 1 = P 0 R n • 1 (24)
we can write [START_REF] Bouloukakis | Performance modeling of the middleware overlay infrastructure of mobile things[END_REF] as follows:

E(n) on/of f = ∞ n=0 nP 0 R n • 1 = P 0 R ∞ n=0 nR n-1 • 1 = P 0 R (I -R) -1 2 • 1 = A 1 (A 2 + A 3 ) (25) where:
A 1 = p θ OFF (1 -p) -pζθ ON λζ + θ OFF θ ON + θ OFF A2 = θ ON ζ(λ + µ + θ ON ) + θ OFF λζ + θ OFF 1 -p 1 -p + pζ + pζ pθ ON (1 -ζ) + θ OFF A3 = ζ λ + θ ON + θ OFF pθ ON λζ + θ OFF 1 -p + pζ + θ OFF -pζθ ON pθ ON (1 -ζ) + θ OFF
If ζ=1, i.e., if events always join the queue then (22) becomes:

P 0 = P 0,0 P 0,1 = θ ON λ+θ OFF θ OFF θ ON +θ OFF -p θ OFF θ ON +θ OFF -p (26)
Similarly, [START_REF] Bouloukakis | Queueing network modeling patterns for reliable and unreliable publish/subscribe protocols[END_REF] becomes [START_REF] Bouloukakis | Performance modeling of the middleware overlay infrastructure of mobile things[END_REF]:

E(n) on/of f = λθ ON + p θ ON + θ OFF 2 θ OFF -p θ ON + θ OFF θ ON + θ OFF = p + λT OFF P server (OF F ) 1 -p (27)
where p = λ/µ • P server ON .

Having determined E(n) on/of f via (23) (or via [START_REF] Neuts | Matrix-geometric solutions in stochastic models: an algorithmic approach[END_REF], assuming ζ=1), we can calculate the average system time (server + queue), ∆ q prob on/of f , via Littles law as follows:

∆ q prob on/of f = E(n) on/of f λ ef f (28)
where

λ ef f = λ 1-P server (OF F )(1-ζ) = λ on/of f out
. We leverage [START_REF] Latouche | Introduction to matrix analytic methods in stochastic modeling[END_REF] to estimate [START_REF] Zanella | Internet of things for smart cities[END_REF] where λ = λ notif y si and µ = µ out si .

IV. EXPERIMENTAL RESULTS

We now validate the probabilistic ON/OFF model and evaluate the event dropping mechanism of our approach. For this, we use the JINQS (Java simulation library for multiclass queueing networks) open source simulator which enables system designers to build simulations for a wide range of queueing networks [START_REF] Field | Jinqs: An extensible library for simulating multiclass queueing networks[END_REF]. We extend JINQS to: (i) implement the probabilistic ON/OFF model; and (ii) simulate the proposed event-dropping mechanism as well as other existing approaches of pub/sub systems [START_REF]Sun Microsystems JMS Specifications[END_REF], [START_REF] John | A survey of distributed message broker queues[END_REF].

A. Analytical vs. simulated response time

After implementing the probabilistic ON/OFF queue using our simulator, we parameterize it as follows: (i) the server remains in the ON and OFF states for exponentially distributed time periods T ON = T OFF = 20 sec, thus, the server processes events and then buffers them every 20 sec on average; (ii) during the server's OFF periods, events join the queue with probability ζ which takes on values: 0.25, 0.5, 0.75 and 1.0; (iii) events are processed with a mean service rate µ = 8 events/sec; (iv) there is sufficient buffer capacity so that no events are dropped because of this; and (v) events arrive to the queue with a mean rate varying from 0.05 to 3.5 events/sec. We apply the above parameters to our simulation model and plot curves of mean response time (server+queue) as depicted in Fig. 4. The analytical results obtained by [START_REF] Latouche | Introduction to matrix analytic methods in stochastic modeling[END_REF] and depicted also in Fig. 4, show the high accuracy of [START_REF] Latouche | Introduction to matrix analytic methods in stochastic modeling[END_REF]. Note that when applying a join probability of ζ = 1, the ON/OFF queueing system is saturated for arrival rates greater than 4 events/sec. For ζ < 1, the system drops events and thus it is possible to apply arrival rates greater than 4 events/sec based on the condition 1 -λ ef f /µ < 1.

B. Event dropping comparison

We now compare the proposed event dropping mechanism against other mechanisms [START_REF]Sun Microsystems JMS Specifications[END_REF], [START_REF] John | A survey of distributed message broker queues[END_REF] found in the literature of pub/sub systems. We set up our system using our simulator and the queueing network of Fig. 1. Events arrive at the input queue (q in ) to be processed with rate µ in = 16 events/sec. There is no event dropping because of subscriptions, thus events arrive at the subscriber's ON/OFF queue to be transmitted with rate µ out si = 8 events/sec. The server of the ON/OFF queue changes its ON/OFF state based on the subscribers intermittent connectivity -i.e., T si ON = T si OFF = 20 sec. Upon s i 's subscription (r j ), the response time threshold ∆ T hr si = 7 sec is introduced and so the subscriber must receive all events within 7 sec on average. Hence, the pub/sub system must drop events to achieve this. We select this threshold because T si ON = T si OFF = 20 sec, and thus for any arrival rate (λ in b ) or processing rates (µ in , µ out si ), the end-to-end response time cannot be less than 10 sec without event dropping. By setting ∆ T hr si = 7 sec, we enforce event dropping even for very low λ in b . We compare the following dropping mechanisms: 1) Probabilistic event dropping (proposed): events join the queue with a join probability ζ, which is estimated based on ∆ T hr si = 7 sec and (28). 2) Expired event dropping [START_REF]Sun Microsystems JMS Specifications[END_REF]: upon the publication of an event, a lifetime period is applied to represent the event validity inside the queueing network. Hence, an event may enter the queuing network when it is published, but will leave the network as soon as its lifetime elapses and the event is considered expired. This corresponds to an ON/OFF queue with reneging or impatient customers. 3) Overloaded event dropping [START_REF] John | A survey of distributed message broker queues[END_REF]: we apply finite capacity buffers K at both input and output queues q in , q out-prob on/of f . Events that overload the queue will be dropped.

We run each experiment for a different arrival rate λ in b : 0.05 -7.7 events/sec. We apply the parameters depicted in Fig. 5 depending on the applied mechanisms. For the expired event dropping (second) experiment, we apply either deterministic lifetime for each λ in b or based on an exponential distribution. Note that for the second and third mechanisms, the join probability is set to ζ = 1 -i.e., all events join the q out-prob on/of f queue.

Fig. 6 shows the delivery success rates of all three dropping mechanisms for ∆ si = 7 sec = ∆ T hr si . For λ in b < 2 the success rates are greater than 67% for both the deterministic and exponential expired dropping mechanism. It is worth noting that the expired event dropping mechanism provides the highest delivery success rates in comparison to the remaining two. However, for λ in b > 2, success rates decrease suddenly. Regarding the other two mechanisms, the success rate of the overloaded event dropping is slightly higher (∼1-2% greater) than the probabilistic event dropping for λ in b > 0.05 and λ in b < 7.7. On the other hand, Fig. 7 shows the failure rate of events during s i 's connection (ON) periods when applying the overloaded event dropping mechanism -in the probabilistic mechanism there are no failures during ON periods, we only drop events during OFF periods. Therefore, even if the subscriber is connected, events may be dropped with rate 6% for higher arrival rates.

V. CONCLUSION

IoT devices usually exchange data by relying on the pub/sub middleware. Among the different mechanisms, pub/sub often supports event dropping for satisfying subscribers' QoS requirements. In this paper, we introduce a different event dropping mechanism that takes into account the subscribers' QoS semantics and requirements. We model the performance of a pub/sub middleware employing this mechanism and solve it analytically using queueing theory. We validate our analytical model using simulations and we compare our mechanisms against others in pub/sub systems. Our mechanism provides the highest delivery success rate when applying high publication rates and subscribers are connected.

In our future work, we intend to implement a prototype of the proposed mechanism.

  State(n,0) : λζP n-1,0 + θ ON P n,1 -(λζ + θ OFF )P n,0 = 0 State(n,1) : λP n-1,1 + µP n+1,1 + θ OFF P n,0 -(λ + µ + θ ON )P n,1 = 0 ...

1 Fig. 4 :

 14 Fig. 4: Probabilistic ON/OFF model validation.

Fig. 5 :

 5 Fig. 5: Applying parameters for comparison.

Fig. 6 :

 6 Fig. 6: Event-dropping mechanism comparisons.

Fig. 7 :

 7 Fig. 7: Failure rates during ON periods.

TABLE I :

 I Model variables' and shorthand notation.

	Variable(s)	Definition/Description
	v k ∈ V, rj ∈ R	event topics and subscriptions
	pi ∈ P, si ∈ S	publishers and subscribers
	λ pub p i ,v k	, λ in b , λ nosub	publication rate, input b's rate, subscriptions drop rate
	λ notif y s i	, λ sub s i	si's notification rate, si's delivery rate
	ζs i , S b		join probability, |S| subscribed in b
	µ in , µ out s i	processing rate, transmission rate
	T ON , T s i	s i OFF	average connected period, average disconnected period
	∆s i , ∆ T hr s i	, Ξs i	si's response time, si's threshold, si's success rate
	sponds to the subscriber's connected/disconnected states. An
	analytical model estimates the message dropping probability
	for satisfying specific response times. In our experimental
	results we validate the analytical model by relying on an
	open source simulator [19]. Additionally, our approach ensures
	100% message success rates during the subscribers' connected
	periods in comparison to others.
	The core contributions of this paper are:
	1) A formal model of a pub/sub probabilistic message drop-
	ping mechanism during the subscribers' disconnections
	for satisfying response time requirements ( §II).
	2) An extensive analysis of the probabilistic ON/OFF
	queueing model with an intermittent available server and
	probabilistic arrival rates ( §III).
	3) The validation of the proposed model by relying on an
	open source simulator ( §IV).
	4) The comparison of the proposed message dropping
	mechanism against several others via simulations ( §IV).

  . Additionally, Probabilistic ON/OFF queue. T si ON and T si OFF periods are estimated statistically inside b based on s i 's ON/OFF states by relying on a monitoring tool.

			KEͬK&&
	ߣ		ߤ	ߣ ݊ ݂݂
	ŝĨ ƐĞƌ|Ğƌ ŝƐ K&& ߞ	ǁĂŝƚŝŶŐ ĂƌĞĂ	ƐĞƌ|Ğƌ ŶŽĚĞ

/ ݐݑ Fig.

2:


Yann Bernard
email: yann.bernard@inria.fr-bernard.girau@loria.fr

Emeline Buoy

Adrien Fois

Bernard Girau

NP-SOM: network programmable self-organizing maps

Self-organizing maps (SOM) are a wellknown and biologically plausible model of input-driven selforganization that has shown to be effective in a wide range of applications. We want to use SOMs to control the processing cores of a massively parallel digital reconfigurable hardware, taking into account the communication constraints of its underlying network-on-chip (NoC) thanks to bio-inspired principles of structural plasticity. Although the SOM accounts for synaptic plasticity, it doesn't address structural plasticity. Therefore we have developed a model, namely the NP-SOM (network programmable self-organizing map), able to define SOMs with different underlying topologies as the result of a specific configuration of the associated NoC. To gain insights on a future introduction of advanced structural plasticity rules that will induce dynamic topological modifications, we investigate and quantify the effects of different hardwarecompatible topologies on the SOM performance. To perform our tests we consider a lossy image compression as an illustrative application.

Introduction

The structural organization of the brain is already a source of inspiration of several neuromorphic integrated circuits, but several dynamic properties of the brain computation have not really been explored as design principles for computational architectures. We are interested in the introduction of brain-inspired self-organization principles into the design of adaptive and dynamic digital computing architectures. Selforganizing neural models have already been studied, especially for vector quantization tasks. In project Saturn [START_REF] Saturn | Self-adaptive technologies for upgraded reconfigurable neural computing, french research agency (anr)[END_REF] it has been studied how neural self-organizing maps (SOMs) may control the development of computing areas in a manycore substrate, thus applying principles of synaptic plasticity to a hardware configuration. In [START_REF] Saturn | Self-adaptive technologies for upgraded reconfigurable neural computing, french research agency (anr)[END_REF], different input streams are analysed so as to quantify the complexity of the information they carry, then these measurements are fed into a SOM in which each neuron is associated to a core of the computing substrate: the codeword that is learned for a neuron determines which input stream must be processed by the associated core (e.g. visual input). But computing resources need to exchange data while they are dynamically allocated to different tasks, therefore communications between resources also need to re-organize themselves with the same constraints of decentralization. Existing self-organizing models are limited in this context, because they rely on a predefined topology and they do not take into account the communication costs nor the afferent connectivity. Therefore, we want to extend the usual self-organization mechanisms to account for a combination of bio-inspired principles of synaptic and structural plasticities. A few self-organizing models already consider structural plasticity, such as growing neural gas (GNG), but their induced connections are only data-dependent, so that they are usually hardware incompatible. We are currently developing variants of SOMs that include local pruning and sprouting rules while preserving underlying topologies that fit hardware communication constraints [START_REF] Upegui | Pruning self-organizing maps for cellular hardware architectures[END_REF]. But before introducing advanced rules for structural plasticity that induce changes to the network topology, an important first step is to study how different hardware-compatible topologies affect the behaviour and the performance of SOMs. This is precisely the aim of this paper, in which we analyse how different pre-designed topologies impact the SOM operation, in order to gain insights into the potential effects of an upcoming introduction of structural plasticity rules. For this analysis, we consider an application of vector quantization in which the SOM properties are known to improve the results [3, p.743] : lossy image compression. On the hardware side, we use basic principles on the operation of locally configurable network-on-chips (NoCs) to define the hardware constraints in our model. We consider three different configurations of a NoC that induce three SOM topologies. We compare the performance of the different SOMs in terms of pixel error, peak signal-to-noise ratio, and we compare how the final differential and entropy coding steps perform with the different SOMs. These comparisons help us to analyse the precise effects of the topological modifications, and to interpret them in terms of future applications for reconfigurable reconfiguration. In Section 1, we propose a short survey of vector quantization and its application to the concept of a self-organizing machine architecture. In Section 2, the basic Kohonen model for self-organizing maps is sketched out, and its application to lossy image compression is precisely described. Section 3 introduces our networkprogrammable version of SOMs (NP-SOM), first defining the kind of NoC we take into account. Section 4 gathers our experimental results, from which we derive several conclusions and discussions in Section 5.

Background 1.Vector quantization

We are interested in this work by brain-inspired inputdriven self-organization. More specifically, we want a network to be able to represent an input distribution (e.g. visual input) by learning it in an unsupervised way. The learning of the input distribution is usually conducted in the network by the modification of the synaptic weights and/or the creation or suppression of connections and/or neurons. The aim of this self-organized learning procedure is to start from an disorganized state (e.g. with randomly initialized synaptic weights) and converge toward a more ordered state. This increase in order in the network is characterized by the gradual formation of spatially segregated clusters of neurons that are codingand hence are selectively tuned to -certain features of the input distribution. In this regard vector quantization (VQ) techniques seem to be tightly related to the kind of input-driven self-organization we expect. VQ is a lossy source coding technique in which block of samples are quantized together [START_REF] Vasuki | A review of vector quantization techniques[END_REF]. It consists in approximating the probability density of the input space (which is split in blocks of samples) with a finite set of prototype vectors. A prototype vector is often referred to as a codeword and the set of codewords as the codebook.

Many VQ techniques exist such as k-means [START_REF] Macqueen | Some methods for classification and analysis of multivariate observations[END_REF], selforganizing maps (SOM) [START_REF] Kohonen | Self-organized formation of topologically correct feature maps[END_REF], neural gas (NG) [START_REF] Martinetz | Neural-gas network for vector quantization and its application to time-series prediction[END_REF], growing neural gas (GNG) [START_REF] Fritzke | A Growing Neural Gas Network Learns Topologies[END_REF] or growing when required (GWR) [START_REF] Marsland | A selforganising network that grows when required[END_REF]. Algorithms such as NG, GNG or GWR present good performance in terms of quantization error minimization which is measured by the mean squared error. However this performance may come during the learning phase with the creation in the network of a very large number of new prototypes and/or connections between prototypes. Additionally, the induced modifications are only data-dependent, without any topological restrictions. This is problematic as the connectivity and the computational resources are limited in reconfigurable hardware, therefore making those algorithms hardly able to reflect hardware communication constraints.

On the other hand the SOM is based on a static underlying topology and a fixed number of prototypes, making it more suited to the concept of a self-organizing hardware substrate. Moreover in a SOM and in contrast to standard VQ techniques, each prototype has an associated position in a map that has a predefined topology (the map is usually a 2D lattice). This spatial arrangement of the prototypes in the map makes it able to capture the topographic relationships (i.e. the similarities) between the inputs, in such a way that similar blocks of samples tend to be represented by spatially close prototypes in the map. This clustering results from the projection of the input space onto a lower-dimensional space (the map), which embodies pre-designed neighborhood relationships and competitive learning through a winner-takes-all mechanism. This property can be measured by the distortion that is computed by the Gaussian averages of distances between prototypes and input samples around the sample-related winners. As a matter of fact, the SOM is a well-known and biologically plausible model of the topographical mapping of the visual sensors to the cortex [START_REF] Yin | The Self-Organizing Maps: Background, Theories, Extensions and Applications[END_REF]. Besides its biological plausibility, the SOM has shown to be effective in a wide range of applications such as image compression and segmentation, data visualization or text mining [START_REF] Yin | The Self-Organizing Maps: Background, Theories, Extensions and Applications[END_REF][START_REF] Kohonen | Essentials of the self-organizing map[END_REF]. However, despite the interesting features that the SOM offers, the static underlying topology remains a limiting factor in the context of a self-organizing hardware project. Indeed, it corresponds to a manycore substrate where only neighbouring nodes can communicate. To extend it to long-range and adaptive communications, we intend to use more flexible network-on-chip solutions (see 3.1) and we therefore need to develop a SOM variant that takes into account this additional topological flexibility.

The SOMA project

The work presented in this paper is part of a broader project that follows a previous one [START_REF] Saturn | Self-adaptive technologies for upgraded reconfigurable neural computing, french research agency (anr)[END_REF], namely the SOMA project (Self-Organizing Machine Architecture [START_REF] Khacef | Neuromorphic hardware as a self-organizing computing system[END_REF]). The SOMA project aims at developing an architecture based on brain-inspired self-organization principles in a digital reconfigurable hardware, focusing on how structural plasticity principles can inspire new hardware mechanisms. As we wish to deploy the architecture in a manycore substrate, the scalability of the architecture needs to be ensured. For this reason, the communication system between the cores shall be carefully chosen to avoid the Von Neumann bottleneck. Consequently, rather than using a shared bus, a network-on-chip (NoC) ensures a decentralized communication between the cores in the SOMA architecture. Following [START_REF] Saturn | Self-adaptive technologies for upgraded reconfigurable neural computing, french research agency (anr)[END_REF], a SOM controls the configuration of computing nodes by analysing the complexity of the different input streams and deriving clusters of neurons that are directly related to computing areas in the manycore substrate. However, any configuration of the cores induces communication costs in terms of interconnects utilization in the underlying NoC. The idea of SOMA is to simultaneously learn the task allocation of nodes and the structural connectivity that the NoC must implement, so that the NoC constraints are taken into account while defining the computing areas. Thus, the principle of a free topology as in the Growing Neural Gases (GNG) is interesting to dynamically create topologies that better fit the input distribution, but it results in connections between neurons that induce too costly NoCbased communications between the associated nodes. Therefore, even if both SOM and GNG have interesting properties, they do not take into account the hardware communication restrictions (GNG) nor NoC configurability (SOM). This is why we propose here the model of a reconfigurable SOM. Such a model is able to dynamically change its underlying topology and adapt its codebook learning to these changes. In the context of this paper, we do not yet take into account such dynamic changes. We first want to estimate the impact of different hardware compatible topologies onto the behaviour of the SOM. We thus consider NoC-based topologies that differ from the basic 2D lattice of Kohonen SOMs, and we test them for a typical application for which various and complementary performance criteria are available.

Kohonen SOM

The model

The map

The neurons of the Kohonen SOM [START_REF] Kohonen | Essentials of the self-organizing map[END_REF] are spatially arranged in a discrete map which usually consists in a twodimensional grid. It shall be reminded that we will consider this topology as well as other hardware-compatible topologies in Section 3. Each neuron n is fully connected to all the source nodes and has a weight vector w n , or codeword, whose dimension is equal to a source node.

The algorithm

First, all codewords are initialized with random weights. The training of the SOM lasts a certain number of epochs. One epoch includes enough training iterations such that the whole training dataset has been used once for learning. For each training iteration, a training vector v is picked among the inputs. The best matching unit (BMU) g is then found, it corresponds to the neuron with the minimal L 2 distance between w g and v. Then the weights of all neurons are updated according to the following equation: w i pt `1q " w i ptq ` ptq ¨Θpσptq, d i,g q ¨pv ´wi ptqq [START_REF] Saturn | Self-adaptive technologies for upgraded reconfigurable neural computing, french research agency (anr)[END_REF] with and σ time functions (more details on them later), d i,g is the normalized L 1 distance between neuron i and the BMU. Θ is a normalized centred Gaussian function with standard deviation σ.

Parameters

σptq is a parameter that influences the neighbourhood function. The higher it is, the more the BMU influences other neurons. We have set it to start at 0.5 and linearly decrease to a final value of 0.001, so that at the beginning of the training all neurons are significantly influenced by the BMU, and at the end, nearly none except the BMU are. ptq is the learning parameter, it starts at 0.6 and linearly decreases to a final value of 0.05. In our tests, we ran the SOM for 50 epochs.

Application: lossy image compression

We consider a well-known application of vector quantization: lossy image compression [START_REF] Xiao | Selforganizing map-based color palette for high-dynamic range texture compression[END_REF]. A picture or series of pictures to be compressed is split into smaller k ˆk pixels wide thumbnails. When the image height or width is not divisible by k, we crop it on the right and bottom. We then use these thumbnails as training samples of a VQ model. Once the training is finished, the compressed image is composed of the whole codebook, and the index of the BMU for each thumbnail extracted from the image or images. A final lossless entropy coding such as Huffman coding is used to further compress the file. Decompression is performed by reverting the final lossless compression, and recomposing the original image from the stored codebook and the indexes of the BMUs: each index is replaced by the corresponding codeword thumbnail. The result is similar to the original image, but with every subimage replaced by the codeword learned by its BMU. Figure 2 illustrates this compression/decompression process, without the entropy coding step. In the case of a SOM used as VQ model, an additional step can be introduced just before entropy coding to further improve its efficiency. A differential coding can be applied to the stored BMU indexes, as in [START_REF] Amerijckx | Image Compression using self-Organizing Maps[END_REF]. Each index is replaced by the difference between this index and the BMU index of the immediately neighbouring thumbnail in the direction which maximizes the image smoothness (see [START_REF] Amerijckx | Image Compression using self-Organizing Maps[END_REF] for details). This process results in rather small differences thanks to SOM properties, and the final entropy coding performs better on such small values.

Compression rate

We consider here the compression of a single greyscale image. A raw compression rate can be calculated before the final differential and entropy coding steps. It depends on the number of neurons N ˆN and the size of the side of each square sub-image. This raw compression rate (R c ) is the ratio between the initial image size and the size of the file that contains the codebook and the binary coded BMU indexes. It is expressed as below:

R c " S i S f " 8hw 8N 2 s 2 `2 hw s 2 log 2 pN q (2)
S i and S f represent respectively the size of the original image and of the compressed image, h and w are respectively the height and width of the image, N ˆN is the number of neurons and s is the side length of a sub-image. As seen in Figure 3, for each number of neurons, R c first increases with s, then it decreases, which reflects the influence of the two terms in the denominator of equation 2. Furthermore, the lesser neurons there are, the better the compression is. However, a compromise between compression rate and quality of the image has to be found.

The final compression rate depends on the efficiency of the entropy coding, which itself depends on the distribution of the values computed during the differential coding step.

Quality assessment of the compression

There are many possible metrics to quantify the differences between two images. But none of them can really give a definitive judgement on the visual quality of the compression. This is because evaluating quality is a multi-criteria problem dependent on the observer (one observer may prefer colour correctness over finely detailed edges and another one the inverse), and the fact that knowing the impact each pixel has in an observer's evaluation of quality is a non-trivial problem.

We will present some of the metrics we used and the reasons behind each of these, but keep in mind that the eyeball is currently our best tool.

Mean pixel difference

The most obvious metric is to compute the mean error per pixel. It is obtained with the following equation:

mean " 1 w ˆh w ÿ x"1 h ÿ y"1 |P x,y ´P 1 x,y | (3)
with P x,y the pixel at the x th column and y th of the original image, and P 1 x,y its equivalent in the compressed image. There are many problems with this metric for image comparison, because it puts the same weight on all pixels (some background pixels may have the same impact on the result as a high information foreground pixel). Moreover, it doesn't guarantee that the error is well distributed: 100 pixels that are off by 1 will have the same error as 5 pixels off by 20, although the visual result would be quite different. But it is also a generalizable measurement that would work equivalently with any other data, and it is the measure that our neurons try to minimise locally, so it is the best one to evaluate if the learning task of the SOM is correctly performed.

Peak Signal to Noise Ratio

A common metric used in image compression is the Peak Signal to Noise Ratio (PSNR). The goal is to measure the noise added to the signal (in our case the image) during compression. It is calculated from the Mean Square Error (MSE) with the following formulas, and expressed in decibels (dB):

M SE " 1 w ˆh w ÿ x"1 h ÿ y"1 pP x,y ´P 1
x,y q 2 (4)

P SN R " 10 ˆlog 10 p 255 2 M SE q (5)
PSNR has been widely used in image compression because it is a loose approximation to the human perception of quality, and as such it is a rather satisfactory metric for what we want to measure. It still has some of the defaults of the mean pixels difference (all pixels have the same weight regardless of usefulness in the recognition), but now error spikes are more penalizing for the quality score than small diluted errors.

Image database used

Because of long training times we chose to limit ourselves to small greyscale images of 256*256 pixels. They can be found here [14].

3 The model of a topologically restricted SOM

Locally configurable Network-on-Chip

In the SOMA architecture, the proposed self-organizing mechanisms will be exploited by user-defined applications running on a multicore array in the form of a NoC-based manycore system. The NoC will provide different features such that computation nodes may:

• Communicate between neighbouring and remote computing nodes in the manycore array. Constraints apply to simultaneous communications. • Communicate to the underlying self-organizing layer in order to influence the self-organization. • Get inputs and dynamic configurations from the selforganization layer. Different NoC technologies are available. A popular approach is packet switching, where channels of communications are created along the packet transfer path, using the information in the header to locally determine the next node of the path. Channels are occupied during the transmission of data, and then released. This approach is well adapted to applications where nodes communicate irregularly. The idea behind the SOMA architecture is to take into account hardware communications channels that evolve like some kind of dendritic tree. For example if the nodes perform neural computations, connected nodes will continuously exchange data. A possibility is to use a NoC architecture able to combine as many channels as possible at a time, e.g. using the HER-MES routing scheme [START_REF] Moraes | Hermes: an infrastructure for low area overhead packet-switching networks on chip[END_REF] for inter-node communication, for which an adapted version of the NoC architecture to support dynamic reconfiguration has been proposed [START_REF] Fiack | Dynamic parallel reconfiguration for self-adaptive hardware architectures[END_REF]. Such a NoC architecture is able to build multiple and steady communication channels simultaneously. Another option is to use a locally configurable NoC dedicated to neural architectures, such as in the FPNA concept [START_REF] Girau | FPNA: concepts and properties[END_REF]. Despite their differences (such as Hermes' ability to handle type-based routing), these NoC architectures eventually reduce to a common principle: configuring local connections in an oriented graph where each node behaves as a local network switch between incoming arcs (input gates) and outgoing arcs (output gates). To ensure a simple hardware compatibility, we consider in this paper that this graph is based on a simple grid, see 3.

Link between SOM topology and Networks-on-Chip

In the self-organizing hardware architecture targeted by the SOMA project, each computing core is virtually associated to a neuron of the SOM that controls task allocation. Since the learning process of this SOM must reflect the communication constraints among the cores according to their allocated task, we propose that this SOM learns its codebook and its underlying topology together, while constraining this topology to be NoC compatible. After learning, the computing areas will be associated to groups of neurons that have similar codewords, and the fundamental properties of SOMs will result in the fact that such neurons will be close with respect to the NoC compatible underlying topology. We consider that the best way to ensure this NoC compatibility is to directly define the SOM topology as the result of a specific configuration of the NoC. Our goal is then to define learning mechanisms at the level of the local configurations. Before defining such local learning rules on a bio-inspired basis, we want to study in this paper the effect of various NoC-based SOM topologies on VQ properties. To that purpose, we propose below the network programmable SOM model (NP-SOM), first without any mechanism to learn the topology, but evaluating various static NoC-based topologies.

A first obvious configuration corresponds to the fact that each routing node only sends the received data to the local core/neuron. Since the underlying graph of the NoC is a grid, this results in the usual grid topology of SOMs. Many other configurations are possible. Among them, we focus on configurations that somehow would minimize the resulting communication times for distant cores. Two such configurations are chosen, they will be depicted in the next section.

The NP-SOM model Simple Model

Let us consider a couple pN , Gq, where N is a set of neurons and G is a set of gates. The neurons are positioned as in a grid. Each neuron is surrounded by 8 gates, 2 in the North, East, West and South directions of the neuron. The two gates that can be found in each direction around a neuron stand for the input and output gates of this neuron from and towards this direction. The set composed by a neuron and its gates is called a node.

Within each node, a local connection matrix defines which neuron or input gate is connected to which output gate or neuron. This matrix is filled with 0's and 1's: 0 if there is no connection and 1 if there is a connection between some input and output gates, or between an input gate and the local neuron n or between the local neuron n and an output gate.

The distance

As seen previously, neurons of a SOM need a distance metric in order to know the degree of closeness they have with the BMU during learning. In the perspective of associating each communication channel created in the NoC as a direct privileged link between computing nodes, we consider that any neuron that can be accessed by routing from a source neuron without having to go through another neuron (i.e. the only possible routing is through gate-to-gate connections except for the source and receiver nodes) is at a distance 1 from the source. In the general case, when there is k neurons between the source and the receiver, with k being minimal, the distance is equal to k `1.

For example, as it can be seen in the bottom of Figure 4, the distance between neurons A and B is 6.

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 A I H G F E D C B A I H G F E D C B Resulting Graph

Three derived topologies

In the context of this paper, two topologies have been tested in addition to the grid topology often used for Kohonen SOMs. Figure 5 depicts these underlying topologies (or graph structure of the SOMs) on the right, while showing how to derive them from local interconnections on the left. From now on, we call kohonen a NP-SOM that uses a static grid as underlying topology, star a NP-SOM that uses the depicted scale-free star-like configuration as underlying topology, and sw a NP-SOM that uses the depicted small world-like configuration as underlying topology. Of course, kohonen behaves exactly as a standard Kohonen SOM using a grid structure.

Kohonen-like topology

Small World-like topology

Equivalent Graph

Scale Free-like topology

NoC version

General Model

Let's consider an undirected graph Φ " pN , Aq where N is a finite set of neurons and A is the set of every possible link between neurons. For example for n, n 1 P N , pn, n 1 q P A is a link between n and n 1 but it does not mean that n and n 1 are connected.

The set L " tpn, e, oq{n P N , e " pn 1 , nq P A Y tpn, nqu, o " pn, n"q P A Y tpn, nquu is defined as all possible local connections that can exist in Φ. At the level of a neuron n, a triplet pn, e, oq represents a direct connection from an incoming link e (from n 1 to n) or from neuron n itself (when e " pn, nq) to an outgoing link o (from n to n") or to neuron n itself (when o " pn, nq). The triplet (n,(n,n),(n,n)) is not allowed because it would represent a neuron connected to itself. A configuration of a NP-SOM based on Φ is a subset C Ă L of instantiated connections.

Neuron distance

The definition of the distance first needs the definition of a simple path.

Let us consider two neurons n 1 , n 2 P N , a simple path γpn 1 , n 2 q is a list of triplets of C, that represent successive connected links able to "go" from n 1 to n 2 within Φ, where there is no intermediate neuron in the path. This can be represented as follows:

γpn 1 , n 2 q " ppn 1 1 , e 1 , o 1 q, ..., pn 1 m , e m , o m qq with • n 1 1 " n 1 , e 1 " pn 1 , n 1 q, n 1 m " n 2 , o m " pn 2 , n 2 q • @i P t1, . . . , mu, pn 1
i , e i , o i q P C • @i ą 1 and @n P N , e i ‰ pn, nq • @j ă m and @n P N , o j ‰ pn, nq

• @i P t2, . . . , m´1u, e i " pn 1 i´1 , n 1 i q and o i " pn 1 i , n 1 i`1 q Thus, @pn, n 1 q P N 2 , if there is a simple path γpn, n 1 q in Φ configured by C, the distance between n and n 1 is dpn, n 1 q " 1. We then define a complex path between neurons n and n 1 as a list of simple paths Γpn, n 1 q " pγpn, n 1 q, γpn 1 , n 2 q, ..., γpn m´2 , n m´1 q, γpn m´1 , n 1 qq. The length of a complex path is the size of the list (number of simple paths in the complex path). Eventually, the distance d between two neurons pn, n 1 q is the minimum length of a complex path Γpn, n 1 q in Φ configured by C. If there is no such complex path, the distance is `8.

Learning algorithm

The learning algorithm of a NP-SOM defined by a graph of neurons Φ and a configuration C of Φ is the same learning algorithm as for Kohonen SOMs, see Section 2, except that the distance used in equation 1 is defined as just above.

Results

Statistical analysis

In order to compare the different topologies on our set of metrics, we ran the three of them on three images from our dataset, and three configurations of picture sizes and neuron numbers so that all configurations approximately results in the same theoretical compression ratio (CR) of 9 (3x3 subpictures with 9x9 neurons has a CR of 9.23, 6x6 ones with 12x12 neurons is at 9.36 and 9x9 ones 9x9 neurons has a CR of 9.02). For each combination of all parameters, we ran 20 different seeds for the random weight initialisation and with each 10 other seeds that determine the order of presentation of the training vectors. So in Figure 7, each boxplot distribution corresponds to 200 random runs for each of the three topologies. Given that the variance of the distributions significantly differ, we used the Kruskal-Wallis rank based test. We ran this test for each of the 36 configurations represented in the Figure 7 and found p-values lower than 2e ´12 for any configuration, except one, which is the total compression on the Lake image with 3*3 thumbnails.

On the resulting boxplots in Figure 7, we can observe that the distributions differ greatly between the topologies and images. For the mean error criterion, the star NP-SOM obtains the lowest value, and kohonen has the highest one, except when using small 3x3 thumbnails where it is equivalent to star. This could be due to the fact that a smaller dimensionality on data increases the density of samples in the training space, thus making stronger bonds between neurons an improving factor, unlike in larger dimensional spaces.

The PSNR column shows again star as a clear winner. The sw NP-SOM follows with a notably high variance. For kohonen we can observe that it is clearly less satisfactory than with star, even in the cases where it was better in mean error. The PSNR is based on the squared error, thus star's better performance here implies that this NP-SOM is more capable of learning outliers training vectors.

The third criterion used in Figure 7 relates to differential coding. We computed a ratio by dividing the combination of differential coding followed by an entropy coding, by what the result would have been if only entropy coding was used without differential coding. This is meant to measure the gains of differential coding, by which we can estimate a SOM property that neighbouring neurons are also closely related in the input space, and as we expect similar sub-pictures to be close in the image, differential coding should give low numbers resulting in a more efficient entropy coding. The kohonen NP-SOM is as expected a clear winner here. The strong neighbourhood correlations aren't as present in the other layouts, consequently the gains here are less important because close sub-pictures may not be coded with close neurons.

The last column in Figure 7 is the total compression ratio. It is obtained by using the basic VQ compression followed by lossless differential and entropy coding. There is no clear winner here, but kohonen and sw seem a little bit ahead. The compression gains observed in differential coding for kohonen are somewhat mitigated by the density-respecting property of Kohonen SOM. As we can see in Figure 6 the codewords are more equally distributed for kohonen than for star or sw where a single neuron can represent a great number of pictures. This has an impact on the entropy coding compression, and explains why kohonen does not always reach the best compression ratio.

Examples

In this section we present some visual results and interpretations that complements the statistical data seen in the previous subsection, using a single random run of our SOM on a test image. On Figure 8 we can see the com- pressed/decompressed version of the Einstein image (row 1: using 3 ˆ3 thumbnails, row 3: using 9 ˆ9 thumbnails) and the associated codebooks (rows 2 and 4) by showing the subpictures learned by the neurons arranged according to the neuron positions in the underlying topology. The left column corresponds to the results obtained with kohonen and the right one with star. For kohonen we can see a clear correlation between all neighbouring neurons in the codebook, but most neurons just learn some shade of grey with only a few features. On the other hand star better learns the most salient facial features (eyes, nose, moustache, . . . ). The star codebook shows a clear segmentation of blocks of 3 by 3 codewords. All codewords within each block are closely related but still have enough freedom to learn specific features, while block centers (connected in sw) are highly correlated.

Similar results are obtained for the other images, though they were chosen to stand for very different features (texture, saliency, . . . ). For example the compressed/decompressed Pepper image shows that edges are better defined and less blurry with star. The star codebook segmentation in blocks of 3 by 3 codewords is much slighter. Qualitative results obtained by sw are closer to those obtained by star than by kohonen.

Conclusion

In this paper, we defined the concept of network programmable self-organizing map (NP-SOM) from which we can define variants of Kohonen's SOMs that use different hardware-compatible topologies. Specific NP-SOMs using static underlying topologies have been derived to study the impact of topologies on the performance of the SOM. This is done in the context of the SOMA project to gain insights on the future introduction of advanced structural plasticity rules that induce changes to the network topology. By hardwarecompatible topologies, we specifically mean topologies compatible with a simplified model of Network-on-Chip (NoC) which is a decentralized communication routing system.

The two proposed topologies, scale-free star-like and small-world-like, have numerous advantages for our proposed usage. They use less connections (approximately 45% less than in a grid for the scale-free star-like topology and 30% for the small-world-like one). The NP-SOMs that use one of these two topologies (called star and sw) have a lower error rate and higher PSNR than Kohonen SOM, at the cost of losing Kohonen's integration properties, which is reflected Resulting performance distributions on three images from our dataset. Each colour represents a topology, red corresponds to Kohonen, green to Star and blue to Small-worlds. For all criteria except mean error, the higher is the better. with lower differential coding gains. On the other hand, lower neighbouring constraints gives star, and to a lesser extent sw, more freedom to explore the input space and adapt to the shape of the data. Consequently they follow a more segregatory approach, and are able to learn outliers that a strongly constrained Kohonen SOM would have ignored.

For the SOMA project this result suggests that the networking between neurons in SOM has a notable impact on it's performances and behaviour, and validates our approach to use structural plasticity as a mean to modify and improve SOM properties. For example star and sw are able to introduce mode abrupt transitions between neighbouring codewords when it better fits the input. This property may result in a more clearly defined task allocation for the cores at the border of processing areas.

Figure 1 :

 1 Figure 1: Example of a Kohonen SOM learning a sample of random uniformly distributed data in r0, 1s 2

Figure 1

 1 Figure1illustrates how a SOM unfolds in the input space (here simply 2D): the codewords that are learned are shown in red in the input space (from which random inputs are drawn, see blue points), red links being virtually added between the codewords of neighbouring neurons in the map.

Figure 2 :

 2 Figure 2: Simplified scheme of the image compression/decompression process (with only 25 sub-images and 9 neurons) with a simple test example underneath.

Figure 3 :

 3 Figure 3: Compression rate function of the side s of subimages and the number N ˆN of neurons.

Figure 4 :

 4 Figure 4: The top row illustrates an example of a neuron n local connection matrix. The bottom row represents a 3x3 NP-SOM and its resulting distance graph used for our SOM.

Figure 5 :

 5 Figure 5: Examples of connection configurations on a NoC.

Figure 6 :

 6 Figure 6: Histogram of the first 30 neurons sorted in decreasing order of times they were selected as BMU on one run.

Figure 7 :

 7 Figure7: Resulting performance distributions on three images from our dataset. Each colour represents a topology, red corresponds to Kohonen, green to Star and blue to Small-worlds. For all criteria except mean error, the higher is the better.

Figure 8 :

 8 Figure 8: Compressed/decompressed image and learned subpictures of the Einstein image, using (top) 3 ˆ3 sub-pictures and 9 ˆ9 neurons, or (bottom) 9 ˆ9 sub-pictures and 12 ˆ12 neurons. kohonen is on the left and star on the right. (The horizontal and vertical black lines in the SOM are borders present in the original image.)

Acknowledgement

The authors would like to thank the Swiss National Science Foundation (SNSF) and the Agence Nationale de la Recherche (ANR) for funding the SOMA project: <ANR-17-CE24-0036>.