前言

本章主要介绍计算机网络中的一些流量控制策略包含流量整形和流量排队。

流量整形

在之前的章节中我们学到，当流量大于承诺信息速率(CIR)时，流量具有丢弃资格(DE)。而当流量大于承诺信息速率(CIR)+超额信息速率(EIR)时，传输的流量就有可能会被丢弃。

在网络中一般有两种常见的流量控制方法——流量限速(Traffic Policing)与流量整形（Traffic Shaping）。它们保证了最大的流量不超过承诺信息速率(CIR)+超额信息速率(EIR)所传输的最大量。

流量限速(Traffic Policing)是一种确保没有流量超过配置的最大速率的方法，当流量速率达到配置的最大速率时，将会直接丢弃或标记超出部分的数据包，其流量图表现为锯齿状。 而流量整形（Traffic Shaping）使用缓冲队列来延迟数据包传输，将突发流量转换为平滑流量。它可以防止数据包丢失，使得流量图呈现得更平滑。

流量限速在传输大规模数据时可能会导致大量的丢包，所以主流的流量控制方法时流量整形，流量整形有两种常见的算法——漏桶算法(Leaky bucket algorithm)和令牌桶算法(Token bucket algorithm)。

漏桶算法 (Leaky bucket algorithm)将所有进入网络的数据包都放入一个固定容量的桶（先进先出队列）中，数据包会以恒定的速率从桶的底部漏出，相当于一个漏斗。如果桶已满，则不能接受新的数据包，可能导致数据包的丢失。如图是一个漏桶的例子，其中桶的总大小为s (size)，已经存在的数据包突发量为b，桶的平均泄露率为Pout。漏桶算法以一个恒定的速率发送数据。 当桶没有满时，即b < s，此时若想不丢包，理论上桶的最大进入速率Pin = (s-b)/t + Pout。因为在特定的时间内（t），桶内能够额外接受的数据量，同时再加上桶本身的泄露率Pout，它表示了在不超过桶的总容量（s）的情况下，桶短时间内能够处理的最大输入速率。 我们通过一个例子来理解漏桶算法的基本过程：

Suppose,the buffer size = 10000 Mb , leak rate = 1000 Mb/s. Assume at some point the packets are thrown into the bucket as [200,500,400,500,200]. Now, in each iteration (per second), how to transfer the packets such that the sum of the size of each packet is not greater than the leak rate?
假设缓冲区大小 = 10000 Mb，泄漏率 = 1000 Mb/s。在某一点，数据包被投入桶中为[200,500,400,500,200]。在每次迭代（每秒）中，如何传输数据包，使得每个数据包的大小之和不大于泄漏率？

根据题目内容已知Pout = 1000 Mb/s, s=10000Mb，初始情况下，桶为空，b = 0。故在每次迭代中，传输的数据包如下（不能部分传输数据包）：

  1. 传输200,500
  2. 传输400,500
  3. 传输200

 

而令牌桶(Token bucket)与漏桶的不一样，它是一个以限制的速率发送数据。令牌桶算法发送数据包时需要消耗令牌(token)，每发送一个数据包就从桶中移走一定数量的令牌。只有当桶中有足够的令牌时，才允许数据包通过桶。 如图，其中桶的大小为b，令牌生成速度为r，桶如果满了，新令牌就会被丢弃。如果桶中令牌不足，那么数据包需要等待直到有足够的令牌。 若在t1时间内达到令牌桶的上限，令牌消耗的最大数量为o1 = p1t1 = b+rt1，p1=(b+rt1)/t1。在t2(t2>t1)时间内，超出令牌生成的部分数据包将会以均匀的令牌生成速度r传输，即在t2时间内传输的最大数据为o2 = p1t1 + r(t2 - t1) 。在t1时间内，数据包的传输不会超过令牌数，此时传输速率Pin = Pout，在此之后，Pout = r。 下面是一个令牌桶应用的例子：

