在現今的IT環境中，人們對於資訊應用的需求與日俱增，而網格計算很適合滿足人們這方面的需求。因此，如何利用網格環境中的複本管理機制去建立複本，使得分散於各地的閒置資源進行整合，提供高效率的計算資源以及儲存空間，是近年來一直被廣泛研究的問題。
考量服務品質的資料複本配置問題是屬於NP-complete問題，針對不同的服務品質限制條件有許多不同的演算法被提出。本研究利用二元圖的架構去實現考量複本至網路節點的延遲時間限制、複本負荷量與網路節點需求量的複本配置演算法，並能讓每個網路節點都至少能連上K個複本節點，達到錯誤容忍的功效。
而在實驗分析中，利用隨機的方式產生一般圖以及實驗參數，並分析本研究所提出的方法與下限解作比較，而比較結果顯示本研究所提出之方法能夠在多項式時間複雜度得到一組與最佳解以及下限解相差不大的複本集合。

In the recent IT environment, the demand for information applications becomes ever increasing, where Grid computing can meet this requirement. Therefore, how to use replica management mechanism to build replica in Grids in order to integrate all of the idle resource into the high-efficiency computing resource and storage space has been extensively studied recently in this field.
One of the grid computing problems is the QoS-aware (Quality of Service-aware) replica placement problem, which belongs to a NP-complete problem. There are many different algorithms have been proposed for QoS constraints, for example, L-Greedy-Insert and L-Greedy-Delete. In this thesis, we propose replica placement algorithms, which considers network transmission latency, replica server workload, network demand, fault tolerance. These algorithms transform the replica placement problem into a Bipartite Graph and then solve the problem on the graph. Each network server could connect to K-th replica nodes. In other words, it can tolerate K-1 failure replica nodes in the network.
In this thesis, we create networks and assign the experiment parameters randomly for experiments. Then, we compare the lower bounds with the algorithm results. The experimental results show that the proposed algorithm could find out a set of replicas that can satisfy all nodes in the network with less number of replica and polynomial time complexity.

[1]J. H. Abawajy, “Placement of File Replicas in Data Grid Environment,” Lecture Notes in Computer Science, Vol. 3038, pp. 66-73 (2004).
[2]C.C.Bisdikian and B. V. Patel, “Cost-based program allocation for distributed multimedia-on-demand systems,”IEEE Computer Society PressMultimedia, Vol. 3, No. 3, pp. 62-72(1996).
[3]I. Foster, “The Grid: A New Infrastructure for 21st Century Science,” Physics Today, Vol. 55, No. 2, pp. 42-47 (2002).
[4]I. Foster, C. Kesselman, and S. Tuecke, “The Anatomy of the Grid: Enabling Scalable Virtual Organizations,” International Journal of High Performance Computing Applications, Vol. 15, No. 3, pp. 200-222(2001).
[5]W. Fu, N. Xiao, and X. Lu, “A Quantitative Survey on QoS-Aware Replica Placement,”Seventh International Conference onGrid and Cooperative Computing. IEEE, pp. 281-286 (2008).
[6]M. R. Garey and D. S. Johnson, “Computers and Intractability: A Guide to the Theory of NP-Completeness,”W.H. Freeman and Company,(1979).
[7]GridCafe, Retrieved from http://www2.twgrid.org/gridcafe/
[8]W. J. Jeon, I. Gupta and K. Nahrstedt, “QoS-aware Object Replication in Overlay Networks,” Global Telecommunications Conference, 2006. IEEE,pp. 1-5 (2006).
[9]D. S. Johnson, “Approximation algorithms for combinatorial problems,” The fifth Annual ACM Symposium on Theory of Computing, pp. 38-49 (1973).
[10]K. Kalpakis, K. Dasgupta and O. Wolfson, “Optimal Placement of Replicas in Trees with Read, Write, and Storage Costs”,IEEE Transactions on Parallel and Distributed Systems, Vol. 12, No. 6, pp. 628- 637(2001).
[11]M. J. Kao and H. L. Chen, “Approximation Algorithms for the Capacitated Domination Problem,” Lecture Notes in Computer Science, Vol. 6213,pp. 185-196 (2010).
[12]H. Lamehamedi, Z. Shentu, B. Szymanski, E. Deelman,“Simulation of dynamic data replication strategies in data grids,” IEEE Computer Science Press, Parallel and Distributed Processing Symposium (2003).
[13]D.Pisinger, “A minimal algorithm for the Multiple-Choice Knapsack Problem,”European Journal of Operational Research, Vol. 83, No. 2, pp. 394-410 (1995).
[14]K. Ranganathan, I. Foster, “Design and evaluation of dynamic replication strategies for a high performance data grid,”International Conference on Computing in High Energy and Nuclear Physics, Vol. 2001( 2001).
[15]K. Ranganathana and I. Foster, “Identifying dynamic replication strategies for a high performance data grid,”In Proceedings of the International Grid Computing Workshop, pp. 75-86(2001).
[16]G. Sushant, B. Rajkumar, “Data Replication Strategies in Wide Area Distributed Systems”, Enterprise Service Computing: From Concept to Development,IGI Global,(2006).
[17]X. Y. Tang and J. L. Xu, “On replica Placement for Qos-aware content distribution,” IEEE Computer and Communications Society, Vol. 2, pp. 806-815(2004).
[18]X. Y. Tang and J. L. Xu, “QoS-Aware Replica Placement for Content Distribution,” IEEE Transactions on Parallel and Distributed Systems, Vol. 16, No. 10, pp. 921-932 (2005).
[19]TWGrid, Retrieved from http://www.twgrid.org/
[20]H. K. Wang, P. F. Liu and J. J. Wu, “A QoS-Aware Heuristic Algorithm for Replica Placement,” Proceedings IEEE/ACM International Workshop on Grid Computing, pp.96-103 (2006).
[21]T.Wauters, J.Coppens, F. D.Turck, B.Dhoedt,P.Demeester, “Replica placement in ring based content delivery networks,”Computer Communications, Vol. 29, No. 16, pp.3313-3326(2006).
[22]J.J. Wu, Y.F. Lin, P. Liu, “Optimal replica placement in hierarchical data grids with locality assurance,”Journal of Parallel and Distributed Computing, Vol. 68, No. 12, pp.1517-1538(2008).
[23]N. Xiao, W. Fu and X. C. Lu, “QoS-awared replica placement techniques in data grid applications,”SCIENCE CHINA Information Sciences, Vol. 53, No. 8, pp. 1487-1496 (2010).
[24]陳翰霖，「有容量的支配集問題的近似演算法」，碩士論文，國立台灣大學，台北 (2010)。
[25]趙哲寬，「服務品質與成本考量的錯誤容忍資料複本放置演算法」，碩士論文，國立台灣科技大學，台北 (2011)。