1.1 数据流的模型

1.1.1 累积量函数、离散时间与连续时间模型

使用累积量函数R(t)描述数据流很方便：R(t)定义为在时间间隔[0,t]内观测到的比特数。为了方便，除非特别说明，否则令R(0)=0。函数R是广义递增的，即属于第3.1.3节定义的空间F，在这个空间中我们能够使用离散时间或连续时间模型。在真实系统中，总是存在一个最小的粒度（比特、字、信元或数据包），因此总是可以假设R(t)被定义在一个具有有限元素的离散时间集合上。然而，在连续时间上考虑问题通常会令计算更为简便（函数R可以连续，也可以不连续）。如果R(t)是连续函数，则得到一种流体模型（fluid model）。否则，按照习惯应令R(t)为右连续或左连续的（这在实际情况中造成的差异不大）[1]。图1.1展示了这些定义。

例：用广义递增函数R(t)描述流。除非特别说明，在本书中通常考虑下列几种模型。

● 离散时间模型：t∈N={0,1,2,3,…}。

● 流体模型：t∈R+=[0,+∞)，并且R(t)是连续函数。

● 连续时间模型：t∈R+，并且R(t)是左连续或右连续函数。

图1.1是输入和输出函数的例子，用于展示术语定义与惯例。R1和R∗₁表示连续时间的连续函数[流体模型，如图1.1(a)所示]，该函数中假设对于每个数据包以1个时间单位的持续时段逐比特到达。R2和R∗₂表示连续时间下数据包到达时刻不连续的函数[如图1.1(b)所示的时刻1、4、8、8.6和14]：在这里假设只有数据包已经被完全接收才算被观测到。实心圆点表示在不连续点上的值：按照惯例，假设函数是左连续或右连续的。R3和R∗₃表示离散时间模型的函数，如图1.1(c)所示，系统只有在时刻0、1、2才被观测。

我们假设R(t)具有导数则（这时得到了一个流体模型），此时r被称为率函数。然而在这一步可以看出，与率函数相比，累积量函数R更加简单。与使用标准代数不同，使用最小加代数不需要函数具有“好的”性质（例如具有导数）。

通过选择时隙δ，并且依据式（1.1）进行采样，总是可以将连续时间模型R(t)映射到离散时间模型S(n)，n∈N。

S(n)=R(nδ) （1.1）

通常这个结果损失了信息。对于逆映射，使用下面的公式。式（1.2）可以从S(n)导出连续时间模型[2]，其中，n∈N。

正如我们已经要求的那样，得到的函数R′总是左连续的。图1.1(b)展示了这种映射在δ=1，S=R3，R′=R2时的情形。

得益于式（1.1）的映射，任何连续时间模型的结果也可以应用于离散时间模型。除非另有证明，本书所有的结果既可应用于连续时间模型，又可应用于离散时间模型。离散时间模型一般用于ATM场景。反之，处理变长数据包通常使用连续时间模型（但不必是流体模型）。需要注意的是，处理变长数据包需要一些特定的机制，参见第1.7节的描述。

现在设想某个系统S，将其看作一个黑盒。S接收输入的数据，用它的累积量函数R(t)表示，并经过一段可变延迟后发送数据。将R∗(t)称为输出函数，其含义是系统S输出端的累积量函数。系统S可能有以下情况——单一的恒定速率缓冲器、复杂的通信节点，甚至是一个完整的网络。图1.1以不同形式展示了一个单服务队列的输入和输出函数，其中每个数据包接受服务恰好花费3个时间单位。对于输出函数R∗₁（流体模型），假设数据包能够在第1个比特到达后立即以恒定速率接受服务（直通假设），且能够逐比特观察数据包以恒定速率离去，例如，第1个数据包在时刻1与2之间到达，在时刻1与4之间离开。对于输出函数R∗₂，假设在数据包被全部接收之后立即为它提供服务，并且只有当数据包全部被发送后才算离开系统（存储转发假设）。这里，第1个数据包在时刻1之后立即到达，并且在时刻4之后立即离开。对于输出函数R∗₃（离散时间模型），第1个数据包在时刻2到达，在时刻5离开。

1.1.2 积压与虚拟延迟

从输入函数到输出函数，可以导出下面两个有价值的定量关系。

