常用的數據中心網路架構如leaf-spine、fat-tree為每對ToR路由器間提供了多條可用的傳輸路徑，然而現今數據中心常用的負載均衡路由協定：等價多路徑路由(ECMP) 雖然可以達到平衡流量的功能，但由於ECMP產生的雜湊碰撞以及缺乏網路內當下的壅塞資訊，會造成低頻寬使用率的問題。
根據兩篇論文對數據中心內部的流量分析，我們可以得到數據中心內部的流量呈重尾分布，也就是少部分的流佔據了大部分的流量，因此我們認為妥善的規畫這些大象流可以有效提升頻寬使用率。在此論文中，我們針對胖樹網路架構提出了一個基於軟體定義網路 (SDN) 下的負載均衡路由協定以期提升數據中心網路的頻寬使用率及降低伺服器間溝通的延遲。當網路啟動時，路由器採用類似ECMP的方法根據雜湊值為所有流決定路徑，與此同時我們透過類似INT的方法去蒐集網路中的壅塞資訊交給SDN中的控制器。另外邊界路由器本身會透過資料結構去紀錄大象流，當發現疑似的大象流時，會發送訊息給控制器，讓控制器為這些流根據當時蒐集的擁塞資訊決定路徑。最後，為了使路由器可以更高效的轉發封包、降低路由表的規則數，我們採用了標籤轉發。
為了可以實現我們的方法，我們透過P4撰寫我們的路由器處理封包邏輯，並以P4 Runtime為協定，讓控制器跟路由器溝通。另外我們也根據Banzai Machine去驗證我們的大象流識別算法可以適用於P4路由器。最後我們以Mininet為實驗環境，並以BMv2為模擬的P4路由器去做模擬。

Multi-rooted topologies like leaf-spine, and fat-tree are used in data center networks to provide multiple equal-cost paths between ToR switches. The most commonly used routing protocol to achieve load balance in data centers is equal-cost multi-path routing (ECMP), which routes flows based on the hash value of packet’s headers. Since ECMP makes routing decisions without the network’s congestion status, it may cause significant imbalance between paths, thus leading to low bisection bandwidth utilization.
According to the literatures, the traffic pattern in data centers follows a heavy-tailed distribution, that is, a small fraction of flows contribute to most of the bytes in the network. Thus, we decide to carefully route the elephant flows to the least congested path, while we route other flows in a proactive way like ECMP. In this thesis, we propose a routing protocol based on Software-Defined Networking (SDN) architecture, which enables load balancing. This routing protocol aims to provide a better average link utilization for fat-tree. Switches adopt an ECMP like method to route all flows by default. At the same time, we follow the idea of In-band Network Telemetry (INT) to collect link congestion status in data center networks. Edge switches are responsible for detecting elephant flows by running a heavy hitter detection algorithm. When an elephant flow is reported to the controller by an edge switch, our controller will use the collected congestion status to find a least congested path for it. In order to make the switches forward packets more efficiently and reduce the number of rules in switches’ forwarding table, we adopt label switching.
Programming Protocol-independent Packet Processors (P4) is an emerging switch describing language. With P4, network developers are able to design the logic how P4 switches process packets. In this thesis, we develop a P4 program to design our novel routing scheme, which contains a heavy hitter detection algorithm. We further validate that our heavy hitter detection algorithm can run on Banzai Machine.We also write a python controller to communicate with P4 switch through P4 Runtime protocol. We use Mininet to construct our testbed, and choose BMv2 as our simulated software P4 switch.

