P4交換機中基於Consistent Hashing之負載平衡

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：104

、訪客IP：18.116.90.161

姓名

石毓安(Yu-An SHI) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

P4交換機中基於Consistent Hashing之負載平衡
(Load balancing based on Consistent Hashing in P4 switches)

相關論文

★ 無線行動隨意網路上穩定品質服務路由機制之研究	★ 應用多重移動式代理人之網路管理系統
★ 應用移動式代理人之網路協同防衛系統	★ 鏈路狀態資訊不確定下QoS路由之研究
★ 以訊務觀察法改善光突發交換技術之路徑建立效能	★ 感測網路與競局理論應用於舒適性空調之研究
★ 以搜尋樹為基礎之無線感測網路繞徑演算法	★ 基於無線感測網路之行動裝置輕型定位系統
★ 多媒體導覽玩具車	★ 以Smart Floor為基礎之導覽玩具車
★ 行動社群網路服務管理系統－應用於發展遲緩兒家庭	★ 具位置感知之穿戴式行動廣告系統
★ 調適性車載廣播	★ 車載網路上具預警能力之車輛碰撞避免機制
★ 應用於無線車載網路上之合作式交通資訊傳播機制以改善車輛擁塞	★ 智慧都市中應用車載網路以改善壅塞之調適性虛擬交通號誌

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 ( 永不開放)

摘要(中)

近年來，新型網路架構蓬勃發展，為了解決單一伺服器處理龐大資料時超出負荷問題，分散式伺服器架構與伺服器之間的負載平衡問題逐漸成為探討核心。傳統實驗環境使用軟體定義網路（Software Define Network, SDN），透過SDN，交換機的控制平面可被分離出來，提供一個由軟體定義的集中式控制平台。然而，SDN在資料平面靈活性不足，使得SDN無法處理未定義的封包。於此同時，Programming Protocol-independent Packet Processors（P4）被提出來，使網路管理者能夠自行定義封包標頭以及根據不同演算法決定封包如何處理及轉發，從而實現真正的軟體定義網路。
為了改善一致性雜湊演算法（Consistent Hashing Algorithm）使其具有壅塞感知（Congestion Awareness）能力，本論文提出了Consistent Hashing with Congestion Awareness （CHCA）的機制，透過CHCA來做網路負載平衡（Network Load Balance）的導引演算法，改善其演算法使其具有一致性雜湊在伺服器增加或減少時只有少量資料搬移，並具有最少連接法能夠避免熱點伺服器持續接收封包導致某些伺服器超載，透過P4交換機新增兩個自定義標頭Forward標頭與MRI標頭，Forward標頭使P4交換機無須維護路由表，可以在Run-time期間根據最佳路徑來做封包轉發決策，以及MRI標頭記錄所有經過P4交換機負載資訊即時改變負載平衡的轉發策略。在實驗中，引入CHCA機制後，與Oriented-hash相比平均RTT只上升0.296ms，因此一致性雜湊演算法所造成額外運算幾乎是可以忽略的。此外與Shell相比平均RTT下降18%，對於controller的平均使用率低了7%。

摘要(英)

In recent years, new network architectures have been booming. To address the issue of a single server being overwhelmed by processing massive amounts of data, distributed server architectures and load balancing between servers have gradually become core topics of discussion. Traditional experimental environments use Software Defined Networks (SDN). Through SDN, the control plane of the switch is separated, providing a centralized control platform defined by software. However, SDN has insufficient flexibility in the data plane, making it unable to handle undefined packets. At the same time, Programming Protocol-independent Packet Processors (P4) has been proposed. P4 allows network administrators to customize packet headers and determine packet processing and forwarding based on different algorithms, thereby achieving a truly software-defined network.
To improve the congestion awareness capability of the consistent hashing algorithm, this paper proposes the Consistent Hashing with Congestion Awareness (CHCA) mechanism. Through CHCA, a load balancing guiding algorithm for the network is implemented. This algorithm improves consistent hashing by ensuring that only a small amount of data is relocated when servers are added or removed and by incorporating the least connection method to prevent hot servers from continuously receiving packets, thereby avoiding server overload. The P4 switch introduces two custom headers: the Forward header and the MRI header. The Forward header allows the P4 switch to make packet forwarding decisions based on the optimal path during runtime without maintaining a routing table. The MRI header records load information from all traversed P4 switches, enabling real-time changes in load balancing forwarding strategies. In the experiments, the introduction of the CHCA mechanism increased the average RTT by only 0.296ms compared to the Oriented-hash, making the additional computation caused by the consistent hashing algorithm negligible. Additionally, compared to Shell, the average RTT decreased by 18%, and the average controller utilization was reduced by 7%.

