基于P2P模式的普适服务发现策略的研究
|
摘要
随着普适计算时代的到来,各种支持普适计算环境的服务发现技术研究在如火如荼的进行。考虑到普适计算环境的高度自组织特性,P2P模式的资源查找算法为研究普适环境中的服务发现提供了优秀的理论基础。
目前已有的P2P资源发现算法主要有集中索引算法、结构化算法、非结构化算法以及混合发现算法。集中索引算法以Napster系统为代表,采用了集中式的目录服务器机制,该算法存在单点失效的问题,即目录服务器将成为整个P2P系统的瓶颈,一旦中心服务器出现问题,将导致整个系统崩溃。非结构化算法代表系统为Gnutella,采用洪泛或类洪泛算法,每一个用户消息都将被广播给与该用户直接相连的若干其他用户,这些用户收到消息后,也同样地将消息广播给各自连接的用户,依此类推,直到请求被应答或消息的TTL(Time To Live)值减少为0,该算法可靠性差,对网络的资源消耗大,安全性低,容易大量散播垃圾文件和病毒。结构化算法典型代表包括Tapestry, Pastry, CAN和Chord等,它们都采用了一种分布式哈希表(Distributed Hashing Table,DHT)的数据结构,并根据不同的算法决定网络中节点维护哈希表的方式。这几种采用不同节点和资源部署方式的结构化算法中,性能最好、应用最为广泛的是Chord。混合发现算法则结合了集中索引和完全分布式两种算法来构建网络拓扑。
本文针对如何提升结构化算法的发现效率和发现覆盖率问题,基于Chord算法,结合Small World理论,提出新的指针表构建算法。传统的DHT发现算法中,每个节点维护的指针表存储的是临近节点的节点信息。为了构建Small-World模型,本课题提出了添加远程节点信息的思想,每个节点维护的指针表通过计算后删除冗余信息,加入相应的远程索引。与一些已经提出的采用随机选取远程连接节点的算法不同,本文将通过本地节点的计算来选取远程节点,保证加入远程连接节点后既能使服务发现的范围覆盖整个网络,又不会增加指针表的长度,并简化了指针表的计算和维护工作。通过仿真证明了该算法能有效减小服务发现的路径长度,提高服务发现成功率。
本文由五章组成,第一章介绍了P2P模式的资源发现研究背景和研究现状；第二章介绍了P2P网络的特点和P2P网络的搜索模式,为我们研究普适环境的服务发现模式奠定了理论基础；第三章介绍了原始的Chord及改进后的Chord协议,并分析了它们各自的不足。第四章给出了本文对Chord算法的改进方案,并对改进算法进行理论分析、仿真以及仿真结果分析；第五章是总结及展望。
With the era of pervasive computing comes, variety of service discovery technology that support pervasive computing environment is researching. Considering the high degree self-organization of pervasive computing environment.P2P service discovery algorithm provides a good theoretical basis for researching service discovery in pervasive environment.
At present, the P2P resource discovery algorithms are concentrated indexing algorithms, structured algorithms, unstructured algorithms and mixed-discovery algorithm. Napster system as the representative of concentrated indexing algorithm, using a centralized directory server mechanism, there is single point of failure problem in this algorithm, the directory server will be the bottleneck of the entire P2P system, once the central server have any problems, will cause the entire system collapsed. Gnutella is the representation of unstructured algorithms, it using flood or similar flooding algorithm, each user broadcasts the message to the user which directly linked to it, after these users received the message, they also broadcast the message to the respective users who connect it.By analogy, until the request is answered or the TTL value of a message reduce to O.The reliability of the algorithm is poor,and the consumption of the network resource are huge.The typical representative of structure algorithms including Tapestry, Pastry, CAN and Chord, all of them are using a distributed hash table (DHT) data structure,and according to different algorithms they decide the way of the nodes maintain hash table in network. In these typical representation of structure algorithms, Chord algorithm has the best performance and used the most widely. Mixed-discovery algorithm combines concentrated indexing algorithm and fully distributed algorithm to construct the network topology.
In this paper, we focus on how to enhance the discovery efficiency and coverage of the structure algorithm. Based on the Chord algorithm, combining with Small World theory, we put forward a new algorithm for fingertable construction. The traditional DHT discovery algorithm each node maintain the fingertable that store node information of adjacent node, In order to build Small-World Model, This issue put forward the idea to add a remote node information. The fingertable of each node delete redundant information by calculating, add the corresponding remote index.It is different from algorithm of select the remote connection node randomly. This paper selects the remote connection node by calculateing local node, after adding a remote connection node it can assure both make the range of service discovery cover all network and not increase the length of fingertable, simplifies the calculation of the fingertable and maintenance work. The simulation proved that the algorithm can reduce the path length of service discovery effectively, improve success rate of service discovery.
This paper formed by the five chapters. The first chapter describes the resource background of discovery research and research status of P2P model; The second chapter describes the characteristics of P2P networks and search models of P2P network, these theory laid the foundation of service discovery in pervasive environment that we research; The third chapter describes the traditional Chord and Chord algorithm, and analyse the shortage of them; The fourth chapter gives an improved method of Chord algorithm. And theoretical analysis of the improved algorithm, simulation and simulation results analysis; The fifth chapter is the summary and prospects.
目前已有的P2P资源发现算法主要有集中索引算法、结构化算法、非结构化算法以及混合发现算法。集中索引算法以Napster系统为代表,采用了集中式的目录服务器机制,该算法存在单点失效的问题,即目录服务器将成为整个P2P系统的瓶颈,一旦中心服务器出现问题,将导致整个系统崩溃。非结构化算法代表系统为Gnutella,采用洪泛或类洪泛算法,每一个用户消息都将被广播给与该用户直接相连的若干其他用户,这些用户收到消息后,也同样地将消息广播给各自连接的用户,依此类推,直到请求被应答或消息的TTL(Time To Live)值减少为0,该算法可靠性差,对网络的资源消耗大,安全性低,容易大量散播垃圾文件和病毒。结构化算法典型代表包括Tapestry, Pastry, CAN和Chord等,它们都采用了一种分布式哈希表(Distributed Hashing Table,DHT)的数据结构,并根据不同的算法决定网络中节点维护哈希表的方式。这几种采用不同节点和资源部署方式的结构化算法中,性能最好、应用最为广泛的是Chord。混合发现算法则结合了集中索引和完全分布式两种算法来构建网络拓扑。
本文针对如何提升结构化算法的发现效率和发现覆盖率问题,基于Chord算法,结合Small World理论,提出新的指针表构建算法。传统的DHT发现算法中,每个节点维护的指针表存储的是临近节点的节点信息。为了构建Small-World模型,本课题提出了添加远程节点信息的思想,每个节点维护的指针表通过计算后删除冗余信息,加入相应的远程索引。与一些已经提出的采用随机选取远程连接节点的算法不同,本文将通过本地节点的计算来选取远程节点,保证加入远程连接节点后既能使服务发现的范围覆盖整个网络,又不会增加指针表的长度,并简化了指针表的计算和维护工作。通过仿真证明了该算法能有效减小服务发现的路径长度,提高服务发现成功率。
本文由五章组成,第一章介绍了P2P模式的资源发现研究背景和研究现状；第二章介绍了P2P网络的特点和P2P网络的搜索模式,为我们研究普适环境的服务发现模式奠定了理论基础；第三章介绍了原始的Chord及改进后的Chord协议,并分析了它们各自的不足。第四章给出了本文对Chord算法的改进方案,并对改进算法进行理论分析、仿真以及仿真结果分析；第五章是总结及展望。
With the era of pervasive computing comes, variety of service discovery technology that support pervasive computing environment is researching. Considering the high degree self-organization of pervasive computing environment.P2P service discovery algorithm provides a good theoretical basis for researching service discovery in pervasive environment.
At present, the P2P resource discovery algorithms are concentrated indexing algorithms, structured algorithms, unstructured algorithms and mixed-discovery algorithm. Napster system as the representative of concentrated indexing algorithm, using a centralized directory server mechanism, there is single point of failure problem in this algorithm, the directory server will be the bottleneck of the entire P2P system, once the central server have any problems, will cause the entire system collapsed. Gnutella is the representation of unstructured algorithms, it using flood or similar flooding algorithm, each user broadcasts the message to the user which directly linked to it, after these users received the message, they also broadcast the message to the respective users who connect it.By analogy, until the request is answered or the TTL value of a message reduce to O.The reliability of the algorithm is poor,and the consumption of the network resource are huge.The typical representative of structure algorithms including Tapestry, Pastry, CAN and Chord, all of them are using a distributed hash table (DHT) data structure,and according to different algorithms they decide the way of the nodes maintain hash table in network. In these typical representation of structure algorithms, Chord algorithm has the best performance and used the most widely. Mixed-discovery algorithm combines concentrated indexing algorithm and fully distributed algorithm to construct the network topology.
In this paper, we focus on how to enhance the discovery efficiency and coverage of the structure algorithm. Based on the Chord algorithm, combining with Small World theory, we put forward a new algorithm for fingertable construction. The traditional DHT discovery algorithm each node maintain the fingertable that store node information of adjacent node, In order to build Small-World Model, This issue put forward the idea to add a remote node information. The fingertable of each node delete redundant information by calculating, add the corresponding remote index.It is different from algorithm of select the remote connection node randomly. This paper selects the remote connection node by calculateing local node, after adding a remote connection node it can assure both make the range of service discovery cover all network and not increase the length of fingertable, simplifies the calculation of the fingertable and maintenance work. The simulation proved that the algorithm can reduce the path length of service discovery effectively, improve success rate of service discovery.
This paper formed by the five chapters. The first chapter describes the resource background of discovery research and research status of P2P model; The second chapter describes the characteristics of P2P networks and search models of P2P network, these theory laid the foundation of service discovery in pervasive environment that we research; The third chapter describes the traditional Chord and Chord algorithm, and analyse the shortage of them; The fourth chapter gives an improved method of Chord algorithm. And theoretical analysis of the improved algorithm, simulation and simulation results analysis; The fifth chapter is the summary and prospects.
引文
[1]Weiser M. The computer for the twenty-first century[J]. Scientific American, 1991, vol.265, no.3:94-104
[2]邢小良.P2P技术及其应用[M].人民邮电出版社.2008
[3]白云.P2P环境中基于语义的资源自组织、发现及推荐研究[D].重庆：西南大学,2008
[4]刘业.适应自组织管理模式的P2P网络技术的研究[D].福建：东南大学,2006
[5]金响红,项明.基于移动代理的P2P网络资源发现方法研究[J].微型电脑应用,2004,vol.20,No.3：37-39
[6]Napster[Z]. http://www.napster.Com,2003
[7]Gnutella[Z]. http://gnutella.wego.Com,2003
[8]Ratnasamy S,Francis P,Handley M et al.A scalable content-addressable network[C]. In:Govindan R ed. Proc of the ACM SIGCOMM,2001, ACM Press,2001:161 - 172
[9]Rowstron A, druschel P. Pastry:scalable, distributed object location and routing for large-scale peer-to-peer system[C]. In:Guerraoui Red. Proc of the Middleware, Heidelberg:Springer-Verlag,2001:329-350
[10]B Kubiatowicz J, Joseph A. Tapestry:An infrastruture for fault-tolerant wide-area location and routing[R].Technical Report., UCB/CSD-01-1141,Computer Sience Division,U C Berkeley,2001
[11]I.Stoica R,Morris D, Karger M Kaashoek F, Balakrishnan H, Chord:a scalable peer-to-peer lookup service for Internet applications,In Proc ACM SIGCOMM01, San Diego, CA, Aug,2001.
[12]Zhang D G. Web-Based Seamless Migration for Task-oriented Nomadic Service, International Journal of Distance Education Techonolgoy (JDET) [J].2006,4(3):108-115.
[13]TEO YM, MARCH V, WANG X. A DHT based grid resource indexing and discovery scheme[R].MIT Alliance Annual Symposium.Singapore:[s. n.],2005.
[14]Zhang D G, Shi Y C, Xu G Y. A Kind of Smart Space for Remote Interactive Access Based on Pervasive Computing[C], The 2nd International Conference on Web-based Learning (ICWL 2003). Springer-Verlag, LNCS, Sydney, Australia.2003
[15]Zhang D G, Shi Y C, Xu G Y. Learning by Seamless Migration---A Kind of Mobile Working Paradigm[C], In Proceedings of the 3th International Conference on Web-based Learning (ICWL2004), Springer-Verlag, LNCS, Beijing, China.2004
[16]陈贵海,吴帆,李宏兴,邱彤庆.基于DHT的P2P系统中高可用数据冗余机制[J].计算机学报.2008,Vol.31 No.10：1696-1703
[17]王昔.P2P应用,运营商下一个增值热点[Z].IT168.2006-10-17
[18]Daswani, Neil, Garcia-Molina, Hector, and Yang, Beverly. Open Problems in Data-Sharing Peer-to-Peer Systems[C]. In:Proceedings of the 9th International Conference on Database Theory (ICDT). Siena, Italy:2003.
[19]Zhao, B., Kubiatowicz, J., and Joseph, A. Tapestry:An infrastructure for fault-tolerant wide-area location and routing[J]. Technical Report UCB/CSD-01-1141, Computer Science Division, U. C. Berkeley.2001
[20]Stoica, I., Morris, R., Karger, D., Kaashoek, M. F., and Balakrishnan, H. Chord: A scalable peer-to-peer lookup service for Internet applications[J]. In:Proc. ACM SIGCOMM'01. SanDiego, CA:2001.
[21]Milgram, S. The small world problem[J]. Psychology Today,1967, (2):60-67
[22]顾荣强.可管理P2P引领IPTV技术潮流[Z].流媒体网.2006-9-11
[23]张辰DyChord:一种动态自适应结构化P2P网络[D].上海：上海交通大学软件学院,2008
[24]任小金,古志民,高志伟,段赵磊RR-Chord:一种基于Chord的低开销快速查询P2P系统[J].北京理工大学学报.2008,Vo1.28,no.2,134-138
[25]于少山DR-Chord:一种高效的双环Chord协议的研究[D].新疆：新疆大学计算机应用专业,2007
[26]李伟荣,吴国新,李建飞Small-World在对等网络中的应用[J].计算机工程与应用.2006,158-161
[27]Watts, D. J. and Strogatz, S. H. Collective dynamics of small-world networks [J]. Nature,1998,393:440-442
[28]J. Kleiberg. The small-world phenomenon:An algorithmic perspective[R]. Cornell Computer Science Tech. Pep,1999
[29]卢国明,韩永国,孙世新,王磊.基于知识的P2P网格资源发现研究[J].计算机应用研究.2007,Vol.24,no.4,295-298
[30]解哲.P2P网络中Chord搜索算法的改进与实现[D].吉林：吉林大学软件工程专业,2008
[31]曹俊,宗平Chord算法的研究和改进[.J].科技咨询.2008,No.3,233-236
[32]朱晓姝,周娅,黄桂敏.对等网络仿真模型研究[N].桂林电子工业学报.2006,Vol26.No.2：105-108
[33]王国洪.基于P2P的网络仿真的协议可扩展性研究[D].北京：北方工业大学计算机应用技术专业,2008
[34]俞嘉地BitTorrent对等网文件共享系统关键技术研究[D].上海：上海交通大学计算机科学与工程系,2007
[35]卢丽.P2P网络资源搜索模型的研究[D].重庆：重庆大学计算机应用技术专业,2007
[36]宋建涛.对等计算中的若干问题研究[D].上海：复旦大学计算机科学与工程系,2003
[37]朱骏.基于小群体特性的P2P网络自组织资源查找算法的研究[D].上海：上海交通大学通信与信息系统专业,2007
[38]朱郑州,吴中福,吴开贵,周尚波.基于用户满意度的学习服务发现算法[J].计算机工程.2009,Vol.35 No.3,71-73
[39]王必晴,贺鹏H-Chord:基于层次划分的Chord路由模型及算法实现[J].计算机工程与应用.2007,43(36)：141-168
[40]刘小虎,蒋从锋,李垦.lndexPeer:半结构化P2P系统资源发现模型及其DHT算法[J].计算机应用研究.2008,Vol.25 No.6：1648-1651
[41]李士宁,夏贻勇,杜艳丽.对等网中DHT搜索算法综述[J].计算机应用研究.2008,Vol.25No.6：1611-1615
[42]李普聪,魏文红.基于DHT的P2P覆盖网络的研究[J].计算机工程.2008,Vol.34 No.7：101-103
[43]段一飞,林关成,王凤琳.基于DHT的P2P网络资源定范围模型研究[N].宝鸡文理学院学报.2007.Vol.27 No.1：60-63
[2]邢小良.P2P技术及其应用[M].人民邮电出版社.2008
[3]白云.P2P环境中基于语义的资源自组织、发现及推荐研究[D].重庆：西南大学,2008
[4]刘业.适应自组织管理模式的P2P网络技术的研究[D].福建：东南大学,2006
[5]金响红,项明.基于移动代理的P2P网络资源发现方法研究[J].微型电脑应用,2004,vol.20,No.3：37-39
[6]Napster[Z]. http://www.napster.Com,2003
[7]Gnutella[Z]. http://gnutella.wego.Com,2003
[8]Ratnasamy S,Francis P,Handley M et al.A scalable content-addressable network[C]. In:Govindan R ed. Proc of the ACM SIGCOMM,2001, ACM Press,2001:161 - 172
[9]Rowstron A, druschel P. Pastry:scalable, distributed object location and routing for large-scale peer-to-peer system[C]. In:Guerraoui Red. Proc of the Middleware, Heidelberg:Springer-Verlag,2001:329-350
[10]B Kubiatowicz J, Joseph A. Tapestry:An infrastruture for fault-tolerant wide-area location and routing[R].Technical Report., UCB/CSD-01-1141,Computer Sience Division,U C Berkeley,2001
[11]I.Stoica R,Morris D, Karger M Kaashoek F, Balakrishnan H, Chord:a scalable peer-to-peer lookup service for Internet applications,In Proc ACM SIGCOMM01, San Diego, CA, Aug,2001.
[12]Zhang D G. Web-Based Seamless Migration for Task-oriented Nomadic Service, International Journal of Distance Education Techonolgoy (JDET) [J].2006,4(3):108-115.
[13]TEO YM, MARCH V, WANG X. A DHT based grid resource indexing and discovery scheme[R].MIT Alliance Annual Symposium.Singapore:[s. n.],2005.
[14]Zhang D G, Shi Y C, Xu G Y. A Kind of Smart Space for Remote Interactive Access Based on Pervasive Computing[C], The 2nd International Conference on Web-based Learning (ICWL 2003). Springer-Verlag, LNCS, Sydney, Australia.2003
[15]Zhang D G, Shi Y C, Xu G Y. Learning by Seamless Migration---A Kind of Mobile Working Paradigm[C], In Proceedings of the 3th International Conference on Web-based Learning (ICWL2004), Springer-Verlag, LNCS, Beijing, China.2004
[16]陈贵海,吴帆,李宏兴,邱彤庆.基于DHT的P2P系统中高可用数据冗余机制[J].计算机学报.2008,Vol.31 No.10：1696-1703
[17]王昔.P2P应用,运营商下一个增值热点[Z].IT168.2006-10-17
[18]Daswani, Neil, Garcia-Molina, Hector, and Yang, Beverly. Open Problems in Data-Sharing Peer-to-Peer Systems[C]. In:Proceedings of the 9th International Conference on Database Theory (ICDT). Siena, Italy:2003.
[19]Zhao, B., Kubiatowicz, J., and Joseph, A. Tapestry:An infrastructure for fault-tolerant wide-area location and routing[J]. Technical Report UCB/CSD-01-1141, Computer Science Division, U. C. Berkeley.2001
[20]Stoica, I., Morris, R., Karger, D., Kaashoek, M. F., and Balakrishnan, H. Chord: A scalable peer-to-peer lookup service for Internet applications[J]. In:Proc. ACM SIGCOMM'01. SanDiego, CA:2001.
[21]Milgram, S. The small world problem[J]. Psychology Today,1967, (2):60-67
[22]顾荣强.可管理P2P引领IPTV技术潮流[Z].流媒体网.2006-9-11
[23]张辰DyChord:一种动态自适应结构化P2P网络[D].上海：上海交通大学软件学院,2008
[24]任小金,古志民,高志伟,段赵磊RR-Chord:一种基于Chord的低开销快速查询P2P系统[J].北京理工大学学报.2008,Vo1.28,no.2,134-138
[25]于少山DR-Chord:一种高效的双环Chord协议的研究[D].新疆：新疆大学计算机应用专业,2007
[26]李伟荣,吴国新,李建飞Small-World在对等网络中的应用[J].计算机工程与应用.2006,158-161
[27]Watts, D. J. and Strogatz, S. H. Collective dynamics of small-world networks [J]. Nature,1998,393:440-442
[28]J. Kleiberg. The small-world phenomenon:An algorithmic perspective[R]. Cornell Computer Science Tech. Pep,1999
[29]卢国明,韩永国,孙世新,王磊.基于知识的P2P网格资源发现研究[J].计算机应用研究.2007,Vol.24,no.4,295-298
[30]解哲.P2P网络中Chord搜索算法的改进与实现[D].吉林：吉林大学软件工程专业,2008
[31]曹俊,宗平Chord算法的研究和改进[.J].科技咨询.2008,No.3,233-236
[32]朱晓姝,周娅,黄桂敏.对等网络仿真模型研究[N].桂林电子工业学报.2006,Vol26.No.2：105-108
[33]王国洪.基于P2P的网络仿真的协议可扩展性研究[D].北京：北方工业大学计算机应用技术专业,2008
[34]俞嘉地BitTorrent对等网文件共享系统关键技术研究[D].上海：上海交通大学计算机科学与工程系,2007
[35]卢丽.P2P网络资源搜索模型的研究[D].重庆：重庆大学计算机应用技术专业,2007
[36]宋建涛.对等计算中的若干问题研究[D].上海：复旦大学计算机科学与工程系,2003
[37]朱骏.基于小群体特性的P2P网络自组织资源查找算法的研究[D].上海：上海交通大学通信与信息系统专业,2007
[38]朱郑州,吴中福,吴开贵,周尚波.基于用户满意度的学习服务发现算法[J].计算机工程.2009,Vol.35 No.3,71-73
[39]王必晴,贺鹏H-Chord:基于层次划分的Chord路由模型及算法实现[J].计算机工程与应用.2007,43(36)：141-168
[40]刘小虎,蒋从锋,李垦.lndexPeer:半结构化P2P系统资源发现模型及其DHT算法[J].计算机应用研究.2008,Vol.25 No.6：1648-1651
[41]李士宁,夏贻勇,杜艳丽.对等网中DHT搜索算法综述[J].计算机应用研究.2008,Vol.25No.6：1611-1615
[42]李普聪,魏文红.基于DHT的P2P覆盖网络的研究[J].计算机工程.2008,Vol.34 No.7：101-103
[43]段一飞,林关成,王凤琳.基于DHT的P2P网络资源定范围模型研究[N].宝鸡文理学院学报.2007.Vol.27 No.1：60-63