Of kernels and queues: when network calculus meets analytic combinatorics

Anne Bouillard; Céline Comte; Élie de Panafieu; Fabien Mathieu

doi:10.1109/ITC30.2018.10061

Of kernels and queues: when network calculus meets analytic combinatorics

Anne Bouillard
, Céline Comte
, Élie de Panafieu
, Fabien Mathieu

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

3 Citations (Scopus)

Abstract

Stochastic network calculus is a tool for computing error bounds on the performance of queueing systems. However, deriving accurate bounds for networks consisting of several queues or subject to non-independent traffic inputs is challenging. In this paper, we investigate the relevance of the tools from analytic combinatorics, especially the kernel method, to tackle this problem. Applying the kernel method allows us to compute the generating functions of the queue state distributions in the stationary regime of the network. As a consequence, error bounds with an arbitrary precision can be computed. In this preliminary work, we focus on simple examples which are representative of the difficulties that the kernel method allows us to overcome.

Original language	English
Title of host publication	Proceedings of the 2018 International Workshop on Network Calculus and Applications, NetCal2018 - Co-located with the 30th International Teletraffic Congress, ITC 2018 and 1st International Conference in Networking Science and Practice
Editors	Giuseppe Bianchi, Thomas Zinner, Eitan Altman
Place of Publication	Piscataway
Publisher	Institute of Electrical and Electronics Engineers
Pages	49-54
Number of pages	6
ISBN (Electronic)	978-0-9883045-5-0
DOIs	https://doi.org/10.1109/ITC30.2018.10061
Publication status	Published - 15 Oct 2018
Externally published	Yes
Event	2018 International Workshop on Network Calculus and Applications, NetCal2018 - Vienna, Austria Duration: 7 Sept 2018 → …

Conference

Conference	2018 International Workshop on Network Calculus and Applications, NetCal2018
Country/Territory	Austria
City	Vienna
Period	7/09/18 → …

Keywords

Analytic combinatorics
Kernel method
Network Calculus
analytic combinatorics
kernel method

Access to Document

10.1109/ITC30.2018.10061

Cite this

Bouillard, A., Comte, C., de Panafieu, É., & Mathieu, F. (2018). Of kernels and queues: when network calculus meets analytic combinatorics . In G. Bianchi, T. Zinner, & E. Altman (Eds.), Proceedings of the 2018 International Workshop on Network Calculus and Applications, NetCal2018 - Co-located with the 30th International Teletraffic Congress, ITC 2018 and 1st International Conference in Networking Science and Practice (pp. 49-54). Article 8493034 Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/ITC30.2018.10061

Bouillard, Anne ; Comte, Céline ; de Panafieu, Élie et al. / Of kernels and queues : when network calculus meets analytic combinatorics . Proceedings of the 2018 International Workshop on Network Calculus and Applications, NetCal2018 - Co-located with the 30th International Teletraffic Congress, ITC 2018 and 1st International Conference in Networking Science and Practice. editor / Giuseppe Bianchi ; Thomas Zinner ; Eitan Altman. Piscataway : Institute of Electrical and Electronics Engineers, 2018. pp. 49-54

@inproceedings{02dc510307284700839b61fcf9df33d4,

title = "Of kernels and queues: when network calculus meets analytic combinatorics ",

abstract = "Stochastic network calculus is a tool for computing error bounds on the performance of queueing systems. However, deriving accurate bounds for networks consisting of several queues or subject to non-independent traffic inputs is challenging. In this paper, we investigate the relevance of the tools from analytic combinatorics, especially the kernel method, to tackle this problem. Applying the kernel method allows us to compute the generating functions of the queue state distributions in the stationary regime of the network. As a consequence, error bounds with an arbitrary precision can be computed. In this preliminary work, we focus on simple examples which are representative of the difficulties that the kernel method allows us to overcome.",

keywords = "Analytic combinatorics, Kernel method, Network Calculus, analytic combinatorics, kernel method",

author = "Anne Bouillard and C{\'e}line Comte and \{de Panafieu\}, {\'E}lie and Fabien Mathieu",

year = "2018",

month = oct,

day = "15",

doi = "10.1109/ITC30.2018.10061",

language = "English",

pages = "49--54",

editor = "Giuseppe Bianchi and Thomas Zinner and Eitan Altman",

booktitle = "Proceedings of the 2018 International Workshop on Network Calculus and Applications, NetCal2018 - Co-located with the 30th International Teletraffic Congress, ITC 2018 and 1st International Conference in Networking Science and Practice",

publisher = "Institute of Electrical and Electronics Engineers",

address = "United States",

note = "2018 International Workshop on Network Calculus and Applications, NetCal2018 ; Conference date: 07-09-2018",

}

