網絡演算：互聯網確定性排隊系統理論

本書主要闡述網路演算的理論，介紹對互聯網確定性排隊系統性能的界限分析方法。第一部分結合應用實例，給出網路演算綜述及概念解釋，介紹時延、積壓、輸出流量行為等界限分析方法。第二部分詳細介紹網路演算的形式化數學理論研究，基於最小加代數的分析體系，對更通用、更複雜的系統進行建模和分析。第三部分介紹結合互聯網特性的進階研究，包括很優多媒體平滑、聚合調度、自我調整保證與資料包尺度速率保證、時變整形器、有損系統等場景，給出積壓等界限分析方法及其結果。

本書開創性地確立了互聯網確定性排隊系統的理論基礎，可供通信、電腦網路專業的研究生學習，亦可供從事互聯網、即時系統等設計、分析、驗證的工程師參考。

第一部分網路演算基礎知識
第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．13種界限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．1GPS和保證速率節點86
2．1．1資料包調度86
2．1．2GPS及其實際運用87
2．1．3GR節點和優選加代數方法90
2．1．4GR節點的級聯93
2．1．5證明95
2．2IETF的綜合服務模型97
2．2．1保證服務97
2．2．2互聯網路由器的綜合服務模型97
2．2．3通過RSVP進行預留設置98
2．2．4流建立演算法101
2．2．5多播流102
2．2．6ATM流建立103
2．3可調度性103
2．3．1EDF調度器104
2．3．2SCED調度器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．3PSRG和自我調整服務曲線256
7．5PSRG節點的級聯257
7．5．1FIFOPSRG節點的級聯257
7．5．2非FIFOPSRG節點的級聯258
7．6GR和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．2VBR整形器中的損失界限298
9．4帶有兩個邊界的Skorokhod反射問題的解301
9．5參考文獻說明305
參考文獻306
索引312

讓-伊夫·勒布代克（Jean-Yves Le Boudec），1984年獲得法國雷恩大學博士學位。先後在加拿大貝爾北方研究中心、IBM蘇黎世實驗室工作。1994年加入瑞士洛桑聯邦理工學院擔任副教授，目前是洛桑聯邦理工學院教授，IEEE研究員。曾經在許多會議和期刊的編輯委員會任職，包括ACM SIGCOMM，ACM SIGMETRICS，IEEE INFOCOM，Performance Evaluation和ACM/IEEE Transactions on Networking等。著有Performance Evaluation of Computerand Communication Systems等專著。