Basic Search / Detailed Display

Author: 趙哲寬
Che-kuan Chao
Thesis Title: 服務品質與成本考量的錯誤容忍資料複本放置演算法
QoS-aware and Cost Considerable Network Replication with Fault-Tolerance
Advisor: 徐俊傑
Chiun-chieh Hsu
Committee: 洪政煌
Degree: 碩士
Department: 管理學院 - 資訊管理系
Department of Information Management
Thesis Publication Year: 2011
Graduation Academic Year: 99
Language: 中文
Pages: 88
Keywords (in Chinese): 複本放置錯誤容忍服務品質二元圖網路流量
Keywords (in other languages): Replica Placement, Fault Tolerance, Quality of Service, Bipartite Graph, Network Flow
Reference times: Clicks: 308Downloads: 0
School Collection Retrieve National Library Collection Retrieve Error Report
  • 在網際網路蓬勃發展的今天,網路資料每天的存取量已經不是我們可以想像的數字了,如此大量的檔案或資料已經無法全部儲存在同一台檔案伺服器中,不但會降低效率、也提高資料損壞無法修復的風險。除此之外網路使用者數量越來越多,使用者要求的資料若無法由其他鄰近或負載較低的伺服器提供,就得耗費大量的時間來等候伺服器的回傳,導致許多具有時效性的系統無法在要求的特定時間內得到資料。
    目前有多位學者致力於探討該如何透過最少的複本伺服器來滿足所有使用者的服務品質需求,該類問題已有許多啟發式演算法或近似演算法的研究成果,但是所解決的問題層面不夠廣泛,鮮少有提出考量錯誤容忍和伺服器負荷量的複本放置演算法,因此在本研究中,我們將該類問題轉換成網路流量的問題,同時兼顧複本放置、錯誤容忍以及負荷量限制的應用情境,並且能夠找出最小傳輸成本的流量配置。本研究利用二元圖(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.

    中文摘要 I Abstract II 誌謝 III 目錄 IV 圖索引 VI 表索引 VIII 第一章 緒論 1 1.1 研究背景 1 1.2 研究動機與目的 3 1.3 研究方法與貢獻 3 1.4 論文架構 6 第二章 文獻探討 7 2.1 網格運算 (Grid Computing) 7 2.1.1 資料網格(Data Grid) 8 2.1.2 計算網格(Compute Grid) 9 2.1.3 複本管理(Replica Management) 9 2.1.4 複本放置與選擇(Replica Placement and Selection) 10 2.2 網路流量(Network Flow) 15 2.2.1 最短路徑(Shortest Path) 16 2.2.2 最大流量(Maximum Flow) 16 2.2.3 最小傳輸成本(Minimum Transmission Cost) 19 2.3 最少集合覆蓋問題(Minimum Set Cover Problem) 21 第三章 研究方法 22 3.1 矩陣轉換 22 3.2 二元圖轉換 24 3.3 效率函數(Efficiency Function) 26 3.3.1 符號定義 27 3.3.2 成本不考量與需求可分割(CUDS)效率函數 29 3.3.3 成本不考量與需求不可分割(CUDU)效率函數 29 3.3.4 成本考量與需求可分割(CWDS)效率函數 29 3.3.5 成本考量與需求不可分割(CWDU)效率函數 30 3.4 需求滿足原則 30 3.5 演算法介紹與範例說明 31 3.5.1 成本不考量與需求可分割 (CUDS)-啟發式演算法 31 3.5.2 成本不考量與需求可分割 (CUDS)-網路應用範例 33 3.5.3 成本不考量與需求不可分割 (CUDU)-啟發式演算法 35 3.5.4 成本不考量與需求不可分割 (CUDU)-網路應用範例 37 3.5.5 成本考量與需求可分割 (CWDS)-啟發式演算法 39 3.5.6 成本考量與需求可分割 (CWDS)-網路應用範例 39 3.5.7 成本考量與需求不可分割 (CWDU)-啟發式演算法 40 3.5.8 成本考量與需求不可分割 (CWDU)-網路應用範例 41 3.6 最小傳輸成本說明與應用 41 3.7 複本容錯說明與應用 45 第四章 實驗分析與結果 48 4.1 比較方法 48 4.2 實驗規劃 49 4.3 實驗結果 51 4.3.1 節點數量的變動關係 72 4.3.2 節點連接邊比率與服務品質比率的變動關係 75 4.3.3 負荷量和需求量比值與服務品質比率的變動關係 78 4.3.4 節點數量與演算法時間的比較 81 第五章 結論與未來展望 85 參考文獻 86

    [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)。

    無法下載圖示 Full text public date 2016/07/22 (Intranet public)
    Full text public date This full text is not authorized to be published. (Internet public)
    Full text public date This full text is not authorized to be published. (National library)