Basic Search / Detailed Display

Author: 鄭雅如
Ya-ru Jheng
Thesis Title: 考量服務品質、負荷量、需求量與容錯之資料複本配置演算法
A Network Replica Placement Algorithm Considering QoS-aware, Capacity, Demand, and Fault-Tolerance
Advisor: 徐俊傑
Chiun-chieh Hsu
Committee: 賴源正
Yuan-cheng Lai
郭啟容
none
Degree: 碩士
Master
Department: 管理學院 - 資訊管理系
Department of Information Management
Thesis Publication Year: 2012
Graduation Academic Year: 100
Language: 中文
Pages: 58
Keywords (in Chinese): 複本放置錯誤容忍服務品質二元圖
Keywords (in other languages): Replica Placement, Fault Tolerance, Quality of Service, Bipartite Graph
Reference times: Clicks: 225Downloads: 1
Share:
School Collection Retrieve National Library Collection Retrieve Error Report
  • 在現今的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.

    中文摘要 I Abstract II 誌謝 III 目錄 IV 圖索引 VI 表索引 VII 第一章 緒論 1 1.1 研究背景 1 1.2 研究動機與目的 1 1.3 研究方法與貢獻 2 1.4 論文架構 3 第二章 文獻探討 4 2.1 問題定義與假設 4 2.2 服務品質考量的複本容錯演算法 4 2.3 相關文獻 7 2.3.1 網格計算(Grid Computing) 7 2.3.2 資料複本配置 9 2.3.3 最小集合覆蓋問題(Minimum Set Cover Problem) 11 第三章研究方法 13 3.1 矩陣轉換 13 3.2 二元圖轉換 15 3.3 效率函數(Efficiency Function) 17 3.3.1 符號定義 18 3.3.2 第一階段效率函數 20 3.3.3 第二階段效率函數 20 3.3.4 第三階段效率函數 21 3.4 節點滿足原則 22 3.5 演算法介紹與範例說明 24 3.5.1 Demand Unsplittable Domination(DUD) 啟發式演算法 24 3.5.2 Demand Unsplittable Domination(DUD) 範例 26 3.5.3 Demand Splittable Domination(DSD) 啟發式演算法 30 3.5.4 Demand Splittable Domination(DSD) 範例 33 第四章實驗分析與結果 38 4.1 比較方法 38 4.2 實驗規劃 39 4.3 實驗結果 41 4.3.1 節點數量的變動關係 50 4.3.2 節點連接邊數量比例與服務品質比例的變動關係 51 4.3.3 負荷量和需求量比值與服務品質比例的變動關係 53 第五章結論與未來展望 55 參考文獻 56

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

    無法下載圖示 Full text public date 2017/07/02 (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)
    QR CODE