对等网络的拥塞研究

摘 要：对等网络的普遍应用带来了网络拥塞。从对等网络的拓扑属性研究网络拥塞，首先分析真实的Gnutella网络的流量，确定节点介数与网络拥塞之间存在关系。接着根据排队论模型从理论上给出了导致网络拥塞的临界负载与网络拓扑属性介数的公式解。最后设计拥塞控制策略，通过增加具有大介数节点的容量和这些节点间连接的方法来减轻网络拥塞。

关键词：对等网络；拓扑；网络拥塞

中图分类号： TP393.02文献标识码：A

文章编号：1001-9081(2007)04-0791-04

0 引言

近年来，随着对等计算技术的迅猛发展，出现了许多基于对等计算技术的应用，这些应用中使用人数最多的就是文件共享的对等网络，包括Gnutella、eDonkey和Kazza等。在这些文件共享的对等网络中，每个用户可以共享或者搜索一些文件。这些文件共享应用虽然给用户带来了方便，但是也大大地增加了网络的流量，给网络造成了巨大的负载。

当在网络中同时存在过多的信息需要传递时，整个网络的性能会下降，这种现象称为拥塞。拥塞与网络的动态性之间的关系不仅仅限于像因特网[1,2]这样的网络。很多网络，像电话网络、交通网络和计算机网络，在传输信息时如果出现拥塞，都会出现严重的延时。

文献[3]表明导致网络拥塞存在许多因素，例如网络节点的容量、网络连接的带宽以及网络的拓扑结构等。通过控制网络节点的服务能力以及网络带宽可以增强网络的性能。当然，除了节点容量和带宽这些物理性质外，通过优化网络的拓扑结构（逻辑性质）也可以增强网络的通信性能[4]。针对这些物理的或逻辑的性质，制定高效的通信协议对于在通信网络中出现高流量时减少网络拥塞非常重要。

许多对网络拥塞算法的改进主要是从对等网络的通信协议来进行的，很少针对对等网络的拓扑结构属性。网络中节点的介数是一个非常重要的拓扑属性，也是衡量网络通信中节点负载的一个重要指标。本文主要研究节点介数与网络拥塞之间的关系，使网络出现拥塞的网络流量的临界值是否存在，如果存在的话临界值与节点介数之间的关系，以及如何通过节点介数这个拓扑属性设计控制拥塞的高效算法。

1 介数与拥塞的关系

节点的介数就是网络中所有节点对之间通过这个节点的最短路径个数。对于任何一种网络，节点之间的通信如果都通过最短路径，那么它的通信效率将是很高的。但是，如果网络中流量特别大，而且处于这些最短路径上的节点的服务能力有限，拥塞就很有可能会出现在这些节点上。在真实网络中，可以使用近似最优的路由路径来提高整体的网络性能。例如因特网上使用的边界网关协议中就使用了类似的方法。

下面通过在Gnutella的真实拓扑上进行仿真来分析节点介数与网络拥塞之间的关系，首先介绍一下仿真过程。由Gnutella协议可知，主要只有搜索请求和搜索响应会增加Gnutella网络中的流量。还有其他一些因素如PING和PONG机制会增加网络流量，但其数量远小于搜索所带来的，为了简化仿真忽略这些因素。搜索响应是按照搜索请求的路径原路返回，所有搜索路径上节点的负载是两者的叠加。仿真实验以离散的时间步运行，每一时间步随机选择占网络节点总数百分比为f的节点发出搜索请求，有可能同一个节点连续发出搜索请求。以前发出的搜索请求按照下面的路由算法传递给邻居节点，如果某些节点匹配搜索请求，那么将搜索响应沿原路返回，每一时间步返回给一层邻居，直到到达源节点。

仿真实验将采用随机k节点路由策略。在搜索请求路由的过程中如果要考虑节点的服务能力，将会有以下两种情况:1)如果随机选择的k个节点中有的节点因服务能力已满而不能再接收请求，那么该搜索请求在本地缓存起来，到下一个时间步时再执行，如果下一次还不行，就一直缓存直到条件被满足；2)如果随机选择的k个节点中有的节点不能再接收请求，假设这些节点具有队列缓存，把这些搜索请求缓存到邻居队列中，等待在以后的时间步来依次处理这些请求。

