Broker-placement in latency-aware peer-to-peer networks

In large peer-to-peer (P2P) overlay networks, nodes usually share resources to support all kinds of applications. In such networks, a subset of the nodes may assume the role of broker in order to act as intermediaries for finding the shared resources. When some notion of distance between nodes such as the internode latency is defined, a brokers may be responsible for maintaining information about resources shared by a group of nodes that are close to each other, with the set of nodes assigned to a broker being determined by the broker's location. In this paper, we present a broker-placement algorithm that finds a suitable location for a new broker when some broker is overloaded in such a way that some of the nodes are reassigned from the overloaded to the new broker. With latency as a metric, an overlay network can be embedded in an Euclidean space R^d, and our algorithm amounts to an optimization problem of selecting a suitable region in R^d for broker-placement, where a region represents equivalent broker locations. Our algorithm guarantees that if suitable regions exist, one of them will be found. The worst-case complexity of the algorithm is O (n^{d + 1}) with n the number of nodes that may be assigned to the new broker, which is optimal up to a linear factor in n. We further show a simple optimization that brings down the complexity of the algorithm to a linear function of n in most of the cases. The linear complexity of the broker-placement algorithm is confirmed in a series of experiments on a real dataset. In addition, the performance of our broker-placement algorithm is compared to the performance of a naive approach, and it turns out that in a system with one million servers and one hundred brokers, our broker-placement algorithm is roughly 150 times more efficient.