网络演算 互联网确定性排队系统理论

1.作者经验丰富，内容专业
本书作者让-伊夫·勒布代克是继网络演算提出者克鲁兹去世之后在网络演算领域的代表人物，作品具有行业代表性。
2.由浅入深，通俗易懂
作者由浅入深的将自己对于网络演算中的经验与心得写于本书，对于通信计算机专业的研究生以及从业人士具有参考价值。
4. 适合小白学习
不需要预习系统论的知识，也可以学习本书讲解的网络演算知识。

本书主要阐述网络演算的理论，介绍对互联网确定性排队系统性能的界限分析方法。第一部分结合应用实例，给出网络演算综述及概念解释，介绍时延、积压、输出流量行为等界限分析方法。第二部分详细介绍网络演算的形式化数学理论研究，基于最小加代数的分析体系，对更通用、更复杂的系统进行建模和分析。第三部分介绍结合互联网特性的进阶研究，包括很优多媒体平滑、聚合调度、自适应保证与数据包尺度速率保证、时变整形器、有损系统等场景，给出积压等界限分析方法及其结果。
本书开创性地确立了互联网确定性排队系统的理论基础，可供通信、计算机网络专业的研究生学习，亦可供从事互联网、实时系统等设计、分析、验证的工程师参考。

让-伊夫·勒布代克（Jean-Yves Le Boudec）
1984年获得法国雷恩大学博士学位。先后在加拿大贝尔北方研究中心、IBM苏黎世实验室工作。1994年加入瑞士洛桑联邦理工学院担任副教授，目前是洛桑联邦理工学院教授， IEEE研究员。曾经在许多会议和期刊的编辑委员会任职，包括ACM SIGCOMM，ACM SIGMETRICS，IEEE INFOCOM，Performance Evaluation和ACM/IEEE Transactions on Networking等。著有Performance Evaluation of Computer and Communication Systems等专著。

帕特里克·蒂兰（Patrick Thiran）
1996年获得洛桑联邦理工学院博士学位。2000—2001年在美国加利福尼亚州伯林格姆的Sprint优选技术实验室工作，目前为洛桑联邦理工学院的电气工程教授。担任IEEE通信领域精选期刊的编辑，在网络领域不同会议的程序委员会中任职，包括ACM SIGCOMM，ACM SIGMETRICS，AMC IMC，ACM CoNEXT和IEEE INFOCOM，曾担任AMC IMC 2011和ACM CoNEXT 2012的TPC主席。

译者简介
李峭，北京航空航天大学工学博士，北京航空航天大学电子信息工程学院副教授，曾在沈阳飞机设计研究所担任客座航空电子工程师，主要研究领域涉及实时系统、数字通信、数据通信和计算机网络，承担过多项航空电子综合化网络工程课题。从2002年开始学习并熟悉网络演算理论，并将其应用于航空电子网络（如AFDX网络和TTE网络）技术的推广工作中。目前主要研究时间敏感网络（TSN）和航空电子无线机舱内互连（WAIC）网络，致力于利用确定性网络演算和随机网络演算进行网络性能评价。

赵露茜，北京航空航天大学工学博士，2017年前往丹麦技术大学从事博士后研究工作，获玛丽·居里学者称号，2019年年底开始在慕尼黑工业大学从事科研工作。主要研究方向为实时通信网络形式化方法（确定性网络演算）下实时性能的分析以及网络配置研究，主要研究对象为针对实时和安全关键性应用的以太网新一代子标准时间敏感网络（TSN）。在相关领域发表10余篇论文，谷歌学术h因子为10。

何锋，北京航空航天大学工学博士，北京航空航天大学电子信息工程学院副教授，2014～2015年作为公派访问学者赴法国INP-ENSEEIHT（法国工程师学校，图卢兹大学成员）从事合作研究。主要研究领域涉及实时通信系统、嵌入式网络、实时性能评估（主要聚焦于航空电子和车载电子领域），以及航空电子综合技术。已出版2部专著，发表76篇论文。

赵琳，北京航空航天大学工学博士，中国航天科工集团有限公司工程师。主要研究方向为安全关键性网络和实时网络性能评估，近3年在通信与信息系统专业领域发表7篇学术论文，包含2篇SCI检索期刊论文和1篇很好会议论文.

周璇，北京航空航天大学电子信息工程学院工学学士，现攻读北京航空航天大学信息与通信工程博士学位。主要研究领域为实时通信系统调度设计与性能评估，已在实时计算机网络领域发表5篇学术论文，包含1篇很好会议论文。

