Abstract: Software-Defined Networking (SDN) allows flexible and efficient management of networks. However, the limited capacity of flow tables in SDN switches hinders the deployment of SDN. In this paper, we propose a novel routing scheme to improve the efficiency of flow tables in SDNs. To efficiently use the routing scheme, we formulate an optimization problem with the objective to maximize the number of flows in the network, constrained by the limited flow table space in SDN switches.The problem is NP-hard, and we propose the K Similar Greedy Tree (KSGT) algorithm to solve it. We evaluate the performance of KSGT against ``traditional" SDN solutions with real-world topologies and traffic. The results show that, compared to the existing solutions, KSGT can reduce about 60% of flow entries when processing the same amount of flows, and improve about 25% of the successful installation and forwarding flows under the same flow table space..

Key words: Software-Defined Networking, MPLS, Flow table reuse, Overhead.

1 Introduction

With the development of next generation Internet, Software-Defined Networking (SDN) is widely used in enterprise WANs and data center networks [1]. Surveys show some companies deploy their SDN network devices, and achieve a lot of benefits by using simple switch configuration and traffic engineering [3].The Ternary Content Addressable Memory (TCAM) is widely used in SDN switches, and it enables the fast forwarding packets in the data center network [2]. However, the capacity of TCAM in the SDN switch is limited since the TCAM is expensive, thus the flow tables of switch is limited [3][4][5]. Following the basic OpenFlow principle, the OpenFlow controller installs flow entries to every switch in the forwarding path, so the flow table capacity is often not enough when there are a large number of flows in the network. The flow entries are overflowed in some core switches but underflowed in other switches, which may cause a lot of flows transmission failure when the flow tables of some core switches are highly utilized [6][7]. Hence, designing a scheme that can efficiently reduce and balance the flow table entries to accommodate more flows in networks is a paramount problem.

To accommodate more traffic in the network,some studies [3][8] focus on assigning suitable timeout to different flows, and conducting a feedback control to adjust the max timeout value. However, those schemes may cause overload on the links between the controller and switches because the switches generate a large number of packet-in events. Alternatively, some studies [5][6] try to increase the flow entry matching rate by caching the flow entries in switches as many as possible, but it can not improve the capacity of the flow number in the network.JumpFlow [9], on the other hand, reduces flow entries in SDN switches, but it only handles a single flow.

In this paper, we try to solve the problem of how to reduce and balance the flow entries in different SDN switches to accommodate more flows in networks. We encapsulate Multi-Protocol Label Switching (MPLS) labels for each packet to indicate the routing information of forwarding path. Therefore, we do not need to install the flow entry to each switch of the forwarding path. However, if we add the MPLS labels to the packet only at the ingress node, it will generate too much overhead on the first link of forwarding path. Hence, we make full use of the advantages of SDN flexible center control to intelligently select nodes to install flow entry.

Although the problem of reducing and balancing the flow entries in different SDN switches is an NP-hard problem,we propose a fast algorithm called K Similar Grade Tree (KSGT) to solve it under the network resource constraints. The KSGT algorithm comes from K-means algorithm [10], and it includes four main phases: 1) KSGT divides all flows into some clusters based on the coincidence degree of the forwarding paths of the flows.2) KSGT greedily selects a small number of switches from the forwarding path of flow to install entries. 3) KSGT just greedily enumerates the possible flow entry schemes of the flows in each cluster to achieve the optimal solutions of the cluster. So the KSGT does not have high time complexity since it does not enumerate all of the solution space. 4) We use a phase function to balance the flow table entries of different switches.Hence, KSGT can effectively reduce and balance the flow table entries of different switches even though many new flows arrive in the network at the same time.

The major contributions of this paper are listed as follows:

1) As far as we know, we are the first to consider the overhead load of MPLS labels when reducing flow table entries in SDN network. We formulate the problem as an optimization problem, and prove that the problem is NP-hard. %We also give the complexity analysis of the problem.

2)We propose the KSGT algorithm that can reduce and balance the flow table entries in SDN switches. We achieve the aim that the network can accommodate more flows even if the capacity of TCAMs in switches is limited.

3)We evaluate KSGT by extensive simulation studies with real network topologies. The results of the simulation demonstrate that KSGT can effectively reduce flow entries in SDN switches and achieve a good balance of flow tables. %when the number of TCAM is limited

The rest of the paper is organized as follows. In Section 2, we discuss some related works. Section 3 presents the model of our problem. In Section 4, the KSGT algorithm is proposed to solve the problem. In Section 5, by comparing with the previous algorithms, the KSGT algorithm can achieve better performance with a little footprint. It can reduce about 60\% of flow entries compared to the previous algorithm, and improve about 25\% of the successful installation and forwarding flows under the same flow table space. In Section 6, we conclude the paper.

2 Related Works

In order to avoid flow table overflow, some researches try to increase the usage efficiency of flow tables. In [8], Zhu et al. propose the dynamic timeout for SDN-based data centers, which can assign a suitable timeout to different flows according to their characteristics, and conduct a feedback control from the switch to adjust the maximum timeout value according to the current flow table occupation. However, it may cause the controller overload due to the constraints of CPU, TCAMs, and other resources. In [3], Cohen et al. concentrate on satisfying global network objectives, such as the maximum flow, for maximizing network utilization in environments where the size of the forwarding table in network devices is limited. However, it can only handle the static scene.

