计网是四大件之一，在计算机基础中占重要地位，对于相关学习者来说是绕不开的一部分。以此系列博客记录一下我大三上学期计网的学习过程，期间用到的教材是第五版龙书，有需要电子版的朋友可以联系我。（因为是由英文原书翻译过来的，有些看起来荒谬冗长的语句需要大家联想纠正）

这里将网络层的拥塞控制这一章节详细展开讲述

拥塞的发生

网络中存在太多的数据包导致数据包被延迟和丢失，从而降低了传输性能，这种情况称为拥塞（congestion）。网络层和传输层共同承担着处理拥塞的责任，在这里，我们将着眼于拥塞控制在网络层方面的处理。

图5-21 描绘了拥塞的发生。当主机发送到网络的数据包数量在其承载能力范围之内时，送达的数据包数与发送的数据包数成正比例增长。如果发送量增加了两倍，则送达量也增长了两倍。然而，随着负载接近承载能力，偶尔突发的流量填满了路由器内部的缓冲区，因而某些数据包会被丢失。这些丢失的数据包消耗
了部分容量，因此，送达的数据包数量低于理想曲线。网络现在开始拥挤了。

拥塞控制的途径

拥塞的出现意味着负载暂时大于资源可以处理的能力。很自然人们能想到两个解决方案：增加资源或减少负载。

如图5-22 所示，这些解决方案通常应用在不同的时间尺度上，要么预先避免拥塞，要么一旦发生拥塞随之做出反应。

• 避免拥塞的最基本方法是建立一个与流量匹配良好的网络。有时当出现严重拥塞时，可以动态增加网络资源。这就是所谓的供给（provisioning）在长期流量趋势推动下大约需要几个月的时间。
• 为了充分利用现有的网络容量，可以根据每天的流量模式度身定制路由，因为不同时区的网络用户每天醒来和睡觉的时间是不同的。例如，一些本地广播电台有直升机围绕着城市上空飞来飞去，及时报告城市道路拥堵情况，帮助它们的移动听众路由它们的数据包（汽车）绕开热点地区，这称为流量感知的路由（traffic-aware routing)。
• 然而，有的时候不可能增加容量。那么对抗拥塞的唯一的办法就是降低负载。在一个虚电路网络中，如果新的连接将导致网络变得拥挤不堪，那么就应该拒绝这种新连接的建立。这种控制称为准入控制（admission control）。
• 最后，当一切努力都失败，网络不得不丢弃它无法传递的数据包。这种方法的通用名称是负载脱落(load shedding)。一个选择丢弃哪些数据包的良好策略可以防止拥塞崩溃。

流量感知路由

最直接的方式是把链路权重设置成一个（固定）链路带宽、传输延迟、（可变）测量负载或平均排队延迟的函数。’在所有其他条件都相同的情况下，最小权重的路径更青睐那些轻负载的路径。

早期Internet 使用的流量感知路由就是按照这个模型设计的。然而，这种路由存在一个危险。

考虑图5-23 所示的网络，这里网络被分为东部和西部，这两部分通过链路CF 和EI 相连。假设东西之间的大部分流量使用链路CF, 因此，这个链路负荷超重因而延迟增大。如果把排队延迟加入到计算最短路径的权重中，那么链路EI将变得更具吸引力。当新的路由表被安装好之后，大部分东西方的流量现在改走链路EI由此增加了此链路的负载。因此，在下一次路由更新时，CF 将成为最短路径。结果，路由表可能会剧烈地摇摆不定，从而导致不稳定的路由和许多潜在的问题。

如果忽略负载，只考虑带宽和传输延迟，这个问题就不会发生。尝试在路由权重中包括负载但将其限定在一个狭窄的范围可减缓路由振荡。两种技术有助于获得成功的解决方案。首先是多路径路由，即从源到目的地可以存在多条路径。在我们的例子中，这意味着可以把整个流量分散到东部和西部的两条链路上。第二个技术是把流量慢慢迁移，足够慢到路由算法得到收敛。

由于存在这些困难，Internet 路由协议通常不依赖于负载来调整自己的路由。相反，在路由协议外部通过慢慢改变它的输入来调整路由。这种方法就是所谓的流量工程（traffic engineering )。

准入控制

