[Docs] [txt|pdf] [Tracker] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01

Network Working Group                                         E. Harjula
Internet-Draft                                             M. Ylianttila
Intended status: Informational                        University of Oulu
Expires: September 9, 2010                                 March 8, 2010


       Load balancing models for DHT-based Peer-to-Peer Networks
              draft-harjula-p2psip-loadbalancing-survey-01

Abstract

   Load balancing in structured (DHT-based) Peer-to-Peer (P2P) systems
   has been thoroughly studied during the past years.  This draft
   provides a review of the existing and proposed load balancing
   mechanisms for structured P2P systems, categorizes them to four
   fundamental load balancing models, and introduces their main
   characteristics.

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 9, 2010.

Copyright Notice

   Copyright (c) 2010 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



Harjula & Ylianttila    Expires September 9, 2010               [Page 1]


Internet-Draft          DHT Load Balancing Models             March 2010


   (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
   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 BSD License.


Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
   2.  Terminology  . . . . . . . . . . . . . . . . . . . . . . . . .  4
   3.  Fundamental load balancing models  . . . . . . . . . . . . . .  4
     3.1.  Virtual servers  . . . . . . . . . . . . . . . . . . . . .  4
     3.2.  Controlling the object location  . . . . . . . . . . . . .  5
     3.3.  Controlling the node location  . . . . . . . . . . . . . .  5
     3.4.  Address space balancing  . . . . . . . . . . . . . . . . .  6
     3.5.  Other mechanisms . . . . . . . . . . . . . . . . . . . . .  6
   4.  Comparison of the models . . . . . . . . . . . . . . . . . . .  6
     4.1.  Virtual servers  . . . . . . . . . . . . . . . . . . . . .  6
     4.2.  Controlling the object location  . . . . . . . . . . . . .  7
     4.3.  Controlling the node location  . . . . . . . . . . . . . .  8
     4.4.  Address space balancing  . . . . . . . . . . . . . . . . .  8
     4.5.  Summary  . . . . . . . . . . . . . . . . . . . . . . . . .  8
   5.  Future work  . . . . . . . . . . . . . . . . . . . . . . . . . 10
   6.  Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 10
   7.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 10
   8.  Security Considerations  . . . . . . . . . . . . . . . . . . . 10
   9.  References . . . . . . . . . . . . . . . . . . . . . . . . . . 10
     9.1.  Normative References . . . . . . . . . . . . . . . . . . . 10
     9.2.  Informative References . . . . . . . . . . . . . . . . . . 10
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 11


















Harjula & Ylianttila    Expires September 9, 2010               [Page 2]


Internet-Draft          DHT Load Balancing Models             March 2010


1.  Introduction

   Load balancing in P2P has special aspects and requirements that
   distinguish it from load balancing in distributed server systems.  In
   most of the dedicated client/server systems it is enough to prevent
   the load within a node to grow in such extent that the node would
   fail in performing its tasks.  However, in P2P systems the
   requirements for the fairness of load distribution are higher since
   P2P nodes are not usually dedicated to certain tasks.  Instead, the
   P2P software usually runs on the background while the user of the
   device is doing other tasks with the node.  This emphasizes the
   importance of fair load distribution between the nodes in a P2P
   system.

   The network management and routing in structured P2P systems are
   based on a collaborative effort of the participating nodes instead of
   centralized control.  Structured P2P networks were developed to
   improve routing efficiency and success rate, and thus to decrease the
   communication overhead [P2PSURVEY].  In structured P2P networks, the
   overlay uses specialized algorithms for generating topologies for the
   nodes participating the system.  The overlay has specific control for
   the routing between the nodes, and the overlay controls the content
   placement.

   P2P systems usually consist of two distinguishable functions: 1)
   Search and discovery of nodes, content, or services (also called as
   signaling part), and 2) Transferring content or information between
   the nodes in either realtime or non-realtime manner (also called as
   data- or media part).  The load generated by the signaling part is
   called signaling load, and the load generated by the data part is
   called data transfer load.  In the basic P2P scenario, the content is
   moved directly between the nodes, and thus the content transfer
   generates load only to the source and target node.  In addition, most
   of the systems allows the content to be stored outside the node that
   is actually sharing it, enabling e.g. content 4 sharing while the
   sharing node is offline.  In the case of realtime content, the media
   cannot be split in similar manner to third party nodes.  However,
   realtime streams may be routed through one or more third party nodes.
   The reason for using third party streaming relays may be e.g. the
   restrictions of the access network of source or target node.

   This draft provides a survey of the existing and emerging load
   balancing technologies in structured P2P networking.  The presented
   overlay load balancing models aim to balance both the signaling and
   data transfer load by affecting the node's responsibilities in the
   overlay, such as the address space or the number of objects an
   overlay node is responsible for.  As the issues concerning realtime
   media transfers are outside the scope of P2PSIP WG, the load



