The Library
Two extensions of Kingman's GI/G/1 bound
Tools
Tools
Tools
Ciucu, Florin and Poloczek, Felix (2018) Two extensions of Kingman's GI/G/1 bound. Proceedings of the ACM on Measurement and Analysis of Computing Systems - SIGMETRICS, 2 (3). 43. doi:10.1145/3287322 ISSN 2476-1249.
|
PDF
WRAP-two-extensions-Kingman's-bound-Ciucu-2018.pdf - Published Version - Requires a PDF viewer. Download (1495Kb) | Preview |
Official URL: https://doi.org/10.1145/3287322
Abstract
A simple bound in GI/G/1 queues was obtained by Kingman using a discrete martingale transform. We extend this technique to 1) multiclass $\Sigma\textrm{GI/G/1}$ queues and 2) Markov Additive Processes (MAPs) whose background processes can be time-inhomogeneous or have an uncountable state-space. Both extensions are facilitated by a necessary and sufficient ordinary differential equation (ODE) condition for MAPs to admit continuous martingale transforms. Simulations show that the bounds on waiting time distributions are almost exact in heavy-traffic, including the cases of 1) heterogeneous input, e.g., mixing Weibull and Erlang-k classes and 2) Generalized Markovian Arrival Processes, a new class extending the Batch Markovian Arrival Processes to continuous batch sizes.
| Item Type: | Journal Article | ||||||
|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
| Library of Congress Subject Headings (LCSH): | Markov processes, Martingales (Mathematics), Stochastic processes | ||||||
| Journal or Publication Title: | Proceedings of the ACM on Measurement and Analysis of Computing Systems - SIGMETRICS | ||||||
| Publisher: | ACM | ||||||
| ISSN: | 2476-1249 | ||||||
| Official Date: | 31 December 2018 | ||||||
| Dates: |
|
||||||
| Volume: | 2 | ||||||
| Number: | 3 | ||||||
| Article Number: | 43 | ||||||
| DOI: | 10.1145/3287322 | ||||||
| Status: | Peer Reviewed | ||||||
| Publication Status: | Published | ||||||
| Reuse Statement (publisher, data, author rights): | © ACM, 2018. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Proceedings of the ACM on Measurement and Analysis of Computing Systems - SIGMETRICS, 2 (3). 43. doi: http://doi.acm.org/10.1145/10.1145/3287322 | ||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||
| Date of first compliant deposit: | 29 November 2018 | ||||||
| Date of first compliant Open Access: | 13 February 2019 |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
