论文部分内容阅读
摘要：Chord是一种比较有效的P2P路由算法，它能够快速地查找到该资源的位置，但是当节点能力差异较大时会影响网络的稳定性；Chord环上的节点ID与实际物理地址不一致会造成信息的延迟现象；混合式的P2P能够较好的管理能力较差的节点，但是查询具有盲目性。该文通过分析它们两者的优缺点提出了基于混合结构的Chord系统，在一定程度上解决了传统Chord的稳定性、绕路问题和混合P2P结构的查询效率问题。
关键词：Chord；P2P；混合的P2P结构
中图分类号：TP393文献标识码：A文章编号：1009-3044(2008)35-2559-02
Based on the Mixed Structure of the Chord System
ZENG Xiao-yun
(Guangxi University of Finance and Economics,Nanning 530003,China)
Abstract: Chord is an efficient routing algorithm of P2P, and it can locate resources quickly. However, the stability of network will be impacted when the abilities of nodes is different. The disaccord between actually physical address and node ID of Chord ring also leads to information delay. Hybrid P2P could be used to effectively manage the nodes with bad managing abilities, but its query lacks of clear objects. This paper analyses both advantages and disadvantages of them, and suggests a new Chord system based on mixed structure. It will solve the problems which involve the stability of traditional Chord, detour limitations and query efficiency of hybrid P2P.
Key words: chord;P2P;hybrid P2P
1 引言
当今，P2P搜索技术是网络研究的热点。集中式、结构化、非结构化和混合式的P2P结构各有各的优缺点。其中Chord网络模型，以它的无中心控制、可扩展强、负载平衡、高容错和使查询具有方向性使得P2P的优势更为突出，但现实环境中，Chord环上的节点之间存在很大差异性，有很多能力较弱的节点在Chord中作为独立节点的时候，也要负责系统中大量的查询和下载工作，由于自身资源的限制，它们必然会引起系统响应时间增加等问题，可能成为系统的瓶颈；而且，这些能力较差的节点可能随时出现加入或离开系统的情况，这种频繁的变迁必定增加结构化P2P系统的开销；同时，搜索网络与物理网络不一致产生查询的绕路问题。而混合结构的P2P系统通过处理能力较强的超级节点管理其他节点，能较好的管理能力弱的节点；但是混合结构的P2P系统在查询时需要通过泛洪方式来进行，使得查询盲目没有方向性，查询效率较低。如果能够造一个系统将他们两者结合起来，取长补短，应该可以克服双方的缺点。
2 基于混合结构的Chord系统模型
为了实现上述想法，我们让处理能力强、网络带宽大的超级节点作为Chord系统中的独立节点，负责管理其它的节点，并代替那些节点来负担的部分工作，就像是很多局域网的服务器作为Chord系统的节点一样，搜索仅在超级节点中进行。如下图(矩形表示超级节点，小圆圈表示普通节点)。
我们采用超级节点的IP地址前缀作为Chord模型的节点标识，并按照IP地址前缀将超级节点顺序排成Chord环。在一定程度上可以保证标识相近的超级节点在Chord网络中也是相邻的。每个超级节点都直接管理若干普通节点，它们具有与超级节点标识相等的IP地址前缀。从而改变了传统P2P系统中Chord网络节点由单个节点构成的状况,增强了网络节点的健壮性。
3 系统基本操作
每个超级节点维护一张本地客户索引表，以保存与自己IP地址前缀相同的客户机信息，还有一张信息索引表，记录该超级节点所管理的客户机和发布在它们上的信息资源关键字的hash值。
3.1 节点的加入
这一部分主要处理新结点的加入以及由此带来的网络自适应问题。
当一个普通节点A加入系统的时候，它首先找到系统中的一个超级节点B，然后比较A和B的IP地址前缀，如果前缀相同，则A作为B的一个客户机添加到以B为超级节点的域中，B修改本地客户索引表，将A的信息添加进去。这是超级节点所在域的内部操作，对外是不可见的。如果在Chord环中没有找到与之前缀相同的超级节点，则网络不允许A直接加入Chord环，只有等到A有一个自己的超级节点后，才能让该超级节点加入Chord。而域中超级节点的Chord路由表则不必进行更新，这将使得节点加入频繁的情况下Chord 系统的路由也不会受到太大影响，从而提高了系统的效率。如果加入系统的节点是超级节点，则它根据自己IP地址前缀在Chord上找到自己的位置，并调用Chord处理节点加入的函数修改其前驱和后继的指针表完成加入操作。
3.2 信息发布
当一个结点加入了Chord网络后，它就可以把它本身的资源发布出去了。在发布它的资源之前，它首先会hash它所要发布的资源，由此得到一个资源的hash值，发送给自己的超级节点，超级节点调用find successor函数，查找此hash值的所对应的超级节点，找到后资源的hash值送到这个超级结点上，保存在信息索引表中；然后超级节点在自己的本地客户索引表中随机找出一个客户机，将该客户机的信息添加到信息索引表相应的资源记录上，这样就能实现资源的发布了。
3.3 信息查询
当超级节点A所管理的客户机C想查询某个信息时，C首先把要查找的资源的关键字进行一个hash操作，得到一个hash值，发送给A，A调用find successor函数，找到此hash值的对应超级节点B，B在接收到此请求后，在自己的信息索引表中搜索存放有该信息hash值的记录，找到相应的客户机，如果未找到，发送找不到，如果找到，把找到的记录发送给结点C，此记录信息包含存储所要查找的资源，最后，结点C与这个结点建立连接通信，使资源的传送在两个结点之间进行，而不经过任何服务器。这样的查找方法使得查找具有方向性，不需要再像混合结构的系统那样进行泛洪搜索。
3.4 节点的退出
在传统的Chord 系统中, 如果节点A是Chord环上的某个节点（即超级节点），则它退出的时候，路由表中包含A的节点都将把A替换成A的后继。如果使用基于混合结构的Chord系统，Chord环上的节点是超级节点，该超级节点所管理的域中某一客户机退出不会影响Chord环中超级节点的路由表中的信息，只需超级节点的本地客户索引表中将该客户机的信息删除并将发布在它上面的信息转移到别的节点上即可。这就可以保证Chord系统在有节点频繁退出时的稳定性。当然，超级节点也有退出Chord环的可能,无论是超级节点B正常或异常退出，根据Chord的自适应能力，能将原先发布在B上的信息转移到后继节点C上。 但是，因为超级节点是某个局域网的服务器，具有较强的性能，所以一般情况下不会出现失效退出的情况。
3.5 负载均衡
如果由于发布在某个节点上的信息很热门引发了高访问量，则有可能会造成网络拥塞。为了解决这个问题，超级节点需要定期检查各个客户机的文件访问情况，挑选出一段时间内访问频率较高的文件，将他们冗余复制到自己的邻居超级节点上。
4 系统评估
由于根据IP地址对节点进行了分组,可以保证物理位置相邻的节点属于同一区域内,普通节点加入或者退出系统所引发的不稳定性远少于传统的Chord；并且信息的转储只发生在物理位置相邻的超级节点间,提高了网络的稳定性；信息的路由按照从近到远的顺序进行，减少了信息在网络上的传输距离、及传输时延,因而减少了信息在网络中传输的代价；而且因为引入了Chord环，克服了混合P2P模型泛洪的致使查询效率低下的问题。
5 下一步的工作
该论文将Chord系统和混合结构的P2P系统结合起来，在一定程度上优化了P2P系统的结构，使得系统的稳定性和可靠性及效率有了提高。但是对于安全问题和并行查找没有进行研究，这将是下一步努力的方向。
参考文献：
[1] 任小金,古志民,高志伟,段赵磊. RR-Chord:一个基于Chord 的低开销快速查询P2P系统[J].北京理工大学学报,2008,28(2):134-138.
[2] 杨明华,曹元大,张常有,于炯,谭励.Fast-chord:快速部署的P2P覆盖网络[J].计算机应用研究,2007,24(10):305-307.
[3] 祝铭,李佳,陆际光.G-Chord:具有本地性和可靠性的改进型Chord模型[J].计算机应用与软件,2008,25(5):203-204.
[4] 董晓刚.Chord网络的搜索方法研究[D].山东师范大学硕士学位论文,2007,4.
[5] 姜守旭.韩希先,李建中.基于超节点的Chord系统[J].小型微型计算机系统,2007,28(2):266-270.
[6] 吕二涛.混合多层P2P网络中群的深入研究[D].西安电子科技大学硕士学位论文,2007,1.
关键词：Chord；P2P；混合的P2P结构
中图分类号：TP393文献标识码：A文章编号：1009-3044(2008)35-2559-02
Based on the Mixed Structure of the Chord System
ZENG Xiao-yun
(Guangxi University of Finance and Economics,Nanning 530003,China)
Abstract: Chord is an efficient routing algorithm of P2P, and it can locate resources quickly. However, the stability of network will be impacted when the abilities of nodes is different. The disaccord between actually physical address and node ID of Chord ring also leads to information delay. Hybrid P2P could be used to effectively manage the nodes with bad managing abilities, but its query lacks of clear objects. This paper analyses both advantages and disadvantages of them, and suggests a new Chord system based on mixed structure. It will solve the problems which involve the stability of traditional Chord, detour limitations and query efficiency of hybrid P2P.
Key words: chord;P2P;hybrid P2P
1 引言
当今，P2P搜索技术是网络研究的热点。集中式、结构化、非结构化和混合式的P2P结构各有各的优缺点。其中Chord网络模型，以它的无中心控制、可扩展强、负载平衡、高容错和使查询具有方向性使得P2P的优势更为突出，但现实环境中，Chord环上的节点之间存在很大差异性，有很多能力较弱的节点在Chord中作为独立节点的时候，也要负责系统中大量的查询和下载工作，由于自身资源的限制，它们必然会引起系统响应时间增加等问题，可能成为系统的瓶颈；而且，这些能力较差的节点可能随时出现加入或离开系统的情况，这种频繁的变迁必定增加结构化P2P系统的开销；同时，搜索网络与物理网络不一致产生查询的绕路问题。而混合结构的P2P系统通过处理能力较强的超级节点管理其他节点，能较好的管理能力弱的节点；但是混合结构的P2P系统在查询时需要通过泛洪方式来进行，使得查询盲目没有方向性，查询效率较低。如果能够造一个系统将他们两者结合起来，取长补短，应该可以克服双方的缺点。
2 基于混合结构的Chord系统模型
为了实现上述想法，我们让处理能力强、网络带宽大的超级节点作为Chord系统中的独立节点，负责管理其它的节点，并代替那些节点来负担的部分工作，就像是很多局域网的服务器作为Chord系统的节点一样，搜索仅在超级节点中进行。如下图(矩形表示超级节点，小圆圈表示普通节点)。
我们采用超级节点的IP地址前缀作为Chord模型的节点标识，并按照IP地址前缀将超级节点顺序排成Chord环。在一定程度上可以保证标识相近的超级节点在Chord网络中也是相邻的。每个超级节点都直接管理若干普通节点，它们具有与超级节点标识相等的IP地址前缀。从而改变了传统P2P系统中Chord网络节点由单个节点构成的状况,增强了网络节点的健壮性。
3 系统基本操作
每个超级节点维护一张本地客户索引表，以保存与自己IP地址前缀相同的客户机信息，还有一张信息索引表，记录该超级节点所管理的客户机和发布在它们上的信息资源关键字的hash值。
3.1 节点的加入
这一部分主要处理新结点的加入以及由此带来的网络自适应问题。
当一个普通节点A加入系统的时候，它首先找到系统中的一个超级节点B，然后比较A和B的IP地址前缀，如果前缀相同，则A作为B的一个客户机添加到以B为超级节点的域中，B修改本地客户索引表，将A的信息添加进去。这是超级节点所在域的内部操作，对外是不可见的。如果在Chord环中没有找到与之前缀相同的超级节点，则网络不允许A直接加入Chord环，只有等到A有一个自己的超级节点后，才能让该超级节点加入Chord。而域中超级节点的Chord路由表则不必进行更新，这将使得节点加入频繁的情况下Chord 系统的路由也不会受到太大影响，从而提高了系统的效率。如果加入系统的节点是超级节点，则它根据自己IP地址前缀在Chord上找到自己的位置，并调用Chord处理节点加入的函数修改其前驱和后继的指针表完成加入操作。
3.2 信息发布
当一个结点加入了Chord网络后，它就可以把它本身的资源发布出去了。在发布它的资源之前，它首先会hash它所要发布的资源，由此得到一个资源的hash值，发送给自己的超级节点，超级节点调用find successor函数，查找此hash值的所对应的超级节点，找到后资源的hash值送到这个超级结点上，保存在信息索引表中；然后超级节点在自己的本地客户索引表中随机找出一个客户机，将该客户机的信息添加到信息索引表相应的资源记录上，这样就能实现资源的发布了。
3.3 信息查询
当超级节点A所管理的客户机C想查询某个信息时，C首先把要查找的资源的关键字进行一个hash操作，得到一个hash值，发送给A，A调用find successor函数，找到此hash值的对应超级节点B，B在接收到此请求后，在自己的信息索引表中搜索存放有该信息hash值的记录，找到相应的客户机，如果未找到，发送找不到，如果找到，把找到的记录发送给结点C，此记录信息包含存储所要查找的资源，最后，结点C与这个结点建立连接通信，使资源的传送在两个结点之间进行，而不经过任何服务器。这样的查找方法使得查找具有方向性，不需要再像混合结构的系统那样进行泛洪搜索。
3.4 节点的退出
在传统的Chord 系统中, 如果节点A是Chord环上的某个节点（即超级节点），则它退出的时候，路由表中包含A的节点都将把A替换成A的后继。如果使用基于混合结构的Chord系统，Chord环上的节点是超级节点，该超级节点所管理的域中某一客户机退出不会影响Chord环中超级节点的路由表中的信息，只需超级节点的本地客户索引表中将该客户机的信息删除并将发布在它上面的信息转移到别的节点上即可。这就可以保证Chord系统在有节点频繁退出时的稳定性。当然，超级节点也有退出Chord环的可能,无论是超级节点B正常或异常退出，根据Chord的自适应能力，能将原先发布在B上的信息转移到后继节点C上。 但是，因为超级节点是某个局域网的服务器，具有较强的性能，所以一般情况下不会出现失效退出的情况。
3.5 负载均衡
如果由于发布在某个节点上的信息很热门引发了高访问量，则有可能会造成网络拥塞。为了解决这个问题，超级节点需要定期检查各个客户机的文件访问情况，挑选出一段时间内访问频率较高的文件，将他们冗余复制到自己的邻居超级节点上。
4 系统评估
由于根据IP地址对节点进行了分组,可以保证物理位置相邻的节点属于同一区域内,普通节点加入或者退出系统所引发的不稳定性远少于传统的Chord；并且信息的转储只发生在物理位置相邻的超级节点间,提高了网络的稳定性；信息的路由按照从近到远的顺序进行，减少了信息在网络上的传输距离、及传输时延,因而减少了信息在网络中传输的代价；而且因为引入了Chord环，克服了混合P2P模型泛洪的致使查询效率低下的问题。
5 下一步的工作
该论文将Chord系统和混合结构的P2P系统结合起来，在一定程度上优化了P2P系统的结构，使得系统的稳定性和可靠性及效率有了提高。但是对于安全问题和并行查找没有进行研究，这将是下一步努力的方向。
参考文献：
[1] 任小金,古志民,高志伟,段赵磊. RR-Chord:一个基于Chord 的低开销快速查询P2P系统[J].北京理工大学学报,2008,28(2):134-138.
[2] 杨明华,曹元大,张常有,于炯,谭励.Fast-chord:快速部署的P2P覆盖网络[J].计算机应用研究,2007,24(10):305-307.
[3] 祝铭,李佳,陆际光.G-Chord:具有本地性和可靠性的改进型Chord模型[J].计算机应用与软件,2008,25(5):203-204.
[4] 董晓刚.Chord网络的搜索方法研究[D].山东师范大学硕士学位论文,2007,4.
[5] 姜守旭.韩希先,李建中.基于超节点的Chord系统[J].小型微型计算机系统,2007,28(2):266-270.
[6] 吕二涛.混合多层P2P网络中群的深入研究[D].西安电子科技大学硕士学位论文,2007,1.