拥塞控制新算法：试算平衡

夏长会

(河南财政金融学院 工程经济学院，河南 郑州 451464)

0 引言

所谓拥塞是指网络中对某一资源的需求超过了该资源所能提供的可用部分，导致网络性能变坏的情况，用关系式表示为：对资源的需求>可用资源[1]。在网络中，若许多资源需求同时发出，就会产生网络拥塞，网络的性能就会明显变坏，网络吞吐量[2]将急速下降。因此，拥塞控制的意义不言而喻。有效地控制拥塞，将大大提高网络的运营效率和性能，使网络资源更好地实现共享。

为了避免网络拥塞，学者们提出了许多行之有效的办法。Jacobson在认为TCP(transmission control protocol)的滑窗机制是有效的同时，提出了慢开始(slow-start)[3]、拥塞避免(congestion avoidance)算法[4]。其后在此基础上增加了快速重传算法[5]和快速恢复算法[6];于是形成了目前广泛使用的TCP拥塞控制策略的4个核心组成部分。以后又出现了TCP改进版本,如New-reno、SACK、Vegas等[7]。这些算法尽管使网络传输情况大大改善，也增大了网络的吞吐量，但存在诸多不足，主要表现在以下3个方面。

1)资源分配的不公平性[8]。 由于Internet是一种尽力而为(best effort) 的服务模式,大家争用有限的资源。源端的目标就是尽可能多地占有带宽。按照传统拥塞控制算法，当网络出现拥塞时,路由器开始丢弃包。实际上大多数包的丢失是由于路由器将包丢弃而造成的,而并非由于包损坏。因此当包发生丢弃时,发送端认为网络出现了拥塞,需要按拥塞避免算法将发送窗口减半,以减轻网络拥塞。在多个TCP连接共享一个网络瓶颈时,这些TCP连接争用有限的带宽,使得各个连接占有的带宽不等,甚至少数几个连接占完了所有带宽,而多数连接无法通过网络传递数据，造成严重失衡。

2)极易破坏数据流的平滑性以及与QOS(quality of service)的结合[9]。传统的拥塞控制算法，使TCP每发现一个报文丢失就将窗口减半，发送方发送速率产生剧烈的抖动，极大地破坏了数据流的平滑性,导致接收者感受到服务质量的显著下降，尤其在实时媒体流应用逐渐增多的今天, 传统算法的不足更加突出。

3)网络整体效率低下。在传统算法下，以牺牲整体效率(efficiency) 为代价[10]来减少网络拥塞发生。由于传统的拥塞控制算法不能从根本上解决拥塞控制问题,某种程度上加重了拥塞情况的发生，在实际运用中常遇到许多难以逾越的障碍,网络性能无法得到充分的提高或明显的改善。

针对上述传统拥塞控制算法的不足，根据网络中对某一资源的需求与该资源所能提供的可用部分之间的关系，本文借鉴会计学中试算平衡理论，提出了试算平衡算法，可有效地控制拥塞，实现资源分配的公平匹配，保持数据流传输的平滑性，可提高网络运营的整体效率、稳定性和安全性(security)。

1 拥塞控制新算法——试算平衡

所谓试算平衡，就是通过按一定比例控制各部分资源的使用程度，从而限制网络对资源的需求，以实现全局资源的供需平衡，其实质是实现网络各部分资源的匹配，也就是说综合考虑网络中各资源要素，通过对资源需求的再分配，实现网络资源供给与需求的相对平衡，进而对拥塞实现更好的控制，以达到避免拥塞的目的。

1.1 将网络上各资源分别按容量从大到小，或速率从高到低进行分层排序

设a为节点缓存容量，b为链路容量，c为处理机速率，d为其他，排序情况见表1，其中

1)a1>a2> …>an-1>an，a1为网络节点的最大缓存容量，an为节点的最小缓存容量；

2)b1>b2>…>bn-1>bn，b1为链路最大容量值，bn为链路最小容量值；

3)c1>c2>…>cn-1>cn，c1为处理机速率最高值，cn为处理机速率最低值；

4)d1>d2> …>dn-1>dn，d1为其他类网络资源的最大值，dn为其他类网络资源的最小值。

表1 网络资源分层排序Tab.1 Hierarchical sorting of network resource

