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
| Folder/File | Content |
|---|---|
| ./omnetpp.ini | main configuration file, store configuration parameters for different runs |
| ./adversarialQueueing | symbolic link to main executable (only available after compilation; don't forget to add omnet to your path variable!) |
| ./messages | messages used for component internal communication and actual network packets, compile by opp_msgc |
| ./node | network nodes are composed of three layers, corresponding classes are here |
| ./networks | OMNeT++ ned representation of available networks |
| ./channelvariation | you may use OMNeT DelayChannel or DatarateChannel for deterministic AQT simulations (make sure that the time step length is matched by link traversal time; this folder gives the additional possibility to model a channel's capacity variation over time |
| ./adversaries | super class AdvancedAversary and subclasses which are examples of adversary implementations |
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.