Development, Validation and Tool Support of a Stochastic Calculus for Networks with Flow Transformations
Final Report Abstract
Over the last decade, the stochastic network calculus has established itself as a versatile alternative methodology to the classical queueing theory for the performance analysis of networks and distributed systems. Its prospect is that it can deal with problems that are fundamentally hard for queueing theory based on the fact that it works with (probabilistic) bounds rather than striving for exact solutions. A great challenge of existing methodologies for queueing analysis was and, admittedly, to some degree still is to deal with queueing networks subject to flow transformations, which occur when the flows’ data is altered inside the network. Flow transformations are in fact characteristic to many modern networked and distributed systems, e.g., a wireless sensor network processes the transported data, while delivering it to a sink node, for energy-efficiency purposes. This project investigated an extension of the stochastic network calculus to deal with such flow transformations and comprised of three inter-connected parts. On the theoretical side, the project developed stochastic scaling elements, for modelling flow transformations within the framework of the stochastic network calculus. On the application side, the project applied its theory to several real-world application scenarios, like NFV/SDN architectures, wireless networks with reliability mechanisms and load balancing in parallel systems, in order to validate its usefulness as well as its accuracy. Furthermore, within the context of the project a software tool called the DISCO Stochastic Network Calculator was developed to support automated analyses. Besides these research results, the two principal investigators (together with Markus Fidler and Jörg Liebeherr) organized a Dagstuhl seminar on Network Calculus (no. 15112) bringing together the most active and influential researchers working in this field. At the seminar, about 30 invited attendees from academia and industry discussed the promises, approaches, and open challenges of the network calculus.
Publications
- (2014) On the catalyzing effect of randomness on the per-flow throughput in wireless networks. IEEE INFOCOM 2014 - IEEE Conference on Computer Communications, pp. 2616-2624
Ciucu, Florin; Schmitt, Jens
(See online at https://doi.org/10.1109/INFOCOM.2014.6848209) - Performance modelling and analysis of unreliable links with retransmissions using network calculus. In Proceedings of the 25th International Teletraffic Congress (ITC 25), September 2013
H. Wang, J. Schmitt, und F. Ciucu
- The disco stochastic network calculator version 1.0 - when waiting comes to an end. In Proceedings of the 7th International Conference on Performance Evaluation Methodologies and Tools (VALUETOOLS 2013), Dezember 2013
M. A. Beck und J. Schmitt
- End-to-end delay bounds for variable length packet transmissions under flow transformations. In Proceedings of the 8th International Conference on Performance Evaluation Methodologies and Tools (VALUETOOLS 2014), Dezember 2014
H. Wang und J. B. Schmitt
(See online at https://doi.org/10.4108/icst.Valuetools.2014.258194) - Scheduling analysis with martingales. Performance Evaluation, 79:56 – 72, September 2014. Special Issue: Performance 2014
F. Poloczek und F. Ciucu
(See online at https://doi.org/10.1109/ITC-28.2016.131) - Sharp per-flow delay bounds for bursty arrivals: The case of FIFO, SP, and EDF scheduling. In IEEE Infocom, Seiten 1896–1904, April 2014
F. Ciucu, F. Poloczek, und J. Schmitt
(See online at https://doi.org/10.1109/INFOCOM.2014.6848129) - Computable bounds in fork-join queueing systems. In ACM Sigmetrics, Seiten 335–346, Juni 2015
A. Rizk, F. Poloczek, und F. Ciucu
(See online at https://doi.org/10.1145/2796314.2745859) - Service-martingales: Theory and applications to the delay analysis of random access protocols. In IEEE Infocom, Seiten 945–953, Mai 2015
F. Poloczek und F. Ciucu
(See online at https://doi.org/10.1109/INFOCOM.2015.7218466) - Load balancing - towards balanced delay guarantees in NFV/SDN. In Proceedings of the 2016 IEEE Conference on Network Function Virtualization and Software Defined Networks (NFV-SDN ’16), November 2016
H. Wang und J. B. Schmitt
(See online at https://doi.org/10.1109/NFV-SDN.2016.7919504)
