拥塞控制算法

anthonyu

　　网络拥塞现象是由于网络的数据流量或交通量超过网络额定容量而引起的，致使网络的吞吐能力急剧下降。通常，网络信道容量是按照能满足传输需求的平均水平设计的。如果网络浪涌交通量超过这个平均水平，则可能引起网络拥塞现象。当发生网络拥塞现象时，必须通过适当的拥塞控制措施来疏导网络交通，如路由器节点丢弃一些次要的数据分组（亦称分组节流）来缓解拥塞；改变发送节点的发送速率等。　　拥塞控制与流量控制不同，拥塞控制主要用于保证网络通畅地传送数据，它涉及网络中所有与之相关的主机和路由器的发送和转发行为，是一种全局性的控制措施。 　　流量控制只涉及发送端和接收端之间的点到点的流量控制行为，主要用于保证发送端的发送速率与接收端的缓冲区容量相匹配，以防止在接收端缓冲区不足时发生数据丢失现象。　　尽管拥塞控制也要通过反馈机制的要求发送节点减缓发送速率来疏导网络交通，但引起它的原因可能是多方面的，如接收节点的缓冲区溢出、线路拥挤以及带宽不足等。　　拥塞控制算法大致可分成开环控制和闭环控制两大类，开环控制算法是通过良好的网络系统设计来避免拥塞问题的发生。在网络运行过程中，何时接受新分组，何时丢弃分组以及丢弃哪些分组都是事先规划好的，并不考虑当前的网络流量状况。闭环控制算法是通过反馈机制来调整当前网络流量，使网络流量与网络可用资源相协调，从而使网络拥塞问题得到解决。由于闭环控制算法能够根据当前网络状况对流量进行动态控制，具有较高的效率。因此，现代网络系统大都采用闭环控制算法来解决网络拥塞问题。　　在闭环控制算法中，关键技术在于：检索机制，能够随时发现拥塞问题；反馈机制，能够将发生拥塞的信息传送到适当的控制点；调整机制，能够通过调整系统操作来排除问题。　　检索机制将根据当前网络状况来监视网络是否发生了拥塞，判断的依据或基准参数主要有：因缺少缓冲区空间而丢弃的分组数量、平均分组队列长度、超时重发分组的数量、平均分组延迟时间等。如果基准参数超过临界值，则意味着可能发生了网络拥塞。　　反馈机制是将发生拥塞的信息从检查点传送到控制点。反馈方式有两种：显式反馈和隐式反馈，显式反馈采用由检查点向控制点反馈一个警告分组的方式来通告网络已发生了拥塞；隐式反馈采用由控制点(源端)通过观察应答分组返回所用时间进行推断的方式来判断网络是否发生了拥塞。 　　调整机制是通过检查点和控制点相互协作来共同努力解决拥塞问题。控制点通过降低载荷，即降低分组发送速率来缓解拥塞；检查点通过载荷脱落，即丢弃一些分组来疏导交通，或者通过增加系统资源(如增加附加的线路或提高线路带宽)来提高流量通过能力，对于后者，要求系统能够提供后备的资源。　　在拥塞控制算法中，根据数据交换方式(虚电路或数据报)的不同，采用不同的控制策略。 2.4.3.1 面向虚电路的拥塞控制算法 1．漏桶算法　　漏桶算法是将交通整形操作形象地比喻成一个底部带有一个小孔的水桶，不管流入桶中的水速多大，从底部小孔流出的水速是恒定的。如果桶中无水，则速率为0；如果桶中水满，则流入桶中的水将从桶边溢出，即流失掉了。漏桶算法相当于在路由器内部实现一个有限长度队列，路由器将以恒定速率从队列中取出分组发送出去，而进入路由器的分组被排到队列的尾部，一旦队列饱和，新来的分组将被丢弃。这种算法实际上是一种具有恒定服务时间的单服务器排队系统。　　主机系统也可采用该算法来整形分组的发送，将上层应用进程不均匀的数据流整形成均匀的分组流向网络发送，平滑了突发的数据流，减少了发生拥塞的机会。 　 2. 令牌桶算法　　令牌桶算法与恒定输出速率的漏桶算法有所不同，它允许一定量的突发数据流。该算法以恒定速率产生一个个令牌放入桶中，每发送一个分组都要获得和消耗一个令牌，如果令牌消耗完，则新来的分组就要等待生成新令牌或被丢弃。由于突发性的输入流往往导致拥塞的发生，因此获得令牌的分组将被快速地输出，使突发性的输入流得到迅速的疏导。　　在令牌桶算法中，使用一个令牌计数器来计数令牌数量。令牌计数器每隔Δt时间加1，表示新增加一个令牌；每发送一个分组，令牌计数器减1，表示已消耗一个令牌。当计数器减至0时，表示令牌已消耗完，不能再发送分组了。 2.4.3.2 面向数据报的拥塞控制算法　　数据报是一种无连接传输方式。路由器一旦检测到系统可用资源(如线路利用率或队列长度)超过临界值，就会向源端主机发送一个抑制分组，警告网络可能发生拥塞。源端主机定期地侦听抑制分组，如果在侦听期内收到抑制分组，则会逐步减少发送给特定目的主机的数据量；当减至在侦听期内不再收到抑制分组后，可以再逐渐增加通信量。主机可以通过调整其发送操作的相关参数来减少通信量，如改变发送窗口尺寸或漏桶输出速率等。路由器通常采用加权公平队列算法来处理分组排队，检测是否超过临界值以及何时发送抑制分组。 在广域网环境下，采取完全由远程的源端主机减少通信量来缓解拥塞的方法并不是很有效的，因为距离远，反应慢。一种改进的方法是抑制分组途经的各个路由器都要抑制通信量，使拥塞得到迅速的控制，但路由器要提供一定数量的缓冲区空间用于暂存过量的分组。当抑制分组到达源端主机后，由源端主机采取适当的措施最终才能使通信量降下来。这种方法的优点是可以迅速地控制拥塞，但中间的路由器节点需要较大的缓冲区空间开销。 在IP协议中，采用了抑制分组的方法来解决网络拥塞问题。 当网络发生严重拥塞时，路由器往往需要采用载荷脱落(Load Shedding)，即丢弃分组的方法来疏导交通。理论上，路由器可以随意选择要丢弃的分组。实际上，路由器总是采用某种策略来丢弃分组，如按先来先服务的规则丢弃后到的分组；按分组优先级的规则丢弃优先级低的分组等。当然，被丢弃的分组要重新传输。　　按分组优先级的规则丢弃分组的方法被很多网络系统或协议所采用，如ATM网络、帧中继网络以及IP协议等。在这些网络系统中，分组(或帧)中设有一个优先级字段，发送者在生成一个分组时，要设置其优先级字段(通常由应用程序指定)，说明在发生拥塞时丢弃分组的优先次序。一旦发生拥塞，路由器将根据分组中所标记的优先级来选择要丢弃的分组。