Home > Publications > Publikationen


Brinkmann, André;Scheideler, Christian;Awerbuch, Baruch:

Anycasting and Multicasting in Adversarial Systems: Routing and Admission Control.

, 2002


In this paper we consider the problem of routing packets in dynamically changing networks, concentrating on two different modes: anycasting and multicasting. In anycasting, a packet has a set of destinations but only has to reach any one of them, whereas in multicasting, a packet has a set of destinations and has to reach all of them. Both communication modes have a tremendous number of applications, but so far not much is known from a theoretical point of view about how to efficiently support these communication modes even in static networks. We demonstrate in this paper that even if both the network and the packet injections are under adversarial control, efficient distributed routing strategies can be found for both modes. This even holds if the adversary is not bounded in the number of injections, and therefore packets may have to be dropped from overfull buffers. In order to study the performance of our protocols, we use competitive analysis. The performance is measured in terms of communication throughput (i.e. the number of successful packet deliveries) and space overhead. Our results demonstrate that, in principle, efficient communication is possible even in such highly dynamic networks as mobile ad hoc networks and peer-to-peer networks.




author = {Brinkmann, André and Scheideler, Christian and Awerbuch, Baruch},
title = {Anycasting and Multicasting in Adversarial Systems: Routing and Admission Control},
institution = {Johns Hopkins University and University of Paderborn},
year = {2002},

Copy bibTeX to clipboard