Harjula & Ylianttila    Expires September 9, 2010               [Page 3]


Internet-Draft          DHT Load Balancing Models             March 2010


   balancing models focusing specifically to streaming between the end
   nodes are excluded from this draft.  The main purpose of this draft
   is to provide a scientific background for defining which of the
   available load balancing models are the most suitable for P2PSIP
   environment.


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 [RFC2119].

   Load: The stress caused to a certain node in the network, concerning
   e.g. the node's computational, network, memory, storage, or battery
   capacity.

   Signaling load: The load caused by the overlay maintenance and
   payload signalling.

   Data transfer load: The load caused by the overlay data transfers,
   including storing, retrieving, relocation and replication of data.

   Overload: A computing entity can be interpreted as overloaded if its
   functionality, performance, reliability, or usability substantially
   suffers from the load.

   Load balancing: A technique to distribute workload fairly across two
   or more networked nodes, in order to attain optimal resource
   utilization, maximize throughput, minimize response time, and avoid
   overload of any node.


3.  Fundamental load balancing models

   This section presents the fundamental overlay load balancing models
   that aim to balance the signaling and data transfer load by affecting
   the node's responsibilities in the overlay.  Note that several
   proposed mechanisms may fall under the same fundamental model, as
   well as one proposal may contain 4 elements from more than one
   fundamental models.

3.1.  Virtual servers

   During the past years, a great deal of research has been conducted to
   improve the load balancing in structured P2P networks.  Many of the
   proposed load balancing mechanisms are based on the concept of
   virtual servers [CHORD], where single physical node may host several



Harjula & Ylianttila    Expires September 9, 2010               [Page 4]


Internet-Draft          DHT Load Balancing Models             March 2010


   virtual nodes (virtual servers) that are all participating
   independently the same overlay.  The basic concept of multiple
   virtual servers per physical node balances the load statistically.
   Fundamentally, the model also enables resource-aware load balancing,
   since the number of virtual servers allocated per node can vary.  In
   dynamic virtual server load balancing [VIRTUALSERVER_1],
   [VIRTUALSERVER_2], the load between the physical nodes is balanced by
   dynamically controlling the number of virtual servers per physical
   node (i.e. moving them between physical nodes during runtime).

3.2.  Controlling the object location

   Another fundamental load balancing concept is to directly control the
   object location on the overlay.  Power of Two Choices [POWEROF2], is
   based on the concept of using multiple hash functions per object.
   When inserting an object to an overlay, all respective hash values
   are computed and the load information of the corresponding peer
   candidates is retrieved.  Finally, the object is stored on the peer
   with the lightest load.  Searching the object can be implemented by;
   1) sending separate lookups using each respective hash values, or 2)
   using redirection pointers between the corresponding peer candidates,
   and sending single lookup using some of the hash functions (if the
   peer receiving the lookup does not contain the object, it forwards
   the request to the containing peer, using the redirection pointer).

3.3.  Controlling the node location

   Controlling the node location on the overlay can as well be used for
   load balancing.  Node migration, proposed by Karger&Ruhl
   [SIMPLELOADBAL], is a mechanism allowing underloaded nodes to migrate
   to portions of the address space occupied by too many data items, to
   share the load of the node responsible for the overloaded address
   space.  In this model, an underloaded node queries the load of a
   randomly chosen remote node and makes a pairwise load comparison
   between itself and the remote node.  If the load of the remote node
   is higher, the node relocates to share the address space of the
   remote node.

   Rieche et al [HEATDISP], presented another load balancing model,
   which is fundamentally based on moving objects between the overlay
   nodes.  In this model, the address space is divided to intervals,
   containing f nodes, where f is a fixed minimum number of nodes
   assigned to an interval.  The nodes within the interval are
   collectively responsible for all of the objects stored in the
   interval.  If the interval gets overloaded,; 1) the overloaded
   interval can be split to two intervals if the interval contains more
   than 2f nodes, 2) move nodes from other intervals to the overloaded
   interval to reach 2f nodes in the interval and split it (as in the



Harjula & Ylianttila    Expires September 9, 2010               [Page 5]


Internet-Draft          DHT Load Balancing Models             March 2010


   first case), or 3) move the border between the overloaded interval
   and its successor or predecessor to balance the load between them.

