Dagstuhl Seminar 15112
Network Calculus
( Mar 08 – Mar 11, 2015 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/15112
Organizers
- Florin Ciucu (University of Warwick - Coventry, GB)
- Markus Fidler (Leibniz Universität Hannover, DE)
- Jörg Liebeherr (University of Toronto, CA)
- Jens Schmitt (TU Kaiserslautern, DE)
Contact
- Susanne Bach-Bernhard (for administrative matters)
Schedule
The network calculus has established as a versatile methodology for the queueing analysis of resource sharing based systems. Its prospect is that it can deal with problems that are fundamentally hard for alternative methodologies, based on the fact that it works with bounds rather than striving for exact solutions. The high modelling power of the network calculus has been transposed into several important applications for network engineering problems, traditionally in the Internet’s Quality of Service proposals IntServ and DiffServ, and more recently in diverse environments such as wireless sensor networks, switched Ethernets, Systems-on-Chip, as well as smart grids.
The goal of this Dagstuhl seminar is to gather the deterministic and stochastic network calculus community, to discuss recent research activities, to identify future research questions, and to strengthen cooperation. Open questions and challenges that will be topics of this Dagstuhl seminar arise in the following areas:
- Network topology: A remarkable quality of the network calculus is that it includes a variety of systems that can be composed to arbitrary network topologies. Various analytical as well as numerical approaches have been explored to analyze different types of topologies, such as line topologies or feed-forward networks. The goal of this seminar is to identify relevant classes of topologies, their defining properties, and corresponding methods.
- Parallel systems: The area of performance evaluation of parallel systems has recently become increasingly important due to the prevalence of modern parallel computational models. It is thus a great opportunity for the network calculus community to develop new models and methods which can enable a fundamental and broad understanding of the performance of parallel systems.
- Wireless systems: For the analysis of wireless networks, a question of interest is how the stochastic properties of wireless channels impact delay and backlog performance. The usual statistical models for radio signals in a propagation environment do not lend themselves easily to a queueing model. Promising methods that will be elaborated in the seminar are effective capacities and a recent network calculus of fading channels.
- Flow transformations: A great challenge of existing methodologies for queueing analysis is to deal with flow transformations, which occur when the flows’ data is altered inside the network, e.g., in case of a video transcoder. While some progress for specific scaling elements has been made in the last few years, there are still many open issues. The promise of this topic is high as it widens the modelling scope of the network calculus dramatically
- Lower bounds and tightness of bounds: Based on the ability to solve some fundamentally hard queueing problems, the stochastic network calculus is regarded as a valuable alternative to the classical queueing theory. The derivation of performance bounds in the stochastic network calculus, e.g., for backlog, and delay, frequently exploits well known tail estimates, such as Chernoff bound and others. The tightness of these bounds and alternative more accurate models and techniques will be a topic of the seminar.
- Finite buffers: A typical and convenient assumption in network calculus is that queueing buffers are infinite. It is of significant interest to re-consider this fundamental assumption and develop new models which can be more suitable for finite buffer systems.
The network calculus has established as a versatile methodology for the queueing analysis of resource sharing based systems. Its prospect is that it can deal with problems that are fundamentally hard for alternative methodologies, based on the fact that it works with bounds rather than striving for exact solutions. The high modelling power of the network calculus has been transposed into several important applications for network engineering problems, traditionally in the Internet's Quality of Service proposals IntServ and DiffServ, and more recently in diverse environments such as wireless networks, sensor networks, switched Ethernets, Systems-on-Chip, as well as smart grids.
The goal of this Dagstuhl seminar was to gather the deterministic and stochastic network calculus community, to discuss recent research activities, to identify future research questions, and to strengthen cooperation. Topics of this Dagstuhl seminar were:
Wireless systems: for the analysis of wireless networks, a question of interest is how the stochastic properties of wireless channels impact delay and backlog performance. The usual statistical models for radio signals in a propagation environment do not lend themselves easily to a queueing model. Promising methods that were elaborated in the seminar are effective capacities and a recent network calculus of fading channels.
ower bounds and tightness of bounds: based on the ability to solve some fundamentally hard queueing problems, the stochastic network calculus is regarded as a valuable alternative to the classical queueing theory. The derivation of performance bounds in the stochastic network calculus, e.g., for backlog, and delay, frequently exploits well known tail estimates, such as Chernoff bound and others. The tightness of these bounds and alternative more accurate models and techniques, such as Martingale bounds, were a topic of the seminar.
Network topology: a remarkable quality of the network calculus is that it includes a variety of systems that can be composed to arbitrary network topologies. Various analytical as well as numerical approaches have been explored to analyze different types of topologies, such as line topologies or feed-forward networks. The goal of this seminar was to identify relevant classes of topologies, their defining properties, and corresponding methods.
Parallel systems: the area of performance evaluation of parallel systems has recently become increasingly important due to the prevalence of modern parallel computational models. It is thus a great opportunity for the network calculus community to develop new models and methods which can enable a fundamental and broad understanding of the performance of parallel systems. At the seminar, recent approaches to parallel systems have been discussed.
Related methods: the network calculus has a number of rather unexplored and unexploited connections to related methods in the areas of competitive analysis, adversarial queueing theory, and robust queueing theory that may offer a significant potential for future research. At the seminar, researchers from related fields provided valuable new input to the network calculus community.
During the seminar, we discussed and (partly) answered the following questions:
What are the requirements on a wireless network calculus? Given the increasing importance of wireless communications, the seminar featured two sessions comprising seven presentations on wireless systems, where different approaches and their applications were discussed. Subsequently, a wireless roadmap discussion was centered around the following questions:
- How to model wireless channels and systems?
- What are the most relevant future systems and technologies?
- Which assumptions are needed, which can be safely made?
- What kind of results are needed, which theories can provide these?
With regard to the questions above, we highlight some of the main aspects that were elaborated on during the seminar. The methods that were presented include
- effective capacities,
- impairment models (duality with left-over service curves of scheduling),
- (min, x)-calculus for fading channels,
- capacity-delay-error boundaries,
- central limit theorem,
- Martingale bounds.
Providing different pros, a common basis of many of these methods was found to be due to the prevailing use of moment generating functions (Laplace transforms or Mellin transforms). Relevant systems that were discussed are cognitive radio, 3GPP, MIMO, spatial multiplexing, automatic repeat request, and medium access control. Some fundamental aspects of modelling wireless systems are the assumptions that are required today. Typical choices include
- service increments:
- independent,
- Markovian, Gilbert-Elliott channel,
- in-order delivery,
- error-free, instantaneous feedback channel,
- instantaneous retransmission of erroneous data,
- channel state information.
During the discussion, the need for transfer domains beyond Gilbert-Elliott models was raised. Also, the introduction of a notion of time into information-theoretic concepts, such as channel capacity, was discussed and finite-block length capacity results were brought up. Topics of further interest included spatial aspects of wireless networks, interference, and multi-hop networks in general. Regarding the solutions that can be obtained, a tradeoff between exactness and analytical closed forms became apparent. In particular, in system optimization analytical solutions were mentioned to be most useful to obtain derivatives of relevant performance measures. The discussion also touched upon some more general aspects such as qualitative vs. quantitative results, where many practical applications may not require exact results but can benefit from measurable rules of thumb.
What are most promising future research topics in the network calculus?This question was elaborated on in group work sessions, where the task was to identify an upcoming, relevant research topic where performance evaluation can be expected to make a key contribution. The discussion was guided by the following questions:
- What are the requirements for theory, which assumptions can be made?
- Which results would be needed from theory?
- How would a model/approach look like?
- What would be the best case outcome?
- Which body of theory could provide such results?
- What would be a good topic/method/approach for a PhD dissertation in this area?
Relevant topics in the network calculus were found to include cross-layer design, industrial communication, systems on chip, networks on chip, data center communication, and big data. A strategic orientation may also focus on new and unorthodox problems such as
- just-in-time manufacturing,
- renewable energy, smart grid,
- caching,
- financial engineering,
- road traffic,
where the intuitive concept of envelopes as used by the network calculus may be beneficial for many applications in industry. Methodological aspects that may pose relevant and interesting challenges were discussed in the areas of:
- re-entrant lines, particularly stability of such systems,
- max-min problems,
- derivative constraints, e.g., in modelling of batteries,
- network topologies, particularly non-feed forward networks.
Making network calculus happen: computational aspects, application modelling, tool support. Clearly, for network calculus to become a standard technique in performance modelling and analysis of networked and distributed systems it is crucial to arrive at computable solutions, demonstrate its strengths in diverse applications and provide software tools to support performance engineers in their daily tasks. As these different issues are interrelated on many levels two sessions with nine presentations were devoted to them. Among the different issues raised during these presentations and the corresponding discussions were the following:
- What are suitable novel application domains for network calculus? What are their requirements?
- How can network calculus computations be made more scalable? Where are fundamental limits for the network analysis? How do current software tools perform?
- What is the "killer" application for network calculus, and, in particular, for stochastic network calculus?
- How can network calculus' scope be extended to open up for new application domains?
Some (partial) answers to these important questions could be hinted at by the presentations and the subsequent discussions:
- Currently, some of the most promising application domains of (deterministic) network calculus were identified in industrial control, automotive and aerospace industries; also, interesting steps using (stochastic) network calculus in the modelling of smart energy grids were presented.
- The hardness of feedforward network analysis is by now understood, good heuristic approaches are on the way; however, cyclic dependencies and feedback systems are still open problems to some degree.
- The modelling of parallel systems using network calculus seems a promising building block to address novel attractive applications.
- Software tool support for network calculus, in particular for the stochastic version, is under construction and requires a community effort.
Looking over the fence: related methods. The research goals of network calculus and its methodologies, such as system performance evaluation, Markov chain analysis, or large deviations, intersect with those of other research communities. The objective of the session "Related Methods" was to create a forum where researchers from diverse research communities present their research approaches and discuss them with network calculus researchers. Thus, the session exposed the network calculus community to recent trends in system performance evaluation. Moreover, since speakers in this session had previously no or only limited exposure to network calculus, the session created an opportunity to disseminate the network calculus research agenda to other communities. The session was subtitled as "Looking over the fence", indicating an interest in learning new methodologies and the desire for cross- and interdisciplinary interactions. The session featured speakers from four countries (Canada, France, Israel, USA), from three disciplines (mathematics, theoretical computer science, operations research), presenting recent research on approaches on topics such as robust queueing theory, adversarial queueing theory, and competitive analysis.
This report provides an overview of the talks that were given during the seminar. Also, the seminar comprised a one minute madness session for introduction and for statements on the network calculus, a breakout session for group work on promising future research topics in the network calculus, as well as a podium discussions on wireless network calculus. The discussions, viewpoints, and results that were obtained are also summarized in the sequel.
We would like to thank all presenters, scribes, and participants for their contributions and lively discussions. Particular thanks go to the team of Schloss Dagstuhl for their excellent organization and support.
Creative Commons BY 3.0 Unported license
Florin Ciucu, Markus Fidler, Jörg Liebeherr, and Jens Schmitt
- Sami Akin (Leibniz Universität Hannover, DE) [dblp]
- Hussein Al-Zubaidy (KTH Royal Institute of Technology, SE) [dblp]
- Michael Beck (TU Kaiserslautern, DE) [dblp]
- Nico Becker (Leibniz Universität Hannover, DE) [dblp]
- Daniel Berger (TU Kaiserslautern, DE) [dblp]
- Steffen Bondorf (TU Kaiserslautern, DE) [dblp]
- Anne Bouillard (ENS - Paris, FR) [dblp]
- Marc Boyer (ONERA - Toulouse, FR) [dblp]
- Peter Buchholz (TU Dortmund, DE) [dblp]
- Almut Burchard (University of Toronto, CA) [dblp]
- Florin Ciucu (University of Warwick - Coventry, GB) [dblp]
- Markus Fidler (Leibniz Universität Hannover, DE) [dblp]
- Reinhard German (Universität Erlangen-Nürnberg, DE) [dblp]
- Fabien Geyer (TU München, DE) [dblp]
- Yashar Ghiassi-Farrokhfal (University of Waterloo, CA) [dblp]
- James Gross (KTH Royal Institute of Technology, SE) [dblp]
- Kai-Steffen Jens Hielscher (Universität Erlangen-Nürnberg, DE) [dblp]
- Yuming Jiang (NTNU - Trondheim, NO) [dblp]
- Eduard Jorswieck (TU Dresden, DE) [dblp]
- George Kesidis (Pennsylvania State University - University Park, US) [dblp]
- Kai Lampka (Uppsala University, SE) [dblp]
- Jörg Liebeherr (University of Toronto, CA) [dblp]
- Krishna S. Pandit (TU Darmstadt, DE) [dblp]
- Felix Poloczek (TU Berlin, DE) [dblp]
- Amr Rizk (University of Massachusetts - Amherst, US) [dblp]
- Adi Rosén (CNRS / University Paris-Diderot, FR) [dblp]
- Gabriel Scalosub (Ben Gurion University - Beer Sheva, IL) [dblp]
- Jens Schmitt (TU Kaiserslautern, DE) [dblp]
- Giovanni Stea (University of Pisa, IT) [dblp]
- Hao Wang (TU Kaiserslautern, DE) [dblp]
- Nataly Youssef (MIT - Cambridge, US) [dblp]
Classification
- modelling / simulation
- networks
Keywords
- queueing networks
- network calculus
- min-plus algebra
- effective bandwidths
- effective capacity
- real-time calculus
- performance evaluation
