學術產出-學位論文

文章檢視/開啟

書目匯出

Google ScholarTM

政大圖書館

引文資訊

TAIR相關學術產出

題名 基於時間序列下的動態需求之資源模擬 - 使用等候模型
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, Fangen_US
dc.contributor.author (作者) 褚宣凱zh_TW
dc.contributor.author (作者) Chu, Hsuan Kaien_US
dc.creator (作者) 褚宣凱zh_TW
dc.creator (作者) Chu, Hsuan Kaien_US
dc.date (日期) 2016en_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 (其他 識別碼) G0103356041en_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 (描述) 103356041zh_TW
dc.description.abstract (摘要) 在服務資源需求量會隨時間而改變的情況下,系統的服務資源供給對致力於提供高服務品質的資源提供者來說是一個重要的議題。在服務資源可以迅速的部署和解除的假設下,像是以雲端運算為基礎之服務,本研究提供了系統性的估算服務資源方法,本方法之結構是以模擬為基礎並結合了非監督式學習、顧客到達率之估計以及統計技術。首先,本研究將每一日之顧客到達率進行分群運算並將具有類似顧客到達模式的日期分為一群,且每一群之包含日期具備可解釋之代表性;下一階段使用兩階段式的忙碌因子模型去建立每一群的顧客到達率模型,並估計該群的多區間普瓦松分布來做為系統模擬隨機過程所需之參數;最後應用了等候模型理論去設計系統模擬方法,模擬出顧客在系統中到達並接受服務的隨機過程,其結果包含觀察出顧客在系統中的等待時間和排隊長度以及所需之服務資源,並提供在不同的服務策略情形下之表現。
本研究使用了一個來自電力公司客服中心之進線量資料進行本方法之實驗,展示出如何使用本方法建立一個能滿足服務水準要求的服務資源配置策略,也和該公司過去之配置策略進行比較,並提出實質上如何提升服務品質的配置策略之建議。
zh_TW
dc.description.tableofcontents Contents
1 Introduction 1
2 Literature Review 3
2.1 CloudSimulation 3
2.2 ResourceProvision 4
2.3 ArrivalRateEstimation 5
2.4 ClusteringMethods 6
2.4.1 K-Means 6
2.4.2 SOM 7
2.4.3 GHSOM 9
2.5 QueueingModel 11
3 Methodology 13
3.1 ArrivalPatternClustering 13
3.2 ArrivalRateModelingandEstimation 17
3.2.1 One-Layer model 17
3.2.2 SpecialCasesofOne-Layer model 20
3.2.3 Two-Layer model 21
3.3 StochasticSimulationwithQueuingModels 23
3.4 DynamicResourceProvision 27
4 Case Study 28
4.1 LogPreprocessStage 29
4.2 ArrivalPatternClustering 30
4.3 ArrivalRateModeling 32
4.4 SimulationParameterAdjustment 33
4.5 SimulationResult 36
4.6 SimulationPlatform 39
5 Conclusion 40
5.1 Summary 40
5.2 Limitation 40
References 41
zh_TW
dc.format.extent 1848312 bytes-
dc.format.mimetype application/pdf-
dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0103356041en_US
dc.subject (關鍵詞) 到達率估計zh_TW
dc.subject (關鍵詞) 服務資源配置zh_TW
dc.subject (關鍵詞) 隨時間序列改變之需求zh_TW
dc.subject (關鍵詞) 服務模擬zh_TW
dc.subject (關鍵詞) Arrival Rate Estimationen_US
dc.subject (關鍵詞) Service Simulationen_US
dc.subject (關鍵詞) Time-varying Demandsen_US
dc.subject (關鍵詞) Resource Provisionen_US
dc.title (題名) 基於時間序列下的動態需求之資源模擬 - 使用等候模型zh_TW
dc.title (題名) Simulating Time-Varying Demand Services with Queuing Modelsen_US
dc.type (資料類型) thesisen_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