《无结构对等网络中的搜索算法与安全机制》秦志光，罗绪成，马新新编著|(epub+azw3+mobi+pdf)电子书下载

图书名称：《无结构对等网络中的搜索算法与安全机制》

【作　者】秦志光，罗绪成，马新新编著

【页 数】 109

【出版社】 成都：电子科技大学出版社 , 2008.12

【ISBN号】978-7-5647-0036-X

【价 格】29.00

【分 类】计算机网络-安全技术-研究

【参考文献】 秦志光，罗绪成，马新新编著. 无结构对等网络中的搜索算法与安全机制. 成都：电子科技大学出版社, 2008.12.

图书目录：

《无结构对等网络中的搜索算法与安全机制》内容提要：

18170411030108

《无结构对等网络中的搜索算法与安全机制》内容试读

第一章对等网络的研究概况

本章重点概述对等网络的研究现状，主要包括对等网络的发展历程、技术优势、体系结构和对等搜索的分类。

第

1.1对等网络的发展历程

章

翠

近年来，计算机行业迅猛发展，网络边界设备（如个人电脑）性能不断提高

网

而成本却不断下降，网络基础设施的建设也日趋完善，用户的网络接入带宽不断

的

增加。网络平台性能的提高与普及促进了新的网络应用的出现，也促进了新的互

联网应用架构的出现，对等计算就是在这种条件下诞生的。对自由共享MP3音乐

究

文件的需求导致了第一个P2P文件共享系统的出现，即Napster,.Napster的最初

况

版本由Shawn Fanning和Parker于1999年6月发布，其高峰期用户达到2640万，所产生的效应导致了对P2P系统研究的热潮。由于Napster采用集中的索引服务器来提供文件搜索服务，因此，其架构上存在性能瓶颈和单点失效的风险，而且还可能带来版权方面的法律问题，Napster于2001年7月由于版权问题被迫关闭。考虑到集中索引服务的风险，需要一种完全分布的对等搜索系统，Gnutella山应运而生。Gnutella是第一种构建完全分布式对等搜索网络的协议，节点随机选择邻居互相连接，最终构成一个随机图。Gnutella采用泛洪方式传播查询请求，每个节点检查新接收到消息的生命期，如果生命期大于0，则首先对消息生命期做减1操作，然后将该消息转发给所有邻居，反之则丢弃该消息。由于泛洪方式带来的消息开销呈指数增长，因此，Gnutella的可扩展性比较差，不适合大规模应用。

2001年3月，Niklas Zennstrom等引入了另一种无需集中索引的P2P共享应用，即基于FastTrack协议2的Kazaa。Kazaa是一种层次化的无结构对等网络，根据节点在网络中所担当的角色，可以把节点划分为超级节点和叶节点。超级节点之间建立随机连接，形成一个随机图，本质上，超级节点网络就是一个无结构对等网络：叶子节点连接到一个或者多个超级节点，并将共享信息发布在所连接的超级节点。在资源搜索过程中，超级节点代理叶子节点完成资源的搜索。层次

1

化对等网络利用了节点的异构性，并且缩小了搜索网络的规模，因此，具有较高的实用价值。

针对Gnutella的不可扩展性，研究人员考虑从体系结构方面来解决可扩展的大规模对等搜索。基于分布式数据结构方面的研究成果，L.Stoica等提出了第一个分布式哈希表(DHT)Chord4之后，其他类似的DHT也被提了出来，如CAN

构对等

1、Tapestry 6、Pastry、Kademlia[等。DHT的节点之间具有确定的关系，并

且数据项和节点之间的关系也是确定的，正因为DHT的这种严格的拓扑结构要求

中

和数据分布要求，DHT又称为结构化对等网络。为了维护这种确定的拓扑结构，

需要额外的开销，特别是在高度动态的条件下，所需的开销更多，因此DHT适用

于相对稳定的应用场景。DHT具有哈希表的接口，因此，使用简单方便：通常，

法

DHT的邻居数和查询时延均为O(IogN),其中N为系统中的节点总数，因此，

具有较好的可扩展性：DHT的另一个优点是能够保证搜索的成功。

当前的研究热点之一是优化的搜索算法和新型应用。利用对等网络的特点，

与安全

可以构建低成本、高可用的大规模信息共享系统，如P2PWEB、基于P2P的WIKI

系统等。这些应用对资源搜索具有更高的要求，如支持复杂查询、更高的搜索成

制

功率（无论流行资源还是稀有资源）等。在应用方面，用户还需要更高级的资源共享模式，而不是简单的免费共享。

1.2

对等网络的技术优势

对等网络具有低成本、自组织、鲁棒性、可扩展和隐私保护等技术优势9山，

这些特点的具体说明如下：

(1)低成本

对于客户机/服务器架构，中央服务器需要大量投资以满足负载要求，而对等网络则无需大量投资，具有低成本的优势。首先，对等网络可以有效聚集大量空

闲的资源，如存储空间、网络带宽和CPU计算能力等，节点之间相互协作来完成

特定的功能，因此，其基础设施成本和维护成本分散到不同节点，避免了中央服务器的大笔投资。其次，对等网络构建灵活，不需要对网络基础设施做任何更改，任何中档个人电脑均可发起建立一个对等网络（如Bittorent).。

