The Library
Scheduling analysis with martingales
Tools
Tools
Tools
Poloczek, Felix and Ciucu, Florin (2014) Scheduling analysis with martingales. Performance Evaluation, Volume 79 . pp. 56-72. doi:10.1016/j.peva.2014.07.004 ISSN 0166-5316.
|
PDF
WRAP_Ciucu_envelopecr.pdf - Accepted Version - Requires a PDF viewer. Download (1240Kb) | Preview |
Official URL: http://dx.doi.org/10.1016/j.peva.2014.07.004
Abstract
This paper proposes a new characterization of queueing systems by bounding a suitable exponential transform with a martingale. The constructed martingale is quite versatile in the sense that it captures queueing systems with Markovian and autoregressive arrivals in a unified manner; the second class is particularly relevant due to Wold’s decomposition of stationary processes. Moreover, using the framework of stochastic network calculus, the martingales allow for a simple handling of typical queueing operations: (1) flows’ multiplexing translates into multiplying the corresponding martingales, and (2) scheduling translates into time-shifting the martingales. The emerging calculus is applied to estimate the per-flow delay for FIFO, SP, and EDF scheduling. Unlike state-of-the-art results, our bounds capture a fundamental exponential leading constant in the number of multiplexed flows, and additionally are numerically tight.
| Item Type: | Journal Article | ||||||
|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
| Library of Congress Subject Headings (LCSH): | Martingales (Mathematics) , Queuing theory, Scheduling, Stochastic analysis | ||||||
| Journal or Publication Title: | Performance Evaluation | ||||||
| Publisher: | Elsevier Science BV | ||||||
| ISSN: | 0166-5316 | ||||||
| Official Date: | September 2014 | ||||||
| Dates: |
|
||||||
| Volume: | Volume 79 | ||||||
| Page Range: | pp. 56-72 | ||||||
| DOI: | 10.1016/j.peva.2014.07.004 | ||||||
| Status: | Peer Reviewed | ||||||
| Publication Status: | Published | ||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||
| Date of first compliant deposit: | 4 April 2016 | ||||||
| Date of first compliant Open Access: | 26 July 2016 | ||||||
| Embodied As: | 1 |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
