在網際網路蓬勃發展的今天，網路資料每天的存取量已經不是我們可以想像的數字了，如此大量的檔案或資料已經無法全部儲存在同一台檔案伺服器中，不但會降低效率、也提高資料損壞無法修復的風險。除此之外網路使用者數量越來越多，使用者要求的資料若無法由其他鄰近或負載較低的伺服器提供，就得耗費大量的時間來等候伺服器的回傳，導致許多具有時效性的系統無法在要求的特定時間內得到資料。
目前有多位學者致力於探討該如何透過最少的複本伺服器來滿足所有使用者的服務品質需求，該類問題已有許多啟發式演算法或近似演算法的研究成果，但是所解決的問題層面不夠廣泛，鮮少有提出考量錯誤容忍和伺服器負荷量的複本放置演算法，因此在本研究中，我們將該類問題轉換成網路流量的問題，同時兼顧複本放置、錯誤容忍以及負荷量限制的應用情境，並且能夠找出最小傳輸成本的流量配置。本研究利用二元圖(Bipartite Graph)結合網路流量的架構，從中發現許多相關問題的解決與改進方法。
本研究將深入探討當複本放置的問題轉換為網路流量模式之後，可以利用哪些圖論的方法來解決眾多疑難雜症，以及其他相關且應用在該架構上的問題，並且找出有效率又接近最佳解的複本放置啟發式演算法(Heuristic Algorithm)，實驗結果也證實了本論文所提出的方法與最佳解差異不大，但是在時間方面卻比最佳解快了許多。

With the rapid development of the Internet, the volume of network resources and resource accessing rate are not what we could imagine. It is even impossible to put all the data together in only one network file server, which not only reduces the efficiency but also raises the risk of unrecovered file damage. In addition, due to the rapid increasing of network users, once the request data cannot be serviced by nearby or not overloaded data server, users have to spend much time on waiting for server response. This situation causes many real time system cannot obtain essential data in specific time delay.
Recently, there are many researchers devoting to the research of using as least as possible replica servers to satisfy all the network users' Quality-of-Service (QoS) requirement. There are a lot of solutions by heuristic algorithms or approximation algorithms for similar research issues, but few of replica placement researches take the fault tolerance and replica server workload into consideration. In our research, we consider replica placement, fault tolerance and workload limits situation. We transform replica placement problem into network flow problem and find out the data flow deployment strategy with the minimum transmission cost. In addition, we use the architecture of Bipartite Graph integrates with network flow and find out lots of related problem solutions and improvements.
In this thesis, we will utilize graph algorithms to solve the problems or related applications after we transformed the replica placement problem into network flow model. Furthermore, we will propose an effective and near optimal replica placement heuristic algorithm. The experimental result also reveals that the difference between the optimal and our algorithm result is not obvious but the proposed algorithm is much faster than that of deriving optimal solutions.

[1]J. H. Abawajy, “Placement of File Replicas in Data Grid Environment,” Lecture Notes in Computer Science, Vol. 3038/2004, 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. 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)
[4]E. Cronin, S. Jamin, C. Jin, A. R. Kurc, D. Raz and Y. Shavitt, “Constrained Mirror Placement on the Internet,” IEEE Journal on Selected Areas in Communications, Vol. 20, No. 7, pp. 1369-1382 (2002)
[5]M. R. Garey and D. S. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness, W. H. Freeman and Company (1979)
[6]C. C. Hsu, P. F. Liu and C. M. Wang, “Heuristic Algorithms for Replication Transition Problem in the Grid Systems,” Proceedings CCGRID 2008 - 8th IEEE International Symposium on Cluster Computing and the Grid, pp. 492-499 (2008)
[7]W. J. Jeon, I. Gupta and K. Nahrstedt, “QoS-aware Object Replication in Overlay Networks,” GLOBECOM-IEEE Global Telecommunications Conference, (2007)
[8]D. S. Johnson, “Approximation algorithms for combinatorial problems,” The fifth Annual ACM Symposium on Theory of Computing, pp. 38-49 (1973)
[9]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)
[10]M. Karlsson and C. Karamanolis, “Bounds on the Replication Cost for QoS,” HP Technical Report HPL-2003-156, (2003)
[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]Y. F. Lin, J. J. Wu and P. F. Liu, “A List-based Strategy for Optimal Replica Placement in Data Grid Systems,” Proceedings of the International Conference on Parallel Processing, pp. 198-205 (2008)
[15]R. M. Nauss, “The 0-1 knapsack problem with multiple choice constraints,” European Journal of Operational Research, Vol. 2, No. 2, pp.125-131 (1978)
[16]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)
[17]A. S. Tanenbaum, Computer Network 4th Edition, Prentice Hall, (2002)
[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]S. Wakabayashi and K. Kikuchi, “Solving the Minimum Dominating Set Problem with Instance-Specific Hardware on FPGAs,” Proceedings 2005 IEEE International Conference on Field Programmable Technology, pp. 69-76 (2005)
[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]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]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)
[23]J. Xu, B. Li and D. L. Lee, “Placement Problems for Transparent Data Replication Proxy Services,” IEEE Journal on Selected Areas in Communications, Vol. 20, No. 7, pp. 1383-1398 (2002)
[24]陳翰霖，「有容量的支配集問題的近似演算法」，碩士論文，國立台灣大學，台北 (2010)。