第 一部分 網(wǎng)絡(luò)演算基礎(chǔ)知識 第　1 章 網(wǎng)絡(luò)演算　3 1.1　數(shù)據(jù)流的模型　3 1.1.1　累積量函數(shù)、離散時間與連續(xù)時間模型　3 1.1.2　積壓與虛擬延遲　6 1.1.3　例子：播放緩沖器　6 1.2 到達(dá)曲線　8 1.2.1　到達(dá)曲線的定義　8 1.2.2　漏桶模型和通用信元速率算法　12 1.2.3　次可加性和到達(dá)曲線　17 1.2.4　最小到達(dá)曲線　21 1.3　服務(wù)曲線　23 1.3.1　服務(wù)曲線的定義　23 1.3.2　經(jīng)典服務(wù)曲線示例　26 1.4 網(wǎng)絡(luò)演算基礎(chǔ)　29 1.4.1　3 種界限　29 1.4.2　界限是緊致的嗎　35 1.4.3　級聯(lián)　36 1.4.4　積壓界限的改進(jìn)　38 1.5　貪婪整形器　40 1.5.1　定義　40 1.5.2　貪婪整形器的輸入/輸出特性　40 1.5.3　貪婪整形器的性質(zhì)　43 1.6　最大服務(wù)曲線、可變延遲和固定延遲　45 1.6.1　最大服務(wù)曲線　45 1.6.2　積壓造成的延遲　49 1.6.3　可變延遲與固定延遲　51 1.7　處理變長數(shù)據(jù)包　52 1.7.1　變長數(shù)據(jù)包引入不規(guī)則性的示例　52 1.7.2　打包器　54 1.7.3　貪婪整形器和打包器之間的關(guān)系　59 1.7.4　打包貪婪整形器　62 1.8　無損有效帶寬和等效容量　68 1.8.1　流的有效帶寬　68 1.8.2　等效容量　70 1.8.3　示例：FIFO 多路復(fù)用器的接受域　71 1.9 定理　1.4.5 的證明　73 1.10 參考文獻(xiàn)說明　76 1.11　習(xí)題　78 第　2 章 網(wǎng)絡(luò)演算應(yīng)用于互聯(lián)網(wǎng)　86 2.1　GPS 和保證速率節(jié)點(diǎn)　86 2.1.1　數(shù)據(jù)包調(diào)度　86 2.1.2　GPS 及其實(shí)際運(yùn)用　87 2.1.3　GR 節(jié)點(diǎn)和最大加代數(shù)方法　90 2.1.4　GR 節(jié)點(diǎn)的級聯(lián)　93 2.1.5　證明　95 2.2　IETF 的綜合服務(wù)模型　97 2.2.1　保證服務(wù)　97 2.2.2　互聯(lián)網(wǎng)路由器的綜合服務(wù)模型　97 2.2.3　通過 RSVP 進(jìn)行預(yù)留設(shè)置　98 2.2.4　流建立算法　101 2.2.5　多播流　102 2.2.6　ATM 流建立　103 2.3　可調(diào)度性　103 2.3.1　EDF 調(diào)度器　104 2.3.2　SCED 調(diào)度器　106 2.3.3　緩沖需求　112 2.4　應(yīng)用于區(qū)分服務(wù)　113 2.4.1　區(qū)分服務(wù)　113 2.4.2　顯式的 EF 延遲界限　114 2.4.3　帶阻尼器的聚合調(diào)度界限　121 2.4.4　靜態(tài)最早時間優(yōu)先　125 2.5　參考文獻(xiàn)說明　126 2.6　習(xí)題　126 第二部分　數(shù)學(xué)知識 第　3 章 基本最小加演算和最大加演算　131 3.1　最小加演算　131 3.1.1　下確界和求最小　131 3.1.2　雙子代數(shù)　133 3.1.3　廣義遞增函數(shù)的類型　134 3.1.4　廣義遞增函數(shù)的偽逆　137 3.1.5　凹函數(shù)、凸函數(shù)與星形函數(shù)　138 3.1.6　最小加卷積　139 3.1.7　次可加函數(shù)　146 3.1.8　次可加閉包　149 3.1.9　最小加解卷積　154 3.1.10　以時間反轉(zhuǎn)表達(dá)的最小加解卷積　159 3.1.11　水平偏差與垂直偏差　162 3.2　最大加演算　163 3.2.1　最大加卷積與解卷積　163 3.2.2　在最大加代數(shù)中最小加解卷積的線性　164 3.3　習(xí)題　165 第　4 章 最小加系統(tǒng)論和最大加系統(tǒng)論　166 4.1　最小加算子和最大加算子　166 4.1.1　矢量的記法　166 4.1.2　算子　168 4.1.3　算子的類型　169 4.1.4　上半連續(xù)和下半連續(xù)算子　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　不動點(diǎn)方程（空間方法）　184 4.3.1　主要理論　184 4.3.2　應(yīng)用的例子　186 4.4　不動點(diǎn)方程（時間方法）　191 4.5　小結(jié)　192 第三部分　網(wǎng)絡(luò)演算進(jìn)階 第　5 章 最優(yōu)多媒體平滑　195 5.1　問題設(shè)定　195 5.2　無損平滑約束　197 5.3　延遲與回放緩沖區(qū)最低要求　198 5.4　最優(yōu)平滑策略　199 5.4.1　最大解　199 5.4.2　最小解　199 5.4.3　最優(yōu)解集　200 5.5　最優(yōu)恒定速率平滑　202 5.6　最優(yōu)平滑與貪婪整形　205 5.7　與延遲均衡的比較　209 5.8　跨越兩個網(wǎng)絡(luò)的無損平滑　211 5.8.1　兩個網(wǎng)絡(luò)的延遲和緩沖區(qū)最低要求　212 5.8.2　跨越兩個網(wǎng)絡(luò)的最優(yōu)恒定速率平滑　214 5.9　參考文獻(xiàn)說明　216 第　6 章 聚合調(diào)度　218 6.1　概述　218 6.2　經(jīng)過聚合調(diào)度的到達(dá)曲線的變換　219 6.2.1　在嚴(yán)格服務(wù)曲線元件中的聚合多路復(fù)用　219 6.2.2　在 FIFO 服務(wù)曲線元件中的聚合多路復(fù)用　221 6.2.3　在保證速率節(jié)點(diǎn)中的聚合多路復(fù)用　226 6.3　帶有聚合調(diào)度的網(wǎng)絡(luò)的穩(wěn)定性和性能界限　227 6.3.1　穩(wěn)定性問題　227 6.3.2　時間停止方法　228 6.4　穩(wěn)定性結(jié)果和顯式界限　232 6.4.1　環(huán)是穩(wěn)定的　232 6.4.2　帶有強(qiáng)源端速率條件的同構(gòu) ATM 網(wǎng)絡(luò)的顯式界限　236 6.5　參考文獻(xiàn)說明　243 6.6　習(xí)題　244 第　7 章 自適應(yīng)保證與數(shù)據(jù)包尺度速率保證　245 7.1　概述　245 7.2　服務(wù)曲線的局限性和 GR 節(jié)點(diǎn)抽象　246 7.3　數(shù)據(jù)包尺度速率保證　247 7.3.1　數(shù)據(jù)包尺度速率保證的定義　247 7.3.2　數(shù)據(jù)包尺度速率保證的實(shí)際實(shí)現(xiàn)　251 7.3.3　由積壓得到延遲　252 7.4　自適應(yīng)保證　253 7.4.1　自適應(yīng)保證的定義　253 7.4.2　自適應(yīng)保證的屬性　255 7.4.3　PSRG 和自適應(yīng)服務(wù)曲線　256 7.5　PSRG 節(jié)點(diǎn)的級聯(lián)　257 7.5.1　FIFO PSRG 節(jié)點(diǎn)的級聯(lián)　257 7.5.2　非 FIFO PSRG 節(jié)點(diǎn)的級聯(lián)　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　參考文獻(xiàn)說明　281 7.9　習(xí)題　281 第　8 章 時變整形器　282 8.1　概述　282 8.2　時變整形器　282 8.3　初始狀態(tài)非空的時不變整形器　284 8.3.1　初始緩沖區(qū)非空的整形器　284 8.3.2　初始水位非空的漏桶整形器　285 8.4　時變漏桶整形器　287 8.5　參考文獻(xiàn)說明　289 第　9 章 有損系統(tǒng)　290 9.1　損失的表示方程　290 9.1.1　有限存儲元件中的損失　290 9.1.2　有界延遲元件中的損失　293 9.2　應(yīng)用 1：損失率的界限　294 9.3　應(yīng)用 2：復(fù)雜系統(tǒng)中的損失界限　296 9.3.1　緩沖器和管制器之間分隔的損失界限　296 9.3.2　VBR 整形器中的損失界限　298 9.4　帶有兩個邊界的 Skorokhod 反射問題的解　301 9.5　參考文獻(xiàn)說明　305 參考文獻(xiàn)　306 索引　312