最佳化交換處理系統之權重選擇

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：92

、訪客IP：18.217.182.45

姓名

鄭文智(Wen-Chih Cheng) 查詢紙本館藏

畢業系所

統計研究所

論文名稱

最佳化交換處理系統之權重選擇
(Choosing Optimal Queue Weights for Switched Processing Systems)

相關論文

★ 可資源共享之平行分散處理系統的最大吞吐量控制策略	★ 設計複雜網路系統之高效率模擬方法
★ 反應曲面法在複雜網路上的應用	★ 複雜網路系統模擬之均勻設計
★ 使用 Support Vector Regression 建構複雜網路系統之反應曲面模型	★ 增加具動態伺服器配置的交換系統之吞吐量
★ 流量模型基於分數綜合自還原移動平均過程	★ 適用於網路交換處理系統下的角錐延展策略
★ 以抽樣及測量為基準之交換處理系統控制策略	★ 樹狀網路之控制與統計反向問題
★ 貝他演算法的表現評估	★ 廣泛區域之均勻設計與電腦實驗之運用
★ Evaluation of Algorithms for Generating Dirichlet Random Vectors	★ 資料傳輸網路之貝氏診斷
★ 可共享資源的非循環網路系統建構在測量基礎上之控制策略

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

交換處理系統對許多領域來說是個重要的模型如通訊網路、電腦網路與製造業網路。它可被刻劃成是具有彈性的、獨立的服務能力，以及多層的工作流量的模型。過去幾年，非常豐富的文獻資料都在發展能夠同時具備最大吞吐量與達到某種程度穩定性的控制策略。近年來，研究轉向於改善服務品質表現如等待時間與存貨。本研究探討一種使吞吐量最大的控制策略稱為最大內積控制策略。其目的是希望在使用最大內積控制策略之下能對每一個佇列放置最佳佇列權重以有效地改進等待的表現值。我們所提出的方法動機是源自於有名的最短處理時間優先服務的法則。對於輸入流量不變的例子，我們介紹一個一維度方向的搜尋方法以尋找最佳佇列權重。對於輸入流量可變化的情形，我們也提出一個更有彈性且實用的搜尋方法。模擬結果顯示對於不同的系統輸入，我們提出的方法都可以顯著地改善平均等待時間與九十五百分比的等待時間。

摘要(英)

Switched Processing Systems (SPS) represent crucial models for many applications in communication, computer, and manufacturing networks. They are characterized by flexible, independent service capabilities and multiple classes of job flows. Over the years, a fairly rich literature has been developed for maximizing the system’s throughput and at the same time constructing scheduling policies that maintain a certain level of system stability. Recently, research has been shifted to improving the quality of service (QoS) performance with respect to the performance metrics such as delay and backlog. In this study, we investigate a class of throughput maximizing scheduling policies called MaxProduct policies. The goal is to place the optimal weight on each queue so that the delay performance under the MaxProduct policies can be significantly improved. The proposed approach is motivated by the well known Shortest Processing Time First (SPTF) rule. For systems where the input traffic does not change, a one-dimensional search procedure for finding the optimal queue weights is introduced. For systems where the input traffic statistics might change, a more flexible and practical search procedure is suggested. The simulation results reveal that our proposed methods can substantially improve the average system delay and the 95th percentile of delays for various types of input traffic.

關鍵字(中)

★ 佇列權重
★ 最短處理時間優先服務法則
★ 最大內積策略
★ 等待時間
★ 模擬
★ 交換處理系統

關鍵字(英)

★ Shortest Processing Time First (SPTF) rule
★ the MaxProduct policies
★ delay
★ Switched Processing Systems
★ queue weights
★ simulation

論文目次

