Basic Search / Detailed Display

Author: 楊承峰
Cheng-fong Yang
Thesis Title: 邊流量負載考量的服務品質複本配置演算法
Edge Capacity and QoS-aware Considerable Network Replica Allocation Algorithm
Advisor: 徐俊傑
Chiun-chieh Hsu
Committee: 王有禮
Yue-li Wang
張錫正
Hsi-cheng Chang
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, Edge Capacity, Bipartite Graph, Flow Network, Quality of Service
Reference times: Clicks: 292Downloads: 1
Share:
School Collection Retrieve National Library Collection Retrieve Error Report
  • 在網際網路資訊成長快速的時代,透過網路可以在短時間內存取非常多的資料。然而,越來越多的資料無法完全儲存於單一伺服器內。此外,網路中的使用者越來越多,網路中資料傳輸的頻率也越高,容易造成網路延遲的情況。當資料毀損時,可能造成資料無法存取或延遲取得,如此會降低資料存取的品質。
    在資料網格中,複本配置問題被廣泛的探討,這個問題也被證明為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].

    中文摘要 I ABSTRACT II 誌謝 III 目錄 IV 圖索引 VI 表索引 VII 第一章 緒論 1 1.1 研究背景 1 1.2 研究動機與目的 1 1.3 研究方法與貢獻 2 1.4 論文架構 3 第二章 文獻探討 4 2.1 複本配置問題 (Replica Placement Problem) 4 2.2 資料網格 (Data Grid) 5 2.2.1 複本管理 (Replica Management) 6 2.2.2 複本配置 (Replica Placement) 6 2.3 流量網路 (Flow Network) 8 2.3.1 最短路徑 (Shortest Path) 8 2.3.2 最大流量 (Maximum Flow) 9 2.4 最小集合覆蓋問題 (Minimum Set Cover Problem) 10 2.5 服務品質複本配置演算法 10 第三章 研究方法 13 3.1 矩陣轉換 13 3.2 二元圖轉換 15 3.3 效率函數 (Efficiency Function) 16 3.3.1 符號定義 17 3.3.2 不考量邊容量(UEC)效率函數 18 3.3.3 考量邊容量(WEC)效率函數 19 3.4 邊流量原則 20 3.5 演算法介紹與範例說明 21 3.5.1 不考量邊容量(UEC)演算法 21 3.5.2 考量邊容量(WEC)演算法 23 3.5.3 不考量邊容量(UEC)範例說明 25 3.5.4 考量邊容量(WEC)範例說明 27 第四章 實驗分析與結果 30 4.1 比較方法 31 4.2 實驗規劃 33 4.3 實驗結果 34 4.3.1 UEC與CUDU的節點數量比較 50 4.3.2 UEC與CUDU的服務品質比較 51 4.3.3 WEC的邊數量比率與服務品質限制比率的關係 52 4.3.4 WEC的邊容量與服務品質限制比率的關係 53 4.3.5 節點數量與演算法時間的關係 54 第五章 結論及未來展望 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] 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)

    無法下載圖示 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