### 网络演算(Network Calculus)：一种确定性排队系统的理论
#### 简介
《网络演算》是一本关于确定性排队系统理论的电子书，由Jean-Yves Le Boudec和Patrick Thiran编写。该书通过研究到达曲线(service curves)和服务曲线(arrival curves)来对互联网中的排队网络系统进行建模，并提供了一种确定性的性能边界分析方法。本书不仅适用于学术研究人员，也适用于从事网络设计和优化工作的工程师。
#### 核心概念与原理
##### 数据流模型
**累积函数与时间模型**
- **累积函数**是网络演算的基础之一，用于表示数据随时间累积的数量。累积函数可以分为离散时间和连续时间两种模型。
- **离散时间模型**通常用于描述分组交换网络中的数据流，例如互联网。
- **连续时间模型**更适用于模拟连续信号或流量的累积过程，如视频流等实时应用。
**背板(backlog)与虚拟延迟(virtual delay)**
- 背板是指在某一时刻，网络节点中尚未被发送的数据量。
- 虚拟延迟是指一个包从进入系统到被服务的时间差，它是理解系统性能的关键指标。
**示例：播放缓冲区(playout buffer)**
- 播放缓冲区是一种特殊类型的背板，用于存储视频流中的数据包，确保播放端可以平滑地显示视频内容。通过调整播放缓冲区的大小，可以在传输延迟和流畅性之间取得平衡。
##### 到达曲线(Arrival Curves)
**到达曲线定义**
- 到达曲线用于描述数据流到达网络节点的特性。它是一个上界，表明了数据流在任意时间间隔内可能达到的最大数据量。
**漏桶模型(Leaky Bucket)与通用单元速率算法(Generic Cell Rate Algorithm)**
- **漏桶模型**是最常见的到达曲线之一，它限制了数据流的平均速率。
- **通用单元速率算法(GCRA)**则是一种更为灵活的方法，能够适应突发流量，同时保证长期的平均速率不超过特定值。
**子加性(Sub-additivity)与到达曲线**
- 子加性是评估多个数据流合并时性能的一个重要性质。如果两个或多个数据流满足各自的到达曲线约束，则它们的合并也应满足相应的约束条件。
**最小到达曲线(Minimum Arrival Curve)**
- 最小到达曲线是指所有满足给定到达曲线约束的数据流中速率最小的那个。它对于理解和优化系统性能非常关键。
##### 服务曲线(Service Curves)
**服务曲线定义**
- 服务曲线描述了一个网络节点能够提供的服务水平，即在网络节点中数据包被服务的速率下限。服务曲线可以帮助我们计算数据包的延迟和背板大小。
**经典的服务曲线例子**
- 例如，恒速服务曲线(constant-rate service curve)表示网络节点以恒定的速度服务数据包。
- 另一种常见的服务曲线是基于优先级的服务曲线(priority-based service curve)，它可以为不同优先级的数据流提供不同的服务质量。
#### 网络演算基础
- 网络演算的基础部分涵盖了如何利用到达曲线和服务曲线来分析和设计排队网络系统。
- 这包括对基本概念的理解，以及如何运用这些概念来推导出系统性能的确定性界限。
本书的作者们通过不断的修订和改进，确保了内容的准确性和实用性。例如，在2002年1月14日的更新中，作者增加了对广义重排节点(Generic Rearrange Nodes, GR nodes)更好的覆盖，并修复了一些已知的问题。此外，书中还介绍了一些高级主题，如非先进先出(non-first-in-first-out, non-FIFO)节点的性质以及在区分服务(Differentiated Services, DiffServ)环境下的应用等。
总而言之，《网络演算》这本书为读者提供了深入理解网络性能分析所需的理论工具和技术手段。无论是对于学生、研究人员还是网络工程师而言，这都是一本不可或缺的参考书籍。
