Search

Ce chapitre traite des files d’attente fluides markoviennes à capacité finie ou infinie. Notre méthode d’analyse se fonde sur l’étude des probabilités de passage conditionnellement au niveau maximal atteint pendant une période d’activité. Elle aboutit au calcul du taux de perte et à une caractérisation de la distribution de la durée de congestion et d’information perdue pendant une telle période.

Stochastic fluid flow models and in particular those driven by Markov chains have been intensively studied in the last two decades. Not only they have been proven to be efficient tools to mimic Internet traffic flow at a macroscopic level but they are useful tools in many areas of applications such as manufacturing systems or in actuarial sciences to cite but a few. This chapter proposes to focus on such a model in the context of performance analysis of a potentially congested system. The latter is modeled by means of a finite-capacity system whose content is described by a Markov driven stable fluid flow. We step-by-step describe a methodology to compute exactly the loss probability of the system. Our approach is based on the computation of hitting probabilities jointly with the peak level reached during a busy period, both in the infinite and finite buffer case. Accordingly we end up with differential Riccati equations that can be solved numerically. Moreover we are able to characterize the complete distribution of both the duration of congestion and of the total information lost during such a busy period.

We use a fluid flow model with reactive bounds to analyse a data processing center with energy-aware servers. The servers switch between four energy states depending on the level of the buffer content and on three reactive bounds. Every state consumes different amounts of energy. We use a regenerative approach to calculate the stationary distribution of the system and the expected energy consumption.

We consider a fluid flow model with infinite buffer. We compute the Laplace-Stieltjes transform of the sojourn time proceeding in two steps. We first compute the stationary distribution of the buffer at arrival instants, using a change of clock. Secondly, we compute the transform of the time spent to empty the buffer. Numerical examples of sojourn time in a fluid flow are finally examined.

Thanks to the fact that Belgium is a densely populated country, and also lags behind in the roll-out of Long Term Evolution (LTE) / 4G, it is still possible to visit areas enjoying different Radio Access Technology (RAT) coverages within a limited territory. This paper reports an analysis of the dataset of web requests collected through a field survey mostly performed in south-western Belgium and northern France. This analysis highlights the impact of Radio Access Network (RAN) conditions (signal strength, mobility) and settings (timers) on the canvas Page Load Time (cPLT).

Thanks to the fact that Belgium is a densely populated country, and also lags behind in the roll-out of Long Term Evolution (LTE) / 4G, it is still possible to visit areas enjoying different Radio Access Technology (RAT) coverages within a limited territory. This paper reports an analysis of the dataset of web requests collected through a field survey mostly performed in south-western Belgium and northern France. This analysis focuses on the impact of the spreading of web sites across CDNs.

International audience

We explore the conditions under which a fluid queue is positive recurrent, null recurrent, or transient. We consider the simple system where fluid rates are independent of the level, and exploit the similarity found by Ramaswami between fluid queues and Quasi-Birth-and-Death (QBD) processes. Inspired by the Wiener-Hopf factorization obtained by Rogers for a key matrix, and by an earlier work by Latouche and Taylor on drift conditions for QBDs, we determine in this note two pairs of eigenvectors which combine to give four characteristic inequalities. This is illustrated on a simple example.

Average consensus algorithms have attracted increasing interest in the last decade because of their potential for use in high-density wireless sensor networks. This paper analyzes an algorithm that is based on a model of asymmetric broadcasting on a random geometric graph, in which nodes broadcast and listen only intermittently. We show that each node can easily estimate its update weight from the degree of silence in its neighborhood, and, after the weights have been assigned in this way, that the consensus algorithm converges to the true average. Both a synchronous and an asynchronous update model are analyzed.

