臺灣博碩士論文加值系統

雲端運算是近年來成長快速且受歡迎的新興服務遞送模式。雲端供應商可以在特定的時間將配有硬體資源(resources)、開發平台(Development Platform)或應用程式服務(Application Service)的虛擬機器(Virtual Machine, VM)指派給使用者。
提供這些服務的雲端供應商可以用服務類型分成三類：
(1)提供商業軟體當作服務(Software as a Service; SaaS)
(2)提供開發平台為服務(Platform as a service; PaaS)
(3)提供硬體資源當服務(Snfrastructure as a service; IaaS)並以隨支隨付(Pay as you use)的付費方式來計算出租雲端服務的使用費用 [20]。
目前在各種類型的雲端服務有許多知名廠商積極投入。 SaaS供應商為達成平均總成本支出的目標，需要在不同環境參數下決定資源池規模大小與組成資源池的虛擬機器種類。資源池規模大小與組成資源池機器種類將決定SaaS供應商的租賃成本與違背成本。 SaaS供應商為根據使用者數量，將資源池中不同種類的虛擬機器數量擴張或收縮以期達到有效之資源提供方式。
本研究主要目的是在隨機的使用者需求下，根據平均使用者抵達人數與需求波動大小將決定資源池(resource pool)內虛擬機器種類間的比例，並達到雲端供應商支付服務運行成本(租賃成本加違約成本)最小化的目標。
本研究將此問題分成兩個階段(Phase)進行解題：
在第一階段，本研究根據平均使用者抵達人數與需求波動大小決定資源池初始規模大小。
在第二階段，延續第一階段的資源池規模大小，根據使用者等候狀態調整建構資源池中虛擬機器的比例。
本研究針對上述步驟建立隨機派翠網模型(Stochastic Petri Nets, SPN)評估雲端資源提供策略並設計三個實驗佐證我們的想法是正確的
(1)同預期人數不同抵達變異程度對機台類型比例的影響
(2)用多種虛擬機器組合資源池比單一虛擬機器有較低的成本
(3)變異驅動資源指派策略和 optimal multiserver approach比較。

關鍵字：雲端運算、資源提供策略、隨機派翠網、虛擬機器比例

In this paper, we discuss how to decide SaaS vendor resources size and type under different user behavior, lead to average total cost minimum.
We propose ``Arrival Variance-based Methods for Resource Provision and Allocation Management with Heterogeneous Types of VMs' according to the average user arrivals determine the size of the resource pool and virtual machines type ratio within cloud service providers to achieve goal.
We designed a series of experiments to support our idea is correct and experiments results show our methods is significant.

目錄
書名頁. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
論文口試委員審定書 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
中文摘要. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
英文摘要. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
誌謝. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii
目錄. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix
表目錄. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii
圖目錄. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii
一、緒論. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 研究背景. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 研究動機. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 研究目的. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.4 相關研究進展與限制. . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.5 資源提供問題的想法與解決方案框架. . . . . . . . . . . . . . . . . . . 4
1.6 貢獻. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.7 論文架構. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
二、文獻討論. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
三、環境. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.1 雲端運算(Cloud Computing) . . . . . . . . . . . . . . . . . . . . . . . . 8
3.1.1 雲端運算演進. . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.1.2 雲端運算定義與特性. . . . . . . . . . . . . . . . . . . . . . . . 9
3.1.3 雲端服務類型與佈署種類. . . . . . . . . . . . . . . . . . . . . 11
3.2 SaaS 雲端服務架構(SaaS Service Framework) . . . . . . . . . . . . . . 12
3.3 SaaS 商業模式(SaaS Business Model) . . . . . . . . . . . . . . . . . . . 12
3.3.1 租賃模型(lease model) . . . . . . . . . . . . . . . . . . . . . . . 12

3.3.2 懲罰模型(penalty model) . . . . . . . . . . . . . . . . . . . . . . 14
3.4 隨機派翠網路. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.4.1 隨機派翠網路元件與定義. . . . . . . . . . . . . . . . . . . . . 14
3.5 半馬可夫決策過程. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
四、問題定義. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.1 隨機動態的線性模型. . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
五、方法提案. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.1 變異驅動雲端資源提供設計構想. . . . . . . . . . . . . . . . . . . . . . 22
5.2 需求變異驅動雲端資源提供與指派求解流程. . . . . . . . . . . . . . . 23
5.3 需求變異驅動雲端資源提供與指派計算細節. . . . . . . . . . . . . . . 24
六、模擬. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
6.1 模擬的基本概念. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
6.2 選擇模擬工具：Stochastic Petri Net . . . . . . . . . . . . . . . . . . . 26
6.3 模擬雲端特色行為. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
6.4 SPN模型. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
6.4.1 任務抵達行為模擬. . . . . . . . . . . . . . . . . . . . . . . . . 29
6.4.2 使用者SLA違背行為模擬. . . . . . . . . . . . . . . . . . . . . . 29
6.4.3 計算資源指派行為模擬. . . . . . . . . . . . . . . . . . . . . . . 29
6.4.4 使用者服務行為模擬. . . . . . . . . . . . . . . . . . . . . . . . 30
6.4.5 計算資源縮放行為. . . . . . . . . . . . . . . . . . . . . . . . . 31
6.4.6 雲端系統績效成本模型. . . . . . . . . . . . . . . . . . . . . . . 33
6.4.7 模型參數化. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
七、實驗. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
7.1 實驗參數設定. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
7.2 對照組設定. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
7.3 實驗一：同預期人數不同抵達變異程度對機台類型比例的影響. . . . . 36
7.4 實驗二：用多種虛擬機器組合資源池比單一虛擬機器有較低的成本. . 37
7.5 實驗三：變異驅動資源指派策略和optimal multiserver approach比較. 38
八、結論. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
參考文獻. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

