The hopcount to an anycast group

The probability density function of the number of hops to the most nearby member of the anycast group consisting of m members (e.g. servers) is analysed. The results are applied to compute a performance measure η of the efficiency of anycast over unicast and to the server placement problem. The server placement problem asks for the number of (replicated) servers m needed such that any user in the network is not more than j hops away from a server of the anycast group with a certain prescribed probability. Two types of shortest path trees are investigated: the regular k ‐ary tree and the irregular uniform recursive tree. Since these two types of trees indicate that the performance measure η ≈ 1 − a log m where the real number a depends on the details of the tree, it suggests that for trees in real networks (as the Internet) a same logarithmic law applies. An order calculus on exponentially growing tree further supplies evidence for the conjecture that η ≈ 1 − a log m for small m . Copyright © 2004 John Wiley & Sons, Ltd.