An efficient hypercube labeling schema for dynamic Peer-to-Peer networks

This paper addresses the general problem of reducing unnecessary message transmission thereby lowering overall bandwidth utilization in a Peer-to-Peer (P2P) network. In particular, we exploit the characteristics of a P2P network engineered to resemble a hypercube. The reason for doing this is to achieve constant computation time for inter-node distances that are needed in the process of query optimization. To realize such a hypercube-like engineered structure, we develop a new labeling scheme which assigns identifiers (labels) to each node and then uses these labels to determine inter-node distances as is done in a hypercube, thus eliminating the need to send out queries to find the distance from one node to another. The labels allow for creating a virtual overlay which resembles a hypercube. We prove that the labeling scheme does in fact allow for reducing bandwidth utilization in the network. To confirm our theoretical findings we conduct various experiments with randomly selected P2P networks of various sizes. Detailed statistics on the outcome of these experiments are provided which show clearly the practical utility of the labeling approach.