This project page is about our 2014 ACM SIGMETRICS paper On the Relevance of Adversarial Queueing Theory in Practice on how to construct loss-efficient network adversaries. In case of questions, contact our project members Daniel S. Berger (University of Kaiserslautern), Martin Karsten (University of Waterloo), and Jens Schmitt (University of Kaiserslautern).

Summary

Adversarial Queueing Theory (AQT) [1] has been introduced to analyze the inherent stability characteristics of network topologies assuming certain scheduling policies. In particular, it has been shown for FIFO scheduling that seemingly innocent continuous packet injection strategies, where the aggregated arrival rate of requests for each link does not exceed the link capacity, can lead to unbounded queue lengths and thus, unbounded delay. Such a network configuration is termed unstable.

In reality, such patterns can be caused by misconfiguration, or unfortunate circumstances and have also been considered as a possible security threat. In fact, descriptions of network adversaries read like a cookbook for stealthy low-rate denial-of-service (DoS) attacks inducing arbitrary long queues in a target network, which in turn cause high delays and loss.

Little attention has been given to quantifying the actual threat potential of adversarial queueing effects. Although topological considerations suggest that adversarial instability may be possible in realistic network topologies [2], it is not immediately obvious whether instability effects really pose a practical threat. The most striking theoretical and "analytically convenient" assumptions of AQT are infinite buffers and a synchronized network model.

This work [3,4] attempts a new perspective on adversarial queueing effects. We investigate

• the quantitative effects of adversarial queueing in finite buffer networks (-> loss)
• with some asynchrony due to random effects in nodal processing and link delays
• and with timing variations for adversarial injections

Our results, using analysis and simulation, indicate that classical AQT examples appear harmless under realistic assumptions but for a novel class of adversaries considerably higher loss can be observed. This novel class introduces two new AQT concepts to construct loss-efficient network adversaries.

Our analysis (and simulations) also prove that the loss caused by classical adversaries (like the Baseball (BB) scenario) diminishes to irrelevant values in face of network randomization. The underlying model assumes that (instead of a deterministic network model with
uniform and synchronized network links) each channel’s delay (the corresponding server delay for processing a single
packet) follows a Weibull distributed random variable with mean one and various degrees of standard deviations up to 300%.

The new class of network adversaries (shown here, the Reactive Adversary (RA)) proves robust against randomized de-synchronization effects both in terms of variable link delays and injection synchronization.

Simulation Framework and Source Code

The work in our papers [3,4] is supported by simulations that are carried out in the AQTmodel extension to the simulation framework is OMNeT++. All source code is open and available here. You will need a running OMNeT++ 4 distribution (the simulator was developed in 4.2 and 4.4 but any more recent version should work, too), sufficient hard disk space to store recorded results (on the order of 5-100 GB ,dependent on what is recorded and in which network), and TCL/TK for visualization.

Installation

This AQTmodel comes as a source library written in OMNeT++ 4.2.2 (for version v.01) and OMNeT 4.4.1 (for version v.03). You'll need to

• source setenv in the omnet folder,
• cd to the project folder,
• run make to compile first,
• and then execute ./adversarialQueueing, which will display a menu to choose the scenario to run.

In order to run different configurations (e.g., injection rates, or adversaries), no modification of the code is requires - it is a good idea to start with adjusting the main configuration file omnetpp.ini.

License

To encourage modifications and future reuse, we distribute this code under the GNU Lesser General Public License (see licenses).

This program is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

Available Network Adversaries

The Baseball Adversary due to [5]

The A+ Instability Minor from [2]

 The adversary by Diaz et al. [8]

The gadget chain adversary due to Lotker et al. [7]

The new Interlocked Baseball Adversary proposed in [4]. The internal name (in the simulator is CE3).

The new Reactive Adversary proposed in [4]. The internal name (in the simulator is CE7).

Further drafts on possible extensions like this one, which bears the internal name CE75.

Download