We study the blocking probability in a Markovian bufferless queuing system with a finite number of servers when the packet arrival process is a Markov-modulated Poisson process (MMPP), a superposition of a finite number N of independent MMPPs. We present an algorithm to compute the blocking probability in the system. The algorithm is exact if some related Quasi-birth-and-death (QBD) processes are reversible. We prove that the complexity of our algorithm scales linearly with N, whereas that of the standard solution does it exponentially. We illustrate the use of our algorithm in a bufferless multi-server system receiving long-range dependent (LRD) input traffic. This problem finds applications in the study of the blocking probability in bufferless optical packet switching (OPS) and optical burst switching (OBS) networks. We emulate LRD traffic with an MMPP, a superposition of N independent ON/OFF sources, which are also MMPPs. Our algorithm is in this case approximative since the reversibility condition is not fulfilled with the proposed MMPP. An extensive numerical analysis suggests that our algorithm can accurately approximate the blocking probability in the original queueing system with LRD input traffic. We provide an insight into the reason why our approximation is accurate.

The extinction probability of a branching process is characterized as the solution of a fixed-point equation which, for a fairly general class of Markovian branching processes, is vector quadratic. We address the question of solving that equation, using a mixture of algorithmic and probabilistic arguments. We compare the relative efficiency of three iterative methods based on functional iteration, on the basis of the probabilistic interpretation of the successive iterations as well as on the basis of traditional rate of convergence analysis. We illustrate our findings through a few numerical examples and conclude by showing how they extend to more complex systems.

In this paper we present a stochastic network model for packet-switching networks with no buffering capabilities at the nodes. This model can be directly used in the study of all-optical packet-switching (OPS) and optical burst switching (OBS) networks without fiber delay lines (FDLs). Our model provides for the first time a complete description of the dependencies arising among packets from different sources in the network. Such dependencies originate when packets from different sources share a finite number of channels for their transmission through a network link. We relate our model to well-known loss network models for circuit-switching networks and derive expressions for the packet loss probability. We briefly show how our work can be extended to model parallel hybrid optical networks, and propose some promising future lines of work. Our numerical results suggest that the well-known Erlang fixed-point approximation (EFPA) overestimates the blocking probability when compared to our model predictions. They also show that our model is scalable up to network scenarios with at least 30 links with 160 wavelength channels per link. This makes the proposed model an interesting tool for studying the dependencies arising among packets in a realistically-sized OPS/OBS network without FDLs.

Continuous-time multi-type branching processes have applications in a large number of fields such as biology and telecommunication systems. A basic problem for this kind of processes is to determine the extinction probability and, in order to compute it, it is necessary to find the minimal nonnegative solution of a non-linear matrix equation. We consider here a particular family of branching processes called Markovian binary trees. These give rise to second-order equations and we apply Newton’s method for fixed-point equations. We show that this algorithm is well defined and converges quadratically in the domain of interest. We also give it a probabilistic interpretation in terms of the branching process itself.

We consider systems which exhibit a mixture of smooth behavior and occasional jumps, controlled by continuous-time Markovian processes on a finite state space, and we call these fluid queues with jumps, thereby emphasizing the fact that they constitute a generalization of fluid queues. We characterize their stationary distribution in an algorithmically tractable way by constructing an auxiliary fluid queue without jumps. We give a few examples to illustrate the procedure and we analyze in detail a buffer model where bursts of high priority traffic interrupt the transmission of low priority files.

This paper presents the Laplace transform of the time until ruin for a fairly general risk model. The model includes both the classical and most Sparre-Andersen risk models with phase-distributed claim amounts as special cases. It also allows for correlated arrival processes, and claim sizes that depend upon environmental factors such as periods of contagion. The paper exploits the relationship between the surplus process and fluid queues, where a number of recent developments have provided the basis for our analysis.

In our Web traffic model, http session requests occur according to a Poisson process and each request induces multiple transmissions of sub-documents, called objects. We use a transient MAP process to model the epochs at which the transmissions of objects associated to a given document are initiated. The lengths of transmission of the objects are modeled as i.i.d, random variables. We analyze the distribution of the total number of objects being in transmission at any given time and determine its auto-correlation function.

