论文部分内容阅读
摘要：介绍了P2P的概念和特点，分析了P2P搜索与传统搜索的不同之处，并从结构角度出发剖析和比较了P2P四种不同的搜索技术，给出了它们的优缺点。
关键词：P2P；网络搜索
中图分类号：TP393文献标识码：A文章编号：1009-3044(2008)24-1144-02
Analysis of P2P Networks Search Method
HUANG Xi-ni
(Dept. of Computer Science,Zhanjiang Pedagogical Academy,Zhanjiang 524037,China)
Abstract:In this paper,we firstly introduce the concept and characteristics of P2P, analysis of the difference between the P2P search and the traditional search, and to analysis and compare of the four different P2P search technology, given their advantages and disadvantages.
Key words: peer-to-peer;web searching
1 引言
近几年来，计算机对等网（peer-to-peer）技术的迅猛发展，P2P的研究得到了国内外学术界和商业组织的广泛关注，并被《财富》杂志称为改变因特网未来的四大新技术之一。目前，P2P研究中的一个主要问题就是搜索问题。P2P搜索技术发展迅速，给传统的web搜索技术带来了很大的冲击。
2 P2P概念和特点
对等计算（Peer-to-Peer，简称P2P）[1]， P2P是一种分布式网络，在这种网络中所有的节点是对等的（称为对等点），各节点具有相同的责任与能力并协同完成任务。对等点之间通过直接互连共享信息资源、处理器资源、存储资源甚至高速缓存资源等，无需依赖集中式服务器或资源就可完成。P2P网络和与当今广泛使用的客户端/服务器（C/S）的在通信模式和网络结构上有很大的不同，C/S模式中服务器是网络的控制核心，而P2P模式的节点则具有很高的自治性和随机性。如下图是P2P模式与C/S模式的比较:
图2 P2P模式网络结构
P2P网络结构无中心化，走向网络边沿，使得网络上的闲置的网络资源得以充分利用，在一定程度上解决了C/S模式中扩散性差、负载不均衡、健壮性差等方面的缺点，但P2P也带来了管理难，搜索相对复杂的缺点。
3 P2P搜索与传统搜索的比较
P2P领域一个很重要的研究就是搜索研究，P2P网络中的搜索和现在使用的搜索引擎搜索技术有很大的差别。在P2P网络中，用户将各自拥有的资源共享出来，搜索无需要通过Wed服务器，不受文档格式与宿主设备限制，一台设备的消息对应N台，搜索的范围将会在几秒钟内以几何级数增长，可以达到传统搜索无法比拟的搜索深度。P2P搜索促进了搜索的多元化和权利、义务的分解，使每一台机器都参与到了搜索过程中去，由普通的接受服务的客户端向可以提供服务的一方转变。在一定程度上弥补传统搜索技术不足。
4 P2P的网络搜索模型
P2P的检索方式取决于系统的资源发布模式。P2P搜索技术从结构角度出发可以分为四类：集中式P2P网络的搜索技术，结构化P2P网络的搜索技术，非结构化P2P网络的搜索技术，混合式P2P网络的搜索技术。
4.1 集中式P2P网络的搜索技术
P2P集中索引模型是中心化拓扑的网络，整个系统由目录服务器和客户端（对等体）构成。目录服务器由一台或多台有高性能的服务器承担，主要负责所有活动客户端共享资源的管理，提供资源查询服务。对等体加入网络时向目录服务器注册关于自身的信息（其名称、地址、资源和元数据），当对等体的资源发生变化时，比如资源的增加，修改，删除等，也向索引服务器提供更新消息，服务器据此修改缓存的资源索引信息。对等体根据服务器返回的消息与对应拥有资源的对等体建立连接，并在对等体之间传输文件。这类网络的代表系统有Napster、eMule，如图3，Napster网络模型，P5查找文件S2并下载。
这种模式实现了文件查询与文件传输的分离，有效地节省了中央服务器的带宽消耗，减少了系统的文件传输延时，因此查询效率高、对等体负载均衡、系统可维护性好。但是由于采用了中心化拓扑结构，所以对索引服务器的处理能力和带带宽的要求很高、安全性要求比较高，易遭受Dos（拒绝服务攻击）等攻击而瘫痪。P2P系统本质上所不可避免的两个问题：索引服务器法律版权纠纷问题和资源浪费的问题。集中式P2P网络，在管理方面有一定的优势，但是当网络扩展，维护的成本会很大的提高，这种形式不适合大型网络使用，这种网络的搜索形式只适合小型网络。
4.2 非结构化P2P网络的搜索技术
图4 Gnutella（分布式P2P）网络结构
非结构化P2P网络不存在中心目录服务器，所有的服务及相关信息完全散布在各个P2P结点中，因此其最显著的特点就是“完全去中心化” [3]。这是一种纯的P2P网络，每个peer既可以作为客户端又可以作为服务器，并且它和相邻的Peer有相同的能力。搜索技术主要采取的是泛洪（Flooding）。非结构化P2P网络的典型代表就是Gnutella，采取基于随机图的泛洪算法，如图4所示。每个结点都将自己收到的消息转发出去，这种查找方式使得网络流量的几何式增长，一般通过TTL（Time To Live）机制来控制查询的深度。节点的查询消息时设置TLL初值，如TLL=4，消息传播一次TLL减1，TLL=0时停止传播，控制消息永远循环。但随着联网节点的不断增多，网络规模不断扩大，通过这种Flooding方式定位对等点的方法将造成网络流量急剧增加，从而导致网络中部分低带宽节点因网络资源过载而失效。
4.3 结构化P2P网络的搜索技术
结构化P2P网络是纯的P2P网络，采用分布式哈希表（Distributed Hash，Table简称DHT）结构，使用分布式哈希表索引对资源和节点进行搜索。在结构化P2P网络中，客户端主机称为节点，文件数据称为对象。首先，将搜索空间对应到一个散列（Hash）空间，对各个节点（基于节点的IP地址）也进行相应散列如N=HASH（IP），每个节点各负责一部分散列空间。当一个节点发布一个资源（例如文件），需要对该资源的唯一标识（如文件名）进行散列K=HASH（文件的名字），而根据该散列值可以确定负责管理该资源的节点。代表软件有Chord，CAN，Tapestry， Pastry等。如图5为Chord的搜索过程。Chord诞生于美国的麻省理工学院。它的目标是提供一个适合于P2P环境的分布式资源发现服务，它通过使用DHT技术使得发现指定对象只需要维护O（logN）长度的路由表。chord的主要贡献是提出了一个分布式查找协议，该协议可将指定的关键字（Key）映射到对应的节点（Node）搜索时源节点的请求发送到与资源标识符最接近的节点上。收到查询请求的节点如果发现自身存储了被查询的信息，可以直接回应源节点，不在则将请求转发到与键值最接近的节点上。这样的过程一直持续到找到相应的节点为止。搜索过程实际上就是折半查找的过程。
DHT类结构能够自适应结点的动态加入/退出，有着良好的可扩展性、鲁棒性、结点ID分配的均匀性和自组织能力。由于重叠网络采用了确定性拓扑结构，DHT可以提供精确的发现。
4.4 混合式P2P网络的搜索技术
在混合P2P网络中，选择性能较高（处理、存储、带宽等方面性能）的节点作为超级节点（Super-peer），在各个超级节点上存储了系统中其他部分节点的信息，发现算法仅在超级节点之间转发，超级节点再将查询请求转发给适当的端点。其代表就是KaZaA，其搜索过程如图6所示。混合式P2P网络搜索的优点是性能、可扩展性较好，较容易管理，但对超级节点依赖性大，易于受到攻击，容错性也受到影响，实现上比较困难，为了能够利用这种模式的优点，需要提供能够有效组织对等体间关系的搜索网络，这里所说的组织关系，包括超级节点间的组织模式、客户对等体与超级节点间的组织模式、超级节点间的负载平衡等。
4.5 四种网络搜索技术性能分析
综上所述， P2P网络搜索的四种性能比较可归纳为下表1。
表1 P2P网络性能比较
5 P2P搜索技术研究的挑战
P2P搜索技术中最重要的研究成果应该是基于Small World理论的非结构化搜索算法和基于DHT的结构化搜索算法。但是P2P在实际的应用中，以下因素影响了搜索的效率：
5.1 网络节点异质性
物理网络中影响路由的一些因素开始影响P2P发现算法的效率。P2P由于客户机/服务器模式在Internet和分布式领域十几年的应用和大量种类的电子设备的普及，如手提电脑、移动电话或PDA。这些设备在计算能力、存储空间和电池容量上差别很大。在通信基础方面，P2P必须提供在现有硬件逻辑和底层通信协议上的端到端定位（寻址）和握手技术，建立稳定的连接。实际网络被路由器和交换机分割成不同的自治区域，体现出严密的层次性。
5.2 网络的波动程度
网络波动（Churn）包括结点的加入、退出、失败、迁移、并发加入过程、网络分割等。网络的波动的影响节点发现算法的效率。
5.3 复查查询的需求
复杂的查询，如关键词、内容查询等，DHT精确关键词映射的特性阻碍了DHT在复杂查询方面的应用。
P2P搜索方法一直是研究的热点。但是与传统的搜索技术还有很大的差距，研究搜索速度快、成本低、分布性好、支持多关键词搜索、带宽要求小的P2P搜索方法，可以使搜索技术大步向前迈进，走出搜索形式多样化的道路
6 小结
本文对P2P网络模式与传统的c/s模式的分析比较，主要研究了P2P的四种网络模式和其搜索方法的剖析，对P2P将来的应用进行了展望。
参考文献：
[1] 张炤峰.P2P搜索技术研究[D].沈阳.沈阳工业大学,2007:8-10.
[2] 杨天路,刘宇宏,张文,等.P2P网络技术原理与系统开发案例[M].北京:人民邮电出版社,2007:37-63.
[3] 杨再晗,陈建二,王建新.P2P计算研究现状及关键技术[J].现代电子技术,2004(1):1.
[4] 《电信新技术新业务新要点解读丛书》编写组.对等网络（P2P）[M].北京:人民邮电出版社,2007:17-35.
关键词：P2P；网络搜索
中图分类号：TP393文献标识码：A文章编号：1009-3044(2008)24-1144-02
Analysis of P2P Networks Search Method
HUANG Xi-ni
(Dept. of Computer Science,Zhanjiang Pedagogical Academy,Zhanjiang 524037,China)
Abstract:In this paper,we firstly introduce the concept and characteristics of P2P, analysis of the difference between the P2P search and the traditional search, and to analysis and compare of the four different P2P search technology, given their advantages and disadvantages.
Key words: peer-to-peer;web searching
1 引言
近几年来，计算机对等网（peer-to-peer）技术的迅猛发展，P2P的研究得到了国内外学术界和商业组织的广泛关注，并被《财富》杂志称为改变因特网未来的四大新技术之一。目前，P2P研究中的一个主要问题就是搜索问题。P2P搜索技术发展迅速，给传统的web搜索技术带来了很大的冲击。
2 P2P概念和特点
对等计算（Peer-to-Peer，简称P2P）[1]， P2P是一种分布式网络，在这种网络中所有的节点是对等的（称为对等点），各节点具有相同的责任与能力并协同完成任务。对等点之间通过直接互连共享信息资源、处理器资源、存储资源甚至高速缓存资源等，无需依赖集中式服务器或资源就可完成。P2P网络和与当今广泛使用的客户端/服务器（C/S）的在通信模式和网络结构上有很大的不同，C/S模式中服务器是网络的控制核心，而P2P模式的节点则具有很高的自治性和随机性。如下图是P2P模式与C/S模式的比较:
图2 P2P模式网络结构
P2P网络结构无中心化，走向网络边沿，使得网络上的闲置的网络资源得以充分利用，在一定程度上解决了C/S模式中扩散性差、负载不均衡、健壮性差等方面的缺点，但P2P也带来了管理难，搜索相对复杂的缺点。
3 P2P搜索与传统搜索的比较
P2P领域一个很重要的研究就是搜索研究，P2P网络中的搜索和现在使用的搜索引擎搜索技术有很大的差别。在P2P网络中，用户将各自拥有的资源共享出来，搜索无需要通过Wed服务器，不受文档格式与宿主设备限制，一台设备的消息对应N台，搜索的范围将会在几秒钟内以几何级数增长，可以达到传统搜索无法比拟的搜索深度。P2P搜索促进了搜索的多元化和权利、义务的分解，使每一台机器都参与到了搜索过程中去，由普通的接受服务的客户端向可以提供服务的一方转变。在一定程度上弥补传统搜索技术不足。
4 P2P的网络搜索模型
P2P的检索方式取决于系统的资源发布模式。P2P搜索技术从结构角度出发可以分为四类：集中式P2P网络的搜索技术，结构化P2P网络的搜索技术，非结构化P2P网络的搜索技术，混合式P2P网络的搜索技术。
4.1 集中式P2P网络的搜索技术
P2P集中索引模型是中心化拓扑的网络，整个系统由目录服务器和客户端（对等体）构成。目录服务器由一台或多台有高性能的服务器承担，主要负责所有活动客户端共享资源的管理，提供资源查询服务。对等体加入网络时向目录服务器注册关于自身的信息（其名称、地址、资源和元数据），当对等体的资源发生变化时，比如资源的增加，修改，删除等，也向索引服务器提供更新消息，服务器据此修改缓存的资源索引信息。对等体根据服务器返回的消息与对应拥有资源的对等体建立连接，并在对等体之间传输文件。这类网络的代表系统有Napster、eMule，如图3，Napster网络模型，P5查找文件S2并下载。
这种模式实现了文件查询与文件传输的分离，有效地节省了中央服务器的带宽消耗，减少了系统的文件传输延时，因此查询效率高、对等体负载均衡、系统可维护性好。但是由于采用了中心化拓扑结构，所以对索引服务器的处理能力和带带宽的要求很高、安全性要求比较高，易遭受Dos（拒绝服务攻击）等攻击而瘫痪。P2P系统本质上所不可避免的两个问题：索引服务器法律版权纠纷问题和资源浪费的问题。集中式P2P网络，在管理方面有一定的优势，但是当网络扩展，维护的成本会很大的提高，这种形式不适合大型网络使用，这种网络的搜索形式只适合小型网络。
4.2 非结构化P2P网络的搜索技术
图4 Gnutella（分布式P2P）网络结构
非结构化P2P网络不存在中心目录服务器，所有的服务及相关信息完全散布在各个P2P结点中，因此其最显著的特点就是“完全去中心化” [3]。这是一种纯的P2P网络，每个peer既可以作为客户端又可以作为服务器，并且它和相邻的Peer有相同的能力。搜索技术主要采取的是泛洪（Flooding）。非结构化P2P网络的典型代表就是Gnutella，采取基于随机图的泛洪算法，如图4所示。每个结点都将自己收到的消息转发出去，这种查找方式使得网络流量的几何式增长，一般通过TTL（Time To Live）机制来控制查询的深度。节点的查询消息时设置TLL初值，如TLL=4，消息传播一次TLL减1，TLL=0时停止传播，控制消息永远循环。但随着联网节点的不断增多，网络规模不断扩大，通过这种Flooding方式定位对等点的方法将造成网络流量急剧增加，从而导致网络中部分低带宽节点因网络资源过载而失效。
4.3 结构化P2P网络的搜索技术
结构化P2P网络是纯的P2P网络，采用分布式哈希表（Distributed Hash，Table简称DHT）结构，使用分布式哈希表索引对资源和节点进行搜索。在结构化P2P网络中，客户端主机称为节点，文件数据称为对象。首先，将搜索空间对应到一个散列（Hash）空间，对各个节点（基于节点的IP地址）也进行相应散列如N=HASH（IP），每个节点各负责一部分散列空间。当一个节点发布一个资源（例如文件），需要对该资源的唯一标识（如文件名）进行散列K=HASH（文件的名字），而根据该散列值可以确定负责管理该资源的节点。代表软件有Chord，CAN，Tapestry， Pastry等。如图5为Chord的搜索过程。Chord诞生于美国的麻省理工学院。它的目标是提供一个适合于P2P环境的分布式资源发现服务，它通过使用DHT技术使得发现指定对象只需要维护O（logN）长度的路由表。chord的主要贡献是提出了一个分布式查找协议，该协议可将指定的关键字（Key）映射到对应的节点（Node）搜索时源节点的请求发送到与资源标识符最接近的节点上。收到查询请求的节点如果发现自身存储了被查询的信息，可以直接回应源节点，不在则将请求转发到与键值最接近的节点上。这样的过程一直持续到找到相应的节点为止。搜索过程实际上就是折半查找的过程。
DHT类结构能够自适应结点的动态加入/退出，有着良好的可扩展性、鲁棒性、结点ID分配的均匀性和自组织能力。由于重叠网络采用了确定性拓扑结构，DHT可以提供精确的发现。
4.4 混合式P2P网络的搜索技术
在混合P2P网络中，选择性能较高（处理、存储、带宽等方面性能）的节点作为超级节点（Super-peer），在各个超级节点上存储了系统中其他部分节点的信息，发现算法仅在超级节点之间转发，超级节点再将查询请求转发给适当的端点。其代表就是KaZaA，其搜索过程如图6所示。混合式P2P网络搜索的优点是性能、可扩展性较好，较容易管理，但对超级节点依赖性大，易于受到攻击，容错性也受到影响，实现上比较困难，为了能够利用这种模式的优点，需要提供能够有效组织对等体间关系的搜索网络，这里所说的组织关系，包括超级节点间的组织模式、客户对等体与超级节点间的组织模式、超级节点间的负载平衡等。
4.5 四种网络搜索技术性能分析
综上所述， P2P网络搜索的四种性能比较可归纳为下表1。
表1 P2P网络性能比较
5 P2P搜索技术研究的挑战
P2P搜索技术中最重要的研究成果应该是基于Small World理论的非结构化搜索算法和基于DHT的结构化搜索算法。但是P2P在实际的应用中，以下因素影响了搜索的效率：
5.1 网络节点异质性
物理网络中影响路由的一些因素开始影响P2P发现算法的效率。P2P由于客户机/服务器模式在Internet和分布式领域十几年的应用和大量种类的电子设备的普及，如手提电脑、移动电话或PDA。这些设备在计算能力、存储空间和电池容量上差别很大。在通信基础方面，P2P必须提供在现有硬件逻辑和底层通信协议上的端到端定位（寻址）和握手技术，建立稳定的连接。实际网络被路由器和交换机分割成不同的自治区域，体现出严密的层次性。
5.2 网络的波动程度
网络波动（Churn）包括结点的加入、退出、失败、迁移、并发加入过程、网络分割等。网络的波动的影响节点发现算法的效率。
5.3 复查查询的需求
复杂的查询，如关键词、内容查询等，DHT精确关键词映射的特性阻碍了DHT在复杂查询方面的应用。
P2P搜索方法一直是研究的热点。但是与传统的搜索技术还有很大的差距，研究搜索速度快、成本低、分布性好、支持多关键词搜索、带宽要求小的P2P搜索方法，可以使搜索技术大步向前迈进，走出搜索形式多样化的道路
6 小结
本文对P2P网络模式与传统的c/s模式的分析比较，主要研究了P2P的四种网络模式和其搜索方法的剖析，对P2P将来的应用进行了展望。
参考文献：
[1] 张炤峰.P2P搜索技术研究[D].沈阳.沈阳工业大学,2007:8-10.
[2] 杨天路,刘宇宏,张文,等.P2P网络技术原理与系统开发案例[M].北京:人民邮电出版社,2007:37-63.
[3] 杨再晗,陈建二,王建新.P2P计算研究现状及关键技术[J].现代电子技术,2004(1):1.
[4] 《电信新技术新业务新要点解读丛书》编写组.对等网络（P2P）[M].北京:人民邮电出版社,2007:17-35.