(2)自组织

对等网络中的节点以“ad-hoc”的方式相互连接，构成一个松散耦合的网络系统，节点自主地加入和退出系统，自主的选择邻居节点。当节点退出系统或者发生网络故障时，相关节点更新其邻居列表，自组织为新的网络系统，节点的所

2

有行为均具有自治性，不需要中央节点的协调。自组织特性降低了对等系统的维护开销，并且提高了对等系统的鲁棒性。

(3)鲁棒性

在大规模网络系统中，网络故障、节点故障的发生是不可避免的，这些故障对系统的稳定性和服务质量造成影响。在客户机服务器模式下，服务器成为整个系统的关键节点，一旦服务器发生故障，导致整个系统的崩溃。在对等模式下，系统的服务能力是节点服务能力的聚集，系统的服务能力是分散在不同的节点，而且节点提供的服务具有冗余性，因此，部分节点和网络发生故障，对整个系统的影响不大，保证了系统的稳定性和服务的可用性。对等网络还是一个动态的自

■

组织系统，节点和网络故障触发网络的重新布局，形成新的稳定系统。因此，对

第

等模式具有很高的鲁棒性。

章

(4)可扩展

传统的客户机/服务器模式，服务器的功能限制了其最大服务能力，从而决定

网

了能够支持的客户机数量。设计过大的服务能力需要更多的投资，而这些能力并

的

不一定会充分使用：相反，过小的服务能力可能导致负载过重，给后期的系统升级带来困难。与之相对，对等模式具有客户机/服务器模式不可比拟的可扩展性。

究概况

对等模式中，节点既是客户机又是服务器，节点之间相互协作实现特定的功能，新节点的加入同时给系统带来了额外的资源，如存储空间、网络带宽、文件资源、CPU计算能力等。实际对等网络的规模也说明了对等模式的可扩展性，如Gnutella网络的活跃节点数量通常超过1百万2。因此，对等模式具有高可扩展性。

(5)隐私保护

由于对等网络中的节点是自治的，除直接邻居外，其他节点无法知晓节点的加入和退出。节点之间通过相互转发消息完成系统的功能，对任意节点来说，很难区分消息的来源和目的，结合密码学手段，对等网络能够很容易地实现匿名功能31)，包括发送者匿名、接收者匿名和发送者接收者互匿，从而保护用户隐私。相对而言，客户机/服务器模式很难做到匿名性和用户隐私的保护，因为中央服务

器能够轻易获取客户机的信息，至少包括P地址等信息。

对等网络的内在优势决定其成为构建大规模互联网应用的首选架构，其中最重要的应用之一为信息共享，其基础为对等搜索。虽然集中式搜索引擎，如Google、

Baidu、Yahoo等能够提供信息搜索的能力，但集中式搜索引擎存在其自身的缺陷。首先，需要大量的基础设施投资，如高性能数据中心的建立；其次，集中式服务常常成为网络攻击的目标，导致服务的瘫痪，而对等网络具有内在的鲁棒性，单个或者部分节点的失败不会导致系统功能的下降：第三，由于商业原因，集中式搜索引擎存在内容审查和操纵搜索结果的可能，可能导致搜索结果具有倾向

3

在无结构P2P系统中构建一个分布式哈希表，分别解决各自擅长的问题。

(3)系统的层次

根据覆盖网络是否具有层次结构，P2P系统可以划分为层次化的(hierarchical)和非层次化的(non-hierarchical)。完全分布式的纯P2P系统通常是非层次化的，所有节点都处于同一层次，如Gnutella。而混合系统和部分分布式纯P2P系统属于层次化系统，如KaZaa),层次化系统充分利用了节点的异构性，能够提供更好的可扩展性，具有很高的路由效率。

1.4对等搜索的分类

◆

第

章

对等计算的典型应用之一是资源共享，包括文件共享、存储空间共享、CPU

