非结构化P2P环境下高效资源发现策略.pdf

摘 要 基于无结构化 P2P 的资源发现策略可以分成盲目搜索和已知搜索两大类, 资源查找的命中率,查询带来的网络流量是衡量资源发现策略的标准。盲目搜 索算法采用洪泛式或随意游走的方式能够提高资源查找的命中率,但是其代价 是网络流量的增加;已知搜索算法根据资源查找的历史记录有目的把查询导向 昀可能命中资源的路径,这样能够在保证 资源命中率的同时,减少网络流量, 代价是增加了节点空间资源的开销。 本文提出的两段路由索引表更新策略,它是一种利用副本节点的已知资源 发现策略。副本节点是 P2P 网络是从资源原始拥有节点完整获取资源的节点。 当一个节点想要获取一个资源时,他可以从资源原始拥有节点获取,也可以从 副本节点获取。像 Freenet 是把资源复制到资源成功查询路径上所有的节点来提 高查询效率,这条路径上所有节点都是副本节点。但是 P2P 文件共享系统一般 都是查询节点在下载资源后才变成副本节点,这样做在减少资源空间的同时也 符合用户行为。副本节点周围路径上没有记录导向副本节点的历史信息,所以 开始阶段只能通过盲目搜索才能发现副本节点。本文提出两段机制,第一段是 根据 APS 和路由算法来实现更新,第二阶段是节点成为副本节点之后反向的更 新路由表。这样,既可以提高资源查找的命中率,也能够减少网络流量。当前 的搜索算法都是集中在第一阶段,而没有后继的第二阶段。 P2P 文件共享系统中动态文件的出现将导致副本节点的副本资源会过时, 因此副本节点需要及时更新副本。这样做既是为自身更新,同时也是为查找到 副本节点的搜索节点能够获得较新的资源。因此本文提出了基于 Bloom 过滤器 推模式和基于 AIMD的拉模式的副本一致性维护的混合模式。 根据本文提到的改进算法做了相应仿真实验,证明两段路由索引更新机制 在资源发现效率上有一定的提升,同时副本一致性维护混合模式也减少了没有 接收到更新消息的节点数目。 本文的主要工作包括:1. 提出了两段路由索引表更新机制 现有的非结构化 P2P 的已知搜索算法都集中在第一阶段,也就是搜索的阶 1 段,没有考虑到查询节点在下载资源后会变成副本节点。这样副本节点为查询 做贡献只能通过盲目搜索才能实现,之后副本节点才能出现在的路由索引表中, 所以本文提出了在查询节点变成副本节点之后马上反向更新查询路径上的路由 索引表,这就是第二阶段的路由索引表的更新模式。 2实现了副本一致性维护的系统模型 副本节点中的副本资源是非静态文件的情况下,就存在资源可能发生更新 的情况。这样 P2P 网络中的副本资源就会产生不一致性,因此副本节点需要及 时更新副本资源,以保证整个网络中的副本的一致性,为依靠副本的已知查询 策略服务。 关键字: P2P;资源发现;路由索引表; Bloom过滤器;一致性维护; Gnutella 2 Abstract The resource discovery strategy based on the unstructured P2P networks which include blind search and informed search, the rate of successful search and the network traffic are used to measure the algorithms of search. blind search that uses flooding search or random walk to enhance the rate of hit result but the network traffic of search is increased at the same time; informed search algorithms forward the query to the nodes which have the resources with high probabilistic based on the history query records, in this way, the informed search algorithms can ensure the rate of successful search result and reduce the network traffic at the same time, and its price is the increase of storage space in peersIn this paper, we proposal two-phase route indices updated mechanism for infor