Efficient routing algorithms for anycast communication

An anycast packet is one that should be delivered to one member in a group of designated recipients. Using anycast services may considerably simplify some applications. Little work has been done on the problem of routing anycast packets. In this paper, we propose and analyze three routing algorithms for anycast packets: i) source-destination based routing with weighted random selection (SD/WRS), ii) destination based routing with weighted random selection (D/WRS), and iii) the shortest shortest path first (SSPF) algorithms. The SSPF algorithm is a simple extension to the traditional SPF algorithm for routing unicast packets. The SD/WRS and D/WRS algorithms explicitly take into account characteristics of anycast message traffic and its recipient group. As a result, our simulation study shows that both the SD/WRS and D/WRS algorithms perform much better than SSPF in terms of average end-to-end packet delay. In particular, the SD/WRS algorithm performs very close to a dynamic optimal algorithm in most cases. Our algorithms are simple, efficient, and compatible with the most of existing routing technologies.