# Network Virtualization and Security Final Report

# SDN Load Balancing
**Group 12**
* D05942016 曹景程
* R08922A25 龔柏丞
* R08942134 王佳豪
* R08921067 劉元泰
## Background
One of the benefits of the SDN architecture is dynamically updating routing tables in each switch. Every switch has its routing algorithm in the traditional data network, which would perform routing algorithms like Link State Algorithm(dijkstra's Algorithm) or Distance Vector Algorithm(Bellman–Ford Algorithm). But the traditional network switch updates its routing tables when the network adds a new switch or the link cost changes. And the algorithm will automatically select the shortest or lowest-cost path to routing a packet between two nodes. The shortest path or lowest cost path does not always mean the best routing in a network when every switch route packet to destination through the specific lowest path. Traditional data networks will optimize the routing algorithm and got the cost information through switches.
**Traditional routing method**

Due to the centralized network controller collecting the whole network information from every switch, the optimized routing algorithm for the whole network can be considered, and every routing path can be optimized in the network aspect instead of the switch aspect. After the controller finishes the optimized routing path for each switch, the corresponding routing table will be updated to every switch in the network and once the environment changes the controller will update the routing table immediately. There are some advantages by using SDN.
1. Better computing power: by using more powerful server to compute complicated algorithm
2. More information: the centralized controller can collect data from every switch
3. Dynamically routing adjustment: SDN controller can collect real-time information and then generate the corresponding routing table

**Centralized SDN controller**

## Related Works
We study several papers related to SDN controller load balance, and we select two papers introduce below.
* “A Load Balancing Strategy for SDN Controller based on Distributed Decision” International Conference on Trust, Security and Privacy in Computing and Communications, 2014.
* “Load-Balancing Mechanism for Distributed SDN Control Plane Using Response Time,” IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT, 2018.

In the first paper, authors proposed a new load balance strategy in multiple SDN controller environment, which is called Dynamic and Adaptive Load Balancing (DALB).
DALB has some feature:
* DALB is totally based on distributed architecture, without any centralized component.
* DALB is running on every SDN controller and it allows controller make load balancing policy locality, which reduces the decision delay caused by network transmission.
* DALB can make load decision based on the collected information locality and elect high-load switches to migrate to an under-load SDN controller to realize load balancing among distributed controllers.

Distributed decision can reduce decision delay
Flowchart of DALB

In the second paper, proposed a new concept absolute load balancing will not necessary. Previous works have proposed load-balancing methods with switch migration to address this issue. However, the higher-load controller is always directly considered as the overloaded controller that need to shift its load to other controllers, even if it has no response time delay.The pursuit of absolute load-balancing effect can also result in frequent network delays and service interruptions.
* SMCLBRT
To avoid frequently unnecessary operations, we take full advantage of the changing features of response time and controller load and propose a novel load-balancing scheme, the SDN multiple controller load-balancing strategy based on response time (SMCLBRT).

Basic Architecture of SMCLBRT

## Fat-tree Topology
The fat tree network is a universal network for provably efficient communication and it was invented by Charles E. Leiserson of the Massachusetts Institute of Technology in 1985.

One problem with the traditional tree structure is that the root easily becomes a communication bottleneck. This is because in order to communicate between child nodes, all must pass through the parent node. In this way, the closer the link is to the root, the greater the amount of communication.

Traditional tree structure

In 1985, Leiserson proposed to modify the general tree structure used in computer science into a fat tree.

In the fat tree structure, the path between nodes gradually widens from the leaf to the root, which adapts to the actual requirement that the traffic volume gradually increases from the leaf to the root.

In this team report, we design a 3-layer fat-tree structure to achieve the load balance for networks traffic.

To perform load balancing and achieve better transmission rate, our group present a algorithm to efficiently schedule flows for 3-layer fat-tree topology networks by using ONOS controller. The algorithm utilizes the hierarchical feature of 3-layer fat-tree networks to recursively search for a path, and makes decisions based on real-time traffic statistics obtained via the OpenFlow protocol. After using the Mininet network emulator to evaluate the algorithm, by comparing it with the none load balancing algorithms.

## Tools
1. OS - Ubuntu 18.04 LTS
2. SDN Controller - ONOS
3. Open Source Build and Test Tool - Bazel
4. Network Simulator - Mininet
5. Language - Java

## Implementation Approach

We implement the ONOS application in java language, which is a official interface provided by ONOS. The java language interface of ONOS application is more efficiently than Northbound APIs (REST APIs). The main functionalities of our load balance application is written in the class **LBmanager**, and we use the infrastructure class in onosproject project.
These are some important utility classes support by ONOS:
* **org.onosproject.net.topology.DefaultTopologyVertex**:Creates a new topology vertex that can be used in DFS
* **org.onosproject.net.device.DeviceService:** Get the current speed and flows in the switch.
* **org.onosproject.net.statistic.PortStatisticsService:** Obtaining statistic information about device ports.

**Our load balance algorithm**:
1. Find All Paths
* Use DFS, with given source host A and destination host B, search recursively until all possible acylic path from A to B are found.
2. Calculate Weight
* Using the utility classes mentioned above, we are able to obtain the load percentage on each link by calculating (remained bandwidth)/(entire bandwidth),which will be actual weight of that link.
* The weight of the entire path is equal to the maximum weight among all of its link.
3. Select the best path
* Sort all path weight in ascending order
* Select all the top ranking paths where its weight < minimum path weight + measureTolerance
* Select best path from these selected paths where its count of link is the least
5. Build the entire path
* Prepend soure edge link and destination edge link to the best path to form actual routing path

Our load balance main class:

The class to measurment link loading:

The formuala to measure link loading in **LB_MetricLinkWeight**:
The packet processing class:

## Result
Below is a simple test for our LoadBalance application in ONOS.
* Fat-tree topology in the onos web gui, and port numbers in the swich **of:0000000000000002**.

* Activate our load balance application in ONOS, called **LoadBalance**.
* Firstly, the **h1** host ping **h8** host.
* The flows in the switch **of:0000000000000002**.
* Next, the **h2** host ping **h8** host.
* Because the port 3 has traffic, but port 4 has no traffic. Our **LoadBalance** application select port 4 for host **h2** ping command.

* The path of **h1 ping h8**, and **h2 ping h8**.

## Reference
[James F. Kurose, Keith W. Ross, Computer networking : a top-down approach, 6th ed. PEARSON]
[A Load Balancing Strategy of SDN Controller Based on Distributed Decision](https://ieeexplore.ieee.org/document/7011337)
[A Load-Balancing Mechanism for Distributed SDN Control Plane Using Response Time](https://ieeexplore.ieee.org/document/8493344)
[ONOS Java API](http://api.onosproject.org/1.3.0/apidocs/)