3.4.  Address space balancing

   Yet another fundamental load balancing model is address space
   balancing between the overlay nodes.  The concept was introduced in
   [SIMPLELOADBAL], together with the previously introduced object
   location controlling model.  The main idea in the address space
   balancing is that each node has a fixed set of O(log N) possible
   locations, called virtual nodes, on the overlay, calculated using
   different hash algorithms (notice the difference in the terms between
   virtual node and virtual server).  Each node has only one of these
   virtual nodes active at any time.  The virtual node that spans the
   smallest address space between the real node owning it and the
   succeeding real node, is selected as the active node.  The selection
   is made occasionally.  With high probability, each node will be
   responsible for O(1/N) fraction of the address space.

3.5.  Other mechanisms

   Several improvements have been developed for most of the presented
   fundamental load balancing models, offering e.g. better performance,
   lower overhead or locality awareness.  However, as they do not
   significantly change the fundamental working principles, they do not
   form separate load balancing categories.


4.  Comparison of the models

   Common goal for each of the presented fundamental load balancing
   mechanisms is to achieve fair load distribution between the overlay
   nodes without generating too much overhead to the overlay.  However,
   there are significant differences in both the quality of load
   distribution and the generated overhead.  The following subsections
   briefly discuss the benefits and drawbacks of each of the presented
   fundamental mechanisms.

4.1.  Virtual servers

   In its basic form, the virtual server model affects the load balance
   statistically.  The situation can be compared to throwing a die once
   versus throwing it n times and calculating their average result.  The
   heterogeneity between the nodes can be addressed by allocating more
   virtual servers to higher-capacity devices and less virtual servers
   to lower-capacity devices.  Dynamic load variations can be addressed
   by a mechanism that allows moving virtual servers (and the objects
   they are responsible for) between the nodes during runtime.



Harjula & Ylianttila    Expires September 9, 2010               [Page 6]


Internet-Draft          DHT Load Balancing Models             March 2010


   The general problem with the virtual server model is the signaling
   overhead it generates.  As a physical node appears as multiple
   virtual nodes (virtual servers) in the overlay, the overlay size
   grows with O(N) relation to the number of virtual servers per
   physical device.  The problem is emphasized with structured P2P
   networks, due to their dependence on network management signaling,
   which grows with the overlay size.  With some optimizations, such as
   sending only one request message per physical node and keeping shared
   node-specific routing tables (instead of virtual server-specific),
   the signaling overhead does not grow with the same proportion, but is
   still a major problem.  The overhead gets even worse with dynamic
   load balancing, which requires mechanisms for runtime load monitoring
   and moving virtual servers between the nodes.

4.2.  Controlling the object location

   Controlling the object location, with e.g. the power of two choices
   method, is simple but efficient load balancing method.  The method
   does not generate any additional management overhead, since each
   physical device appears as a single node in the overlay, in contrast
   to the virtual server model.  Instead, the model generates some
   additional overhead to payload messaging due to the redundancy in
   storing and looking up an object, as pointed out in section 2.
   However, as shown by multiple research articles, such as
   [MAINTENANCE_CHORD] and [CONTROLMESSAGE_OVERHEAD], the management
   signaling dominates the signaling load in structured P2P networks.
   Thus, the generated overall overhead is significantly lower than with
   virtual server model in most of the P2P networks.  With redirection
   pointers, the payload signaling overhead can be alleviated with the
   cost of increased maintenance signalling, as the pointers need
   maintenance.  The model also inherently takes into account the node
   heterogeneity, as the load is calculated locally at each node.

   The power of two choices is a passive load balancing model, i.e. it
   does not provide active load transfers between the nodes.  Thus, even
   though with high probability an overloaded node does not receive any
   additional objects during runtime, the objects (causing overload to
   the node) cannot be moved to another node during their lifetime.  If
   the redirection pointers are in use, and thus the responsible node
   candidates for a certain object are aware of each other, they can
   move objects between each other to provide dynamic load balancing.

   When compared to virtual server model, the power of two choices model
   generates less overhead but is also slower in reacting to dynamic
   load changes.  The dynamic load balancing between the candidate nodes
   (mentioned in previous paragraph) brings some help, but the mechanism
   is quite inefficient, since the load can be balanced only between the
   candidate nodes.  Therefore the model works better in dynamic high



