分组交换：延迟保证

在这段视频中，我将继续介绍分组交换，特别是我将告诉你如何保证从网络的一端到另一端的延迟，这可能有点令人惊讶，因为在前面的视频中，我告诉你排队延迟是如何变化的，所以我们一般不能控制网络的延迟，但我们将使用特殊的技术，依靠我们在速率保证视频中学习的加权公平排队，所以你应该确保你先看那个视频。

延迟保证：直觉

让我先给你一些关于延迟保证如何工作的直觉，记得我们的端到端延迟方程：

$$\tau=\sum_{i}\left(\frac{p}{r_{i}}+\frac{l_{i}}{c}+Q_{i}(t)\right)$$

它告诉我们从网络一端到另一端的延迟是数据分组延迟的函数，即分组长度除以速率；再加上传播延迟，即链路长度除以传播延迟或光速，再加上排队延迟。前两个项被定义为网络的固定函数，它们取决于我们控制的东西，而通常排队延迟不受我们控制。因此，如果我们想提供端到端的延迟保证，那么我们就必须为沿路的每个路由器的队列提供一个延迟保证。

所以基本的想法是，如果我们知道$Q_1, Q_2, Q_3$的上限，那么我们就知道端到端的延迟上限。那么我们如何做到这一点呢？

如果在一个路由器中，我知道分组要经过哪些队列，缓冲区的大小和服务的速率，那么就知道分组可能遇到的最大延迟。

因为我们在速率保证视频中看到的WFQ加权公平排队给了我一个速率$R_i$：

$$R_i=\frac{w_i}{\sum w_i} \times R$$

然后我可以简单地说，通过这个路由器的延迟为被缓冲区的大小$B$除以$R_i$，即它实现的速率所限制。

所以我们可以如何控制分组延迟

我们已经知道如何控制延迟：

1. 队列的服务速率(WFQ)。

2. 每个队列的大小。

这两点给出了路由器的模型，在这个模型中，我们对进入的分组进行分类，把它们放在正确的队列中，然后设置队列大小，以正确的速率为队列服务。

任何到达路由器的分组都会有一个有限的延迟，如果我们正确地把延迟的所有组成部分加起来，那么我们就可以得到端到端的延迟。

这适用于一路畅通的分组。如果分组到达的速度太快而被丢弃怎么办？

放大一个队列

我们要注意$d(t)$——$D(t)$和$A(t)$之间的水平距离(它是一个先进先出的的队列。)$D(t)$是很好的约束，但如果到达过程太大，$Q(t)$会增长，分组会被丢弃。

如果我们能以某种方式控制$A(t)$以确保这种情况不会发生呢？这就是我们接下来要研究的问题。如果我们能解决这个问题，那么我们就能通过路由器提供延迟保证。

如果我们可以说，在任何间隔$T$，没有超过$B + R_1\times T$的比特可以到达队列呢？换句话说：

$$A(t+T)-A(t)\le B+R_1\times T$$

这种方法的优点：

• 队列永远不会溢出，所以我们知道延迟是有保证的。

• 我们已经给到达过程$A(t)$留出了很大的回旋余地。

约束流量

要限制流量，我们要使用一个相当知名的技术来做这件事，叫做“$(\sigma, \rho)$ regulation”：

让我来告诉你什么是"$(\sigma, \rho)$ regulation"，它基本上是我刚才告诉你的想法。如果这条蓝色(绿色)的曲线是我们的累计到达过程$A(t)$，我将说，在任何长度为$t$的时期内可以到达的比特数的上界为

$$\sigma +\rho t$$

即在任何时候，我们可以画出蓝线$\sigma +\rho t$，实际的曲线(绿色)一定在该线下方。

如果这个方程成立，那么我们说$A(t)$是“$(\sigma, \rho)$ regulation”，你可以看到$A(t)$下方有相当大的余地，只是从任何一点开始都不能超过它。

在我们的例子中：

$$\begin{aligned} \sigma&=B\\ \rho&=R_1 \end{aligned}$$

$(\sigma,\rho)$约束到达率和最低服务率

如果我有$(\sigma,\rho)$ regulation的到达率和最低服务率，那么最低服务率是$R_1$，

上图中，绿线是累计到达过程$A(t)$，红线是出发过程$D(t)$，$A(t)$始终位于$(\sigma, \rho)$线之下，所以$A(t)$和$D(t)$的竖直距离小于等于$(\sigma, \rho)$线和$D(t)$的竖直距离，所以我们可以约束

