Corrected phase-type approximations for the workload of the MAP/G/1 queue with heavy-tailed service times

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Citations (Scopus)
3 Downloads (Pure)

Abstract

In many applications, significant correlations between arrivals of load-generating events make the numerical evaluation of the load of a system a challenging problem. Here, we construct very accurate approximations of the workload distribution of the MAP/G/1 queue that capture the tail behavior of the exact workload distribution and provide a small relative error. Motivated by statistical analysis, we assume that the service times are a mixture of a phase-type and a heavy-tailed distribution. With the aid of perturbation analysis, we derive our approximations as a sum of the workload distribution of the MAP/PH/1 queue and a heavytailed component that depends on the perturbation parameter. We refer to our approximations as corrected phase-type approximations, and we exhibit their performance with a numerical study. Keywords: Markovian Arrival Process (MAP); Workload distribution; Heavy-tailed service times; Tail asymptotics; Perturbation analysis.
Original languageEnglish
Title of host publication31st International Symposium on Computer Performance, Modeling, Measurements and Evaluation (IFIP WG 7.3 Performance 2013), Vienna, Austria, September 24-26, 2013
Place of PublicationNew York
PublisherAssociation for Computing Machinery, Inc
Pages53-55
DOIs
Publication statusPublished - 2013

Publication series

NameACM SIGMETRICS Performance Evaluation Review
Number2
Volume41
ISSN (Print)0163-5999

Fingerprint

Markovian Arrival Process
Workload
Queue
Perturbation Analysis
Approximation
Tail Asymptotics
Tail Behavior
Heavy-tailed Distribution
Parameter Perturbation
Relative Error
Statistical Analysis
Numerical Study
Evaluation

Cite this

Vatamidou, E., Adan, I. J. B. F., Vlasiou, M., & Zwart, B. (2013). Corrected phase-type approximations for the workload of the MAP/G/1 queue with heavy-tailed service times. In 31st International Symposium on Computer Performance, Modeling, Measurements and Evaluation (IFIP WG 7.3 Performance 2013), Vienna, Austria, September 24-26, 2013 (pp. 53-55). (ACM SIGMETRICS Performance Evaluation Review; Vol. 41, No. 2). New York: Association for Computing Machinery, Inc. https://doi.org/10.1145/2518025.2518036
Vatamidou, E. ; Adan, I.J.B.F. ; Vlasiou, M. ; Zwart, B. / Corrected phase-type approximations for the workload of the MAP/G/1 queue with heavy-tailed service times. 31st International Symposium on Computer Performance, Modeling, Measurements and Evaluation (IFIP WG 7.3 Performance 2013), Vienna, Austria, September 24-26, 2013. New York : Association for Computing Machinery, Inc, 2013. pp. 53-55 (ACM SIGMETRICS Performance Evaluation Review; 2).
@inproceedings{d9f5affd973f448dab219b62f0a18eec,
title = "Corrected phase-type approximations for the workload of the MAP/G/1 queue with heavy-tailed service times",
abstract = "In many applications, significant correlations between arrivals of load-generating events make the numerical evaluation of the load of a system a challenging problem. Here, we construct very accurate approximations of the workload distribution of the MAP/G/1 queue that capture the tail behavior of the exact workload distribution and provide a small relative error. Motivated by statistical analysis, we assume that the service times are a mixture of a phase-type and a heavy-tailed distribution. With the aid of perturbation analysis, we derive our approximations as a sum of the workload distribution of the MAP/PH/1 queue and a heavytailed component that depends on the perturbation parameter. We refer to our approximations as corrected phase-type approximations, and we exhibit their performance with a numerical study. Keywords: Markovian Arrival Process (MAP); Workload distribution; Heavy-tailed service times; Tail asymptotics; Perturbation analysis.",
author = "E. Vatamidou and I.J.B.F. Adan and M. Vlasiou and B. Zwart",
year = "2013",
doi = "10.1145/2518025.2518036",
language = "English",
series = "ACM SIGMETRICS Performance Evaluation Review",
publisher = "Association for Computing Machinery, Inc",
number = "2",
pages = "53--55",
booktitle = "31st International Symposium on Computer Performance, Modeling, Measurements and Evaluation (IFIP WG 7.3 Performance 2013), Vienna, Austria, September 24-26, 2013",
address = "United States",

}