Source Code: both for v.03 (paper [3] and the old version v.01 (paper [4]) is available here. The source code of v.02 is deprecated and we encourage updating to v.03.

Source Code Overview

References and Publications

[1] A. Borodin, J. Kleinberg, P. Raghavan, M. Sudan, and D. P. Williamson. Adversarial queuing theory. Journal of the ACM, 48(1):13–38, Jan. 2001.
[2] M. Weinard. Deciding the FIFO stability of networks in polynomial time. Algorithms and Complexity, (3):81–92, 2006.
[3] DS. Berger, M. Karsten, J. Schmitt. On the Relevance of Adversarial Queueing Theory in Practice, In ACM SIGMETRICS (to appear), 2014.
[4] DS. Berger, M. Karsten, and J. Schmitt. Simulation of Adversarial Scenarios in OMNeT ++ – Putting Adversarial Queueing Theory from Its Head to Feet. In Proc. of the ICST Conference on Simulation Tools and Techniques, 2013.
[5] M. Andrews, B. Awerbuch, A. Fernandez, T. Leighton, Z. Liu, and J. Kleinberg. Universal-stability results and performance bounds for greedy contention-resolution protocols. Journal of the ACM, 48(1):39–69, Jan. 2001.
[6] R. Bhattacharjee and A. Goel. Instability of FIFO at Arbitrarily Low Rates in the Adversarial Queueing Model. SIAM Journal on Computing, 34(2):318, 2005.
[7] Z. Lotker, B. Patt-Shamir, and A. Rosen. New Stability Results for Adversarial Queuing. SIAM Journal on Computing, 33(2):286, 2004.
[8] J. Diaz, D. Koukopoulos, S. Nikoletseas, M. Serna, P. Spirakis, and D. M. Thilikos. Stability and  non-stability of the FIFO protocol. In Proc. of the SPAA, pages 48–52, Crete Island, Greece, 2001. ACM.

This document is still in process and hopefully will evolve at some day into a full grown course about Stochastic Network Calculus, giving a good overview over this exciting theory. Hence, please provide feedback to This email address is being protected from spambots. You need JavaScript enabled to view it..

This First Course in Stochastic Network Calculus builds on the lecture Performance Modeling of Distributed Systems at the University of Kaiserslautern. The concepts of stochastic network calclulus parallels those of deterministic network calculus. This is why I reference on the lecture of 2011 at several points to stress these connections. This document however is thought of a stand-alone course and hence a deep study of the lecture is not necessary (but recommended).

This course contains a rather large probability primer to ensure the student can really grasp the expressions, which appear in stochastic network calculus. A student familiar with probability theory might skip this first chapter and delve directly into the stochastic network calculus. For each topic exercises are given, which can (and should) be used to strengthen the understanding of the presented definitions and theory.

A First Course in Stochastic Network Calculus

What is it?

A toolbox for the stochastic network calculus (SNC) with moment-generating functions (MGFs) is implemented. It is focused on (sigma, rho)-constrained processes. It provides a list a typical stochastic network calculus arrival processes, operators, and performance bounds in order to conduct end-to-end network analyses.

The toolbox works well with JetBrains PyCharm and supports, e.g., features like type hints.
Screenshot in PyCharm:

More Information

For more information, check out the README.md on Github

Feedback

For feedback, questions, ... etc. please contact Paul Nikolaus

System Requirements

Python 3.10 or higher and all libraries in requirements.txt

Download

The code is exclusively available on Github!

What is it?

The SNC Quick Start is a simple guide on how to implement the stochastic network calculus (SNC) with moment-generating functions (MGFs).
It is a Jupyter Notebook that combines the mathematical background with an actual implementation in Python 3.

The notebook works well with VS Code (together with the "Jupyter" and the "Markdown+Math" extension) or JetBrains DataSpell.

More Information

For more information, check out the README.md on Github

Screenshot in VS Code

Feedback

For feedback, questions, ... etc. please contact Paul Nikolaus

System Requirements

Python 3.10 or higher and all libraries in requirements.txt

Download

The code is exclusively available on Github!