表目錄
5.1 環境參數意義與說明. . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5.2 決策參數意義與說明. . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
6.1 SPN架構轉移元件意義與說明. . . . . . . . . . . . . . . . . . . . . . . 28
6.2 SPN架構元件位置意義與說明. . . . . . . . . . . . . . . . . . . . . . . 29
7.1 環境參數意義與說明. . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

圖目錄
1 Optimum proportion of different types of virtual machines . . . . . . . vi
2 single-type resource pool V.S. Multi-type resource pool . . . . . . . . . vii
3 our methods V.S. optimal multiserver approach . . . . . . . . . . . . . vii
1.1 企業外包給SaaS供應商管理QoS示意圖. . . . . . . . . . . . . . . . . . 2
1.2 成本與品質關係圖. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 研究流程圖. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 論文組織架構圖. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.1 雲端運算演進圖. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2 雲端服務種類示意圖. . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.3 雲端SaaS服務架構. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.4 SLA懲罰模型. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.5 SLA範例說明. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.6 半馬可夫決策範例說明. . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.1 時間軸與決策之間關係圖. . . . . . . . . . . . . . . . . . . . . . . . . 18
4.2 系統行為與狀態轉移圖. . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.1 使用者抵達變異小. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.2 使用者抵達變異大. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.3 需求量變異. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.4 變異程度大. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
6.1 雲端提供與指派行為SPN模型. . . . . . . . . . . . . . . . . . . . . . . 30
6.2 使用者抵達雲端服務系統進入佇列等待行為之SPN模型。. . . . . . . 30
6.3 使用者等候太久導致SaaS供應商違背SLA行為之SPN模型。. . . . . . 31
6.4 計算資源指派行為SPN模型. . . . . . . . . . . . . . . . . . . . . . . . 31
6.5 使用者接受雲端服務. . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
6.6 計算資源縮放行為SPN模型. . . . . . . . . . . . . . . . . . . . . . . . 32
7.1 同預期人數不同抵達變異程度對機台類型比例的影響. . . . . . . . . . 37
7.2 用多種虛擬機器組合資源池比單一虛擬機器有較低的成本. . . . . . . 38
7.3 總成本比較圖. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
7.4 租賃成本比較圖. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
7.5 違背成本比較圖. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

