Premium
The hopcount to an anycast group
Author(s) -
Mieghem Piet Van
Publication year - 2004
Publication title -
international journal of communication systems
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.344
H-Index - 49
eISSN - 1099-1131
pISSN - 1074-5351
DOI - 10.1002/dac.642
Subject(s) - unicast , anycast , computer science , server , logarithm , tree (set theory) , conjecture , measure (data warehouse) , group (periodic table) , computer network , the internet , steiner tree problem , path (computing) , function (biology) , combinatorics , multicast , mathematics , routing (electronic design automation) , operating system , data mining , mathematical analysis , chemistry , organic chemistry , evolutionary biology , biology
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.