Details
| Original language | English |
|---|---|
| Pages (from-to) | 1026-1039 |
| Number of pages | 14 |
| Journal | Computer networks |
| Volume | 50 |
| Issue number | 8 |
| Publication status | Published - 5 Oct 2005 |
| Externally published | Yes |
Abstract
Network calculus is a theory of deterministic queuing systems that has successfully been applied to derive performance bounds for communication networks. Founded on min-plus convolution and de-convolution, network calculus obeys a strong analogy to system theory. Yet, system theory has been extended beyond the time domain applying the Fourier transform thereby allowing for an efficient analysis in the frequency domain. A corresponding dual domain for network calculus has not been elaborated, so far. In this paper we show that in analogy to system theory such a dual domain for network calculus is given by convex/concave conjugates referred to also as the Legendre transform. We provide solutions for dual operations and show that min-plus convolution and de-convolution become simple addition and subtraction in the Legendre domain. Additionally, we derive expressions for the Legendre domain to determine upper bounds on backlog and delay at a service element and provide representative examples for the application of conjugate network calculus.
Keywords
- Fenchel duality theorem, Legendre transform, Network calculus
ASJC Scopus subject areas
- Computer Science(all)
- Computer Networks and Communications
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: Computer networks, Vol. 50, No. 8, 05.10.2005, p. 1026-1039.
Research output: Contribution to journal › Article › Research › peer review
}
TY - JOUR
T1 - Conjugate network calculus
T2 - A dual approach applying the Legendre transform
AU - Fidler, Markus
AU - Recker, Stephan
N1 - Funding information: This work was supported in part by an Emmy Noether grant of the German Research Foundation (DFG) and in part by the Centre for Quantifiable Quality of Service in Communication Systems (Q2S). The Q2S Centre of Excellence is appointed by the Research Council of Norway and funded by the Research Council, NTNU and UNINETT.
PY - 2005/10/5
Y1 - 2005/10/5
N2 - Network calculus is a theory of deterministic queuing systems that has successfully been applied to derive performance bounds for communication networks. Founded on min-plus convolution and de-convolution, network calculus obeys a strong analogy to system theory. Yet, system theory has been extended beyond the time domain applying the Fourier transform thereby allowing for an efficient analysis in the frequency domain. A corresponding dual domain for network calculus has not been elaborated, so far. In this paper we show that in analogy to system theory such a dual domain for network calculus is given by convex/concave conjugates referred to also as the Legendre transform. We provide solutions for dual operations and show that min-plus convolution and de-convolution become simple addition and subtraction in the Legendre domain. Additionally, we derive expressions for the Legendre domain to determine upper bounds on backlog and delay at a service element and provide representative examples for the application of conjugate network calculus.
AB - Network calculus is a theory of deterministic queuing systems that has successfully been applied to derive performance bounds for communication networks. Founded on min-plus convolution and de-convolution, network calculus obeys a strong analogy to system theory. Yet, system theory has been extended beyond the time domain applying the Fourier transform thereby allowing for an efficient analysis in the frequency domain. A corresponding dual domain for network calculus has not been elaborated, so far. In this paper we show that in analogy to system theory such a dual domain for network calculus is given by convex/concave conjugates referred to also as the Legendre transform. We provide solutions for dual operations and show that min-plus convolution and de-convolution become simple addition and subtraction in the Legendre domain. Additionally, we derive expressions for the Legendre domain to determine upper bounds on backlog and delay at a service element and provide representative examples for the application of conjugate network calculus.
KW - Fenchel duality theorem
KW - Legendre transform
KW - Network calculus
UR - http://www.scopus.com/inward/record.url?scp=33646493332&partnerID=8YFLogxK
U2 - 10.1016/j.comnet.2005.09.004
DO - 10.1016/j.comnet.2005.09.004
M3 - Article
AN - SCOPUS:33646493332
VL - 50
SP - 1026
EP - 1039
JO - Computer networks
JF - Computer networks
SN - 1389-1286
IS - 8
ER -