Network Working Group S. Das Internet-Draft A. Swaminathan Intended status: Standards Track V. Narayanan Expires: September 4, 2009 Qualcomm, Inc. March 3, 2009 A Load Balancing Mechanism for REsource LOcation And Discovery draft-saumitra-p2psip-loadbalance-00 Status of this Memo This Internet-Draft is submitted to IETF in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. This Internet-Draft will expire on September 4, 2009. Copyright Notice Copyright (c) 2009 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents in effect on the date of publication of this document (http://trustee.ietf.org/license-info). Please review these documents carefully, as they describe your rights and restrictions with respect to this document. This document may contain material from IETF Documents or IETF Contributions published or made publicly available before November 10, 2008. The person(s) controlling the copyright in some of this Das, et al. Expires September 4, 2009 [Page 1] Internet-Draft loadbalance March 2009 material may not have granted the IETF Trust the right to allow modifications of such material outside the IETF Standards Process. Without obtaining an adequate license from the person(s) controlling the copyright in such materials, this document may not be modified outside the IETF Standards Process, and derivative works of it may not be created outside the IETF Standards Process, except to format it for publication as an RFC or to translate it into languages other than English. Abstract Load balancing is essential to effectively manage data and provide services on overlays. This draft presents a solution for load balancing the default topology plugin in RELOAD. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 3. Load Imbalance in DHTs . . . . . . . . . . . . . . . . . . . . 4 3.1. Imbalance in RELOAD DHT . . . . . . . . . . . . . . . . . 4 4. Load balancing solution . . . . . . . . . . . . . . . . . . . 5 4.1. Basic scheme . . . . . . . . . . . . . . . . . . . . . . . 5 4.2. Recommendations on virtual nodes . . . . . . . . . . . . . 6 4.3. Routing . . . . . . . . . . . . . . . . . . . . . . . . . 6 4.4. Dynamic update to system parameters . . . . . . . . . . . 7 4.5. Obtaining virtual node identities . . . . . . . . . . . . 9 4.5.1. Without enrollment server . . . . . . . . . . . . . . 9 4.5.2. With enrollment server . . . . . . . . . . . . . . . . 9 4.6. Extensions to overlays with heterogeneous nodes . . . . . 10 5. Security Considerations . . . . . . . . . . . . . . . . . . . 11 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11 7. Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 7.1. Comparison with Chord . . . . . . . . . . . . . . . . . . 11 7.2. Performance as Network grows . . . . . . . . . . . . . . . 12 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 14 8.1. Normative References . . . . . . . . . . . . . . . . . . . 14 8.2. Informative References . . . . . . . . . . . . . . . . . . 14 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 15 Das, et al. Expires September 4, 2009 [Page 2] Internet-Draft loadbalance March 2009 1. Introduction Load balancing is essential to effectively manage data and provide services on overlays. Load balancing, as an integral part of the overlay, encourages participation by imposing collective fate sharing on the nodes. Without such a scheme, overlay adoption may be significantly affected. However, the RELOAD DHT protocol based on Chord does not support operating the overlay in a load balanced manner. Consider a system with N nodes. If node and item identifiers are randomly chosen, then there is a O(log N) imbalance factor in the number of items stored at a node even if all the nodes and objects are assumed to be homogeneous. In the case of heterogeneous networks, where the capabilities of nodes (storage and bandwidth) can differ by multiple orders of magnitude, problem of load balancing becomes more important because the imbalance in load distribution could potentially create a bottleneck in the system. Finally, in the case of objects stored in the overlay with heterogeneous popularity or characteristics, the load to and from a node can become imbalanced in the overlay In summary load balancing is required in structured overlays such as RELOAD for the following reasons: o Using uniform hashing for object placement in the RELOAD DHT has an effect of producing a O(log N) imbalance factor. o RELOAD does not handle node heterogeneity as different nodes might have different capabilities. o RELOAD does not handle object-load heterogeneity as different objects might produce different amounts of load. For instance, some objects may be queried more resulting a larger traffic and load to/from the node that owns it. While we do not deal with this issue in our draft, by reducing the imbalance caused by the first two factors above, we make it easier to reduce the impact of this third factor. Additionally, the imbalance factor resulting due to object load heterogeneity can be addressed by other complementary techniques such as replication and caching. This draft presents a solution for load balancing the default DHT in RELOAD. Das, et al. Expires September 4, 2009 [Page 3] Internet-Draft loadbalance March 2009 2. Terminology The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [1]. 3. Load Imbalance in DHTs This section takes a closer look at load balancing properties of DHTs. Most DHTs, such as Chord, Pastry, CAN, Tapestry, employ uniform hashing to generate object IDs so that the object IDs are uniformly distributed over the ID space (example 0 to D = 2^128 - 1). Objects are then assigned to the nodes based on their IDs and the exact way that this is done differs in different DHTs. Let us assume that there are N nodes in the network. Suppose the nodes IDs are generated uniformly at random, then the probability that the ith largest nodeID is equal to k is given by: P(nodeID(i) == k) = (N-1)C(i-1) * (k/D)^(i-1) * (N-i)C(1) * (1/D) * (1 - (k+1)/D)^(N-i+1) For large N and D, this distribution can be approximated as follows: P(nodeID(i) == k) = e^(-k*N/D) * (k*N/D)^1 * (1/i!) Therefore, ith largest node IDs follows a Poisson distribution. The inter-node distance then follows an exponential distribution with parameter N/D. 3.1. Imbalance in RELOAD DHT In the case of the RELOAD DHT specified in [2], the data items are assigned to a node the object IDs are assigned circularly to the node whose ID follows the object ID. Therefore, the number of data items assigned to a node is proportional to the inter-node distance and, thus, follows an exponential distribution (c denotes an arbitrary constant) Pr(#items in node == x) = c * (N/D) * e^(c*(N/D)*x) The goodness of Chord for load balancing can be measured in terms of the imbalance metric defined as: imbalance factor= Maximum # of data items / Average # of data items Here, the maximum value is calculated as the one which is largest with probability: O(1 - (1/N^l)) where l is any constant. The Das, et al. Expires September 4, 2009 [Page 4] Internet-Draft loadbalance March 2009 imbalance factor measures the storage load of a server; the longer the interval is, the more data has to be stored in the server. For the case of Chord, this imbalance factor is of the order of O(log N). This suggests that the imbalance factor for Chord increases as the number of nodes in the network and as the number of nodes increase the maximum number of data items handled per node increases of the order of O(M*(logN/N)) where M denotes the total number of objects on the overlay. Ideally, we would expect the maximum value to be close to the average value of (M/N) giving an imbalance factor close to 1 for a good load balancing algorithm. Therefore, RELOAD base DHT is not very efficient for load balancing. 4. Load balancing solution Several research papers have proposed schemes to provide load balancing. Some of the schemes have general techniques while others are targeted towards optimizing a specific DHT. This solution proposed in this draft takes into account results and ideas from previous ideas for load balancing in [4], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14], [15]. 4.1. Basic scheme The basic scheme for load balancing proposed in this draft is an extension of the virtual nodes approach[7] with the benefit of reducing the routing state. At a high level, virtual nodes approach works in improving load balancing as follows. The work in [7] suggested that load balancing can be performed efficiently if each peer simulates a logarithmic number of "virtual peers". The method works by associating keys with virtual nodes, and mapping multiple virtual nodes (with unrelated identifiers) to each real node. The authors show that this will provide a more uniform coverage of the identifier space. For example, if we allocate O(log N) randomly chosen virtual nodes to each real node, with high probability each of the N bins will contain O(log N) nodes. The downside of this approach is the additional routing state and its maintenance cost. This draft proposes load balancing based on a proposal in [13]. The load balancing proposal in this draft is an improvement over the basic virtual nodes approach ([7]) to reduce the number of active connections while keeping the imbalance factor close to 1. In our approach, each physical node has O(log N) virtual nodes but with a constraint that the locations of the virtual nodes to be close to each other in the nodeID space. The main system parameters of the solution in this draft are: how Das, et al. Expires September 4, 2009 [Page 5] Internet-Draft loadbalance March 2009 many virtual nodes should be chosen exactly and what should the spacing between the node identifiers of those virtual nodes. The next sections describe draft recommendations on virtual nodes and routing for a load balanced DHT. Since these choices depend on network dynamics, this draft further discusses dynamically adjusting load balancing with network dynamics. This draft then discusses how virtual node identities are obtained in the two deployment scenarios that RELOAD envisions: with an enrollment server certified node identity and with a self-certified node identity when no enrollment server exists. Finally, this draft discusses extensions to overlays that have heterogeneous nodes. 4.2. Recommendations on virtual nodes Selection of virtual nodes require two decisions to be made. (1) How many virtual nodes (denoted by alpha) should we choose?, and (2) What should be the namespace spacing (represented by delta) in between these virtual nodes?. This section provides the draft's recommendation on choosing alpha and delta in this section. Nodes MUST use alpha = 2 log N virtual nodes virtual node identities for load balancing where N is the number of nodes in the overlay. This value was found to work well in simulations with diminishing returns found with increasing alpha beyond this value. The primary node id (denoted as vp) is chosen using existing techniques in RELOAD. The other virtual nodes are chosen such that the ith virtual node is uniformly distributed in [vp-i*delta, vp- (i+1)*delta]. The value of delta defines the spacing between the virtual nodes and this draft requires that node MUST choose the value of delta as 1/N where N is the number of nodes in the network. This value was found to perform well in simulations and is consistent with the value reported in [13]. While both these parameters depend on N (the size of the network), Section Section 4.4 describes an algorithm used to determine alpha and delta without performing explicit network size estimation. 4.3. Routing To locate any object in the overlay, the nodes MUST first employ the finger tables to reach the virtual node ID that is closest to the query object ID. At the end of this step, the chosen physical node may or may not have the object. If the physical node does not have the object, then it forwards the object request to its neighbors. Das, et al. Expires September 4, 2009 [Page 6] Internet-Draft loadbalance March 2009 Therefore the total number of message hops required for locating an object is of the order of O(log N) + 1. With regard to the routing state, each node MUST maintain only one finger table corresponding to the virtual node vp, and a neighbor table. The neighbor table of v MUST contain the entries of all nodes which maintain ownership of any part of the logN/N space that node v owns. As in the case of Chord, each virtual server belonging to the node obtains its successor list of its immediate successor. If this total length is greater than alpha, the clockwise-farthest entry is dropped to restrict the number of neighbor table entries to alpha. Further, it can be shown that the maximum number node IDs that fall within this space is 2logN resulting in those many neighbor table entries. Thus, this draft requires maintaining a lower number of connections than that of a pure virtual nodes based approach for load balancing. This is because, while the basic Chord scheme with O(log N) virtual nodes per physical node requires maintaining O(log N) sets of fingers (and O(log N) routing tables) for each physical node for efficient routing, this draft requires maintaining just one set of fingers (and routing table) per physical node. 4.4. Dynamic update to system parameters All DHTs require constant updating as the size of the network grows. For example, in the case of Chord, each node starts out with m entries in the finger table (if nodeIDs take values from 0 to 2^m-1). When the number of nodes in the network is small, some of these m entries collapse to the same node. As the number of nodes in the network increase, the finger table entries degenerate to pointing to different nodes and the number of fingers grows as O(log N). Thus, the number of fingers that each node has to maintain grows as O(log N) as N increases. A similar update step is required the solution in this draft scheme as well because the system parameters, alpha and delta, also depend upon the value of N. This section describes how nodes MUST update the values of alpha and delta as the network changes in size with the algorithm below. This draft proposes to update the system values each time the network size doubles as follows: Das, et al. Expires September 4, 2009 [Page 7] Internet-Draft loadbalance March 2009 UpdateAlphaDelta() { If (number_of_fingers increases by 1) { // Can be detected as in the case of Chord when finger tables are updated. This implies that the network size has about doubled. delta = delta/2; // update delta // Update existing virtual server locations for i = 1 to alpha virt_server_i = vp - (vp - virt_server_i)/2; // Choose new virtual server location between (vp - alpha*delta, vp - (alpha+1)*delta); virt_server_(alpha+1) = random (vp - alpha*delta, vp - (alpha+1)*delta); virt_server_(alpha+2) = random (vp (alpha+1)*delta, vp - (alpha+2)*delta); alpha = alpha + 2; Move_Data(); } If (number_of_fingers decreases by 1) { // Can be detected as in the case of Chord when finger tables are updated. This implies that the network size has about doubled. Remove virt_server_(alpha-1); //leave network with those virtual ids Remove virt_server_(alpha); delta = delta*2; // update delta alpha = alpha -2; // Update existing virtual server locations for i = 1 to alpha virt_server_i = vp - (vp - virt_server_i) * 2; Move_Data(); } } Figure 1: Alpha and delta update algorithm Note that the finger tables do not change due to the updates since the location of the primary nodeID is fixed. Das, et al. Expires September 4, 2009 [Page 8] Internet-Draft loadbalance March 2009 4.5. Obtaining virtual node identities 4.5.1. Without enrollment server When a new node, v, joins the system, the first primary node identity vp MUST be computed by applying the digest specified in the self- signed-permitted element of the overlay configuration document to the DER representation of the node's public key. The subsequent alpha - 1 virtual node ids MUST be computed as follows: the ith virtual id is chosen as random(vp - i*delta, vp - (i+1)*delta) This ensures that the chosen virtual nodes are close to each other and a maximum of logN/N apart. A node's public key relates to the vp and can be verified by other nodes. However, all other virtual node ids cannot be related to this public key so they need to be verified based on vp. There are two options to do this verification: o a. Use a constant fixed offset for the ith virtual node as vp - i*delta exactly. This removes the random component of the virtual node id selection. Since all virtual node ids are at fixed intervals from vp, a node can weakly verify the node id. However node id collisions may make this hard. o b. Use the current technique described in Section Section 4.2 with random selection in an interval. In this case a node can verify that the virtual node id is in a small range near vp. OPEN ISSUE: At the moment we recommend option (b), but this issue needs further analysis. 4.5.2. With enrollment server When an enrollment server is present, the added security benefits of the enrollment server certified node identities are for virtual node identities. The enrollment server is provided the values of the system parameters alpha and delta, and based on them, the enrollment server gives out a set of virtual node identities to a node. Similar to what a node itself does in a deployment without an enrollment server; the enrollment server MUST use a uniform hash function to randomly choose the primary virtual node ID from the space (0, 2^128 - 1); call this virtual node ID vp. The remaining (alpha - 1) node IDs MUST be then chosen by the enrollment server around vp in such a way that the ith virtual nodeID of v is chosen to be uniformly distributed in (vp - i/N, vp - (i+1)/N). These node IDs are then passed on to the node. Das, et al. Expires September 4, 2009 [Page 9] Internet-Draft loadbalance March 2009 When a node initially joins, it does not have an estimate of alpha and delta since that is based on the number of fingers in the routing table. Thus, the enrollment server MUST use existing values of alpha and delta in requests it receives from nodes in the current overlay or based on its own diagnostic messages sent into the overlay to determine the number of virtual nodes and the spacing in between the virtual nodes and consequently the node ids handed out to the joining node. If the overlay has recently formed the enrollment server MAY bootstrap the values of alpha and delta as 20 and 1/1000 respectively. The enrollment server may also choose to use past overlay size estimates it may possess to bootstrap alpha and delta as 2log(Nestimated) and 1/Nestimated. For example, an enrollment server at a venue based overlay which is torn down can use past size estimates. Note that the enrollment procedure in RELOAD already defines providing multiple node identities to the enrolling node. The change needed is to include the values of alpha and delta in the simple enrollment request. When the dynamic update algorithm notices a change in the system parameters, the node MUST request the enrollment server for a new set of identities and stop participating in the overlay network with the old node identities. The enrollment server MAY choose to implement diagnostics using mechanisms in [3] to ascertain that the node requesting identities is not requesting more than what is should based on the finger table sizes of a random sampling of other nodes in the overlay. 4.6. Extensions to overlays with heterogeneous nodes This draft can be extended for overlays with nodes with heterogeneous node capacities. Let the capacity of the node-v in the overlay be represented by Cv. If an overlay has nodes with heterogeneous nodes, nodes in the overlay MUST use alpha = 2*Cv*log N virtual nodes per physical node. The location of these (2Cv log N) virtual nodes MUST be chosen near the primary node location vp such that the location of the ith virtual nodeID is uniformly distributed in (vp - i/N, vp - (i+1)/N). Each physical node then maintains a total of O(Cv log N) neighbor entries and O(Cv log N) routing fingers. The imbalance factor for this scenario, defined as, Imbalance factor = Maximum # of data items / Cv*Average # of data items can be shown to be close to 1. Das, et al. Expires September 4, 2009 [Page 10] Internet-Draft loadbalance March 2009 Note that in addition to alpha and delta, the node capacity of the node MUST be passed to the enrollment server in the simple enrollment request. This capacity value is used by the enrollment server to calculate Cv as Cv(node n) = node_capacity(node n)/ sum_{k=1}^N node_capacity(node k). In deployments with no enrollment servers, the node MUST estimate Cv(node n) by obtaining its neighbors node capacities and building an estimate of average node capacity. 5. Security Considerations One important concern for the virtual nodes approach is that it is not easily enforceable. Given a set of virtual nodeIDs for a physical node, it must be ensured that the physical node actually takes ownership of all the virtual nodeIDs assigned to it. In the presence of a centralized enrollment server, this server can ensure that each physical node gets its share of the number of virtual nodes. In the absence of the enrollment server, the verification can be performed during the join process. For instance, in the case of Chord, when a new node joins the overlay, it contacts its neighbors to obtain neighbor relations and finger table entries. A similar approach can be adopted in the case of virtual nodes approach. In this scenario, each physical node provides its neighbors a list of 2 log N virtual node IDs. The neighbors first verify that the number of virtual node locations received is close to the number of virtual node locations that it owns before sending the finger table entries to the joining node. In this way, it can be ensured that each node has O(log N) virtual locations on the overlay. 6. IANA Considerations 7. Appendix This appendix lists a few performance results of the load balancing solution proposed in this draft. 7.1. Comparison with Chord Compared to the virtual markers approach in [5], this draft does not require O(log N) nodes to change their location upon each node arrival. For instance, in the case of the virtual markers approach, if O(log N) nodes change location, then O(log N/N) data objects need to be reassigned and at least O(2 log N) nodes are involved in this step. This is in addition to the messages required for updating Das, et al. Expires September 4, 2009 [Page 11] Internet-Draft loadbalance March 2009 routing tables which is O(log^3 N). In contrast to the virtual markers approach, this draft requires O(1/N) data objects to be reassigned and around O(log N) nodes send data to the joining node. The number of routing messages required is still O(log^2 N) similar to the case of Chord with no virtual nodes; this is because the number of connections is still O(log N) links per node. We performed some simulation studies to compare the performance of the solution in this draft scheme with Chord. In order to study the percentage of nodes with significant load imbalance, we look at the q-percentile load imbalance factor defined as the ratio of the q-percentile load and the average load. For example, a 99-percentile imbalance factor of 5 implies that less than 1 percent of nodes in the system have a load more than the value 5 times the average load. We tested the solution in this draft under N = 2^(15) and compared the results with Chord. We found that the 99-percentile imbalance factor for the solution in this draft is around 2. In comparison, our results with Chord suggest that the 100-percentile imbalance factor is around 9, the 99-percentile imbalance factor is around 4.5 and so on. This result suggests that in Chord, around 1% of the nodes have an imbalance between 4.5 and 9, 2% have an imbalance greater than 4 and so on compared to the solution in this draft where less than 1% of the nodes has an imbalance greater than 2. With regard to routing, our simulations compared the average route length for Chord (with one virtual server) with this draft's solution (2 log N) servers; the results showed that the both these DHT implementations require around the same number of hops. 7.2. Performance as Network grows In this section, we take a closer look at the performance of the solution in this draft as network size grows in terms of load imbalance factor and routing state maintenance. (1) Load Imbalance: In our simulations, we fix the value of the estimated network size to be Nest = 2^9, and chose alpha = 18 and delta = 2^(-9). The actual network size is then increased from 2^2 to 2^(14). When N < Nest, the spacing between virtual nodes (chosen as 1/Nest) is very small and the solution in this draft becomes similar to Chord. In this case, the load imbalance factor is of the order of O(log N). However, since the numerical value of N is small, the imbalance factor is still low and around 3 for most nodes as demonstrated by our simulations. As the value of network size, N, increases, the spacing, delta, comes into effect and the virtual nodes help balance the load. Our simulations indicate that the imbalance Das, et al. Expires September 4, 2009 [Page 12] Internet-Draft loadbalance March 2009 is around its lowest value of 2 when N = Nest, and increases slowly as N becomes larger than Nest. (2) Routing State: Here, we examine the performance this solution with regard to the amount of routing state that it needs to maintain as the network grows. We analyze the performance of the solution in this draft analytically to determine the number of hops required to reach a destination as a function of N and Nest. We perform the analysis in two steps: * [Step 1] Routing within a distance of 1/N from destination: If nodes in this solution employ only their primary virtual servers (and the corresponding O(log N) connections) for routing as in the case of Chord, it can be shown that any discretization built upon the solution in this draft would be able to get within a distance of 1/N from the destination node in O(log N) hops with O(logN) fingers per node. This results is unaffected by the relative values of N and Nest. * [Step 2] Last-mile: The number of hops required to route messages from within a distance of 1/N to the exact destination (referred to as the last-mile problem) would depend upon the exact realization of DHT and its construction of neighbor tables. In this draft, each node has alpha virtual servers chosen uniformly at random separated by a distance O(delta). Therefore, the number of nodes within a 1/N distance from a chosen location would be of the order of O(log N + N*log(1+s alpha delta)), where 's' is a constant independent of N. If alpha and delta are chosen using Nest, then the number of nodes within a 1/N distance can be approximated to be of the order of O(log N + N* log(Nest)/ Nest) for large Nest. Therefore, a random walk would lead to the final destination within O(log N + N* log(Nest)/Nest) hops. This result indicates that when N < Nest, the solution in this draft performs similar to Chord and messages can be routed to any node in O(log N) hops by maintaining O(log N) fingers and O(log N) successors. On the other hand, when N is much larger compared to Nest, O(N) hops might be required to reach the destination if the number of fingers per node is O(log N). However, this situation arises only when the network size estimation is very much lower than N and the value of alpha and delta are not updated as the network grows. 8. References Das, et al. Expires September 4, 2009 [Page 13] Internet-Draft loadbalance March 2009 8.1. Normative References [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [2] Jennings, C., Lowekamp, B., Rescorla, E., Baset, S., and H. Schulzrinne, "REsource LOcation And Discovery (RELOAD) Base Protocol", draft-ietf-p2psip-base-01 (work in progress), December 2008. [3] Yongchao, S. and X. Jiang, "Diagnose P2PSIP Overlay Network", draft-ietf-p2psip-diagnostics-00 (work in progress), January 2009. 8.2. Informative References [4] Bienkowski, M., Korzeniowski, M., and F. auf der Heide, "Dynamic load balancing in distributed hash tables", In Proc. of IPTPS, 2005. [5] Karger, D. and M. Ruhl, "Simple efficient load balancing algorithms for peer-to-peer systems", In 3rd International Workshop on Peer-to-Peer Systems (IPTPS), 2004. [6] Awerbuch, B. and C. Scheideler, "Group spreading: A protocol for provably secure distributed name service", In Proc. of the 31st Int. Colloquium on Automata, Languages, and Programming (ICALP), 2004. [7] Stoica, I., Morris, R., Karger, D., Kaashoek, M., and H. Balakrishnan, "Chord: A scalable peer-to-peer lookup service for internet applications", In Proc. of the ACM SIGCOMM, 2001. [8] Fraigniaud, P. and C. Gavoille, "The content-addressable network d2b", Technical Report 1349, LRI, Univ. Paris-Sud, France, 2003. [9] Kaashoek, F. and D. Karger, "Koorde: A simple degree-optimal hash table", In Proc. 2nd International Workshop on Peer-to- Peer Systems (IPTPS), 2003. [10] Naor, M. and U. Wieder, "Novel architectures for p2p applications: the continuous-discrete approach.", In Proc. of the 15th ACM Symp. on Parallel Algorithms and Architectures (SPAA), 2003. [11] Byers, J., Considine, J., and M. Mitzenmacher, "Simple load balancing for distributed hash tables", In 2nd International Das, et al. Expires September 4, 2009 [Page 14] Internet-Draft loadbalance March 2009 Workshop on Peer-to-Peer Systems (IPTPS), 2003. [12] Manku, G., "Routing Networks for Distributed Hash Tables", In Proc. of the Principles of Distributed Computing (PODC), 2003. [13] Godfrey, B. and I. Stoica, "Heterogenity and load balance in Distributed Hash Tables", IEEE INFOCOM, 2005. [14] Godfrey, B., Lakshminarayanan, K., Surana, S., Karp, R., and I. Stoica, "Load balancing in dynamic structured p2p systems", In 23rd Conference of the IEEE Communications Society (INFOCOM), 2004. [15] Rao, A., Lakshminarayanan, K., Surana, S., Karp, R., and I. Stoica, "Load balancing in structured p2p systems", In 2nd International Workshop on Peer-to-Peer Systems (IPTPS), 2004. Authors' Addresses Saumitra M. Das Qualcomm, Inc. 3195 Kifer Road Santa Clara, CA USA Phone: +1 408-533-9529 Email: saumitra@qualcomm.com Ashwin Swaminathan Qualcomm, Inc. 5775 Morehouse Dr San Deigo, CA USA Phone: +1 858-845-8775 Email: sashwin@qualcomm.com Das, et al. Expires September 4, 2009 [Page 15] Internet-Draft loadbalance March 2009 Vidya Narayanan Qualcomm, Inc. 5775 Morehouse Dr San Deigo, CA USA Phone: +1 858-845-2483 Email: vidyan@qualcomm.com Das, et al. Expires September 4, 2009 [Page 16]