5.3.3. The value of objective function

5.3.4. The overhead for all flows

Seen from Fig. 7, the overhead of First-node algorithm is larger than other algorithms. With the increasing of the arrival rate of new flows, the overhead gap also increases. It is worth empha- sizing that there are many different network packets whose sizes are between 100 bytes and 300 bytes according to the statistics in [17]. As described in Section 3, the longer the forwarding path is or the smaller the packet size is, the larger the overhead becomes. So the First-node algorithm cannot be widely used since the overhead may exceed the network border load in the networks. Although the overhead of All-nodes algorithm is very small, it needs to install a lot of flow table entries as shown in Fig. 4 and Fig. 5, while it rejects many flows in Fig. 9 due to the TCAM capacity limit. The number of flows that can be transmitted by the network is an im- portant indicator to evaluate the performance of the network, so the All-nodes algorithm is not suitable for large-scale deployment. In summary, the algorithm KSGT is the best choice.

5.3.5. The percentage of overhead

We test the average overhead percentage of total load by run- ning all algorithms 100 times. Fig. 8 demonstrates the evaluation results of the average overhead and error bars of standard devi- ation on the forwarding path, from which we can learn that our proposal keeps a low percentage compared to the First-node algo- rithm and JumpFlow algorithm. Although the All-nodes algorithm achieves the lowest overhead percentage, it installs the most en- tries in the switches in Fig. 4 and leads to massive flows rejected in Fig. 9. Hence, the KSGT algorithm is more feasible in terms of reducing and balancing the flow entries in SDN switches to hold more flows in networks with low overhead.

5.3.6. The percentage of rejected flows

The rejected flows mean that these flows cannot be successfully transmitted because the flow tables are full. Fig. 9 shows that with the increasing of the arrival rate of new flows, the All-nodes algorithm leads to more and more flows rejected. In other words, the KSGT algorithm improves the successful installation and forwarding flows by about 25% as compared with All-nodes algorithm. So the All-nodes algorithm cannot be widely used because it causes massive flows rejected. Although the First-node algorithm causes a small percentage of flows to be rejected, it causes too much over- head in Figs. 7 and 8. The percentage of rejected flows of KSGT algorithm is close to the First-node algorithm, and KSGT algorithm has tolerable overhead, thereby the KSGT algorithm is more practical.

6. Related work

In order to avoid flow table overflow, some researches try to increase the usage efficiency of flow tables. Zhu et al. [9] propose the dynamic timeout for SDN-based data centers, which can assign a suitable timeout to different flows according to their character- istics, 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. Cohen et al. [3] concentrate on satisfying global network objectives, such as the maximum flow, for maximizing network utilization in environ- ments where the size of the forwarding table in network devices is limited. However, it can only handle the static scene.

Liang et al. [7] focus on optimizing idle_timeout value for In- stant Messaging (IM) to balance flow tables and controller processing resources in OpenFlow networks, but their scheme only bal- ances flow tables and cannot 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 gen- erate a large number of packet-in events per second to indicate the controller processing resource cost. Kim et al. [5] propose a mod- ified 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 because the flow tables of switches are not bal- anced. Guo et al. [10] 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.

Banerjee and Kannan [30] propose Tag-In-Tag, an approach that exploits SDN features and replaces the flow entries with two lay- ers 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. The other tagging allows finer identification of the flows to enable flow spe- cific actions. However, this can be troublesome for large graphs as this can lead to path explosion. The key idea in segment rout- ing [11,12] is to break up the routing path into segments in or- der 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.

The work of Chu et al. [20] is based on the destination of each flow on the fault link, so each of the nodes on the forwarding path of the flow should be configured in advance for any possi- ble link failure on the forwarding path. In order to avoid link over- head, some works [31–33] try to use the SDN switches to manage the traffic in the network. Other works [21,34] based on the full topology to achieve load balancing for the links at the exit ports of the SDN switches. All these schemes must collect the workload on each link and the traffic volume between all source-destination pairs by the controller when the link fails, so the recovery time will be larger than 50ms.

Cascone et al. [35] deploy SDN switches in enterprise networks using VLANs and switch ports to enable each flow to go through at least one SDN switch. The main contribution of et al. [36] is to systematically tackle the problem of how to partially deploy SDN-enabled switches into existing legacy networks, and reap the benefits of the controllable network, subject to budget and re- source constraints. However, the scheme is limited by the number of VLANs, and it also needs to set the switch ports.

Caria et al. [34] focus on the hybrid SDN network scenario and discuss about the migration algorithms from the perspective of traffic engineering in an ISP network. It proposes a new architec- ture for a hybrid SDN/OSPF operation, in which a few SDN node is used to partition the OSPF domain into multiple sub-domains. Caria et al. [34] mainly concentrates on searching for an optimized migration sequence of the routers in the traditional IP network to minimize the maximum link utilization. But the SDN switches de- ployment scheme is not able to work for some topologies. The traf- fic scheduling in the intra-domain cannot be optimized. Cascone et al. [35] present two traffic management applications that exploit a stateful data plane and their prototype implementation based on OpenState, an OpenFlow evolution that recently proposed. The au- thors present two applications, namely forwarding consistency and failure recovery, that greatly benefit from the stateful SDN data plane. However, it will not be able to achieve traffic load balanc- ing. The program requires to pre-configure a large number of flow table entries, which occupy a large number of ternary content ad- dressable memory (TCAM) resources in SDN switches, and these flow table entries will not be used for a very long time until the distant link fails. In our scheme, we can effectively reduce and bal- ance the flow table entries of different switches even though many new flows arrive in the network at the same time.

7 Conclusions

In this paper, we formulate the problem of reducing and bal- ancing the flow table entries to hold more flows with low overhead as an optimization problem. The problem is proved to be NP-hard. Hence, we propose the greedy algorithm KSGT to solve the prob- lem. Compared with the existing solutions, KSGT can reduce about 60% of flow entries when processing the same amount of flows; and improve the successful installation and forwarding flows by about 25% under the same flow table space in SDN switches. Con- sidering the limited flow table space in SDN switches and MPLS labels overhead in the network, KSGT is the best choice to be used in real networks. We present our future work in two aspects. Theo- retically, on the one hand, we will try to improve the classification efficiency of the flows in order to better schedule the flows. On the other hand, we need to pay attention to the Multi-level flowtable structure and analyze the flow table aggregation algorithm based on TCAMs.

分享让更多人看到