Harjula & Ylianttila    Expires September 9, 2010               [Page 7]


Internet-Draft          DHT Load Balancing Models             March 2010


   churn networks with short object lifetimes, since the model does not
   significantly increase the already high maintenance signaling
   overhead, and load balancing is more effective as it can take place
   more often (as it happens only in object insertions).

4.3.  Controlling the node location

   Similarly to previous model, controlling the node location aims to
   balance the load between nodes by controlling the number of objects
   per node.  However, instead of controlling object locations, the
   locations of nodes themselves are controlled by the load balancing
   mechanism.  In a passive form, additional overhead is generated only
   during the joining phase and when the nodes are looked up.  Object
   lookups are not affected by the model.  Active node location
   management generates also load transfer overhead, as the objects are
   moved between the moved node and the node taking over the objects the
   moving node was storing in the original location and, similarly,
   between the moving node and the node that was holding the objects in
   the new location.  In addition, the distribution of load information
   between the devices also generates overhead to the overlay.  This
   model takes also into account the node heterogeneity, as the load is
   calculated locally.

4.4.  Address space balancing

   In practice, this load balancing model is somewhat similar to the
   previously presented node location management mechanism, but the
   general idea of how to achieve the load balance is different.
   Address space balancing aims to place the nodes to the overlay so
   that the address space controlled by each node is as equal as
   possible.  This model generates both management and load transfer
   overhead, as the optimal node location is determined every time the
   address space of a node is changed due to neighbour node departures
   and new node arrivals, and changed when needed.  A major drawback of
   this model is that it only aims to balance the address-space between
   the nodes, and does not take into account the actual load of the
   node.

4.5.  Summary

   The summary of the main characteristics of the fundamental load
   balancing models is presented in the table below.

   +---------------+------------+----------------+---------------------+
   | LB model      | Achievable | Responsiveness | Cost                |
   |               | LB quality | to rapid load  |                     |
   |               |            | changes        |                     |
   +---------------+------------+----------------+---------------------+



Harjula & Ylianttila    Expires September 9, 2010               [Page 8]


