对等网络的网络弹性分析

1、对等网络的网络弹性分析摘 要：网络弹性研究的是网络在节点失效或被有意 攻击下所表现出来的特征。分析Gnutella网络的网络弹性， 包括对于随机攻击的容错性和对于选择性攻击的抗攻击性， 并与ER模型和EBA模型进行了对比。Gnutella网络对于随机 攻击具有很好的容错性，但是对于选择性攻击却显得脆弱。 最后对网络弹性进行了理论分析，给出了网络在出现最大集 团临界点之前的平均集团大小的公式解。关键词：对等网络；无标度；网络弹性；脆弱性中图分类号：TP393.02文献标识码：A文章编号：1001-9081(2007)04-0784-040引言在过去的40多年里，科学家习惯于将所有复杂网络看 作是

2、随机网络。随机网络中绝大部分节点的连结数目会大致 相同。1998年开展的一个描绘互联网的项目却揭示了令人惊 诧的事实：基本上，互联网是由少数高连结性的页面串联起 来的，80%以上页面的连结数不到4个，而只占节点总数不 到万分之一的极少数节点，例如门户网Yahoo和搜索引擎 Google等类似网站，却高达上百万乃至几十亿个链接。研究 者把包含这种重要集散节点的网络称为无标度网络1。具有集散节点和集群结构的无标度网络，对意外故障具 有极强的承受能力，但面对蓄意的攻击和破坏却不堪一击2。 在随机网络中，如果大部分节点发生瘫痪，将不可避免地导 致网络的分裂。无标度网络的模拟结果则展现了全然不同的 情况

3、，随意选择高达80%的节点使之失效，剩余的网络还可 能组成一个完整的集群并保持任意两点间的连接，但是只要 5%-10%的集散节点同时失效，就可导致互联网溃散成孤立 无援的小群路由器。许多复杂网络系统显示出惊人的容错特性，例如复杂通 信网络也常常显示出很强的健壮性，一些关键单元的局部失 效很少会导致全局信息传送的损失。但并不是所有的网络都 具有这样的容错特性，只有那些异构连接的网络，即无标度 网络才有这种特性，这样的网络包括WWW、因特网、社会 网络等。虽然无标度网络具有很强的容错性，但是对于那些 有意攻击，无标度网络却非常脆弱。容错性和抗攻击性是通 信网络的基本属性，可以用这两种属性来概括网络

4、弹性。对等网络技术和复杂网络理论的进展促使对现有对等 网络的拓扑结构进行深入分析。对网络弹性的认识可以使从 网络拓扑的角度了解网络的脆弱点，以及如何设计有效的策 略保护、减小攻击带来的危害。本文研究Gnutella网络的网 络弹性，并与ER模型和EBA模型进行了比较，对比不同类 型的复杂网络在攻击中的网络弹性。当网络受到攻击达到某 一个临界值时，网络中已不存在最大集团了，节点分散于许 多相互独立的小集团里，分析了这些小集团大小的分布及平 均大小，并对于攻击对网络造成的损害进行了定量的理论分 析。1网络的容错性和抗攻击性对一般网络的攻击方式可以选择去点与去边两种方式， 从选择的方式上分为随机攻击

5、和选择性攻击两种类型3，抵 抗这两种攻击的能力分别称为网络的容错能力与抗攻击能 力。随机攻击，顾名思义就是在一个网络中随机选择一些节 点，并去掉这些节点，攻击者不知道这些节点在整个网络拓 扑结构中的位置。选择性攻击才可以理解为真正意义的对网 络的攻击，比如计算机网络中的黑客攻击。对网络攻击脆弱 性的研究表明，攻击者为了最大化攻击效果，往往想挑选那 些网络中最重要的节点进行攻击，这需要事先知道整个网络 的拓扑结构，但这在真实网络环境下是不太可能的。然而， 为了深入了解不同攻击行为对网络造成的影响，往往是在知 道网络的全局拓扑的情况下对各种攻击行为进行分析。选择 性攻击使用两种不同方式：第一种攻击

6、使用基于节点度的策 略，即按顺序去掉网络中那些节点度高的节点；第二种攻击 使用基于节点介数的策略，即去掉网络中那些介数比较大的 节点。研究表明2,3，无标度网络具有很强的容错性，但是对 于基于顶点的度值或介数的选择性攻击抗攻击能力较差，对 于基于边的介数的攻击也非常敏感。文献2不仅讨论了网络 的最短距离等几何性质在去边去点攻击下的改变，还讨论了 节点度与介数等几何量的相关性。一些文献对代谢网络、食 物链网络、Email网络4和Internet5,6等网络的网络弹性进 行了深入讨论。1.1 Gnutella网络的弹性分析Gnutella是一份用于文件共享的内容分发和分布式检索 的协议。虽然该协议

