基于P2P覆盖网的路由算法研究
|
摘要
对等网应用在近几年内已得到突飞猛进的发展。资源共享系统是对等网最重要的应用之一。资源系统的性能极大地取决于P2P系统中的一个核心问题：如何高效地定位到所需要的资源，即路由算法问题。
P2P覆盖网为一系列可扩展和非集中式分布应用提供了一个新颖的平台。在结构化P2P网络中，物理网络和覆盖网之间的唯一联系是分布式哈希表，节点里没有包含任何关于其物理位置的信息。这样构建而成的P2P未能充分利用底层物理网络的拓扑结构，从而造成实际的路由效率低下。因为路由算法是P2P的核心。本文围绕P2P路由效率的改善，对如何提取节点在物理网络上的位置信息和如何利用位置信息构造拓扑敏感的P2P系统进行了深入的研究，提出了利用网络拓扑结构来改进P2P路由性能的方案，并通过实验和分析阐明了此方案能有效地改善现有P2P路由效率。
JXTA是Sun公司提出的一个构建P2P环境的平台，提供在任何平台、任何地方以及任何时间实现P2P计算的一整套简单、小巧和灵活的机制。但是随着网络节点的不断增多，网络规模的不断扩大，其所采用的“洪泛”路由机制造成网络流量急剧增加，从而导致网络中部分低宽带节点因网络资源过载而失效，致使路由效率低下。本文找出使用了汇集节点视图是导致效率低下的原因，提出了将DHT引入JXTA的方案，最后给出了方案的设计与实现。
Application of P2P(Peer-to-Peer)network has developed rapidly in recent years. Resource sharing system is an important application of P2P. The performance of such system depends on the kernel problems of P2P: how to locate the needed resource effectively, that is, routing algorithm.
P2P overlay network offers a novel platform for a variety of scalable and decentralized, distributed applications. In a structured P2P network, the only relation between physical layer and overlay network is DHT and nodes do not contain any information about their physical location. Such P2P overlay network does not take into account physical network topology and results in high routing latency and low efficiency. Focusing on improving routing enhancement, the thesis conducts an in-depth research on how to extract topology information and how to utilize the information to construct topology-aware P2P systems. The thesis proposes the solution exploiting the network topology and proves the solution can greatly improve routing efficiency in Chord.
JXTA is a platform proposed by Sun to construct P2P environment, and provides a simple, small and flexible mechanics to realize P2P computing at any platform, any place and any time. However, with the increase of network nodes and enlargement of network scale, its "flooding" routing algorithm leads to rapid augmentation of network flow, and results in the low latency. The thesis finds out that employing rendezvous peer view is the reason of that, and proposes the solution to introduce the DHT into JXTA. The design and implementation of the solution are given at last.
P2P覆盖网为一系列可扩展和非集中式分布应用提供了一个新颖的平台。在结构化P2P网络中，物理网络和覆盖网之间的唯一联系是分布式哈希表，节点里没有包含任何关于其物理位置的信息。这样构建而成的P2P未能充分利用底层物理网络的拓扑结构，从而造成实际的路由效率低下。因为路由算法是P2P的核心。本文围绕P2P路由效率的改善，对如何提取节点在物理网络上的位置信息和如何利用位置信息构造拓扑敏感的P2P系统进行了深入的研究，提出了利用网络拓扑结构来改进P2P路由性能的方案，并通过实验和分析阐明了此方案能有效地改善现有P2P路由效率。
JXTA是Sun公司提出的一个构建P2P环境的平台，提供在任何平台、任何地方以及任何时间实现P2P计算的一整套简单、小巧和灵活的机制。但是随着网络节点的不断增多，网络规模的不断扩大，其所采用的“洪泛”路由机制造成网络流量急剧增加，从而导致网络中部分低宽带节点因网络资源过载而失效，致使路由效率低下。本文找出使用了汇集节点视图是导致效率低下的原因，提出了将DHT引入JXTA的方案，最后给出了方案的设计与实现。
Application of P2P(Peer-to-Peer)network has developed rapidly in recent years. Resource sharing system is an important application of P2P. The performance of such system depends on the kernel problems of P2P: how to locate the needed resource effectively, that is, routing algorithm.
P2P overlay network offers a novel platform for a variety of scalable and decentralized, distributed applications. In a structured P2P network, the only relation between physical layer and overlay network is DHT and nodes do not contain any information about their physical location. Such P2P overlay network does not take into account physical network topology and results in high routing latency and low efficiency. Focusing on improving routing enhancement, the thesis conducts an in-depth research on how to extract topology information and how to utilize the information to construct topology-aware P2P systems. The thesis proposes the solution exploiting the network topology and proves the solution can greatly improve routing efficiency in Chord.
JXTA is a platform proposed by Sun to construct P2P environment, and provides a simple, small and flexible mechanics to realize P2P computing at any platform, any place and any time. However, with the increase of network nodes and enlargement of network scale, its "flooding" routing algorithm leads to rapid augmentation of network flow, and results in the low latency. The thesis finds out that employing rendezvous peer view is the reason of that, and proposes the solution to introduce the DHT into JXTA. The design and implementation of the solution are given at last.
引文
[1] Gnutella: http://www.gnutella.com
[2] Napster: http://www.napster.com
[3] C. E. Perkins (edt.). Ad Hoc Networking. Addison-Wesley, 2000.
[4] Ben Y. Zhao, John Kubiatowicz and Anthony D. Joseph. Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and Routing. Technical Report No. UCB/CSD-01-1141, University of California Berkeley, April 2001.
[5] Antony Rowstron, Peter Druschel. Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems. IFIP/ACM International Conference on Distributed Systems Platforms(Middleware 2001).
[6] Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan. Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications. In Proceeding of ACM SIGCOMM2001, San Diego, California, USA.
[7] Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker. A Scalable Content-Addressable Network. In Proceedings of ACM SIGCOMM 2001, San Diego, California, USA.
[8] Scan Rhea, Chris Wells, Patrick Eaton, Dennis Geels, Ben Zhao, Hakim Weatherspoon, and John Kubiatowicz. Maintenance-Free Global Data Storage. IEEE Internet Computing Sep/Oct 2001.
[9] C. Creg Plaxton, Rajmohan Rajaraman, Andrea W. Richa. Accessing nearby copies of replicated objects in a distributed environment. In Proceedings of ACM Symposium on Parallel Algorithms and Architectures. June 1997.
[10] DABEK, F., BRUNSKILL, E. KAASHOEK, et al. Building Peer-to-Peer Systems With Chord, a Distributed Lookup Service. In Proceedings of the 8th Workshop on Hot Topics in Operating Systems (HotOS-Ⅷ), Schloss Elmau, Germany, May 2001.
[11] STANFOR Peer Group's home page, http://www-db.stanford.edulpeers.2004
[12] PEER-TO-PEER WORKING GROUP. http://www.p2pwg.org.2001
[13] PEER-TO-PEER WORKING GROUP. Bidirectional Peer-to-Peer Communication with Interposing Firewalls and NATs. p2pwg White Paper, Revision 0.091. May 23,2001.
[14] GRID COMPUTING BIOTECHNOLOGY. http://www.gridcomputing.net, 2001.
[15] DRUSCHEL P. AND ROWSTRON, A. PAST: A Large-Scale, Persistent Peer-to-Peer Storage Utility, HotOS Ⅷ, Schloss Elmau, Germany, May 2001
[16] JXTA. The JXTA home page http://www.jxta.org, 2001.
[17] INTEL. Peer-to-Peer-Enabled Distributed Computing. Intel White Paper, 2001.
[18] Clarke I, Sandberg O, Wiley B, Hong T. Freenet: A distributed anonymous information storage and retrieval system. In: ICSI Workshop on Design Issues in Anonymity and Unobservability. 2000.
[19] 龚海刚，刘明，谢立．P2P流媒体传输的研究进展综述．计算机科学，2004，31(9)：20-22
[20] 刘业，杜庆伟，杨鹏．基于语义路由的P2P系统综述．计算机科学，2004，31(7)：26-28
[21] 熊继平，郭立鹏，洪佩琳，李津生．基于IPv6地址聚类性的改进型DHT网络．小型微型计算机系统，2006，27(008)：1421-1425
[22] 胡鹏，洪峰，李明禄．改进型Chord：利用节点会话时间的差异性提高P2P系统的稳定性．计算机应用与软件，2006，23(009)：57-58，60
[23] 许立波，于坤，吴国新．基于匹配路径和概率平衡树的P2P语义路由模型．软件学报，2006，17(010)：2106-2117
[24] 黄维雄，王晓宇．一种基于自配置策略的新型Peer-to-Peer平台系统．软件学报，2003，014(002)：237-246．
[25] 邹鹏．信任敏感的P2P拓扑构造及其相关技术研究：[博士学位论文]．长沙：国防科学技术大学，2003
[26] 宋建涛．对等计算中的若干问题研究：[博士学位论文]．上海：复旦大学，2004
[27] The Maze Web site. http://maze.pku.edu.cn
[28] Weimin Zheng, Jinfeng Hu, Ming Li. Granary: Architecture of Object Oriented Internet Storage Service. IEEE International Conference on E-Commerce Technology for Dynamic E-Business (CEC-EAST 2004). September 2004.
[29] Jinfeng Hu, Chunhui Hong, Huanan Zhang, Ming Li, Weimin Zheng, Dongsheng Wang. Tourist: Utilizing Heterogeneity to Build a Scalable, Efficient, and Apative DHT Routing Protocol. In Submission. Available at http://hpc.cs.tsinghua.edu.cn/granary/.
[30] The AnvSee Web site, http://grid.hust.edu.cn/anysee
[31] 张联峰,刘乃安,钱秀槟,张玉清．综述：对等网(P2P)技术．计算机工程与应用,2003,039(012)：142-14
[32] Q. Lv, P. Cao, E. Cohen, K. Li, and S. Shenker. Search and replication in unstructured peer-to-peer networks. Proceedings of 16th ACM International Conference on Supercomputing (ICS'02), New York, USA, June 2002.
[33] I. Clarke, T.W. Hong, S.G. Miller, O. Sandberg, and B. Wiley. Protecting free expression online with Freenet. IEEE Internet Computing 6(1), pp40-49 2002.
[34] I. Stoica, R. Morris, D. Karger, F. Kaashoek, and H. Balakrishnan. Chord: A scalable peer-topeer lookup service for Internet applications. Proceedings of ACM SIGCOMM 2001, August 2001.
[35] S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker. A scalable content addressable network. Proceedings of ACM SIGCOMM 2001, August 2001.
[36] A. Fiat, J. Saia. Censorship resistant peer-to-peer content addressable networks. Proceedings of the 13th ACMSIAM Symposium on Discrete Algorithms, San Francisco, USA, January 2002.
[37] C. Labovitz, A. Ahuja, A. Bose, and F. Jahanian. Delayed Internet Routing Covergence. IEEE/ACM Transactions on Networking, 9(3): 293-306, June 2001.
[38] Alex C. Snoeren, H. Balakrishnan. An End-to-End Approach to Host Mobility. In Proc. 6th ACM/IEEE MOBICOM, August 2000.
[39] 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, pp. 654-663.
[40] FIPS 180-1. Secure Hash Standard. U.S. Department of Commerce/NIST, National Technical Information Service, Springfield, VA, Apr. 1995.
[41] Sean C. Rhea, John Kubiatowicz. Probabilistic Location and Routing. In Proceedings of IEEE INFOCOM 2002.
[42] Pete Keleher, Samrat Bhattacharjee, and Bujor Silaghi. Are virtualized overlay networks too much of a good thing? In Proceedings of International Workshop on Peer-to-Peer Systems (IPTPS' 02), 2002.
[43] Bujor Silaghi, Samrat Bhattacharjee, Pete Keleher. Routing in the TerraDir Directory Service. In Proceedings of SPIE ITCOM'02, 2002.
[44] Waldovgel M, Rinaldi R. Efficient Topology-Aware Overlay Network[C]. ACM HotNets 2002, SIGC OMM/CCR, 2003.
[45] T. S. E. Ng, H. Zhang. Predicting Internet network distance with coordinates-based approaches. In Proceedings of the IEEE INFOCOM 2002.
[46] M. Pias, J. Crowcroft, S. Wilbur, S. Bhatti, and T. Harris. Lighthouses for Scalable Distributed Location. In Proc. of the 2nd Int. Workshop on. P2P Systems (IPTPS'03), Berkeley, CA, Feb. 2003.
[47] M. Costa, M. Castro, A. Rowstron, P. Key. Pie: Practical internet coordinates for distance estimation. In Proceedings of the IEEE ICDCS 2004.
[48] Christos Fatoutsos, Shari Roseman. Fractals for Secondary Key Retrieval. ACM SIGACT-SIGMOD-SIGART Symposium on PODS, pp. 247-252, 1989.
[49] Statistics of One-Way Internet Packet Delay http://www.ietf.org/vroceedinis/02mar/slides/ippm-4.pdf
[50] S. Waterhouse. JXTA Search: Distributed Search for Distributed Networks. white paper, Sun Microsystems, Palo Alto, Calif., 2001; available online at (current Nov. 2001). http://search.jxta.org/protocol.html
[51] JXTA Shetl.http://shell.jxta.org/
[52] Ratnasamy S, Handley M, Karp R, Shenker S. Topologically-Aware overlay construction and server selection. In Proc. of the IEEE INFOCOM Conf. New York: Institute of Electrical and Electronics Engineers, Inc., 2002. 1190-1199.
[53] Krishna P. Gummadi, Ramakrishna Gummadi, Steven D. Gribble, Sylvia Ratnasamy, Scott Shenker, Ion Stoica. The Impact of DHT Routing Geometry on Resilience and Proximity. In Proceedings of the ACM SIGCOMM Symposium on Network Architectures and Protocols, August 2003
[2] Napster: http://www.napster.com
[3] C. E. Perkins (edt.). Ad Hoc Networking. Addison-Wesley, 2000.
[4] Ben Y. Zhao, John Kubiatowicz and Anthony D. Joseph. Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and Routing. Technical Report No. UCB/CSD-01-1141, University of California Berkeley, April 2001.
[5] Antony Rowstron, Peter Druschel. Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems. IFIP/ACM International Conference on Distributed Systems Platforms(Middleware 2001).
[6] Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan. Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications. In Proceeding of ACM SIGCOMM2001, San Diego, California, USA.
[7] Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker. A Scalable Content-Addressable Network. In Proceedings of ACM SIGCOMM 2001, San Diego, California, USA.
[8] Scan Rhea, Chris Wells, Patrick Eaton, Dennis Geels, Ben Zhao, Hakim Weatherspoon, and John Kubiatowicz. Maintenance-Free Global Data Storage. IEEE Internet Computing Sep/Oct 2001.
[9] C. Creg Plaxton, Rajmohan Rajaraman, Andrea W. Richa. Accessing nearby copies of replicated objects in a distributed environment. In Proceedings of ACM Symposium on Parallel Algorithms and Architectures. June 1997.
[10] DABEK, F., BRUNSKILL, E. KAASHOEK, et al. Building Peer-to-Peer Systems With Chord, a Distributed Lookup Service. In Proceedings of the 8th Workshop on Hot Topics in Operating Systems (HotOS-Ⅷ), Schloss Elmau, Germany, May 2001.
[11] STANFOR Peer Group's home page, http://www-db.stanford.edulpeers.2004
[12] PEER-TO-PEER WORKING GROUP. http://www.p2pwg.org.2001
[13] PEER-TO-PEER WORKING GROUP. Bidirectional Peer-to-Peer Communication with Interposing Firewalls and NATs. p2pwg White Paper, Revision 0.091. May 23,2001.
[14] GRID COMPUTING BIOTECHNOLOGY. http://www.gridcomputing.net, 2001.
[15] DRUSCHEL P. AND ROWSTRON, A. PAST: A Large-Scale, Persistent Peer-to-Peer Storage Utility, HotOS Ⅷ, Schloss Elmau, Germany, May 2001
[16] JXTA. The JXTA home page http://www.jxta.org, 2001.
[17] INTEL. Peer-to-Peer-Enabled Distributed Computing. Intel White Paper, 2001.
[18] Clarke I, Sandberg O, Wiley B, Hong T. Freenet: A distributed anonymous information storage and retrieval system. In: ICSI Workshop on Design Issues in Anonymity and Unobservability. 2000.
[19] 龚海刚，刘明，谢立．P2P流媒体传输的研究进展综述．计算机科学，2004，31(9)：20-22
[20] 刘业，杜庆伟，杨鹏．基于语义路由的P2P系统综述．计算机科学，2004，31(7)：26-28
[21] 熊继平，郭立鹏，洪佩琳，李津生．基于IPv6地址聚类性的改进型DHT网络．小型微型计算机系统，2006，27(008)：1421-1425
[22] 胡鹏，洪峰，李明禄．改进型Chord：利用节点会话时间的差异性提高P2P系统的稳定性．计算机应用与软件，2006，23(009)：57-58，60
[23] 许立波，于坤，吴国新．基于匹配路径和概率平衡树的P2P语义路由模型．软件学报，2006，17(010)：2106-2117
[24] 黄维雄，王晓宇．一种基于自配置策略的新型Peer-to-Peer平台系统．软件学报，2003，014(002)：237-246．
[25] 邹鹏．信任敏感的P2P拓扑构造及其相关技术研究：[博士学位论文]．长沙：国防科学技术大学，2003
[26] 宋建涛．对等计算中的若干问题研究：[博士学位论文]．上海：复旦大学，2004
[27] The Maze Web site. http://maze.pku.edu.cn
[28] Weimin Zheng, Jinfeng Hu, Ming Li. Granary: Architecture of Object Oriented Internet Storage Service. IEEE International Conference on E-Commerce Technology for Dynamic E-Business (CEC-EAST 2004). September 2004.
[29] Jinfeng Hu, Chunhui Hong, Huanan Zhang, Ming Li, Weimin Zheng, Dongsheng Wang. Tourist: Utilizing Heterogeneity to Build a Scalable, Efficient, and Apative DHT Routing Protocol. In Submission. Available at http://hpc.cs.tsinghua.edu.cn/granary/.
[30] The AnvSee Web site, http://grid.hust.edu.cn/anysee
[31] 张联峰,刘乃安,钱秀槟,张玉清．综述：对等网(P2P)技术．计算机工程与应用,2003,039(012)：142-14
[32] Q. Lv, P. Cao, E. Cohen, K. Li, and S. Shenker. Search and replication in unstructured peer-to-peer networks. Proceedings of 16th ACM International Conference on Supercomputing (ICS'02), New York, USA, June 2002.
[33] I. Clarke, T.W. Hong, S.G. Miller, O. Sandberg, and B. Wiley. Protecting free expression online with Freenet. IEEE Internet Computing 6(1), pp40-49 2002.
[34] I. Stoica, R. Morris, D. Karger, F. Kaashoek, and H. Balakrishnan. Chord: A scalable peer-topeer lookup service for Internet applications. Proceedings of ACM SIGCOMM 2001, August 2001.
[35] S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker. A scalable content addressable network. Proceedings of ACM SIGCOMM 2001, August 2001.
[36] A. Fiat, J. Saia. Censorship resistant peer-to-peer content addressable networks. Proceedings of the 13th ACMSIAM Symposium on Discrete Algorithms, San Francisco, USA, January 2002.
[37] C. Labovitz, A. Ahuja, A. Bose, and F. Jahanian. Delayed Internet Routing Covergence. IEEE/ACM Transactions on Networking, 9(3): 293-306, June 2001.
[38] Alex C. Snoeren, H. Balakrishnan. An End-to-End Approach to Host Mobility. In Proc. 6th ACM/IEEE MOBICOM, August 2000.
[39] 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, pp. 654-663.
[40] FIPS 180-1. Secure Hash Standard. U.S. Department of Commerce/NIST, National Technical Information Service, Springfield, VA, Apr. 1995.
[41] Sean C. Rhea, John Kubiatowicz. Probabilistic Location and Routing. In Proceedings of IEEE INFOCOM 2002.
[42] Pete Keleher, Samrat Bhattacharjee, and Bujor Silaghi. Are virtualized overlay networks too much of a good thing? In Proceedings of International Workshop on Peer-to-Peer Systems (IPTPS' 02), 2002.
[43] Bujor Silaghi, Samrat Bhattacharjee, Pete Keleher. Routing in the TerraDir Directory Service. In Proceedings of SPIE ITCOM'02, 2002.
[44] Waldovgel M, Rinaldi R. Efficient Topology-Aware Overlay Network[C]. ACM HotNets 2002, SIGC OMM/CCR, 2003.
[45] T. S. E. Ng, H. Zhang. Predicting Internet network distance with coordinates-based approaches. In Proceedings of the IEEE INFOCOM 2002.
[46] M. Pias, J. Crowcroft, S. Wilbur, S. Bhatti, and T. Harris. Lighthouses for Scalable Distributed Location. In Proc. of the 2nd Int. Workshop on. P2P Systems (IPTPS'03), Berkeley, CA, Feb. 2003.
[47] M. Costa, M. Castro, A. Rowstron, P. Key. Pie: Practical internet coordinates for distance estimation. In Proceedings of the IEEE ICDCS 2004.
[48] Christos Fatoutsos, Shari Roseman. Fractals for Secondary Key Retrieval. ACM SIGACT-SIGMOD-SIGART Symposium on PODS, pp. 247-252, 1989.
[49] Statistics of One-Way Internet Packet Delay http://www.ietf.org/vroceedinis/02mar/slides/ippm-4.pdf
[50] S. Waterhouse. JXTA Search: Distributed Search for Distributed Networks. white paper, Sun Microsystems, Palo Alto, Calif., 2001; available online at (current Nov. 2001). http://search.jxta.org/protocol.html
[51] JXTA Shetl.http://shell.jxta.org/
[52] Ratnasamy S, Handley M, Karp R, Shenker S. Topologically-Aware overlay construction and server selection. In Proc. of the IEEE INFOCOM Conf. New York: Institute of Electrical and Electronics Engineers, Inc., 2002. 1190-1199.
[53] Krishna P. Gummadi, Ramakrishna Gummadi, Steven D. Gribble, Sylvia Ratnasamy, Scott Shenker, Ion Stoica. The Impact of DHT Routing Geometry on Resilience and Proximity. In Proceedings of the ACM SIGCOMM Symposium on Network Architectures and Protocols, August 2003