Patrick Wüchner
email: patrick.wuechner@uni-passau.de

János Sztrik
email: jsztrik@inf.unideb.hu

Hermann De Meer

Modeling Wireless Sensor Networks Using Finite-Source Retrial Queues with Unreliable Orbit

Keywords: performance evaluation, unreliable finite-source retrial queue, wireless sensor network, energy efficiency, self-organization

Motivated by the need for performance models suitable for modeling and evaluation of wireless sensor networks, we introduce a retrial queueing system with a finite number of homogeneous sources, unreliable servers, orbital search, and unreliable orbit. All random variables involved in model construction are assumed to be independent and exponentially distributed. Providing a generalized stochastic Petri net model of the system, steady-state analysis of the underlying continuous-time Markov chain is performed and steady-state performance measures are computed by the help of the MOSEL-2 tool. The main novelty of this investigation is the introduction of an unreliable orbit and its application to wireless sensor networks. Numerical examples are derived to show the influence of sleep/awake time ratio, message dropping, and message blocking on the senor nodes' performance.

Introduction

Wireless sensor networks (WSNs, [START_REF] Akyildiz | Wireless Sensor Networks[END_REF][START_REF] Dressler | Self-Organization in Sensor and Actor Networks[END_REF]) are communication networks with harsh resource constraints. They need lightweight, energy-efficient, and self-organizing communication protocols.

In this paper, we propose a model that allows to discuss the trade-off between the energy efficiency and performance of WSNs by showing the positive and negative effects of message dropping and blocking for variable sleep/awake time ratios. The model is based on retrial queueing systems [START_REF] Artalejo | Retrial Queueing Systems: A Computational Approach[END_REF] in which arriving jobs that find all servers unavailable do not line up in a queue, but join a so-called orbit. An orbit is a buffer from where the jobs retry to get service until they are successfully served. In contrast to ordinary queueing systems, the server(s) might be idle even if the buffer contains jobs.

Due to their broad practical applicability, e.g., in the field of communication networks, and due to their non-triviality, retrial queues have been receiving wide interest in the scientific community. The interested reader is referred to [START_REF] Artalejo | Retrial Queueing Systems: A Computational Approach[END_REF] for a recent introduction and summary of main methods, results, and applications.

Here, we focus on finite-source retrial queues. The arrival process is then non-Poisson and depends on the number of customers already staying at the system (see [7, p. 32]). While several variants of finite-source retrial queues have been studied in related work (e.g., in [2-4, 6, 17-19]), the authors are not aware of any discussion of the orbit's unreliability, not even in the infinite-source case.

Our main contribution is presenting and discussing a generalized model of finite-source retrial queues with unreliable orbit that also takes unreliable servers (cf. [START_REF] Artalejo | New results in retrial queueing systems with breakdown of the servers[END_REF][START_REF] Wang | Reliability analysis of the retrial queue with server breakdowns and repairs[END_REF][START_REF] Almasi | Homogeneous finite-source retrial queues with server subject to breakdowns and repairs[END_REF][START_REF] Wüchner | Modeling finite-source retrial queueing systems with unreliable heterogeneous servers and different service policies using MOSEL[END_REF]) and orbital search (cf. [START_REF] Artalejo | An M/G/1 retrial queue with orbital search by the server[END_REF][START_REF] Chakravarthy | Analysis of a multi-server retrial queue with search of customers from the orbit[END_REF][START_REF] Dudin | Analysis of the BMAP/G/1 retrial system with search of customers from the orbit[END_REF][START_REF] Wüchner | Homogeneous finite-source retrial queues with search of customers from the orbit[END_REF][START_REF] Wüchner | Finite-source M/M/S retrial queue with search for balking and impatient customers from the orbit[END_REF]) into account.

By the help of this model, we discuss the influence of the sleep/awake time ratio, message dropping, and message blocking on the senor nodes' mean response time, serving probability, and blocking probability.

The paper is organized as follows. We introduce the investigated WSN scenario in Sect. 2. In Sect. 3, we present the full model description in form of a generalized stochastic Petri net (GSPN), discuss the underlying continuous-time Markov chain (CTMC), and present the main performance measures. Numerical results, conveniently derived using the MOSEL-2 tool, are presented and their implications on WSN design are discussed in Sect. 4. We conclude by summarizing the paper and giving directions for future work in Sect. 5.

Use Case: Wireless Sensor Network

An example WSN scenario is shown in Fig. 1. Immobile sensor nodes (circles) are deployed in a two-dimensional (x, y) area. The nodes are labeled with their distance to the sink measured by the number of communication hops. The sink node (solid black circle) is located at coordinate [START_REF] Artalejo | Retrial Queueing Systems: A Computational Approach[END_REF][START_REF] Artalejo | New results in retrial queueing systems with breakdown of the servers[END_REF]. 1 Due to harsh resource constraints and the resulting limited transmission range, each node i (located at (x i , y i )) is only able to communicate directly with its immediate neighbors, i.e., with all nodes j where |x j -x i | ≤ 1 and |y j -y i | ≤ 2. For example, the node located at [START_REF] Artalejo | Retrial queues with a finite number of sources[END_REF][START_REF] Amador | On the distribution of the successful and blocked events in retrial queues with finite number of sources[END_REF] is able to exchange messages directly with the nodes located at [START_REF] Artalejo | Retrial queues with a finite number of sources[END_REF][START_REF] Artalejo | Retrial queues with a finite number of sources[END_REF], [START_REF] Artalejo | New results in retrial queueing systems with breakdown of the servers[END_REF][START_REF] Artalejo | New results in retrial queueing systems with breakdown of the servers[END_REF], [START_REF] Artalejo | New results in retrial queueing systems with breakdown of the servers[END_REF][START_REF] Almasi | Homogeneous finite-source retrial queues with server subject to breakdowns and repairs[END_REF], (6, 2), [START_REF] Artalejo | Retrial Queueing Systems: A Computational Approach[END_REF][START_REF] Almasi | Homogeneous finite-source retrial queues with server subject to breakdowns and repairs[END_REF], and also with the sink. We further assume that each node is aware of its own distance to the sink measured in the number of hops. The purpose of the given sensor network is to monitor the covered area, record incidents, and communicate the appearance of incidents to the sink in a multihop fashion. In a real system, such incidents could be, e.g., the recognition of an intrusion, temperatures or humidity exceeding or under-running predefined thresholds, or the detection of fire, gas, vibration, movement, noise, etc. We assume that each node may be equipped with several sensors. Hence, each node may detect several but a finite number of distinct incidents.

In the example scenario sketched in Fig. 1, three incidents (Incidents 0, 1, and 2) can be detected by the sensor network. For example, node [START_REF] Almasi | Heterogeneous finite-source retrial queues[END_REF][START_REF] Artalejo | Retrial queues with a finite number of sources[END_REF] detects Incidents 0 and 1, immediately generates a message for each incident, and tries to send both messages toward the sink. Node [START_REF] Almasi | Heterogeneous finite-source retrial queues[END_REF][START_REF] Artalejo | Retrial queues with a finite number of sources[END_REF] has six neighbors of which two are closer to the sink: node (3, 7) and node [START_REF] Almasi | Homogeneous finite-source retrial queues with server subject to breakdowns and repairs[END_REF][START_REF] Artalejo | New results in retrial queueing systems with breakdown of the servers[END_REF].

In principle, all neighbors can be aware of the transmission due to the broadcast character of the wireless air interface. Hence, each neighbor may serve as next-hop node. However, nodes are self-organizing and, for saving energy, may decline to receive new messages, store messages, or (re-)send messages depending on the node's energy status, the sender's distance to the sink, etc.

By sending an acknowledgment, a receiver agrees to accept the message and to take care of forwarding it further. If none of the neighbors accepts the message, node [START_REF] Almasi | Heterogeneous finite-source retrial queues[END_REF][START_REF] Artalejo | Retrial queues with a finite number of sources[END_REF] stores it locally and retries to forward it later. If in the meanwhile node [START_REF] Almasi | Heterogeneous finite-source retrial queues[END_REF][START_REF] Artalejo | Retrial queues with a finite number of sources[END_REF] receives further messages reporting the same incident, it merges the messages. Hence, each incident is only stored once at the node.

As soon as the message has successfully been transferred to the next hop, the latter takes care of forwarding the message toward the sink. Messages that reach the sink leave the sensor network.

Model and Performance Measures

As a first step toward assessing the influence of system parameters on the performance and energy efficiency of the WSN scenario introduced in Sect. 2, we focus on a single node and its neighbors in this paper.

In this section, we present a model representing such a group of nodes. After constructing the model in the form of a GSPN (cf. [10, p. 64]) and discussing the underlying CTMC (cf. [10, p. 96]), performance measures are derived based on the model's steady-state probabilities.

Generalized Stochastic Petri Net Model

In Figure 2, the model is graphically represented in form of a GSPN.The model is a generalization of finite-source retrial queues with unreliable servers (cf. [START_REF] Almasi | Homogeneous finite-source retrial queues with server subject to breakdowns and repairs[END_REF][START_REF] Wüchner | Modeling finite-source retrial queueing systems with unreliable heterogeneous servers and different service policies using MOSEL[END_REF]) and finite-source retrial queues with orbital search (cf. [START_REF] Wüchner | Homogeneous finite-source retrial queues with search of customers from the orbit[END_REF][START_REF] Wüchner | Finite-source M/M/S retrial queue with search for balking and impatient customers from the orbit[END_REF]) by introducing an unreliable orbit, server hopping, and a variable number of server repairmen.

The main model parameters, the places' descriptions, and the transitions' functions are summarized in Tabs. 1, 2, and 3, respectively. Tab. 4 maps the use case's parameters to the model parameters and defines default values used as a basis for numerical evaluations in Sect. 4.

