对等网中Chord协议及算法的研究及改进
|
摘要
对等网应用所面临的一个关键问题是如何有效定位存储特定资源的结点。不同的对等网查找算法采用不同的策略，其查询效率也有所不同。
本文分析了一种分布式查找算法Chord。Chord作为第二代对等网算法，以分布式散列表为查找策略。Chord算法是可改进的，并且每个结点只需维持对数级的Chord环上结点数的结点，便可完成通信任务，而且需要传递的信息量也是对数级的。Chord算法具有负载平衡、可靠性、可扩展性等优点，但是它的查询效率比较低。
针对Chord算法的不足，本文提出了Full-Chord算法。Full-Chord算法主要改进了Chord算法的指针表，将原来计算指针表的公式扩展为两个，这样可以在顺时针和逆时针两个方向上同时进行。Full-Chord算法在查询开始时，就能将查询限制在半个Chord环上，这样便能更接近目标结点，提高查询效率。通过理论分析，Full-Chord算法的查询效率明显优于Chord算法。
对等网中结点加入和离开是很平常的，因此必需考虑对等网的自适应性。关于这个方面，本文做了大量研究，提出了为每个结点再建立一张拥有r个后继结点的后继列表的设想，很好地解决了这个问题。
本文还借鉴了small-world领域的研究成果，扩展了Chord算法。通过对结点度数的分析，提出“超级结点”的概念。并且参考Google的网页搜索技术PageRank，给出了计算结点级别的公式noderange，从而能很好地确定超级结点。通过超级结点，可以更加有效地定位资源，提高查询效率。
最后，通过仿真测试表明，Full-Chord算法在平均查找路径长度和平均查询时间这两个方面的性能明显优于原始Chord算法。
One of fundamental problems confronted by peer-to-peer(P2P) applications is how to efficiently locate the node that stores a particular data item, different strategies are adopted by different P2P search algorithms, in which the efficiency is different.
One of distributed search algorithms, named Chord was analysed. As the second generation of P2P algorithm, distributed hash table is adopted by Chord as the search strategy. Chord is scalable, with communication cost and the state maintained by each node scaling logarithmically with the number of Chord nodes, many advantages are hold by Chord algorithm, such as balance load, reliability, expansibility and so on, but the search efficiency of Chord is low.
The Full-Chord algorithm which addressed the disadvantage of Chord was presented. The finger table of Chord was improved by Full-Chord algorithm, the formula which calculated the finger table was extended into two, so that the calculating procedure could be conducted in both of clockwise and anti-clockwise directions. At the beginning of the search procedure, the range of the search could be restricted in a half Chord-Circle by Full-Chord. In such a way, the target node could be approached more easily and the search efficiency also could be improved. Theoretical analyses had showed that the efficiency of Full-Chord algorithm is clearly superior to original Chord algorithm.
It is very common to insert or delete a node in a P2P network, and therefore the adaptability of P2P network must be considered. Through lots of work in this aspect, an assumption of creating a table having r successors for each node was presented and this will solve the problem better.
The research results in small-world field were also used for reference to extend Chord algorithm. Through the analysis of the node degree, a concept which is called "super node" was presented. Referencing to the search technology of Google called PageRank, a formula which can calculate the node range called noderange was found and the super node can be determined easily through this formula. The resource could be efficiently located by super node, and the search efficiency also could be improved.
Finally, the simulated testings had showed that the efficiency of Full-Chord is clearly superior to the original Chord in two aspects of average search path length and average search time.
本文分析了一种分布式查找算法Chord。Chord作为第二代对等网算法，以分布式散列表为查找策略。Chord算法是可改进的，并且每个结点只需维持对数级的Chord环上结点数的结点，便可完成通信任务，而且需要传递的信息量也是对数级的。Chord算法具有负载平衡、可靠性、可扩展性等优点，但是它的查询效率比较低。
针对Chord算法的不足，本文提出了Full-Chord算法。Full-Chord算法主要改进了Chord算法的指针表，将原来计算指针表的公式扩展为两个，这样可以在顺时针和逆时针两个方向上同时进行。Full-Chord算法在查询开始时，就能将查询限制在半个Chord环上，这样便能更接近目标结点，提高查询效率。通过理论分析，Full-Chord算法的查询效率明显优于Chord算法。
对等网中结点加入和离开是很平常的，因此必需考虑对等网的自适应性。关于这个方面，本文做了大量研究，提出了为每个结点再建立一张拥有r个后继结点的后继列表的设想，很好地解决了这个问题。
本文还借鉴了small-world领域的研究成果，扩展了Chord算法。通过对结点度数的分析，提出“超级结点”的概念。并且参考Google的网页搜索技术PageRank，给出了计算结点级别的公式noderange，从而能很好地确定超级结点。通过超级结点，可以更加有效地定位资源，提高查询效率。
最后，通过仿真测试表明，Full-Chord算法在平均查找路径长度和平均查询时间这两个方面的性能明显优于原始Chord算法。
One of fundamental problems confronted by peer-to-peer(P2P) applications is how to efficiently locate the node that stores a particular data item, different strategies are adopted by different P2P search algorithms, in which the efficiency is different.
One of distributed search algorithms, named Chord was analysed. As the second generation of P2P algorithm, distributed hash table is adopted by Chord as the search strategy. Chord is scalable, with communication cost and the state maintained by each node scaling logarithmically with the number of Chord nodes, many advantages are hold by Chord algorithm, such as balance load, reliability, expansibility and so on, but the search efficiency of Chord is low.
The Full-Chord algorithm which addressed the disadvantage of Chord was presented. The finger table of Chord was improved by Full-Chord algorithm, the formula which calculated the finger table was extended into two, so that the calculating procedure could be conducted in both of clockwise and anti-clockwise directions. At the beginning of the search procedure, the range of the search could be restricted in a half Chord-Circle by Full-Chord. In such a way, the target node could be approached more easily and the search efficiency also could be improved. Theoretical analyses had showed that the efficiency of Full-Chord algorithm is clearly superior to original Chord algorithm.
It is very common to insert or delete a node in a P2P network, and therefore the adaptability of P2P network must be considered. Through lots of work in this aspect, an assumption of creating a table having r successors for each node was presented and this will solve the problem better.
The research results in small-world field were also used for reference to extend Chord algorithm. Through the analysis of the node degree, a concept which is called "super node" was presented. Referencing to the search technology of Google called PageRank, a formula which can calculate the node range called noderange was found and the super node can be determined easily through this formula. The resource could be efficiently located by super node, and the search efficiency also could be improved.
Finally, the simulated testings had showed that the efficiency of Full-Chord is clearly superior to the original Chord in two aspects of average search path length and average search time.
引文
[1] Napster Website[EB/OL]. http://www. napster. com, 2005
[2] Gnutella Website[EB/OL]. http://www. gnutella. com, 2005
[3] Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan. Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications. SIGCOMM' 01, San Diego, California, USA, 2001
[4] BUYYA R. Economic models for Management of the Resources in Peer-to-Peer and Grid Computing[A]. Proceedings of the Commercial Applications for High-Performance Computing Conference[C],2001:220-231P
[5] S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker. A scalable content-addressable network, in Proc. ACM SIGCOMM, San Diego, 2001:161-172P
[6] B. Zhao, J. Kubiatowicz, A. Joseph. Tapestry:An infrastructure for fault-tolerant wide-area location and routing. Berkeley: Univ. California, 2001:338-354P
[7] P. Druschel, A. Rowstron. Pastry:Scalable, distributed object location and routing for large-scale peer-to-peer systems. In Proc. 18th IFIP/ACM Int. Conf. Distributed Systems Platforms(Middleware 2001), 2001:329-350P
[8] Kazaa Website[EB/OL]. http://www, kazaa, com
[9] Prasanna Ganesan, Gurmeet Singh Manku. Optimal Routing in Chord. Stanford University. SODA 2004
[10] 刘业，杜庆伟，杨鹏．基于P2P的分布对象定位机制的研究．东南大学学报．2004，34(3)：327-328页
[11] 罗杰文．Peer to Peer(P2P)综述．第二版．北京：中科院计算技术研究所．2005：1-3页
[12] Sylvia R, Scott S, Ion S. Routing Algorithms for DHTs: Some Open Questions[A]. Ist International Workshop on Peer-to-Peer Systems[C],2002
[13] Emil S, Robert M. Security Considerations for Peer-to-Peer Distributed Hash Tables[A]. Ist International Workshop on P0eer-to-Peer Systems[C],2002
[14] Milojicic DS, Kalogeraki V, Lukose R, et al. Peer-to-Peer Computing[Z]. HP Laboratories palo alto, HPL-2002-57,2002
[15] F. Dabek, M.F. Kaashoek, D. Karger, R. Morris, I. Stoica. Wide-area cooperative storage with CFS. In Proc.ACM SOSP'O1, Banff, Canada, 2001
[16] P. Druschel, A. Rowstron. PAST: A large-scale, persistent peer-to-peer storage utility. In Proc. HotOS Ⅷ, Schloss Elmau, Germany, 2001
[17] P. Druschel, A. Rowstron. Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility. In Proc. ACM SOSP'01, Banff, Canada, 2001
[18] A. Rowstron, A.M. Kermarrec, P. Druschel, M. Castro. Scribe:The design of a large-scale event notification infrastructure.http://www. research. microsoft. com/antr/SCRIBE/
[19] 王张宜，李波，张焕国．Hash函数的安全性研究．计算机工程与应用．2005，41(34)：18-19页
[20] 陈伟东．P2P对等网络中资源定位的研究与改进．中山大学硕士学位论文．2005：26-28页
[21] 张世永等编著．网络安全原理与应用．第一版．北京：科学出版社，2004：121-125页
[22] 李霞．MD5加密算法浅析及应用．运城学院学报．2005，23(5)：56-58页
[23] 林雅榕，侯整风．对哈希算法SHA-1的分析和改进．计算机技术与发展．2006，16(3)：124-126页
[24] 张振权，罗新民，齐春．数字签名算法MD5和SHA-1的比较及其AVR优化实现．网络安全技术与应用．2005，21(7)：64-67页
[25] 李运娣，冯勇．基于DHT的P2P搜索定位技术研究．计算机应用研究．2005，22(10)：226-228页
[26] David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin, Rina Panigrahy. Consistent Hashing and Random Trees:Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (El Paso, TX),1997:654-663P
[27] Daniel Lewin. Consistent Hashing and Random Trees:Algorithms for caching in distributed networks[MS, thesis]. Department of Electric. Eng. Comput. Sci. Cambridge:Massachusetts Inst. Technol,1998
[28] 李祖鹏，黄建华，唐辉．基于P2P计算模式的自组织网络路由模型．软件学报．2005，16(5)：916-930页
[29] 张浩，金海，聂江武，徐婕，章勤．Dual-Chord：一种更加有效的分布式哈希表．小型微型计算机系统．2006，27(8)：1450-1454页
[30] 张震，王晓明．对等网中Chord资源查找算法研究．计算机工程与应用．2006，42(33)：147-152页
[31] Eng Keong Lua, Jon Crowcroft, Marcelo Pias, Ravi Sharma, Steven Lim. A Survey and Comparison of Peer-to-Peer Overlay Network Schemes. IEEE communications survey and tutorial, 2004
[32] Stephanos, Stheotokis R, Spinellis D. A Survey of Peer-to-Peer Content Distribution Technologies[J]. Proceedings of ACM Computing Surveys, 2004,36(4):335-371P
[33] 董芳．对等网络Chord分布式查找服务的研究[J]．计算机应用．2003，23(11)：25-28页
[34] Miguel Castro, Peter Druschel, Ayalvadi Ganesh, Antony Rowstron and Dan S. Wallach. Secure routing for structured peer-to-peer overlay networks. In Proc. of the 5th Usenix Symposium on Operating Systems Design and Implementation, Boston, MA, 2002
[35] 梁达明．P2P网络资源定位模型研究．浙江大学硕士学位论文．2006：41-58页
[36] 费新元．分布式P2P网络模型研究．贵州工业大学硕士学位论文．2003：35-36页
[37] Zhang H, Goel A, Govindan R. Using the Small-world Model to Improve Freenet Performance[C]. Proceedings of the 21th IEEE Information Conference, New York, 2002:40-49P
[38] Newman M E J, Jensen I, Ziff R M. Percolation and Epidemics in A Two-dimensional Small World[J]. Physical Review E, 2002,65(2)
[39] 乐光学．基于 Region 多层结构 P2P 计算网络模型[J]．软件学报．2005，16(6)：1140-1150页
[40] Watts D J, Strogatz S H. Collective dynamics of small-world networks. Nature, 1998,393:440-442P
[41] 朱晓姝，周娅，黄桂敏．基于小世界层次分布式路由模型研究．计算机 工程．2006，32(15)：120-122页
[42] 张海涛，董洲．搜索引擎Google的检索功能及PageRank技术分析[J]．情报科学．2002，20(8)：813-815页
[43] P2Psim Website. http://pdos. csail. mit. edu/p2psim/index. html
[44] 温忠智．高阶Chord：一种新型P2P查找策略．四川大学硕士学位论文．2005：37-40页
[2] Gnutella Website[EB/OL]. http://www. gnutella. com, 2005
[3] Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan. Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications. SIGCOMM' 01, San Diego, California, USA, 2001
[4] BUYYA R. Economic models for Management of the Resources in Peer-to-Peer and Grid Computing[A]. Proceedings of the Commercial Applications for High-Performance Computing Conference[C],2001:220-231P
[5] S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker. A scalable content-addressable network, in Proc. ACM SIGCOMM, San Diego, 2001:161-172P
[6] B. Zhao, J. Kubiatowicz, A. Joseph. Tapestry:An infrastructure for fault-tolerant wide-area location and routing. Berkeley: Univ. California, 2001:338-354P
[7] P. Druschel, A. Rowstron. Pastry:Scalable, distributed object location and routing for large-scale peer-to-peer systems. In Proc. 18th IFIP/ACM Int. Conf. Distributed Systems Platforms(Middleware 2001), 2001:329-350P
[8] Kazaa Website[EB/OL]. http://www, kazaa, com
[9] Prasanna Ganesan, Gurmeet Singh Manku. Optimal Routing in Chord. Stanford University. SODA 2004
[10] 刘业，杜庆伟，杨鹏．基于P2P的分布对象定位机制的研究．东南大学学报．2004，34(3)：327-328页
[11] 罗杰文．Peer to Peer(P2P)综述．第二版．北京：中科院计算技术研究所．2005：1-3页
[12] Sylvia R, Scott S, Ion S. Routing Algorithms for DHTs: Some Open Questions[A]. Ist International Workshop on Peer-to-Peer Systems[C],2002
[13] Emil S, Robert M. Security Considerations for Peer-to-Peer Distributed Hash Tables[A]. Ist International Workshop on P0eer-to-Peer Systems[C],2002
[14] Milojicic DS, Kalogeraki V, Lukose R, et al. Peer-to-Peer Computing[Z]. HP Laboratories palo alto, HPL-2002-57,2002
[15] F. Dabek, M.F. Kaashoek, D. Karger, R. Morris, I. Stoica. Wide-area cooperative storage with CFS. In Proc.ACM SOSP'O1, Banff, Canada, 2001
[16] P. Druschel, A. Rowstron. PAST: A large-scale, persistent peer-to-peer storage utility. In Proc. HotOS Ⅷ, Schloss Elmau, Germany, 2001
[17] P. Druschel, A. Rowstron. Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility. In Proc. ACM SOSP'01, Banff, Canada, 2001
[18] A. Rowstron, A.M. Kermarrec, P. Druschel, M. Castro. Scribe:The design of a large-scale event notification infrastructure.http://www. research. microsoft. com/antr/SCRIBE/
[19] 王张宜，李波，张焕国．Hash函数的安全性研究．计算机工程与应用．2005，41(34)：18-19页
[20] 陈伟东．P2P对等网络中资源定位的研究与改进．中山大学硕士学位论文．2005：26-28页
[21] 张世永等编著．网络安全原理与应用．第一版．北京：科学出版社，2004：121-125页
[22] 李霞．MD5加密算法浅析及应用．运城学院学报．2005，23(5)：56-58页
[23] 林雅榕，侯整风．对哈希算法SHA-1的分析和改进．计算机技术与发展．2006，16(3)：124-126页
[24] 张振权，罗新民，齐春．数字签名算法MD5和SHA-1的比较及其AVR优化实现．网络安全技术与应用．2005，21(7)：64-67页
[25] 李运娣，冯勇．基于DHT的P2P搜索定位技术研究．计算机应用研究．2005，22(10)：226-228页
[26] David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin, Rina Panigrahy. Consistent Hashing and Random Trees:Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (El Paso, TX),1997:654-663P
[27] Daniel Lewin. Consistent Hashing and Random Trees:Algorithms for caching in distributed networks[MS, thesis]. Department of Electric. Eng. Comput. Sci. Cambridge:Massachusetts Inst. Technol,1998
[28] 李祖鹏，黄建华，唐辉．基于P2P计算模式的自组织网络路由模型．软件学报．2005，16(5)：916-930页
[29] 张浩，金海，聂江武，徐婕，章勤．Dual-Chord：一种更加有效的分布式哈希表．小型微型计算机系统．2006，27(8)：1450-1454页
[30] 张震，王晓明．对等网中Chord资源查找算法研究．计算机工程与应用．2006，42(33)：147-152页
[31] Eng Keong Lua, Jon Crowcroft, Marcelo Pias, Ravi Sharma, Steven Lim. A Survey and Comparison of Peer-to-Peer Overlay Network Schemes. IEEE communications survey and tutorial, 2004
[32] Stephanos, Stheotokis R, Spinellis D. A Survey of Peer-to-Peer Content Distribution Technologies[J]. Proceedings of ACM Computing Surveys, 2004,36(4):335-371P
[33] 董芳．对等网络Chord分布式查找服务的研究[J]．计算机应用．2003，23(11)：25-28页
[34] Miguel Castro, Peter Druschel, Ayalvadi Ganesh, Antony Rowstron and Dan S. Wallach. Secure routing for structured peer-to-peer overlay networks. In Proc. of the 5th Usenix Symposium on Operating Systems Design and Implementation, Boston, MA, 2002
[35] 梁达明．P2P网络资源定位模型研究．浙江大学硕士学位论文．2006：41-58页
[36] 费新元．分布式P2P网络模型研究．贵州工业大学硕士学位论文．2003：35-36页
[37] Zhang H, Goel A, Govindan R. Using the Small-world Model to Improve Freenet Performance[C]. Proceedings of the 21th IEEE Information Conference, New York, 2002:40-49P
[38] Newman M E J, Jensen I, Ziff R M. Percolation and Epidemics in A Two-dimensional Small World[J]. Physical Review E, 2002,65(2)
[39] 乐光学．基于 Region 多层结构 P2P 计算网络模型[J]．软件学报．2005，16(6)：1140-1150页
[40] Watts D J, Strogatz S H. Collective dynamics of small-world networks. Nature, 1998,393:440-442P
[41] 朱晓姝，周娅，黄桂敏．基于小世界层次分布式路由模型研究．计算机 工程．2006，32(15)：120-122页
[42] 张海涛，董洲．搜索引擎Google的检索功能及PageRank技术分析[J]．情报科学．2002，20(8)：813-815页
[43] P2Psim Website. http://pdos. csail. mit. edu/p2psim/index. html
[44] 温忠智．高阶Chord：一种新型P2P查找策略．四川大学硕士学位论文．2005：37-40页