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.
Martin Grohe
Tuesday 9 October 2001
An error occured whilst processing this directive