Exercise 10.1
A token bucket traffic shaper: Token generator with rate r = 4 (byte/s), and Token bucket size b = 8 (byte). The output rate R (byte/s). The token bucket starts out full with b tokens.
Q1. If the interval T1 = 1 s, what is the maximum of R within this interval?
Q2. If the input rate of packets P = 12 (byte/s), what is the maximum amount of traffic can be sent before the interval T2 = 2 s?
Q3. If P = 20 (byte/s), what is the maximum amount of traffic can be sent before the interval T2 = 2 s?
假设，令牌生成器的速率r = 4 (字节/秒)，令牌桶的大小b = 8 (字节)。输出速率R (字节/秒)。令牌桶开始时满的，有b个令牌。
Q1. 如果间隔T1 = 1 s，那么在这个间隔内R的最大值是多少？
Q2. 如果数据包的输入速率P = 12 (字节/秒)，那么在间隔T2 = 2 s之前，可以发送的最大流量是多少？
Q3. 如果P = 20 (字节/秒)，那么在间隔T2 = 2 s之前，可以发送的最大流量是多少？

  • Q1. R表示离开令牌桶时的传输速率，根据令牌桶模型的速率变化图，在T1 = 1s内最大的输出速率R = (b+rT1) / T1 = 12 byte/s.
  • Q2. 若P = 12 byte/s = Rmax，则说明其在T1 = 1s内保持最大输出速率，在T1~T2 s内保持平均速率r，则最后最大发送的流量为o = b + rT_1 + r(T2 - T1) = 16 bytes. 此时的平均速率为R' = o / T2 = 8 byte/s
  • Q3. 若P = 20 byte/s > Rmax，则此时速率会被令牌桶限制，最大传输的流量也为16 bytes.

除了这两种常见的流量整形方法外，在帧中继网络中还有一种帧中继流量整形(FRTS, Frame Relay Traffic Shaping)的动态整形方法。

在这个过程中，数据被分成固定大小的帧，然后按照设定的速率发送。如果网络拥堵或速率不匹配，整形器会缓冲数据，以便在适当的时间再次发送。这有助于确保网络流量平滑传输，避免拥塞和丢包。

流量排队

流量排队(Traffic Queuing)是网络中一种典型的现象，当网络中的数据包到达的速度超过了网络设备处理它们的速度时，这些数据包就会在设备的缓冲区中排队等待处理。排队算法是配置在网络设备上用于处理拥堵期间数据包调度问题的方法，它使得关键任务和延迟敏感的流量优先发送出去。流量排队可以分为硬件排队(hardware queuing)和软件排队(software queuing)。

  • 硬件排队(hardware queuing)，通常发生在物理设备中，如网络路由器或交换机。这些设备有专门的硬件资源（如缓冲器 buffer）用于存储和管理待处理的数据包。由于硬件排队直接在物理设备中进行，它通常能提供更高的处理速度和更低的延迟。然而，硬件排队的策略和容量通常由设备的物理设计确定，不易进行修改或优化。硬件排队又被称为缓冲(Buffering)。
  • 软件排队(software queuing)则发生在计算机的操作系统或应用程序中。在软件排队中，数据被存储在计算机的内存中，并由软件优先级排序算法进行管理和调度。与硬件排队相比，软件排队具有更高的灵活性，可以根据需要调整排队策略和容量。但是由于软件排队需要计算机的处理器和内存资源，其性能可能受到这些资源的限制。软件排队又被称为重新排序(Re-order)。

通常情况下，硬件排队和软件排队是同时存在的。首先由软件排队将数据包重新排序后，再存储到计算机的缓存区中，如图：

