研究生: |
陳怡豪 Yi-Hao Chen |
---|---|
論文名稱: |
基於糾刪碼的網路備份點及路徑抉擇 A backup node and path in the network by erasure coding |
指導教授: |
沈上翔
Shan-Hsiang Shen |
口試委員: |
沈上翔
Shan-Hsiang Shen 沈中安 Chung-An Shen 金台齡 Tai-Lin Chin |
學位類別: |
碩士 Master |
系所名稱: |
電資學院 - 資訊工程系 Department of Computer Science and Information Engineering |
論文出版年: | 2023 |
畢業學年度: | 111 |
語文別: | 中文 |
論文頁數: | 35 |
中文關鍵詞: | 糾刪碼 、史坦納樹 、最小生成樹 、資料備份 |
外文關鍵詞: | Erasure Coding, Steiner Tree, Minimum spanning tree, Data backup |
相關次數: | 點閱:155 下載:0 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
隨著現今網路的迅速發展,行動裝置、物聯網的使用需求提高
下,資料備份因此成為一個很常探討的議題,於 Information Centric
Networking(ICN) 網路中,信息的傳遞是通過內容名稱而非 IP 位址的一
種新穎網路,在網路上從 producer 到 consumer 的路徑上,時常需要傳送
相當大量的檔案,傳統的多副本備份會造成有過多的冗餘複製封包,且其
可靠度不佳,容易造成資料遺失,此時若能將檔案切成數個小塊進行備份
再傳送,便不需要像傳統的方式去做到多副本的複製,如此更能夠降低不
必要的空間耗損,也更能保證數據的可靠性,因此我們要用糾刪碼的技術
來取代,以達到保證數據可靠度及降低不必要的空間耗損的目的。
本文提出 erasure coding path compute algorithm(ECPC) 比較了基
於 Steiner Tree 和 Minimum Spanning Tree 下的數種不同方式 (Degree,
Bruce force, Random) 的頻寬消耗,以探於不同的網路拓樸隨機產生節
點和鏈接下,在特定的 Tree 中尋找能使整個拓樸的總頻寬消耗最小的
erasure coing 點以及傳輸路徑,如此以達到 performance 最大化,更能進
一步減少網路上硬體資源的需求。
Nowadays, with the rapid development of the Internet, the using demand
of mobile device and the Internet of Things(IoT) increases, data backup
has been a issue we often mention. In the Information Centric Networking(ICN) , data transmission is depend on name not IP address. It is a novel
network. On the Internet on the path from producer to consumer, it often
requires to send a large file. If we can cut the file to be several small data
chunks, backup them, and transmit them, it will reduce the unnecessary
space which store redundant data, such as multi-copy replication. It can
ensure the reliability of data. Thus, we want to use erasure coding technology to replace.
This paper proposes an algorithm called Erasure Coding Path Compute
algorithm(ECPC). To evaluate our methods, we randomly generate nodes
and links for different topologies, and compare the bandwidth consumption of several different methods(Degree, Bruce force, Random) based on
Steiner Tree and Minimum Spanning Tree. Finding the erasure coding
point in the certain Tree that can make the total bandwidth consumption
least, and do the best performance. Thus, it can reduce the demand of hardware resources on the Internet.
[1] S. K. Lee, M. Bae, and H. Kim, “Future of iot networks: A survey,” Applied Sciences, vol. 7, no. 10,
2017.
[2] E. Guttman, “Service location protocol: automatic discovery of ip network services,” IEEE Internet
Computing, vol. 3, no. 4, pp. 71–80, 1999.
[3] A. Segall, “Distributed network protocols,” IEEE Transactions on Information Theory, vol. 29, no. 1,
pp. 23–35, 1983.
[4] B. Ahlgren, C. Dannewitz, C. Imbrenda, D. Kutscher, and B. Ohlman, “A survey of informationcentric networking,” IEEE Communications Magazine, vol. 50, 2012.
[5] T. Koponen, M. Chawla, B.-G. Chun, A. Ermolinskiy, K. H. Kim, S. Shenker, and I. Stoica, “A dataoriented (and beyond) network architecture,” in Proceedings of the 2007 conference on Applications,
technologies, architectures, and protocols for computer communications, pp. 181–192, 2007.
[6] V. Jacobson, M. Mosko, D. Smetters, and J. Garcia-Luna-Aceves, “Content-centric networking,”
Whitepaper, Palo Alto Research Center, pp. 2–4, 2007.
[7] S. Tarkoma, M. Ain, and K. Visala, “The publish/subscribe internet routing paradigm (psirp): Designing the future internet architecture.,” in Future Internet Assembly, pp. 102–111, 2009.
[8] C. Dannewitz, D. Kutscher, B. Ohlman, S. Farrell, B. Ahlgren, and H. Karl, “Network of information
(netinf)–an information-centric networking architecture,” Computer Communications, vol. 36, no. 7,
pp. 721–735, 2013.
[9] D. R. Cheriton and M. Gritter, “Triad: A new next-generation internet architecture,” 2000.
[10] O. Wolfson, S. Jajodia, and Y. Huang, “An adaptive data replication algorithm,” ACM Trans. Database
Syst., vol. 22, p. 255–314, jun 1997.
[11] Y. Qiao, X. Kong, M. Zhang, Y. Zhou, M. Xu, and J. Bi, “Towards in-network acceleration of erasure
coding,” in Proceedings of the Symposium on SDN Research, SOSR ’20, (New York, NY, USA),
p. 41–47, Association for Computing Machinery, 2020.
[12] Tencent, “Replication vs erasure coding.” https://cloud.tencent.com/developer/article/
1829995.
[13] S. B. Wicker and V. K. Bhargava, “Reed-solomon codes and their applications,” John Wiley & Sons,
1999.
[14] B. Sklar, “Reed-solomon codes,” Downloaded from URL http://www. informit. com/content/images/
art. sub.–sklar7. sub.–reed-solomo-n/elementLinks/art. sub.–sklar7. sub.–reed-solomon. pdf, pp. 1–
33, 2001.
[15] M. Sudan, “Decoding of reed solomon codes beyond the error-correction bound,” Journal of complexity, vol. 13, no. 1, pp. 180–193, 1997.
[16] GeeksforGeeks, “Steiner tree.” https://www.geeksforgeeks.org/steiner-tree/.
[17] Karthikeyan Ramasamy, “Topology and steiner tree example.” https://medium.com/.
[18] Topology Zoo, “Amres topology.” http://www.topology-zoo.org//.