關鍵字(中)

★ 軟體定義網路
★ programming protocol-independent packet processors
★ 負載平衡
★ 一致性雜湊
★ 壅塞避免

關鍵字(英)

★ Software-Defined Networking
★ Programming protocol packet processors
★ Load balancing
★ Consistent hash
★ Congestion avoidance

論文目次

摘要 i
Abstract ii
誌謝 iv
目錄 v
圖目錄 viii
表目錄 x
第一章緒論 1
1.1.概要 1
1.2.研究動機 2
1.3.研究目的 2
1.4.章節架構 3
第二章背景知識與相關研究 4
2.1.軟體定義網路 4
2.2.P4:Programmin Protocol-Independent Packet Processor 6
2.3.負載平衡演算法 8
2.4.壅塞感知 11
2.5.相關研究 12
第三章系統架構設計及機制運作 15
3.1. 系統架構與設計 15
3.1.1. Forward標頭以及MRI標頭設計 17
3.1.2. 使用MurMurHash3雜湊 21
3.1.3. 具壅塞感知一致性雜湊演算法 22
3.2. 系統運作流程與實作 22
3.2.1. 初始化階段 23
3.2.2. 封包偵測與修改階段 25
3.2.3. 封包轉發 31
3.3. 系統環境 34
第四章實驗與討論 35
4.1. 情境一：CHCA功能性驗證 35
4.1.1. 實驗一：封包基於一致性雜湊轉發的驗證 35
4.1.2. 實驗二：反向TCP Port Scan功能驗證 37
4.1.3. 實驗三：Forward標頭與MRI標頭功能驗證 39
4.1.4. 實驗四：具壅塞感知之一致性雜湊演算法驗證 41
4.2. 情境二：效能比較 43
4.2.1. 實驗五：CHCA、Oriented-Hash、Round-Robin、SHELL在RTT的效能比較 43
4.2.2. 實驗六：CHCA與SHELL在controller的CPU使用率比較 45
4.3. 情境三：衡量一致性雜湊的設計對整體的影響 46
4.3.1. 實驗七：不同雜湊演算法對一致性雜湊的效能比較 47
4.3.2. 實驗八：雜湊導向與一致性雜湊資料搬移比較 48

第五章結論與未來研究方向 51
5.1. 結論 51
5.2. 研究限制 52
5.3. 未來研究 52

參考文獻 54

參考文獻