1.2 求网络资源基础平衡点

分别以an、bn、cn、dn为标准，测定出与其相匹配的其他资源的值，分别设为a、b、c、d，其匹配情况见表2。

表2 网络资源匹配情况测算Tab.2 Matching calculation of network resource

1)求出标准值与其匹配值之和，分别用a′、b′、c′、d′表示，则

a′=an+b1+c1+d1，b′=bn+a1+c2+d2，c′=cn+a2+b2+d3，d′=dn+a3+b3+c3。

2)比较a′、b′、c′、d′的大小，取最小值为基础平衡点的值(设为T)。

Min{a′，b′，c′，d′},若a′最小，则T=an;若b′最小，则T=bn;若c′最小，则T=cn;若d′最小，则T=dn。

1.3 根据网络资源基础平衡点，确定并计算“余地”资源比例

试算平衡在强调资源平衡配置的同时，设有“余地”资源。所谓“余地”资源是指在不影响网络正常运行的情况下，将一定比例的资源留作备用，以防网络运行中不测事件发生拥塞的资源。

设an为基础平衡点，则与其相匹配的其他资源值为b1、c1、d1。

1)求出bn、cn、dn与an匹配值的差,分别设其差为m1、m2、m3，则m1=an-b1，m2=cn-c1，m3=dn-d1。

2)求出m1、m2、m3占其对应资源最小值的百分比，分别设为β1、β2、β3，则β1= (m1/bn)×100%，β2=(m2/cn) ×100%，β3= (m3/dn)×100%。

3)取β1、β2、β3的最大值作为“余地”资源的比例(设为δ)，即δ=max{β1，β2，β3}。

由上述计算可以看出，“余地”资源的大小，要看资源各类别最高层与最低层的差别程度，又要看资源间的匹配程度：若最高层与最低层差别越大，则“余地”资源所占的比例就越大，否则就越小。若各资源间的匹配程度越高，则“余地”资源所占的比例就越小；否则，若资源间的匹配程度越低，“余地”资源所占比例就越大。

当m1=m2=m3=0时，“余地”资源的比例δ=0，也就是说，这时网络资源是完全匹配的。

事实上，由于受经济、政治、地域、环境等诸多因素的影响，无论是现在还是将来，网络的资源配置，都将存在着不匹配的问题，只是通过人们的共同努力，不匹配的程度会变得越来越低。采用试算平衡虽然可以实现网络上的虚拟平衡，但网络运行中仍存在许多不可测因素，因此，在资源平衡配置的同时，留出“余地”资源十分必要。其作用是一旦节点发生拥塞，发生拥塞处根据需求自动启用“余地”资源，化解拥塞。拥塞解除后，资源自动恢复原状态下工作。

1.4 根据基础平衡点及确定的“余地”资源比例，计算网络各资源的使用程度

假设an为基础平衡点，“余地”资源为δ，则不同层次资源使用的比例如表3；若设bn为基础平衡点，“余地”资源为δ时，各资源使用比例见表4。同样也可求出cn、dn为基础平衡点，“余地”资源为δ的各资源使用的比例。

表3 基于基础平衡点an网络资源使用程度测算Tab.3 Using degree of network resource measurement based on basic equilibrium point an

表4 基于基础平衡点bn网络资源使用程度测算表Tab.4 Using degree of network resource measurement based on basic equilibrium point bn

1.5 根据计算出各资源的使用程度，确定对资源的需求的抑制程度

假设an为基础平衡点，“余地”资源为δ，则不同层次资源需求的抑制比例如表5；若设bn为基础平衡点，“余地”资源为δ时，各资源需求的抑制比例如表6。同样也可求出cn、dn为基础平衡点，“余地”资源为δ，对不同层次资源的需求的抑制比例。

表5 基于基础平衡点an 各资源需求抑制比例计算表Tab.5 Calculation of resource demand suppression ratio based on basic equilibrium point an

表6 基于基础平衡点bn各资源需求抑制比例计算表Tab.6 Calculation of resource demand suppression ratio based on basic equilibrium point bn

由此可以看出，采用试算平衡算法，基础平衡点的值越小，网络上可用的各种资源利用程度越低，对资源的需求抑制程度就越高；否则，基础平衡点的值越大，资源的利用程度就越高，对资源的需求抑制程度就越低。

