摘要：本文首先阐述了计算机网络中拥塞的定义、拥塞产生的原因以及经常提起的拥塞控制的定义；流量控制的定义和控制方式；拥塞控制和流量控制的关系；中间阐述了目前使用最多的拥塞控制算法FIFO算法和RED算法，最后提出了这两个算法的改进思想。
关键字：拥塞控制，流量控制，IP拥塞算法改进
一、概述
1。拥塞定义
当网络中存在过多的数据包时，网络的性能就会下降，这种现象称为拥塞。在网络发生拥塞时，会导致吞吐量下降，严重时会发生“拥塞崩溃”现象。一般来说，在网络负载的增加导致网络效率的降低的时候，就会发生拥塞崩溃。Floyd总结出拥塞崩溃主要包括以下几种：传统的崩溃、未传送数据包导致的崩溃、由于数据包分段造成的崩溃、日益增长的控制信息流造成的崩溃等。
2。拥塞产生的原因
网络产生的拥塞的根本原因在于用户提供给网络负载大于网络资源容量和处理能力，表现为数据包延时增加、丢弃概率增大、上层应用系统性能下降。拥塞产生的直接原因有以下三点： 存储空间不足。几个输入数据流共同需要同一个输入端口，在这个端口就会建立排队，假如没有足够的存储空间，数据包就会丢弃，对突发数据流更是如此。增加存储空间在一定程度上可以缓解这一矛盾，但假如路由器有无限存储量，拥塞只可能变得更坏，而不是更好。因为网络里的数据包经过长时间排队后才通过路由器完成转发，会浪费网络资源，加重网络拥塞。
带宽容量不足，低速链路对高速数据流的输入也会产生拥塞。根据香农信息理论，任何信道带宽最大值为C＝Blog2。所有信源发生的速率R必须小于或等于信道容量C，假如R ＆gt；C，则在理论上无差错传输就是不可能的。所以在网络低速链路处就会形成带宽瓶颈，当其满足不了所有信源带宽要求时，网络就会发生拥塞。
处理器能力弱、速度慢，也能引起拥塞。假如路由器的CPU在执行排队缓存，更新路由表等功能时，处理速度跟不上高速链路，也会产生拥塞。同样，低速链路对高速CPU也会产生拥塞。
3.拥塞控制的定义
拥塞控制就是采用某种策略或机制，保持网络工作在正常的状态下，也就是使网络经常工作在崖点左侧的区域内。若一种控制机制使得网络工作在膝点四周，该方法称之为拥塞避免；若一种控制机制是的网络工作在崖点或崖点以后的网络回复至膝点前后，该方法称之为拥塞恢复。
因此拥塞控制策略包括拥塞避免和拥塞控制这两种不同的控制机制。拥塞避免是“预防”机制，它的目标是避免网络进入拥塞状态，使网络运行在高吞吐量、低延迟的状态下。拥塞控制是“恢复”机制，它用于把网络从拥塞状态中恢复出来。
4.拥塞控制方法
①缓冲区预分配法。该法用于虚电路分组交换网中。在建立虚电路时，让呼叫请求分组途经的节点为虚电路预先分配一个或多个数据缓冲区。若某个节点缓冲器已被占满，则呼叫请求分组另择路由，或者返回一个"忙"信号给呼叫者。这样，通过途经的各节点为每条虚电路开设的永久性缓冲区(直到虚电路拆除)，就总能有空间来接纳并转送经过的分组。此时的分组交换跟电路交换很相似。当节点收到一个分组并将它转发出去之后，该节点向发送节点返回一个确认信息。该确认一方面表示接收节点已正确收到分组，另一方面告诉发送节点，该节点已空出缓冲区以备接收下一个分组。上面是"停一等"协议下的情况，若节点之间的协议允许多个未处理的分组存在，则为了完全消除拥塞的可能性，每个节点要为每条虚电路保留等价于窗口大小数量的缓冲区。这种方法不管有没有通信量，都有可观的资源(线路容量或存储空间)被某个连接占有，因此网络资源的有效利用率不高。这种控制方法主要用于要求高带宽和低延迟的场合，例如传送数字化语音信息的虚电路。 ②分组丢弃法。该法不必预先保留缓冲区，当缓冲区占满时，将到来的分组丢弃。若通信子网提供的
是数据报服务，则用分组丢弃法来防止拥塞发生不会引起大的影响。但若通信子网提供的是虚电路服务，则必须在某处保存被丢弃分组的备份，以便拥塞解决后能重新传送。有两种解决被丢弃分组重发的方法，一种是让发送被丢弃分组的节点超时，并重新发送分组直至分组被收到；另一种是让发送被丢弃分组的节点在尝试一定次数后放弃发送，并迫使数据源节点超时而重新开始发送。但是不加分辨地随意丢弃分组也不妥，因为一个包含确认信息的分组可以释放节点的缓冲区，若因节点元空余缓冲区来接收含确认信息的分组，这便使节点缓冲区失去了一次释放的机会。解决这个问题的方法可以为每条输入链路永久地保留一块缓冲区，以用于接纳并检测所有进入的分组，对于捎带确认信息的分组，在利用了所捎带的确认释放缓冲区后，再将该分组丢弃或将该捎带好消息的分组保存在刚空出的缓冲区中。
③定额控制法。这种方法在通信子网中设置适当数量的称做"许可证"的特殊信息，一部分许可证在通信子网开始工作前预先以某种策略分配给各个源节点，另一部分则在子网开始工作后在网中四处环游。当源节点要发送来自源端系统的分组时，它必须首先拥有许可证，并且
每发送一个分组注销一张许可证。目的节点方则每收到一个分组并将其递交给目的端系统后，便生成一张许可证。这样便可确保子网中分组数不会超过许可证的数量，从而防止了拥塞的发生。
5.流量控制
定义：流量控制用于防止在端口阻塞的情况下丢帧，这种方法是当发送或接收缓冲区开始溢出时通过将阻塞信号发送回源地址实现的。流量控制可以有效的防止由于网络中瞬间的大量数据对网络带来的冲击，保证用户网络高效而稳定的运行。
两种控制流量的方式：
1，在半双工方式下，流量控制是通过反向压力（backpressure）即我们通常说的背压计数实现的，这种计数是通过向发送源发送jamming信号使得信息源降低发送速度。
2，在全双工方式下，流量控制一般遵循IEEE 802.3X标准，是由交换机向信息源发送“pause”帧令其暂停发送。
有的交换机的流量控制会阻塞整个lan的输入，这样大大降低了网络性能；高性能的交换机仅仅阻塞向交换机拥塞端口输入帧的端口。采用流量控制，使传送和接受节点间数据流量得到控制，可以防止数据包丢失。
二、拥塞控制与流量控制的关系
1.拥塞控制所要做的都有一个前提，就是网络能够承受现有的网络负荷。
2.拥塞控制是一个全局性的过程，涉及到所有的主机、所有的路由器，以及与降低网络传输性能有关的所有因素。
3．流量控制往往指在给定的发送端和接收端之间的点对点通信量的控制。
4.流量控制所要做的就是抑制发送数据的速率，以便使接收端来得及接收。
三、计算机网络中IP拥塞控制算法
1。FIFO算法
FIFO又叫“先到先服务”，即第一个到达路由器的数据包首先被传输。由于每个路由器的缓存总是有限的，假如包到达时缓存己满，那么路由器就不得不丢弃该包。这种做法没有考虑被丢弃包的重要程度。由于FIFO总是丢弃到达队尾的包，所以有时又称为“去尾”算法。但“去尾”和FIFO是两个不同的概念。FIFO是一种包调度策略，决定包传送的顺序：“去尾”是一种丢弃策略，决定哪些包被丢弃。因为FIFO和“去尾”分别是最简单的包调度和丢弃策略，所以两者有时被视为一体，甚至有时就简单称为FIFO排队。
2。RED算法
RED算法包含两部分：如何监控队列长度和何时丢弃数据包。
首先，RED使用类似TCP计算超时时使用的权值Weight来计算平均排队长度Qe，即：
Qe＝Qe+WeightSampleQe
其中，Weight是滤波系数，0＆lt;Weight＆lt;1，SampleQe是即时采样的队列长度。
RED有两个阀值：Qmin和Qmax。当一个数据包到达路由器时，RED将当前Qe和这两个阀值按以下原则比较：假如Qe＆lt;Qmax时，将此包排队；假如
Qmin＆lt;Qe＆lt;Qmax，计算丢弃概率P，并以P丢弃此包；假如Qmax＆lt;Qe，则丢弃此包。这种规则意味着假如平均队长小于较低的阂值，路由器不会采取任何措施，假如平均队长大于高阀值，数据包都要被丢弃，假如平均队长介于两者之间，新到数据包就要以某个概率P丢弃。显然，丢弃概率P在Qe处于两个阀值之间时缓慢增加，在Qmax到达最大值MaxP。当然，也有一些研究建议从随机丢弃到完全丢弃的过渡应该更“平滑”。
三、算法改进
1。对FIFO的改进
FIFO排队的主要问题是无法区分不同的数据流。由于整个TCP的拥塞控制是在源端执行，而FIFO排
队不提供约束所有数据源遵守拥塞控制的机制，这就有可能让行为不良的数据流强占大量带宽。在Internet环境中，某个应用不使用TCP协议是完全可能的。结果，它可以绕开端到端的拥塞控制机制，向路由器任意发送自己的数据包，从而引起其它应用的包被丢弃。
公平排队算法则解决了这个问题。FQ算法是一种“轮询”的调度算法。在FQ算法中，路由器对每个输出线路有一个排队队列。路由器按“轮询”方式处理包。当一条线路闲时，路由器就往返扫描所有队列，依次将每队第一个包发出。当某个流的数据包到达过快时，其队列就会很快占满，属于这个流的新到的包就会被丢弃。采用这种方式，每个数据流就不可能牺牲其它数据流而多占资源。www。qiqi8。cn778论文
另外，FQ算法并没有告知源端路由器状态的机制，也就是说，FQ仍然要依靠于端到端的拥塞控制机制。它只是将数据流分隔，使不遵守拥塞控制机制的数据流不至于影响其它流。所以它在。没有牺牲统计复用的情况下提供了公平性，与端到端的拥塞控制机制也可以较好地协同。加权公平排队算法是FQ的改进算法。WFQ对每个流分配一个权值。这个权值决定
了路由器每次发往该队列的比特数量，从而控制数据流得到的带宽。将所有权值看成1，那么FQ也是一种非凡的WFQ。权值的分配往往对应不同优先级的数据流，例如用IP包头中TOS 域指定流的优先级，排队时再按优先级分配权值。这也是区分服务的思想。WFQ中权值可以由路由器自己决定，也可以由源端通过某种信令通知路由器来决定。
总之，WFQ根据不同数据流应用的不同带宽要求，对每个排队队列采用加权方法分配缓存资源，从而增加了FQ对不同应用的适应性。
2。对RED的改进
LRED算法把LossRatio引入到RED的丢弃概率的计算中，对RED的鲁棒性有一定改进，但链路利用率考虑不够;VRC算法对队列长度进行规范，获得了高的链路利用率，也具有快速的响应速度，但其鲁棒性欠缺。在综合考虑RED，PI，REM，LRED及其他RED改进算法存在问题的基础上，本文结合LRED与VRC算法的优缺点，介绍一种新的AQM算法：LRC——RED 算法。鉴于文章篇幅问题，LRED算法和VRC算法就不再次累赘了，读者可以参考文献4和5。
算法实现如下：
周期性地计算丢失比率，令l为最近M个测量周期内的丢失包的比率，即可表示为在最近M个周期被丢弃的数据包的数目与总的到达的数据包的数目的比率，表示为
接着需要利用瞬时队列长度和总的输入速率来设计计算数据包的丢包率的函数。此函数必须满足：当队列长度和总的输入速率在各自的目标值四周抖动时，丢包率应该尽可能地接近被测丢失率。结合LRED和VRC算法的思想，设计了如下简单的丢包率方程：
优点：同时稳定到目标队列值和瓶颈队列的链路带宽值，并把单个丢包率同整体数据丢失率联系在一起。
参考文献：
徐昌彪，计算机网络中的拥塞控制与流量控制，2007
罗万明，林闯，阎宝平。TCP/IP拥塞控制研究【J】，计算机学报，2001
刘秋让，倪洪波。TCP拥塞控制解决方法分析及评价【J】，计算机工程，2001
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议