Adversarial Queueing Theory

The Adversarial Queueing Theory is a model in order to analyse Queueing-Strategies. This Theory was introduced by Andrews et. al in 1996 and 2001. The common used Queueing-Strategy is FIFO (First In First Out) which performs poorly in a lot of models.

One major problem in analysing a Queueing-Strategy is to model network traffic which is realistic. Several models use therefore observed network or probabilistic generated network traffic, e.g. using a Poisson-Distribution or a Stochastic-Event. In contrast to this, in the Adversarial Queueing Theory no Probabilistic-Event or Data is used. This Theory only uses an Adversarial which generates network-traffic deterministically. The Adversarial knows the topology of the network and the behaviour of the Queueing-Strategy. With this information, it tries to increase the number of packets in the system and the delivery-time – the time between sending and receiving the packet - of a packet. Furthermore, the Queueing-Strategy tries to limit the number of packets in the system and the delivery-time of a packet. The Queueing-Strategy is evaluated using the maximum value of these two parameters.

Currently (March 2006), there does not exist any Queueing-Strategy for which it is proved that the number of packets in the system as well as the delivery-time of a packet is limited to o(exp(diameter of the network)). Furthermore, there exists an example where the common used Queueing-Strategy FIFO cannot limit the number of packets in the system as well as the delivery-time of the packet. All other basic Queueing Strategies except LIFO (Last In First Out) have at least one example where the number of packets and the delivery-time of the packets is at least exponential in the diameter of the network. For LIFO, this is an open question.

The global aim is to design a Queueing-Strategy which limits the number of packets in the system as well as the delivery-time of the packets to o(exp(diameter of the network)) or even to c*n. For more information, I refer to the articles concerning the Adversarial Queueing Theory.

Why do I use this Theory?

I do not use the Adversarial Queueing Theory for analysing any Queueing-Strategy. In order to test and simulate the artificial immune system, I need network traffic which is as realistic as it could be. For the generation of this network traffic, I use the idea of the Adversarial Queueing Theory. There exist an adversarial in the network which knows the topology of the network and the behaviour of the artificial immune system and the aims of the adversarial are to insert attacks and to maximize the number of succeeded attacks. Consequently, I do not care about any stochastic models or I have to collect and interpret data from a network. Anymore, I can model using such an adversarial nearly all possible network traffic and I can test the artificial immune system using this realistic environment.

"Adversarial Queueing Theory" is mentioned on: SANA_AIS