Stationary Analysis of a Fluid Queue Driven by Some Countable State Space Markov Chain

Motivated by queueing systems playing a key role in the performance evaluation of telecommunication networks, we analyze in this paper the stationary behavior of a fluid queue, when the instantaneous input rate is driven by a continuous-time Markov chain with finite or infinite state space. In the case of an infinite state space and for particular classes of Markov chains with a countable state space, such as quasi birth and death processes or Markov chains of the G/M/1 type, we develop an algorithm to compute the stationary probability distribution function of the buffer level in the fluid queue. This algorithm relies on simple recurrence relations satisfied by key characteristics of an auxiliary queueing system with normalized input rates.      

Second order fluid models with general boundary behaviour

A crucial property of second order fluid models is the behaviour of the fluid level at the boundaries. Two cases have been considered: the reflecting and the absorbing boundary. This paper presents an approach for the stationary analysis of second order fluid models with any combination of boundary behaviours. The proposed approach is based on the solution of a linear system whose coefficients are obtained from a matrix exponent. A practical example demonstrates the suitability of the technique in performance modeling. This work is partially supported by the Italian-Hungarian bilateral R&D programme, by OTKA grant n. T-34972, by Italian Ministry for University and Research (MIUR) through PRIN project Famous and by EEC project Crutial.     

Markov Chains Competing for Transitions: Application to Large-Scale Distributed Systems

We consider the behavior of a stochastic system composed of several identically distributed, but non independent, discrete-time absorbing Markov chains competing at each instant for a transition. The competition consists in determining at each instant, using a given probability distribution, the only Markov chain allowed to make a transition. We analyze the first time at which one of the Markov chains reaches its absorbing state. We obtain its distribution and its expectation and we propose an algorithm to compute these quantities. We also exhibit the asymptotic behavior of the system when the number of Markov chains goes to infinity. Actually, this problem comes from the analysis of large-scale distributed systems and we show how our results apply to this domain.     

Stochastic Analysis of Rumor Spreading with Multiple Pull Operations

Methodology and Computing in Applied Probability - We propose and analyze a new asynchronous rumor spreading protocol to deliver a rumor to all the nodes of a large-scale distributed network. This...     

A fluid queue driven by a Markovian queue

We consider an infinite buffer fluid queue receiving its input from the output of a Markovian queue with finite or infinite waiting room. The input is characterized by a Markov modulated rate process. We derive a new approach for the computation of the stationary buffer content. This approach leads to a numerically stable algorithm for which the precision of the result can be given in advance. This revised version was published online in June 2006 with corrections to the Cover Date.     

A Finite Buffer Fluid Queue Driven by a Markovian Queue

We consider a finite buffer fluid queue receiving its input from the output of a Markovian queue with finite or infinite waiting room. The input flow into the fluid queue is thus characterized by a Markov modulated input rate process and we derive, for a wide class of such input processes, a procedure for the computation of the stationary buffer content of the fluid queue and the stationary overflow probability. This approach leads to a numerically stable algorithm for which the precision of the result can be specified in advance.     

Maximum Level and Hitting Probabilities in Stochastic Fluid Flows Using Matrix Differential Riccati Equations

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.     

Ascending Runs in Dependent Uniformly Distributed Random Variables: Application to Wireless Networks

We analyze in this paper the longest increasing contiguous sequence or maximal ascending run of random variables with common uniform distribution but not independent. Their dependence is characterized by the fact that two successive random variables cannot take the same value. Using a Markov chain approach, we study the distribution of the maximal ascending run and we develop an algorithm to compute it. This problem comes from the analysis of several self-organizing protocols designed for large-scale wireless sensor networks, and we show how our results apply to this domain.     

Moments’ Analysis in Homogeneous Markov Reward Models

We analyze the moments of the accumulated reward over the interval (0,t) in a continuous-time Markov chain. We develop a numerical procedure to compute efficiently the normalized moments using the uniformization technique. Our algorithm involves auxiliary quantities whose convergence is analyzed, and for which we provide a probabilistic interpretation.     

Asymptotic results for the superposition of a large number of data connections on an ATM link

The M/PH/∞ system is introduced in this paper to analyze the superposition of a large number of data connections on an ATM link. In this model, information is transmitted in bursts of data arriving at the link as a Poisson process of rate λ and burst durations are PH distributed with unit mean. Some transient characteristics of the M/PH/∞ system, namely the duration θ of an excursion by the occupation process {X_t} above the link transmission capacity C, the area V swept under process {X_t} above C and the number of customers arriving in such an excursion period, are introduced as performance measures. Explicit methods of computing their distributions are described. It is then shown that, as conjectured in earlier studies, random variables Cθ,CV and N converge in distribution as C tends to infinity while the utilization factor of the link defined by γ = λ/C is fixed in (0,1), towards some transient characteristics of an M/M/1 queue with input rate γ and unit service rate. Further simulation results show that after adjustment of the load of the M/M/1 queue, a similar convergence result holds for the superposition of a large number of On/Off sources with various On and Off period distributions. This shows that some transient quantities associated with an M/M/1 queue can be used in the characterization of open loop multiplexing of a large number of On/Off sources on an ATM link. This revised version was published online in June 2006 with corrections to the Cover Date.