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

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

關鍵字

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

並列摘要

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

參考文獻

[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.

[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.

國際替代計量

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

未授權

主題瀏覽