●出版者的話
譯者序
序言
前言
致謝
第一部分排隊論簡介
第1章分析建模的功能及實例2
1.1什麼是排隊論2
1.2排隊論實例3
第2章排隊論術語8
2.1我們將去向何方8
2.2單服務器網絡8
2.3排隊網絡的分類9
2.4開放網絡10
2.5更多指標：吞吐量和利用率10
2.6封閉網絡12
2.6.1交互式（終端驅動）繫統13
2.6.2批處理繫統14
2.6.3封閉繫統中的吞吐量14
2.7封閉網絡和開放網絡之間的差異15
2.8閱讀材料16
2.9習題16
第二部分必要的概率背景知識
第3章概率知識復習18
3.1樣本空間和事件18
3.2事件定義的概率18
3.3事件的條件概率19
3.4獨立事件和有條件獨立事件20
3.5總概率定律21
3.6貝葉斯定律22
3.7離散隨機變量與連續隨機變量22
3.8概率和密度23
3.8.1離散：概率質量函數23
3.8.2連續：概率密度函數25
3.9期望和方差27
3.10聯合概率和獨立性29
3.11條件概率和期望30
3.12基於條件化的概率和期望34
3.13期望的線性性質35
3.14正態分布36
3.14.1線性變換特性37
3.14.2中心極限定理39
3.15隨機變量的隨機數的和40
3.16習題41
第4章生成用於模擬的隨機變量45
4.1逆變換方法45
4.1.1連續情況45
4.1.2離散情況46
4.2接受拒絕方法47
4.2.1離散情況47
4.2.2連續情況48
4.2.3一些更難的問題50
4.3閱讀材料50
4.4習題50
第5章樣本路徑、收斂和均值52
5.1收斂52
5.2強/弱大數定律55
5.3時間均值與整體均值56
5.3.1動機56
5.3.2定義57
5.3.3解釋57
5.3.4等價性58
5.3.5模擬59
5.3.6繫統時間均值60
5.4閱讀材料60
5.5習題60
第三部分簡單運籌定律的預測能力：“假設”問題和答案
第6章Little定律和其他運籌定律62
6.1開放繫統的Little定律62
6.2直覺62
6.3封閉繫統的Little定律63
6.4開放繫統的Little定律證明63
6.4.1基於時間均值的陳述64
6.4.2證明64
6.4.3推論65
6.5封閉繫統的Little定律證明66
6.5.1基於時間均值的陳述66
6.5.2證明66
6.6廣義的Little定律67
6.7應用Little定律的示例67
6.8更多運籌定律：強制流定律69
6.9運籌定律組合70
6.10設備需求72
6.11與Little定律相關的閱讀和其他主題73
6.12習題73
第7章修改分析：封閉繫統的“假設”75
7.1回顧75
7.2封閉繫統的漸近界限76
7.3封閉繫統的修改分析78
7.4更多修改分析示例78
7.5封閉網絡和開放網絡的比較80
7.6閱讀材料81
7.7習題81
第四部分從馬爾可夫鏈到簡單隊列
第8章離散時間馬爾可夫鏈84
8.1離散時間與連續時間馬爾可夫鏈84
8.2DTMC的定義85
8.3有限狀態DTMC的示例85
8.3.1維修設施問題85
8.3.2雨傘問題86
8.3.3程序分析問題86
8.4P的冪：n步轉移概率87
8.5平穩方程88
8.6平穩分布等於極限分布89
8.7求解平穩方程的示例90
8.7.1維修設施成本問題90
8.7.2雨傘問題91
8.8無限狀態DTMC91
8.9無限狀態平穩性結果91
8.10求解無限狀態DTMC中的平穩方程93
8.11習題95
第9章遍歷性理論97
9.1遍歷性問題97
9.2有限狀態DTMC98
9.2.1極限分布的存在98
9.2.2訪問狀態之間的平均時間101
9.2.3時間均值102
9.3無限狀態馬爾可夫鏈102
9.3.1常返與瞬時103
9.3.2無限隨機遊走示例106
9.3.3正常返與零常返108
9.4馬爾可夫鏈的遍歷定理109
9.5時間均值110
9.6極限概率解釋為速率112
9.7時間可逆性定理113
9.8當鏈是周期性的或者不可約的114
9.8.1周期鏈115
9.8.2不可約的鏈119
9.9結論119
9.10馬爾可夫鏈的遍歷定理的證明119
9.11習題124
第10章真實世界的示例：Google、Aloha和HarderChains129
10.1Google的PageRank算法129
10.1.1Google的DTMC算法129
10.1.2真實網絡圖的問題131
10.1.3死角和蜘蛛陷阱問題的Google解決方案131
10.1.4PageRank算法的評估132
10.1.5實際實現的注意事項132
10.2Aloha協議分析132
10.2.1SlottedAloha協議133
10.2.2Aloha馬爾可夫鏈133
10.2.3Aloha馬爾可夫鏈的性質134
10.2.4改進Aloha協議135
10.3Aloha為更難的馬爾可夫鏈生成函數136
10.3.1z變換136
10.3.2求解鏈136
10.4閱讀材料138
10.5習題138
第11章指數分布和泊松過程141
11.1指數分布的定義141
11.2指數的無記憶特性142
11.3通過δ-步將指數與幾何相關聯143
11.4指數的更多屬性144
11.5有名的泊松過程146
11.6合並獨立泊松過程149
11.7泊松分裂149
11.8均勻性151
11.9習題152
第12章轉換到連續時間馬爾可夫鏈154
12.1定義CTMC154
12.2解決CTMC問題157
12.3泛化和解釋159
12.3.1解釋CTMC的平衡方程160
12.3.2CTMC的概要定理160
12.4習題160
第13章M/M/1和PASTA161
13.1M/M/1隊列161
13.2使用M/M/1隊列的示例163
13.3PASTA164
13.4進一步閱讀166
13.5習題166
第五部分服務器機群與網絡：多服務器和多隊列繫統
第14章服務器機群：M/M/k與M/M/k/k排隊繫統173
14.1連續時間馬爾可夫鏈的時間可逆性173
14.2M/M/k/k損失繫統174
14.3M/M/k176
14.4三種服務器組織模式的比較180
14.5閱讀材料181
14.6習題181
第15章服務器機群的容量規劃184
15.1在M/M/k中，負載的真正含義是什麼184
15.2M/M/ 185
15.2.1M/M/ 分析185
15.2.2M/M/k容量規劃的首次削減規則186
15.3平方根配置187
15.4閱讀材料189
15.5習題189
第16章時間可逆性和Burke定理193
16.1有限狀態CTMC的更多示例193
16.1.1緩衝空間有限的網絡193
16.1.2M/M/2I/O的批處理繫統194
16.2反向鏈195
16.3Burke定理198
16.4Burke定理的另一種(部分)證明198
16.5應用：串聯式服務器199
16.6具有概率路由的一般非循環網絡200
16.7閱讀材料201
16.8習題201
第17章隊列網絡和Jackson乘積形式203
17.1Jackson網絡的定義203
17.2到達每個服務器的過程204
17.3解決Jackson網絡205
17.4本地平衡法205
17.5閱讀材料209
17.6習題209
第18章分類隊列網絡212
18.1概述212
18.2分類網絡的動機212
18.3分類Jackson網絡的符號和建模214
18.4單服務器分類網絡215
18.5乘積形式定理216
18.6分類網絡示例220
18.6.1面向連接的ATM網絡示例220
18.6.2作業類別分布示例221
18.6.3CPU密集型和I/O密集型作業示例222
18.7閱讀材料224
18.8習題224
第19章封閉隊列網絡226
19.1動機226
19.2乘積形式的解227
19.2.1封閉網絡的局部平衡方程227
19.2.2推導極限概率的示例229
19.3均值分析230
19.3.1到達定理230
19.3.2平均響應時間的迭代推導232
19.3.3MVA示例233
19.4閱讀材料234
19.5習題234
第六部分實際工作負載：高可變性和重尾
第20章尾巴的故事：實際工作負載的案例研究239
20.1研究生院的故事——過程遷移239
20.2UNI程壽命測量240
20.3帕累托分布的性質241
20.4有界帕累托分布242
20.5重尾242
20.6活動進程遷移的益處243
20.7帕累托分布無處不在243
20.8習題244
第21章相位型分布和矩陣分析方法246
21.1用指數代表一般分布246
21.2PH工作負載的馬爾可夫鏈建模249
21.3矩陣分析法251
21.4時變負載分析252
21.4.1高級別的想法252
21.4.2生成矩陣Q252
21.4.3R求解254
21.4.4尋找π→0254
21.4.5性能指標255
21.5更復雜的鏈256
21.6閱讀材料和進一步的評論258
21.7習題258
第22章具有分時服務器的網絡261
22.1乘積形式網絡261
22.2BCMP結果261
22.2.1FCFS服務器的網絡261
22.2.2PS服務器的網絡262
22.3M/M/1/PS264
22.4M/Cox/1/PS264
22.5M/G/1/PS服務器的串聯網絡268
22.6具有概率路由的PS服務器網絡269
22.7閱讀材料270
22.8習題270
第23章M/G/1隊列與檢驗悖論271
23.1檢驗悖論271
23.2M/G/1隊列及其分析271
23.3更新獎勵理論273
23.4申請更新獎勵以獲得預期的超量收益275
23.5回到檢驗悖論276
23.6回到M/G/1隊列277
23.7習題278
第24章服務器機群的任務分配策略280
24.1FCFS服務器機群的任務分配281
24.2PS服務器機群的任務調度288
24.3很好服務器機群設計291
24.4閱讀材料和進一步跟進294
24.5習題296
第25章變換分析298
25.1變換的定義和一些示例298
25.2從變換中獲取矩：剝洋蔥300
25.3變換的線性性質302
25.4條件303
25.5M/M/1繫統中響應時間的分布304
25.6結合拉普拉斯變換和z變換305
25.7變換的更多結果305
25.8閱讀材料306
25.9習題306
第26章M/G/1變換分析309
26.1繫統中數字的z變換309
26.2繫統中時間的拉普拉斯變換311
26.3閱讀材料313
26.4習題313
第27章功率優化應用314
27.1功率優化問題314
27.2M/G/1的繁忙時段分析315
27.3M/G/1與設置成本318
27.4比較ON/IDLE與ON/OFF320
27.5閱讀材料321
27.6習題321
第七部分M/G/1中的智能調度
第28章性能指標327
28.1傳統度量標準327
28.2單一隊列的常用度量標準327
28.3當下流行的度量標準328
28.4饑餓/公平指標328
28.5導出性能指標329
28.6閱讀材料329
第29章調度：非搶占式、非基於規模的策略330
29.1FCFS、LCFS和RANDOM330
29.2閱讀材料332
29.3習題332
第30章調度：搶占式、非基於規模的策略333
30.1PS333
30.1.1PS的起源333
30.1.2M/G/1/PS繫統中的作業年齡334
30.1.3響應時間作為作業規模的函數335
30.1.4對PS結果的直覺336
30.1.5理解FCFS的PS結果的含義337
30.2搶占式LCFS338
30.3FB調度339
30.4閱讀材料342
30.5習題343
第31章調度：非搶占式、基於規模的策略345
31.1優先級排隊345
31.2非搶占式優先級346
31.3最短作業優先348
31.4關於非搶占式策略的問題350
31.5習題350
第32章調度：搶占式、基於規模的策略351
32.1動機351
32.2搶占式優先級排隊351
32.3搶占式最短作業優先354
32.4PSJF的變換分析355
32.5習題357
第33章調度：SRPT與公平性358
33.1最短剩餘處理時間358
33.2SRPT等待時間的準確推導360
33.3與其他策略的比較361
33.3.1與PSJF的比較361
33.3.2SRPT與FB362
33.3.3所有調度策略的比較362
33.4SRPT的公平性363
33.5閱讀材料366
參考文獻367