审校者简介
张嘉怡：清华大学博士。在华为公司从事网络演算的应用研究、网络建模和性能评估工作。
王心远：河北工业大学硕士。在华为公司从事高速以太接口、网络演算的研究工作。
王童童：瑞典林雪平大学硕士。在华为公司从事网络SLA保障关键技术研究和标准化工作，担任IEEE 802.1DF编委。

第 一部分 网络演算基础知识
第  1 章 网络演算  3
1.1  数据流的模型  3
1.1.1  累积量函数、离散时间与连续时间模型  3
1.1.2  积压与虚拟延迟  6
1.1.3  例子：播放缓冲器  6
1.2
到达曲线  8
1.2.1  到达曲线的定义  8
1.2.2  漏桶模型和通用信元速率算法  12
1.2.3  次可加性和到达曲线  17
1.2.4  最小到达曲线  21
1.3  服务曲线  23
1.3.1  服务曲线的定义  23
1.3.2  经典服务曲线示例  26
1.4
网络演算基础  29
1.4.1  3 种界限  29
1.4.2  界限是紧致的吗  35
1.4.3  级联  36
1.4.4  积压界限的改进  38
1.5  贪婪整形器  40
1.5.1  定义  40
1.5.2  贪婪整形器的输入/输出特性  40
1.5.3  贪婪整形器的性质  43
1.6  优选服务曲线、可变延迟和固定延迟  45
1.6.1  优选服务曲线  45
1.6.2  积压造成的延迟  49
1.6.3  可变延迟与固定延迟  51
1.7  处理变长数据包  52
1.7.1  变长数据包引入不规则性的示例  52
1.7.2  打包器  54
1.7.3  贪婪整形器和打包器之间的关系  59
1.7.4  打包贪婪整形器  62
1.8  无损有效带宽和等效容量  68
1.8.1  流的有效带宽  68
1.8.2  等效容量  70
1.8.3  示例：FIFO 多路复用器的接受域  71
1.9
定理  1.4.5 的证明  73
1.10
参考文献说明  76
1.11  习题  78
第  2 章 网络演算应用于互联网  86
2.1  GPS 和保证速率节点  86
2.1.1  数据包调度  86
2.1.2  GPS 及其实际运用  87
2.1.3  GR 节点和优选加代数方法  90
2.1.4  GR 节点的级联  93
2.1.5  证明  95
2.2  IETF 的综合服务模型  97
2.2.1  保证服务  97
2.2.2  互联网路由器的综合服务模型  97
2.2.3  通过 RSVP 进行预留设置  98
2.2.4  流建立算法  101
2.2.5  多播流  102
2.2.6  ATM 流建立  103
2.3  可调度性  103
2.3.1  EDF 调度器  104
2.3.2  SCED 调度器  106
2.3.3  缓冲需求  112
2.4  应用于区分服务  113
2.4.1  区分服务  113
2.4.2  显式的 EF 延迟界限  114
2.4.3  带阻尼器的聚合调度界限  121
2.4.4  静态最早时间优先  125
2.5  参考文献说明  126
2.6  习题  126
第二部分  数学知识
第  3 章 基本最小加演算和优选加演算  131
3.1  最小加演算  131
3.1.1  下确界和求最小  131
3.1.2  双子代数  133
3.1.3  广义递增函数的类型  134
3.1.4  广义递增函数的伪逆  137
3.1.5  凹函数、凸函数与星形函数  138
3.1.6  最小加卷积  139
3.1.7  次可加函数  146
3.1.8  次可加闭包  149
3.1.9  最小加解卷积  154
3.1.10  以时间反转表达的最小加解卷积  159
3.1.11  水平偏差与垂直偏差  162
3.2  优选加演算  163
3.2.1  优选加卷积与解卷积  163
3.2.2  在优选加代数中最小加解卷积的线性  164
3.3  习题  165
第  4 章 最小加系统论和优选加系统论  166
4.1  最小加算子和优选加算子  166
4.1.1  矢量的记法  166
4.1.2  算子  168
4.1.3  算子的类型  169
4.1.4  上半连续和下半连续算子  171
4.1.5  保序算子  172
4.1.6  线性算子  172
4.1.7  因果算子  177
4.1.8  平移不变算子  178
4.1.9  幂等算子  180
4.2  算子的闭包  180
4.3  不动点方程（空间方法）  184
4.3.1  主要理论  184
4.3.2  应用的例子  186
4.4  不动点方程（时间方法）  191
4.5  小结  192
第三部分  网络演算进阶
第  5 章 很优多媒体平滑  195
5.1  问题设定  195
5.2  无损平滑约束  197
5.3  延迟与回放缓冲区大力度优惠要求  198
5.4  很优平滑策略  199
5.4.1  优选解  199
5.4.2  最小解  199
5.4.3  很优解集  200
5.5  很优恒定速率平滑  202
5.6  很优平滑与贪婪整形  205
5.7  与延迟均衡的比较  209
5.8  跨越两个网络的无损平滑  211
5.8.1  两个网络的延迟和缓冲区大力度优惠要求  212
5.8.2  跨越两个网络的很优恒定速率平滑  214
5.9  参考文献说明  216
第  6 章 聚合调度  218
6.1  概述  218
6.2  经过聚合调度的到达曲线的变换  219
6.2.1  在严格服务曲线元件中的聚合多路复用  219
6.2.2  在 FIFO 服务曲线元件中的聚合多路复用  221
6.2.3  在保证速率节点中的聚合多路复用  226
6.3  带有聚合调度的网络的稳定性和性能界限  227
6.3.1  稳定性问题  227
6.3.2  时间停止方法  228
6.4  稳定性结果和显式界限  232
6.4.1  环是稳定的  232
6.4.2  带有强源端速率条件的同构 ATM 网络的显式界限  236
6.5  参考文献说明  243
6.6  习题  244
第  7 章 自适应保证与数据包尺度速率保证  245
7.1  概述  245
7.2  服务曲线的局限性和 GR 节点抽象  246
7.3  数据包尺度速率保证  247
7.3.1  数据包尺度速率保证的定义  247
7.3.2  数据包尺度速率保证的实际实现  251
7.3.3  由积压得到延迟  252
7.4  自适应保证  253
7.4.1  自适应保证的定义  253
7.4.2  自适应保证的属性  255
7.4.3  PSRG 和自适应服务曲线  256
7.5  PSRG 节点的级联  257
7.5.1  FIFO PSRG 节点的级联  257
7.5.2  非 FIFO PSRG 节点的级联  258
7.6  GR 和 PSRG 的比较  262
7.7  证明  262
7.7.1  引理 7.3.1 的证明  262
7.7.2  定理 7.3.2 的证明  264
7.7.3  定理 7.3.3 的证明  265
7.7.4  定理 7.3.4 的证明  266
7.7.5  定理 7.4.2 的证明  267
7.7.6  定理 7.4.3 的证明  268
7.7.7  定理 7.4.4 的证明  269
7.7.8  定理 7.4.5 的证明  270
7.7.9  定理 7.5.3 的证明  273
7.7.10  命题 7.5.2 的证明  279
7.8  参考文献说明  281
7.9  习题  281
第  8 章 时变整形器  282
8.1  概述  282
8.2  时变整形器  282
8.3  初始状态非空的时不变整形器  284
8.3.1  初始缓冲区非空的整形器  284
8.3.2  初始水位非空的漏桶整形器  285
8.4  时变漏桶整形器  287
8.5  参考文献说明  289
第  9 章 有损系统  290
9.1  损失的表示方程  290
9.1.1  有限存储元件中的损失  290
9.1.2  有界延迟元件中的损失  293
9.2  应用 1：损失率的界限  294
9.3  应用 2：复杂系统中的损失界限  296
9.3.1  缓冲器和管制器之间分隔的损失界限  296
9.3.2  VBR 整形器中的损失界限  298
9.4  带有两个边界的 Skorokhod 反射问题的解  301
9.5  参考文献说明  305
参考文献  306
索引  312

我很高兴看到华为技术有限公司与北京航空航天大学合作完成这部专著中文版的翻译工作，希望这部译著能够推动对互联网提供确定性承载、可承诺时延及带宽等基础业务保障方面的创新研究及探索，最终让网络可以更好地服务用户，推动经济发展。
——中国工程院院士 刘韵洁


网络演算的基本思想是通过描述流量的优选突发度，控制和量化这些突发数据，使得这些突发数据可以在系统中无损传输，以便根据优选突发度计算网络中端到端时延的确定性上界。
本书不仅提供了基于研究动机的实用介绍，也包括了进阶的学术研究内容，是研究者了解网络演算理论很好的选择。
——华为巴黎研究所研究科学家 安妮·布亚尔（Anne Bouillard）