[1] abiquo. [Online]. Available: http://www.abiquo.com/.
[2] accelops. [Online]. Available: http://www.accelops.com/.
[3] Amazon ec2. [Online]. Available: http://aws.amazon.com/cn/ec2/.
[4] appdynamics. [Online]. Available: http://www.appdynamics.com/.
[5] Appistry. [Online]. Available: http://www.appistry.com/.
[6] Appscale. [Online]. Available: http://www.appscale.com/.
[7] At＆t cloud 101. [Online]. Available: https://www.synaptic.att.com/
clouduser/html/cloud101/Cloud_101_Details.htm.
[8] Bluelock. [Online]. Available: http://www.bluelock.com/.
[9] Chelsio communications. [Online]. Available: http://www.chelsio.com/.
[10] Einstein@home. [Online]. Available: http://www.einstein-online.info/
spotlights/EaH.
[11] How to scale an application. [Online]. Available: http://www.windowsazure.
com/en-us/documentation/articles/cloud-services-how-to-scale/.
[12] Hp performance optimized datacenter. [Online]. Available: http://www.ndm.net/
hppod/.
[13] Openstack. [Online]. Available: http://www.openstack.org/.
[14] Oracle’s on demand crm software. [Online]. Available: http://www.oracle.com/
us/products/applications/crmondemand/index.html.
[15] Salesforce. [Online]. Available: http://www.salesforce.com/tw/?ir=1.
[16] Sap er. [Online]. Available: http://www.sacom/index.html.
[17] Smartcloud enterprise. [Online]. Available: http://www-935.ibm.com/
services/us/en/cloud-enterprise/index.html.
[18] workday. [Online]. Available: http://www.workday.com/ap/.
[19] D. Ardagna and M. Passacantando. Generalized nash equilibria for the service provisioning problem in cloud systems. IEEE Transactions on Service Computing, 6:429–442, 2013.
[20] M. Armbrust, A. Fox, R. Griffith, A. D. Joseph, R. Katz, A. Konwinski, G. Lee, D. Patterson, A. Rabkin, I. Stoica, and M. Zaharia. A view of cloud computing. In Communications of the ACM, volume 53, pages 50–58. April 2010.
[21] S. Aulbach, T. Grust, D. Jacobs, A. Kemper, and J. Rittinger. Multi-tenant databases for software as a service: Schema-mapping techniques. ACM SIGMOD International Conference on Management of Data, pages 1195–1206, 2008.
[22] A. Beloglazov, J. Abawajy, and R. Buyya. Energy-aware resource allocation heuristics for efficient management of data centers for cloud computing. Future Generation Computer Systems, 28:755–768, 2012.
[23] A. Benlian, M. Koufaris, and T. Hess. Service quality in software-as-a-service: Developing the saas-qual measure and examining its role in usage continuance. Journal of Management Information Systems, 8:85–126, 2011.
[24] D. Bruneo. A stochastic model to investigate data center performance and qos in iaas cloud computing systems. IEEE Transactions on Parallel and Distributed System, 25:560–569, 2014.
[25] M. Bulmer. Principles of Statistics. Dover Publications, 1979.
[26] J. M. Butler, W. Theilmann, and R. Yahyapour. Service Level Agreements for Cloud Computing. Springer, 2011.
[27] J. Cao, K. Hwang, K. Li, and A. Y. Zomaya. Optimal multiserver configuration for profit maximization in cloud computing. IEEE Transactions on Parallel and Distributed System, 24:1087–1096, 2013.
[28] A. Castro, V. Villagra, B. Fuentes, and B. Costales. A flexible architecture for service management in the cloud. IEEE Transactions on Network and Service Management, 11:116–125, 2014.
[29] C. E. Catlett. In search of gigabit applications. In IEEE Communications Magazine. IEEE, 1992.
[30] S. Chaisiri, B.-S. Lee, , and D. Niyato. Optimization of resource provisioning cost in cloud computing. IEEE Transactions on Service Computing, 5(2):164–177, 2012.
[31] G. Ciardo, R. German, and C. Lindemann. A characterization of the stochastic process underlying a stochastic petri net. IEEE Transactions on Software Engineering, 20:506–515, 1994.
[32] Y. Dong, Y. Xia, Q. Zhu, and Y. Huang. A stochastic approach to predict performance of web service composition. In International Symposium on Electronic Commerce and Security, pages 460–464. IEEE, 2009.
[33] J. Du, D. J. Dean, Y. Tan, X. Gu, and T. Yu. Scalable distributed service integrity attestation for software-as-a-service clouds. IEEE Transactions on Parallel and Distributed System, PP(99), 2013.
[34] T. Genez, L. Bittencourt, and E. Madeira. Workflow scheduling for saas / paas cloud providers considering two sla levels. In Network Operations and Management Symposium (NOMS), pages 906–912. IEEE, 2012.
[35] C. Gravier, J. Subercaze, A. Najjar, F. Laforest, X. Serpaggi, and O. Boissier. Context awareness as a service for cloud resource optimization. IEEE Internet Computing, PP:1089–7801, 2013.
[36] C. Hirel, B. Tuffin, and K. Trivedi. Spnp: Stochastic petri nets. version 6.0. In B. Haverkort, H. Bohnenkamp, and C. Smith, editors, Computer Performance Evaluation.Modelling Techniques and Tools, volume 1786, pages 354–357. Springer Berlin Heidelberg, 2000.
[37] Z. Huang, C. He, L. Gu, and J. Wu. On-demand service in grid: Architecture, design and implementation. In International Conference on Parallel and Distributed Systems. IEEE Computer Society, 2005.
[38] A. Iosup, S. Ostermann, M. N. Yigitbasi, R. Prodan, T. Fahringer, and D. H. Epema. Performance analysis of cloud computing services for many-tasks scientific computing. IEEE Transactions on Parallel and Distributed System, 22:931–945, 2011.
[39] L. Jianjie, H. Zhaohui, Y. Xuan, Z. Ran, and X. Chengan. Analysis of process of triage in disaster rescue action using stochastic petri net. In Industrial Control and Electronics Engineering, pages 111–115. IEEE, 2012.
[40] M. Jo, Y. W. Ahn, A. Cheng, J. Baek, and H.-H. Chen. An auto-scaling mechanism for virtual resources to support mobile, pervasive, real-time healthcare applications in cloud computing. IEEE Network, 27:62–68, 2013.
[41] E. C. Jr, A. Puhalskii, M. Reiman, and E. Wright. Processor-shared buffers with reneging. Performance Evaluation, 19:26 –46, 1994.
[42] E. Kao. A semi-markovian population model with application to hospital planning. IEEE Transactions on Systems Man and Cybernetics, 3:327–336, 1973.
[43] L. Lei, Y. Han, and Z. Zhong. Performance analysis of device-to-device communications with frequency reuse using stochastic petri nets. In Wireless Networking Symposium, pages 6354–6359. IEEE, 2013.
[44] H. Liang, L. X. Cai, D. Huang, X. Shen, and D. Peng. An smdp-based service model for interdomain resource allocation in mobile cloud networks. IEEE Transactions on Vehicular Technology, 61:2222–2232, 2012.
[45] H. Liao. Saas business model for software enterprise. In Information Management and Engineering (ICIME), pages 604–607. IEEE, 2010.
[46] C. LIN and D. C. Marinescu. Stochastic high-level petri nets and applications. IEEE Transactions on Computers, 37:815–823, 1998.
[47] F. Liu, B. Li, Z. Zhou, B. Li, H. Jin, and H. Jiang. On arbitrating the powerperformance tradeoff in saas clouds. IEEE Transactions on Parallel and Distributed System, PP(99):1, 2013.
[48] D. Ma. The business model of software-as-a-service. In International Conference on Services Computing. IEEE, 2007.
[49] Z. Ma, P. E. Caines, and R. Malhame. Control of admission and routing in loss networks: Hybrid dynamic programming equations. IEEE Transactions on Automatic Control, 55:350–366, 2010.
[50] M. Mao and M. Humphrey. A performance study on the vm startup time in the cloud. In International Conference on Cloud Computing, pages 423–430. IEEE, 2012.
[51] P. Mell and T. Grance. The nist definition of cloud computing. Technical Report Special Publication 800-145, National Institute of Standards and Technology U.S. Department of Commerce, September 2011.
[52] Y. Mo, J. Chen, X. Xie, C. Luo, and L. T. Yang. Cloud-based mobile multimedia recommendation system with user behavior information. Ieee Systems Journal, 8:184–193, 2014.
[53] S. Namasivayam. Profiting from business process outsourcing. In IT Pro. IEEE Computer Society, 2004.
[54] V. Nikolopoulos, G. Mpardis, I. Giannoukos, I. Lykourentzou, and V. Loumos.
Web-based decision-support system methodology for smart provision of adaptive digital energy services over cloud technologies. IET Software, 5:454–465, 2011.
[55] Z. Pervez, S. Lee, and Y.-K. Lee. Multi-tenant, secure, load disseminated saas architecture. In International Conference on Advanced Communication Technology, pages 214–219. IEEE, 2010.
[56] B. Silva, P. Maciel, J. Brilhante, and A. Zimmermann. Geoclouds modcs: A perfomability evaluation tool for disaster tolerant iaas clouds. In Systems Conference. IEEE, 2014.
[57] H. Sun, S. Huang, Y. Fan, and W. Su. Configuration and optimization of virtual business in cloud computing environment. In International Conference on Cloud and Green Computing. IEEE, 2012.
[58] W. Tan and M. Zhou. Business and Scientific Workflows: A Web Service-Oriented Approach. Wiley-IEEE Press, 2013.
[59] J. Tang, W. P. Tay, and Y. Wen. Dynamic request redirection and elastic service scaling in cloud-centric media networks. IEEE Transactions on Multimedia, PP:1–13, 2014.
[60] R. Uhlig, G. Neiger, D. Rodgers, A. L.Santoni, F. C. Martins, A. V. Anderson, S. M.Bennett, A. K. F. H, and L. L. Smith. Intel virtualization technology. In IEEE Computer Society. IEEE, 2005.
[61] J. Walz and D. Grier. Time to push the cloud. IT Professional, 12:14–16, 2010.
[62] L. Wu, S. K. Garg, S. Versteeg, and R. Buyya. Sla-based resource provisioning for software-as-a-service applications in cloud computing environments. IEEE Tarnsactions on Services Computing, pp:1–30, 2013.
[63] Z. Xiao, W. Song, and Q. Chen. Dynamic resource allocation using virtual machine for cloud computing environment. IEEE Transactions on Parallel and Distributed System, 24(6):1107–1117, 2013.
[64] B. Yang and L. Wei-Hong. Capability evaluation of air cargo export handling system using stochastic petri net. In Logistics Systems and Intelligent Management, pages 1583–1593. IEEE, 2010.
[65] S.-T. Yee and J. A. Ventura. Phase-type approximation of stochastic petri nets for analysis of manufacturing systems. IEEE Transactions on RoboticsA and automation, 16:318–322, 2000