peer-to-peer介绍最近几年，peer-to-peer(对等计算，简称p2p)迅速(编辑修改稿)

peer-to-peer介绍最近几年，peer-to-peer(对等计算，简称p2p)迅速(编辑修改稿)内容摘要：

研究者证明 O(logN)甚至O(logN/loglogN)的平均路径长度也不能满足状态变化剧烈的网络应用 的需求。 新的搜索算法受到这种折衷关系制约的根本原因在于 DHT 对网络拓扑结构的确定性认识。 2. 语义查询和 DHT 的矛盾 现有 DHT 算法由于采用分布式散列函数，所以只适合于准确的查找，如果要支持目前Web 上搜索引擎具有的多关键字查找的功能，还要引入新的方法。 主要的原因在于 DHT 的工作方式。 基于 DHT 的 P2P 系统采用相容散列函数根据精确关键词进行对象的定位与发现。 散列函数总是试图保证生成的散列值均匀随机分布，结果两个内容相似度很高但不完全相同的对象被生成了完全不同的散列值，存放到了完全随机的两个结点上。 因此， DHT 可以提供精确匹配查询，但是支持语义是非常困难的。 目前在 DHT 基础上开展带有语义的资源管理技术的研究还非常少。 由于 DHT 的精确关键词映射的特性决定了无法和信息检索等领域的研究成果结合，阻碍了基于 DHT 的 P2P 系统的大规模应用。 二、非结构化 P2P 网络的搜索技术 1. 小世界模型 (Small World)对 P2P 搜索技术的影响 非结构化 P2P 搜索技术一直采用洪泛转发 (Flooding)的方式，与 DHT 的启发式搜索算法相比，可靠性差，对网络资源的消耗较大。 最新的研究从提高搜索算法的可靠性和 寻找随机图中的最短路径两个方面展开。 也就是对重叠网络 (Overlay Network)的重新认识。 其中，小世界模型特征和幂规律证明实际网络的拓扑结构既不是非结构化系统所认识的一个完全随机图，也不是 DHT 发现算法采用的确定性拓扑结构。 实际网络体现的幂规律分布的含义可以简单解释为在网络中有少数结点有较高的 “度 ”，多数结点的 “度 ”较低。 度较高的结点同其他结点的联系比较多，通过它找到待查信息的概率较高。 Small world 模型的特性：网络拓扑具有高聚集度和短链的特性。 在符合 Small World特性的网络模型 中，可以根据结点的聚集度将结点划分为若干簇 (Cluster)，在每个簇中至少存在一个度最高的结点为中心结点。 大量研究证明了以 Gnutella 为代表的 P2P 网络符合 Small World 特征，也就是网络中存在大量高连通结点，部分结点之间存在 “短链 ”现象。 图 2 Gnutella 重叠网络的 Small World 现象 因 此， P2P搜索算法中如何缩短路径长度的问题变成了如何找到这些 “短链 ”的问题。 尤其是在 DHT 搜索算法中，如何产生和找到 “短链 ”是搜索算法设计的一个新的思路。 Small World特征的发现和引入会对 P2P 搜索算法产生重大影响。 2. 非结构化 P2P 搜索算法 按照搜索策略，可以分为两大类：盲目搜索和启发式搜索。 盲目搜索通过在网络中传播查询信息并且把这些信息不断扩散给每个节点。 通过这种洪泛方式来搜索想要的资源。 而启发式搜索在搜索的过程中利用一些已有的信息来辅助查找过程。 由于信息搜索对资源的存储有一些知识，所以信息 搜索能够比较快的找到资源。  Flooding 搜索方法 在最初的 Gnutella协议中，使用的是 Flooding方法，在网络中，每个节点都不知道其他节点的资源。 当它要寻找某个文件，把这个查询信息传递给它的相邻节点，如果相邻节点含有这个资源，就返回一个 QueryHit 的信息给 Requester。 如果它相邻的节点都没有命中这个被查询文件，就把这条消息转发给自己的相邻节点。 这种方式像洪水在网络中各个节点流动一样，所以叫做 Flooding 搜索。 由于这种搜索策略是首先遍历自己的邻接点，然后再向下传播，所以又称为宽度 优先搜索方法（ BFS）。 如图所示：搜索的节点一开始 TTL=3，它每传播一次 TTL 减 1，如果 TTL 减到 0 还没有搜索到资源，则停止。 如果搜索到资源则返回目标机器的信息以用来建立连接。 在搜索过程中可能出现循环，但是由于有 TTL 控制，所以这个循环不会永远进行下去，当 TTL=0 的时候自然结束。 图 3Flooding 方法示意图  ModifiedBFS 方法 这种方法是在宽度优先方法 Flooding上面作了一定修改。 跟 Flooding 搜索方法不同，搜索源只是随机的选取一定比例的相邻节点作为查询信息的发送目标，而不是发送给所有相邻节点。 相比于 Flooding 方法来说，是以时间换取空间的有效尝试。  Iterative Deepening 搜索方法 迭代递增是 Flooding 方法的改进，策略循环递增 TTL（ Time to Live）值，这个值用来控制Flooding 的搜索深度。 跟 Flooding 搜索方法给 TTL赋一个较大的值不同，这种方法在初始阶段，给 TTL 一个很小的值，如果在 TTL减为 0，还没有搜索到资源，则给 TTL重新赋更高的值。 这种策略可以减少搜索的半径，但是在最坏的情况下，延迟很大，如果 P2P 网络内重复资源丰富，这种方法在不影响搜索质量的基础上将减少网络内的查询流量，在有的文献中亦称为 Expanding Ring（扩展环搜索）。 图 4 Iterative Deepening 过程  Random Walk 搜索方法 : 在随机漫步中，请求者发出 K 个查询请求给随机挑选的 K 个相邻节点。 然后每个查询信息在以后的漫步过程中直接与请求者保持联系，询问是否还要继续下一步。 如果请求者同意继续漫步，则又开始随机选择下一步漫步的节点，否则中止搜索。 图 5 Random Walk 效果图  Gnutella2 的搜索方法 Gnutella2 建立 SuperNode,它存储着离它最近的叶子节点的文件信息，这些 SuperNode,再连通起来形成一个 Overlay ，它首先从它连接的SuperNode的索引中寻找，如果找到了文件，则直接根据文件所存储的机器的 IP 地址建立连接，如果没有找到，则 SuperNode 把这个查询请求发给它连接的其他超级节点，直到得到想要的资源 ,KaZaa， POCO 等都是基于这种超级节点的思想。 图 6 Gnutella2 的 SuperNode 节点图  基于移动 Agent 的搜索方法 移动 Agent 是一个能在异构网络中自主地从一台主机迁移到另一台主机，并可与其他 Agent或资源进行交互的程序。 Agent非常适合在网络环境中来帮助用户完成信息检索的任务。 现在意大利的一些研究人员在移动 Agent 结合 P2P方面做了一些 前沿的研究，其中的一些想法，就是通过在 P2P 软件中嵌入 Agent 的运行时环境。 当有节点需要搜索的时候，它发送一个移动 Agent 给它相邻的节点，移动 Agent 记录着它的一些搜索的信息。 当这个 Agent到达一台新的机器上，然后在这个机器上进行资源搜索任务，如果这台机器上没有它想要的资源，则它把这些搜索的信息传给它的邻节点，如果找到资源，则返回给请求的机器。  Query Routing 方法 这种方法是一种启发式搜索方法。 首先每个 Peer 给本节点的资源做索引，并且纪录相邻节点的资源信息，当查询到达的时候，可以查 询路由表直接定位到资源的位置，而不需要再次转发查询信息。 图 7Query Routing 方法 三、 P2P 搜索技术研究的挑战 P2P 搜索技术中最重要的研究成果应该是基于 Small World 理论的非结构化搜索算法和基于 DHT 的结构化搜索算法。 尤其是 DHT 及其搜索技术为资源的组织与查找提供了一种新的方法，在近年来的 P2P 研究领域成为热点。 随着 P2P系统实际应用的发展，物理网络中影响路由的一些因素开始影响 P2P 发现算法的效率。 一方面，实际网络中结点之间体现出较大的差异，即异质性。 由于客户机 /服务器模式在 Inter 和分布式领域十几年的应用和大量种类的电子设备的普及，如手提电脑、移动电话或 PDA。 这些设备在计算能力、存储空间和电池容量上差别很大。 另外，实际网络被路由器和交换机分割成不同的自治区域，体现出严密的层次性。 另一方面，网络波动的程度严重影响搜索算法的效率。 网络波动（ Churn）包括结点的加入、退出、失败、迁移、 并发加入过程、网络分割等。 DHT 的发现算法如 Chord、 CAN 等都是考虑网络波动的最差情况下的设计与实现。 由于每个结点的度数尽量保持最小，这样需要响应的成员关系变化的维护可以比较小，从而可以快速恢复网络波动造成的影响。 但是每个结点仅有少量路由状态的代价是发现算法的高延时，因为每一次查找需要联系多个结点，在稳定的网络中这种思路是不必要的。 同时，作为一种资源组织与发现技术必然要支持复杂的查询，如关键词、内容查询等。 尽管信息检索和数据挖掘领域提供了大量成熟的语义查询技术，由于 DHT 精确关键词映射的特性阻碍了 DHT 在复杂查询方面的应用。 P2P 搜索方法一直是研究的热点。 一些新的搜索方法不断的涌现，但是，在资源搜索效率和准确定位方面还有很大的改善空间，以及基于 P2P 技术的搜索引擎要达到现在集中式的搜索引擎 Google，百度这样广泛使用还需要一段长时间的努力。 PeertoPeer 的应用研究、面临的问题与前景展望 一、国外公司与研究机构研究情况 近年来，随着 Napster、 KaZaa、 BT、 eMule这样的基于 P2P 技术的文件共享软件在 Inter上迅速传播， P2P 技术在国际国内都引发了研究的新热潮。 国外开展 P2P 研究的学术团体主要包括 P2P工作组（ P2PWG）、全球网格论坛 (GGF)以及各高校的研究小组。 P2P工作组成立的主要目的是希望加速 P2P 计算基础设施的建立和相应的标准化工作。 P2。