1.3 服务曲线

1.3.1 服务曲线的定义

我们已经看出综合服务网络的第一个原则是用到达曲线约束流。为了提供预留，网络节点反过来需要为流提供一些保障，这是由数据帧的调度[5]完成的。本节介绍和研究了服务曲线的概念，利用这一概念可以抽象出数据帧调度的详细内容。由于服务曲线比到达曲线更加抽象，因此本节将结合一些例子进行解释。

首先，设想一个简单的通用处理器共享（Generalized Processor Sharing,GPS）[6]节点的调度器的例子，这里只给出简单的定义，第2章将给出更多细节。GPS节点并行服务多条流，假设每条流都被分配了给定的速率。可以保证的是，流在节点上产生积压所持续的t时间段内将获得至少等于rt的服务量，其中r为分配给流的速率。GPS节点是一个理论概念，实际上无法实现，因为它依赖于流体模型，而在真实网络中使用的是数据帧。第2.1节将介绍如何解决实际方案与GPS模型之间的差异。设想一条输入流R经过一个速率为r的GPS节点后，对应的输出流为R∗，另外假设节点的缓冲区足够大，因此不会发生溢出，读者将在本节中学习如何计算满足上述假设的缓冲区的大小。对于有损系统的分析参见第9章的内容。在这些假设下，对于所有时刻t，令t0为距离时刻t最近的忙周期的开始时刻，根据GPS的假设，有

R∗(t)−R∗(t0)≥r(t−t0)

像往常一样假设R为左连续的，那么在时刻t0，流量的积压为0，因此有R(t0)−R∗(t0)=0。结合前一个公式，有

R∗(t)−R(t0)≥r(t−t0)

因此，对于所有时刻t，有，也可以写成

R∗≥R⊗γr,0 （1.7）

注意，GPS节点的局限性案例是速率为r的恒定比特率服务器，该服务器专门用于服务单条流。第2章将详细研究GPS。

接下来介绍第二个例子，假设关于网络节点唯一的信息是，给定流R的比特的最大延迟，由某个定值T限制，并按先进先出的顺序服务流的比特。我们将在第1.5节中介绍，这种假设与一族被称为“最早截止期限优先（Earliest Deadline First,EDF）”的调度器一起使用。可以将该假设转换为对于所有t的延迟界限为d(t)≤T。由于R∗总是广义递增的，因此根据d(t)的定义可以得出R∗(t+T)≥R(t)。相反地，如果R∗(t+T)≥R(t)，那么d(t)≤T。换言之，最大延迟受到T的限制等价于对于所有t，有R∗(t+T)≥R(t)，又可以写为

R∗(s)≥R(s−T),s≥T

第3章中介绍的“冲激”函数δT定义为：若0≤t≤T，则δT(t)=0；若t>T，则δT(t)=+∞。该函数具有以下性质：对于t≥0定义下的任意广义递增函数x(t)，若t≥T，则(x⊗δT)(t)=x(t−T)；否则，(x⊗δT)(t)=x(0)。因此，关于最大延迟的条件，可以写成

R∗≥R⊗δT （1.8）

对于上述的两个例子，存在相同形式的输入/输出关系[式（1.7）和式（1.8）]，这表明服务曲线的定义确实可以提供有用的结果。

定义1.3.1（服务曲线） 设想一个系统S，以及一条经过S的输入和输出函数为R和R∗的流。当且仅当β为广义递增函数，且满足β(0)=0和R∗≥R⊗β时，可以认为S为这条流提供的服务曲线是β。

图1.8展示了上述定义，输出R∗必须位于R⊗β之上，R⊗β为所有曲线的下包络。上述定义条件也可以表示为，β为广义递增函数，满足β(0)=0，且对于所有t≥0，有

实际上，如果β是连续的，则可以避免使用下确界。以下命题可以由定理3.1.8直接得到。

命题1.3.1 若β是连续的，则服务曲线的属性意味着对于所有t，可以找到t0≤t，使得

