網絡演算 互聯網確定性排隊系統理論 Network Calculus: A Theory of Deterministic Queuing Systems for the Internet

让-伊夫·勒布代克（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