Congestion and packet classification based flow management for software-defined networks

Abstract

In this thesis, we focus on problems in the control plane and problems in the data plane of SDN separaterly. In the control plane, we specifically try to increase the response time of the SDN controller in ultra-dense scenarios. In the data plane, we aim to construct an efficient data structure to achieve both fast rule update and fast packet classification. In the SDN, the control plane is responsible for deciding route and operations for flows that coming to the data plane. To do so, the SDN controller in the control plane has a central view and controls all switches in the data plane. But, this can cause an increase in both e2e latencies of packets and drop rate in the controller if there is a high spiky demand of incoming heterogeneous flows. Because, switches in data plane have to ask what to do to the controller if there is a new incoming flow to them. When newly coming flows increase, communication traffic between the controller and data plane increase. As a result, this can cause congestion in the SDN controller, and e2e latency and drop rate in the controller increase because of this congestion. To solve these problems, we propose a management engine to implement in the SDN controller in ultra-dense SDN scenarios. In this engine, we propose two steps: admission and prioritization steps. We also create different queues for different types of 5G flows (URLLC, eMBB, mMTC) in each step. In the admission, we modify Loss Ratio-Based Random Early Detection (LRED) Algorithm. In prioritization, we propose a tree-based prioritization that considers the priority needs of different flow types and near future states of different queues. According to simulation results, our response time of the SDN controller, e2e latency of packets and dropped rate in the controller are better up to 53%, 58%, and 36%, respectively. Packet classification is a key factor for choosing proper action for incoming packet and has to be done fast, especially in OpenFlow. But OpenFlow vSwitch technology doesn't allow to use some fast hardware technology for packet classification like TCAM. Decision tree methods are preferred solutions for fast classification in OpenFlow vSwitch in the literature. But most of these methods can cause the rule replication problem. As a result, while the duration of packet classification decreases, rule update duration increases. There are also rule partitioning methods in the literature to solve this problem, but the running time of these methods mostly depends on the number of rule fields. Also, some of these solutions don't overcome the rule replication problem. At that point, the main question is that how can we make the rule partitioning fast by both preventing the rule replication and allowing fast packet classification and rule update in OpenFlow vSwitch? To solve the rule partitioning problem, we convert this problem to the interval partitioning and propose a classic Greedy Algorithm. As a result, the running time of the partitioning algorithm only depends on the rule number. After partitioning, we propose to use HyperCuts to construct decision trees for fast packet classification and rule update. According to performance evaluation results, we do the rule partitioning and rule updates faster than the PartitionSort method with the percentage of 88, 15, respectively. We also classify packets faster than the TupleMerge method with the percentage of 40 for online and 50 for offline scenarios.