R∗(t)≥Rl(t0)+β(t−t0) （1.9）

其中为在t0的左极限，若R为左连续的，那么Rl(t0)=R(t0)。

对于恒定速率的服务器（以及任何严格服务曲线），可以将式（1.9）中的t0视为忙周期的开始；对于其他情况，则t0是未知的。然而，某些情况下，可以选择随t递增的t0。

命题1.3.2 若服务曲线β是凸的，那么可以找到某个广义递增函数τ(t)，使得式（1.9）中可以取t0=τ(t)。

注意，由于假设服务曲线为广义递增的，因此凸函数β必须为连续的。因而可以应用命题1.3.1的结论。

证明：这里给出当R为左连续时的证明，更一般情况下的证明基本上是相同的，仅涉及一些ε削减。考虑t1<t2，且当t=t1时，令τ1为式（1.9）中t0的值。同时考虑任意t′≤τ1，根据τ1的定义，有

R∗(t′)+β(t1−t′)≥R∗(τ1)+β(t1−τ1)

因此

R∗(t′)+β(t2−t′)≥R∗(τ1)+β(t1−τ1)−β(t1−t′)+β(t2−t′)

由于β为凸的，因此对于任意4个满足a≤c≤b、a≤d≤b以及a+b=c+d的数总有

β(a)+β(b)≥β(c)+β(d)

感兴趣的读者可以通过画图进行验证。将以上式子应用于a=t1−τ1、b=t2−t′、c=t1−t′、d=t2−τ1，有

R∗(t′)+β(t2−t′)≥R∗(τ1)+β(t2−τ1)

上式对所有t′≤τ1均成立。接下来固定t2，对于所有的t′≤t2，求R∗(t′)+β(t2−t′)的最小值。对于某些t′≥τ1，上式可以达到最小值。

第1.4节将给出服务曲线，保证服务曲线与到达曲线约束的结合构成综合服务网络中使用的确定性边界的基础。在此之前，先给出一个在实际中使用的经典服务曲线的示例。

1.3.2 经典服务曲线示例

保证延迟节点 对于第1.3.1节中第二个例子的分析可以被重现，表述如下。

命题1.3.3 对于无损的比特处理系统，任何比特的延迟都由某个定值T限制，等价于系统向流提供δT的服务曲线。高低优先级非抢占式服务如图1.9所示。

图1.9的说明：两条优先级流（H和L）在队列头部（Head of the Line,HOL）接受可抢占式服务。高优先级的流受到达曲线α的约束。

不可抢占式优先级节点 设想一个服务两条流RH(t)和RL(t)的节点，第一条流具有高于第二条流的不可抢占式优先级（见图1.9）。该示例说明了某些流类型比其他流类型具有高优先级时所使用的通用框架，如因特网的区分服务[7]。服务器的速率是恒定的，等于C；称R∗_H(t)和R∗_L(t)为两条流的输出。对于第一条高优先级流，在某个时刻t，令s为高优先级流积压周期的起始时刻。高优先级的服务可以因在s之前不久到达的低优先级数据帧延迟。但是，只要这个数据帧被服务完毕，服务器就会专用于高优先级。只要有高优先级的流排队，在时间区间(s,t]上，输出的比特数为C(t−s)。因此

R∗H(t)−R∗H(s)≥C(t−s)−lLmax

其中lLmax为低优先级数据帧的最大帧长。根据s的定义，有R∗H(s)=RH(s)，因此

R∗_H(t)≥RH(s)+C(t−s)−lLmax

又因为

R∗_H(t)−RH(s)=R∗_H(t)−R∗_H(s)≥0

从而可以得到

R∗_H(t)≥RH(s)+［C(t−s)−lLmax］+

函数被命名为“速率–时延”函数，其中速率为C、延迟为（参见参考文献[8]，本书中记为）。因此该函数为高优先级流的服务曲线。