Bouillard, A, Comte, C, de Panafieu, É & Mathieu, F 2018, Of kernels and queues: when network calculus meets analytic combinatorics . in G Bianchi, T Zinner & E Altman (eds), Proceedings of the 2018 International Workshop on Network Calculus and Applications, NetCal2018 - Co-located with the 30th International Teletraffic Congress, ITC 2018 and 1st International Conference in Networking Science and Practice., 8493034, Institute of Electrical and Electronics Engineers, Piscataway, pp. 49-54, 2018 International Workshop on Network Calculus and Applications, NetCal2018, Vienna, Austria, 7/09/18. https://doi.org/10.1109/ITC30.2018.10061

Of kernels and queues: when network calculus meets analytic combinatorics . / Bouillard, Anne; Comte, Céline; de Panafieu, Élie et al.
Proceedings of the 2018 International Workshop on Network Calculus and Applications, NetCal2018 - Co-located with the 30th International Teletraffic Congress, ITC 2018 and 1st International Conference in Networking Science and Practice. ed. / Giuseppe Bianchi; Thomas Zinner; Eitan Altman. Piscataway: Institute of Electrical and Electronics Engineers, 2018. p. 49-54 8493034.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Of kernels and queues

T2 - 2018 International Workshop on Network Calculus and Applications, NetCal2018

AU - Bouillard, Anne

AU - Comte, Céline

AU - de Panafieu, Élie

AU - Mathieu, Fabien

PY - 2018/10/15

Y1 - 2018/10/15

N2 - Stochastic network calculus is a tool for computing error bounds on the performance of queueing systems. However, deriving accurate bounds for networks consisting of several queues or subject to non-independent traffic inputs is challenging. In this paper, we investigate the relevance of the tools from analytic combinatorics, especially the kernel method, to tackle this problem. Applying the kernel method allows us to compute the generating functions of the queue state distributions in the stationary regime of the network. As a consequence, error bounds with an arbitrary precision can be computed. In this preliminary work, we focus on simple examples which are representative of the difficulties that the kernel method allows us to overcome.

AB - Stochastic network calculus is a tool for computing error bounds on the performance of queueing systems. However, deriving accurate bounds for networks consisting of several queues or subject to non-independent traffic inputs is challenging. In this paper, we investigate the relevance of the tools from analytic combinatorics, especially the kernel method, to tackle this problem. Applying the kernel method allows us to compute the generating functions of the queue state distributions in the stationary regime of the network. As a consequence, error bounds with an arbitrary precision can be computed. In this preliminary work, we focus on simple examples which are representative of the difficulties that the kernel method allows us to overcome.

KW - Analytic combinatorics

KW - Kernel method

KW - Network Calculus

KW - analytic combinatorics

KW - kernel method

UR - https://www.scopus.com/pages/publications/85057191236

U2 - 10.1109/ITC30.2018.10061

DO - 10.1109/ITC30.2018.10061

M3 - Conference contribution

AN - SCOPUS:85057191236

SP - 49

EP - 54

BT - Proceedings of the 2018 International Workshop on Network Calculus and Applications, NetCal2018 - Co-located with the 30th International Teletraffic Congress, ITC 2018 and 1st International Conference in Networking Science and Practice

A2 - Bianchi, Giuseppe

A2 - Zinner, Thomas

A2 - Altman, Eitan

PB - Institute of Electrical and Electronics Engineers

CY - Piscataway

Y2 - 7 September 2018

ER -

Bouillard A, Comte C, de Panafieu É, Mathieu F. Of kernels and queues: when network calculus meets analytic combinatorics . In Bianchi G, Zinner T, Altman E, editors, Proceedings of the 2018 International Workshop on Network Calculus and Applications, NetCal2018 - Co-located with the 30th International Teletraffic Congress, ITC 2018 and 1st International Conference in Networking Science and Practice. Piscataway: Institute of Electrical and Electronics Engineers. 2018. p. 49-54. 8493034 doi: 10.1109/ITC30.2018.10061

Of kernels and queues: when network calculus meets analytic combinatorics

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this