计算资源的共享等。在这类应用中，其核心问题是如何发现（或者定位）所需的共享对象，该问题统称为资源搜索问题。一般来说，当前的资源搜索算法可以分

络

为三类：无结构P2P、结构化P2P和混合P2P。

1.4.1无结构P2P

究概况

无结构P2P中，节点之间、节点和资源之间均无确定关系。从整个系统来说，

所构成的覆盖网络的拓扑结构是一个随机图，资源在网络中随机分布，在这样的

条件下，设计有效的资源搜索算法是一个挑战性问题。在无结构P2P的发展过程

中，提出了下列主要的资源搜索算法：

(1)泛洪搜索算法

在无结构P2P网络中，每个节点只具有局部网络状态信息，即该节点的邻居

信息，无结构P2P网络的拓扑结构是一个随机图，因此，设计高效的资源搜索是

一个难题。由于无结构对等网络的特点，数据项定位只能采用盲目搜索(Blidsearch)策略，其目标在于以最小的开销把查询请求发送给尽可能多的节点。泛洪搜索是最直接的盲目搜索，对新接收到消息，节点首先根据消息的类型做本地操作（如本地关键字匹配)，然后对消息的生命期做减1操作，如果生命期大于0，则将该消息转发给所有邻居节点（消息来源节点除外），反之则丢弃该消息。泛洪机制简单、容错，适用于网络规模较小的情况。由于泛洪机制的消息量呈指数增长，因此，可扩展性差。在网络规模较大的情况下，产生大量的冗余消息，导致网络带宽的浪费，同时造成网络拥塞，恶化网络的性能。

(2)随机游走

随机游走常用于解决随机网络中的各种问题，资源搜索是其中之一。就简单

5

的随机游走而言，每走一步，节点选择一个随机邻居，将消息转发给该邻居。随机游走能够很好地适应网络的动态性，并且降低冗余消息的传播。由于随机游走采用串行方式传播查询请求，导致其查询时延较大，为了解决这个问题，QiLv

无结构

等8别提出了k随机游走，初始节点同时发起k个并行的随机游走，每个行走者之间是独立的。k随机游走是在查询冗余消息和查询时延之间的一个折中，其搜索

等

性能远远高于泛洪搜索。随机游走的另一个变体是偏好随机游走，查询消息的下

一跳选择不是随机的，而是根据邻居节点的属性来做出决策，比如选择节点度最

中

大的邻居作为下一跳。L.A.Adamic等I列提出了幂律图中基于偏好随机游走的搜索算法，充分利用高度节点在搜索中的重要角色，提高了大规模幂律网络中资源

搜索算法

搜索的性能。

(3)混合搜索

泛洪搜索和随机游走都有其优缺点，泛洪搜索能快速局部扩展，而随机游走能快速纵深渗透。就单独一种搜索方式而言，泛洪在扩展深度增加的条件下，其与

消息开销呈指数增加，但是覆盖的节点也迅速增加：随机游走在扩展深度增加的条件下，其覆盖的网络节点增加缓慢，但是消息开销小。C.Gkantsidis等2o提出制

了组合随机游走和浅层泛洪的混合搜索算法。对一个新消息，节点首先局部扩展该消息一将该消息转发给1跳或者2跳范围的所有邻居。然后，对消息的生命期做减1操作，如果该消息生命期大于0，则将该消息转发给一个随机邻居。混合搜索策略降低了搜索的消息开销和时延，同时提高了搜索的成功率。

(4)复制策略

在数据项流行度很高的条件下，泛洪搜索的性能很好，具有低时延、高成功率的性能测度，然而，自然的副本分布无法有效提高资源搜索的性能。Edith Cohen等2详细研究了无结构对等网络中的复制策略，考虑副本量和查询流行度之间的关系，提出了一致复制、正比复制和平方根复制策略。通过分析发现，一致复制和正比复制具有相同的平均搜索开销，而平方根策略具有优化的平均搜索开销。根据生日悖论的原理，R.A.Ferreira等22提出了查询率无关的复制策略，该策略利用生日悖论原理确定副本的分配模型，采用随机游走方法来实现副本的部署，该策略保证了搜索的高成功率。BubbleStorm2)是另一种查询率无关的复制策略，相似的，其副本分配源于生日悖论，并且考虑流量成本，BubbleStorm采用随机多图上的BubbleCast实现副本的部署。

1.4.2结构化P2P

基于泛洪的无结构P2P网络存在可扩展性差的问题，该问题引出了从两个方

面来提高P2P系统的搜索性能。一方面，改进泛洪算法或者提出新的消息传播算

6

···试读结束···