Vatamidou, E, Adan, IJBF, Vlasiou, M & Zwart, B 2013, Corrected phase-type approximations for the workload of the MAP/G/1 queue with heavy-tailed service times. in 31st International Symposium on Computer Performance, Modeling, Measurements and Evaluation (IFIP WG 7.3 Performance 2013), Vienna, Austria, September 24-26, 2013. ACM SIGMETRICS Performance Evaluation Review, no. 2, vol. 41, Association for Computing Machinery, Inc, New York, pp. 53-55. https://doi.org/10.1145/2518025.2518036

Corrected phase-type approximations for the workload of the MAP/G/1 queue with heavy-tailed service times. / Vatamidou, E.; Adan, I.J.B.F.; Vlasiou, M.; Zwart, B.

31st International Symposium on Computer Performance, Modeling, Measurements and Evaluation (IFIP WG 7.3 Performance 2013), Vienna, Austria, September 24-26, 2013. New York : Association for Computing Machinery, Inc, 2013. p. 53-55 (ACM SIGMETRICS Performance Evaluation Review; Vol. 41, No. 2).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Corrected phase-type approximations for the workload of the MAP/G/1 queue with heavy-tailed service times

AU - Vatamidou, E.

AU - Adan, I.J.B.F.

AU - Vlasiou, M.

AU - Zwart, B.

PY - 2013

Y1 - 2013

N2 - In many applications, significant correlations between arrivals of load-generating events make the numerical evaluation of the load of a system a challenging problem. Here, we construct very accurate approximations of the workload distribution of the MAP/G/1 queue that capture the tail behavior of the exact workload distribution and provide a small relative error. Motivated by statistical analysis, we assume that the service times are a mixture of a phase-type and a heavy-tailed distribution. With the aid of perturbation analysis, we derive our approximations as a sum of the workload distribution of the MAP/PH/1 queue and a heavytailed component that depends on the perturbation parameter. We refer to our approximations as corrected phase-type approximations, and we exhibit their performance with a numerical study. Keywords: Markovian Arrival Process (MAP); Workload distribution; Heavy-tailed service times; Tail asymptotics; Perturbation analysis.

AB - In many applications, significant correlations between arrivals of load-generating events make the numerical evaluation of the load of a system a challenging problem. Here, we construct very accurate approximations of the workload distribution of the MAP/G/1 queue that capture the tail behavior of the exact workload distribution and provide a small relative error. Motivated by statistical analysis, we assume that the service times are a mixture of a phase-type and a heavy-tailed distribution. With the aid of perturbation analysis, we derive our approximations as a sum of the workload distribution of the MAP/PH/1 queue and a heavytailed component that depends on the perturbation parameter. We refer to our approximations as corrected phase-type approximations, and we exhibit their performance with a numerical study. Keywords: Markovian Arrival Process (MAP); Workload distribution; Heavy-tailed service times; Tail asymptotics; Perturbation analysis.

U2 - 10.1145/2518025.2518036

DO - 10.1145/2518025.2518036

M3 - Conference contribution

T3 - ACM SIGMETRICS Performance Evaluation Review

SP - 53

EP - 55

BT - 31st International Symposium on Computer Performance, Modeling, Measurements and Evaluation (IFIP WG 7.3 Performance 2013), Vienna, Austria, September 24-26, 2013

PB - Association for Computing Machinery, Inc

CY - New York

ER -

Vatamidou E, Adan IJBF, Vlasiou M, Zwart B. Corrected phase-type approximations for the workload of the MAP/G/1 queue with heavy-tailed service times. In 31st International Symposium on Computer Performance, Modeling, Measurements and Evaluation (IFIP WG 7.3 Performance 2013), Vienna, Austria, September 24-26, 2013. New York: Association for Computing Machinery, Inc. 2013. p. 53-55. (ACM SIGMETRICS Performance Evaluation Review; 2). https://doi.org/10.1145/2518025.2518036