Gather: A method to optimize the number of control flow tables in SDN networks with in-band control

1. Introduction

In-band SDN networks have attracted more and more attention due to their good flexibility and economical deployment. However, in in-band SDN networks, control flows and data flows share a physical link for forwarding. Therefore, switches need to store flow entries for forwarding control flows. This will cause too many flow entries in some SDN switches close to the controller in some large networks, such as data center networks. A large number of flow tables will not only make management complicated, but also occupy network resources such as TCAM. So we proposed Gather: a method to optimize these flow entries for forwarding control flows.

2. Design Introduction

(1) Design basis

The following figure shows the flow table distribution diagram of the SDN network under traditional in-band control (this article only focuses on the case of one controller):

Figure 1: Organization of flow tables in traditional SDN networks

In a network topology, if the shortest path algorithm is used to calculate the path from each switch to the controller, a tree-like control topology can be obtained. Gather is optimized based on this tree-like topology. From the figure, it can be seen that the characteristic of flow table storage in traditional networks is that switches close to the controller need to store flow table items of control flows for subsequent child nodes. Therefore, switches closer to the root (controller) need to store more flow table items of control flows. In networks with a large number of switches, such as data center networks, this will cause a significant surge in the number of flow tables in switches close to the controller. The main goal of Gather is to reduce these unnecessary flow table overheads.

(2) Design ideas

The basic idea of ​​Gather is to divide the switches in the topology into groups. A group is equivalent to a connected subset of the entire control tree. At the same time, a group is represented by a label (label or tag). There are many ways to implement labels. In this article, we use segment routing to implement the label system. The following figure is a schematic diagram of Gather:

Figure 2: Gather flow table optimization diagram

As can be seen from the figure, S2, S3, and S4 are grouped together, and all packets sent to this group are labeled with an X label. After receiving the packet, S2 will know that the packet is data sent to the switch in the group by matching the X label. It will then continue to match the flow table of the packet in flow table 2 to determine the forwarding strategy. At the same time, after a round of topology optimization, a second round of optimization can still be performed based on the existing grouping. The specific approach is to treat all groups as switches and replace them. After that, a reduced topology will be obtained, and the optimization can be repeated on this topology to further reduce the flow table of the control flow. But at the same time, one label will be added to the data packet.

(3) How to find a valid group?

There are many ways to find effective groups, and you can design the required algorithms according to your needs. Before introducing the algorithm, some definitions are given first: Node distance refers to the number of intermediate nodes from a node to the controller, S refers to the set of child nodes, G is the set of groups output in the end, and time of optimization refers to the number of times the full topology is optimized. After one optimization, the topology needs to be modified (groups and switches are replaced). In this algorithm, the basic idea is to use the depth-first algorithm first and start calculating from the leaf nodes. As can be seen from the algorithm, it uses an iterative idea, extending to a leaf node and then calculating and comparing each node upward. Then it will determine the distribution of the group based on the comparison results.

3. Design Test

First, we test the effect of the label in the data packet (the structure of the group is implemented using segment routing in this paper) on the forwarding delay. The test results are as follows:

Figure 3 Test results of the number of labels on forwarding delay

From the table, we can see that labels have little impact on forwarding delay. Even in the case of 3 labels, the delay is only 4% higher than that of traditional forwarding. We then tested the ability to optimize the flow table, and the results are as follows:

Figure 4 Schematic diagram of flow table optimization structure

It can be seen from the three topologies that the results of the first optimization are generally good, while the results of the second and third optimizations drop very quickly. This is because the topology after replacing the group with the switch in the first optimization is much smaller than the topology before optimization. Therefore, the number of flow table entries that can be optimized is also much smaller. At the same time, this is also related to the design of the algorithm.