路由器中的数据包排队与丢弃机制

路由器是一种非常重要的网络设备，它们负责引导数据在网络中的传输路径。路由器通常拥有一个或多个这样的功能。输入以及输出接口它们分别负责接收和发送数据包。 由于路由器的内存是有限的，因此路由器可能会耗尽用于存储新到达的数据包的空间。 这种情况发生在数据包的到达速率大于数据包从路由器内存中释放出来的速率时。 在这种情况下，新的数据包会被忽略，而旧的数据包则会被丢弃。 作为资源分配机制的一部分，路由器必须实现某种排队机制，以决定在何种情况下应该对数据包进行缓冲处理，或者在何种情况下应该丢弃这些数据包。
[标题：“attachment_1688988”，对齐方式：居中，宽度：940]

 图1：对路由器进出流量的描述
[/caption]
 

队列拥塞与排队理论

由于路由器可用的缓冲区有限，因此路由器队列容易出现拥塞现象。当进入网络的流量超过输出接口能够处理的能力时，就会引发拥塞现象。造成这种情况的原因主要有：
 

• 进入网络的流量速度超过了离开网络的流量速度。
• 所有输入接口产生的总流量超过了整体的输出能力。
• 路由器处理器无法处理如此庞大的转发表，因此无法确定路由路径。

在出现拥塞的情况下，为了合理分配路由器内存给各个数据包，路由器会遵循不同的规则来决定哪些数据包应该被保留，而哪些数据包则应该被丢弃。因此，路由器中存在着以下重要的排队规则：
 

先入先出队列算法

大多数路由器所采用的默认排队机制是FIFO模式。 通常来说，这种设置几乎不需要在服务器上进行任何配置工作。 FIFO中的所有数据包都会按照它们进入路由器的顺序被处理。 当内存达到饱和状态时，试图进入路由器的新数据包会被丢弃（即所谓的“尾部丢弃”）。 不过，这样的方案并不适合用于实时应用，尤其是在出现拥堵情况的时候。 像VoIP这样的实时应用程序，由于需要持续发送数据包，因此在拥塞期间可能会遇到数据包丢失的情况。
 

优先级排队机制

在优先级队列中，路由器不会使用单一的队列结构，而是根据某种优先级标准将内存划分为多个队列。之后，每个队列都会按照FIFO的方式被处理，即逐个处理各个队列中的内容。这些队列会被标记为……高, 中等或者低根据优先级来排序。来自“高优先级队列”的数据包总是先被处理，而来自“中等优先级队列”的数据包则次之。同样地，来自“中等优先级队列”的数据包也总是先被处理，然后再处理来自“普通优先级队列”的数据包。只要“高优先级队列”中还有数据包存在，其他任何队列中的数据包都不会被处理。因此，高优先级的数据包会优先被处理。只有当高优先级队列中的数据包处理完毕后，才会开始处理低优先级的数据包。
 

图2：在优先级队列方案中，使用了多个子队列。

PQ方案的一个明显优势是，优先级较高的流量总是会优先得到处理。不过，PQ方案的一个显著缺点就是，低优先级的流量往往也会被处理掉。
因为……所以完全没有服务可言。饥饿持续不断的、优先级较高的流量会迫使那些优先级较低的队列陷入“饥饿状态”。
 

加权公平队列（Weighted Fair Queuing, WFQ）

加权公平队列（Weighted Fair Queuing, WFQ）能够根据流量情况动态创建队列，并根据优先级为这些流量分配带宽。 这些子队列会动态地被分配相应的带宽。 假设存在三个队列，当它们都处于活跃状态时，各自的带宽利用率分别为20%、30%和50%。 如果那20%的队列处于空闲状态，那么被释放出来的带宽就会分配给其余的队列，同时仍然保持原有的带宽分配比例。 因此，原本分配给30%的队列的带宽现在被分配给了75/2%，而原本分配给50%的队列的带宽则被分配给了125/2%。
交通流量它们是通过数据包中的各种头部字段来区分和识别的，例如：
 

• 源地址与目标地址
• 源端口与目标端口（TCP或UDP）
• IP协议编号
• 服务类型值（IP优先级或DSCP）

图3：在WFQ中，为子队列动态分配带宽。

因此，数据包会根据与其相关的流量情况被分配到不同的队列中。 一旦识别出属于同一流量流的数据包，这些数据包就会被放入一个专门为这类流量而创建的队列中。 默认情况下，路由器内最多可以创建256个队列。不过，这个数量可以增加到4096个队列。 与PQ方案不同，WFQ队列根据它们的排队优先级来分配不同的带宽。 优先级较高的数据包会优先被处理，而同时到达的、优先级较低的数据包则会被依次处理。
 

排队论对网络的影响

排队策略的选择会影响网络的性能，主要体现在丢包数量、延迟等方面。在分析不同策略的影响时，我们发现这些策略对各个参数都有显著的影响。
 

图4：不同排队算法下，数据包被丢弃的次数与时间的关系（在Riverbed Modeler上进行模拟测试）

对这三种方案下网络中的整体数据包丢失情况进行测量后，得到如下结果：
 

• 在所有这些机制中，最初阶段不会出现数据包丢失的情况。这是因为，路由器缓冲区需要一定的时间才能被填满。而数据包的丢失则发生在缓冲区被填满之后。在初期阶段，由于缓冲器的容量尚未达到最大值，因此不会出现数据包丢失的情况。.
• 在FIFO机制中，数据包的丢弃行为发生在PQ阶段之后，但在WFQ阶段之前。值得注意的是，FIFO模式下，被丢弃的数据包数量是最多的。这是因为……一旦出现拥堵情况，所有来自各个应用程序的流量都会被完全中断，而不会受到任何区分。.
• 在PQ方案中，数据包的丢失现象最早出现。由于PQ方案是根据优先级来划分队列的，因此各个队列的整体大小也会得到相应的分配。假设内存被简单地划分为几个部分……重要的/值得关注的排队，还有……不太重要/无关紧要“排队中。”队列的大小减少了一半。因此，被分配到子队列中的数据包会更快地填满队列，从而导致数据包丢失的情况更早发生。