常见的排队方法有：

  1. FIFO（First In, First Out）：FIFO 是最简单和最常见的排队方法之一。它按照数据包到达的顺序将它们存储在队列中，并按照它们到达的顺序将它们发送出去。但可能导致某些数据包在队列中长时间等待，从而增加延迟。
  2. WFQ（Weighted Fair Queuing）：WFQ 是一种公平的排队方法，它根据数据包的流量和服务质量要求来分配带宽和优先级。它为每个数据流分配一个权重，以确保每个流都能公平地共享网络资源。WFQ 在多流量情况下能够提供较好的性能，但实现起来相对复杂。
  3. PQ（Priority Queuing）：PQ 是一种优先级排队方法，它将数据包划分为多个优先级队列，并按照优先级顺序发送数据包。具有高优先级的队列中的数据包将优先于低优先级队列中的数据包进行发送。PQ 可以确保重要的数据优先被传输，但可能导致低优先级数据包被长时间阻塞，产生延迟。
  4. CQ（Custom Queuing）：CQ是FIFO和PQ的结合。自定义队列CQ保证了关键任务数据始终被分配一定的带宽比例，但也确保了其他流量的可预测吞吐量。

对于优先级排队（PQ），首先需要对流量中的数据包按照一些标准分类，并将他们分配给四个输出队列中：它们分别代表High, Medium, Normal, Low的优先级。当网络设备准备好发送数据包时，它首先检查优先级高的队列。一旦高优先级队列为空，网络设备就检查中优先级队列，依此类推，这个过程（从高优先级队列开始）在网络设备每次准备发送数据包时重复进行。它的过程如图所示： 对于加权公平排队 (WFQ)，它为每个流量类别分配一个权重，然后根据这些权重公平地处理数据包。具有较高权重的流量类别将获得更多的处理时间，而具有较低权重的流量类别将获得较少的处理时间。简单来说就是：各个队列根据其权重获得不同的服务比例。更高权重的队列可以发送更多的数据，即使在网络拥塞的情况下也保证了带宽的分配。我们通过一个例子来理解这个排队算法的过程： 如图所示的分组和权重分布，有17个数据包等待发送。 在一个调度周期中，这些队列分别可以发送的数据包大小比例为1:2:3。假设一个周期内可以发送的数据包没有限制，则权重为1的队列每次发送1个数据包，数据包的大小为k bytes，那么权重为2的队列则可以发送2k bytes，权重为3的队列则可以发送3k bytes，这个过程确保了每个队列都能根据其权重公平地获得带宽。

  1. 我们首先选取权重小的作为开始，首先发送数据包1，大小为100 bytes(之后省略单位)，此时Counter1 = 100. 此时对于W=2的队列, 它可以发送200的数据，此时发送数据包2和3，大小为250，达到限制大小200. 对于W=3的队列，它可以发送300的数据，于是发送数据包4,5,6，大小为410，达到限制大小300。 此时的Counter情况如下： 
    Counter1: 100
Counter2: 250
Counter3: 410
  2. 接下来继续发送权重小的，数据包7，大小为120，Counter1为220. 对于W=2的队列，限制大小为440大于Counter2，则可以继续发送数据包8,9，10，11达到500. 对于W=3的队列，可以发送660的数据，于是发送13,14，达到760. 此时的Counter情况如下： 
    Counter1: 100 + 120 = 220
Counter2: 250 + 250 = 500
Counter3: 410 + 380 = 760
  3. 接着下一个调度周期，发送数据包15，Counter1为240. 而Counter2 * 2 > Counter1，W=3的队列已全部发送，故此次没有其他数据包发送。此时的Counter情况如下： 
    Counter1: 100 + 120 + 20 = 240
Counter2: 250 + 250 = 500
Counter3: 410 + 380 = 760
  4. 下一个周期中，发送数据包16，Counter1为310，对于W=2的队列，可以发送的数据为620 > Counter2，故可以继续发送数据包17，达到690. 此时的Counter情况如下： 
    Counter1: 100 + 120 + 20 + 70 = 310
Counter2: 250 + 250 + 190 = 690
Counter3: 410 + 380 = 760
  5. 最后，所有的数据包发送完毕。

整个过程中，数据包发送的顺序为：

1,2,3,4,...,17

对于自定义队列CQ，它是FIFO和PQ的结合，首先通过PQ将流量分组，分为不同优先级的队列中，然后在每个队列中使用FIFO队列的方式发送数据包。下面是它的简单概念图：

我们通过下面的一个例题来理解这些软件排队算法是如何重新排列数据包发送顺序的。

