网络存取级拥塞控制-计算机网络原理

网络存取（Network Access，NA）级拥塞控制的目标是根据网络的整体拥挤状况来限制外部向网络的信息输入量，从而达到控制拥塞的目的。网络的整体拥挤状况可以通过对网络内部拥挤的测量获得，这些测量可以是局部的（如入口结点缓冲器的占有率）、全局的（如整个网络所具有的总的可用缓冲器数）或是有选择的（如通向一个给定目的结点的道路拥挤状况）。拥挤的状况在网络的存取点被测定（或是向网络存取点报告），而且被用来调节外部对网络的存取信息量。

网络存取级拥塞控制与跳跃级（HL）和入口出口级（ETE）拥塞控制的区别在于：NA控制是通过阻止外部的信息量来防止整个内部缓冲器的拥挤，HL控制是通过限制某指定存储转结点的存取来防止局部拥挤和存储转发死锁，而ETE控制则是通过限制某指定的源结点到目的结点对之间的信息流量来防止拥挤，尤其是目的结点拥挤和重装缓冲器死锁。但这些区别并不是非常明显的，常常相互借用，相互影响，乃至混合在一起。例如HL和ETE都可以具有某些NA的拥塞控制特征。

常见的NA拥塞控制方法有：Isarithmic法，它是通过发行固定数目许可证来防止全局拥挤的方法；输入缓冲器限制法，它是通过对存储于每个结点上的输入分组数目加以限制来防止局部拥挤的方法；阻止报文分组法，它是有选择的拥挤测量法，是建立在传递由拥挤结点返回到源结点的特殊控制报文分组基础上的一种方法，该特殊的分组就称为阻止报文分组（Choke Packet）。下面简要介绍第一、第三种方法，有关第二种方法的细节请参考有关著述。

1、Isarithmic法

因为网络拥挤的基本原因是网络中存储了过多的分组，所以从直观上讲，合理防止拥挤的基本原理应该是在任意时刻都对网内流动的分组总数加以限制，Isarithmic法正是这一原理的实施方法。

Isarithmic这个术语是从“ISO（均匀）”和“arithmatic（算法）”派生出来的，所以Isarithmic法又被称为均匀算法。它是建立在“许可证”概念基础上的，即允许一个分组进入网络的前提是它必须获得一个许可证。网络开始备有许多许可证，每个结点也各存有几个，主机必须获取许可证后才能向网络投入分组。主机获取的许可证既可以从结点的许可证池中取得，也可以在网络中游动的许可证经过本结点时取得。当分组传到目的结点时，所获得的许可证将被投入结点许可证池中，或被投入网络中让其继续游动。由于整个网络的许可证数目是一定的，因此投入到网中的最多分组数也是一定的，从而从整体角度保证了网络不发生拥塞。

这种方法存在的主要问题是：

①尽管此法可从整体角度保证子网不会拥塞，但无法保证某一CCP不会被瞬间大量到达的分组搞得应接不暇；

②许可证的分配十分困难。为了防止因本地的CCP四处搜寻许可证而使新产生的报文被长时期地延迟，许可证必须在子网内均匀分布，使得各个CCP都有几个，但为使文件能高速传输，又不希望CCP长时间寻找以获得足够多的许可证。如将许可证集中管理可使大量的用户得到满足，但也会带来一些难以解决的问题，如脆弱性、许可证回收困难等等。可取的折衷方案是给CCP一个许可证的贮集地即许可证池，在其中贮集一定数量的许可证，使传送时分组可以迅速发出，而不必等待较长时间；或给CCP从网中抓取游动许可证保留一定的时间。许可证池的大小是一个需仔细考虑的值，英国NPL实验室对18个结点的网络进行的试验表明：许可证池的规模的大小为3时最优。要注意的是，多余的许可证在网内的游动本身就是子网的一个负担；

③无论何种原因，如果许可证损坏，如传送错误、CCP出错、被拥塞的CCP丢弃等，网络的整体传输能力就会减小，而要确定在网络中游动的许可证的数量是很困难的。

顺便提一下，许可证在网内游动的路由算法可采用随机走动法。(www.xing528.com)

2、阻止报文分组法

阻止报文分组法（Choke Packet，CP）是建立在链路和通路拥挤的概念基础上的。如果链路的利用率在一定时限内按某种方法计算超过了一个给定的阈值，则认为该链路拥挤。如果任一链路拥挤，则通过该链路的通路也就拥挤。把通路拥挤的消息在网络中沿原有道路反向传送，以使每一个收到该消息的结点通过减少发往该通路的信息量来避免拥挤进一步发生、加剧。换句话说，阻止报文分组法是在拥挤发生到一定程度时，引发一种机制，以防进一步拥挤。这样，既可以尽量少地降低网络的吞吐量，又不致引起拥塞。

阻止报文分组法的方案之一是：每一个CCP都监测它的每一条输出线路的利用率，而每一线路都用一实数u（0≤u≤1.0）表示此线路当前的利用率。为了使u有较准确的估计值，须周期性地求出线路利用率的瞬时值f，并对u进行更新

u=au+（1-a）f

其中，f=1，表示此刻线路被占用，f=0，表示此刻线路未被占用；a（0≤a≤1）为遗忘参数，a=0，表示完全遗忘从前的记忆，a=1则表示一点也不遗忘从前的记忆。这样，当0＜a＜1时，u值随着探测的次数逐渐地遗忘以前的记忆，而得到目前的线路状态。当u值达到并超过某一阈值时，此输出线路就处于告警状态，也就是说此链路拥挤。

一个数据分组到达某结点后，将了解它所要输出的链路是否处在告警状态，如果是，将导致以下的动作：

①本结点向源主机发送一阻止报文分组CP，并把该数据分组的目的地址放入CP中。同时将该数据分组加上特殊标记后继续前送，使它不会再引起回发CP，CP分组本身也不会引发CP；

②源主机收到CP后，将CP中指明的目的站的分组流量减少X%，由于已经发出的分组会继续引发回送CP，故丰机将在一段时间内不再理睬CP；

③源主机经过一段时间后再查CP，若仍有，则进一步减少流量，若没有了，可逐步增加流量。

这种方法实际上是一种负反馈的方法，在出现拥挤之前并不限制流量，出现拥挤之后才开始限制流量。阻止报文分组法还有许多其它方案，例如不用线路利用率而用队列长度作为引发信号，此处不再详述。