引言

网络演算（network calculus）是近年发展出来的一套分析方法，这套方法对人们解决网络中流（flow）的问题提供深层次的理解。网络演算的基础是双子（dioid）代数理论，特别是最小加（min-plus）双子（也被称为最小加代数）。采用网络演算，我们能够理解综合服务（integrated service）网络、窗口流控、调度，以及缓冲或延迟定量的一些基本属性。

本书分为3个部分。第一部分（第1章和第2章）是关于网络演算的初级教程。该部分自成体系，可用作本科生或研究生入门课程的教材，但初学者需要先学习线性代数和微积分等本科生课程。第1章给出了初级教程中主要的一组分析结果——到达曲线（arrival curve）和服务曲线（service curve），以及功能强大的串联分析结果，这一章分别对这些结果进行介绍、推导并以图表进行展示。在合理的框架下，这一章给出了一些实用的定义，例如漏桶（leaky bucket）模型、通用信元速率算法，并推导了它们的基本属性。这一章还对整形器的本质属性进行了推导。第2章展示了第1章给出的基本结果如何应用于互联网。例如，说明了为什么互联网综合服务能够将任意路由器抽象为一种“速率–时延”服务曲线。这一章还给出了用于区分服务（differentiated service）的一些性能界限的理论基础。

第二部分介绍了本书各章都会用到的基础知识。第3章包含相关的初级数学知识。例如，以简明的方式阐释了最小加卷积（min-plus convolution）和次可加闭包（sub-additive closure）的概念。第3章引用了第一部分的大量内容，但仍是自成体系的。第3章的目的是提供便于读者进一步使用网络演算方法的数学知识。第4章给出了最小加代数的一些高级的结论，涉及不动点方程式等在第一部分未提到的内容。

第三部分包含一些进阶的内容，适合用于研究生课程。第5章展示了在保证服务的网络中如何应用网络演算确定优化的回放延迟（playback delay），这种方法解释了如何确定多媒体流的基本性能界限。第6章介绍了带有聚合调度（aggregate scheduling）的系统。尽管本书中介绍的网络演算的大部分内容适用于采用调度器将流分隔开的系统，但仍能够从聚合调度系统推导出一些有趣的结论。第7章进一步扩展了第1章对服务曲线的定义，对自适应保证（adaptive guarantee）进行分析，自适应保证被用于互联网区分服务。第8章分析时变整形器，时变整形器是第1章基本结论的扩展，考虑到由于自适应方法会导致系统参数发生变化，这一章给出了一种关于可重新协商预留服务的应用。最后，第9章介绍如何应对有损系统，其基础的结论是给出一种在流系统中表达损失的新方法，这种新方法能够用于在复杂系统中界定丢弃数据包损失的概率或拥塞的概率。

网络演算属于“异构代数”（exotic algebra）或“专题代数”（topical algebra）类代数方法。这是一类数学结果的集合，通常具有很高的描述复杂性（description complexity），可用于解释人造的信息系统，这些系统包含并发程序、数字电路，当然也包含通信网络。Petri网也属于这类数学结果。对于这个有前景的研究领域的一般讨论，请参考相应的概述性论文[1]和专著[2]。

我们希望能够使读者清楚地认识到：从本书所用的方法中，可以推导出一整套在很大程度上尚未被发现的、基础性的关系。例如在第1章推导出的“整形器保持到达约束”或“突发一次性准则”（pay burst only once）的结论具有相应的物理解释，并且对网络工程师而言具有实践上的重要意义。

本书所有的结果都是确定性的。更先进的网络演算专著应揭示随机系统与本书推导的确定关系之间的关联，但这些内容超出了本书的范围。感兴趣的读者可参阅参考文献[2,3]。本书的最后还提供了书中定义的术语的索引。

网络演算：计算机网络的系统论

接下来将要重点介绍网络演算与所谓的“系统论”（system theory）之间的相似关系。如果读者不熟悉系统论，可以跳过这些内容。

网络演算是在计算机网络中出现的确定性排队系统（deterministic queuing system）理论，它也被看作应用于计算机网络的系统论。网络演算与常规（已成功应用于电子电路设计中）的系统论的主要区别在于，网络演算考虑了另一种代数结构，对算子（operator）进行了如下替换：加法（+）替换成计算最小（min），乘法（×）替换成加法（+）。