7、也支持传统的客户端/中心服务器的检索 规范，但它更主要是支持点对点的，没有中心的检索。根据Gnutella的协议规范，在Gnutella网络中为了找到 需要的信息，一个节点将请求消息发送给其邻节点，邻节点 首先查找自己是否有与请求消息匹配的信息。如果存在匹配 信息则发送响应消息，然后检查请求消息中的TTL (Time To- Live)是否小于零；如果没有超过则继续转发请求消息， 否则停止转发。接下来介绍怎样通过PING、PONG命令和TTL值来探测 Gnutella网络的拓扑结构。当探测节点发送一个TTL值为2 的PING命令给其邻节点时，邻节点收到PING命令后将TTL 字段值减1,此时T

8、TL值为1,邻节点再将PING命令转发至 下一层邻节点，下一层邻节点收到PING命令后同样将TTL 值减1,此时TTL值为0，因此不再转发PING命令，而只将 PONG命令返回给探测节点。这样探测节点可以收集到与它 相邻的第二层邻节点的IP地址信息，然后探测节点又发送 TTL值为2的PING命令至第二层邻节点，这样又可以得到第 三层邻节点的信息，按照这种广度优先的搜索方式，最后就 可以得到整个网络的拓扑结构。通过分析Gnutella网络的拓 扑结构来考察网络弹性。随机性攻击的情况比较简单，这里 使用随机选择去掉某些节点来模拟真实网络环境中节点失 效的情况。任何一个网络的互联性从本质上可以由它的

9、网络直径 和平均最短路径长度来描述。网络直径描述了网络中两个节 点相互通信的能力：直径越小那么两点间期望的通信长度就 越短。一个网络就算拥有大量的节点也可能具有很小的网络 直径，比如拥有80亿个节点的WWW网络，它的网络直径 大约为19。设想当一个完整的网络（即所有节点都是连通的）在受到 攻击后，网络的拓扑结构势必会受到很大的影响，以至网络 中的某些边也会消失，从而导致整个网络分裂成很多相互独 立的子图，这些子图之间没有连接。反映到真实网络情况就 是说某些节点之间的通信无法进行，从而使网络的通信受到 影响。因此，下面将基于最大集团，网络紧中心性和网络直 径三个拓扑属性来分析Gnutella网络

10、的网络弹性。最大集团 指的是相对大小，即最大集团中的节点数与网络中所有节点 数的比值。紧中心性定义为：d(x,y)，这里d(x,y)表示节点x 和y之间的最短路径长度，U是所有节点的集合。在试验时，为了观察随机失效给网络带来的影响，这里 随机选择去掉网络中的一小部分节点，用百分比f表示。同 样对于模拟选择性攻击，首先去掉网络中节点度最高的节点， 然后按照节点度降序的规则选择被去掉的节点。图1一图3 描述了最大集团相对大小、网络紧中心性和网络直径在随机 攻击(Failure)、基于度的攻击(DAttack)和基于介数的攻击 (BAttack)三种情况下的变化过程。在对Gnutella网络拓扑进

11、行探测时，经过大量的数据分析发现，在Gnutella网络中超 级节点所占的比例大约是3.3%，这种节点是使用基于度的攻 击方法时的目标节点，因此上述三个图中x轴的变化范围限 定在0,0.05。如图1一图3所示，Gnutella网络对于随机攻击显示 出很好的容错性：最大集团的相对大小变化非常缓慢，到去 掉4%左右的节点时，S大小仍然在0.85左右，见图1；网 络的紧中心性在整个过程基本上保持不变，只有微小的波动， 见图2；网络直径的变化也不明显，在区间0, 0.04内保持不 变，到Uf为5%时才增加1，见图3。然而，Gnutella网络在基于度的攻击和基于介数的攻击时却显得非常脆弱。如图1所示，

12、对于基于度的攻击(DAttack)，当f趋于2% 时，最大集团相对大小S趋向于0,这说明这时网络中已经 不存在最大子图，大部分节点都分散在很多小的子图里，或 者某些节点已经成为孤立的节点；基于介数的攻击(BAttack) 时，情况要比DAttack时好一些，当f趋于3.3%左右时S才 趋于0，这说明在Gnutella网络中，基于度的攻击比基于介数 的攻击对于网络的危害更大一些。如图2所示，对于基于度的攻击(DAttack)，f趋于1%时 网络的紧中心性达到最小值0.145，对于基于介数的攻击 (BAttack)，f趋于3%时网络紧中心性达到最小值0.145,这里 的情况跟选择性攻击对最大集团的

13、影响相似，基于度的攻击 比基于介数的攻击危害性要大一些。图2中另外一个有趣的现象是，当紧中心性达到最小值 后，在两种攻击情况下，紧中心性又开始逐渐增大。这是因 为网络紧中心性是针对网络中的最大集团来计算的，攻击刚 开始时，网络中的最大集团大小相比整个网络节点数目来说 较大，攻击发生后去掉了一些关键节点导致某些关键路径也 从网络中去掉，影响了节点间通信的平均最短路径，确切地 说是增大了平均最短路径，从而导致紧中心性的减小；然而 随着攻击的增加，网络中的最大集团大小越来越小，即网络 被分成了许多独立的小的子图，而这时最大集团中的平均最 短路径也会变小，集团中的节点间通信平均来说会更快，相 应地紧中

