學術產出-學位論文
文章檢視/開啟
書目匯出
-
題名 基於時間序列下的動態需求之資源模擬 - 使用等候模型
Simulating Time-Varying Demand Services with Queuing Models作者 褚宣凱
Chu, Hsuan Kai貢獻者 蔡瑞煌<br>郁方
Tsaih, Rua Huan<br>Yu, Fang
褚宣凱
Chu, Hsuan Kai關鍵詞 到達率估計
服務資源配置
隨時間序列改變之需求
服務模擬
Arrival Rate Estimation
Service Simulation
Time-varying Demands
Resource Provision日期 2016 上傳時間 2-八月-2016 17:02:27 (UTC+8) 摘要 在服務資源需求量會隨時間而改變的情況下，系統的服務資源供給對致力於提供高服務品質的資源提供者來說是一個重要的議題。在服務資源可以迅速的部署和解除的假設下，像是以雲端運算為基礎之服務，本研究提供了系統性的估算服務資源方法，本方法之結構是以模擬為基礎並結合了非監督式學習、顧客到達率之估計以及統計技術。首先，本研究將每一日之顧客到達率進行分群運算並將具有類似顧客到達模式的日期分為一群，且每一群之包含日期具備可解釋之代表性；下一階段使用兩階段式的忙碌因子模型去建立每一群的顧客到達率模型，並估計該群的多區間普瓦松分布來做為系統模擬隨機過程所需之參數；最後應用了等候模型理論去設計系統模擬方法，模擬出顧客在系統中到達並接受服務的隨機過程，其結果包含觀察出顧客在系統中的等待時間和排隊長度以及所需之服務資源，並提供在不同的服務策略情形下之表現。本研究使用了一個來自電力公司客服中心之進線量資料進行本方法之實驗，展示出如何使用本方法建立一個能滿足服務水準要求的服務資源配置策略，也和該公司過去之配置策略進行比較，並提出實質上如何提升服務品質的配置策略之建議。 參考文獻 [1] R. Buyya, A. Beloglazov, and J. Abawajy, “Energy-efficient management of data center resources for cloud computing: a vision, architectural elements, and open challenges,” arXiv preprint arXiv:1006.0308, 2010.[2] P. Mell and T. Grance, “The nist definition of cloud computing,” 2011.[3] F. Yu, Y.-w. Wan, and R.-h. Tsaih, “Quantitative analysis of cloud-based streaming services,” in Services Computing (SCC), 2013 IEEE International Conference on, pp. 216–223, IEEE, 2013.[4] S. Chaisiri, B.-S. Lee, and D. Niyato, “Optimization of resource provisioning cost in cloud computing,” Services Computing, IEEE Transactions on, vol. 5, no. 2, pp. 164– 177, 2012.[5] E. Amazon, “Amazon elastic compute cloud (amazon ec2),” Amazon Elastic Compute Cloud (Amazon EC2), 2010.[6] R. N. Calheiros, M. A. Netto, C. A. De Rose, and R. Buyya, “Emusim: an integrated emulation and simulation environment for modeling, evaluation, and validation of performance of cloud computing applications,” Software: Practice and Experience, vol. 43, no. 5, pp. 595–612, 2013.[7] B. N. Oreshkin, N. Regnard, and P. L’Ecuyer, “Rate-based daily arrival process models with application to call centers,” tech. rep., Working Paper, Université de Montréal, 2014.[8] R. N. Calheiros, R. Ranjan, A. Beloglazov, C. A. De Rose, and R. Buyya, “Cloudsim: a toolkit for modeling and simulation of cloud computing environments and evalua- tion of resource provisioning algorithms,” Software: Practice and Experience, vol. 41, no. 1, pp. 23–50, 2011.[9] R. Buyya, R. Ranjan, and R. N. Calheiros, “Modeling and simulation of scalable cloud computing environments and the cloudsim toolkit: Challenges and opportuni- ties,” in High Performance Computing & Simulation, 2009. HPCS’09. International Conference on, pp. 1–11, IEEE, 2009.[10] B. Wickremasinghe, R. N. Calheiros, and R. Buyya, “Cloudanalyst: A cloudsim- based visual modeller for analysing cloud computing environments and applications,” in Advanced Information Networking and Applications (AINA), 2010 24th IEEE International Conference on, pp. 446–452, IEEE, 2010.[11] B. Wickremasinghe et al., “Cloudanalyst: A cloudsim-based tool for modelling and analysis of large scale cloud computing environments,” MEDC project report, vol. 22, no. 6, pp. 433–659, 2009.[12] S. K. Garg and R. Buyya, “Networkcloudsim: Modelling parallel applications in cloud simulations,” in Utility and Cloud Computing (UCC), 2011 Fourth IEEE In- ternational Conference on, pp. 105–113, IEEE, 2011.[13] W. Zhao, Y. Peng, F. Xie, and Z. Dai, “Modeling and simulation of cloud computing: A review,” in Cloud Computing Congress (APCloudCC), 2012 IEEE Asia Pacific, pp. 20–24, IEEE, 2012.[14] D. Kliazovich, P. Bouvry, and S. U. Khan, “Greencloud: a packet-level simulator of energy-aware cloud computing data centers,” The Journal of Supercomputing, vol. 62, no. 3, pp. 1263–1283, 2012.[15] S.-H. Lim, B. Sharma, G. Nam, E. K. Kim, and C. R. Das, “Mdcsim: A multi- tier data center simulation, platform,” in Cluster Computing and Workshops, 2009. CLUSTER’09. IEEE International Conference on, pp. 1–9, IEEE, 2009.[16] P. Jamshidi, A. Ahmad, and C. Pahl, “Autonomic resource provisioning for cloud- based software,” in Proceedings of the 9th International Symposium on Software Engineering for Adaptive and Self-Managing Systems, pp. 95–104, ACM, 2014.[17] D. Kusic and N. Kandasamy, “Risk-aware limited lookahead control for dynamic resource provisioning in enterprise computing systems,” Cluster Computing, vol. 10, no. 4, pp. 395–408, 2007.[18] H. C. Lim, S. Babu, and J. S. Chase, “Automated control for elastic storage,” in Proceedings of the 7th international conference on Autonomic computing, pp. 1–10, ACM, 2010.[19] M. N. Bennani and D. A. Menasce, “Resource allocation for autonomic data centers using analytic performance models,” in Autonomic Computing, 2005. ICAC 2005. Proceedings. Second International Conference on, pp. 229–240, IEEE, 2005.[20] S. Chaisiri, B.-S. Lee, and D. Niyato, “Optimal virtual machine placement across multiple cloud providers,” in Services Computing Conference, 2009. APSCC 2009. IEEE Asia-Pacific, pp. 103–110, IEEE, 2009.[21] S.-L. Chung, S. Lafortune, and F. Lin, “Limited lookahead policies in supervisory control of discrete event systems,” Automatic Control, IEEE Transactions on, vol. 37, no. 12, pp. 1921–1935, 1992.[22] M. Arlitt and T. Jin, “A workload characterization study of the 1998 world cup web site,” Network, IEEE, vol. 14, no. 3, pp. 30–37, 2000.[23] H. Zhang, G. Jiang, K. Yoshihira, H. Chen, and A. Saxena, “Intelligent workload factoring for a hybrid cloud computing model,” in Services-I, 2009 World Conference on, pp. 701–708, IEEE, 2009.[24] “U.S. Viewers Watched an Average of 3 Hours of Online Video in July - comScore, Inc.” http://www.comscore.com/Insights/Press-Releases/2007/09/ US-Online-Video-Streaming. (Accessed on 03/06/2016).[25] A. N. Avramidis and P. L’Ecuyer, “Modeling and simulation of call centers,” in Simulation Conference, 2005 Proceedings of the Winter, pp. 9–pp, IEEE, 2005.[26] N. Roy, A. Dubey, and A. Gokhale, “Efficient autoscaling in the cloud using predic- tive models for workload forecasting,” in Cloud Computing (CLOUD), 2011 IEEE International Conference on, pp. 500–507, IEEE, 2011.[27] I. Cunha, J. Almeida, V. Almeida, and M. Santos, “Self-adaptive capacity manage- ment for multi-tier virtualized environments,” in Integrated Network Management, 2007. IM’07. 10th IFIP/IEEE International Symposium on, pp. 129–138, IEEE, 2007.[28] J. A. Hartigan and M. A. Wong, “Algorithm as 136: A k-means clustering algorithm,” Journal of the Royal Statistical Society. Series C (Applied Statistics), vol. 28, no. 1, pp. 100–108, 1979.[29] K. R. Žalik, “An efficient k�-means clustering algorithm,” Pattern Recognition Letters, vol. 29, no. 9, pp. 1385–1391, 2008.[30] T. Kohonen, “The self-organizing map,” Proceedings of the IEEE, vol. 78, no. 9, pp. 1464–1480, 1990.[31] J. Vesanto and E. Alhoniemi, “Clustering of the self-organizing map,” Neural Net- works, IEEE Transactions on, vol. 11, no. 3, pp. 586–600, 2000.[32] A. Rauber, D. Merkl, and M. Dittenbach, “The growing hierarchical self-organizing map: exploratory analysis of high-dimensional data,” Neural Networks, IEEE Trans- actions on, vol. 13, no. 6, pp. 1331–1341, 2002.[33] D. G. Kendall, “Stochastic processes occurring in the theory of queues and their analysis by the method of the imbedded markov chain,” The Annals of Mathematical Statistics, pp. 338–354, 1953.[34] U. Herzog, L. Woo, and K. M. Chandy, “Solution of queuing problems by a recursive technique,” IBM Journal of Research and Development, vol. 19, no. 3, pp. 295–300, 1975.[35] I. Adan and J. Resing, “Queueing theory,” 2002.[36] E. Gelenbe, G. Pujolle, and J. Nelson, Introduction to queueing networks, vol. 2. Wiley Chichester, 1998.[37] X. Meng, J. Bradley, B. Yavuz, E. Sparks, S. Venkataraman, D. Liu, J. Freeman, D. Tsai, M. Amde, S. Owen, et al., “Mllib: Machine learning in apache spark,” arXiv preprint arXiv:1505.06807, 2015.[38] “Mllib | apache spark.” http://spark.apache.org/mllib/. (Accessed on 03/06/2016).[39] E. Buist and P. L’Ecuyer, “A java library for simulating contact centers,” in Proceed- ings of the 37th conference on Winter simulation, pp. 556–565, Winter Simulation Conference, 2005. 描述 碩士
國立政治大學
資訊管理學系
103356041資料來源 http://thesis.lib.nccu.edu.tw/record/#G0103356041 資料類型 thesis dc.contributor.advisor 蔡瑞煌<br>郁方 zh_TW dc.contributor.advisor Tsaih, Rua Huan<br>Yu, Fang en_US dc.contributor.author (作者) 褚宣凱 zh_TW dc.contributor.author (作者) Chu, Hsuan Kai en_US dc.creator (作者) 褚宣凱 zh_TW dc.creator (作者) Chu, Hsuan Kai en_US dc.date (日期) 2016 en_US dc.date.accessioned 2-八月-2016 17:02:27 (UTC+8) - dc.date.available 2-八月-2016 17:02:27 (UTC+8) - dc.date.issued (上傳時間) 2-八月-2016 17:02:27 (UTC+8) - dc.identifier (其他 識別碼) G0103356041 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/99553 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 資訊管理學系 zh_TW dc.description (描述) 103356041 zh_TW dc.description.abstract (摘要) 在服務資源需求量會隨時間而改變的情況下，系統的服務資源供給對致力於提供高服務品質的資源提供者來說是一個重要的議題。在服務資源可以迅速的部署和解除的假設下，像是以雲端運算為基礎之服務，本研究提供了系統性的估算服務資源方法，本方法之結構是以模擬為基礎並結合了非監督式學習、顧客到達率之估計以及統計技術。首先，本研究將每一日之顧客到達率進行分群運算並將具有類似顧客到達模式的日期分為一群，且每一群之包含日期具備可解釋之代表性；下一階段使用兩階段式的忙碌因子模型去建立每一群的顧客到達率模型，並估計該群的多區間普瓦松分布來做為系統模擬隨機過程所需之參數；最後應用了等候模型理論去設計系統模擬方法，模擬出顧客在系統中到達並接受服務的隨機過程，其結果包含觀察出顧客在系統中的等待時間和排隊長度以及所需之服務資源，並提供在不同的服務策略情形下之表現。本研究使用了一個來自電力公司客服中心之進線量資料進行本方法之實驗，展示出如何使用本方法建立一個能滿足服務水準要求的服務資源配置策略，也和該公司過去之配置策略進行比較，並提出實質上如何提升服務品質的配置策略之建議。 zh_TW dc.description.tableofcontents Contents1 Introduction 12 Literature Review 32.1 CloudSimulation 32.2 ResourceProvision 42.3 ArrivalRateEstimation 52.4 ClusteringMethods 62.4.1 K-Means 62.4.2 SOM 72.4.3 GHSOM 92.5 QueueingModel 113 Methodology 133.1 ArrivalPatternClustering 133.2 ArrivalRateModelingandEstimation 17 3.2.1 One-Layer model 17 3.2.2 SpecialCasesofOne-Layer model 20 3.2.3 Two-Layer model 213.3 StochasticSimulationwithQueuingModels 233.4 DynamicResourceProvision 274 Case Study 284.1 LogPreprocessStage 29 4.2 ArrivalPatternClustering 304.3 ArrivalRateModeling 32 4.4 SimulationParameterAdjustment 33 4.5 SimulationResult 36 4.6 SimulationPlatform 395 Conclusion 405.1 Summary 40 5.2 Limitation 40References 41 zh_TW dc.format.extent 1848312 bytes - dc.format.mimetype application/pdf - dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0103356041 en_US dc.subject (關鍵詞) 到達率估計 zh_TW dc.subject (關鍵詞) 服務資源配置 zh_TW dc.subject (關鍵詞) 隨時間序列改變之需求 zh_TW dc.subject (關鍵詞) 服務模擬 zh_TW dc.subject (關鍵詞) Arrival Rate Estimation en_US dc.subject (關鍵詞) Service Simulation en_US dc.subject (關鍵詞) Time-varying Demands en_US dc.subject (關鍵詞) Resource Provision en_US dc.title (題名) 基於時間序列下的動態需求之資源模擬 - 使用等候模型 zh_TW dc.title (題名) Simulating Time-Varying Demand Services with Queuing Models en_US dc.type (資料類型) thesis en_US dc.relation.reference (參考文獻) [1] R. Buyya, A. Beloglazov, and J. Abawajy, “Energy-efficient management of data center resources for cloud computing: a vision, architectural elements, and open challenges,” arXiv preprint arXiv:1006.0308, 2010.[2] P. Mell and T. Grance, “The nist definition of cloud computing,” 2011.[3] F. Yu, Y.-w. Wan, and R.-h. Tsaih, “Quantitative analysis of cloud-based streaming services,” in Services Computing (SCC), 2013 IEEE International Conference on, pp. 216–223, IEEE, 2013.[4] S. Chaisiri, B.-S. Lee, and D. Niyato, “Optimization of resource provisioning cost in cloud computing,” Services Computing, IEEE Transactions on, vol. 5, no. 2, pp. 164– 177, 2012.[5] E. Amazon, “Amazon elastic compute cloud (amazon ec2),” Amazon Elastic Compute Cloud (Amazon EC2), 2010.[6] R. N. Calheiros, M. A. Netto, C. A. De Rose, and R. Buyya, “Emusim: an integrated emulation and simulation environment for modeling, evaluation, and validation of performance of cloud computing applications,” Software: Practice and Experience, vol. 43, no. 5, pp. 595–612, 2013.[7] B. N. Oreshkin, N. Regnard, and P. L’Ecuyer, “Rate-based daily arrival process models with application to call centers,” tech. rep., Working Paper, Université de Montréal, 2014.[8] R. N. Calheiros, R. Ranjan, A. Beloglazov, C. A. De Rose, and R. Buyya, “Cloudsim: a toolkit for modeling and simulation of cloud computing environments and evalua- tion of resource provisioning algorithms,” Software: Practice and Experience, vol. 41, no. 1, pp. 23–50, 2011.[9] R. Buyya, R. Ranjan, and R. N. Calheiros, “Modeling and simulation of scalable cloud computing environments and the cloudsim toolkit: Challenges and opportuni- ties,” in High Performance Computing & Simulation, 2009. HPCS’09. International Conference on, pp. 1–11, IEEE, 2009.[10] B. Wickremasinghe, R. N. Calheiros, and R. Buyya, “Cloudanalyst: A cloudsim- based visual modeller for analysing cloud computing environments and applications,” in Advanced Information Networking and Applications (AINA), 2010 24th IEEE International Conference on, pp. 446–452, IEEE, 2010.[11] B. Wickremasinghe et al., “Cloudanalyst: A cloudsim-based tool for modelling and analysis of large scale cloud computing environments,” MEDC project report, vol. 22, no. 6, pp. 433–659, 2009.[12] S. K. Garg and R. Buyya, “Networkcloudsim: Modelling parallel applications in cloud simulations,” in Utility and Cloud Computing (UCC), 2011 Fourth IEEE In- ternational Conference on, pp. 105–113, IEEE, 2011.[13] W. Zhao, Y. Peng, F. Xie, and Z. Dai, “Modeling and simulation of cloud computing: A review,” in Cloud Computing Congress (APCloudCC), 2012 IEEE Asia Pacific, pp. 20–24, IEEE, 2012.[14] D. Kliazovich, P. Bouvry, and S. U. Khan, “Greencloud: a packet-level simulator of energy-aware cloud computing data centers,” The Journal of Supercomputing, vol. 62, no. 3, pp. 1263–1283, 2012.[15] S.-H. Lim, B. Sharma, G. Nam, E. K. Kim, and C. R. Das, “Mdcsim: A multi- tier data center simulation, platform,” in Cluster Computing and Workshops, 2009. CLUSTER’09. IEEE International Conference on, pp. 1–9, IEEE, 2009.[16] P. Jamshidi, A. Ahmad, and C. Pahl, “Autonomic resource provisioning for cloud- based software,” in Proceedings of the 9th International Symposium on Software Engineering for Adaptive and Self-Managing Systems, pp. 95–104, ACM, 2014.[17] D. Kusic and N. Kandasamy, “Risk-aware limited lookahead control for dynamic resource provisioning in enterprise computing systems,” Cluster Computing, vol. 10, no. 4, pp. 395–408, 2007.[18] H. C. Lim, S. Babu, and J. S. Chase, “Automated control for elastic storage,” in Proceedings of the 7th international conference on Autonomic computing, pp. 1–10, ACM, 2010.[19] M. N. Bennani and D. A. Menasce, “Resource allocation for autonomic data centers using analytic performance models,” in Autonomic Computing, 2005. ICAC 2005. Proceedings. Second International Conference on, pp. 229–240, IEEE, 2005.[20] S. Chaisiri, B.-S. Lee, and D. Niyato, “Optimal virtual machine placement across multiple cloud providers,” in Services Computing Conference, 2009. APSCC 2009. IEEE Asia-Pacific, pp. 103–110, IEEE, 2009.[21] S.-L. Chung, S. Lafortune, and F. Lin, “Limited lookahead policies in supervisory control of discrete event systems,” Automatic Control, IEEE Transactions on, vol. 37, no. 12, pp. 1921–1935, 1992.[22] M. Arlitt and T. Jin, “A workload characterization study of the 1998 world cup web site,” Network, IEEE, vol. 14, no. 3, pp. 30–37, 2000.[23] H. Zhang, G. Jiang, K. Yoshihira, H. Chen, and A. Saxena, “Intelligent workload factoring for a hybrid cloud computing model,” in Services-I, 2009 World Conference on, pp. 701–708, IEEE, 2009.[24] “U.S. Viewers Watched an Average of 3 Hours of Online Video in July - comScore, Inc.” http://www.comscore.com/Insights/Press-Releases/2007/09/ US-Online-Video-Streaming. (Accessed on 03/06/2016).[25] A. N. Avramidis and P. L’Ecuyer, “Modeling and simulation of call centers,” in Simulation Conference, 2005 Proceedings of the Winter, pp. 9–pp, IEEE, 2005.[26] N. Roy, A. Dubey, and A. Gokhale, “Efficient autoscaling in the cloud using predic- tive models for workload forecasting,” in Cloud Computing (CLOUD), 2011 IEEE International Conference on, pp. 500–507, IEEE, 2011.[27] I. Cunha, J. Almeida, V. Almeida, and M. Santos, “Self-adaptive capacity manage- ment for multi-tier virtualized environments,” in Integrated Network Management, 2007. IM’07. 10th IFIP/IEEE International Symposium on, pp. 129–138, IEEE, 2007.[28] J. A. Hartigan and M. A. Wong, “Algorithm as 136: A k-means clustering algorithm,” Journal of the Royal Statistical Society. Series C (Applied Statistics), vol. 28, no. 1, pp. 100–108, 1979.[29] K. R. Žalik, “An efficient k�-means clustering algorithm,” Pattern Recognition Letters, vol. 29, no. 9, pp. 1385–1391, 2008.[30] T. Kohonen, “The self-organizing map,” Proceedings of the IEEE, vol. 78, no. 9, pp. 1464–1480, 1990.[31] J. Vesanto and E. Alhoniemi, “Clustering of the self-organizing map,” Neural Net- works, IEEE Transactions on, vol. 11, no. 3, pp. 586–600, 2000.[32] A. Rauber, D. Merkl, and M. Dittenbach, “The growing hierarchical self-organizing map: exploratory analysis of high-dimensional data,” Neural Networks, IEEE Trans- actions on, vol. 13, no. 6, pp. 1331–1341, 2002.[33] D. G. Kendall, “Stochastic processes occurring in the theory of queues and their analysis by the method of the imbedded markov chain,” The Annals of Mathematical Statistics, pp. 338–354, 1953.[34] U. Herzog, L. Woo, and K. M. Chandy, “Solution of queuing problems by a recursive technique,” IBM Journal of Research and Development, vol. 19, no. 3, pp. 295–300, 1975.[35] I. Adan and J. Resing, “Queueing theory,” 2002.[36] E. Gelenbe, G. Pujolle, and J. Nelson, Introduction to queueing networks, vol. 2. Wiley Chichester, 1998.[37] X. Meng, J. Bradley, B. Yavuz, E. Sparks, S. Venkataraman, D. Liu, J. Freeman, D. Tsai, M. Amde, S. Owen, et al., “Mllib: Machine learning in apache spark,” arXiv preprint arXiv:1505.06807, 2015.[38] “Mllib | apache spark.” http://spark.apache.org/mllib/. (Accessed on 03/06/2016).[39] E. Buist and P. L’Ecuyer, “A java library for simulating contact centers,” in Proceed- ings of the 37th conference on Winter simulation, pp. 556–565, Winter Simulation Conference, 2005. zh_TW
