# Load Balancing Implementation in P4

# 組員

- P10942a03 李維哲
- P10942a04 董晉志
- R10921a22 柯以恆

# Introduction

隨著全球化網路發展蓬勃，傳統靜態的網路拓樸難以適應不斷改變的網路現況，為了滿足對於網路品質以及網路流量成長的大量需求，軟體定義網路（Software-Defined Network，SDN）的規模與密度也隨之擴大，但隨著 SDN 的應用情境越來越廣泛，伺服器需要處理的封包請求也越來越多，增加了伺服器因為無法承載而導致服務中斷的挑戰，因此，擁有一個更高效的資源分配能力在未來將扮演一個至關重要的角色。

有鑑於此，本組打算實做軟體定義網路的負載平衡技術，可將網路流量平均分配到不同的伺服器中，提升主機或應用程式在流量高峰時的處理效能，以強化整體網路的穩定度；而當主機需要維修更新或應用程式需要改版時，亦可將連線導入未作業之伺服器主機，待作業完成後再將連線導入，增加整體網路的靈活性。

# Related Work

Different Load Balancing Methods
Domain Name System(DNS)
為多個IP地址配置一個名稱，查詢該名稱的客戶將收到其中一個IP地址。進而使不同的客戶連線至不同的服務器，達到負載平衡。缺點是無法區分伺服器以及反映伺服器當前運行狀況。
Hardware load balancer(HLB)
硬體負載平衡器是將網路流量分布到多個伺服器或資源上的硬體設備，達到負載平衡。它們通過接收進入流量並根據一組規則或演算法（如輪流或最少連接）將其轉發到適當的伺服器。
Server Operating Systems(SLB)
軟體負載平衡是一種技術，用於將網路流量分散到多個伺服器或資源，達到負載平衡。軟體負載平衡通常通過安裝在應用程式伺服器上的軟體來實現，該軟體負責接收進入流量並將其轉發到適當的伺服器。
Application Delivery Controllers(ADC)
應用程式傳輸控制器是一種網路設備，用於提供高性能和可用性的應用程式傳輸。ADC通常位於防火牆和Web之間，負責接收進入的流量並根據設定的規則或演算法將其轉發到適當的應用程式伺服器。目前有許多負載平衡技術和方法可用於ADC，像是Round robin, weighted round robin, IP-based hashing, and SHELL等等。

# Implementation results

在軟體定義網路中利用P4來實作負載平衡技術，並研究其他相關技術作法。