定义1.1.1（积压与虚拟延迟） 对于一个无损系统，在时刻t的积压为R(t)−R∗(t)；在时刻t的虚拟延迟为d(t)=inf{τ≥0:R(t)≤R∗(t+τ)}。

积压是系统中缓存的比特数。如果系统为单缓冲器，则积压是队列的长度。反之，如果系统更加复杂，则积压是假设能够同时观测输入和输出的情况下“正在传输”的比特数。时刻t的虚拟延迟的定义如下：对于某个在时刻t到达的比特，如果在它之前接收的所有比特先于它被服务，则这个在时刻t到达的比特应该经历的延迟为虚拟延迟。如图1.1(a)所示，积压被记为x(t)，是输入和输出函数之间的垂直偏差；虚拟延迟是水平偏差。如果输入/输出函数是连续的（流体模型），则容易看出R∗(t+d(t))=R(t)，且d(t)是满足该等式的最小值。

从图1.1中可以看到3种函数中积压和虚拟延迟的值略有不同。对于图1.1(a)，第1个数据包的最后1个比特的延迟是d(2)=2个时间单位。反之，在图1.1(b)中延迟是d(1)=3个时间单位。当然，这是由各自函数中的不同假设造成的。类似地，在图1.1(b)中第4个数据包的延迟是d（8.6）=5.4个时间单位，这包含2.4个时间单位的等待时间和3个时间单位的服务时间。反之，在图1.1(c)中，d(9)=6个时间单位，其差异源于离散化造成的精确度损失。

1.1.3 例子：播放缓冲器

累积量函数是研究延迟与缓冲的有力工具之一，下面以简单的播放缓冲器问题来展示累积量函数的作用，一个简单的播放缓冲器的例子如图1.2所示。例如，在模仿电路分析（参见引言）的案例中，设想一个分组交换网络，从信源以恒定比特率r承载以比特为单位的信息，采用流体模型。先设定一个系统S，带有输入函数R(t)=rt的网络。因为排队，该网络会存在一些可变延迟，所以输出R∗(t)不再具有恒定比特率r。如何能够再生成一个恒定比特率流呢？标准的机制是在播放缓冲器中平滑延迟的可变部分。具体操作如下：当数据的第1个比特在时刻dr(0)到达后，便被存储于缓冲器中，直到经历一段固定时间∆，其中是函数d的右极限[3]。接着，当缓冲器非空时，缓冲器以恒定比特率r接受服务。这里给出第二个系统S′，它带有输入R∗(t)和输出S(t)的网络。

假设网络延迟的可变范围被∆限制。这意味着对于每个时刻t，虚拟延迟（在本例中也是真实的延迟）满足

−∆≤d(t)−dr(0)≤∆

这样，因为采用流体模型，所以存在

r·(t−dr(0)−∆)≤R∗(t)≤r·(t−dr(0)+∆)

其中，两端的限制在图1.2(b)中以两条与R(t)平行的直线D1和D2表示。图1.2(b)表明，对于播放缓冲器S′，其输入R∗(t)总是在直线D2之上，意味着该播放缓冲器从未缺乏流量。这表明，输出S(t)由S(t)=r·(t−dr(0)−∆)给出。

正式的证明如下。我们使用反证法，假设缓冲器在一些时间饥饿，并且令t1为第1次饥饿发生的时刻。显然，播放缓冲器将在时刻t1为空，这样R∗(t1)=S(t1)。存在时间间隔[t1,t1+ε]，在此间隔内到达播放缓冲器的比特数少于rε，如图1.2(c)所示。于是d(t1+ε)>dr(0)+∆这个不等式是不可能成立的。时刻t的积压等于R∗(t)−S(t)，这是直线D1和直线D2之间的垂直偏差，记为2r∆。

我们已经展示了播放缓冲器能够消除由网络造成的延迟变化，总结如下。

命题1.1.1 设想一个速率为r的恒定比特率流。这个流受到网络的影响，导致产生可变延迟，但是无损。得到的流被放入一个播放缓冲器，该播放缓冲器将流中的第1个比特延迟∆，并且以速率r读取该流。假设由网络造成的延迟可变性在∆的界限之内，则：

（1）播放缓冲器从不饥饿，并且以速率r形成一个恒定速率输出；

（2）缓冲器的容量为2r∆就足以避免溢出。

第5章将采用本章介绍的网络演算概念更仔细地研究播放缓冲器。