图1给出了网络负载与搜索等待时间的关系。 f是每一时间步随机选择的发出搜索请求的节点百分比，T是仿真实验的时间步，即所有节点从发出搜索请求到收到第一个搜索结果所经过时间的平均值。首先来看f与时间T之间的关系，f可以看成是网络的流量，f越大流量就越大，造成拥塞的可能性就越大。图1中，M1和M2分别表示在搜索请求路由过程中，考虑节点的服务能力问题时的两种情况，M1对应第一种，M2对应第二种。

图片图1 网络负载与搜索等待时间的关系

如图1所示，随着f的增大，搜索请求的等待时间也随之增加，在f小于0.3时，M1和M2对应的两种方法所需的等待时间相近；当f大于0.3时，M1和M2的差别开始出现明显变化；当f处于区间段[0.3,0.9]时，搜索等待时间迅速增长；当f大于0.9，趋于1时，等待时间开始出现发散。也就是说，由于网络出现了拥塞，很多搜索请求得不到任何搜索结果。

另外M1的等待时间随f的增长要慢于M2，这是因为M1中，如果随机选择k个邻居节点的要求得不到满足，搜索请求在本地缓存起来，而不是像M2一样将搜索请求缓存到邻居节点上。当网络开始出现拥塞时，使用M2方法时显然比M1会使得网络中有更多的节点中缓存搜索请求，并且搜索等待时间是所有节点的平均值，导致了M1的等待时间随f的增长要慢于M2。

图2和图3给出了节点介数CB与搜索请求在网络中传递时被缓存的等待时间的平均值TW。这里的等待时间不同于前面的搜索等待时间，因为使用M1和M2两种方法时，搜索请求要么在本地被缓存，要么在邻居节点被缓存，这里的等待时间TW就是指所有节点缓存的搜索请求时间的平均值，这个值可以反映出网络的拥塞状态。

图2和图3分别描述了f等于0.1和0.9时等待时间与节点介数之间的变化情况，也就是系统在低负载和高负载时的变化情况。如图2所示，当系统处于低负载时，从两条曲线基本重合可以看出，使用M1和M2两种方法对等待时间与介数关系的影响不大。但是两种方法中随着介数的增大，等待时间也随之增加，这说明介数大的节点上等待时间更长，因为这些节点处于关键路径上，处理的搜索请求多于其他节点。

如图3所示，当系统处于高负载时，介数与等待时间的关系和低负载时相似。但是在介数CB大于100时，M2的变化要快于M1，原因与图1一样，因为M2会使网络中有更多的节点缓存搜索请求。另外，在介数CB小于100时，图3中的等待时间(大约为70)要大于图2所示的等待时间(大约20)。

2 网络的临界负载

本节的仿真模型基于上节所描述的模型，假设网络中存在两种类型的节点：路由节点和端节点。因为Gnutella网络中的超级节点只存储和转发搜索请求和搜索响应，可以把它看作路由节点，而把叶子节点看作端节点。定义端节点密度为ρ。网络中的流量由端节点发出的搜索请求和搜索响应结果构成，搜索请求和响应在网络中路由时，如果某个节点忙，那么将其放入这个节点队列中。假设每个节点的队列长度无限长。对于Gnutella网络和BA模型，路由方式是随机选择k个邻居节点发送请求；对于规则网络和随机网络，因为平均节点度比较小，随机选择一个邻居节点发送请求。对于端节点，每一个时间步只有占节点数百分比为f的节点产生搜索请求，也就是说整个网络只有fρ的节点产生搜索请求。

2.1 拥塞定义

定义从一个源端节点s发出搜索请求，到达一个满足该搜索请求的目的端节点d所经过的时间为延时τs,d，由于采用了k节点路由机制，那么整个网络的延迟可定义为所有这些节点对之间延时的平均，即：

(2)这里T表示仿真实验终止时的时间值，S表示集合{s，d}的大小。当网络中的流量很小并且所有节点上的队列都是空时，那么平均延时与网络包所经过的节点个数近似地成正比。随着网络流量的增加，节点上的队列开始变长，网络的平均延时也相应变大。如果网络流量继续增加，达到某个临界值fc时，一些节点的队列迅速增长，平均延时会急剧上升甚至出现发散。在这个临界负载点，网络开始拥塞。对于网络吞吐量来说也存在这样的临界现象，吞吐量定义为在每个时间步到达目的端节点的搜索请求包的个数。开始时，随着网络负载的增加，吞吐量随之增加，直到临界负载点吞吐量达到最大值。

