Efficient distributed computation of distance sketches in networks

摘要: Distance computation (e.g., computing shortest paths) is one of the most fundamental primitives used in communication networks. The cost effectively and accurately pairwise network distances can become prohibitive large-scale networks such as Internet Peer-to-Peer (P2P) idea behind distance sketches to preprocess graph store a small amount information (called sketch or label) that whenever query for any issued, be well approximated (i.e., with stretch) very quickly an online fashion. Specifically, pre-processing (usually) involves storing this each node, at time only concerned nodes need looked up compute approximate distance. In paper, we present first theoretical study derived from oracles distributed network. We fast algorithm sketches, based on implementation oracle scheme (Thorup Zwick, J ACM 52(1):1---24, 2005). also show how modify basic construction achieve different tradeoffs between number pairs which estimate accurate, size message complexity necessary them. These then combined give efficient provable average-case worst-case performance. Our algorithms use small-sized messages hence are suitable bandwidth-constrained networks, various networking applications topology discovery construction, token management, load balancing, monitoring overlays, several other problems algorithms.