Load balancing is a critical issue in peer-to-peer networks. DHT （distributed hash tables） do not evenly partition the hash-function range, and some nodes get a larger portion of it. The loads of some nodes are as m...Load balancing is a critical issue in peer-to-peer networks. DHT （distributed hash tables） do not evenly partition the hash-function range, and some nodes get a larger portion of it. The loads of some nodes are as much as O（log n） times the average. In this paper, a low-cost, decentralized algorithm for ID allocation with complete knowledge in DHT-based system is proposed. It can adjust system load on nodes’ departure. It is proved that the ratio of longest arc to shortest arc is no more than 4 with high probability when network scale increases non-strictly. When network scale decreases from one stable state to another, algorithm can repair the unevenness of nodes distribution. The performance is analyzed in simulation. Simulating results show that updating messages only occupy a little of network bandwidth.展开更多
文摘Load balancing is a critical issue in peer-to-peer networks. DHT （distributed hash tables） do not evenly partition the hash-function range, and some nodes get a larger portion of it. The loads of some nodes are as much as O（log n） times the average. In this paper, a low-cost, decentralized algorithm for ID allocation with complete knowledge in DHT-based system is proposed. It can adjust system load on nodes’ departure. It is proved that the ratio of longest arc to shortest arc is no more than 4 with high probability when network scale increases non-strictly. When network scale decreases from one stable state to another, algorithm can repair the unevenness of nodes distribution. The performance is analyzed in simulation. Simulating results show that updating messages only occupy a little of network bandwidth.
