On anycast routing with bandwidth constraint

Anycast refers to the transmission of data from a source node to (any) one member in a group of designated recipients in a network. In this paper, we study the problem of finding a set of low cost paths for anycast routing with bandwidth constraint. The anycast routing problem (ARP) in this case involves the construction of a set of low-cost paths with bandwidth requirements, one for each source, for anycasting messages to one of the member in the anycast destination group. An optimal solution to ARP is a set of paths, one for each source node, that incurs the least overall cost. This problem is known to be NP-complete and hence a heuristic algorithm is proposed to find solutions for the problem. In addition. we derive a lower bound on the cost of an optimal solution for ARP by using Lagrangean Relaxation and Subgradient Optimization techniques. This lower bound is used to evaluate the performance of anycast routing algorithms in terms of their ability to find close-to-optimal solution. Simulation results show that the lower bound is tight and that our proposed algorithm is able to achieve good performance in terms of its ability of finding a set of low-cost paths for the problem. (C) 2003 Elsevier Science B.V. All rights reserved.