## Experiment setup
- OS
- Ubuntu 16.04.4
- Required software
- P4
- Mininet
- Python
- PI
- Behavioral Model (BMv2)
- P4C
- P4-Utils
- MiniP4 (https://github.com/joncastro/minip4)
Dependencies: Mininet, p4c-bm, behavorial-model
- Docker


## Experiment

1. Hash-based Load Balancing

- 前置作業：
- 確認與調整檔案架構如下：
- 編譯 P4 規則並建立 Mininet 虛擬網路交換器

- 在主機 h2 與 h3 分別啟用 HTTP 伺服器，並於 h1 透過 curl 指令存取 10.0.0.1 的網頁，可以發現由於來源的連接埠每次都不相同，每次存取網頁時分派的主機也會跟著不同
- 第一次存取
- 六次存取後的分配情形

- 進一步透過以下實驗，檢查負載平衡分配到的主機是否活著
- 利用 docker 建立四台目標網頁伺服器
- 模擬 h5 主機網頁伺服器無法正常存取的情況
- 透過 curl 檢查主機狀態，將確認無法存取的主機以 table_modify 更新其狀態，將主機從負載平衡的候選目標中移除
- 理想情況下，在我們連續發送 1000 個存取請求時，如果有啟用 controller，負載平衡器會自動避開異常的主機，不過可惜的是，我們這次的實驗使用的 docker container 因為缺乏 TC 相關程式，最終卡在最後一步沒有成功模擬出來
啟用 controller 的模擬結果
停用 controller 的模擬結果

2. Weighted Round-Robin Load Balancing
- Setup
- h1: client
- h2: server1
- h3: server2

- Execution: 在h1上使用 curl指令存取 10.0.0.1的位置，可以看到server1的處理數量約是server2的兩倍，這是因為權重的分配上我們將server1設至2，server2設至1
- P4 Switch端的權重設置，meta.mymetadata.flowlet_select等於1或2，則h2會被選擇，若meta.mymetadata.flowlet_select等於3，則h3會被選擇，然後重複
- 啟用Controller將所有HTTP Request導向server2(h3)，可以看到框框中的時間軸，黃色為啟用之前，紅色為啟用之後。這樣的目的是能夠動態去分配server之間的權重，若有一個server過載或者閒置，我們可以透過Controller動態調整權重，來達到load balance的成效

3. SHELL Load Balancing

- 編譯 P4 程式，產出實驗用的拓樸（`basic.json`）
- 根據剛才產出的拓樸啟用虛擬網路交換器
- 為 P4 交換器建立規則
- 實際發送連續測試封包時，發現 IPv6 路由沒有正常設置，因此無法成功驗證負載平衡的情形

## Algorithm

1. Hash-based Load Balancing
Hash Load Balancing使用一種演算法，該演算法使用客戶端和伺服器的來源和目的地IP地址生成唯一的hash key。該key用於將客戶端分配到特定的伺服器。由於如果連線中斷可以重新生成key，因此這種負載平衡方法可以確保將客戶端導向先前使用的同一個伺服器，進而達成附載平衡。
負載均衡器腳本是用P4語言編寫的，位於host和controller之間，使執行順暢。 使用source IP, source port, destination IP,destination port,protocol(TCP or UDP)作為hash key。 所有host都連接到P4交換機負載均衡器，如圖所示。

#ECMP（Equal-Cost Multi-Path）
#將"standard_metadata"中的"drop"字段設置為1來標記要丟棄的封包。
    action drop() {
        mark_to_drop(standard_metadata);
    }
    
#將source IP, source port, destination IP,destination port,protocol用於計算hash
    action set_ecmp_select(bit<16> ecmp_base, bit<32> ecmp_count) {
        hash(meta.ecmp_select,
	    HashAlgorithm.crc16,
	    ecmp_base,
	    { hdr.ipv4.srcAddr,
	      hdr.ipv4.dstAddr,
              hdr.ipv4.protocol,
              hdr.tcp.srcPort,
              hdr.tcp.dstPort },
	    ecmp_count);
    }
#設定封包目的地的MAC地址,IPv4地址及port   
    action set_nhop(bit<48> nhop_dmac, bit<32> nhop_ipv4, bit<9> port) {
        hdr.ethernet.dstAddr = nhop_dmac;
        hdr.ipv4.dstAddr = nhop_ipv4;
        standard_metadata.egress_spec = port;
        hdr.ipv4.ttl = hdr.ipv4.ttl - 1;
    }
#ecmp_group表用於確定是否應將封包丟棄或傳送到ecmp_nhop表以進一步處理 
    table ecmp_group {
        key = {
            hdr.ipv4.dstAddr: lpm;
        }
        actions = {
            drop;
            set_ecmp_select;
        }
        size = 1024;
    }
#ecmp_nhop表用於根據ecmp_select的值確定封包的下一個跳點 
    table ecmp_nhop {
        key = {
            meta.ecmp_select: exact;
        }
        actions = {
            drop;
            set_nhop;
        }
        size = 2;
    }
 #將ecmp_group和ecmp_nhop表應用於封包。   
    apply {
        if (hdr.ipv4.isValid() && hdr.ipv4.ttl > 0) {
            ecmp_group.apply();
            ecmp_nhop.apply();
        }
    }

2. Weighted Round-Robin Load Balancing
在Round-Robin的演算法中，我們會將clients的request以輪流且照先後順序的方式平均分配給各個server，如下圖。
但是不同的server之間可能具有不同的性能，且動態分配時不同的sever負載度也不同，這時候我們就可以使用Weighted Round-Robin的演算法，將性能高、負載低的server配置較高的權重，讓request優先分配到權重較高的server以達到load balance的目的，下圖我們將server1的權重配至5。

3. SHELL Load Balancing
SHELL 演示了在使用 IPv6 分段路由（IPv6 Segment Routing）和隱蔽通道（Convert Channel）的情況下，Application-aware 的負載平衡器能夠以無狀態（Stateless）的方式，將流量分配給眾多應用程式中最合適的那個，SHELL 的架構如下圖所示：
相較於其他無狀態的負載平衡解決方案，SHELL 除了提供了相同效果的吞吐量跟延遲的特性，還能夠提供好很多的連線穩定性。SHELL 由下列三個主要元件所組成：控制層（Control Plane）、基於 P4 的負載平衡資料層（Data Plane）以及伺服器 agent。

# Conclusion
在本次的報告中，我們研究了3種運用於軟體定義網路的load balanceing方法，分別為Hash-based, Weighted Round-Robin, SHELL。我們實作了Hash-based及Weighted Round-Robin，並透過研讀文獻了解3種方法間的差異。使用Hash和Weighted Round Robin等方法在資源分配上具有不錯的表現；SHELL則因提供較佳的吞吐量跟延遲特性，其負載平衡在所有特性方面都非常適合大型網絡。在軟體定義網路中利用 P4 來實作負載平衡技術，確實改善了軟體定義網路品質及處理封包的效率，增加整體網路的靈活性。

# Reference
- [M. Kulkarni, B. Goswami and J. Paulose, "P4 based Load Balancing Strategies for Large Scale Software-Defined Networks," 2022 Second International Conference on Advances in Electrical, Computing, Communication and Sustainable Technologies (ICAECT), 2022, pp. 1-7](https://ieeexplore.ieee.org/document/9807999)

- [Load-Balanacing-in-P4](https://github.com/Manasa-Kulkarni-396/Load-Balanacing-in-P4)

- [Chih-Heng Ke, Shih-Jung Hsu, "Load Balancing Using P4 in Software-Defined Networks," Journal of Internet Technology, vol. 21, no. 6 , pp. 1671-1679, Nov. 2020.](https://jit.ndhu.edu.tw/article/viewFile/2400/2415)

- [Load Balancing Using P4 in Software-Defined Networks](http://csie.nqu.edu.tw/smallko/sdn/p4-dockernet.htm)

- [P4: Load Balancing](https://cornell-pl.github.io/cs6114/lecture09.html)

- [P4 load balancing 實作](https://ithelp.ithome.com.tw/articles/10248925)