在进入本书的主题之前，我们简要地展示一些最小加系统理论与常规系统理论之间的相似点与区别，其中前者应用于本书的通信网络，后者应用于电子电路。

让我们从一个非常简单的电路谈起，例如图0.1(a)所示的“电阻电容”（Resistor Capacitor,RC）电路单元。如果输入电压信号x(t)∈R，则这个简单电路的输出y(t)∈R是x与该电路冲激响应的卷积，其中冲激响应为，t≥0。

图0.1的说明：RC电路与贪婪整形器在它们各自的代数结构下是基本的线性系统。

现在考虑通信网络的节点，将其理想地抽象为一个（贪婪）整形器（greedy shaper），如图0.1(b)所示。（贪婪）整形器是一种将输入信号x(t)强行约束为某种输出信号y(t)的装置，其中输出信号y(t)服从由流量包络σ（整形曲线）给定的速率集，（贪婪）整形器会导致经过缓冲器的流的时延增大。此处所指的输入和输出“信号”是累积流，定义为在时间区间[0,t]观测到的数据流的比特数。输入和输出函数是关于参数t非递减的，参数t可以是连续或离散的。在本书中我们将看到x和y的关系如下式所示。

该关系定义了σ和x的最小加卷积。

在常规系统理论中，卷积既满足交换律又满足结合律，该属性很容易将对小规模电路的分析扩展到对大规模电路的分析。例如，图0.2(a)所示的串联线性电路的冲激响应是各个基本单元电路冲激响应的卷积。

在第1章中，我们将发现同样的属性也适用于贪婪整形器。图0.2(b)所示的第2个整形器的输出为y(t)=(σ⊗x)(t)，其中

这将帮助我们理解前文提到的“突发一次性准则”。

图0.2的说明：两个串联的线性电路的冲激响应是它们各自冲激响应的卷积，两个串联的整形器的整形曲线是它们各自整形曲线的卷积。

因此，“常规”的电路和系统理论与网络演算存在明显的相似之处。但二者也存在重要的区别。

首要的区别在于线性系统对多个输入之和的响应。这对于线性电路[例如用于从加性噪声n(t)中将信号x(t)去噪的线性低通滤波器，如图0.3(a)所示]和计算机网络[例如具有输出链路容量C的缓冲器节点的链路，其中研究者所关心的流x(t)与背景流量n(t)多路复用，如图0.3(b)所示]，都是非常普遍的情况。

图0.3的说明：线性电路对两个输入之和x(t)+n(t)的响应ytot(t)是它们各自的响应之和，见图0.3(a)；然而，聚合流量贪婪整形器对两个输入之和x(t)+n(t)的响应ytot(t)不是它们各自的响应之和，见图0.3(b)。

因为图0.3(a)所示的电子电路是线性系统，所以两个输入之和的响应是各自信号的独立响应之和。定义y(t)是线性系统对纯信号x(t)的响应，yn(t)是对噪声n(t)的响应，并且ytot(t)是对被噪声干扰的信号x(t)+n(t)的响应。则ytot(t)=y(t)+yn(t)。这种有用的属性已经应用于设计最优线性系统，以尽可能地滤除噪声。

如果在输出链路上流量尽快地接受先入先出（First Input First Output,FIFO）的服务，则图0.3(b)所示的节点等效于贪婪整形器，其整形曲线对于t≥0，有σ(t)=Ct。因此它也是线性系统，只不过这个情况下是在最小加代数的范畴里的线性系统。这意味着，对两个输入中较小者的响应是系统对每个单独输入的最小响应。然而，这也意味着对两个输入之和的响应不再是系统对每个单独输入的响应之和，因为现在x(t)+n(t)是对两个输入x(t)和n(t)进行非线性运算，所以加法起到了常规系统论中乘法的作用。这样确实很遗憾，线性属性不能被应用于聚合x(t)和n(t)的情况。因此，对于多路复用的聚合流，我们掌握的知识仍然很少。第6章将向读者介绍一些新的数学成果，以及一些看上去简单但至今仍然有待解决的问题。

