雲端儲存中工作排程問題的演算法

Algorithms for Task Scheduling Problem in Cloud Storage

楊舜宇

指導教授 ： 許健平

國立清華大學/電機資訊學院/資訊工程學系/碩士(2013年)

摘要

近年來雲端運算在學界與業界都是一個熱門的議題，越來越多的雲端資料服務提供可信賴的與靈活的資料儲存服務給使用者。如何提供服務達到使用者的服務層級協議(service level agreement ; SLA)，對於服務提供者與使用者是很重要的議題。服務提供者必須排程每一個使用者的任務，並且決定這些任務應該被哪個伺服器服務，使得服務提供者可以服務更多的使用者。因為這個任務排程問題在雲端儲存中是一個NP-hard的問題，我們提出啟發式演算法解決這個問題，與最佳解相比，我們的方法有不錯的效能，並且我們的演算法在頻寬分配率跟隨機的方法比好了平均百分之十，在請求服務率跟隨機的方法比好了平均百分之十五。

關鍵字

雲端運算 ； 資料中心網路 ； 資料存儲 ； 資源分配

參考文獻

[2] H. Amur, J. Cipar, V. Gupta, G. R. Ganger, M. A. Kozuch, and K. Schwan, “Robust and flexible power-proportional storage,” in Proceedings of the 1st ACM Symposium on Cloud Computing, Indianapolis, Indiana, USA, June 10–11, 2010.

[4] J. Broberg, R. Buyya, and Z. Tari, “MetaCDN: Harnessing 'storage clouds' for high performance content delivery”, Journal of Network and Computer Applications, vol. 32 no. 5, pp. 1012–1022, September 2009.

[13] J. Kim and D. Rotem, “FREP: energy proportionality for disk storage using replication,“ Journal of Parallel and Distributed Computing vol. 72, issue 8, pp. 960–974, August 2012.

[14] J. M. Kleinberg, “Single-source unsplittable flow,” in Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Washington, DC, USA, pp. 68–77, 1996.

[17] Y. Xiao, Y. Li, J. Wang, and H. Gao, “An energy-efficient data placement algorithm and node scheduling strategies in cloud computing systems,” in 2nd International Conference on Advances in Computer Science and Engineering, Los Angeles, CA, USA, 2013.