Introduction

Decentralized structured overlays and distributed hash tables proffer a unique vision of computing: each machine seamlessly contributes to and benefits from a large service-oriented network. This vision has yet to be realized, in part, because machines are not identical, because the workload applied to the system may be heavy-tailed, and because node availability and churn rates may change over time. Learning to adapt to these characteristics through load balancing in a decentralized, scalable, and secure manner is a step toward realizing this ideal of computing.

Several existing proposals for load balancing algorithms in this context have focused on ideal conditions [1,26,30,32]. They have made unrealistic assumptions about node heterogeneity, workload skew, and node churn. In general, they have assumed that nodes are uniform, that there is no skew in the workload, and that nodes are neither arriving nor departing. Deployed systems do not adhere to these idealistic conditions [39,45].

Other proposals have attempted to handle skew, churn, and heterogeneity [12,20,35]. Those that achieve good performance let nodes join as normal and then reactively position nodes to arbitrary locations in the namespace. Arbitrarily choosing identifiers (IDs) forfeits an important security goal for p2p systems: a verifiable identifier. Without verifiable IDs tying virtual overlay addresses to specific agents, application building blocks such as reputation [13], micropayments [46], and auctions [23] are not possible outside of a trusted network.

In this paper, we propose k-Choices, a load balancing algorithm for structured overlays that supports wide variation in skew, heterogeneity, and churn while retaining the security and application advantages afforded by verifiable IDs. At a high level, the algorithm works as follows: (a) each node generates a set of verifiable IDs based on a single unit of certified information; (b) at join time, a node greedily reduces discrepancies between capacity and load both for itself and for nodes that will be affected by its join; and (c) optionally, each node experiencing overload or underload may periodically probe the network and reposition itself to another element from its set of verifiable IDs. Minimizing discrepancies between load and capacity achieves load balance, and limiting IDs to a well-defined set keeps the algorithm secure.

This paper proceeds as follows. In Section II, we introduce our model and assumptions. In Section III, we present the k-Choices algorithm in detail. In Section IV, we review four state-of-the-art algorithms for load balancing in p2p systems. In Sections V and VI, we present results from trace-driven simulations where we vary system characteristics, including node heterogeneity, skew, and churn. We also present results from an implementation of k-Choices. Sections VII and VIII present related work and conclusions, respectively.