1 |
A dynamic hashing approach to supporting load balance in P2P systemsLi, Sih-ning 19 June 2006 (has links)
In a P2P (Peer-to-Peer) system, every user node, i.e., the peer, may dynamically join and leave the system. In general, peers can exchange information and contribute portions of their resources to the community in a P2P system. They are treated functionally identical. Therefore, it is very important to efficiently locate the peer that stores a particular data item and make the system load balance in P2P systems. Chord is a structured P2P system which has a ring architecture, where a structured P2P system means that peers maintain information about what resources neighbor peers offer.
It provides support for just one operation: to assign the data key to the peer by hashing. Therefore, we can efficiently locate the peer that stores a particular data key. However, in the Chord system, most of data keys may be assigned to the same peer by using the static hashing scheme, which results in the case that the load of the system not be balanced. Therefore, in this thesis, we propose a strategy which uses the dynamic hashing scheme to locate the data key based on the Chord architecture, and to maintain the load balance. A dynamic hashing allows the address space allocated to the file to be increased and reduced without reorganizing the whole file. The basic idea of a dynamic hashing approach is to split the current overflow bucket into two new buckets by using the next level hashing function without reorganizing the other buckets, and our proposed strategy uses such an approach.
In our strategy, we use two data structures for a peer, one stores the data hashed to the current peer and the other one stores the data from its predecessor. When an overflow occurs in the bucket after insertion of a data key, we use the one hashing function to split data keys stored in the data bucket. If the capacity of the current peer is larger than that of its successor, we forward some data keys to the successor. Similarly, we also consider the case of an underflow occurs in the bucket after deletion of a data key. Therefore, the unbalanced condition of the load (even distribution of items to nodes) of the system can be improved based on our strategy.
From our simulation results, we show that the load of the P2P system based on our strategy is much more balanced than that used in the Chord system, when there are few peers and a lot of data keys in the P2P system. We also show that the load based on our strategy is still more balanced than that used in the Chord system, when the data distribution becomes skew.
|
Page generated in 0.0717 seconds