![]() |
|
以作者查詢圖書館館藏 、以作者查詢臺灣博碩士 、以作者查詢全國書目 、勘誤回報 、線上人數:8 、訪客IP:18.116.15.111
姓名 邱啟宗(Chi-Tsung Chiu) 查詢紙本館藏 畢業系所 統計研究所 論文名稱 可資源共享之平行分散處理系統的最大吞吐量控制策略 相關論文 檔案 [Endnote RIS 格式]
[Bibtex 格式]
[相關文章]
[文章引用]
[完整記錄]
[館藏目錄]
[檢視]
[下載]
- 本電子論文使用權限為同意立即開放。
- 已達開放權限電子全文僅授權使用者為學術研究之目的,進行個人非營利性質之檢索、閱讀、列印。
- 請遵守中華民國著作權法之相關規定,切勿任意重製、散佈、改作、轉貼、播送,以免觸法。
摘要(中) 在這篇文章我們探討具有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)為基礎。 關鍵字(中) ★ 資源共享
★ 隨機網路
★ 控制策略
★ 吞吐量
★ 平行分散處理系統關鍵字(英) ★ control policy
★ throughput
★ queueing
★ resource sharing
★ parallel and distributed processing system
★ stochastic network論文目次 目錄
第一章:緒論……………………………………………………………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.指導教授 洪英超(Ying-Chao Hung) 審核日期 2004-7-1 推文 plurk
funp
live
udn
HD
myshare
netvibes
friend
youpush
delicious
baidu
網路書籤 Google bookmarks
del.icio.us
hemidemi
myshare