[1] R. Singh, None Vibha, R. Mishra, Rani Nandkishor Aher, Avishek Ghosal, and N. Chakraborty, “A Survey on Cloud Computing Approaches,” Nov. 2023, doi: https://doi.org/10.1109/iccsai59793.2023.10421324.
[2] “Global Load Balancer Market Size, Share, Growth Analysis, By Component (Hardware, Software), By Service (Training and Consulting, Integration and Deployment), By Type (Local Load Balancer, and Global Load Balancer ), By Deployment (Cloud, and On-premise ),” www.giiresearch.com. https://www.giiresearch.com/report/sky1373831-global-load-balancer-market-size-share-growth.html (accessed Jun. 12, 2024).
[3] T. Loba, N. Konate, M. R. Batiebo, and R. D. J. Bita, “Development of a web server load balancing system,” International Journal of Innovation and Applied Studies, vol. 41, no. 3, pp. 859–866, Jan. 2024, Accessed: Jun. 12, 2024. [Online]. Available: https://ijias.issr-journals.org/abstract.php?article=IJIAS-23-330-09
[4] P. Bosshart et al., “P4,” ACM SIGCOMM Computer Communication Review, vol. 44, no. 3, pp. 87–95, Jul. 2014, doi: https://doi.org/10.1145/2656877.2656890.
[5] Mohammad Rifki Baihaqi, Ridha Muldina Negara, and R. Tulloh, “Analysis of Load Balancing Performance using Round Robin and IP Hash Algorithm on P4,” Dec. 2022, doi: https://doi.org/10.1109/isriti56927.2022.10052975.
[6] M. Hamdan et al., “A comprehensive survey of load balancing techniques in software-defined network,” Journal of Network and Computer Applications, vol. 174, p. 102856, Jan. 2021, doi: https://doi.org/10.1016/j.jnca.2020.102856.
[7] M. Coluzzi, A. Brocco, Patrizio Contu, and Tiziano Leidi, “A survey and comparison of consistent hashing algorithms,” Apr. 2023, doi: https://doi.org/10.1109/ispass57527.2023.00048.
[8] Maria Manuela Silva, P. Nielsen, N. Bay, and Paulo A.F. Martins, “Failure mechanisms in single-point incremental forming of metals,” vol. 56, no. 9–12, pp. 893–903, Jun. 2011, doi: https://doi.org/10.1007/s00170-011-3254-1.
[9] L. Tan et al., “In-band Network Telemetry: A Survey,” Computer Networks, vol. 186, p. 107763, Feb. 2021, doi: https://doi.org/10.1016/j.comnet.2020.107763.
[10] D. Kreutz, F. M. V. Ramos, P. Esteves Verissimo, C. Esteve Rothenberg, S. Azodolmolky, and S. Uhlig, “Software-Defined Networking: A Comprehensive Survey,” Proceedings of the IEEE, vol. 103, no. 1, pp. 14–76, Jan. 2015, doi: https://doi.org/10.1109/jproc.2014.2371999.
[11] ONF Solution Brief, "OpenFlow-Enabled SDN and Network Functions Virtualization," Open Netw. Found, vol. 17, pp. 1-12, 2014.
[12] A. Lara, A. Kolasani, and B. Ramamurthy, “Network Innovation using OpenFlow: A Survey,” IEEE Communications Surveys & Tutorials, vol. 16, no. 1, pp. 493–512, 2014, doi: https://doi.org/10.1109/surv.2013.081313.00105.
[13] C. Partridge, J. Hughes, and J. Stone, “Performance of checksums and CRCs over real data,” ACM SIGCOMM Computer Communication Review, vol. 25, no. 4, pp. 68–76, Oct. 1995, doi: https://doi.org/10.1145/217391.217413.
[14] M. Menth, H. Mostafaei, D. Merling, and M. Häberle, “Implementation and Evaluation of Activity-Based Congestion Management Using P4 (P4-ABC),” Future Internet, vol. 11, no. 7, p. 159, Jul. 2019, doi: https://doi.org/10.3390/fi11070159. “P4: Programming Networks Forwarding Plane,” VOLANSYS, Aug. 17, 2018. https://www.volansys.com/blog/p4-programming-networks-forwarding-plane/ (accessed Jun. 13, 2024).
[15] "P4: Programming Networks Forwarding Plane" Accessed on: May 23, 2023. [Online]. Available: https://www.volansys.com/blog/p4-programming-networks-forwarding-plane/
[16] T. Barbette et al., “A High-Speed Load-Balancer Design with Guaranteed Per-Connection-Consistency,” pp. 667–683, Jan. 2020.
[17] E. Jafarnejad Ghomi, A. Masoud Rahmani, and N. Nasih Qader, “Load-balancing algorithms in cloud computing: A survey,” Journal of Network and Computer Applications, vol. 88, pp. 50–71, Jun. 2017, doi: https://doi.org/10.1016/j.jnca.2017.04.007.
[18] Y. Sato, Y. Namba, and H. Nishi, “Layer-7 and 5-Tuple Information Analysis Framework for Providing Positional Flexibility In Location Determination for Service Provision,” Oct. 2023, doi: https://doi.org/10.1109/iecon51785.2023.10311793.
[19] J. S. Chase, D. C. Anderson, P. N. Thakar, A. M. Vahdat, and R. P. Doyle, “Managing energy and server resources in hosting centers,” ACM SIGOPS Operating Systems Review, vol. 35, no. 5, p. 103, Dec. 2001, doi: https://doi.org/10.1145/502059.502045.
[20] None Hailong Zhang, None Xiao Guo, None Jinyao Yan, None Bo Liu, and None Qianjun Shuai, “SDN-based ECMP algorithm for data center networks,” Oct. 2014, doi: https://doi.org/10.1109/comcomap.2014.7017162.
[21] C. Avin, K. Mondal, and S. Schmid, “Demand-Aware Network Design With Minimal Congestion and Route Lengths,” IEEE/ACM transactions on networking, vol. 30, no. 4, pp. 1838–1848, Aug. 2022, doi: https://doi.org/10.1109/tnet.2022.3153586.
[22] C. Rizzi, Z. Yao, Yoann Desmouceaux, M. Townsley, and T. Clausen, “Charon: Load-Aware Load-Balancing in P4,” arXiv (Cornell University), Oct. 2021, doi: https://doi.org/10.23919/cnsm52442.2021.9615535.
[23] “A randomized least-connection first layer-4 load balancer using P4 switch, Jul. 28, 2020. https://hdl.handle.net/11296/3b5arp (accessed Jun. 13, 2024).
[24] D. E. Eisenbud et al., “Maglev: a fast and reliable software network load balancer,” pp. 523–535, Mar. 2016.
[25] M. Kulkarni, B. Goswami, and J. Paulose, “P4 based Load Balancing Strategies for Large Scale Software-Defined Networks,” IEEE Xplore, Apr. 01, 2022. https://ieeexplore.ieee.org/abstract/document/9807999 (accessed Jun. 13, 2024).
[26] Benoit Pit-Claudel, Yoann Desmouceaux, P. Pfister, M. Townsley, and T. Clausen, “Stateless Load-Aware Load Balancing in P4,” HAL (Le Centre pour la Communication Scientifique Directe), Sep. 2018, doi: https://doi.org/10.1109/icnp.2018.00058.
[27] C. Filsfils, S. Previdi, L. Ginsberg, B. Decraene, S. Litkowski, and R. Shakir, “Segment Routing Architecture,” www.rfc-editor.org, Jul. 2018, doi: https://doi.org/10.17487/RFC8402.
[28] “GitHub - p4lang/behavioral-model: The reference P4 software switch,” GitHub. https://github.com/p4lang/behavioral-model (accessed Jun. 13, 2024)
[29] C. L. Schuba, I. V. Krsul, M. G. Kuhn, E. H. Spafford, A. Sundaram, and D. Zamboni, “Analysis of a denial of service attack on TCP,” Proceedings. 1997 IEEE Symposium on Security and Privacy (Cat. No.97CB36097), 1997, doi: https://doi.org/10.1109/secpri.1997.601338.
[30] V. Akoto-Adjepong, “An Enhanced Non- Cryptographic Hash Function,” ir.knust.edu.gh, Sep. 2016, Accessed: Jun. 13, 2024. [Online]. Available: https://ir.knust.edu.gh/items/71431c56-89e5-45ed-8e9e-699435f48b54
[31] K. Kaur, M. Kaur, K. Kaur, and A. Madaan, "A Comparative Study of OSI and TCP/IP Models," International Journal of Engineering and Management Research, vol. 13, no. 2, pp. 127-135, 2023.
[32] “In-band Network Telemetry — What Is It All About? CodiLime,” CodiLime, Jan. 30, 2023. https://codilime.com/blog/in-band-network-telemetry-what-is-it-all-about/ (accessed Jun. 13, 2024).
[33] V. Henson, “An Analysis of Compare-by-hash,” www.usenix.org, 2003. https://www.usenix.org/conference/hotos-ix/analysis-compare-hash
[34] P. Saxena, “Analysis of Various Hash Function,” International Journal of Innovative Science and Research Technology, vol. 3, no. 5, 2018, Accessed: Jun. 13, 2024. [Online]. Available: https://ijisrt.com/wp-content/uploads/2018/05/Analysis-Of-Various-Hash-Function.pdf
[35] “The murmur hashing algorithm,” KeiruaProd, Apr. 02, 2023. https://www.keiruaprod.fr/blog/2023/04/02/the-murmur-hashing-algorithm.html (accessed Jun. 13, 2024).
[36] M. Xiang, Y. Jiang, Z. Xia, and C. Huang, “Consistent hashing with bounded loads and virtual nodes-based load balancing strategy for proxy cache cluster,” Cluster Computing, vol. 23, no. 4, pp. 3139–3155, Feb. 2020, doi: https://doi.org/10.1007/s10586-020-03076-4.
[37] GeeksforGeeks, “TCP 3-way handshake process,” GeeksforGeeks, Oct. 26, 2021. https://www.geeksforgeeks.org/tcp-3-way-handshake-process/(accessed Jun. 13, 2024).
[38] “Ethernet Protocol — Computer Networking 0.5 documentation,” cot-cn.cougarnet.uh.edu. https://cot-cn.cougarnet.uh.edu/docs/compnet/012-ethernet.html(accessed Jun. 13, 2024).
[39] "p4-utils", Accessed on July 13, 2024. [Online]. Available: https://github.com/nsg-ethz/p4-utils
[40] "mininet", Accessed on July 13, 2024. [Online]. Available: http://mininet.org/
[41] "Scapy", Accessed on July 13, 2024. [Online]. Available: https://scapy.readthedocs.io/en/latest/
[42] "Wireshark", Accessed on July 13, 2024. [Online]. Available: https://www.wireshark.org/
[43] "iperf", Accessed on July 12, 2024. [Online]. Available: https://iperf.fr/
[44] "Ping", Accessed on July 12, 2024. [Online]. Available: https://www.man7.org/linux/man-pages/man8/ping.8.html
[45] H. Handschuh, “SHA Family (Secure Hash Algorithm),” Encyclopedia of Cryptography and Security, pp. 565–567, 2020, doi: https://doi.org/10.1007/0-387-23483-7_388.
[46] C. Hayes, “Non-Cryptographic Hash Functions: Focus on FNV - MURAL - Maynooth University Research Archive Library,” Maynoothuniversity.ie, 2023, https://mural.maynoothuniversity.ie/18141/1/Final%20thesis%20submission%20to%20examination%20office%20Jan%202024.pdf.
[47] "Intel Tofino 2", Accessed on June 8, 2023. [Online]. Available: https://www.intel.com/content/www/us/en/products/network-io/programmable-ethernet-switch/tofino-2-series.html
[48] S. Laki, R. Stoyanov, D. Kis, R. Soulé, P. Vörös, and N. Zilberman, “P4Pi,” ACM SIGCOMM Computer Communication Review, vol. 51, no. 3, pp. 17–21, Jul. 2021, doi: https://doi.org/10.1145/3477482.3477486.
[49] G. C. Sankaran, K. M. Sivalingam and H. Gondaliya, "P4 and NetFPGA-Based Secure In-Network Computing Architecture for AI-Enabled Industrial Internet of Things," IEEE Internet of Things Journal, vol. 10, no. 4, pp. 2979-2994, Feb, 2023, doi: 10.1109/JIOT.2021.3125862.
[50] "SmartNICs with P4 support" Accessed on June 8, 2023. [Online]. Available: https://codilime.com/blog/smartnics-with-p4-support/

指導教授

周立德(Li-Der Chou)

審核日期

2024-8-14

推文