One primary purpose of introducing the phase-type planar point process was to offer an algorithmically tractable point process on the plane. In an attempt to achieve this objective, we describe here a powerful technique to obtain the distribution and the moments of the number of points generated by the process and located in a particular convex bounded Borel set of the plane. Applied to the case of the circle, this technique has enabled us to estimate the outage probability in a CDMA based wireless system. Furthermore, a numerical analysis of the second moment of the number of points in a circle is discussed. This analysis highlights among others some relevant asymptotic results and therefore ways to distinguish between the processes. The technique we derive here can be exploited in many different problems as illustrated in our conclusion.

The isotropic planar point processes of phase-type are natural generalizations of the Poisson process on the plane. On the one hand, those processes are isotropic and stationary for the mean count, as in the case of the Poisson process. On the other hand, they exhibit dependence of counts in disjoint sets. In a recent paper, we have proved that the number of points in a square window has a Poisson distribution asymptotically as the window is located far away from the origin of the process. We extend our work to the case of a window of arbitrary shape.

We consider a family of planar point processes which are a natural generalization of the two-dimensional Poisson process. In this family, points are located on a sequence of concentric circles centered at the origin; the radii of the circles are chosen through a phase-type construction, the points on each circle are uniformly distributed. These processes are called isotropic PH planar point processes for short. Although point patterns obtained in this fashion are very different from those of the Poisson process, nevertheless we show that if one considers the region of the plane far away from the origin, the PH processes exhibit some similarities to the Poisson process.

Quasi-Birth-and-Death Processes are useful tools for studying queuing systems. Of particular interest is the distribution of the first passage time to a certain level of congestion, a given number of customers in the queue, for instance. We present an algorithmic method based on a decomposition of the set of levels precedings the level of congestion, it aims to compute the two first moments of the time till congestion and it is well-adapted to the particular configuration of QBD process transition matrix.

International audience; In this work, we expose a clear methodology to analyze maximum level and hitting probabilities in a Markov driven fluid queue for various initial condition scenarios and in both cases of infinite and finite buffers. Step by step we build up our argument that finally leads to matrix differential Riccati equations for which there exists a unique solution. The power of the methodology resides in the simple probabilistic argument used that permits to obtain analytic solutions of these differential equations. We illustrate our results by a comprehensive fluid model that we exactly solve.

In this paper we analytically derive the sojourn time of a user accessing an online IPTV recording service. Basically, the system consists of a server (or server farm) and the bandwidth at which a user can download recorded files depends on the number of other concurrently downloading users. In particular, we consider both cases, one in which the user's download speed is limited by his own access bandwidth, whereas in the other case the server is the bottleneck and all downloading users share the server's upload capacity. Our model includes user impatience which depends on the actual download speed. A user may abort his download attempt if a threshold duration is exceeded. The file size distribution is obtained by measurements of offered files at an existing server.

We define the family of transient Markov arrival processes (transient MAPs) which combine features of transient (or terminating) renewal processes and of the well-known MAPs: transient MAPs are point processes on the line, controlled by a finite Markov chain, which almost surely comprise a finite number of points. We analyze their basic properties.

We deal with the uplink outage probability for a UMTS cellular network at a reference base station equipped with a smart antenna. Users are assumed to be distributed according to a planar Poisson point process. Their respective transmission rates are modeled by independent random variables. This leads to a compound Poisson process for the total data rate to be served in a cell by code division multiplexing. Outage occurs if the total rate exceeds the effective chip rate (3.84 MChip/s divided by the minimum required bit energy to noise power ratio). Circulant matrices, a normal approximation, and Monte Carlo integration are employed to determine the outage probability as a performance parameter of the system.

We assume that a base transmitter station (BTS) in a code division multiple access (CDMA) mobile network is equipped with a smart antenna. Each transmitting user is tracked by a beam of fixed width centered at the user. Mobiles are assumed to apply perfect power control such that each is received with the same unit power at the BTS. Under these assumptions outage occurs if the number of overlapping beams exceeds a certain threshold. The according probability is calculated under different random traffic models. Particularly homogeneous Poisson fields and isotropic planar phase processes are considered. The investigations are strongly related to the first hitting time in a M/D/∞ queue as well as object recognition for a photon detector.