Personal tools
You are here: Home Events Abstract Archives 2001 Simple Routing Strategies for Adversarial Systems

Simple Routing Strategies for Adversarial Systems

Petra Berenbrink Dept. of Computer Science University of Warwick 4pm Tuesday 20 November Room 2511, JCMB, King's Buildings

In this talk I consider the problem of delivering dynamically changing input streams in dynamically changing networks where both the topology and the input streams can change in an unpredictable way. In particular, I will present two simple distributed balancing algorithms (one for packet injections and one for flow injections) and show that for the case of a single receiver these algorithms will always ensure that the number of packets in the system is bounded at any time step, even for an injection process that completely saturates the capacities of the available edges, and even if the network topology changes in a completely unpredictable way. Interestingly, the balancing algorithms do not only behave well in a completely adversarial setting. We show that also in the other extreme of a static network and a static injection pattern the algorithms will converge to a point in which they achieve an average routing time that is close to the best possible average routing time that can be achieved by any strategy. This demonstrates that there are simple algorithms that can be efficient at the same time for very different communication scenarios. To have such algorithms will be of particular importance for communication in wireless mobile ad hoc networks (or short MANETs), in which at some time the connections between mobile nodes and/or the rates of input streams may change quickly and unpredictably and at some other time may be quasi static.

Joint work with Baruch Awerbuch, Andre Brinkmann, Christian Scheideler.

Document Actions