臺灣博碩士論文加值系統

本論文提出一個稱為Reef的超檔案系統(Hyper File System)。Reef 結合軟體定義網路(Software-Defined Networking, SDN)及分散式檔案系統(Distributed File System, DFS) 技術。使用軟體定義網路的控制器(Controller)集中式管理網路通信量，可以更有效率的分配網路資源解決網路壅塞、降低延遲時間及減少頻寬消耗;使用分散式檔案系統當作儲存空間，則具有高度的可擴展性，營運商可以根據需求增加或減少儲存資源，使得檔案系統的使用更佳靈活。Reef也整合糾刪碼(Erasure code, EC)提高資料可靠性。糾刪碼是一種數據容錯方法，它將數據分割成不同片段，將其擴展、編碼，並存儲在不同的位置。相比多副本複製容錯方法而言，糾刪碼能夠以更小的數據冗餘獲得更高數據可靠性。本論文也提出Residual-Network Multiple Shortest Path (RNMSP)演算法找出路徑以到達平均端點至端點延遲(Average end to end delay)最低的儲存節點，並將經過糾刪編碼後的檔案存在各個節點，達到異地備源的功能。本論文並針對RNMSP演算法及其他儲存節點路徑尋找演算法在不同網路拓樸上進行模擬，以比較其執行時間及平均端點至端點延遲。

In this study, we propose a hyper file system, named Reef, which is a combination of the technologies of Software Defined Networking (SDN) and the Distributed File System (DFS). Reef uses the SDN controller to manage network traffic in a centralized way so that the network resources can be allocated more efficiently to reduce network latency, congestion, and bandwidth consumption. Furthermore, Reef uses DFS storage nodes to store data to keep high scalability; operators can increase or decrease storage resources dynamically according to users demands, leading to high utilization of the file system. Reef also integrates the erasure code (EC) to improve data reliability. The EC is a method to make data fault-tolerant; it divides data into different fragments, which are encoded with redundancy to be stored across a set of different locations. Compared with the traditional multi-replica method to make data fault-tolerant, the EC can utilize smaller data redundancy for higher data reliability. We also propose the Residual-Network Multiple Shortest Path (RNMSP) algorithm to find paths to the storage nodes minimizing the average end to end delay for storing EC-encoded data blocks. We simulate the RNMSP algorithm and other related storage node path-finding algorithms under different network topologies for comparing algorithms in terms of the execution time and the average end to end delay.

中文摘要 i
Abstract ii
誌謝 iii
目錄 iv
圖目錄 v
表目錄 vi
一、緒論 1
二、背景知識與研究 5
2.1. Openflow協定 5
2.2. 延伸Dijkstra演算法 7
2.3. 群播 8
2.3.1. 群播樹 8
2.3.2. SCTF演算法 9
2.3.3. EDA-MSCTF演算法 10
2.4. 糾刪碼 11
2.4.1. 里德所羅門編碼 (Reed-solomon codes) 13
2.5 剩餘網路 (Residual network) 14
三、場景描述與解法 15
3.1. 場景描述 15
3.2. 解決方法 17
3.3. 系統架構圖 20
3.4. 系統流程 22
3.4.1. 檔案儲存流程 22
3.4.2. 糾錯編解碼流程 23
3.4.3. 讀取檔案流程 24
四、實驗模擬與效能評估 25
4.1. 實驗設置 25
4.2. 網路拓樸與配置 26
4.3. 效能評估 29
五、結論與未來展望 34
六、參考文獻 35

[1] C. Banse, S. Rangarajan, “A secure northbound interface for SDN applications.” in IEEE Conference on Trustcom/BigDataSE/ISPA, 2015.
[2] XinGuard, “Software-Defined Networking,” December 30, 2015.
[3] Open Networking Foundation, “OpenFlow Switch Specification version 1.5.0,” December 19, 2014.
[4] B. Nunes, M. Mendonça, X. Nguyen, K. Obraczk, and T. Turletti, “A survey of software-defined networking: Past, present, and future of programmable networks,” in IEEE Communications Surveys & Tutorials, 2014.
[5] S Jain, A Kumar, S Mandal, et. al., “B4：Experience with a Globally-Deployed Software Defined WAN,” in ACM SIGCOMM conference, 2013.
[6] S. Ghemawat, H. Gobioff, and S.T. Leung, “The Google File System,” in ACM SOSP’03, October 19–22, 2003.
[7] K. Shvachko, H. Kuang, S. Radia, R. Chansler, “The Hadoop Distributed File System,” in IEEE 26th Symposium on Mass Storage Systems and Technologies (MSST), 2010.
[8] V. Gramoli , G. Jourjon and O. Mehani, “Disaster-Tolerant Storage with SDN”, in Networked Systems Volume 9466 of the series Lecture Notes in Computer Science pp 293-307, 2015.
[9] N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, and J. Turner, “OpenFlow: Enabling Innovation in Campus Networks,” in ACM SIGCOMM Computer Communication, 2008.
[10] J. R. Jiang, H. W. Huang, J. H. Liao, and S. Chen, “Extending Dijkstra’s Shortest Path Algorithm for Software Defined Networking,” in APNOMS, Asia-Pacific. IEEE, 2014
[11] S. RAMANATHAN, “Multicast tree generation in networks with asymmetric links,” IEEE/ACM Transactions on Networking (TON), 1996.
[12] S. Y. Chen, J. R. Jiang, “Building Steiner Tree with Extended Dijkstra's Algorithm for Software-Defined Networking Multicast,” in NCU Institutional Repository, 2015.
[13] Y. Q. Lin, “Hadoop 3.0 Erasure Coding,” February 26, 2016 ,from http://blog.csdn.net/androidlushangderen/article/details/50724917.
[14] B. Sklar, “Reed Solomon Codes.” in Englewood Cliffs, NJ: Prentice-Hall, 2001.
[15] Wikiwand , “ Reed-solomon codes,” June 30 ,2015
[16] J. S. Plank., “A tutorial on Reed-Solomon coding for fault tolerance in RAID-like systems.” in Software—Practice and Experience (SPE), 27(9):995–1012, Sept. 1997
[17] J. S. Plank,“Optimizing Cauchy Reed-Solomon Codes for Fault-Tolerant Storage Applications,” in Fifth IEEE International Symposium on Network Computing and Applications (NCA'06) 24-26 July, 2006.
[18] NTNU, “Residual Network, ” from http://www.csie.ntnu.edu.tw/~u91029/Flow.html
[19] Wikipedia, “Residual Network, ” from https://zh.wikipedia.org/wiki/網路流
[20] M. Sathiamoorthy et al., “XORing elephants: Novel erasure codes for big data,” in Proc. Very Large Data Bases Endowment, vol. 6, no. 5,pp. 325–336, Mar. 2013.
[21] C. Huang, H. Simitci, Y. Xu, A. Ogus, B. Calder, P. Gopalan, J. Li, and S. Yekhanin, “Erasure coding in Windows Azure Storage,” presented at the USENIX Annu. Tech. Conf., Boston, MA, 2012.
[22] University of Adelaide, “The Internet Topology Zoo,” from http://www.topology-zoo.org/.