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 coincidence degree of the forwarding paths of the flows. The KSGT algorithm has low time complexity because it does not enumerate the whole solution space. Moreover, it uses the cost function shown in equation 7 to balance the flow table entries of switches. The algorithm All-nodes [23] 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 [24] 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 installs the least flow table entries in all algorithms, but it may cause the most overhead load.

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 [22]. We randomly set the initial flow entries number of switches which do not exceed the flow table capacity u_{max}. We assume that each switch's flow table capacity u_{max} is equal to 5000. We evaluate the algorithms with different new flows arrival speed 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

1)The number of entries installed for all nodes

Fig. 2 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. 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 $\varphi$ as the analysis in Section 3 and may cause too much overhead load as shown in Fig. 4. However, the KSGT algorithm can overcome these drawbacks. So the KSGT algorithm is more practical.

2)The difference between the maximum and minimum flow entries to be installed

We use $\sigma$ to describe the maximum flow entries subtract the minimum flow entries, so $\sigma$ can describe the balance degree of flow table of different switches. As shown in Fig. 3, with the increasing of the arrival rates of new flows, the value of $\sigma$ is increasing. We can find that the parameter $\sigma$ of the KSGT algorithm is always smaller than the all-nodes algorithm. So the switches' flow tables of KSGT algorithm are more uniform than All-nodes algorithm. From Fig. 4 and Fig. 5, we can see the First-node algorithm causes too much overhead load. As it is analysed in our model, it can not be applied to the networks where the overhead load is restricted.

3)The overhead load for all flows

Seen from Fig. 4, the overhead load of First-node algorithm is larger than other algorithms. With the increase of the arrival rate of new flows, the overhead load gap also increases.It is worth emphasizing that there are many different network packets whose sizes are between 100 bytes and 300 bytes according to the statistics in [17]. So the average overhead load on the link of the forwarding path is about 18% of total load. As described in Section \ref{sec: system}, the longer the forwarding path is or the smaller the packet size is, the larger the overhead load becomes. So the First-node algorithm can not be widely used since the overhead load may exceed the network border load in the networks.

4) The percentage of overhead load

We test the average overhead load percentage of total load by running all algorithms 100 times. Fig. 5 demonstrates the evaluation results of the average overhead load and error bars of standard deviation on the forwarding path, from which we can learn that our proposal keeps a low percentage compared to the First-node algorithm. Although the All-nodes algorithm achieves the lowest overhead load percentage, it installs the most entries in the switches in Fig. 6 and leads to massive flows rejected in Fig. 2. Hence, the KSGT algorithm is more feasible in terms of reducing and balancing the flow entries in SDN switches to accommodate more flows in networks.

5)The percentage of rejected flows

The rejected flows mean that these flows can not be successfully transmitted because the flow tables are full, so the switches can not forward the packets of the flows. Fig.6 shows that with the increase 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 can not 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 overhead load in Fig. 4 and Fig. 5. The percentage of rejected flows of KSGT algorithm is close to the First-node algorithm, and the overhead load of KSGT algorithm is tolerable, so the KSGT algorithm is more practical.

6 Conclusions and Further Work

In this paper, we formulate the problem of reducing and balancing the flow table entries with limited TCAMs in SDN switches as an optimization problem, then we prove that the problem is an NP-hard problem. We propose the greedy algorithm KSGT to solve the problem. 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. Considering the limited flow table space in SDN switches and MPLS labels overhead in the network, KSGT is more widely used in real networks. We present our future work from two aspects. Theoretically, 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 flow table structure and analyze the flow table aggregation algorithm based on TCAMs.

References

[1] S. Jain, A. Kumar, S. Mandal, J. Ong, L. Poutievski, A. Singh,S. Venkata, J. Wanderer, J. Zhou, M. Zhu et al., “B4: Expe-rience with a globally-deployed software defined wan,” in inproceedings of the INFOCOM ACM SIGCOMM. ACM, 2013,pp. 3–14.

[2] Z. A. Qazi, C.-C. Tu, L. Chiang, R. Miao, V. Sekar, and M. Yu,“Simple-fying middlebox policy enforcement using sdn,” in inproceedings of the INFOCOM ACM SIGCOMM. ACM, 2013,pp. 27–38.

[3] R. Cohen, L. Lewin-Eytan, J. S. Naor et al., “On the effect offorwarding table size on sdn network utilization,” in Proceed-ings of IEEE INFOCOM.IEEE, 2014, pp. 1734–1742.