Note that not all model properties can be mapped to the graphical GSPN representation conveniently. For example, the dashed inhibitor arcs are subject to additional guard functions. Please refer to Tab. 3 (IF statements in column Value) for a comprehensive list of all guard functions that have to be considered. The model consists of three main parts (gray boxes in Fig. 2): a finite set of sources, a finite set of servers, and the orbit component.

In our finite-source model, there are K sources represented by K Petri net tokens initially residing in place So. All tokens located in place So represent incidents that are currently not sensed by, reported to, or accepted by the node under investigation. New incidents arrive to the node with arrival rate λ per unreported incident (transition t 1 ). Remember that incoming reports of incidents that are already currently processed by the node do not imply new tasks which motivates the application of a finite-source model.

Arriving tokens enter place R from where they immediately try to enter the group of S servers. The node immediately tries to forward new messages (represented by tokens in place R) to one of the next hops, represented by the group of S servers. Each server might be idle and up (tokens in place S iu ), busy and up (S bu ), idle and down (S id ), or busy and down (S bd ). Busy servers represent next-hop nodes that are currently not able to receive incident messages since they are processing former messages (t 3 ) with rate µ. A server is considered down when the corresponding next-hop node is sleeping, i.e., in power-saving mode. Only servers that are up and idle are ready to receive tokens. If none of the servers (next hops) is idle and up (awake), arriving tokens (incident messages) move to the orbit O (investigated node's local storage of messages) via t 5 . Idle servers fail (t 12 ), i.e., idle next hops fall asleep, with rate δ Si . Each failed idle server gets repaired (t 13 ), i.e., idle next hop wakes up, with a rate of τ Si (if S R ≥ S). Similarly, busy servers fail (t 8 ) with rate δ Sb and get repaired (t 9 ) with τ Sb each (if S R ≥ S). If δ Si = δ Sb > 0, we call the breakdowns independent, and if δ Si = 0 < δ Sb , we call them active (cf. [START_REF] Wüchner | Modeling finite-source retrial queueing systems with unreliable heterogeneous servers and different service policies using MOSEL[END_REF]). In the following, we assume that all breakdowns and repairs are independent with rates δ := δ Si = δ Sb and τ := τ Si = τ Sb , respectively. We call δ -1 and τ -1 the next hops' mean awake and sleeping time, respectively.

For keeping the model general and being able to compare the model to related work, we also allow the number of server repairmen S R to be smaller than the number of servers. If 0 < S R < S, failed busy servers are repaired with a higher priority than idle servers. Hence, S R is the maximum number of repairmen available for failed busy servers and max(0, S R -S bu ) is the remaining maximum number of repairmen available for failed idle servers (see column Value in Tab. 3 for t 9 and t 13 ). In the following, we assume that S R = S.

The model allows server hopping (t 10 ) and flushing (t 11 ) on server failure if the parameters σ and φ are set to true (i.e., 1), respectively. Server hopping enables tokens to be directly transferred from a failing server to any operational idle server. If server flushing is active, tokens are moved from a failing server to the orbit. If both options are enabled, server hopping has higher priority. Workload at failing servers is resumed after repair if both options are disabled. In the following, we assume that hopping is always disabled (σ = 0) and server flushing is referred to as next-hop dropping since incident messages are dropped from failing next hops if φ = 1.

Tokens located in the orbit (O) represent incident messages stored in the node under investigation for retransmission. Each token located in the orbit (O) is retrying (t 6 ) to enter the group of servers after an exponentially distributed retrial time with mean 1/ν.

Representing the node's potential to refrain from storing incoming messages and from sending stored messages for power-saving reasons, the orbit is subject to failure (t 14 ) with rate δ O . A failed orbit gets repaired (t 15 ) with rate τ O . Depending on parameter ω, the failing orbit may discard all stored tokens (node dropping, ω = 1) via t 16 or keep them for later resumption. In the following, we assume δ O = δ and τ O = τ .

Via parameters β and γ, blocked sources (cf., [START_REF] Wüchner | Modeling finite-source retrial queueing systems with unreliable heterogeneous servers and different service policies using MOSEL[END_REF]) can be modeled (see guard function of t 1 ). In the blocked case, sources do not generate new calls if all servers (β = 1) and/or the orbit (γ = 1) is down. In the unblocked case (β = γ = 0), sources are aware neither of server nor orbit failures. Blocked sources represent the node's ability to decline incoming messages since no next hop is available (next-hop blocking, β = 1) or since the node itself is in power-saving mode (node blocking, γ = 1). Here, power-saving of the investigated node refers to the case when it still might forward messages to next hops but refrains from storing and re-sending new incident messages that cannot be sent immediately.

With probability p, a busy server on service completion (token at place F ) informs the (operational) orbit of its upcoming idleness and, if available, directly receives (t 7 ) the next token from the orbit (orbital search). With a probability of 1 -p, orbital search is not performed (t 4 ). For p ≈ 1, the performance of a reliable retrial queue resembles the performance of a classical first-come-firstserved queue. In the following, we assume that the investigated node gets aware of a next hop's idleness with a probability of 10%, i.e., p = 0.1.

Underlying Markov Chain

The described GSPN can be mapped to the five-dimensional stochastic process X(t) = (S bu (t), S bd (t), S iu (t), O(t), O u (t)) , where 0 ≤ S bu (t) ≤ min(S, K), 0 ≤ S bd (t)≤min(S, K), 0≤S iu (t)≤S, 0≤O(t)≤K, and O u (t)∈{0, 1} are the number of tokens in places S bu , S bd , S iu , O, and O u , respectively, at time t ≥ 0. Note that S id (t)=S -(S bu (t)+S bd (t)+S iu (t)) , So(t)=K -(O(t)+S bu (t)+S bd (t)) , and O d (t)=1-O u (t) . Places R and F do not have to be considered because all states where R(t) > 0 or F (t) > 0 are vanishing due to enabled immediate transitions.

Since all involved random variables are exponentially distributed, X(t) constitutes a CTMC. We denote the state space of X(t) with X. Since X is both finite and irreducible, the CTMC is ergodic for all positive values of the arrival rate λ. From now on, the system is assumed to be in steady state, i.e., t → ∞. Due to space limitations and the high complexity of the underlying CTMC, we refrain from visualizing it here. We also refrain from giving equations for the size of X based on K and S which is a tedious combinatorial problem. Note that for a less complex model, this was achieved in [START_REF] Wüchner | Finite-source M/M/S retrial queue with search for balking and impatient customers from the orbit[END_REF].

Main Performance Measures

The stationary probabilities of the CTMC discussed in Sect. 3.2 are

P (s bu , s bd , s iu , o, o u ) = lim t→∞ P (S bu (t) = s bu , S bd (t) = s bd , S iu (t) = s iu , O(t) = o, O u (t) = o u ) .
The stationary probabilities can conveniently be derived using the software tool MOSEL-2 (see Sect. 4). Knowing the stationary probabilities, the main performance measures of the finite-source retrial queue can be obtained as follows:

-Mean number of tokens at operational servers S bu :

S bu = ∀(s bu ,s bd ,siu,o,ou)∈X s bu P (s bu , s bd , s iu , o, o u ) .
-Mean number of tokens at failed servers S bd : -Probability that all servers are down P S d :

S bd = ∀(
P S d = ∀(0,s bd ,0,o,ou)∈X P (0, s bd , 0, o, o u ) .
-Probability that orbit is down P O d :

P O d = ∀(s bu ,s bd ,siu,o,0)∈X P (s bu , s bd , s iu , o, 0) .
-Mean number of blocked active sources So b :

So b = ∀(0,s bd ,0,o,ou)∈X | β=1; ∀(s bu ,s bd ,siu,o,0)∈X | γ=1; (K -(s bu + s bd ))P (s bu , s bd , s iu , o, o u ) .
-Utilization of servers: ρ = S bu S . -Mean number of busy servers: S b = S bu + S bd .

-Mean number of tokens flushed on orbit failure: O f = ωO .

-Mean number of tokens at service or orbit:

M = S b + O .
-Mean number of active sources:

So = K -M .
-Probability that a specific source is blocked:

P b = So b
So .

-Mean number of unblocked active sources:

So a = So -So b .
-Overall arrival rate: λ in = λSo a .

-Departure rate of served tokens: λ s = µS bu .

-Departure rate of unserved tokens:

λ u = λ in -λ s .
-Probability of an incoming token getting served: P s = λs λin . -Mean waiting time: W = O λin . -Mean response time: T = M λin .

Numerical Results

Instead of deriving the underlying CTMC and solving the system of global balance equations manually, we directly formulate the GSPN shown in Fig. 2 using the Modeling, Specification and Evaluation Language (MOSEL-2). MOSEL-2's evaluation environment then derives the performance measures by automatic generation and numerical evaluation of the underlying CTMC. Due to space limitations, we refer the interested reader to [START_REF] Begain | Practical Performance Modeling -Application of the MOSEL Language[END_REF][START_REF] Wüchner | A brief introduction to MOSEL-2[END_REF] for details on MOSEL-2.

The corresponding MOSEL-2 model is available on request. The scalability of MOSEL-2 in the context of finite-source retrial queues is discussed in [START_REF] Wüchner | Homogeneous finite-source retrial queues with search of customers from the orbit[END_REF]. The validity of the proposed model can be shown by comparing its results in the case of a reliable orbit to numerical results obtained in [START_REF] Almasi | Homogeneous finite-source retrial queues with server subject to breakdowns and repairs[END_REF] and [START_REF] Wüchner | Modeling finite-source retrial queueing systems with unreliable heterogeneous servers and different service policies using MOSEL[END_REF] (both partly based on the Pascal program provided in [14, p. 272-274]), and [START_REF] Wüchner | Homogeneous finite-source retrial queues with search of customers from the orbit[END_REF]. For all comparable parameter settings, our results perfectly match the reference results.

Unless stated otherwise, the model parameters are chosen according to Tab. 4 in the following.

On the x-axis of all result graphs, the parameter α (sleep/awake ratio) is given. As already indicated in Tab. 4,

α = δ τ = τ -1 δ -1 , where τ -1 := τ -1 O = τ -1 Sb = τ -1
Si is the mean time the nodes are in power-saving mode, and

δ -1 := δ -1 O = δ -1 Sb = δ -1
Si is the mean time the nodes (investigated node and its idle or busy next hops) are awake. Hence, α is the proportion of time the investigated nodes are in power-saving mode. The higher α, the longer nodes sleep in comparison to the time they are awake and the less energy they use in the course of time. 5On the y-axis of the presented result graphs, we focus on the mean response time T , source blocking probability P b , and probability of getting served P s .

Influence of Sleep/Awake Ratio and Mean Awake Time

Fig. 3 shows the effect of modifying the sleep/awake ratio α (x-axis) and the mean awake time δ -1 (curves) on the mean response time T (y-axis).

Increasing the energy efficiency (sleep/awake ratio) clearly results in a higher mean response time. Increasing the mean awake time while keeping the mean sleep/awake ratio constant also increases the mean response time, because the sleeping time is a multiple of the awake time. Unfortunately, decreasing the mean awake time is not arbitrarily possible, since switching state often comes with additional overhead not (yet) handled by the model.

An important result is that accepting higher response times, i.e., increased delay tolerance, considerably eases the design of energy-efficient WSNs.

For sleep/awake ratio α ≈ 0, the probability that a node sleeps is very small. For all values of the mean awake time δ -1 , the mean response time T is then close to the processing time µ -1 ≈ 20ms of the next hop. Since the interarrival time λ -1 = 1min is very large in comparison to the processing time, the probability that at arrival of a new incident all next hops are busy is close to zero. Consequently, the probability for having to wait (and to retry) is also close to zero which results in a negligible waiting time.

In the following, we set the mean awake time to δ -1 = 50ms and discuss whether the mean response time can be decreased by dropping messaged from sleeping nodes.

Influence of Sleep/Awake Ratio and Message Dropping

Fig. 4 shows of the effect of the sleep/awake ratio α (x-axis) and incident message dropping by sleeping nodes φ = ω (curves) on the mean response time T (y-axis, top) and on the serving probability P s (y-axis, bottom).

It can be seen at the top of Fig. 4 that dropping stored incident messages from sleeping nodes significantly decreases the mean response time, even below the reliable case. This is because messages that are dropped may spend less time in the system than messages that are successfully served.

Therefore, we also need to have a look at the probability P s that an accepted incident message can be successfully processed. This is shown at the bottom of Fig. 4. Dropping stored messages clearly implies smaller serving probabilities. Therefore, dropping should be used for outdated messages only. However, the age of tokens cannot be considered by the presented model.

Note that even for α ≈ 0, i.e., the probability of the nodes being awake is close to 1, the serving probability is not necessarily close to 1. The serving probability also highly depends on the absolute value of the awake time since after each awake time, stored incident messages are dropped (regardless how short the sleep time is afterwards).

In Sect. 4.3, we aim at increasing the serving probability by blocking incoming messages when nodes are sleeping.

Influence of Sleep/Awake Ratio and Message Blocking

Fig. 5 shows the effects of the sleep/awake ratio α (x-axis) and of the message blocking β = γ (curves) on the mean response time T (y-axis, top), the serving probability P s (y-axis, middle), and the blocking probability P b (y-axis, bottom).

First, we discuss the serving probability shown in the middle of Fig. 5. Blocking incoming messages has a positive effect on the serving probability. For sleep/awake ratio α > 3, the effect of next-hop blocking ( ) has significantly more effect than node blocking ( ). In comparison to the non-blocking case (

), the following improvements can be observed:

-Some improvement ( ): Node blocking prevents arriving messages from being dropped immediately when the node is in power-saving mode and immediate forwarding is not possible due to busy or sleeping next hops at the same time.

-Good improvement ( ): If next-hop blocking is enabled, messages do not join the node when no next hop is accepting messages. This reduction of the number of messages stored at the node increases the serving probability, since all stored messages are dropped later with a high probability.

-Best improvement ( ): The combination of both blocking mechanism results in the best improvement of the serving probability. Focusing on the two best cases with respect to the serving probability (nexthop blocking is enabled, curves and ), we now discuss which is the better alternative regarding the mean response time given at the top of Fig. 5.

Curve refers to the case when node blocking is disabled. As seen before, the serving probability drops significantly when the sleep/awake ratio is increased, because it is more likely that a message needs to wait in the node and hence may be dropped if storage gets disabled before an operational and free next hop is found. Since dropped messages tend to stay less time in the system than served messages, the mean response time decreases.

In the scenario of curve , the probability that an incoming message gets immediately dropped is higher than in the scenario of curve , where this situation is not possible due to node blocking. Curve follows the same behavior as for small sleep/awake ratios (α < 0.5) but is then dominated by another effect that can be explained as follows. Messages are only accepted when they can at least be stored locally. Hence, if they cannot be forwarded immediately on arrival, they will (in contrast to scenario

) always experience waiting time. Additionally, since the nexthop nodes follow the same sleep/awake ratio as the investigated node, stored messages have to wait longer before being successfully transferred to an available next hop with increasing sleep/awake ratio.

Hence, while is more attractive than with respect to the serving probability, it is less attractive regarding the mean response time. Moreover, it can be seen at the bottom of Fig. 5 that has a significantly lower probability of blocking incoming incident messages than . We can therefore conclude that next-hop blocking is more attractive than node blocking. It should be noted, however, that next-hop blocking is relying on local knowledge about the next hops' state. How this knowledge can be obtained in a self-organized manner and which overhead might come with this is not yet covered by this paper.

Conclusions

A generalization of finite-source retrial queueing systems is studied. In addition to unreliable servers, the model can be used to evaluate the effects of an unreliable orbit. The model is used to discuss the trade-off between energy efficiency and performance in a wireless sensor network use case. The model evaluation is carried out using the MOSEL-2 tool. The numerical results are discussed in detail and show the positive and negative effects of message dropping and message blocking.

Our future work aims at finding self-organized mechanisms to provide the sensor nodes with the necessary local knowledge. We also need to discuss in more detail how single-node results can be aggregated suitably to evaluate multiplehop scenarios and larger network topologies. Validation of model results by comparison with test-bed results is considered. Finally, the presented model should assist in developing energy-efficient and self-organizing lightweight communication protocols for wireless sensor networks.

Fig. 1 .

 1 Fig. 1. WSN example scenario.

Fig. 2 .

 2 Fig.2. GSPN of finite-source retrial queue with unreliable servers, unreliable orbit, and orbital search.

Fig. 3 .

 3 Fig.3. Effect of sleep/awake ratio α (xaxis) and mean awake time δ -1 (curves) on mean response time T (y-axis).

Fig. 4 .

 4 Fig. 4. Effect of sleep/awake ratio α (xaxis) and message dropping φ = ω (curves) on mean response time T (y-axis, top) and on serving probability Ps (y-axis, bottom).

Fig. 5 .

 5 Fig. 5. Effect of sleep/awake ratio α (x-axis) and message blocking β & γ (curves) on mean response time T (y-axis, top), serving probability Ps (y-axis, middle), and blocking probability P b (y-axis, bottom).

Table 1 .

 1 Main model parameters.

	Parameter	Symbol Range
	Number of sources	K	N
	Number of servers	S	N
	Number of repairmen	S R	N
	Arrival rate	λ	R +
	Service rate	µ	R +
	Retrial rate	ν	R +
	Search probability	p	(0, 1)
	Busy server breakdown rate	δ Sb	R +
	Busy server repair rate	τ Sb	R +
	Idle server breakdown rate	δ Si	R +
	Idle server repair rate	τ Si	R +
	Orbit breakdown rate	δ O	R +
	Orbit repair rate	τ O	R +
	Sources blocked (servers down) 2	β	0, 1
	Sources blocked (orbit down) 2	γ	0, 1
	Server hopping 2	σ	0, 1
	Server flushing 2	φ	0, 1
	Orbit flushing 2	ω	0, 1

Table 2 .

 2 Places used in Fig.2with capacity (column "Cap.") and initial marking (column "i.M.").

	ID	Description	Cap. i.M.
	So	Active sources	K	K
	R	Incoming requests	1	0
	S bu Servers, busy & up	S	0
	Siu Servers, idle & up	S	S
	S bd Servers, busy & down S	0
	S id Servers, idle & down S	0
	O	Orbit	K	0
	Ou	Orbit up	1	1
	O d	Orbit down	1	0
	F	Finished requests	1	0

Table 3 .

 3 Transitions used in Fig.2.

	ID Type 3 Description	Value
	t1	E	Request generation	IF (β = 0 OR (S id + S bd < S)) AND
				(γ = 0 OR Ou = 1): λSo
	t2	I	Incoming request to server PRIO 1
	t3	E	Service	µS bu
	t4	I	Served and no orbital search WEIGHT 1 -p
	t5	I	Incoming request to orbit	PRIO 0
	t6	E	Retrial	IF Ou = 1: νO
	t7	I	Served and orbital search	IF Ou = 1: WEIGHT p
	t8	E	Busy server breakdown	δ Sb S bu
	t9	E	Busy server repair	τ Sb min(S bd , S R )
	t10	I	Server hopping on failure	IF σ: PRIO 1
	t11	I	Server flushing on failure	IF φ: PRIO 0
	t12	E	Idle server breakdown	δ Si Siu
	t13	E	Idle server repair	τ Si min(S bi , max(0, S R -S bd ))
	t14	E	Orbit breakdown	δ O
	t15	E	Orbit repair	τ O
	t16	I	Orbit flushing on failure	IF ω AND Ou = 0

Table 4 .

 4 Default parameters based on use case.

	Parameter

  s bu ,s bd ,siu,o,ou)∈X s bd P (s bu , s bd , s iu , o, o u ) . (s bu ,s bd ,siu,o,ou)∈X oP (s bu , s bd , s iu , o, o u ) .

	-Mean number of tokens at the orbit O:
	O =

∀

The parameter value 0 refers to false/off/disabled, the parameter value 1 refers to true/on/enabled.

Type of transition: I: immediate transition ⇒ column Value denotes priority (PRIO) or weight (WEIGHT); E: timed transition ⇒ column Value denotes firing rate.

Unless otherwise stated, these values are used as a basis for numerical results presented in Sect. 4.

Note that in this paper we do not yet consider energy used by the process of switching between awake and sleep states.

This research is partially supported by the German-Hungarian Intergovernmental Scientific Cooperation (HAS&DFG, 436 UNG 113/197/0-1), by the New Hungary Development Plan (T ÁMOP 4.2.1./B-09/1/KONV-2010-0007), by the AutoI project (STREP, FP7 Call 1, ICT-2007-1-216404), by the ResumeNet project (STREP, FP7 Call 2, ICT-2007-2-224619), by the SOCIONICAL project (IP, FP7 Call 3, ICT-2007-3-231288), and by the EuroNF Network of Excellence (FP7, IST 216366).


Markus Fiedler

Patrik Arlos

Timothy A Gonsalves

Anuraag Bhardwaj
email: anuraagbady@gmail.com

Hans Nottehed

Time is Perception is Money -Web Response Times in Mobile Networks With Application to Quality of Experience

Keywords: Download time, interactive service, web service, throughput, user perception, file size, measurements, Quality of Experience

The number of mobile operators providing Internet access to end users is growing. However, irrespective of the access network, we observe a distinct sensitivity of user perception to response and download times, in particular for interactive services on the web. In order to facilitate the choice of the right network for a given task, this paper presents a systematic study of web download time and corresponding throughput as a function of the file size. Based on measurement data from three Swedish mobile operators and a particular strategy of choosing file sizes, we find surprisingly simple, yet sufficiently accurate approximations of download times. These approximations are based on simple-to-measure parameters and provide valuable quantitative insights into the acceleration of HTTP/TCP/IP-based data delivery. The paper discusses the emergence of these approximations and related errors. Furthermore, it correlates the findings with Quality of Experience, thus building bridges between performance, user perception and provisioning issues.

Introduction

The success of interactive services depends on their responsiveness, as perceived by their users. Increasingly many such services are built from web services. These are using the HyperText Transfer Protocol (HTTP), running on top of the Transmission Control Protocol (TCP) and the Internet Protocol (IP), for exchanging data and configuration information in form of HyperText Markup Language (HTML) or eXtensible Markup Language (XML) files. This implies that the response time of a service is typically dominated by the download time of a corresponding HTML/XML document. The users find themselves at the end of service chains and have to wait until all the involved sub-services have executed and delivered their results, e.g. via an InforMation eXchange (IMX) [START_REF]Homepage[END_REF] that composes the information to be sent to the user.

We also observe that the number of service chains that include one or multiple mobile links is increasing. The simple exchangeability of mobile operators by replacing the SIM card in a USB dongle (or to switch between different dongles) has opened up new possibilities of choosing different operators if download times are perceived too long and/or throughput is felt to be insufficient. As waiting times increase, so does the risk that the user churns, i.e. leaves one operator for another that offers better performance, eventually entailing loss of revenue for the original provider. On the other hand, assigning more resources to a user increases cost for the provider. Thus, the latter needs to find a reasonable balance between user-perceived performance and cost.

This background motivates us to take a closer look at response times of HTTPbased downloads via different (in our case Swedish) mobile operators, and to relate them to user-perceived Quality of Experience (QoE) [START_REF]Vocabulary for performance and quality of service[END_REF][START_REF] Shaikh | Quality of Experience from user and network perspectives[END_REF]. The typical procedure to benchmark (mobile) networks is as follows: Large files are downloaded, the corresponding quasi-stationary throughput is calculated as amount of downloaded data divided by the download time, and the result is reported together with other performance measures such as round-trip times or jitter values [START_REF] Gonsalves | Comparison of AT-Tester with other popular testers for Quality of Service Experience (QoSE) of an internet connection[END_REF]. However, quasi-stationarity is preceded by a transient phase. TCPs startup behaviour [START_REF] Mellia | TCP model for short lived flows[END_REF][START_REF] Chakravorty | WWW performance over GPRS[END_REF] causes the transient throughput to approach the quasi-stationary throughput from below, which points at an acceleration of the download process. While being of minor interest for large files, the transient phase has a pronounced impact on the first few seconds of a file transfer [START_REF] Chakravorty | WWW performance over GPRS[END_REF], which is just in the order of magnitude of user patience [START_REF]The economic impacts of unacceptable web-site download speeds[END_REF] and thus deserves specific attention. The use of the quasi-stationary throughput to estimate download times during the transient phase will lead to over-optimistic and undesirable underestimations of the download time, and should thus be avoided. This paper presents an original study of the download time and corresponding throughput as functions of the size of the downloaded file, as seen by the end user that does not have any insight into specific parameters and conditions of the mobile network used. The corresponding approximations are simple to parameterise from online measurements on application level and simple to deploy. They provide a useful basis for deciding which operator to choose for particular communication situations, here transfers of files upto some Megabytes). Vice versa, the formulae can be applied by operators and providers to adjust the trade-off between user perception, provisioning and cost, respectively.

