4.4. Phase 3: getting the optimal solution in the kth cluster

The inputs of Algorithm 4 are the k-th (k ∈ [1, K]) cluster and the number of iteration times. The output is some optimal schemes for each cluster. Just as an element in scheme(cnumber) is one in- stalling flow entry scheme for flow cnumber, an element in scheme- cluster(k) is one installing flow entry scheme for all flows in the kth cluster. In line 10–16 of the algorithm, we calculate the objec- tive function for the switches of a scheme in the kth cluster. In line 17 we record the value of objective function and the corresponding flow entry installation scheme of the switches.

4.5 Algorithm Performance Analysis

We now analyze the complexity of the KSGT algorithm. In order to improve the performance, KSGT has some technical implemen- tation details in the algorithm. It usually set the loops in the K- Similar(G) algorithm (Phase 1) within five times, then it can meet other Phases’ demand.

5 Simulation

In this section, we evaluate our solution against baseline schemes use the real network topology 1755 ISP from the Rocketfuel [22]. The flows between node pairs are dynamically generated, and the size of each flow is random [18]. The results show that 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.

5.1 Comparison schemes

We propose the KSGT algorithm to solve the problem that reduces and balances the flow entries in SDN switches. The simulation results of the following algorithms are compared with each other to evaluate the KSGT algorithm.

KSGT: Firstly, it puts all flows in some clusters; secondly, it greedily selects schemes for each flow and each cluster; thirdly, it combines every two clusters into one cluster by choosing some optimal schemes until the last cluster. The last cluster contains the best solution.

Jumpflow: It is proposed in [17]. It uses the available VLAN identifier in the packet to carry routing information, so every packet only carries a few switch ports of forwarding path since the capacity of VLAN is limited.

All-nodes: The ``traditional" SDN solution that the controller installs flow entries to all switches of forwarding path for all flows [22]. It is likely to cause the flow table to overflow.

First-node: It installs an entry only at the flow's ingress switch [24], so the MPLS labels of each packet carry all information of forwarding path. Hence, it causes the most overhead load.

KSGT divides all flows into some clusters based on the coin- cidence degree of the forwarding paths of the flows. The KSGT algorithm has low time complexity because it does not enumer- ate the whole solution space. Moreover, it uses the cost function shown in Eq. (7) to balance the flow table entries of switches. The Jumpflow algorithm uses the available VLAN identifier in the packet to carry routing information, due to the limited space of the VLAN it can only carry little forwarding information. So it installs more flow entries to the switches than KSGT algorithm. The algo- rithm All-nodes [28] installs entries to all switches of forwarding path for all flows. So it installs the most flow table entries in all algorithms. The algorithm First-node [29] installs a flow entry only at the flow’s ingress switch, so each packet carries all switch ports of forwarding path using MPLS labels at the ingress switch. It in- stalls the least flow table entries in all algorithms, but it may cause the most overhead.

5.2 Simulation setup

We test the algorithms in the MacBook with a 2.6 GHz dual- core Intel Core i5 processor. To evaluate the proposed schemes, we use the real network topology 1755 ISP with 332 nodes from the Rocketfuel [27]. KSGT randomly sets the number of initial flow entries which cannot exceed the flow table capacity u_max. KSGT assumes that each switch’s flow table capacity u_max is equal to 5000. We evaluate the algorithms with different new flows arrival speeds which range from 300 flows/second to 1100 flows/second [17], and we test each flow speed ten seconds to get the average value of all parameters.

5.3 Simulation results

5.3.1. The number of entries installed for all nodes

Fig. 4 shows that the number of flow entries installed for all nodes increases with the different arrival rates of new flows. It is evident that the result of KSGT algorithm is smaller than the All- nodes algorithm and JumpFlow algorithm. Compared with the All- nodes algorithm, the KSGT algorithm can reduce the number of the flow entries about 60%. But the OpenFlow protocol of SDN is still using the All-nodes algorithm now. The First-node algorithm may exceed the network border load φ as the analysis in Section 3 and cause too much overhead as shown in Fig. 7. However, the KSGT algorithm can overcome these drawbacks. So the KSGT algorithm is more practical.

5.3.2. The difference between the maximum and minimum flow entries to be installed

σ to describe the maximum flow entries subtract the minimum flow entries, so σ can describe the balance degree of flow table of different switches. As shown in Fig. 5, with the increasing of the arrival rates of new flows, the value of σ is also increases. We can find that the parameter σ of the KSGT algorithm is always smaller than the all-nodes algorithm and JumpFlow algorithm. So the switches’ flow tables of KSGT algorithm are more uniform than All-nodes algorithm and JumpFlow algorithm.

From Figs. 7 and 8, we can see the First-node algorithm causes too much overhead. As it is analyzed in our model, it cannot be applied to the networks where the overhead is restricted. Hence, KSGT algorithm is the best choice to be used in real networks.

分享让更多人看到