M/M/∞ transience : tail asymptotics of congestion periods

M.R.H. Mandjes, F. Roijers

Research output: Book/ReportReportAcademic

1 Downloads (Pure)

Abstract

The c-congestion period, defined as a time interval in which the number of customers is larger than c all the time, is a key quantity in the design of communication networks. Particularly in the setting of M/M/infinity systems, the analysis of the duration of the congestion period, D_c, has attracted substantial attention; related quantities have been studied as well, such as the total area A_c above c, and the number of arrived customers N_c during a congestion period. Laplace transforms of these three random variables being known, as well as explicit formulae for their moments, this paper addresses the corresponding tail asymptotics. Our work addresses the following topics. In the so-called many-flows scaling, we show that the tail asymptotics are essentially exponential in the scaling parameter. The proof techniques stem from large deviations theory; we also identify the most likely way in which the event under consideration occurs. In the same scaling, we approximate the model by its Gaussian counterpart. Specializing to our specific model, we show that the (fairly abstract) sample-path largedeviations theorem for Gaussian processes, viz. the generalized version of Schilder’s theorem, can be written in a considerably more explicit way. Relying on this result, we derive the tail asymptotics for the Gaussian counterpart. Then we use change-of-measure arguments to find upper bounds, uniform in the model parameters, on the probabilities of interest. These change-of-measures are applied to devise of a number of importance-sampling schemes, for fast simulation of rare-event probabilities. They turn out to yield a substantial speed-up in simulation effort, compared to naïve, direct simulations.
Original languageEnglish
Place of PublicationAmsterdam
PublisherCentrum voor Wiskunde en Informatica
Number of pages26
Publication statusPublished - 2008

Publication series

NameCWI Report
VolumePNA-E0806

Fingerprint

Tail Asymptotics
Transience
Congestion
Change of Measure
Scaling
Customers
Large Deviation Theory
Simulation
Rare Events
Importance Sampling
Sample Path
Gaussian Process
Theorem
Communication Networks
Laplace transform
Explicit Formula
Speedup
Random variable
Likely
Infinity

Cite this

Mandjes, M. R. H., & Roijers, F. (2008). M/M/∞ transience : tail asymptotics of congestion periods. (CWI Report; Vol. PNA-E0806). Amsterdam: Centrum voor Wiskunde en Informatica.
Mandjes, M.R.H. ; Roijers, F. / M/M/∞ transience : tail asymptotics of congestion periods. Amsterdam : Centrum voor Wiskunde en Informatica, 2008. 26 p. (CWI Report).
@book{0a743d05fa794bcc8c2acc7998fecd77,
title = "M/M/∞ transience : tail asymptotics of congestion periods",
abstract = "The c-congestion period, defined as a time interval in which the number of customers is larger than c all the time, is a key quantity in the design of communication networks. Particularly in the setting of M/M/infinity systems, the analysis of the duration of the congestion period, D_c, has attracted substantial attention; related quantities have been studied as well, such as the total area A_c above c, and the number of arrived customers N_c during a congestion period. Laplace transforms of these three random variables being known, as well as explicit formulae for their moments, this paper addresses the corresponding tail asymptotics. Our work addresses the following topics. In the so-called many-flows scaling, we show that the tail asymptotics are essentially exponential in the scaling parameter. The proof techniques stem from large deviations theory; we also identify the most likely way in which the event under consideration occurs. In the same scaling, we approximate the model by its Gaussian counterpart. Specializing to our specific model, we show that the (fairly abstract) sample-path largedeviations theorem for Gaussian processes, viz. the generalized version of Schilder’s theorem, can be written in a considerably more explicit way. Relying on this result, we derive the tail asymptotics for the Gaussian counterpart. Then we use change-of-measure arguments to find upper bounds, uniform in the model parameters, on the probabilities of interest. These change-of-measures are applied to devise of a number of importance-sampling schemes, for fast simulation of rare-event probabilities. They turn out to yield a substantial speed-up in simulation effort, compared to na{\"i}ve, direct simulations.",
author = "M.R.H. Mandjes and F. Roijers",
year = "2008",
language = "English",
series = "CWI Report",
publisher = "Centrum voor Wiskunde en Informatica",

}