这里Qi(t)表示时刻t节点i上的队列大小。如果网络没有出现拥塞，那么平均延时是有限值，并且网络中的平均搜索请求包个数也是有限值。超过临界负载点，拥塞节点的队列长度迅速增长，这说明搜索请求包的数目也迅速增加。

2.2 临界负载

要估算临界负载fc的值，一个比较简单的方法是考虑在时刻t所有搜索请求包距离目的端节点的长度和(称为总距离)。在网络拥塞状态，路由节点的队列中出现许多缓存的搜索请求包，那么时刻t+1和时刻t的总距离之差为D(Mt+1)-D(Mt)，这里M(t)表示时刻t网络中所有搜索请求包的个数和，D(Mt)表示在时刻t所有搜索请求包距离目的端节点的长度总和。在每个时间步，增加的搜索请求包个数为Nfρ。如果平均路径长度为，那么增加的总距离为Nfρ。另外，如果网络中每个节点的队列中的第一个请求包被处理后，那么这些请求包离目的端节点更近了一步，这表明总距离长度要减少N。

另一个估算临界负载值的方法是使用Little定理[5]。即在一个排队系统中平均客户数等于客户的平均到达时间乘以客户在系统中花费的时间[6]。也就是说，在稳定状态时，网络中传递的搜索请求包个数等于产生的搜索请求包个数：

这里Nfρ是在每个时间步队列中包的平均到达率，τ(t)表示每个包在网络中存在的时间，M(t)/τ(t)表示每个时间步传递的包的个数。在网络负载较低时，节点上的队列趋向于空并且平均延时可以用平均路径长度表示，即τ≈。当网络负载较高时，τ可以表示为平均路径长度与请求包在队列中所花的时间之和：

2.3 规则网络的临界负载

2.4 Gnutella网络的临界负载

式(11)假设了网络中所有节点上的队列大小非常近似(Q≈M*/N)，而在Gnutella和BA网络这样的无标度网络中，节点度不一样，大度节点通常有较强的处理能力，每个节点的处理能力(队列大小)不一样，大度节点往往更容易发生拥塞，从而导致网络拥塞。可以使用节点介数来表示节点的负载情况，如：

式(18)即为Gnutella网络中临界负载的公式解，证明了对等网络中临界负载和网络拓扑属性节点介数之间存在的定量关系。

如图4所示，当ρ≥0.4时，式(18)表示的理论曲线可以很好地近似表达Gnutella网络(图中实心三角)和BA网络(图中实心圆)的仿真结果。

3 Gnutella网络的拥塞控制

随着网络负载的增加，由于网络节点的服务能力有限，会导致在某些节点出现拥塞状况。由前面的分析可知，在一个网络中，那些具有大的介数的节点处于关键的通信路径上，因此这些节点往往很容易出现拥塞。当拥塞在这些节点上发生后，如果不能采用有效的方法来加以控制，那么网络包到达目的地的时间就有可能发散趋于无穷，这就会导致整个网络性能急剧下降。

式(18)表明节点介数与拥塞以及临界负载之间的重要关系，那么可以考虑从节点介数这个拓扑属性入手来控制网络拥塞。一个直观的拥塞控制方法就是提高那些介数大的节点的处理能力，使它们可以处理更多的网络包。

介数大的节点一般经过它的网络包也会越多，在下面的分析中，定义有效介数为实际通过某个节点的网络包数与网络中包的总数的比。因为介数大的节点经过的包更多一些，一个控制拥塞的直观办法就是增强这些节点的能力。研究表明，在真实网络中，最坏情况下拥塞往往是由一小部分集散节点(具有大的介数)造成，通过增强这些节点的能力并不能很快地减轻网络的拥塞。

在Gnutella网络中存在很多不同的社区组成，社区之间可以通过一些集散节点通信。以一个社区为单位来看，某些社区在网络拓扑中处于较重要的位置，经过这些社区的网络流也会更多一些，这些社区称为中心区域。那么通过增强这些中心区域中的集散节点的能力，有可能减轻整个网络的拥塞。基于此，下面详细讨论三种不同的控制拥塞的方法。