The remainder of the paper is structured as follows. Section 2 discusses related work. Section 3 introduces notations and definitions to be used throughout the paper and the setup of the measurements. Section 4 presents measurement results for three different operators, followed by subsequent analysis and classification. Section 5 proposes and evaluates three-and two-parameter approximation formulae for download times as function of the file sizes. Section 6 presents and discusses closed formulae relating QoE with file sizes through the presented approximation models. Section 7 concludes the paper and takes an outlook on future work.

Related Work

It has been recognised that users get the more distracted, the longer they have to wait [START_REF]The economic impacts of unacceptable web-site download speeds[END_REF][START_REF] Nielsen | Usability Engineering[END_REF]. Obviously, this implies a "negative impact on attitudes toward delay" [START_REF] Rose | Culture and consumer responses to web download time: a four-continent study of mono and polochronism[END_REF]. In particular, it has been recognised that user perception and rating quickly decrease during the first seconds of waiting [START_REF] Shaikh | Quality of Experience from user and network perspectives[END_REF][START_REF]Estimating end-to-end performance in IP networks for data applications[END_REF]. This effect can amongst others be modelled by differential equations [START_REF] Fiedler | A generic quantitative relationship between Quality of Experience and Quality of Service[END_REF][START_REF] Fiedler | Quality of Experience-related differential equations and provisioning-delivery hysteresis[END_REF], where the derivative of QoE with respect to the delay is negative. The resulting QoE-QoS relationships capture the effect of delays on QoE, typically described by negative-exponential [START_REF] Fiedler | A generic quantitative relationship between Quality of Experience and Quality of Service[END_REF][START_REF] Fiedler | Quality of Experience-related differential equations and provisioning-delivery hysteresis[END_REF][START_REF] Hoßfeld | Quantification of Quality of Experience for edge-based applications[END_REF] or logarithmic functions [START_REF]Estimating end-to-end performance in IP networks for data applications[END_REF][START_REF] Fiedler | Quality of Experience-related differential equations and provisioning-delivery hysteresis[END_REF].

