在本篇論文中，我們用M2M的方法，來解決點對點的負載平衡的問題，並且使用stabilize的方法,使得路由封包可以送給正確的實體節點(Physical node),stabilize找前任(predecessor)和繼任者(successor),並取得前任(predecessor)的後繼者(successor),以及後繼者(successor)的前任(predecessor),以維持整個chord ring的完整,並且加入Reverse Finger的資料結構,讓修改速度更快,修改的比例更高

P2P的負載平衡已經變成熱門問題,Napster和Gnutella都有這樣的問題。

在structured overlay網路中，每一個虛擬伺服器，經由雜湊函數SHA-1去對應到一個id.

而一個chord虛擬伺服器負責去管理一段虛擬網路空間(ｉｄｅｎｔｉｆｉｅｒ　ｓｐａｃｅ)，這段虛擬網路空間(ｉｄｅｎｔｉｆｉｅｒ　ｓｐａｃｅ)是本身這個節點和上一個在ｃｈｏｒｄ　ｒｉｎｇ 節點所產生的範圍，物件經由SHA-1做hash產生一個唯一的id,chord的虛擬伺服器也經過SHA-1做hash產生唯一的id,物件交由某個虛擬伺服器,其id大於或等於物件經由hash產生的id。chord提供一個由兩個函數所組成的interface，一個是ｐｕｔ(ID,ｉｔｅｍ)，它用來將物件放到ｃｈｏｒｄ　ｒｉｎｇ的ＩＤ 上;ｇｅｔ(ID)則是去取得ID 上的物件。

In structure P2P system, the identifier space is partitioned among the nodes and
each node is in charge of the items that map into the same portion. Most P2P systems are using DHT (distributed hash table) abstraction as the main part to build P2P overlay network.

Chord adapts efficiently as nodes join and leave the system, and can answer queries even if the system is continuously changing.

The Chord protocol can be implemented in iterative or recursive.In recursive mode,every node forward its query to next node until its successor owns the key.

Current distributed hash tables do not evenly partition the hash-function range; some machines get a larger portion of it. Thus, even if keys are numerous and random, some machine receive more than their fair share, by as much as a factor of O(log N) times the average.

Our M2M algorithm achieves load balancing for system utilizations as high as 90% while moving only about 8% of the load that arrives into the system.

[1] K. P. Gummadi, R. Gummadi, S. Gribble, S. Ratnasamy, S. Shenker, and I. Stoica, “The impact of DHT routing geometry on resilience and proximity,” in Proceedings of the 2003 ACM SIGCOMM, Aug. 2003.

[2] D. Liben-Nowell, H. Balakrishnan, and D. R. Karger, “Analysis of the evolution of peer-to-peer systems,” in Proceedings of the 21st PODC,Aug. 2002.

[3] S. Rhea, D. Geels, T. Roscoe, and J. Kubiatowicz, “Handling churn in a DHT,” in Proceedings of the 2004 USENIX Technical Conference, June 2004.

[4] M. Castro, M. Costa, and A. Rowstron, “Performance and dependability of structured peer-to-peer overlays,” in Proceedings of the 2004 DSN,
June 2004.

[5] S. S. Lam and H. Liu, “Failure recovery for structured P2P networks:Protocol design and performance evaluation,” in Proceedings of the 2004 SIGMETRICS, June 2004.

[6] J. Li, J. Stribling, T. Gil, R. Morris, and M. F. Kaashoek, “Comparing the performance of distributed hash tables under churn,” in Proceedings of the 3rd International Workshop on Peer-to-Peer Systems, Feb. 2004.

[7] I. Stoica, R. Morris, D. Liben-Nowell, D. R. Karger, M. F. Kaashoek, F. Dabek, and H. Balakrishnan, “Chord: A scalable peer-to-peer lookup protocol for Internet applications,” IEEE/ACM Transactions on Networking,pp. 149–160, 2002.

[8]Using bidirectional links to improve peer-to-peer lookup performance, JIANG Jun-jie, TANG Fei-long, PAN Feng, WANG Wei-nong, Journal of Zhejiang University SCIENCE A, 2006

[9]Distributed, Secure Load Balancing with Skew, heterogeneity, and Churn, Jonathan Ledlie and Margo Seltzer, IEEE INFOCOM 2005

[10]Load Balancing in Dynamic Structured P2P Systems Brighten Godfrey, Karthik Lakshminarayanan, Sonesh Surana, Richard Karp, Ion Stoica, INFOCOM 04

[11] M. Adler, Eran Halperin, R. M. Karp, and V. Vazirani, “A
stochastic process on the hypercube with applications to peerto-
peer networks,” in Proc. STOC, 2003.

[12] David Karger and Matthias Ruhl, “New Algorithms for Load Balancing in Peer-to-Peer Systems,” Tech. Rep. MIT-LCS-TR-911, MIT LCS, July 2003.

[13] J. R. Douceur and R. P. Wattenhofer, “Competitive Hill-Climbing Strategies for Replica Placement in a Distributed File System,”in Proc. DISC, 2001.

[14] P. Triantafillou, C. Xiruhaki, M. Koubarakis, and N. Ntarmos,“Towards High Performance Peer-to-Peer Content and Resource Sharing Systems,” in Proc. CIDR, 2003.

[15] G. Aggarwal, R. Motwani, and A. Zhu, “The Load Rebalancing Problem,” in Proc. ACM SPAA, 2003.