Home

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.

The simulation code AQTmodel allow to study such instability examples quantitatively using the OMNeT++ simulation framework. In particular, the simulator was developed to study how instability scenarios behave in a finite-buffer network. Furthermore, it helped in developping the loss-efficient network adversaries of the 2014 ACM SIGMETRICS paper On the Relevance of Adversarial Queueing Theory in Practice. See the project website for further reference.

Installation

This AQTmodel comes as a source library currently written for OMNeT++ 4.5. You will need a running OMNeT++ 4 distribution, 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.

You'll need to

• source setenv in the omnet folder
• cd to the project folder
• run make to compile first,
• 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

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 called CE3).

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

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

Source Code Overview

Structure Semantics 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.