Chinese Abstract i
Abstract ii
Acknowledgments iii
Contents iv
List of Figures v
List of Tables ix
1 Introduction 1
2 System and Control Policies 4
2.1 Switched Processing Systems 4
2.2 System Dynamics and Stability 5
2.3 The MaxProduct Policies 6
3 Choosing Optimal Queue Weights 9
3.1 Choosing Queue Weights Based on the SPTF Rule 9
3.2 Simulation Studies 10
3.2.1 Simulation of 2-Queue Systems 10
3.2.2 Simulation of 3-Queue Systems 12
3.3 The Algorithm for Constructing Optimal Queue Weights 15
4 A Simulation Study 18
4.1 A 2-Queue System with Fixed Input Processes 18
4.2 A 3-Queue System with Fixed Input Processes 21
4.3 2-Queue and 3-Queue Systems with Changing Input Pocesses 24
5 Concluding Remarks 30
Bibliography 31

參考文獻

[1] M. Armony and N. Bambos, “Queueing Dynamics and Maximal Throughput Scheduling in Switched Processing Systems”, Queueing Systems: Theory and Applications, 44(3), pp. 209-252, 2003.
[2] Y.C. Hung, “Modeling and Analysis of Stochastic Networks with Shared Resources”, Department of Statistics, The University of Michigan, Ph.D. thesis, 2002.
[3] N. Bambos and G. Michailidis, “Queueing Networks in Random Environments”, Advances in Applied Probability, 36, pp. 293-337, 2004.
[4] N. Bambos and G. Michailidis, “Queueing Networks of Random Link Topology: Stationary Dynamics of Maximal Throughput Schedules”, Queueing Systems, 50, pp. 5-52, 2005.
[5] J.G. Dai, “Stability of fluid and stochastic processing networks”, MaPhySto Miscellanea Publication, No. 9, Denmark, 1999.
[6] N. McKeown, A. Mekkittikul, V. Anantharam, and J. Walrand, “Achieving 100% Throughput in an Input-Queued Switch”, IEEE Transactions on Communications, 47(8), pp. 1260-1267, 1999.
[7] A. Mekkittikul and N. McKeown, “A Starvation-free Algorithm for Achieving 100% Throughput in an Input-Queued Switch”, Proceedings of ICCCN’96, pp. 226-231, Rockville, Maryland, USA, October 1996.
[8] G. Michailidis, “Optimal Resource Allocation in a Queueing System with Shared Resources”, Proceedings of the 42nd Conference on Decision and Control, pp. 2106-2111, Maui, USA, December 2003.
[9] L. Tassiulas and P.P. Bhattacharya, “Allocation of Interdependent Resources for Maximal Throughput”, Stochastic Models, 16(1), pp. 27-48, 1999.
[10] L. Tassiulas and A. Ephremides, “Stability properties of constrained queueing systems and scheduling for maximum throughput in multihop radio networks”, IEEE Transactions on Automatic Control, 37(12), pp. 1936-1949, 1992.
[11] K.M. Wasserman, G. Michailidis and N. Bambos, “Optimal Processor Allocation to Differentiated Job Flows”, Performance Evaluation, 63, pp. 1-14, 2006.
[12] K. Ross and N. Bambos, “Dynamic Quality of Service Control in Packet Switch Scheduling”, Proceedings of IEEE International Conference on Communications, pp. 396-401, Seoul, Korea, May 2005.
[13] Y. C. Hung and G. Michaillidis, “Improving Quality of Service for Switched Processing Systems”, Proceedings of 11th International Workshop on Computer-Aided Modeling, Analysis and Design of Communication Links and Networks, pp. 46-53, Trento, ITALY, June 2006.
[14] N. Megow and A.S. Schulz, “Scheduling to Minimizing Average Completion Time Revised: Deterministic On-Line Algorithms”, Lecture Notes in Computer Science, Springer, Berlin, pp. 227-234, 2004.
[15] M. Pinedo, Scheduling: Theory , Algorithms, and Systems, Prentice Hall International Series in Industrial and Systems Engineering, New Jersey, 1995.
[16] L. Schrage, “A Proof of the Shortest Remaining Processing Time Processing Discipline”, Operations Research, 16, pp. 687-690, 1968.
[17] J. Walrand, Introduction to Queueing Networks, Englewood Cliffs: Prentice Hall, New York, 1998.
[18] D. P. Kennedy, “A Note on Stochastic Search Methods for Global Optimization”, Advances in Applied Probability, 20, pp. 476-478, 1988.

指導教授

洪英超(Ying-Chao Hung)

審核日期

2007-7-6

推文