14、心性会增大。图3给出了攻击对网络直径的影响，在大图的坐标范围 内无法看到网络直径的变化过程，所以放大了区间0, 001， 如小图所示。图3表明两种攻击对网络直径的影响很大，与 前面两种情况类似，基于度的攻击对网络直径的影响比基于 介数的攻击要大。综上所述，Gnutella网络对于随机攻击具有很强的容错 性，而对选择性攻击却显得比较脆弱；在遭受攻击时测量网 络得到的相关参数表明，基于度的攻击均比基于介数的攻击 对网络造成的危害性更大。1.2 ER模型和EBA模型的网络弹性分析复杂网络的理论研究始于20世纪60年代，著名数学家 Erdfis和Renyi提出了 ER模型，一个由n个节点组成的随机 图

15、中，每两个节点被一条边连接起来的概率为p。鉴于实际 网络的情况，Barabasi和Albert的第二个关于无标度网络的 机制模型考虑了加点、加边和重连三种事件，扩充了原有的 BA模型，即EBA（Extended日入）模型。下面通过ER模型和 EBA模型来比较与Gnutella网络弹性的异同。图4一图6分 别描述了在ER模型中随机攻击和两种选择性攻击对最大集 团大小、网络紧中心性和网络直径的影响。与Gnutella网络 不同，对于ER模型，随机攻击和选择性攻击对于网络的影响基本上是相同的，正如图中所绘的曲线基本是重叠的。如图4,对于基于介数的攻击，当f趋于32%时，S趋于 0;而对于基于度的攻击

16、和随机攻击，当f趋于38%时，S趋 于0，这说明基于介数的攻击危害性要大一些。如图5，对 于基于介数的攻击，当f趋于15%时，CC趋于最小值；对于 基于度的攻击和随机攻击，当f分别趋于17%和18%时，CC 趋于最小值。基于介数的攻击使网络紧中心性下降得更快， 比其他两种攻击更加具有危害性。如图6，这几种攻击对于 网络直径的影响也跟上面的情况类似，影响由大到小的顺序 是：基于介数的攻击，基于度的攻击，随机攻击。图7一图9分别描述了在EBA模型中随机攻击和两种选 择性攻击对最大集团大小、网络紧中心性和网络直径的影响。 从图中曲线的变化可以看出，EBA模型与Gnutella网络具有 比较大的相似性

17、。如图7,对于基于介数的攻击，当f趋于22%时，S趋于 0；而对于基于度的攻击和随机攻击，当f趋于24%时，S趋 于0。如图8,对于基于介数的攻击，当f趋于9%时，CC趋于 最小值；对于基于度的攻击，当f趋于11%时，CC趋于最小 值。EBA模型与ER模型的一个相似之处是它们对于两种不同 的选择性攻击具有相同的反映，从图中BAttack和DAttack的 变化快慢可知，基于介数的攻击比基于度的攻击危害更大，这刚好跟Gnutella网络中的情况相反。因为从f变化范围可 以看出，Gnutella网络中大度节点（ultrapeer）所占比例要小于 EBA模型中大度节点所占比例，并且小度节点（叶子节点

18、）非 常依赖于大度节点，通常小度节点只与三个左右的ultrapeer 相连，小度节点之间基本上没有连接，这样就使得网络在受 到基于度的攻击时，会比受到基于介数的攻击更加脆弱。2网络弹性的理论模型通过试验分析了 Gnutella网络在随机攻击和选择性攻击 发生时，网络的三种拓扑属性的变化情况，并ER模型和EBA 模型做了对比。最大集团大小，网络紧中心性和网络直径这 三种拓扑属性当中，对于实际系统最有意义最直观的就是最 大集团大小。当网络受到攻击后，一般最关心的是这个网络 最大范围内有多少节点仍然可以相互通信。从另一个方面考 虑，当网络受到攻击达到某一个临界值（f趋于某个值），整个 网络已经不存在

19、最大集团了，网络节点都分散于许多相互独 立的小集团里，那么这些小集团大小的分布情况及平均大小 是多少？这些对于攻击对网络造成损害的定量分析非常重 要，下面将进行理论分析。在分析攻击临界点发生后集团大小的分布和集团平均 大小时，为了便于理论分析，可以按如下思路来考虑。在攻 击临界点发生后，网络被分散成许多独立的小集团，由于攻 击的方法是去掉网络中的某些节点，那可以反过来思考网络 的形成过程。开始时网络由一些单个节点组成，随着其他节 点的加入和边的形成，网络会逐渐演化生长，到某一个临界 点时网络中的最大集团开始形成，这里的临界点与攻击使得 最大集团消失的临界点是相同的，只是它们的表述方式不同 而已。因此可以用这种方法来分析最大集团形成前(即临界点 之前)网络中集团的大小分布和集团的平均大小。在一个网络图中随机选择一条边，设想沿着这条边指向 它的一个端点并且通过这个端点可以到达其他节点，就称通 过这条随机选择的边的一端可达的节点集合为一个集团。令 H1(x)为这些集团大小分布的生成函数。沿着一条随机选择的 边，与它相连的可能只是一个单一的节点，没有其他边与这 个节点相连；也可能是有多条边连接的一个节点，每条边又 连接其他的集团，这些集团的大小分布