在網際網路資訊成長快速的時代，透過網路可以在短時間內存取非常多的資料。然而，越來越多的資料無法完全儲存於單一伺服器內。此外，網路中的使用者越來越多，網路中資料傳輸的頻率也越高，容易造成網路延遲的情況。當資料毀損時，可能造成資料無法存取或延遲取得，如此會降低資料存取的品質。
在資料網格中，複本配置問題被廣泛的探討，這個問題也被證明為NP-Complete，許多學者根據考量的因素不同而提出各自的啟發式演算法，目的是要找出有效率又接近最佳解的結果。本研究除了考量服務品質需求、伺服器的負荷量和需求量。為了避免資料傳遞時都透過相同路徑，造成網路阻塞、網路延遲時間增加等情況，所以也考慮了邊容量的因素。
本研究先將一般圖的網路架構轉換成二元圖並結合流量網路的概念，我們提出的啟發式演算法可以在多項式時間複雜度內找到複本配置，透過實驗結果說明本研究所提出的方法比CUDU[25]更接近最佳解。

With rapid growth of information on the Internet, a lot of data can be accessed in a short time through the Internet. However, it is impossible to completely store all the data in a server. Furthermore, the quick increasing of the users on the Internet not only raises the frequency of data transmission but also causes the delays of network. When data corruption occurs, data may not be retrieved or may be delayed in access, which will reduce the quality of data access.
In the data grid, the replica placement problem is widely discussed, which has been proven to be NP-Complete. Many researchers considered different factors in the proposed heuristic algorithms for finding replica placement which is close to the optimal solution. In our research, we consider Quality-of-Service requirement, server capacity, and server demand. In order to avoid transmission of data through the same path, which not only causes network obstruction but also increases network delays, we also consider edge capacity factors.
In this thesis, we convert network architectures into bipartite graphs with flow network. Then we use our heuristic algorithms to find a replica placement with polynomial time complexity. The experimental result shows that our algorithm results are closer to the optimal than those of CUDU[25].

[1] J. H. Abawajy, “Placement of File Replicas in Data Grid Environment”, Lecture Notes in Computer Science, Vol. 3038 , pp. 66-73 (2004)
[2] R. K. Ahuja, T. L. Magnanti and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, (1993)
[3] A. Benoit, V. Rehn-Sonigo and Y. Robert, “Replica Placement and Access Policies in Tree Networks”, IEEE Transactions on Parallel and Distributed Systems, Vol. 19, No. 12, pp. 1614-1627 (2008)
[4] Y. Chen, R. H. Katz and J. D. Kubiatowicz, “Dynamic Replica Placement for Scalable Content Delivery”, Lecture Notes in Computer Science, Vol. 2429 , pp. 306-318 (2002)
[5] C. W. Cheng, J. J. Wu and P. F. Liu, “QoS-aware, access-efficient, and storage-efficient replica placement in grid environments”, Journal of Supercomputing, Vol. 49, No. 1, pp. 42-63 (2009)
[6] A. Chervenak, I. Foster, C. Kesselman, C. Salisbury and S. Tuecke, “The data grid: Towards an architecture for the distributed management and analysis of large scientific datasets”, Journal of Network and Computer Applications, Vol. 23, No. 3, pp. 187-200 (2000)
[7] M. R. Garey and D. S. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness, W. H. Freeman and Company (1979)
[8] W. J. Jeon, I. Gupta and K. Nahrstedt, “QoS-aware Object Replication in Overlay Networks”, IEEE GLOBECOM Technical Conference, (2006)
[9] D. S. Johnson, “Approximation algorithms for combinatorial problems”, Journal of Computer and System Sciences, Vol. 9, pp. 256-278 (1974)
[10] 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)
[11] R. M. Karp, Reducibility Among Combinatorial Problems, Plenum Press, NY, (1972)
[12] B. J. Ko and D. Rubenstein, “Distributed Server Replication in Large Scale Networks”, Proceedings of the International Workshop on Network and Operating System, pp. 127-132 (2004)
[13] Y. F. Lin, P. F. Liu and J. J. Wu, “Optimal Placement of Replicas in Data Grid Environments with Locality Assurance”, Proceedings of the International Conference on Parallel and Distributed Systems - ICPADS, Vol. 1, pp. 465-472 (2006)
[14] L. Qiu, V. N. Padmanabhan and G. M. Voelker, “On the placement of web server replicas”, Proceedings of IEEE INFOCOM 2001, Vol. 3, pp. 1587-1596 (2001)
[15] R. M. Rahman, K. Barker and R. Alhajj, “Replica Placement in Data Grid: Considering Utility and Risk”, IEEE Information Technology: Coding and Computing 2005, Vol. 1, pp. 354-359 (2005)
[16] R. M. Rahman, K. Barker and R. Alhajj, “Replica Placement Strategies in Data Grid”, Journal of Grid Computing, Vol. 6, No. 1, pp. 103-123 (2008)
[17] X. Y. Tang, H. C. Chi and S. T. Chanson, “Optimal Replica Placement under TTL-Based Consistency”, IEEE Transactions on Parallel and Distributed Systems, Vol. 18, No. 3, pp. 351-363 (2007)
[18] X. Y. Tang and J. L. Xu, “On Replica Placement for Qos-Aware Content Distribution”, IEEE INFOCOM 2004, Vol. 2, pp. 806-815 (2004)
[19] 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)
[20] T. Wauters, J. Coppens, F. D. Turck, B. Dhoedt and P. Demeester, “Replica placement in ring based content delivery networks”, Computer Communications, Vol. 29, pp. 3313-3326 (2006)
[21] O. Wolfson and A. Milo, “The multicast policy and its relationship to replicated data placement”, ACM Transaction on Database Systems, Vol. 16, No. 1, pp. 181-205 (1991)
[22] J. J. Wu, Y. F. Lin and P. F. 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] S. Zaman and D. Grosu, “A Distributed Algorithm for the Replica Placement Problem”, IEEE Transactions on Parallel and Distributed Systems, Vol. 22, No. 9, pp. 1455-1468 (2011)
[24] 陳翰霖，「有容量的支配集問題的近似演算法」，碩士論文，國立臺灣大學，臺北 (2010)
[25] 趙哲寬，「服務品質與成本考量的錯誤容忍資料複本放置演算法」，碩士論文，國立臺灣科技大學，臺北 (2011)