Mandjes, MRH & Roijers, F 2008, M/M/∞ transience : tail asymptotics of congestion periods. CWI Report, vol. PNA-E0806, Centrum voor Wiskunde en Informatica, Amsterdam.

M/M/∞ transience : tail asymptotics of congestion periods. / Mandjes, M.R.H.; Roijers, F.

Amsterdam : Centrum voor Wiskunde en Informatica, 2008. 26 p. (CWI Report; Vol. PNA-E0806).

Research output: Book/ReportReportAcademic

TY - BOOK

T1 - M/M/∞ transience : tail asymptotics of congestion periods

AU - Mandjes, M.R.H.

AU - Roijers, F.

PY - 2008

Y1 - 2008

N2 - The c-congestion period, defined as a time interval in which the number of customers is larger than c all the time, is a key quantity in the design of communication networks. Particularly in the setting of M/M/infinity systems, the analysis of the duration of the congestion period, D_c, has attracted substantial attention; related quantities have been studied as well, such as the total area A_c above c, and the number of arrived customers N_c during a congestion period. Laplace transforms of these three random variables being known, as well as explicit formulae for their moments, this paper addresses the corresponding tail asymptotics. Our work addresses the following topics. In the so-called many-flows scaling, we show that the tail asymptotics are essentially exponential in the scaling parameter. The proof techniques stem from large deviations theory; we also identify the most likely way in which the event under consideration occurs. In the same scaling, we approximate the model by its Gaussian counterpart. Specializing to our specific model, we show that the (fairly abstract) sample-path largedeviations theorem for Gaussian processes, viz. the generalized version of Schilder’s theorem, can be written in a considerably more explicit way. Relying on this result, we derive the tail asymptotics for the Gaussian counterpart. Then we use change-of-measure arguments to find upper bounds, uniform in the model parameters, on the probabilities of interest. These change-of-measures are applied to devise of a number of importance-sampling schemes, for fast simulation of rare-event probabilities. They turn out to yield a substantial speed-up in simulation effort, compared to naïve, direct simulations.

AB - The c-congestion period, defined as a time interval in which the number of customers is larger than c all the time, is a key quantity in the design of communication networks. Particularly in the setting of M/M/infinity systems, the analysis of the duration of the congestion period, D_c, has attracted substantial attention; related quantities have been studied as well, such as the total area A_c above c, and the number of arrived customers N_c during a congestion period. Laplace transforms of these three random variables being known, as well as explicit formulae for their moments, this paper addresses the corresponding tail asymptotics. Our work addresses the following topics. In the so-called many-flows scaling, we show that the tail asymptotics are essentially exponential in the scaling parameter. The proof techniques stem from large deviations theory; we also identify the most likely way in which the event under consideration occurs. In the same scaling, we approximate the model by its Gaussian counterpart. Specializing to our specific model, we show that the (fairly abstract) sample-path largedeviations theorem for Gaussian processes, viz. the generalized version of Schilder’s theorem, can be written in a considerably more explicit way. Relying on this result, we derive the tail asymptotics for the Gaussian counterpart. Then we use change-of-measure arguments to find upper bounds, uniform in the model parameters, on the probabilities of interest. These change-of-measures are applied to devise of a number of importance-sampling schemes, for fast simulation of rare-event probabilities. They turn out to yield a substantial speed-up in simulation effort, compared to naïve, direct simulations.

M3 - Report

T3 - CWI Report

BT - M/M/∞ transience : tail asymptotics of congestion periods

PB - Centrum voor Wiskunde en Informatica

CY - Amsterdam

ER -

Mandjes MRH, Roijers F. M/M/∞ transience : tail asymptotics of congestion periods. Amsterdam: Centrum voor Wiskunde en Informatica, 2008. 26 p. (CWI Report).