Much work has been done on the performance of TCP, the underlying protocol for web transfers. However, the steady-state loss and delay performance and throughput are targeted in the majority of contributions, see e.g. [START_REF] Shaikh | Quality of Experience from user and network perspectives[END_REF][START_REF] Chen | Analysis of web response time in asymmetrical wireless network[END_REF][START_REF] Miyagi | Performance prediction method for web-access response time distribution using formula[END_REF][START_REF] Chan | TCP/IP performance over 3G wireless links with rate and delay variation[END_REF][START_REF] Voskarides | Practical evaluation of GPRS use in telemedicine system in Cyprus[END_REF]. For example, [START_REF] Chan | TCP/IP performance over 3G wireless links with rate and delay variation[END_REF] studies the impact of variable rate and variable delay on longlived TCP performance in a Third Generation (3G) mobile network. The study was based on traces from a 3G 1 X network taken around 2002, and simulation results based on the network simulator ns-2. Also, [START_REF] Voskarides | Practical evaluation of GPRS use in telemedicine system in Cyprus[END_REF] finds that the download time is proportional to the file size, which implies a constant throughput. The study employs a variable file size from some ten KB1 on. Reference [START_REF] Baccarelli | Minimization of download times of large files over wireless channels[END_REF] defines web objects as between 1 and 100 KB, and [START_REF] Mellia | TCP model for short lived flows[END_REF] states that average and median of the flow sizes are smaller than 10 KB.

Motivated by the latter observation, [START_REF] Mellia | TCP model for short lived flows[END_REF] addresses explicity the performance problems faced by short flows due to the start-up behaviour of TCP, and proposes an analytic model that explicity covers such short flows. The model is validated by simulations. No measurements in real environments are taken into account. The latter provide the ground for reference [START_REF] Chakravorty | WWW performance over GPRS[END_REF], according to our knowledge the only reference to study measurements of the ramping-up of TCP in a real mobile network. For GPRS, the duration of the slow start phase was found to last at least six seconds before the congestion window is expanded sufficiently in order to allow for approaching the quasi-stationary throughput. No further mobile technologies (3G etc.) were analysed. We conclude that a study of the impact of the file size on the download time and thus on QoE, based on measurements on contemporary mobile networks and compiled into easy-to-deploy formuale, is missing. This paper closes the gap.

Notations, Definitions and Setup

We will now introduce the variables to be used throughout the paper; the size of the file to be downloaded X ; the download time T ; and the perceived throughput on application level R, with the corresponding binary logarithms interrelated through:

