劉邦鋒臺灣大學：資訊工程學研究所鄭傑文Cheng, Chieh-WenChieh-WenCheng2007-11-262018-07-052007-11-262018-07-052007http://ntur.lib.ntu.edu.tw//handle/246246/53664在網路上有一份資料需要被很多人使用到，我們可以將這一份資料複製成好幾分複品，放在網路上不同的地方，供大家使用以增加存取的速度。但是網路上在溝通時會有延遲，所以我們需要一個好的放置策略，來降低這些延遲。這篇論文同時考慮了服務品質的保證以及整個系統的效能，我們提出兩個演算法來決定副本的放置策略，實驗結果顯示我們的方法找到的結果很接近最佳解。This paper studies the QoS-aware replica placement problem in grid environments, given the workload capacity restriction of each replica server. Although there has been much work on replica placement problem, most of them concern average system performance and ignore quality assurance issue. However, we believe that quality assurance is very important, especially in heterogeneous environments. The capacity that each replica server can process is also a key factor in service quality assurance. In this paper, we propose two heuristic algorithms that determine the positions of replicas in order to minimize the sum of update, storage and access cost and satisfy the quality requirements imposed by data requests and the capacity constraint of each replica server. The experimental results indicate that the proposed algorithms find a near-optimal solution effectively and efficiently. Our algorithms can also adapt to various parallel and distributed environments.1 Introduction 1 2 Related Works 4 3 System Model 7 3.1 Replication Cost . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.2 Service Quality Requirement . . . . . . . . . . . . . . . . . . . 9 3.3 Workload Capacity Constraint . . . . . . . . . . . . . . . . . . 10 3.4 QoS-aware Replica Placement With Capacity Constraint . . . 10 4 Heuristic Algorithms 12 4.1 QoS Satisfying Set . . . . . . . . . . . . . . . . . . . . . . . . 12 4.2 Greedy Remove . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.2.1 Time Complexity Analysis . . . . . . . . . . . . . . . . 14 4.3 Greedy Add . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.3.1 Time Complexity Analysis . . . . . . . . . . . . . . . . 18 4.4 Random . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 5 Performance Evaluation 20 5.1 The effects of Workload . . . . . . . . . . . . . . . . . . . . . 22 5.2 The effects of Capacity Constraint . . . . . . . . . . . . . . . . 22 5.3 The effects of QoS . . . . . . . . . . . . . . . . . . . . . . . . 24 5.4 The effects of Storage Cost . . . . . . . . . . . . . . . . . . . . 26 5.5 Execution Time . . . . . . . . . . . . . . . . . . . . . . . . . . 26 6 Conclusion 30310356 bytesapplication/pdfen-US服務品質演算法複品放置策略效能QoSheuristicreplicaplacementperformancethesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53664/1/ntu-96-R94922135-1.pdf