$$B_{\max} = \max \left(\sigma +\rho t - D(t)\right)$$

这是我需要的最大队列占用率，对应的还有$d_{\max}$，即任何位通过队列的最大延迟。

为了使分组没有丢失，我们需要

$$B\ge \sigma$$

如果$R_1\ge \rho$，那么$d(t)\le B/R_1$。

漏斗调节器

我接下来要告诉你的是，如果流量是我们所说的漏斗约束，并且路由器使用加权公平队列，那么当延迟保证是可能的。

那么这个漏斗约束是什么呢？漏斗可以实现$(\sigma,\rho)$ regulation，让我们来看看漏斗是什么？

我的分组到达这里，它们将进入分组缓冲区，而规则是，只有在有足够的token时，我才能发送或从缓冲区中取出分组，而token是以特定的速率$ho$在这里提供的，token桶的大小为$\sigma$。所以这里的token只是一个调度机制，token不会在电线下发出，这个token桶只是持有和实施调度机制的方式，目的是为了限制流量。

这是我们要在源头做的事情，当它在线路下发送分组时，我们要确保它们是$(\sigma,\rho)$ regulation，使用漏斗调节器：当且仅当它的桶里有足够的token时，它才能将它们发送到线路上，所以它将累积一个速率$ho$发出一个$\sigma$，换句话说，它能拥有的最大容量是$\sigma$。如果有足够的token允许发送该大小的分组，那么它将发送一个分组；一旦你发送了token，就用完了token，必须等待更多的token被放入。

你可以看到这将确保我们允许高达$\sigma$的突发事件，但从长远来看，速率只有$ho$，因此这将满足我们想要的约束条件。

把所有的东西放在一起

我们有一个来自A的$(\sigma,\rho)$约束流量，每个路由器以预先确定的速率和缓冲区大小运行WFQ。

分组进入路由器$Q_1$，在$R_1$得到服务，我们只要求$\sigma \le B$和$ho\le R_1$。同样，第二个路由器也是如此，以此类推。然后使用我们的端到端延迟公式，我们可以计算出整个路径的延迟。

你可能想知道$\sigma, \rho ,R_1, B$等的值是如何被告诉路由器的，以及谁首先设置了端到端延迟。有一个叫RSVP的IETF协议(IETF RFC 2205)可以做到这一点， 在教科书和维基百科上有很好的描述。

例子

在下面的网络中，应用程序希望1000字节分组的速率为10Mb/s，端到端延迟小于5ms。

一旦我们决定将每个路由器的延迟限制不超过2.15ms，我们就得出结论，我们需要确保：

• (a) 我们在每个路由器中的存储量不超过2960字节，这一点我们通过在源头设置等于2960字节的token桶来实现；

• (b) 路由器缓冲区至少可以容纳2960字节，这样我们就不会丢掉数据(如果我们愿意，我们可以让路由器缓冲区更大；只是我们不会使用它)；

解答：

固定延迟是分组延迟+传播延迟：

$$(1000\times8/10^9+1000\times8/10^8+1000\times8/10^9)+(120\times10^3/(2\times10^8))=0.696 \mathrm{ms}$$

因此排队延迟需要小于

$$5-0.696=4.304\mathrm{ms}$$

让我们选择将延迟平均分配给两个路由器：即每个路由器2.152ms。因此，

$$B > 10\mathrm{Mb/s} \times 2.15 2\mathrm{ms} = 21520\mathrm{bits} = 2690 \mathrm{bytes}= 21520 \mathrm{bits}$$

A需要用漏斗参数21520 bits和10Mb/s。

实际中

虽然在技术上可以做到这一点，但很少有网络真正控制端到端的延迟，为什么呢？

• 因为它的工作很复杂，需要协调。

• 在大多数网络中，超量供应和优先级的组合工作得很好。

但是我依然想告诉你延迟保证的工作原理，因为如果你能理解整个加权公平排队机制是如何工作的，以及我们如何提供端到端延迟保证，你就会对分组交换网络的排队动态有很多了解，而且这些想法中的一些很可能会在未来的某些网络中使用。

所以总之，如果我们知道队列的大小和服务的速率，那么我们可以通过它来限制延迟，我们可以选择队列的大小，使用加权公平队列，我们可以选择服务队列的速率，因此我们只需要一种方法来防止分组在途中被丢弃，为此我们使用了一个漏斗调节器，因此我们可以约束端到端的延迟。