Scalable 5-Tuple Packet Classification in Overlay Network-Based SDN

Sammanfattning: Traditional networking paradigm, with destination-based forwarding, provides low processing latency in terms of lookup time and it can scale to huge number of rules for traffic engineering. On the other hand, it lacks flexibility in terms of the packet header fields that can be used to implement the traffic engineering rules. The global view of the network or network abstraction is also lacking here, hence it is harder to program the network. The flexibility and programmability problem are two reasons, among others, that motivate the rise of the Software-Defined Network (SDN) paradigm: higher flexibility for traffic engineering and easier programmability for finer traffic engineering rules. SDN offers a huge degree of flexibility in the network for traffic engineering, for example in an OpenFlow-based network infrastructure, up to 38 packet header fields can be observed. This degree of flexibility comes however with a cost in terms of lookup times for packet forwarding, it does not scale for huge number of rules. The SDN paradigm also introduces the centralized control plane, which makes it easier to program the network. One of the well-known implementation of SDN is an overlay network, which builds a virtual network as an abstraction of the physical network. It simplifies the logical topology and provides more flexibility in terms of network programmability. In the overlay network implementation the rules are placed centrally in the centralized controller, rather than distributed to the network devices, hence it is easier to manage and program the network. The drawback of the centralized rules storing is that the requirement of storage space to store the rules is increasing significantly. Consequently, while SDN offers high flexibility and network programmability, it comes with problems for traffic engineering: high processing latency and storage requirement. With the increasing number of applications hosted in the network and the increasing needs for finer traffic engineering, more scalable ways to implement finer traffic engineering rules are needed, so the system can scale even with high number of rules. In this thesis, we address of problem of rule aggregation, a process to combine multiple rules without losing the accuracy of the original individual rules. We also address the problem of packet classification, a process to decide which flow that a packet belongs to and to determine which action needs to be taken for that packet. We propose one possible solution for rule aggregation and packet classification for overlay networks, focusing on 5-tuple traffic engineering rules, with the goal to minimize the storage space requirement and processing latency. The observed system performance metrics are the number of entries stored in the system, the number of entries observed for classification and the lookup times. The proposed solution is evaluated by means of system-level simulation and implementation in the Open Overlay Router and Vector Packet Processing (VPP) platform using synthetic rules generated with real-world distribution. The results are compared with a system without using the proposed rule aggregation and packet classification method. The results show that with the incorporation of both methods, the requirement for storage space and the processing latency can be reduced significantly. As an example, we note that 58.6% maximum saving in the storage required and 29.6% maximum delay reduction can be achieved.