Poloczek, Felix (2016) Stochastic network calculus with martingales. PhD thesis, University of Warwick.

Preview

PDF WRAP_Theses_Poloczek_2016.pdf - Submitted Version - Requires a PDF viewer. Download (2265Kb) | Preview

Request Changes to record.

Abstract

The practicality of the stochastic network calculus (SNC) is often questioned on grounds of looseness of its performance bounds. The reason for its inaccuracy lies in the usage of too elementary tools from probability theory, such as Boole’s inequality, which is unable to account for correlations and thus inappropriate to properly model arrival flows.

In this thesis, we propose an extension of stochastic network calculus that characterizes its main objects, namely arrival and service processes, in terms of martingales. This characterization allows to overcome the shortcomings of the classical SNC by leveraging Doob’s inequality to provide more accurate performance bounds. Additionally, the emerging stochastic network calculus with martingales is quite versatile in the sense that queueing related operations like multiplexing and scheduling directly translate into operations of the corresponding martingales. Concretely, the framework is applied to analyze the per-flow delay of various scheduling policies, the performance of random access protocols, and queueing scenarios with a random number of parallel flows.

Moreover, we show our methodology is not only relevant within SNC but can be useful also in related queueing systems. E.g., in the context of multi-server systems, we provide a martingale-based analysis of fork-join queueing systems and systems with replications.

Throughout, numerical comparisons against simulations show that the Martingale bounds obtained with Doob’s inequality are not only remarkably accurate, but they also improve the Standard SNC bounds by several orders of magnitude.

Item Type:	Thesis (PhD)
Subjects:	Q Science > QA Mathematics T Technology > T Technology (General)
Library of Congress Subject Headings (LCSH):	Queuing theory, Computer networks, Martingales (Mathematics)
Official Date:	June 2016
Dates:	Date Event June 2016 Submitted
Institution:	University of Warwick
Theses Department:	Department of Computer Science
Thesis Type:	PhD
Publication Status:	Unpublished
Supervisor(s)/Advisor:	Ciucu, Florin
Sponsors:	Deutsche Forschungsgemeinschaft
Format of File:	pdf
Extent:	xviii, 182 leaves : illustrations, charts
Language:	eng

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads