2019/4/8 A Load Balancing Mechanism for multiple SDN Controllers based on Load Informing Strategy Miultiple controller 的 load balancing 機制，使用一個叫 Load informing 的方法。 Author: Jinke Yu, Ying Wang, Keke Pei, Shujuan Zhang, Jiacong Li Publisher/Conference: (APNOMS), 2016 18th Asia-Pacific Presenter: Cheng-Feng Ke Date: 2016/12/07 Department of Computer Science and Information Engineering National Cheng Kung University, Taiwan R.O.C. CSIE CIAL Lab 1

Introduction Multiple SDN Controllers 2019/4/8 Introduction Multiple SDN Controllers It is hard for the control plane to make an adaptation to uneven load distribution, when the mapping between a switch and a controller is statically configured. 在 Multiple SDN Controller 的環境下，每個 switch 都被固定的 Controller 管理。 如果其中一個 Controller 處理 Switch 發送過來的訊息太多，負載就會太高，而且不能分給其他 Controller 處理。 National Cheng Kung University CSIE Computer & Internet Architecture Lab CSIE CIAL Lab

2019/4/8 Introduction Load balancing decisions of multiple controllers can be divided into two categories: Centralized Decision Collecting load information of all local controllers. Sending load balancing commands to the local overloaded controller. The time efficiency of load balancing is not high. Distributed Decision Every controller can make balance decision locally. 有大概提到 Multiple controller 有分成兩種類型，集中式的判斷和分散式的判斷。 集中式會蒐集所有 Controller 的資料再決定 load balancing 的方式，所以時間效能會比較慢。 分散式可以在 local 做決定，本篇論文要改善這個模式。 National Cheng Kung University CSIE Computer & Internet Architecture Lab CSIE CIAL Lab

2019/4/8 Introduction The mechanism allows controllers can make decisions locally. Load informing strategy : each controller periodically actively reports its load information to other controllers. It also handles and stores load information informed by other controllers. An inhibition algorithm is proposed to lower the frequency of load informing for reducing the processing and communication overhead caused by the informing strategy. 這篇論文提出的機制可以 local 的去決定如何做 load balancing 。 Load informing 方法，由 controller 自己發送自己的負載資訊給其他的 Controller，並且也會儲存其他 Controller 送來的負載資訊。 Inhibition 演算法可以調整 Load informing 的發送頻率，避免溝通太頻繁導致負載提高。 National Cheng Kung University CSIE Computer & Internet Architecture Lab CSIE CIAL Lab

2019/4/8 ARCHITECTURE Controller 使用 Floodlight 交換負載資訊使用 JGroup JGroup 是一個用 Java 實現的群組通訊工具，可以做 point to peer 或 point to point 的溝通。 是否是負載最重的 Controller。 找出發送訊息最多的 switch。 找到負載小且速度快的 Target Controller。 National Cheng Kung University CSIE Computer & Internet Architecture Lab CSIE CIAL Lab

Load Measurement component 2019/4/8 Load Measurement component Runs on each controller to periodically measure load information. 1. Average message arrival rate (I) from each switch. The CPU load is roughly in proportion to the message arrival rate. 2. Round-trip time (R) from each switch to controller. An important factor to evaluate the performance of control path. 單純蒐集資訊用。 訊息送到 controller 的速度，每秒多少個 message，相當於 CPU 的負載。 Switch 到 Controller 再回到 switch 花費的時間，決定 target controller 時會用到。 National Cheng Kung University CSIE Computer & Internet Architecture Lab CSIE CIAL Lab

Load Informing component 2019/4/8 Load Informing component Each controller can periodically actively reports its load information to other controllers. And it also handles and stores the load information from others. When the current load value does not change much compared to the last value, reporting it to other controllers is a redundant. To reduce these overheads, we put forward an inhibition algorithm. 讓每個 Controller 固定時間發送自己的負載狀況給其他 Controller。 儲存其他 Controller 送過來的負載狀況，用來計算 load balancing 用。 如果自己的負載狀況變化不大，發送自己的負載狀況給其他 controller 是不必要的。 使用 inhibition 演算法決定負載狀況發送的頻率。 National Cheng Kung University CSIE Computer & Internet Architecture Lab CSIE CIAL Lab

Load Informing component 2019/4/8 Load Informing component Inhibition algorithm Threshold : 2150 目前 controller 自己的負載狀況。 上一個 controller 自己的負載狀況。 使用固定頻率有什麼問題。 如果負載很接近 threshold 時，如果被其他 controller 認定為 target controller 而接收 load balancing 後的流量，一樣會導致 overhead。 所以越接近時越提高負載狀況發送的頻率，讓高負載的 controller 有足夠的資訊去找更適合的 controller 做 load balancing。 V0 V1 V2 V3 V4 V5 V6 V7 value 600 1100 1500 1800 2000 2100 2150 frequency 30s 20s 10s 5s 4s 3s 2s 1s National Cheng Kung University CSIE Computer & Internet Architecture Lab CSIE CIAL Lab

Balance Decision component 2019/4/8 Balance Decision component The heaviest overloaded controller judgment Switch selection Target controller selection 判斷自己是不是負載最重的節點。 選擇訊息量最高的 switch。 選擇負載較低的 controller，將 switch 轉移給 target controller。 National Cheng Kung University CSIE Computer & Internet Architecture Lab CSIE CIAL Lab

