Integrated routing algorithms for anycast messages

Use of anycast service can considerably simplify many communication applications. Two approaches can be used for routing anycast packets. Single-path routing always uses the same path for anycast packets from a source, while multipath routing splits anycast traffic into several different paths. The former is simple and easy to implement, while the latter may potentially reduce congestion, improving delay and throughput performance. However, multipath routing may require additional cost to maintain multipath information. To take advantage of both approaches and overcome their shortcomings, we develop a set of integrated routing algorithms that can adaptively select a subset of routers in the network to carry out multipath routing for anycast messages. We demonstrate that systems using our integrated routing algorithms perform substantially better than those where either the single-path or multipath approach is used alone.