当T=a1=a2=…=an时，则节点缓存容量的利用可达到最高程度，对该资源的需求的抑制程度为0；当T=b1=b2=…=bn时，则链路容量的利用可达到最高程度，对该资源的需求抑制程度为0。

2 仿真运算

假定目前网络各资源容量或速率状况如表7，其中an=128，bn=100，cn=1.1，具体运算步骤如下。

1)设经过测定，分别以an、bn、cn为标准，相匹配的其他资源值如表8。

2)求基础平衡点T。a1=128+75+0.9=203.9；b1=100+192+1.5=293.5；c1=1.1+260+85=346.1。Min{a1，b1，c1}=Min{203.9，293.5，346.1 }=230.9，因为a1最小，所以基础平衡点T=an=128。

3)求“余地”资源的比例。求出与bn、cn、与an匹配值的差，m1=100-75=25，m2=1.1-0.9=0.2；求出各差值(m1、m2)占其对应标准值(bn、cn)的百分比，δ1=(m1/bn)×100%=(25/100)×100%=25%，δ2=(m2/cn)×100%=(0.2/1.1)×100%=18%。比较δ1、δ2的大小，取最大值作为“余地”资源的比例。δ= Max{δ1，δ2}=Max{25%,18%}=25%。

4)计算当前状态下，各类不同层次的资源使用比例见表9。

5)确定对网络各资源的需求的抑制比例，见表10。

表7 网络资源容量速率情况表Tab.7 Capacity rate situation of network resource

表8 标准匹配资源值测算表Tab.8 Value measurement of standard matching resource

表9 当前状态下各类不同层次的资源使用比例测算表Tab.9 Calculation of utilization ratio of various resources under the current state

注：1.128×(1-25%)/512×100%=18.75%；2.128×(1-25%)/480×100%=20%；3.1-25%=75%；4.75×(1-25%)/1 000×100%=5.625%；5.75×(1-25%)/900×100%=6.25%；6.75×(1-25%)/100×100%=56.25%；7.0.9×(1-25%)/40×100%=1.69%；8.0.9×(1-25%)/35×100%=1.93%；9.0.9×(1-25%)/1.1×100%=61.4%

表10 网络资源需求抑制比例测算表/%Tab.10 Proportion calculation of network resource demand restraint/%

计算表明，目前情况下，由于各资源的值层次落差很大，若要建立网络的虚拟平衡，不但要保留相当大的“余地”资源的比例(高达25%)用于化解拥塞，而且对各资源的需求的抑制程度较高，资源利用程度较低。低层次资源除节点缓存容量利用程度达到75%，其余均不到62%,而对其需求的抑制程度均在25%以上。高层次资源利用程度更低，均不及20%，而对其资源需求的抑制程度均在80%以上。由此可见，在实现网络上的虚拟平衡条件下，缩小资源各层次的落差，减少资源的层次数是解决问题的关键。只有这样，才能缩小“余地”资源的比例，提高资源的利用程度，从而降低对资源需求的抑制比例。而要做到这一点，除限制低容量资源的利用外，网络资源统一配置十分必要。

3 结束语

这种拥塞控制新算法，首先通过网络各资源按照一定标准进行排序；然后根据各资源匹配值，求出网络资源的基础平衡点；根据网络资源的基础平衡点，确定并计算出“余地”资源的比例；根据基础平衡点来确定“余地”资源比例，计算出各网络资源的使用程度，进而确定对资源需求的抑制程度。

采用此算法，网络运行中资源各部分供给与需求相对平衡，再加上设有 “余地” 资源以防不测，网络将更少发生拥塞，甚至不发生拥塞；由于在网络中实现了资源的基本匹配和相对公平，网络性能十分稳定，出现数据丢失和信息错传的概率极小，可以提供高质量的信息传输；在一定程度上也遏制了“黑客”对网络的恶意攻击，对网络安全起到积极的保护作用；就网络系统的整体资源而言，将获得较高的运营效率和较好的经济效益。但在各资源匹配程度较差的情况下，会导致一些高性能资源的利用程度较低。若通过协议方式或者统一配置资源的方式，缩小各资源性能配置上的差异，则可以解决这一问题。