lb(R/bps) = lb(8 X/B) -lb(T /s) = 3 + lb(X/B) -lb(T /s) .
(

) 1
In order to cover the whole range from small to large files, we increase the file sizes by factor two, starting from the smallest possible file size of one byte (just the end marker) in order to be able to see any particular behaviour for one-packet transmissions. We have chosen a maximal file size of 4 MiB, which comes closest to the file size of 3.7 MB used by the tool described in [START_REF] Gonsalves | Comparison of AT-Tester with other popular testers for Quality of Service Experience (QoSE) of an internet connection[END_REF]. Table 1 contains the classification of file sizes that will be used throughout the paper. Furthermore, we denote the quasi-stationary throughput that can be observed for very large files as R ∞ , amongst others shown by the tool [START_REF] Gonsalves | Comparison of AT-Tester with other popular testers for Quality of Service Experience (QoSE) of an internet connection[END_REF]. The setup used for the measurements is as follows: Host P, a PC with Windows XP connected to the mobile operators using a Huawei E220 USB modem, requests a file via HTTP (not FTP) from the Linux-based host S that is running an Apache web server. Host S is not publicly known, so all HTTP traffic destined to S originates from P, and disturbances caused by competing traffic are avoided. For each file size as specified in Table 1, fourty subsequent downloads are performed (j = 1 . . . 40) without caching the file, before moving to the next file size (i = i + 1). The download time for file size i and replication j, defined as T j (i), is obtained through time stamp T s j (i) just before retrieving the file using the get function found in the Perl module LWP::Simpe. Completion of the transfer triggered a new time stamp T e j (i). From this, we calculate T j (i) = T e j (i) -T s j (i) and the throughput R j (i) = X(i)/T j (i) according to [START_REF]Homepage[END_REF].

Label Size X(i) = 2 i B Range of i S 1 B . . .
Three Swedish mobile operators are considered, denoted by A, B and C, each of them offering HSDPA (High-Speed Downlink Packet Access). Taking the role of an end user, no specific insights into configurations and load conditions of the mobile networks were available. The experiments were conducted during December 2009 during business days. All units were stationary during the tests, and no obvious network congestion was obverved during the series of tests.

Median values of download time and throughput

Typically, the spread of the distribution of R j (i) over j is quite small. In 20 out of a total of 2640 measurements, we observed download times exceeding their neighboring values by up to ten seconds. This effect is rather common and discussed a.o. in [START_REF] Arlos | Influence of the packet size on the one-way delay on the down-link in 3G networks[END_REF]. As these extraordinary long download times have a significant impact on the average, we use the median (and skip that notion frequently for sake of brevity).

The quasi-stationary throughput per operator was approximated by the median of the throughput obtained for the largest investigated file size of 4 MiB, i.e. R ∞ = R med (22). The corresponding values are given in Table 2, accompanied by average m R , standard deviation s R and cofficient of variation c V . Furthermore, the median of a set of round-trip time measurements RTT med performed with the tool [START_REF] Gonsalves | Comparison of AT-Tester with other popular testers for Quality of Service Experience (QoSE) of an internet connection[END_REF] is shown. Obviously, operator A provides the highest quasi-stationary throughput in combination with the smallest relative variation, while the reverse holds for operator C. Operator B, which is actually sharing the 3G network infrastructure with operator A, yields a considerably lower throughput than operator A with comparable relative variation, despite of quite similar RTT values.