[1] Cisco, “Cisco Data Center Spine-and-Leaf Architecture: Design Overview”. Available:
https://www.cisco.com/c/en/us/products/collateral/switches/nexus-7000-series-switches/white-paper-c11-737022.pdf
[2] M. Al-Fares, A. Loukissas, and A. Vahdat, “A Scalable, Commodity Data Center Network Architecture,” in SIGCOMM, 2008, pp. 63-74.
[3] C. Hopps, and D. Thaler, “Multipath Issues in Unicast and Multicast Next-Hop Selection,” document RFC 2991, IEFT, 2000. Available: https://www.ietf.org/rfc/rfc2992.txt
[4] A. Greenberg, S. Kandula, David A. Maltz, James R. Hamilton, C. Kim, P. Patel, N. Jain, P. Lahiri, and S. Sengupta, “VL2: A Scalable and Flexible Data Center Network,” in SIGCOMM, 2009, pp. 51-62.
[5] T. Benson, A. Akella, and A. Maltz, “Network Traffic Characteristics of Data Centers in the Wild,” IMC, Proceedings of the 10th ACM SIGCOMM conference on Internet measurement, 2010, pp. 267-280.
[6] N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, and J. Turner, “OpenFlow: Enabling Innovation in Campus Networks,” ACM SIGCOMM Computer Communication Review, vol. 38, no. 2, 2008, pp. 69-74.
[7] C. Kim, P. Bhide, Ed Doe, H. Holbrook, A. Ghanwani, D. Daly, M. Hira, and B. Davie, “In-band Network Telemetry,” 2016. Available: https://p4.org/assets/INT-current-spec.pdf
[8] P. Bosshart, D. Daly, G. Gibb, M. Izzard, N. McKeown, J. Rexford, C. Schlesinger, D. Talayco, A. Vahdat, G. Varghese, and D. Walker, “P4: Programming Protocol-Independent Packet Processors,” ACM SIGCOMM Computer Communication Review, vol. 44, no. 3, 2014, pp. 87-95.
[9] A. Sivaraman, A. Cheung, M. Budiu, C. Kim, M. Alizadeh, H. Balakrishnan, G. Varghese, N. McKeown, and S. Licking, “Packet Transactions: High-Level Programming for Line-Rate Switches,” in 2016 SIGCOMM, pp. 15-28.
[10] P4 organization, “P4 Runtime,” 2017. Available: https://p4.org/p4-runtime/
[11] B. Lantz, B. Heller, and N. McKeown, “A Network in a Laptop: Rapid Prototyping for Software-Defined Networks,” in Proceedings of the 9th ACM SIGCOMM Workshop on Hot Topics in Networks, 2010, pp. 19:1-19:6.
[12] Behavioral-Model. Available: https://github.com/p4lang/behavioral-model
[13] M. Alizadeh, T. Edsall, S. Dharmapurikar, R. Vaidyanathan, K. Chu, A. Fingerhut, Vinh The Lam, F. Matus, R. Pan, N. Yadav, and G. Varghese, “CONGA: Distributed Congestion-Aware Load Balancing for Datacenters,” ACM SIGCOMM Computer Communication Review, vol. 44, no. 4, 2014, pp. 503-514.
[14] N. Katta, M. Hira, C. Kim, A. Sivaraman, and J. Rexford, “HULA: Scalable Load Balancing Using Programmable Data Planes,” in Proceedings of the Symposium on SDN Research, 2016, pp. 51-62.
[15] Jin-Li Ye, Chien Chen, and Yu-Huang Chu, “A Weighted ECMP Load Balancing Scheme for Data Centers Using P4 Switches,” IEEE 7th International Conference on Cloud Networking, 2018.
[16] M. Al-Fares, S. Radhakrishnan, B. Raghavan, N. Huang, and A. Vahdat, “Hedera: Dynamic Flow Scheduling for Data Center Networks,” in Proceedings of NSDI, 2010.
[17] H. Song, “Protocol-Oblivious Forwarding: Unleash the Power of SDN through a Future-Proof Forwarding Plane,” in SIGCOMM HotSDN Workshop, 2013, pp. 127-132.
[18] OpenFlow Foundation, “OpenFlow Switch Specification Version 1.3.0”. Available: https://www.opennetworking.org/wp-content/uploads/2014/10/openflow-spec-v1.3.0.pdf
[19] P4 organization, “P416 Portable Switch Architecture,” 2019. Available: https://p4.org/p4-spec/docs/PSA.html
[20] Protocol Buffers. Available: https://developers.google.com/protocol-buffers/docs/proto
[21] GRPC. Available: https://grpc.io/
[22] V. Sivaraman, S. Narayana, O. Rottenstreich, S. Muthukrishnan, and J. Rexford, “Heavy-Hitter Detection Entirely in the Data Plane,” in Proceedings of the Symposium on SDN Research, 2017, pp. 164-176.
[23] G. Cormode, and S. Muthukrishnan, “An Improved Data Stream Summary: The Count-Min Sketch and its Applications,” J. Algorithms, 55(1):58-75, 2005.
[24] Yi Lu, A. Montanari, and B. Prabhakar, “Counter Braids: A Novel Counter Architecture for Per-Flow Measurement,” ACM SIGMETRICS Performance Evaluation Review, vol. 36, no. 1, 2008, pp. 121-132.
[25] Y. Li, R. Miao, C. Kim, and M. Yu, “FlowRadar: A Better NetFlow for Data Centers,” Proceedings of the 13th USENIX Symposium on Networked Systems Design and Implementation, 2016, pp. 311-324.
[26] A. Metwally, D. Agrawai, and A. EL Abbadi, “Efficient Computation of Frequent and Top-K Elements in Data Streams,” in International Conference on Database Theory, 2005.
[27] P. Lapukhov, “Use of BGP for Routing in Large-Scale Data Centers,” document RFC 7938, IEFT, 2016. Available: https://tools.ietf.org/html/rfc7938
[28] S. Kandula, D. Katabi, S. Sinha, and A. Berger, “Dynamic Load Balancing without Packet Reordering,” ACM SIGCOMM Computer Communication Review, vol. 37, no. 2, 2007, pp. 51-62.
[29] M. Noormohammadpour, and Cauligi S. Raghavendra, “Datacenter Traffic Control: Understanding Techniques and Tradeoffs,” IEEE Communications Surveys and Tutorials, vol. 20, no. 2, 2018, pp. 1492-1525.
[30] P. Wang, G. Trimponias, and Y, Geng, “Luopan: Sampling-Based Load Balancing in Data Center Networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 30, no. 1, 2019, pp. 133-145.
[31] Open vSwitch. Available: http://openvswitch.org
[32] PI. Available: https://github.com/p4lang/PI
[33] P4C. Available: https://github.com/p4lang/p4c
[34] K. Nichols, S. Blake, F. Baker, and D. Black, “Definition of the Differentiated Services Field in the IPv4 and IPv6 Headers,” document RFC 2474, IEFT, 1998. Available: https://tools.ietf.org/html/rfc2474