一种广泛应用于虚电路网络，防止出现拥塞的技术是准入控制（admission control)。其基本思想非常简单：除非网络可以携带额外的流量而不会变得拥塞，否则不再建立新的虚电路。因此，任何建立新的虚电路的尝试或许会失败。

如果我们想要采用准入控制，必须归纳出虚电路的一些流量特性。流量往往用其速度和形状来描述。如何以一种简单而又有意义的方式来描述流量是困难的，因为流量呈现突发性平均速率只讲述了故事的一半。例如，浏览网页时的流量变化很大，比具有固定长期吞吐量的流式电影更难以处理，因为突发性的网页流量更容易
堵塞住网络中的路由器。捕获这个效果通常采用的描述符是漏桶（leaky bucket) 或令牌桶(token bucket)。一个漏桶有两个参数约束了平均速率和瞬时突发流量大小。我们将在服务质量这节仔细描述它。有了流量说明， 网络就能决定是否接受新的虚电路。

准入控制还可以和流量感知路由相结合，在虚电路建立过程中，考虑绕开流量热点区域的路由。例如，考虑图5-24 的网络，这里显示的两台路由器己经被堵塞。
假设一台连接到路由器A 的主机想要与另一台连接到路由器B 的主机建立一个连接。通常情况下，这个连接将会经过其中一台拥塞的路由器。为了避免这种情形，我们可以重画网络，如图5-24 (b) 所示，去掉拥塞的路由器和它们所有的线路。图中的虚线显示了条可能的虚电路路径，它避开了拥塞的路由器。（Shaikh 等，1999) 给出了这类负载敏感的路由方案设计。

负载脱落

当以上任何一种方法都无法消除拥塞时，路由器可以亮出它的杀手锏，即负载脱落。负载脱落（load shedding） 是一种富有想象力的说法，它指当路由器因为来不及处理数据包而面临被这些数据包淹没的危险时，就将它们丢弃。

对于一个被数据包淹没的路由器来说，关键的问题是选择丢弃哪个数据包。首选的方案可能取决于使用网络的应用程序类型。对于文件传输，旧的数据包价值要高于新的数据包。相比之下，对于实时媒体流，新的数据包价值超过老的数据包。因为如果数据包被延迟并且错失了给用户的播放时间，那么该数据包就变得一无所用。

更智能的卸载方式需要发送方的合作。一个例子是携带路由信息的数据包。这些数据包比普通数据包要重要得多，因为它们是被用来建立的路由；如果丢失它们，或许就会丢失网络连接。为了实现智能丢弃政策，应用程序必须在它们的数据包上打上标记，指示网络它们有多重要。然后，当不得不丢弃数据包时，路由器可以首先丢弃重要性最轻一类数据包，然后是次重要一类数据包，以此类推。

随机早期检测

在拥塞刚出现苗头时就处理它比等拥塞形成之后再设法解决它更加有效。可以利用这种情形来帮助缓解拥塞。在局面变得毫无希望之前让路由器提前丢包，但这里有个时间点的确定问题，即发送方何时采取行动以免为时过晚。解决这个问题的一个流行算法称为随机早期检测（RED，Random Early Detection)。

为了确定何时开始丢弃数据包，路由器要维护一个运行队列长度的平均值。当某条链路上的平均队列长度超过某个阈值时，该链路就被认为即将拥塞，因此路由器随机丢弃一小部分数据包。随机选择丢弃的数据包使得快速发送方发现丢包的可能性更大；因为在数据报网络中，路由器不能分辨出哪个源引起了网络的最大麻烦，因此随机选择丢弃的数据包或许是最佳选择。当没有出现期待的确认信息时，受此影响的发送方就会发现丢包，然后传输协议将放慢速度。因此，丢失的数据包起到了传递抑制包的同样作用，但却是隐含的，无须路由器发送任何显式信号。

相比那些只在缓冲区溢出才丢包的路由器，RED 路由器能提高网络性能，虽然它们可能需要调整正常工作方式。举例来说，理想的丢包数量取决于有多少发送方必须得到拥塞通知。然而，如果ECN 可用，那么它就是首选的选项。它的工作方式几乎完全一样，但提供了一个显式拥塞信号而不是依据丢包来判断是否拥塞；RED 用在主机不能接收显式信号的环境里。