Op. R∞/bps lb(R∞/bps) mR( 22 Figure 1 provides a first impression on the median of the download time obtained from the three different operators. For small files, the download time is quite independent of the file size, with fastest delivery provided by operator C, followed by B and A. A discontinuity is observed for operator A: For very small sizes (X ≤ 32 B), the download time is found between 1 s and 1.2 s, while it then drops to values between 0.25 s and 0.38 s for 64 B ≤ X ≤ 1 KB, which means that small packets may take more time than large packets to get delivered, an observation also reported and discussed in [START_REF] Arlos | Influence of the packet size on the one-way delay on the down-link in 3G networks[END_REF]. For medium-sized files, the download time is growing with the file size for all operators, however with different gradients. Operator B initially displays the longest download times. From around 20 KB on, operator C takes most time to deliver the file. Operator A provides fastest delivery for files larger than 30 KB. For large files, the order of delivery is operator A, followed by operators B and C. As particular examples, we are taking a closer look at the medians of download times T med and throughputs R med provided by operator B, accompanied by error bars indicating the asymmetrical span between maximum and minimum of the 40 contributing values. From figures 2 and 3, we can see three areas in which T med and R med are almost linear in log-log representation. This is illustrated piecewise by linear regressions and points at power-type relationships between download time, throughput and file size, respectively. Quite similar behaviours are obtained for operator A and C, cf. Figure 1. For small files, cf. Table 1, the download time is practically constant, and consequently, the throughput grows proportionally with the file size. For large files, we observe saturation of R med . Its logarithm shows a quite weak, yet linear dependence on lb(X/B), while lb(T med ) grows in almost the same manner as lb(X/B), with a gradient around 1.

For medium-sized files, both lb(T med ) and lb(R med ) raise in a similar fashion, with a gradient around 1/2. Obviously, we are facing a transision area in which both download time and throughput grow as the file size grows, which indicates acceleration while downloading due to TCP start-up. The throughput has not reached its quasi-stationary value yet, which implies that the real download time is higher than any estimation that builds upon the quasi-stationary value R ∞ .

Regressions

We now construct linear least-square regressions on the logarithms of X, T and R for the areas S, M and L for all operators of the types

lb( T /s) = a T lb(X/B) + b T ; ( 2 ) lb( R/s) = a R lb(X/B) + b R ;
( 3 ) and evaluate the coefficient of determination R 2 [START_REF] Shaikh | Quality of Experience from user and network perspectives[END_REF], which mostly signals good matches (R 2 → 1) with exception of some weak trends (a → 0). 3. Regressions for T and R.

Table 3 shows the obtained regressions. As expected from (1), we observe for each operator and file size class a T + a R = 1 and b T + b R 3. A closer look at the results provides the following insights. For small files, the download time regression for operator A has a coefficient a T < 0, which is due to the abovedescribed discontinuity. For the other operators B and C, there is hardly any dependence of the download time on the size for small files (a T 0). For mediumsizes files, the coefficients a T and a R are found close to 0.5, which has shown to be the key for the approximation presented in the next section. For large files, operator C shows an unexpected negative trend in the throughput, seen from a R < 0. The other two operators show slightly increasing trends (0 < a R < 0.1), i.e. the throughput still rises sligthly as the file size increases.

Download Time Approximations

The regressions shown in Figure 2 suggest the use of maximum of the three approximations T = max{ T S , T M , T L } (4)

to estimate the download time. The components of (4) belong to the different regimes of file sizes as defined in Table 1 and are given as follows:

-For small files T S = const.

(

The time T S needed to send a one-packet file depends on the operator. -For medium-sized files

T M /s = 8 X/B R ∞ /bps aT . ( 6
)
This part builds upon the observation that b R a T lb(R ∞ /bps), cf. tables 2 and 3. For a T = 0.5, the general power-type relationship (6) reduces to a simple square-root formula, which reminds of an accelerated movement with constant acceleration a in which the time to reach a distance s is given by t = 2s/a. Translated to our case (s = X), the acceleration of the file transfer would amount to a = R ∞ /32 bps. -For large files

T L /s = 8 X/B R ∞ /bps . ( 7
)
The motivation for this part of the approximation is found in the observation a T → 1 and a R → 0 in Table 3, i.e. the throughput is almost constant and can thus be approximated by R ∞ .

Obviously, the approximation depends on three parameters:

1. the one-packet download time T S to be measured from downloading files of a typical size (e.g. 1 KB);

2. the quasi-stationary throughput R ∞ obtained from downloading large files of several MB and taking the median of the measured values; and 3. the acceleration factor a T obtained from downloading a sequence of mediumsized files, followed by the regression (2).

The three-parameter approximation can be simplified by letting a T = 0.5, which fits operators A and B almost exactly and operator C approximately (a T 0.625). This leaves us with two parameters T S and R ∞ .

We will now investigate the approximation errors, given as the difference of approximated and measured median of the download time

e T (X(i)) = T (X(i)) -T med (X(i)) (8)
and seen from Figure 4. Positive values of e T (X(i)) mean that the approximation overestimates the download time for the given operator and file size X(i). For small files, the only significant deviation is seen for operator A due to the discontinuity mentioned above. For medium-sized files, the approximation estimates on the safe side. The deviations are less than one second for operators A and B, while the two-parameter approximation for operator C displays a steady drift towards two seconds. The performance of the three-parameter approximation for operator C is comparable to that of A and B until a file size of 128 KiB thanks to the better capture of the gradient in the log scale by the third parameter a T = 0.625. Upon reaching the area of large file sizes, a trend towards underestimations of no more than two seconds for operator A and one second for operator B is observed. The approximation for operator C is very conservative, overestimating the median by up to 13 s for a file size of 2 MiB, which indicates the need to use a refined value of R ∞ to better account for this domain. All errors vanish for a file size of 4 MiB, as this was the anchor point for R ∞ .

Links to Quality of Experience

In the following, we assume that we can quantify the QoE by employing a numerical linear Mean Opinion Score (MOS)-type scale from 5 (= excellent) to 1 (= unacceptable). We employ a logarithmic relationship between QoE (user rating) and QoS (response time) found in standard [START_REF]Estimating end-to-end performance in IP networks for data applications[END_REF] and recently re-confirmed a.o. by [START_REF] Shaikh | Quality of Experience from user and network perspectives[END_REF][START_REF] Reichl | The logarithmic nature of QoE and the role of the Weber-Fechner Law in QoE assessment[END_REF]. In our example, the numerical values stem from the case of a time scale of reference of 6 s and a mix of two user groups. They can (be) change(d) according to context and user expectations, as illustrated in [START_REF]Estimating end-to-end performance in IP networks for data applications[END_REF]. Starting from QoE = max{min{4.38 -0.9lb(T /s), 5}, 1}

and inserting the above results ( 5)-( 7), we arrive at QoE = ⎧ ⎨ ⎩ min{4.38 -0.9lb( T S /s), 5} for S max{min{1.68 + 0.9a T (lb(R ∞ /bps)lb(X/B)), 5}, 1} for M max{min{1.68 + 0.9(lb(R ∞ /bps)lb(X/B)), 5}, 1} for L [START_REF]Estimating end-to-end performance in IP networks for data applications[END_REF] As expected, the QoE decreases as file size and download time grow, and increases as throughput increases. However, the sensitivity of QoE to the parameters depend on the file size itself: Due to the acceleration behaviour, the sensitivity is smaller for medium-sized files than for large files. Figure 5 illustrates the QoE estimations from [START_REF]Estimating end-to-end performance in IP networks for data applications[END_REF], based on the three-parameter approximation and Table 2. The discontinuity for operator A is due to the change of domain between medium-sized and large files. Best QoE is reached for operator A, followed by operator C for files up to 30 KB. From then on, operator B provides the second-best perception. This paper presented a measurement-based study of download performance and approximations of download times and corresponding throughputs as functions of the size of the downloaded file. Through a specific strategy of choosing file sizes, employing a factor of two, we were able to see linear relationships between the logarithms of download time, throughput and file size for small, mediumsized and large files. From a subsequent analysis of the parameters of the approximations, we found surprisingly simple approximation formulae with reasonably tight error bounds for the download times. For the small-and medium-sized files that represent the majority of the web downloads and that yield download times in the order of user patience, we obtain an error bound of roughly one second in most cases. The formulae will help users and application providers to "choose the right network for the right task", alternatively to limit data sizes in order to keep download times of an acceptable level. Furthermore, it will help providers to choose the level of provisioning they would like to offer in order to yield a reasonable trade-off between quality and cost.

Besides of refinements of the proposed approaches and formulae, future work will include validation and parameterisation of the download time and throughput approximations for other access network technologies such as WLAN, ADSL and Ethernet. At this point, a deeper analysis of TCP traces and a quantitative comparison to the results obtained from the model proposed in [START_REF] Mellia | TCP model for short lived flows[END_REF] would be of interest. We will also study the impact of data loss and delay variation on the proposed approximations, as they will affect the quasi-stationary throughput. Finally, the practical applicability of the formulae to assess and implement network selection policies for seamless communications will be studied.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Median of the download time T med via different operators versus file size X.

Fig. 3 .

 3 Fig. 3. Median of the perceived throughput R med via operator B versus file size X, with error bars and potential regressions.

Fig. 4 .

 4 Fig. 4. Estimation errors for different operators.

Fig. 5 .

 5 Fig. 5. QoE estimations versus file size X for different operators.

Figure 5

 5 Figure 5 also shows that, in order not to challenge user patience beyond feasibility (i.e. keep the QoE above 3), downloaded files should not be larger than approximately 120 KB for operator A, 70 KB for operator B and 60 KB for operator C, respectively.

Table 1 .

 1 1 KiB 0 . . . 10 M 2 KiB . . . 256 KiB 11 . . . 18 L 512 KiB . . . 4 MiB 19 . . . 22 Classification of file sizes.

Table 2 .

 2 )/bps sR(22)/bps cV(22) RTT med /ms Quasi-stationary throughput estimations and round-trip measurements for different operators.

	A 949584	19.9	935374	38594	0.04	125
	B 530114	19.0	530987	28409	0.05	130
	C 311365	18.3	323128	43934	0.13	336

1 KB = 1000 B, 1 MB = 1000 KB; 1 KiB = 1024 B, 1 MiB = 1024 KiB; we will use the appropriate factor depending on the context

Acknowledgements

The authors would like to thank the Swedish Agency for Innovation Systems, VINNOVA, for sponsoring this work through the EViMonA project (d-nr 2007/ 02505). They are also grateful to the Indian-Swedish project that supported the collaboration, and in particular Prof. Ashok Jhunjhunvala and Prof. Sara Eriksén for their great effort and commitment.


Angelo Coluccia
email: coluccia@ftw.at

Fabio Ricciato
email: ricciato@ftw.at

Peter Romirer-Maierhofer

Bayesian Estimation of Network-wide Mean Failure Probability in 3G Cellular Networks

 we derived a simple but robust sub-optimal estimator, called EPWR, based on the weighted average of individual (per-user) failure probabilities. In this follow-up work we tackle the problem from a different angle and formalize the problem following a Bayesian approach, deriving two variants of non-parametric optimal estimators. We apply these estimators to a real dataset collected from a real 3G network. Our results confirm the goodness of the proposed estimators and show that EPWR, despite its simplicity, yields near-optimum performance.

Introduction

The users of a third-generation (3G) mobile network generate various types of activity. Consider the following events: transmission of IP packets, opening of Transport-and Application-layer connections (i.e., envoy of TCP SYN packets and HTTP GET commands), activation of phone call, SMS envoy, data connection and signaling procedures (Attach Request, Location Area Update, Authentication Request, Paging etc.). All such events have in common two characteristics. First, each event is naturally associated with an individual user in the mobile network: the caller (for outgoing calls) or the callee (for incoming ones), the sender (for uplink packets) or the receiver (for downlink packets). Second, each event has a binary outcome: success or failure. The term "failure" can take on different meanings depending on the type of event: for packets, failure can represent the missed delivery (e.g. due to queue loss or corruption by link-level errors) or late delivery after a delay threshold.

Generally speaking, failures can be caused by the unavailability of some resource -e.g. due to exhaustion by too many concurrent requests -or by its unreachability. The involved resources can be shared -e.g., the GGSN or a Core Network linkor dedicated to individual users -e.g. a dedicated radio channel, or the receive buffer inside the terminal itself. The failure probability experienced by each individual user will be affected by the availability and reachability of both the shared and dedicated resource components.

Even if the status of shared resources is good, user-specific conditions can severely impact the individual failure probability: for example, a user with poor radio link will experience a high rate of packet losses, while a terminal configured with a wrong Access Point Name (APN, ref. [START_REF] Kaaranen | UMTS Networks -Architecture, Mobility and Services[END_REF]) will have all its PDP-context activations rejected. On the other hand, failures affecting multiple users at the same time often indicate a problem and/or overload in the shared section. Therefore, monitoring the incidence of failures across users is of great importance for the operation and troubleshooting of the network infrastructure.

Network equipments typically maintain logs and/or counters of attempts and failures, from which synthetic indicators are derived -often called Key Performance Indicators (KPI). Failures (and successes) can be also measured by a passive monitor either from the observation of an explicit failure indication (e.g. a Negative ACK or reject message) or by the absence of an explicit success indication (e.g. positive ACK). One of the most common KPI is trivially the ratio between the total number of failures and the total number of attempts (or requests). Here we show that such simplistic approach has some fundamental limitations and does not work well in scenarios of practical interest. The problem arises when the individual rate of requests (calls, procedures, packets) varies wildly across users -a case that is typically encountered in real networks when the distribution of user activity is often heavy-tailed. In this work we formulate the problem in terms of Bayesian estimation and provide (two variants of) an optimal estimator. Furthermore, we compare its performance to a simpler estimator developed in a previous work [START_REF] Coluccia | On Robust Estimation of Network-wide Packet Loss in 3G Cellular Networks[END_REF], discussing the trade-offs between optimality and simplicity.

Problem formulation 2.1 System model

To preserve generality, we will adopt the term "REQUEST" to refer to a general resource access attempt -to avoid specific terms like packet, call, connection. Unsuccessful requests are referred to as "FAILURES". Each request is associated with one mobile "USER".

For a generic measurement timebin (e.g. 1 minute), let I denote the total number of active users for which at least one request was observed. In operational networks I is often quite large, from thousands to millions depending on the timebin duration. For every user i (i = 1 . . . I) we introduce the following variables:

n i is the total number of requests associated to i

(n i ≥ 1); -m i is the number of failures (0 ≤ m i ≤ n i ); -r i def = mi
ni denotes the empirical failure ratio for i;

a i the (unknown) failure probability for i (a i ∈ [0, 1]).

We denote by N def = i n i and M def = i m i respectively the total number of requests and failures across all terminals. To simplify the notation we will occasionally use the vectors

n def = [n 1 n 2 • • • n I ] T , m def = [m 1 m 2 • • • m I ] T and a def = [a 1 a 2 • • • a I ] T .
For the sake of mathematical tractability we assume independence between failures: each request for user i fails with probability a i independently from any other request of the same or other users. Therefore m i is the sum of n i Bernoulli trials with probability a i , and all m i 's are independent Binomial random variables:

m i ∼ B(n i , a i ) ⇒ E[m i ] = n i a i VAR[m i ] = n i a i (1 -a i ). (1)
Throughout the paper we assume that m and n have been measured in some way and serve as input for the problem at hand.

Goal definition

A central component of the model is that the (unknown) failure probabilities a i 's are regarded as i.i.d. random variables generated from a common underlying distribution p(a) with mean value

ā def = E[a].
Therefore it is natural to take ā as the summary indicator representative of "network-wide failure probability". In other words, we are interested in obtaining an estimator of the Mean Failure Probability ā from the measured vectors n and m.

The goodness of such an estimator can be evaluated against the following criteria:

-Optimality We consider only unbiased estimators and take minimum variance as the optimality criterion. In fact, when the estimate of ā is used for performance monitoring, lower variance (i.e., smaller statistical fluctuations) allows better discrimination of change-points and/or trends. -Generality In passive monitoring the vector n is given and can not be controlled.

Typically, the traffic volume is distributed very unevenly across users, often with long-tails. Moreover, the traffic distribution change across time, following daily or weekly cycles and long-term trends in user activity (see e.g. [4, §VI-A]). Therefore we seek a robust estimator that does not rely on specific assumptions about (the distribution of) n nor requires manual re-tuning when the distribution changes. -Simplicity The ideal estimator should be easy to implement, fast to compute and conceptually simple -as a matter of fact, methods which can be understood straightforwardly by practitioners are more likely to be adopted in practice.

Resolution Approach

In a previous contribution [START_REF] Coluccia | On Robust Estimation of Network-wide Packet Loss in 3G Cellular Networks[END_REF] we focused on a particular class of weighted estimators and casted the problem in terms of constrained optimization. We derived a very simple sub-optimal estimator, hereafter called Empirical Piecewise-linear Weighted Ratio (EPWR), which showed excellent performance in simulations. The EPWR involves a cut-off parameter θ to be set heuristically -we showed that it is not too sensitive to the exact value of θ as far as extreme settings (very small or very large) are avoided.

In this work we tackle the problem from a more theoretically-grounded perspective: following a formal Bayesian approach, we identify two estimators that are well suited for our purposes. Moreover, we compare the performance of the Bayesian estimators against the EPWR estimator derived in [START_REF] Coluccia | On Robust Estimation of Network-wide Packet Loss in 3G Cellular Networks[END_REF] plus two other simplistic estimators. The comparison is carried out on a sample dataset from a real operational network, based on data obtained with the METAWIN system [7].

Simple estimators

Hereafter we present two common estimators and highlight their limitations. In §3.3 we recall the EPWR estimator which was derived earlier in [START_REF] Coluccia | On Robust Estimation of Network-wide Packet Loss in 3G Cellular Networks[END_REF].

Empirical Global Ratio (EGR)

The Key Performance Indicator (KPI) most widely adopted by practitioners is simply the ratio between the total number of failures and the total number of requests across all users, formally:

S EGR def = I i=1 m i I i=1 n i = M N . (2)
We refer to such quantity as the Empirical Global Ratio (EGR). It can be seen that S EGR is indeed an unbiased estimator for the mean failure probability:

E[S EGR ] = I i=1 E[E[m i |a i ]] I i=1 n i = I i=1 n i E[a i ] I i=1 n i = ā
It is worth remarking that S EGR is the simplest estimator to implement in practice. In fact, it does not require knowledge of the full vectors n, m (each composed of I elements) but only of two global counters N and M . Therefore, it does not require the measurement platform to associate requests and failures to individual users. Intuitively, the problem with S EGR is the presence of few users with very high traffic (large n i ) that occasionally inflate the value of eq. ( 2), thus increasing the estimator variance. One possible approach to "correct" S EGR is to pick users with large n i as "outliers" and filter them out before computing the ratio in eq. ( 2). Such strategy has two drawbacks: for one, it requires an heuristically-tuned method to classify outliers. Second, filtering out "fat" users with large n i means discarding their sample estimates for ā -actually the most reliable ones -and for long-tailed n i 's the loss of information might not be negligible. In other words, the variance increase due to a lower number of reliable measurement samples will partially offset the reduction due to filtering.

Empirical Mean Ratio (EMR)

Note that the empirical loss ratio r i for each user i is an unbiased estimator of the mean failure probability ā, formally

E[r i ] = E E[r i |a i ] = E[a i ] = ā.
Therefore an intuitive summary indicator can be obtained as the arithmetic mean across all users:

S EMR def = 1 I I i=1 r i = 1 I I i=1 m i n i . (3)
We refer to such indicator as the Empirical Mean Ratio (EMR). From a system-level perspective, the implementation of S EMR is more costly than S EGR : in fact, it requires the measurement platform to count requests and failures separately for each user. The additional resource consumption (memory, processing) should be compensated by better accuracy of the estimation. However, S EMR is a sub-optimal estimator for ā. The problem lies in the fact that the variance of r i (conditioned to a i ) is inversely proportional to the number of packets n i , i.e. VAR[r i |a i ] = a i (1 -a i )/n i : intuitively, the larger the sample size, the better the accuracy of the estimate. Therefore, large variability of n i 's maps to large variability of the uncertainty (variance) of the individual estimates -a case of heteroscedasticity. In the simple arithmetic mean as in eq. ( 3), more accurate estimates (for large n i ) weight the same as poor ones (for small n i ), and if the number of low-traffic users is high they will drive up the overall variance. Similarly to S EGR , one possible "correction" for S EMR is to filter out (discard) the observations associated to low-traffic users and compute the ratio in eq. ( 3) only on the samples above a minimum sample size n i ≥ γ. Again, the drawback of such strategy is that a certain amount of information available in the data is simply discarded, which is a grossly suboptimal approach to the problem.

Empirical Piecewise-linear Weighted Ratio (EPWR)

We have seen that both S EMR and S EGR suffer respectively from small and large usersthe user size refers to its traffic volume n i -and that a simplistic workaround would be to just discard the measurements associated with the smallest or biggest users for S EMR and S EGR respectively. This approach involves a certain loss of information. Moreover, the decimation of samples works against the goal of reducing the uncertainty of the estimate. Therefore we are set to find a more clever strategy: instead of selectively discarding measurement samples based on their size, one can simply weight them differently. Following this idea, in a previous work [START_REF] Coluccia | On Robust Estimation of Network-wide Packet Loss in 3G Cellular Networks[END_REF] we have derived a simple sub-optimal estimator that takes the form of a weighted average of the r i 's:

S EPWR def = I i=1 w i r i (4)
with piecewise-linear weigths given by:

w i = x i I i=1 x i , x i = min(n i , θ) ∀i (5)
Such definition involves a single parameter θ that represents a sort of "cut-off" point dividing the users into two regions: those with n i < θ are weighted proportionally to their size n i , while those with n i > θ are weigthed equally -proportionally to θ. The analysis reveals that the optimal value of the cut-off parameter is given by θ

= ā-ā-σ 2 a σ 2 a , i.e.
it depends on the first two moments of the distribution of a. Notably the optimal setting does not depend on n, which is an advantage in applications where n varies in time.

Unfortunately, in practice the optimal value of θ cannot be identified since ā and σ 2 a are unknown. However it can be shown that the performances of S EPWR depend only weakly on the exact value of θ, provided that it falls in a "reasonable" intermediate range away from extreme values (very small or very large), indicating that an heuristically fixed value for θ would be sufficient to achieve near-optimal performance in most practical cases. This claim, supported by simulation results in [START_REF] Coluccia | On Robust Estimation of Network-wide Packet Loss in 3G Cellular Networks[END_REF], will be further confirmed by the numerical results presented below in §5.

Bayesian estimators

Since a is regarded as a random vector, we can apply Bayesian techniques, which provide a theoretically well grounded approach to the estimation problem at the cost of somewhat higher complexity of the resolution procedure. In this section we discuss different possible approaches under the common framework of Bayesian inference.

The structure of our problem is that of a Bayesian hierarchical model [START_REF] Lehmann | Theory of Point Estimation[END_REF]: the data m are described by a probability distribution whose parameters a are random variables themselves. The Bayesian approach requires to provide the a priori distribution p(a), which is unknown in our case. If p(a) were known, the optimal estimator for a would be obtained by following the classical Bayes' procedure, i.e. minimizing a Bayes risk. Two of the most common choices for the Bayes risk are the MAP (Maximum A Posteriori) criterion and the MMSE (Minimum Mean Square Error) criterion. In both cases the key element is the posterior distribution p(a|m), expressed by the Bayes' Theorem as: When p(a) is unknown, as in our case, it is possible to choose a parametric distribution family with unknown parameters for the prior, and to resort to a procedure called Empirical Parametric Bayes [START_REF] Lehmann | Theory of Point Estimation[END_REF]. The basic idea is quite simple: since the parameters of the prior distribution -called hyperparameters -are unknown, their estimates are used instead. It is then possible to derive a Bayesian estimator (MAP or MMSE) in the usual way. The estimation of the hyperparameters is preferably obtained via Maximum Likelihood (ML), although other techniques are sometimes used -e.g. Method of Moments [START_REF] Lehmann | Theory of Point Estimation[END_REF].

In some applications it is not clear which family of distributions should be adopted. In such cases, a well-established practice is to use the so-called conjugate prior, i.e. the prior distribution p(a) that results in a posterior distribution p(a|m) belonging to the same family. In our case, the conjugate prior corresponding to the Binomial distribution is the Beta distribution, with support in [0, 1], defined as:

p(a i ) = 1 B(α, β) a α-1 i (1 -a i ) β-1 i = 1, . . . , I (6)
where

B(x, y) = 1 0 t x-1 (1 -t) y-1 dt (7)
is the Beta function [START_REF] Abramowitz | Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables[END_REF]. The Beta distribution is quite general and flexible: it has two positive shape parameters α, β which allow for a great variety of shapes, ranging from uniform to U-shape, convex or concave, symmetric or skewed. Moreover, consider that Bayesian estimation is usually found to be robust against deviations from the ideal choice of the prior distribution family. The mean of a Beta distribution is given by

X ∼ Beta(α, β) ⇒ E [X] = α α + β (8)
The ML estimates of the hyperparameters are given by:

α, β def = arg max α,β p(m|α, β) (9)
where the marginal distribution p(m|α, β) is obtained by marginalization:

p(m|α, β) = 1 0 • • • 1 0 p(m, a|α, β) da 1 • • • da I . (10)
Due to independence, we can factorize the joint density function as follows:

p(m, a|α, β) = I i=1 p(m i , a i |α, β) = I i=1 p(m i |a i , α, β)p(a i ) = I i=1 n i m i a mi i (1 -a i ) ni-mi • 1 B(α, β) a α-1 i (1 -a i ) β-1
and recalling eq. ( 7) we can rewrite eq. ( 10) as follows:

p(m|α, β) = 1 0 • • • 1 0 I i=1 p(m i , a i |α, β) da i = I i=1 n i m i B(α + m i , β + n i -m i ) B(α, β) (11)
i.e., the marginal distribution of m is the product of I Beta-Binomial distributions BetaBin(n i , α, β). This expression can be used in eq. ( 9) to obtain the ML estimates of the hyperparameters. The solution cannot be expressed in closed-form and must be obtained numerically. Notably, the function ( 11) is unimodal (see [START_REF] Reeds | Compound Multinomial Likelihood functions are unimodal: proof of a conjecture of I[END_REF] for a proof) and its negative logarithm is convex -a consequence of the log-concavity of the likelihood function for Beta [START_REF] George | Conjugate Likelihood Distributions[END_REF] [8] -therefore standard numerical methods can be applied (e.g. the simplex method) which are likely to locate the optimum quickly and accurately.

Given the estimates of the hyperparameters, the posterior distribution

p(a i |m i , α, β) = p(m i , a i |α, β) p(m i |α, β)
is obtained in a similar way, and as expected is a Beta distribution (conjugate prior):

a i |m i , α, β ∼ Beta( α + m i , β + n i -m i ) (12)
The (empirical) Bayes estimator for the generic a i is then derived in the classical way by minimizing a Bayes risk. Two of the most common criteria are MAP and MMSE.

The MAP estimator maximizes the a posteriori probability:

âMAP i def = arg max ai p(a i |m i , α, β) = α + m i -1 α + β + n i -2 (13)
for i = 1 . . . I, as can be easily verified by taking the derivatives of log p(a i |m i , α, β) (ref. eq. ( 6) and ( 12)). From the denominator of eq. ( 13) we observe that the MAP estimator may lead to inconsistent values for small n i . This is a problem in network applications, where typically a considerable fraction of users generate only very few requests. Therefore the MAP estimator is not well suited for our purposes.

The MMSE estimator minimizes the mean squared error, and coincides with the conditional mean [START_REF] Lehmann | Theory of Point Estimation[END_REF]. Recalling eq. ( 8) we can write:

âMMSE i def = E a i m i , α, β = α + m i α + β + n i for i = 1 .
. . I, and by taking the arithmetic mean we obtain the following estimator:

Q MMSE def = 1 I I i=1 âMMSE i = 1 I I i=1 α + m i α + β + n i . (14)
Otherwise, an alternative approach is to estimate directly ā from eq. ( 8) with the ML estimates of the hyperparameters:

Q HYP def = α α + β (15)
where the subscript "HYP" indicates that the estimator is obtained solely from the hyperparameters' estimates, without the posterior information m. Note that in both cases the α, β are estimated from the data vector m, n: the difference between the two estimators lies in the fact that Q MMSE is suboptimal -because it heuristically adopts an arithmetic mean -but uses the posterior information m for both parameters and hyperparameters, while Q HYP is optimal in the ML sense but uses the posterior information only for estimating the hyperparameters and not ā. Despite such difference, we found that Q MMSE and Q HYP always lead to extremely similar values when applied to our real datasets, as discussed later in §5.

Finally we remark that both estimators require a numerical procedure to be computed. However the shape of the objective function (unimodal, convex) allows the use of fast and accurate numerical methods -for the sake of space we do not provide here further details of the implemented numerical procedure. Nonetheless, the computational gap with S EPWR remains large: in a MATLAB simulation with I = 10 5 users, the computation time of Q MMSE and Q HYP is about 10 seconds on a standard computer (Core2 Duo 2Ghz), against a few milliseconds of S EPWR .

GGSN

Numerical Results from Real Datasets

In the previous sections we have presented three sub-optimal estimators, very simple to implement and to compute -S EGR , S EMR and S EPWR -and derived two Bayesian estimators -Q HYP and Q MMSE -which are more complex but optimal given the problem model at hand. Hereafter we compare their performance on a real dataset.

Our dataset is based on measurements collected from an operational 3G cellular network by the METAWIN system [7]. The measurement setting is sketched in Fig. 1: a passive monitor located on the Gn interface near the GGSN observes the TCP traffic in both directions (for more details on 3GPP network architecture refer e.g. to [START_REF] Kaaranen | UMTS Networks -Architecture, Mobility and Services[END_REF]). We aim at revealing congestion and/or other performance glitches in the network section between the monitoring point and the mobile terminals from the observation of TCP handshaking packets between mobile clients and Internet-side servers. To this purpose we collect two datasets: DATA:INV and DATA:RTT.

In DATA:INV we count for each mobile station i all SYNACK packets flowing in downlink (variable n i ) as well as the number of them which failed to be unambiguously associated to a corresponding uplink ACK (variable m i ). Such definition includes those cases where either the SYNACK or the corresponding ACK were lost in the network section from the monitoring point to the mobile terminal, but also other cases not necessarily related to loss events. For example, when two or more identical SYNACKs are observed but only one ACK (between the same end-points) the SYNACK-to-ACK association remains ambiguous, i.e. it is not possible to decide which one of the SYNACK triggered the ACK 3 . In other words, the SYNACK packet in downlink denotes a "request" event, and the presence [resp. lack] of an unambigously corresponding ACK packet in uplink denotes the "success" [resp. "failure"] event.

A second dataset DATA:RTT was obtained from the (semi-)RTT measurements: for each correctly (and unambigously) acknowledged SYNACKs, we measure the clientside RTT, i.e. the elapsed time between the timestamps of the SYNACK and the corresponding ACK. For this dataset, we mark a "failure" event when the RTT exceeds a fixed threshold T -we set T = 0.5 sec and T = 1.5 sec respectively for UMTS/HSPA and GPRS/EDGE. For more details about the measurement setting see [START_REF] Peter Romirer | Network-Wide Measurements of TCP RTT in 3G[END_REF].

The rationale for extracting such measurements is that congestion in the downlink path towards the terminals (e.g. at some SGSN or RNC) would expectedly result in an increase of downlink packet loss and/or delay, and therefore should be reflected in a increase of the "failure" rate in DATA:RTT and/or DATA:INV. Note that serious connectivity problems in the Radio Access Network might impede even the transmission of uplink SYN packets, which would translate into a reduction of SYNACK -i.e. we would observe missing rather than unacknowledged SYNACKs. While in principle such kind of events could be revealed by monitoring the absolute number of SYNs and corresponding SYNACKs, this aspect is left outside the scope of this work.

The measurements are binned in 5 minutes intervals. For this work we consider a measurement period of one week collected in August 2010. The analysis was conducted separately for UMTS/HSPA and GPRS/EDGE users, but for the sake of space we report only results for UMTS/HSPA. The time-series computed with different estimators are reported in Fig. 2 and Fig. 3 respectively for DATA:INV and DATA:RTT datasets. We found that Q HYP and Q MMSE always lead to almost identical results, with only negligible differences in a few timebins -for this reason and for the sake of space we report only the time-series of Q MMSE and skip the graphs for Q HYP . From Fig. 2 and Fig. 3 we first observe that S EGR exhibits larger fluctuations (higher variance) and occasionally large spikes due to the sporadic presence of heavy users (high n i ) with many failures 4 (high m i ). Second, both S EMR and S EPWR perform quite close to the optimal reference Q MMSE . To dig further, we resorted to the inspection of the scatterplots S EMR , Q MMSE and S EPWR , Q MMSE (not shown here) which revealed that S EPWR correlates slightly better than S EMR to the reference Q MMSE values: in DATA:INV the Pearson the correlation coefficient is 0.997 and 0.954 respectively for S EMR , Q MMSE and S EPWR , Q MMSE , while in DATA:RTT S EMR exhibits a larger bias.

Conclusions

So called Key Performance Indicators (KPI) play an important role in the operation of real mobile networks, as they provide a synthetic view of the network-wide status and quality. A large class of network events can be modeled as binary REQUESTS associated to USERS (e.g. origin or destination entity) and having one of two possible outcomes, i.e. SUCCESS or FAILURE. For these, a very popular KPI is the ratio between the total number of failures to the total number of requests, regardless of per-user associations. We have shown that such simplistic KPI -referred to as EGR in this work -suffers from the presence heavy-users. The problem is of practical relevance in real networks, where the distribution of requests across users is often heavy-tailed. In some cases, the variability of EGR makes it useless for any practical exploitation.

To overcome the limitations of EGR, network operators should adopt more robust KPIs based on separate counts of success and failures per individual users. The problem is then how to make the best possible use of such data.

We have introduced a system model that motivates the adoption of the Mean Failure Probability (MFP) as a natural KPI. Since MFP is unknown, it must be estimated from the observed data. We have shown that EGR can be considered an unbiased estimator for MFP, but not the optimal one. In a previous work we had derived a more robust estimator, namely the EPWR, very simple to implement, that involves a free parameter to be tuned heuristically. In this paper we have formalized the problem in terms of Bayesian estimation, deriving two Bayesian estimators which are provably optimal (in two different senses) given the system model. The analysis of two real datasets from an operational 3G mobile network has confirmed that all the proposed estimators are considerably more stable than EGR, and that EPWR performs very closely to the optimal reference provided by the Bayesian solution.

Our estimators can be adopted by network operators and/or equipment vendors as robust KPI. Owing to the generality of the system model, and to the abstract definition of the notions of "request", "failure" and "user" therein, the concepts and estimators proposed in this work can be applied to a wide range of different measurements, in communication networks and other application domains.

  a) p(m, a) da where p(m, a) = p(m|a)p(a).

Fig. 1 .

 1 Fig. 1. Reference measurement scenario.

In[START_REF] Peter Romirer | Network-Wide Measurements of TCP RTT in 3G[END_REF] we showed that such cases are not infrequent in GPRS/UMTS networks due to the presence of "early retransmitter" servers, with initial retransmission timeout set to sub-second values in the same order of the Round Trip Time (RTT) in these networks.

The "spikes" in DATA:INV are due to mobile terminals receiving very high rate of SYNACKs to which they do not respond: they are likely involved in TCP scanning or SYN flooding.