在电子学和计算机网络中均会非常频繁地遇到非线性系统。然而，电路理论和网络演算对非线性系统的处理有很大差异。

以基本非线性电路为例，该电路只包含一个双极晶体管（Bipolar Junction Transistor,BJT）的晶体管放大电路，如图0.4(a)所示。为了分析这种非线性电路，电子工程师首先输入x∗（这是直流分析，x∗为一个固定的电压常量），并计算该电路的静态工作点y∗。接下来，电子工程师在静态工作点附近将非线性元件（晶体管）线性化，以得到所谓的小信号模型，它是冲激响应h(t)的线性模型（这是交流分析）。现在，xlin(t)=x(t)−x∗是在x∗小范围变化的时段内的时变函数，因此，ylin(t)=y(t)−y∗可由ylin(t)≈(h⊗xlin)(t)逼近得到，该模型如图0.4(b)所示。将输入信号限制在工作点附近的小范围内变化，这样就绕过了完全非线性分析的难点。于是可以采用线性化模型，该模型足以满足对我们所关注的性能测度进行评价的准确性要求，如分析放大器的增益。

图0.4的说明：一个基本非线性电路[图0.4(a)]被一个（简化的）小信号线性模型[图0.4(b)]替代；一个带有缓冲窗口流控制器的非线性网络[图0.4(c)]被一个最坏情况下的线性系统[图0.4(d)]替代。

在网络演算中，我们不将输入分解为一个小范围时变的部分和另一个较大但不变的部分。然而，我们确实采用线性系统替代了非线性元件，但现在前者是非线性系统的下界。第1章将介绍以服务曲线表达的例子：非线性系统y(t)=Π(x)(t)被线性系统ylin(t)=(β⊗x)(t)替代，其中β表示该服务曲线。这个模型对于所有t≥0和所有可能的输入x(t)存在ylin(t)≤y(t)。这也将允许我们计算性能测度，例如非线性系统中的延迟和积压。一个例子是图0.4(c)展示的窗口流控制器，第4章将对其进行分析。一条流x通过网络中的缓冲窗口流控制器馈入，实现某种映射y=Π(x)。缓冲窗口流控制器限制网络中准许输入的数据量，通过这种方法，网络中传输的数据的总量总是小于某个正数（窗口的大小）。我们不知道确切的映射 Π，假设知道这条流的一条服务曲线β，这样就能够用图0.4(d)的线性系统替代图0.4(c)中的非线性系统，以得到关于端到端延迟或传输中数据量的确定性界限。

阅读本书的时候，熟悉“常规”的电路与系统理论的读者将会发现两种系统论之间还有其他的相似或不同之处。然而，必须强调的是，读者并不需要预习系统论的知识，也可以学会本书讲解的网络演算知识。

致谢

我们衷心地感谢学者张正尚（Cheng-Shang Chang）和勒内·利奥纳多·克鲁兹的开创性的工作，我们之间的讨论对本书产生了深刻的影响。我们感谢安娜·沙尔尼（Anna Charny）、西尔维娅·乔达诺（Silvia Giordano）、奥利维尔·维舍尔（Olivier Verscheure）、弗雷德里克·沃尔姆（Frédéric Worm）、容·贝内（Jon Bennett）、肯特·本森（Kent Benson）、维桑特·乔尔维（Vicente Cholvi）、威廉·库尔特内（William Courtney）、朱昂·埃查格（Juan Echaguë）、费利克斯·法卡斯（Felix Farkas）、热拉尔·赫布特恩（Gérard Hébuterne）、米兰·沃伊诺维奇（Milan Vojnović）和张志力（Zhi-Li Zhang）提供的卓有成效的协助。在这里还要感谢与拉杰夫·阿格拉沃尔（Rajeev Agrawal）、马修·安德鲁斯（Matthew Andrews）、弗朗索瓦·巴切利（François Baccelli）、纪尧姆·于尔瓦（Guillaume Urvoy）和洛塔尔·蒂勒（Lothar Thiele）之间的交流。感谢霍利·科里亚蒂（Holly Cogliati）帮助准备手稿。