您好, 访客   登录/注册

基于P2P网络搜索技术研究

来源:用户上传      作者: 王艳辉

  提要在P2P系统中,资源分散在各个节点上,节点频繁的加入或退出,P2P系统处于不断的变化之中。本文主要分析P2P网络的基本概念以及目前P2P的几种搜索技术各自的特点及性能。
  
  一、P2P技术简介
  
  (一)概念及特征。P2P是peer to peer的缩写,是一种用于不同用户PC机之间共享他们所拥有的空闲软硬件资源(处理能力、存储能力、网络连接能力、可共享文件等),可以不经过中心节点直接互相访问和交换信息的技术。它打破了传统的C/S式,在对等网络中,每个节点都具备客户机和服务器的双重特性,可以同时作为服务使用者和服务提供者。与其他网络模型相比较,P2P有分散化、可扩展性和健壮性好、高性能等优点。P2P技术目前的主要应用:文件共享与交换、协同工作、搜索引擎、分布计算、智能代理。
  (二)P2P与C/S的区别。每个对等点具有相同的地位,同时扮演着服务器和客户端两个角色,还具有路由和缓冲的功能。P2P中每个结点可以很容易加入系统中,其中任一结点可以利用网络上其他对等体的信息资源、理器周期、速缓存和磁盘空间,P2P是基于内容的寻址方式。P2P模式最主要的优点就是资源的高度利用率,所有节点的资源总和构成了整个网络的资源,整个网络可以被用作具有海量存储能力和巨大计算处理能力的超级计算机。而且对等点越多,网络性能越好,网络随着规模的增大而越稳固。信息在网络设备节点间直接流动,高速即时,降低中转服务成本。但P2P也有些不足,P2P不易管理,对等点可以随意的加入或退出,会造成网络带宽和信息存在的不稳定。
  
  二、P2P的几种搜索技术
  
  (一)P2P搜索的几种基本方式
  1、Index集中式架构。存在一个提供索引功能的节点,这个节点的索引储存了资源所在的位置信息,给定资源的某种查询条件,索引可以迅速找出符合条件的资源及其所在的位置
  2、Hash分布式结构。这种方式要求每一个资源都可以通过某种hash算法找到一个唯一的地址,发布资源时资源不是保存在本地,而是保存在这个资源hash后的地址所对应的节点中。
  3、Flooding分布式架构。这种方式要求每个节点都有查询本地资源的能力,每个节点都有d个邻居,这些节点之间通过邻居关系构成一个连通的网络。查询时通过向邻居广播查询请求来遍历整个网络进行查找。其特点就是节点覆盖率高。
  根据拓扑结构的关系可以将P2P研究分为4种形式:中心化拓扑、全分布式非结构化拓扑、全分布式结构化拓扑(也称作DHT网络)和半分布式拓扑。
  (二)基于集中式索引的搜索。这种搜索引擎的资源分布在世界各地,而作为搜索引擎的服务器(集群)只有一个或少量几个。使用该模型作为搜索方法的一个典型系统是Napster,在这样的系统中存在一个中央服务器存放其他节点所共享资源的一个索引,任何一个注册的节点都要向中央服务器传送自己所共享资源的索引,节点搜索资源时,将带有所搜索资源标识的搜索请求发送到中央服务器,中央服务器检索资源索引,告知资源请求者拥有该资源的节点的标识,然后资源请求者直接去访问资源拥有者节点下载所请求的文件或者使用其资源。这种方式并不是纯粹的P2P模型,因为它需要一个中央服务器,中央索引模型的优点在于搜索速度比较快,并且搜索全面,其他节点可以动态地将信息传至服务器,所以索引更新的速度也比较快,搜索过程中所需要的消息量小,节省了网络带宽。其缺点在于中央服务器的能力限制了节点的数量,系统的可伸缩性不够,并且一旦中央服务器失败,整个系统就无法运行,容错性不高,还可能涉及到版权、法律等方面的问题。
  (三)基于全分布式非结构化的搜索。全分布式非结构化拓扑搜索的典型方法是FLOODING。与集中目录不同,泛洪请求式没有中央目录服务器,用户的请求通过所有连接的节点传递,这些节点或者响应请求,或者在不能满足请求时,交该请求向与自己相连的其他节点广播,直到请求得到响应为止。FLOODING的模式虽然简单,但是拥有高鲁棒性、高可扩展性、简便易行等种种优点,是天生的P2P搜索方式。但是它也存在问题:就是会产生大量冗余消息,特别是当网络规模比较大,节点之间连通度比较高的时候。在实际的P2P网络中,冗余消息增加了节点处理负担,也会占用大量网络带宽。解决这个问题就是在消息中加入TTL,TTL是time-to-time的缩写,每个消息的生存时间就是TTL的值,消息每经过一次转发,TTL就减一,当TTL等于0时就表明这个消息的寿命到头了,系统就会丢弃这个消息。引入TTL机制虽然可以解决消息在环内的无限循环问题,但是带来了另一个问题:TTL的取值太小,很多查询客户端的节点就无法查到;TTL值太大,就会造成大量环内的无用消息泛滥,加重网络负担。随着网络规模的扩大,TTL值不得不增加,相应的无用消息的数量也呈指数增长。另一种解决环的思路是想办法构造一棵以查询起点为根的生成树,消息沿着可生成树发送,自然不会造成网络拥塞。为了解决消息爆炸的问题,对FLOODING方式进行的一些改进方案。1、随机漫步法,节点随机选取N个邻居节点,把请求消息转发给这些相邻结点,然后这些邻居节点将请求消息随机地向它的一个相邻节点进行转发,此可大大减少消息的产生数量。2、逐步加深法,这种搜索策略是在初始阶段,给TTL一个很小的值,如果在TTL减为0时还没有搜索到资源,则给TTL重新赋更高的值,这种策略可以减少搜索的直径。
  (四)基于全分布式DHT的搜索
  1、分布式散列表(DHT)。DHT的基本设计思想是:在P2P中使用一个足够大的ID空间,系统中的所有节点和数据均具有唯一的ID标志,每个节点和数据的ID是通过散列函数。即NodeID=Hash(Node);DataID=Hash(Data),这样系统系统中所有节点就通过NodeID映射到了ID空间,将空间分割成若干个子空间,每个节点负责一个子空间;数据保存在负责DataID所在的子空间的节点上,系统中的每个节点需要按照一定的策略维护其PX部分节点的信息表(即路由表)以便进行查找、定位和路由。
  Chord使用相容散列为每个节点和数据分配m位的ID。节点按照NodeID mod 2m的顺序连成一个环型拓扑结构。而数据k存放在第一个满足NodeID≥DataID的节点上,此节点称为该数据的后继节点,记作sucessor(k),在一个节点数N的系统中,每个节点维护其他O(log(N))个节点的信息,这些信息存储在一个称为Finger Table的路由表中,在节点n的Finger Table中,第i项包含节点s的信息。其中,s=successor(n+2i-1),1
转载注明来源:https://www.xzbu.com/2/view-413444.htm