Balance Decision component 2019/4/8 Balance Decision component The heaviest overloaded controller judgment 𝐿 𝐶𝑢𝑟𝑟𝑒𝑛𝑡 denotes the current load value of a controller. 𝑇ℎ𝑟 is the load threshold of the controller. 𝑃 𝑜𝑣𝑒𝑟𝐿𝑜𝑎𝑑 is the overload proportion of an overloaded controller. 目前 controller 自己的負載情況 高負載的判斷界線 算出每個一個 controller 的 P over load，並判斷自己是不是最重的。 National Cheng Kung University CSIE Computer & Internet Architecture Lab CSIE CIAL Lab

Balance Decision component 2019/4/8 Balance Decision component Switch selection The bigger the average message arrival rate is, the switch brings more load to its controller. If one selected switch with high arrival rate can reduce the load of the controller to be under the threshold, the switch selection is finished. 找出發送最多訊息到 controller 的 switch。 National Cheng Kung University CSIE Computer & Internet Architecture Lab CSIE CIAL Lab

Balance Decision component 2019/4/8 Balance Decision component Switch selection If not, the above switch groups with another switch with high arrival rate as the migrated switches and so on. So we sort the switches controlled by the overloaded controller in descending order with their message arrival rate. When choosing the switch, we also define a constraint formula (3). We ensure that the migrated load 𝐿 𝐶𝑢𝑟𝑟𝑒𝑛𝑡 is not more than 𝐿 𝐶𝑢𝑟𝑟𝑒𝑛𝑡 of the difference between load threshold 𝐿 𝐶𝑢𝑟𝑟𝑒𝑛𝑡 of the target controller and the current load value 𝐿 𝐶𝑢𝑟𝑟𝑒𝑛𝑡 . 找出所有符合這個條件的 switch 並作遷移。 National Cheng Kung University CSIE Computer & Internet Architecture Lab CSIE CIAL Lab

Balance Decision component 2019/4/8 Balance Decision component Target controller selection A switch can connect to one master controller and several slave controllers. R denotes the round-trip time. Both 𝑤1 and 𝑤2 are weight coefficients, and the sum of them is 1.0. 𝐶 𝑇𝑎𝑟𝑔𝑒𝑡 is regarded as a criterion for selecting the target controller. The slave controller with the largest 𝐶 𝑇𝑎𝑟𝑔𝑒𝑡 will be chosen as the target controller. National Cheng Kung University CSIE Computer & Internet Architecture Lab CSIE CIAL Lab

Switch migration component 2019/4/8 Switch migration component Each high-load controller may judge itself the heaviest controller before receiving load messages of other controllers. And they may choose the same target controller. A target controller only accepts overloaded controllers’ one switch migration request. Floodlight 實作 switch 的轉移。 因為每個 controller 上儲存的負載狀況可能都會有點誤差， 所以可能同時有兩個 controller 認為自己是負載最重的 controller，而都轉移 switch 到同一個 target controller 上，導致負載過高。 所以 target controller 一次只接受一個 controller 的轉移。 National Cheng Kung University CSIE Computer & Internet Architecture Lab CSIE CIAL Lab

EVALUATION The distributed OpenFlow controller based on Floodlight. 2019/4/8 EVALUATION The distributed OpenFlow controller based on Floodlight. We choose Mininet to emulate a network of software-based virtual OpenFlow switch as our experimental testbed. 2 controller nodes. 4 switches to connect controller A as master and controller B as slave. Another 4 switches to connect controller B as master and controller A as slave. National Cheng Kung University CSIE Computer & Internet Architecture Lab CSIE CIAL Lab

2019/4/8 EVALUATION A We use Cbench [10] tool to measure the maximum rate in which Packet-In messages are handled by Floodlight based on our physical hardware. The result is an average rate of 12758 Packet-In messages per second (pps). At one time, we injected 5000 pps to controller A and 16000 pps to controller B. Compared with our method, we also measure and plot the throughput when the switch-controller mapping keeps static. 使用 Cbench 工具量測出 Controller 最高的 message 處理速度是 12758 pps。 這個實驗一開始跑的時候，B就已經超過負載了。 會和靜態的 switch 設定做比較。 National Cheng Kung University CSIE Computer & Internet Architecture Lab CSIE CIAL Lab

2019/4/8 EVALUATION A Worload 是每秒輸入多少的 PackIn message。 一開始 proposed 和 static 是一樣的，後來 balancing 之後就比較高。 National Cheng Kung University CSIE Computer & Internet Architecture Lab CSIE CIAL Lab

2019/4/8 EVALUATION B When we evaluate the completion time of our proposed mechanism at a load balancing cycle. We set the threshold values of controller A and controller B to 10000 pps and 11000 pps respectively. The load balancing is completed within 5s. 實驗完成轉移的時間。 National Cheng Kung University CSIE Computer & Internet Architecture Lab CSIE CIAL Lab

2019/4/8 EVALUATION B National Cheng Kung University CSIE Computer & Internet Architecture Lab CSIE CIAL Lab