第一种方法(Alg1)是根据集散节点的介数相应地增强其处理能力，在仿真中增加其容量。节点的新容量是节点介数乘以一个容量因子a。第二种方法(Alg2)是按节点介数从大到小，选择最大的前几个节点并按照第一种方法增大其容量。第三种方法(Alg3)是根据Gnutella网络里的社区现象，增大关键社区里的集散节点的容量。在仿真中，第一种方法里的容量因子a=3；第二种方法里选择介数最大的6个节点，容量因子取a=3；第三种方法里容量因子a=3。网络节点个数N=10000。考察这几种不同方法随网络中集散节点密度d的变化情况。根据对Gnutella网络的测量[7]，仿真实验中取最大密度为3%。

表1给出了使用上述三种方法时，随密度增加，网络中搜索请求包到达目的地的百分比的变化情况。任意时刻，每个节点只能处理一个请求包，其他请求包必须放入队列等待。表1中第一列表示网络中集散节点的密度，第二列表示没有使用拥塞控制方法时的系统状态。如表1所示，显然随着集散节点密度的增加，成功的搜索请求包的百分比也相应增加，这是因为集散节点的增加缩短了网络中许多节点之间的通信路径长度。表中第三、四列分别表示第一、二种方法，两种方法均减轻了拥塞，提高了系统的性能，而且方法二要优于方法一。表中最后一列描述了第三种方法的效果，可以看出，当集散节点密度较低时(d在0.1和0.5之间时)，这种方法的效果并不明显。但随着集散节点密度的增加，这种方法减轻系统拥塞的效果明显要高于其他两种方法。但是第三种方法的缺点是它带来的性能提升是以增加许多集散节点容量为前提的。相比第二种方法，只需要增加6个具有最大介数的集散节点的容量，就可以提升10%左右的性能，并且在低密度情况下与方法三效率相当。

除了增加集散节点的容量外，还可以通过增加这些节点与其他集散节点的连接来减轻网络拥塞。下面分析在上述的第二种方法(Alg2)中使用增加集散节点之间的连接给系统带来的性能提升。第二种方法中只增加了6个集散节点的容量，那么在增加集散节点之间的连接时存在以下一些情况。可以在这6个节点之间增加1条或2条连接；可以在除6个节点之外的其他节点之间增加连接。

如表2所示，在集散节点密度为0.1%时，方法Alg2a在6个集散节点之间随机选择两个节点增加一条连接，使系统性能提高20％左右；方法Alg2b除6个节点之间增加一条连接之外，在其他节点之间随机增加一条连接，使系统性能提高也在20％左右；方法Alg2c在6个集散节点之间随机增加两条连接，使性能提高38%。方法Alg2d除在6个集散节点之间随机增加两条连接，在其他集散节点之间也随机增加两条连接，使性能提高46％。当网络中集散节点密度较大时，表2中的四种方法之间的差别比较小。

比较表1和2还可以看出，Alg2c和Alg2d均优于Alg3，即无论集散节点密度是多少，使用增加连接的方法比除Alg3外的其他两种方法的效果要好。从上面的分析可知，增加具有大的介数的节点的容量可以减轻网络拥塞，在此基础上在一些集散节点之间增加连接可以更有效地减轻拥塞。

4 结语

目前，对网络拥塞的研究计算机网络中的拥塞研究是一个热门的研究方向，但是这些研究工作很少把网络本身的拓扑结构与拥塞控制联系在一起。本文以此为出发点，深入分析了Gnutella网络拓扑与网络拥塞之间的关系。网络中不同节点在拓扑结构中所处的位置导致了它们具有不同的介数，而网络拥塞与介数之间有非常密切的关系。因为介数大的节点处于网络通信的一些关键路径上，较容易出现拥塞。随着网络负载的增加，那些具有较大介数的节点就很有可能出现拥塞现象，本文给出了网络临界负载与节点介数之间的一个公式解，这证明了临界负载和介数之间的必然联系。既然节点介数与网络拥塞之间存在必然联系，那么通过特别对待网络中介数较大的节点是一种直观的控制拥塞的办法。分析结果显示增加集散节点(具有较大的介数)的处理能力以及增加集散节点之间的连接可以有效地减轻网络中的拥塞。

本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。