Liang et al. [6] focus on optimizing idle\_timeout value for Instant Messaging (IM) to balance flow tables and controller processing resources in OpenFlow networks, but their scheme only balances flow tables and can not decrease the number of flow entries in SDN switches. Their scheme may also cause overload on the links between the controller and switches since the switches generate a large number of packet-in events per second to indicate controller processing resource cost. Kim et al. [5] propose a modified flow table management scheme by applying an LRU caching algorithm. By caching the flow entries in a flow table as many as possible, it increases the flow entry matching rate. But it will cause a lot of flow rejections when a large number of new flows appear at the same time due to the flow tables of switches are not balanced.

Guo et al. [9] also reduce flow entries in SDN switches, but their algorithm only handles a single flow and each packet only carries little routing information for the VLAN's limit.

In [11], Banerjee et al. propose Tag-In-Tag, an approach that exploits SDN features and replaces the flow entries with two layers of simpler and shorter tags. One level of tagging exploits the availability of unique path for individual flows from the ingress switch to egress switch that can be computed a-priori. Second level of tagging allows finer identification of the flows to enable flow specific actions.

However, this can be troublesome for large graphs as this can lead to path explosion. The key idea in segment routing [12][13] is to break up the routing path into segments in order to enable better network utilization. Segment routing enables finer control of the routing paths and can be used to route traffic through middle boxes. But those schemes ignore the effect of the overhead on the network.

3 Problem Formulation

3.1 System call

In this section, we formally define the problem of how to reduce and balance flow entries in SDN switches to accommodate more flows in the networks. The latest OpenFlow protocol supports MPLS technology [14], the Push MPLS header actions can push new MPLS headers onto the packet. When a new MPLS tag is pushed on an IP packet, it is the outermost MPLS tag, inserted as a shim header immediately before any MPLS tags or immediately before the IP header. We encapsulate multiple MPLS labels for each packet that indicates the forwarding port numbers of switches on its route. For example, Fig. 1 shows our scheme for a new flow f, the controller selects switches s1 and s7 to install flow entries. When the packets of flow f enter the ingress switch s1, they are encapsulated with 5 MPLS labels, {2,2,3,2,3}, each number indicates a forwarding port of the switch on its route. The packets pop up one MPLS label as a forwarding port of switch when they pass through the switch. Similarly, the packets of flow f are encapsulated with 3 MPLS labels when they reach the switch s7.

The general packet-out message of SDN is to install flow entries in all switches of forwarding path. But we just select a few switches to install flow entries by encapsulating the MPLS tags. It can save TCAM resources by reducing a large number of flow table entries. Moreover, unlike traditional network MPLS, there is no need to maintain path state in forwarding path except on the ingress node, because packets are now routed based on the list of labels they carry [12].The ingress node has to be installed flow entries since it needs to determine the path and add the segment labels to the packet..

3.2 Notation

Let G = (V, E) be a network, where V is the set of nodes, and E is the set of links. Let $F$ denote the set of traffic flows.We use v to represent a node in the network, f to represent a flow in the network.Let r_f denote the arrival rate of flow f, and u_{max} be the flow table capacity of a SDN switch. We use u_v to denote the number of entries in the node v that have been installed before the arrival of the flows, w_v to denote the number of entries to be installed in the node v by controller for all flows. The full list of notations is shown in Table \ref{table:1}..

3.3 Constraints

The goal of the problem is to reduce and balance the flow entries in SDN switches to accommodate more flows with the limited network resources. In our scheme, the switches forwarding packets are based on multiple MPLS labels which are encapsulated with forwarding ports of switches. We give some constraints and definitions before modeling.

Definition 1. Overhead load: The MPLS labels can not be regarded as payload. We define the overhead load as $Inl(c_f)$ since the flow $f$ is encapsulated with MPLS labels to carry the routing information [15][16]. The size of MPLS labels is 4 bytes, so the overhead load for flow $f$ can be formulated as.

Definition 2. Border load: We define border load ? as the tolerable overhead load proportion of each packet in the network.

The smallest data packet size is 46 bytes in the network, butthe size of each MPLS label is 4 bytes [6]. In Fig. 1, if we just install entry at the flow's ingress switch, the size of MPLS labels is 4*9=36 bytes for each packet, so the overhead load on the link between s1 and s2 is more than 12\% of total load for these packets whose sizes are less than 300 bytes. Note that there are many different network packets whose sizes are between 100 bytes and 300 bytes according to the statistics in [17]. The longer the forwarding path is or the smaller the packet size is, the larger the overhead load becomes [19]. So we must select some other nodes to install entries to reduce the overhead load instead of just installing entries in the ingress switch. Hence, we define the border load ratio v for each packet in the network to limit the overhead load [18].

According to the measurement method in [20], we can suppose an observation window contains S packets at time t. The average packet size at time $t$ is defined as

分享让更多人看到