Exercise 10.2
The receiving order of each packet is listed in the queues, what is the sending order of the packets after re-scheduled by the FIFO, PQ, WFQ queuing?
队列中列出了每个数据包的接收顺序，那么通过 FIFO、PQ、WFQ 队列重新排序后，数据包的发送顺序是什么？

对于FIFO，它不会修改数据包的顺序，因为根据先进先出原则，它会按照接受顺序依次发送，故它的发送顺序是：

1,2,3,4,...,9

对于PQ，它是根据队列的优先级发送数据包，根据图中已经提供的分组，我们可以很快的得到发送的顺序按照优先级为：

1,5,6,4,7,9,2,3,8

对于WFQ，它是根据权重来决定每个调度单位时间内发送数据包的大小（而非数量）。我们一步步来看这个过程： 首先我们认为每一个队列的所能发送数据包的速率是相同的，此时一般从权重小的开始计算起。

  1. 在W=1的队列中，我们发送第一个数据包，大小为10 bytes。此时对于W=2的队列，它则可以发送大小为2 * 10 = 20 bytes的数据。不过当前W=2的队列还没有发送过（Counter2 = 0），于是可以尝试发送第4个数据包，大小为55 bytes，它大于了前面的限制20 bytes，于是发送完这个数据包后它就不能继续发了。同理的，对于W=4的队列，它可以发送大小为40 bytes的数据，但是此前还没有发送过数据（Counter3 = 0），于是可以尝试发送数据包2，大小为120 bytes，也超过了前面的限制，于是发送完这个数据包后它就不能继续发了。当前每个队列中的counter如下： 
    Counter1: 10
Counter2: 55
Counter3: 120
  2. 在第二个调度周期中，在W=1的队列中我们可以继续发送数据包5，大小为15 bytes。此时Counter1=10+15=25 bytes，这W=2的队列可以发送50 bytes, W=4的队列可以发送100 bytes的数据。但是在这一周期中，Counter12 < Counter2, Counter1 4 < Counter3，W=2和W=4的队列均不能继续发送(保证公平)。此时Counter的情况： 
    Counter1: 10 + 15 = 25
Counter2: 55 + 0
Counter3: 120 + 0
  3. 在第三个调度周期中，在W=1的队列中我们可以继续发送数据包6，大小为25 bytes，此时Counter1=10+15+25=50 bytes。对于W=2的队列，它可以发送100 bytes的数据，它大于当前的Counter2，故可以继续发送数据包7。同理，对于W=4的队列，它可以发送200 bytes的数据，它大于当前的Counter3，故可以继续发送数据包3。此时Counter的情况： 
    Counter1: 10 + 15 + 25 = 50
Counter2: 55 + 0 + 100 = 155
Counter3: 120 + 0 + 250 = 370
  4. 在第四个调度周期中，W=1的队列已经全部发送完毕，就从W=2的队列开始发送。此时没有了之前的限制，可以发送数据包9，Counter2则等于55+0+100+75=230 bytes 。对于W=4的队列，此时它可以发送460 bytes的数据，于是它发送数据包8，最后的Counter情况如下： 
    Counter1: 10 + 15 + 25 = 50
Counter2: 55 + 0 + 100 + 75 = 230
Counter3: 120 + 0 + 250 + 150 = 520
  5. 最后，所有的数据包发送完毕。

整个过程中，数据包发送的顺序为：

1,4,2,5,6,7,3,9,8

总结一下WFQ这个过程：

  1. 在默认情况下每个队列进入的流量是相同的，我们会以权重小的开始发送；
  2. 权重大的队列能发送的数据包大小需要根据权重小的来判断，且数据包的大小表示的是总体发送数据的大小，而不是单次，如第二、三、四周期的发送条件。
  3. 每一个队列中，只允许增加至多一个大于限制大小数据包，即可以发送达到限制大小前的所有数据包，如之前例子中的第二周期W=2的队列发送8,9，10，11数据包后才达到限制。
这里的一切都有始有终，却能容纳所有的不期而遇和久别重逢。
最后更新于 2024-05-11