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, Switch deployment, Flow control, Network management.

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 [2]. The Ternary Content Addressable Memory (TCAM) is widely used in SDN switches, which enables the fast forwarding packets in the data center network [3]. However, the capacity of TCAM in the SDN switches is limited since the TCAM is expensive [3,4]. OpenFlow in theory can establish fine-grained routing paths by installing flow entries in the OpenFlow switches via the controller [5]. But in practice, there are practical challenges such as limited flowtable sizes and dynamic flow change that need to be addressed [6]. Fol- lowing the basic OpenFlow principle, the OpenFlow controller in- stalls 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 because the flow entries cannot be installed successfully [7,8]. Hence, designing a scheme which 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,9] focus on assigning suitable timeout to different flows, and conducting a feedback control to adjust the max timeout value. However, these 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,7] 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 [10], on the other hand, can reduce flow entries in SDN switches, but it only handles a single flow.

In this paper, we aim 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 La- bel Switching (MPLS) labels for each packet to indicate the routing information of forwarding path. The Segment Routing (SR) technology has been recently presented to provide effective path control solutions while simplifying control plane operations [11]. SR can be applied to MPLS networks by exploiting the label stacking functionality [12]. Using the latest OpenFlow protocol [13], the SDN controller enforces a packet flow through a path by encapsulating a specifical designed stack of MPLS labels at the ingress node. This stack is compatible with the MPLS data plane and consists in an ordered list of segment identifiers (SIDs) [14]. During packet for- warding, only the top label in the stack is processed. That is, the packet is forwarded along the shortest path toward the destination by using the SID. For example, a SID can be related to the switch ports.

Unlike traditional MPLS networks, we maintain per-flow state only at the ingress node, where the label stack is initialized. No signaling protocol is required to populate the forwarding table by transit nodes, which reduces the control plane load and simplifies the complex and time-consuming provisioning procedures [14]. 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 over- head on the first link of forwarding path. Hence, we make full use of the advantages of SDN flexible center control to intelligently se- lect nodes to install flow entries.

Because reducing and balancing the flow entries in different SDN switches is an NP-hard problem, we propose a heuristic algorithm called K Similar Grade Tree (KSGT) to solve it under the network resource constraints. The KSGT algorithm comes from K- means algorithm [15], and includes four main phases: 1) KSGT di- vides 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 to in- stall flow 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. 4) KSGT uses a phase function to balance the flow table entries of different switches. We evaluate KSGT against the per-hop configuration-based forwarding scenario and the first-hop configuration-based scenario in a real network topology with different traffic patterns. KSGT can reduce about 60% of flow entries compared to the previous algorithms, and improve about 25% of the successful installation and forwarding flows under the same flow table space. 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 of MPLS labels when reducing flow table entries in SDN networks. We formulate the problem as an optimization problem, which is proved to be NP-hard.

2.We propose the KSGT algorithm which can reduce and balance the flow table entries in SDN switches with low overhead. The resulting network can accommodate more flows even if the capacity of TCAMs in switches is limited.

3.KSGT is evaluated by extensive simulations 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.

The rest of the paper is organized as follows. In Section 2, we illustrate the motivation and overview of this paper. Section 3 presents the model of our problem. We prove that the optimization problem is NP-hard. 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 un- der the same flow table space. In Section 6, we discuss some related works. Section 7 concludes the paper.

2 Motivation and overview

Throughout 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 with low overhead. The latest OpenFlow protocol supports MPLS technology [13], and the Push MPLS header actions can push new MPLS headers onto the packet. We encapsulate Multi-Protocol Label Switching (MPLS) labels for each packet to indicate the routing information of forwarding path [16].

We design the KSGT algorithm, which is a control plane architecture of SDN focusing on achieving low overhead and holding more flows in networks. The key to achieving our goal is how to reduce and balance the flow table entries of different switches with little overhead. The KSGT algorithm not only can realize the low overhead in SDN switches and the controller, but also can realize the low overhead on links.

In order to make full use of the rare resource of the flow table, we adopt the method of path aggregation. It cannot enumerate all possible paths as the number can be extremely large. However, the observation shows that DCNs do not intend to use all possible paths but a set of desired paths [6]. Based on this observation, KSGT focuses on pre-installing these desired paths in this paper. Even though, the number of desired paths is still large in large DCNs. To tackle the above challenges, we introduce flow sets to path aggregation and path ID assignment methods based on the forwarding path coincidence degree. The algorithm KSGT can re- duce a large number of flow table entries by reusing the flow en- tries to encapsulate and decapsulate the MPLS labels.

2.1 Achieving low overhead

In this section, we outline how to achieve low overhead when reducing and balancing flow entries in SDN switches to accommodate more flows in the networks. First, we use OpenFlow to encapsulate MPLS labels, which can eliminate the need to establish and maintain hierarchical instances of Label Switched Paths (LSPs). Nevertheless, LSPs are required to be maintained in the traditional MPLS protocol in multi-region/layer networks [11]. When a new MPLS label 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. We propose the KSGT algorithm to achieve low overhead and hold more flows in networks with the limited network resources. KSGT not only achieves the low over- head of SDN switches and the controller, but also achieves the low overhead of links.

2.1.1 Reduce links overhead

For example in Figs. 1 and 2, they show the first-hop configuration-based scheme and KSGT scheme respectively for a new flow f. When the first packet of flow f enters the ingress switch s1, the switch s1 will send it to controller using packetin message. Then the controller computes the forwarding path and installs a flow entry to the switch s1. The subsequent packets of the flow will be directly encapsulated MPLS labels to indicate the forwarding path when they arrive the switch s1.

In the scheme shown in Fig. 1, the controller only installs flow entries in ingress switch s1, so the packets are encapsulated with 9 MPLS labels, {2,2,3,2,3,2,3,2,2}, each number indicates a forwarding port of the switch on its routing path. The packets pop up one MPLS label as a forwarding port of switch when they pass through the switch. The size of one MPLS label is 4 bytes, and 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 [18]. Fig. 2 shows our scheme for a new flow f, the controller selects switches s1 and s7 to install flow entries. When the subsequent 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 routing path. Similarly, the subsequent packets of flow f are encapsulated with 3 MPLS labels when they reach the switch s7. Compared with the first-hop configuration-based scheme, our scheme can effectively reduce the links overhead caused by the encapsulation of MPLS labels (Section 3).

2.1.2. Reduce switches overhead

According to the above mentioned methods, the ingress node has to be installed flow entries to indicate the forwarding path. Then the ingress switch will be installed a lot of flow table entries that will exceed the TCAM capacity. Moreover, the ingress switch encapsulates MPLS labels for each flow, which may result in excessive overhead and delay at the switch. We present efficient rule- placement scheme that distributes flow entries across the switches on the forwarding path.

The ingress switch contributes the most to the delay and over- head. Our goal is to reduce and balance the flow table entries in SDN switches, while respecting the link overhead and delay caused by encapsulating MPLS labels. Since optimizing the rule placement is NP-hard [19], KSGT tries to minimize the average overhead and delay at the switches. If the overhead and delay is too high at a switch, the controller may configure the default wildcards at the switch to forward the traffic to adjacent switches. Meanwhile, the controller installs the flow table entries to the adjacent switches to encapsulate the MPLS labels. Hence, the adjacent switches may share the overhead and delay.

分享让更多人看到