[4] H. Song, “Protocol-oblivious forwarding: Unleash the power ofsdn through a future-proof forwarding plane,” in Proceedings ofthe second ACM SIGCOMM workshop on Hot topics in softwaredefined networking.ACM, 2013, pp. 127–132.

[5] E.-D. Kim, Y. Choi, S.-I. Lee, M.-K. Shin, and H.-J. Kim, “Flowtable management scheme applying an lru caching algorithm,”in in proceedings of the Information and Communication Technology Convergence (ICTC).IEEE, 2014, pp. 335–340.

[6] H. Liang, P. Hong, J. Li, and D. Ni, “Effective idle timeoutvalue for instant messaging in software defined networks,” in inproceedings of the Communication Workshop (ICCW).

IEEE,2015, pp. 352–356.

[7] Z. Bozakov and P. Papadimitriou, “Towards a scalable software-defined network virtualization platform,” in in proceedings ofthe Network Operations and Management Symposium (NOMS).IEEE, 2014, pp. 1–8.

[8] H. Zhu, H. Fan, X. Luo, and Y. Jin, “Intelligent timeout master:Dynamic timeout for sdn-based data centers,” in in proceedingsof the Integrated Network Management (IM). IEEE, 2015, pp.734–737.

[9] Z. Guo, Y. Xu, M. Cello, J. Zhang, Z. Wang, M. Liu, andH. J. Chao, “Jumpflow: Reducing flow table usage in software-defined networks,” Computer Networks, vol. 92, pp. 300–315,

2015.

[10] K. Krishna and M. N. Murty, “Genetic k-means algorithm,”Systems, Man, and Cybernetics, Part B: Cybernetics, IEEETransactions on, no. 3, pp. 433–439, 1999.

[11] S. Banerjee and K. Kannan, “Tag-in-tag: Efficient flow tablemanagement in sdn switches,” in in proceedings of the Networkand Service Management (CNSM).IEEE, 2014, pp. 109–117.

[12] R. Bhatia, F. Hao, M. Kodialam, and T. Lakshman, “Opti-mized network traffic engineering using segment routing,” inin proceedings of the Computer Communications (INFOCOM).

IEEE, 2015, pp. 657–665.

[13] C. Filsfils, N. K. Nainar, C. Pignataro, J. C. Cardona, andP. Francois, “The segment routing architecture,” in in proceed-ings of the Global Communications Conference (GLOBECOM).IEEE, 2015, pp. 1–6.

[14]“Openflowswitchspecification1.3.1.”[On-line].vailable:https://www.caida.org/research/traffic-analysis/pkt size distribution/graphs.xml

[15]“Multi-protocollabelswitching(mpls)supportofifferentiatedservices.”

[Online].Available:http://www.hjp.at/doc/rfc/rfc3270.html

[16]“Encapsulatingmplsiniporgenericrout-ingencapsulation(gre).”[Online].Available:http://www.hjp.at/doc/rfc/rfc4023.html

[17]“Packetsizedistributioncomparisonbetweenin-ternetlinksin1998and2008.”[On-].Available::/ww.caida.org/research/traffic-analysis/pkt size distribution/graphs.xml

[18] S. Azodolmolky, P. Wieder, and R. Yahyapour, “Performanceevaluation of a scalablesoftware-defined networking deploy-ment,” in in proceedings of the Software Defined Networks(EWSDN).IEEE, 2013, pp. 68–74.

[19] S. P. Sinha and R. S. Balog Jr, “Lighting control system fordifferent load types,” 2001, uS Patent 6,188,181.

[20] P. Du and S. Abe, “Detecting dos attacks using packet sizedistribution,” in Bio-Inspired Models of Network, Informationand Computing Systems.IEEE, 2007, pp. 93–96.

[21] B. Fortz and M. Thorup, “Internet traffic engineering by op-timizing ospf weights,” in in proceedings of the INFOCOM.IEEE, 2000, pp. 519–528.

[22] N. Spring, R. Mahajan, and D. Wetherall, “Measuring isptopologies with rocketfuel,” in in proceedings of the SIGCOMM.ACM, 2002, pp. 133–145.

[23] N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar,L. Peterson, J. Rexford, S. Shenker, and J. Turner, “Openflow:enabling innovation in campus networks,” ACM SIGCOMMComputer Communication Review, no. 2, pp. 69–74, 2008.

[24] P. Ashwood-Smith, M. Soliman, and T. Wan, “Sdn state reduc-ion,” IEFT draft, 2013. 

分享让更多人看到