Internet-Draft          DHT Load Balancing Models             March 2010


   | Virtual       | High       | High if        | -High maintenance   |
   | Server        |            | dynamic VN     | overhead (also high |
   |               |            | reallocation,  | transfer cost if    |
   |               |            | otherwise no   | dynamic VN          |
   |               |            | responsiveness | reallocation)       |
   |               |            | at all         |                     |
   +---------------+------------+----------------+---------------------+
   | Controlling   | High       | Low (moderate  | -No additional      |
   | Object        |            | if dynamic     | maintenance         |
   | Location      |            | object         | overhead            |
   |               |            | relocation     | -Increased object   |
   |               |            |                | lookup overhead     |
   |               |            |                | (if redirection     |
   |               |            |                | pointers in use,    |
   |               |            |                | no additional       |
   |               |            |                | lookup overhead,    |
   |               |            |                | but increased       |
   |               |            |                | maintenance         |
   |               |            |                | overhead)           |
   |               |            |                | -Multiple hash      |
   |               |            |                | generation in       |
   |               |            |                | object insertion &  |
   |               |            |                | lookup (also        |
   |               |            |                | transfer cost if    |
   |               |            |                | dynamic object      |
   |               |            |                | relocations)        |
   +---------------+------------+----------------+---------------------+
   | Controlling   | High       | High if heavy  | -Increased          |
   | Node Location |            | node probes    | maintenance         |
   |               |            | (otherwise     | overhead            |
   |               |            | low)           | -Incresed node      |
   |               |            |                | lookup overhead     |
   |               |            |                | -Transfer cost in   |
   |               |            |                | node relocations    |
   +---------------+------------+----------------+---------------------+
   | Address-space | Moderate   | Not at all     | -Increased          |
   | Balancing     |            |                | maintenance         |
   |               |            |                | overhead            |
   |               |            |                | -Incresed node      |
   |               |            |                | lookup overhead     |
   |               |            |                | -Transfer cost in   |
   |               |            |                | virtual node        |
   |               |            |                | relocations         |
   +---------------+------------+----------------+---------------------+

              Figure 1: Load balancing model characteristics





Harjula & Ylianttila    Expires September 9, 2010               [Page 9]


Internet-Draft          DHT Load Balancing Models             March 2010


5.  Future work

   The future work includes more detailed analysis of the fundamental
   load balancing models, as well as adding more references to existing
   load balancing mechanisms, and mapping them with the fundamental
   models.


6.  Acknowledgements

   No acknowledgements at this time.


7.  IANA Considerations

   This draft includes no request to IANA at this time.


8.  Security Considerations

   No security considerations at this time.


9.  References

9.1.  Normative References

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119, March 1997.

9.2.  Informative References

   [CHORD]    Stoica, I., Morris, R., Liben-Nowell, D., Karger, D.,
              Kaashoek, M., Dabek, F., and H. Balakrishnan, "Chord: a
              scalable peer-to-peer lookup protocol for Internet
              applications,  IEEE/ACM Transactions on Networking, Volume
              11, Issue 1, Feb. 2003, Page(s) 17-32.".

   [CONTROLMESSAGE_OVERHEAD]
              Hong, S., Hilt, V., and H. Schulzrinne, "Evaluation of
              Control Message Overhead of a DHT-Based P2P System,  Bell
              Labs Technical Journal, Volume 13, Issue 3, 2008.".

   [HEATDISP]
              Rieche, S., Petra, L., and K. Wehrle, "A Thermal-
              Dissipation-based Approach for Balancing Data Load in
              Distributed Hash Tables, IEEE Conference on Local Computer
              Networks (LCN 2004), Tampa, USA, 2004.".



Harjula & Ylianttila    Expires September 9, 2010              [Page 10]


Internet-Draft          DHT Load Balancing Models             March 2010


   [MAINTENANCE_CHORD]
              Maenpaa, J. and G. Camarillo, "Study on Maintenance
              Operations in a Chord-based Peer-to-Peer Session
              Initiation  Protocol Overlay Network, IEEE International
              Symposium on Parallel&Distributed Processing (IPDPS 2009),
              Rome, Italy, 2009.".

   [P2PSURVEY]
              Androutsellis-Theotokis, S. and D. Spinellis, "A survey of
              peer-to-peer content distribution technologies,  ACM
              Computing Surveys, 36(4):335-371, December 2004.".

   [POWEROF2]
              Byers, J., Considine, J., and M. Mitzenmacher, "Simple
              Load Balancing for DHTs, 2nd International Workshop on
              Peer-to-Peer Systems (IPTPS 03), Berkeley, USA, 2003,
              IEEE.".

   [SIMPLELOADBAL]
              Karger, D. and M. Ruhl, "Simple Efficient Load Balancing
              Algorithms for Peer-to-Peer Systems,  4th International
              Workshop on Peer-to-Peer Systems (IPTPS 04), San Diego,
              USA, 2004.".

   [VIRTUALSERVER_1]
              Rao, A., Laksminarayanan, K., Surana, S., Karp, R., and I.
              Stoica, "Load Balancing in Structured P2P Systems,
              International  Workshop on Peer-to-Peer Systems (IPTPS),
              pages 68-79.".

   [VIRTUALSERVER_2]
              Dabek, F., Kaashoek, M., Karger, D., Morris, R., and I.
              Stoica, "Wide-area Cooperative Storage with CFS,  18th ACM
              Symposium on Operating System Principles (SOSP),  Chateau
              Lake Louise, Banff, Alberta, Canada. pp. 202-215.".


Authors' Addresses

   Erkki Harjula
   University of Oulu
   Erkki Koiso-Kanttilan katu 3
   University of Oulu,   90014
   Finland

   Phone: +358 8 553 2522
   Email: erkki.harjula@ee.oulu.fi




Harjula & Ylianttila    Expires September 9, 2010              [Page 11]


Internet-Draft          DHT Load Balancing Models             March 2010


   Mika Ylianttila
   University of Oulu
   Erkki Koiso-Kanttilan katu 3
   University of Oulu,   90014
   Finland

   Phone: +358 8 553 25311
   Email: mika.ylianttila@ee.oulu.fi











































Harjula & Ylianttila    Expires September 9, 2010              [Page 12]


Html markup produced by rfcmarkup 1.129c, available from https://tools.ietf.org/tools/rfcmarkup/