接下来分析低优先级流。为了确保不出现饥饿现象，假设高优先级流受到到达曲线αH的约束。对于任意时刻t，令s′为服务忙周期的起始时刻（注意s′≤s）。在时刻s′，两条流的积压都为0，即满足R∗_H(s′)=RH(s′)和R∗_L(s′)=RL(s′)。在时间间隔(s′,t]上，输出为C(t−s′)。因此

R∗_L(t)−R∗_L(s′)≥C(t−s′)−[R∗_H(t)−R∗_H(s′)]

另外，由于

R∗_H(t)−R∗_H(s′)=R∗_H(t)−RH(s′)≤RH(t)−RH(s′)≤αH(t−s′)

以及R∗_H(t)−R∗_H(s′)≥0，那么有

R∗_L(t)−RL(s′)=R∗_L(t)−R∗_L(s′)≥S(t−s′)

其中，S(u)=[Cu−αH(u)]+。因此，若S为广义递增的，那么低优先级流获得的服务曲线为函数S。进一步假设αH=γr,b，即高优先级流受到漏桶控制器或GCRA的约束。在这种情况下，低优先级流的服务曲线S(t)为速率–时延函数βR,T(t)，其中R=C−r，。

因此，存在以下命题。

命题1.3.4 设想一个速率为C的恒定比特率服务器，它服务高、低优先级的两条流，并且高优先级流是非抢占式的。那么高优先级流具有速率为C和延迟为的速率–时延服务曲线，其中lLmax为低优先级流的最大帧长。此外，若高优先级流是γr,b-平滑的，且r<C，那么低优先级流具有速率为C−r和延迟为的速率–时延服务曲线。

这个例子表明了速率–时延服务曲线的重要性。在第2章（定理2.1.2）可以看到，实际情况下所有GPS的实现都提供了速率–时延类型的服务曲线。

严格服务曲线（strict service curve）对于一类重要的网络节点，服从以下的理论框架。

定义1.3.2（严格服务曲线） 如果在任意积压期间u内，流的输出至少等于β(u)，那么认为系统S为流提供了严格服务曲线β。

GPS节点作为这种示例，提供形式为β(t)=rt的严格服务曲线，利用第1.3.1节GPS节点示例中相同的忙周期分析，可以证明以下命题。

命题1.3.5 如果节点为某条流提供的严格服务曲线为β，那么β也是这条流的服务曲线。

严格服务曲线的性质提供了一种可视化服务曲线概念的边界方式：在这种情况下，β(u)是忙周期内保证的最小服务量。但是注意，定义1.3.1给出的服务曲线定义更加通用。贪婪整形器（见第1.5.2节）是一个将整形曲线作为服务曲线的系统示例，但它并不满足严格服务曲线的属性。相反，在本书后文可以看到，只有在采用严格服务曲线的定义时，某些属性才成立。第7章将给出严格服务曲线的更具一般性的讨论。

可变容量节点 设想一个为某条流提供可变服务容量的网络节点。在某些情况下，可以通过累积量函数M(t)对容量进行建模，其中M(t)为时刻0∼t为流提供的总服务容量。例如，对于ATM系统，将M(t)视为时刻0∼t可用于发送流信元的时隙数。假设节点的缓冲足够大，使溢出不可能发生，那么可以给出以下显而易见的命题，但该命题在实际应用中具有重要的意义。

命题1.3.6 如果对于某个固定的函数β，且对于所有0≤s≤t，可变容量满足最小的保证形式如下

M(t)−M(s)≥β(t−s) （1.10）

那么β为严格服务曲线。

因此，β也是该特定流的服务曲线。利用可变容量节点的概念建立服务曲线属性，也是一个便捷方法。对于实时系统（而不是通信网络）的应用，请参阅参考文献[9]。

第4章将提到可变容量节点的输出可由下式给出

最后，回到优先级节点，有以下命题。

命题1.3.7 命题1.3.4中针对高优先级流的服务曲线是严格的。

该命题的证明留给读者，它依赖于如下的事实，即恒定速率服务器是一种整形器。