P2PSIP Working Group J. Peng Internet-Draft L. Le Intended status: Standards Track China Mobile Expires: January 5, 2012 B. He S. Duan China CATR July 4, 2011 Load Balance Consideration for p2psip network draft-peng-p2psip-loadbalance-00 Abstract This document introduces the practical load balance problems in DHT- based P2P systems and analyses the reasons of these problems. In this document, it introduces some typical mature load balance solutions for Object Load Balance and Routing Load Balance. This document can be taken as a background investigation for implementing load balance in P2PSIP protocol. Status of this Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at http://datatracker.ietf.org/drafts/current/. 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." This Internet-Draft will expire on January 5, 2012. Copyright Notice Copyright (c) 2011 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 (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect Peng, et al. Expires January 5, 2012 [Page 1] Internet-Draft p2psip load balance July 2011 to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Node Load overview . . . . . . . . . . . . . . . . . . . . . . 4 3. Load balance Problems in the DHT-based P2P network . . . . . . 5 3.1. Load balance problems for Object Load . . . . . . . . . . 5 3.2. Load balance problems for Routing Load . . . . . . . . . . 6 4. Solutions for Load Balance . . . . . . . . . . . . . . . . . . 7 4.1. Solutions for Object Load balance . . . . . . . . . . . . 7 4.1.1. Solutions for the mismatch of map relationship between nodes and objects . . . . . . . . . . . . . . 7 4.1.2. Solution for the heterogeneity of node capability . . 8 4.1.3. Solution for the uneven distribution of query . . . . 8 4.1.4. Solution for adapting system dynamic . . . . . . . . . 9 4.2. Solutions for Routing Load Balance . . . . . . . . . . . . 9 4.3. Summary . . . . . . . . . . . . . . . . . . . . . . . . . 10 5. Future work . . . . . . . . . . . . . . . . . . . . . . . . . 11 6. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 12 7. Security Considerations . . . . . . . . . . . . . . . . . . . 13 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 14 9. Normative References . . . . . . . . . . . . . . . . . . . . . 15 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 16 Peng, et al. Expires January 5, 2012 [Page 2] Internet-Draft p2psip load balance July 2011 1. Introduction In the DHT-based P2P network, since single node doesn't know the information of global load distribution and the distribution of user queries is not even, how to balance every node's load is a difficult problem. Every node shares the network load through holding a portion of key space in DHT-based network. At ideal conditions, the nodeID and user data evenly distribute in the DHT space, the access probability for each resource is basically equivalent, so the whole load evenly distributes on every node, thus the system has good capability of load balance and can operate in optimal state. But there is great discrepancy in real DHT-based P2P network and P2P systems may suffer from load-imbalance problems that can degrade the performance. These problems can be caused by different reasons such as skewed object distribution or inefficient routing. Load unbalance is critical and must be treated in order to fairly use the available physical resources. Dynamically changing popularities of data items and skewed user query patterns in P2P systems may cause some of the peers to become bottlenecks, thereby resulting in severe load imbalance and consequently increased user response times. This draft lists some reasons which cause the load balance problems and examples some typical solutions which have been widely cited and demonstrated. The presented load balance solutions aim to balance both object and routing load in the system by changing the node's responsibilities, such as address space or the routing table. The main purpose of this draft is to provide an investigation for current research on load balance which is as background information for developing P2PSIP protocol. We suggest that it must consider load balance problems for P2PSIP when handling user calls. Peng, et al. Expires January 5, 2012 [Page 3] Internet-Draft p2psip load balance July 2011 2. Node Load overview In the DHT-based P2P system, node load consists of two parties: Object Load: it's caused by the objects maintained by the node; Routing Load: it's caused by the query message forwarding according to the routing algorithms and is also called Query Load. For the Object Load, it can be subdivided to two parties: Narrow Object Load: in this case, the node only provides the storage space for the objects, the node load is determined by the number of the objects and the size of each object and is irrelevant to the access objects on the other nodes. Object Access Load: in this case, the objects stored in the node is frequently requested, the node must consume certain resource when handling every request, such as network bandwidth or CPU computing capability, so this kind of load is related to the access frequency and is called Object Access Load. Peng, et al. Expires January 5, 2012 [Page 4] Internet-Draft p2psip load balance July 2011 3. Load balance Problems in the DHT-based P2P network 3.1. Load balance problems for Object Load Here lists some load balance problems for Object Load and most of them are common problems except few exceptional ones. (1) The mismatch of map relationship between nodes and objects. The DHT system uses the consistent hashing to determine the map relationship between nodes and objects, but [CONSISTENTHASH] points that the map results by consistent hashing have inherent heterogeneity. The Identifiers obtained by the hashing will evenly distribute in the address space, but the responsible region determined by the node identifier has different size, the number of objects charged by the some nodes is O(logN) times than the average value. (2) The heterogeneity of node disposal capability. Many measurements show that there is great difference for different node disposal capability. Sometimes the powerful node has still many idle resources and the weak node is almost overwhelmed by the overload. (3) The different size and uneven distribution of objects. The most typical examples are the file-sharing systems and storage systems and every node in the system may have different number of objects which may have different file chunks. (4) The uneven distribution of query. The distribution of query is the distribution of query number for every object during certain time. This distribution may be influenced by the object popularity and the popular object will become the hot spot of query. The current measurements show that the distribution of query messages follows the Zipf distribution in P2P file-sharing systems. (5) The dynamic of nodes. It's also called Churn. The churn will cause the size change of the associated region and the transfer of the associated objects between nodes, thus change the distribution of the load. (6) The dynamic of query. It means the dynamic of the object query distribution which include the change of the query frequency and the hot spot transfer between objects. The dynamic of query will directly influence the object access load. Peng, et al. Expires January 5, 2012 [Page 5] Internet-Draft p2psip load balance July 2011 (7) The dynamic of object. It means that the object randomly joins or exits the system, and it also includes those objects which exit the system as the node fails. Compared to the node churn, the dynamic of object has the similar influence to the system load balance, so the dynamic of object and node is usually put together to handle. The dynamic of node, query and object is usually influence each other, so we call these three dynamic to Network Dynamic or System Dynamic. 3.2. Load balance problems for Routing Load Compared to the Object Load, the load balance of Routing Load is irrespective to the node which possesses the object, the size of the region charged by the node and the distribution of the objects, but it needs to consider the possible effects by applied the routing algorithms. (1) The heterogeneity of node disposal capability. It's similar to the Sec 3.1. (2) The uneven distribution of query. The routing balance algorithms must make a point of handling this instance. The query hot spots will bring a plenty of routing load, this load can congregate to the regions around hot spots and form the routing hot spots, thus cause the node congestion. (3) The dynamic of query. It will directly influence the number and distribution of routing load. In order to handle the dynamic of query, it is necessary to collect the information of the query dynamic and carry out regulation according to the dynamic load. (4) The dynamic of node. The churn has some influence to the distribution of routing load, it can increase or decrease the number of nodes of some node sets which can handle specified queries, thus change the other node load in the same set. (5) The routing algorithms. In the DHT-based network, the queries which are received and handled by the node is nearly related to the routing algorithms. The current researches show that the DHT routing convergence will not make obvious influence on the object load balance, but give a new challenge to the distribution of routing load balance. Peng, et al. Expires January 5, 2012 [Page 6] Internet-Draft p2psip load balance July 2011 4. Solutions for Load Balance The load balance in DHT-based P2P network has been studied for many years and here gives some typical algorithms/solutions to show how to solve this problem from each aspect. 4.1. Solutions for Object Load balance 4.1.1. Solutions for the mismatch of map relationship between nodes and objects [CONSISTENTHASH] shows that there is a O(logN) unbalance factor for the map results of consistent hashing which can cause mismatch of map relationship between nodes and objects. In this case, the aim of the load balance algorithms is to obtain the match of map relationship between nodes and objects. The regulation policies for this problem can be divided to two kinds: one is to adjust the node identifier to adapt the distribution of the objects; the other is to adjust the object identifier to adapt the distribution of the nodes. 4.1.1.1. The policy of node regulation This kind of ways can also be called Address Space Balance method and its aim is to reduce the unbalance factor to the constant magnitude O(1) by regulate every node charged region to the almost same size. [CONSISTENTHASH] notes that the load unbalance problems can be solved by using Virtual Node (VN) or Virtual Server (VS). Every physical node has many VNs, each VN independently maintains a party of identifier space, so the load on the physical node is determined by the sum of all regions maintained by its all VNs. When the number of VNs is more and more, the sum of each node's region accords with normal distribution and thus can guarantee that the region size charged by every physical node has the expected value O(1/N). [ITEMBALANCE] proposes a way to limit the range of node identifier selection, each node prepares logN identifiers in advance and chooses one to use according to the dynamic load. [ITEMBALANCE] can guarantee that the region size charged by every node retains at O(1/N). 4.1.1.2. The policy of object regulation The aim of this policy is to move the object to the suitable region. The node can arbitrarily select node identifier, but the object can't change the hashing result of it and this will cause the other nodes can't find this object. Peng, et al. Expires January 5, 2012 [Page 7] Internet-Draft p2psip load balance July 2011 The first ways is to use multi-hashing functions to generate many identifiers for one object and choose the most suitable place. [TWOCHOICES] presents Single Host with Multi-identifier Algorithm and applies theory of the Power of two random choices to load balance. When the key maps to the ID, the algorithm uses d hash functions (usually d>=2), there are d IDs and d corresponding nodes, then the algorithm chooses the lightest load node to store the key. If there are n items, n peer nodes and d>=2 hash functions, the node can maintain a loglogn/logd + O(1) maximum load with high probability. The second ways is to move the object from the primary node to the new node by means of the pointers in routing table. [OBJECTMOVE] proposes to use a second hash function to obtain a subset of r+1 VNs, places object replicas on a lightly-loaded subset of nodes in Chord's successor list and choose the object on the r nodes with the lowest load. 4.1.2. Solution for the heterogeneity of node capability The above Address Space Balance algorithms assume that every node has equal disposal capability and responsible region and this assume is verified to be illogical by the current P2P network measurements, so the load balance algorithms must consider the heterogeneity of node disposal capability. [CFS] firstly proposes the way to handle the heterogeneity of nodes and this algorithm decides the number of VNS created according to the node disposal capability. When the node is overload, this algorithm allows to delete some VNs to reduce the load. One possible result is that some nodes alternately overload: node A deletes one VN and this makes node B overload, then node B delete one VN and this makes node C overload again, and this phenomenon is called Thrashing. [HETERHASH] proposes a load balance algorithm based on Chord. In this algorithm, the node can create more VNs as its capability is more powerful. If node disposal capability is lower than some threshold, this node will be not allowed to create VN. For one physical node, its all VNs are located in some consecutive regions, so this node can be viewed as a large virtual node and share a virtual routing table (viz. Finger table). So the node is more powerful, its region is more bigger and this can reduce the query forwarding between many VNs on the same node (only one hop is enough). 4.1.3. Solution for the uneven distribution of query The uneven distribution of query will cause hot spots problem and usually solve these problems by setting caching or replica. Peng, et al. Expires January 5, 2012 [Page 8] Internet-Draft p2psip load balance July 2011 [KCHOICE] proposes a load balance algorithm k-choice based on Virtual Server (VS) regulation mechanism. Every node can only create VS at the k scheduled location. When the node joins the system, it can guess the possible influence on its own and neighbor node's load from the distribution of query if choosing different node identifiers, then it uses greedy algorithm to the suitable location from the k location and create VS. The node also can create VS or regulate VS location according to the current dynamic load of each VS. This algorithm essentially adapts the load distribution by dynamically regulating the region size. 4.1.4. Solution for adapting system dynamic In real P2P systems, the distribution of nodes and queries has strong dynamic and this can cause the load distribution varying with time. It request that the node can dynamically regulate the load and adapt to the system dynamic. When using VN/VS mechanism, the node can dynamically increase or decrease some VNs to change its own load. If the VN can be transferred from high-load node to the low-load node, this can avoid the Thrashing problem in [CFS]. So [LB-P2P] gives three load balance policies based on VS transfer: one to one, one to may and many to many, and its basic idea is to move load from overload nodes to light-load nodes by VS transfer. In some applications, the load regulation involves the object movement from one node to another node and this will make demand on the node storage capability and network bandwidth. So for these applications, it must consider the cost for object movement during load balance process. It is a good way for load transfer during the proximity nodes. So many load balance algorithms take the node proximity as one of key design elements. [KARY] presents the k-ary tree model. Relying on a self-organized, fully distributed k-ary tree structure constructed on top of a DHT, load balance is achieved by aligning those two skews in load distribution and node capacity inherent in P2P systems--that is, has higher capacity nodes carry more loads. The proximity information is used to guide virtual server reassignments such that virtual servers are reassigned and transferred between physically close heavily loaded nodes and lightly loaded nodes, thereby minimizing the load movement cost and allowing load balancing to perform efficiently. 4.2. Solutions for Routing Load Balance In the DHT-based P2P network, the routing load of node is close related to its routing table because of the influence of the routing Peng, et al. Expires January 5, 2012 [Page 9] Internet-Draft p2psip load balance July 2011 rules. The current algorithms for solving the routing load balance problems usually focus on the extended work on routing table. Compared to the study of Object Load balance, the number of the papers for Routing Load Balance is much less. Here gives two topical ideas: (1) Using irregular routing table. The simplest way is that the more powerful node has bigger routing table. The node also can regulate the size of routing table according to the network scale and node dynamic. During the routing table initiation process, the node can choose its neighbors according to its neighbor's capability. (2) Increasing the redundancy of routing table. Each item in the routing table has many candidates, the routing algorithm will choose load-lowest node as next hop when forwarding queries. 4.3. Summary Many solutions have been proposed to tackle the load balancing issue in DHT-based P2P systems. However, existing load balancing approaches have some limitations. They either ignore the heterogeneity of node capabilities, or transfer loads between nodes without considering proximity relationships, or for other reasons. So there are no consummate solutions now. In current P2P systems, there are few which carry out comprehensive load balance methods but resort to the characteristics of DHT hash function. Peng, et al. Expires January 5, 2012 [Page 10] Internet-Draft p2psip load balance July 2011 5. Future work The future work is to study how to implement load balance algorithms in P2PSIP protocol. Peng, et al. Expires January 5, 2012 [Page 11] Internet-Draft p2psip load balance July 2011 6. Acknowledgements No acknowledgements at this time. Peng, et al. Expires January 5, 2012 [Page 12] Internet-Draft p2psip load balance July 2011 7. Security Considerations This draft does not introduce any new security issues. Peng, et al. Expires January 5, 2012 [Page 13] Internet-Draft p2psip load balance July 2011 8. IANA Considerations This memo includes no request to IANA. Peng, et al. Expires January 5, 2012 [Page 14] Internet-Draft p2psip load balance July 2011 9. Normative References [CONSISTENTHASH] Karger, D., Lehman, E., and T. Leighton, "Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the worldwide web", 1997. [ITEMBALANCE] Karger, D. and R. Ruhl, "Simple Efficient Load Balancing Algorithms for Peer-to-Peer System", 2004. [TWOCHOICES] Byers, J., Considine, J., and M. Mitzenmacher, "Simple Load Balancing for Distributed Hash Tables [J]", 2003. [OBJECTMOVE] Swart, G., "Spreading the load using consistent hashing: a Preliminary report", 2004. [CFS] DABEK, D., KAASHOEK, K., and D. Karger, "Wide-area cooperative storage with CFS", 2001. [HETERHASH] Godfrey, P. and I. Stoica, "Heterogeneity and load balance in distributed hash tables", 2005. [KCHOICE] Ledlie, J. and M. Seltzer, "Distributed, secure load balancing with skew, heterogeneity, and churn", 2005. [LB-P2P] Rao, R., Laksminarayanan, L., Surana, S., Karp, K., and I. I.Stoica, "Load Balancing in Structured P2P Systems", 2003. [KARY] Zhu, Y. and Y. Hu, "Efficient, Proximity-aware load balancing for DHT-based P2P systems [J]", 2005. Peng, et al. Expires January 5, 2012 [Page 15] Internet-Draft p2psip load balance July 2011 Authors' Addresses Jin Peng China Mobile Unit 2, 28 Xuanwumenxi Ave, Xuanwu District Beijing 100053 P.R.China Phone: 86-13911281193 Email: Penjin@chinamobile.com Lifeng Le China Mobile Unit 2, 28 Xuanwumenxi Ave, Xuanwu District Beijing 100053 P.R.China Phone: 86-13910019925 Email: Lelifeng@chinamobile.com Baohong He China CATR Beijing 100045 P.R.China Phone: 86-10-62300050 Email: Hebaohong@catr.cn Duan Shihui China CATR Beijing 100045 P.R.China Phone: 86-10-62300068 Email: Duanshihui@catr.cn Peng, et al. Expires January 5, 2012 [Page 16]