臺灣博碩士論文加值系統

在這篇文章我們探討具有M個佇列(queue)以及N個伺服器(server)的平行分散處理系統(Parallel and Distributed Processing System)，其中每一個伺服器皆能配置給不同的佇列以達到資源共享(resource sharing)的目的。此系統捕捉到現實生活中許多網路架構的特性，比如資訊傳輸(communications)、電腦網路(computer networks)等。我們藉由系統的穩定條件(stability conditions)和穩定區域(stability region)來比較傳統的控制策略(control policies)以及數種不同動態策略(dynamic policies)之間的差異性，其主要的目的是探討隨機網路系統(stochastic network system)中最基本的表現測量值(performance measurement)─吞吐量(throughput)。本文中我們也提出一新的控制策略─“最大加權停留時間優先策略”(Largest Weighted Delay First Policy)，並證明在一般的假設之下，此控制策略可維持系統的穩定性並讓系統的吞吐量為最大，其證明的方式主要是以偏離分析(drift analysis)為基礎。

目錄

第一章：緒論……………………………………………………………1
第二章：符號……………………………………………………………4
第三章：排隊系統(Queueing System)及其假設………………………6
第四章：系統的穩定以及排程策略…………………………………11
4.1.系統穩定性與不穩定性(Stability and Instability)………………11
4.2.穩定區域(Stability Region)與控制策略(Control Policies)……13
4.2.1.靜態策略(Static Polices)………………………………………14
4.2.2.先到達先服務策略(First-Come-First-Serve Policy)…………16
4.2.3.最大服務率策略(Maximum Service Rate Policy)……………18
4.2.4.最大加權佇列長度策略(Maximum Weighted Queue Length Policy)………………………………………………………20
4.2.5.最大加權停留時間優先策略(Largest Weighted Delay First Policy)………………………………………………………22
4.3.最大吞吐量策略(Maximum Throughput Policy)………………26
第五章：結論與探討………………………………………………29
第六章：參考文獻…………………………………………………33
第七章：附錄“證明定理4.4”………………………………………35
7.1.證明條件(C1)…………………………………………………37
7.2.證明條件(D2)…………………………………………………43
7.3.佇列長度(Queue Length)的穩定性……………………………44

圖目錄

圖3.1：具有M個平行佇列以及N個伺服器的M N交換模型……6
圖4.1：2x2交換模型以及伺服器對應不同佇列的服務率…………14
圖4.2：針對2x2系統(左圖)以及2x3系統(右圖)，在服從五種不同的控制策略下所構成的穩定區域S……………………………24
圖4.3：2x3交換模型…………………………………………………25
圖7.1：Wi(tn+1) 與Wi(tn) 的三種可能關係圖…………………………36

[1] Armony, M. ; Bambos, N. “Queueing Dynamics and Maximal Throughput Scheduling in Switched Processing Systems”, Technical Report SU NETLAB-2001-09/01, Engineering library, Stanford University.

[2] Bell, S. L. ; Williams, R. J. “Dynamic Scheduling of a System with Two Parallel Servers in Heavy Traffic with Resource Pooling: Asymptotic Optimality of A Threshold Policy”, The Annals of Applied Probability, 2001, Vol. 11, No. 3, pp.608-649.

[3] Dai, J. G. “On positive Harris recurrence of multiclass queueing networks: a unified approach via fluid limit models”, Annals of Applied Probability, Vol. 5, 1995, pp.49-77.

[4] Hajek, B. “Hitting-time and Occupation-time Bounds Implied By Drift Analysis with Applications”, Adv. Appl. Prob. 14, pp.501-525.

[5] Hung, Y. C. “Modeling and Analysis of Stochastic Networks with Shared Resource”, Ph.D. Thesis, The University of Michigan, 2002.

[6] Hung, Y. C. ; Michailidis, G. ; Bingham, D. R. “Developing Efficient Simulation Methodology for Complex Queueing Networks”, Proceedings of the Winder Simulation Conference 2003, New Orleans, pp.152-159.

[7] Kelly, F. P. “Reversibility and Stochastic Networks”, 1979.

[8] Leonaridi, E. ; Mellia, M. ; Neri, F. ; Marsan, M. A. “On the Stability of Input-Queued Switches with Speed-up”, IEEE, Transactions on Networking, 9(1), 2001, pp.104-118.

[9] Mekkittikul, A. ; McKeown, N. “A Starvation-free Algorithm For Achieving 100% Throughput in an Input-Queued Switch”, Proc. of ICCCN’96, October, 1996, pp.226-231.

[10] Meyn, S. P. “Stability and Optimization of Queueing Networks and Their Fluid models”, Proceeding of the Summer Seminar on “The Mathematics of Stochastic Manufacturing Systems”, 1996, pp.17-21.

[11] Pemantle, R. ; Rosenthal, J. S. “Moment conditions for a sequence with negative drift to be uniformly bounded in Lr ”, Stochastic Processes and their Applications 82, 1999, pp.143-155.

[12] Ross , S. “Stochastic Processes” , 2nd edition, Chapter 3, pp.98-104.

[13] Stolyar, A. L. “Control of End-To-End Delay Tails in a Multiclass Network: LWDF Discipline Optimality”, The Annals of Applied Probability, 2003. Vol. 13. No. 3. pp.1151-1206.

[14] Walrand, J. “Introduction to queueing networks”, Englewood Cliffs, Prentice Hall” 1988.