Optimization Framework for Minimizing Rule Update Latency in SDN Switches

doi:10.19729/j.cnki.1673-5188.2018.04.004

ZTE Communications ›› 2018, Vol. 16 ›› Issue (4): 15-29.DOI: 10.19729/j.cnki.1673-5188.2018.04.004

• Special Topic • Previous Articles Next Articles

Optimization Framework for Minimizing Rule Update Latency in SDN Switches

CHEN Yan^1,², WEN Xitao³, LENG Xue¹, YANG Bo⁴, Li Erran Li⁵, ZHENG Peng⁶, HU Chengchen⁶

^1. College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China
^2. Department of Electrical Engineering and Computer Science, Northwestern University, Evanston, IL 60208, USA
^3. Google Inc., Mountain View, CA 94043, USA
^4. Microsoft, Shanghai 200000, China
^5. Uber Technologies Inc., San Francisco, CA 94103, USA
^6. School of Electronic and Information Engineering, Xi’an Jiaotong University, Xi’an 710049, China

Received:2018-07-17 Online:2018-07-17 Published:2018-10-25
About author:CHEN Yan (ychen@northwestern.edu) received the Ph.D. degree in computer science from the University of California at Berkeley, USA, in 2003. He is currently a professor with the Department of Electrical Engineering and Computer Science, Northwestern University, USA and a distinguished professor with the College of Computer Science and Technology, Zhejiang University, China. Based on Google Scholar, his papers have been cited over 10,000 times and his h-index is 49. His research interests include network security, measurement, and diagnosis for large-scale networks and distributed systems. He received the Department of Energy Early CAREER Award in 2005, the Department of Defense Young Investigator Award in 2007, the Best Paper nomination in ACM SIGCOMM 2010, and the Most Influential Paper Award in ASPLOS 2018.|WEN Xitao (xitao.wen@gmail.com) received the B.S. degree in computer science from Peking University, China, in 2010, and the Ph.D. degree in computer science from Northwestern University, USA, in 2016. His research interests span the area of networking and security in networked systems, with a current focus on software-defined network security and data center networks.|LENG Xue (lengxue_2015@outlook.com) received the B.S. degree in computer science and technology from Harbin Engineering University, China, in 2015. She is currently pursuing the Ph.D. degree major in computer science and technology with Zhejiang University, China. Her research interests are software-defined networking (SDN), network function virtualization (NFV), microservice and 5G protocol verification. She is a student member of the IEEE and CCF.|YANG Bo (ybo2013@zju.edu.cn) received the B.S. degree in information security from the Huazhong University of Science and Technology, China, in 2013, and the M.S. degree in computer science from Zhejiang University, China, in 2016. He is currently a software engineer with Microsoft, Shanghai, China. His research interests include software-defined network and network security.|Li Erran Li (lierranli@gmail.com) received the Ph.D. degree in computer science from Cornell University, USA. He was a researcher with Bell Labs. He is currently with Uber and also an adjunct professor with the Computer Science Department, Columbia University, USA. His research interests are in machine learning algorithms, artificial intelligence, and systems and wireless networking. He is an ACM Distinguished Scientist. He was an associate editor of the IEEE Transactions on Networking and the IEEE Transactions on Mobile Computing. He co-founded several workshops in the areas of machine learning for intelligent transportation systems, big data, software defined networking, cellular networks, mobile computing, and security.|ZHENG Peng (zeepean@gmail.com) received the B.S. degree in information security from Northwestern Polytechnical University, Xi’an, China, in 2015. He is currently pursuing the Ph.D. degree with the Department of Computer Science and Technology, Xi’an Jiaotong University, China. He was a visiting research fellow at Duke University, USA from July to August 2017 and Brown University from July to October 2018, respectively. He has authored papers in CoNEXT, ICDCS, ICNP, etc. His research interests span the area of computer networking and systems, with a focus on the programmable network and software-defined networking.|HU Chengchen (chengchenhu@gmail.com) received the B.S. degree from the Department of Automation, North-Western Polytechnical University, China, and the Ph.D. degree from the Department of Computer Science and Technology, Tsinghua University, China, in 2003 and 2008, respectively. He worked as an assistant research professor with Tsinghua University from July 2008 to December 2010. After that, he joined the Department of Computer Science and Technology, Xi’an Jiaotong University, China, where he is currently a full professor. His main research interests include computer networking systems and network measurement and monitoring.
Supported by:
This work is supported by National Key R&D Program of China under Grant No(2017YFB0801703);the Key Research and Development Program of Zhejiang Province under Grant No(2018C01088)

Abstract

Abstract:

Benefited from the design of separating control plane and data plane, software defined networking (SDN) is widely concerned and applied. Its quick response capability to network events with changes in network policies enables more dynamic management of data center networks. Although the SDN controller architecture is increasingly optimized for swift policy updates, the data plane, especially the prevailing ternary content-addressable memory (TCAM) based flow tables on physical SDN switches, remains unoptimized for fast rule updates, and is gradually becoming the primary bottleneck along the policy update pipeline. In this paper, we present RuleTris, the first SDN update optimization framework that minimizes rule update latency for TCAM-based switches. RuleTris employs the dependency graph (DAG) as the key abstraction to minimize the update latency. RuleTris efficiently obtains the DAGs with novel dependency preserving algorithms that incrementally build rule dependency along with the compilation process. Then, in the guidance of the DAG, RuleTris calculates the TCAM update schedules that minimize TCAM entry moves, which are the main cause of TCAM update inefficiency. In evaluation, RuleTris achieves a median of <12 ms and 90-percentile of < 15ms the end-to-end perrule update latency on our hardware prototype, outperforming the state-of-the-art composition compiler CoVisor by ~ 20 times.

Key words: SDN, SDN-based cloud, network management, access control, unauthorized attack

CHEN Yan, WEN Xitao, LENG Xue, YANG Bo, Li Erran Li, ZHENG Peng, HU Chengchen. Optimization Framework for Minimizing Rule Update Latency in SDN Switches[J]. ZTE Communications, 2018, 16(4): 15-29.

Figures/Tables 11

Figure 1. Overview of RuleTris optimization framework.

Figure 2. An example rule insert in a TCAM table. The original TCAM table has five entries (Rules 1-5) and one empty slot in the end. Rule 6 needs to be inserted between Rules 1 and 2. In a), the firmware schedules the insertion plan according to the dependencies implied by the priority values, therefore Rule 2 through Rule 5 are moved in order to preserve their relative positions. In b), however, the DAG indicates the newly inserted Rule 6 has no dependency with Rules 3 and 4, therefore only Rules 2 and 5 need to be moved.

Figure 3. Example 1 of dependency construction in parallel composition: cross-product and empty rule removal.

Example 2 of dependency construction in parallel composition: equivalent rule reduction. Figure 4.

Figure 5. Example of sequential composition.

Figure 6. Resolving mega dependency relations.

Figure 7. Example of priority composition.

Figure 8. Example of TCAM move optimization.

Figure 9. Rule update overhead of L3-L4 monitoring + L3 router. The first group (HW) is hardware experiment results and the rest are emulation results.

Figure 10. Rule update overhead of L3-L4 network address translation (NAT) > L3 router.

Figure 11. Rule update overhead of single rule swaps with CacheFlow. Results are from hardware experiments.

References 28

[1]	Requirements of an MPLS Transport Profile, IETF RFC 5654, 2009.
[2]	M. Al-Fares, S. Radhakrishnan, B. Raghavan, N. Huang,A. Vahdat, “Hedera: Dynamic flow scheduling for data center networks.” in 7th USENIX Symposium on Networked Systems Design and Implementation (NSDI), San Jose, USA, 2010, pp. 19-19.
[3]	ONF. (2013, Oct. 8). Solution brief: SDN security considerations in the data center [Online]. Available:
[4]	M. Kuzniar, P. Perešíni,D. Kostic, “What you need to know about SDN flow tables,” in International Conference on Passive and Active Measurement, New York, USA, 2015, pp. 347-359. doi: 10.1007/978-3-319-15509-8_26.
[5]	X. Jin, H. H. Liu, R. Gandhi, et al., “Dynamic scheduling of network updates,” in ACM Conference on SIGCOMM, Chicago, USA, 2014, pp. 539-550. doi: 10.1145/2619239.2626307.
[6]	X. Jin, J. Gossels, J. Rexford,D. Walker, “CoVisor: a compositional hypervisor for software-defined networks,” in USENIX Symposium on Networked Systems Design and Implementation (NSDI’15), Oakland, USA, 2015, pp. 87-101.
[7]	X. T. Wen, C. X. Diao, X. Zhao, et al., “Compiling minimum incremental update for modular SDN languages,” in Third Workshop on Hot Topics in Software Defined Networking (HotSDN), Chicago, USA, 2014. doi: 10.1145/2620728.2620733.
[8]	J. Van Lunteren and T. Engbersen, “Fast and scalable packet classification,” IEEE Journal on Selected Areas in Communications, vol. 21, no. 4, pp. 560-571, May 2003. doi: 10.1109/JSAC.2003.810527.
[9]	T. Mishra and S. Sahni, “DUO-dual TCAM architecture for routing tables with incremental update,” in IEEE International Symposium on Computers and Communications (ISCC), Riccione, Italy, 2010, pp. 503-508. doi: 10.1109/ISCC.2010.5546713.
[10]	H. Y.Song and J. Turner, “Fast filter updates for packet classification using TCAM,” in IEEE GLOBECOM, San Francisco, USA, 2006. doi: 10.1109/GLOCOM.2006.342
[11]	D. Shah and P. Gupta, “Fast updating algorithms for TCAMs,” IEEE Micro, vol. 21, no. 1, pp. 36-47, Jan. 2001. doi: 10.1109/40.903060.
[12]	A. Voellmy, J. Wang et al., “Maple: simplifying SDN programming using algorithmic policies,” in ACM SIGCOMM, Hong Kong, China, 2013, pp. 87-98. doi: 10.1145/2534169.2486030.
[13]	N. Katta, O. Alipourfard, J. Rexford,D. Walker, “Infinite cacheflow in software-defined networks,” in Third Workshop on Hot Topics in Software Defined Networking (HotSDN), Chicago, USA, 2014, pp. 175-180. doi: 10.1145/2620728.2620734.
[14]	J. Reich, C. Monsanto, N. Foster, J. Rexford,D. Walker. (2013). Composing software defined networks [Online]. Available:
[15]	C. J. Anderson, N. Foster, A. Guha, et al., “NetKAT: semantic foundations for networks,” in 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL’14), San Diego, USA, 2014. doi: 10.1145/2535838.2535862.
[16]	C. C. Hu, J. Yang, H. B. Zhao,J. H. Lu. (2014). Design of all programmable innovation platform for software defined networking [Online]. Available:
[17]	ONetSwitch.(2018). ONetSwitch45 [Online]. Available:
[18]	K. He, J. Khalid, S. Das, et al., “Mazu: taming latency in software defined networks,” University of Wisconsin-Madison, Tech. Rep., 2014.
[19]	K. Pagiamtzis and A. Sheikholeslami, “Content-Addressable Memory Circuits and Architectures: A Tutorial and Survey,” IEEE Journal of Solid-State Circuits, vol. 41, no. 3, pp. 712-727, Mar. 2006. doi: 10.1109/JSSC.2005.864128.
[20]	N. Foster, R. Harrison, M. J. Freedman, et al., “Frenetic: a network programming language,” in 16th ACM SIGPLAN international conference on Functional programming, Tokyo, Japan, 2011, pp. 279-291. doi: 10.1145/2034773.2034812.
[21]	C. Monsanto, N. Foster, R. Harrison,D. Walker, “A compiler and run-time system for network programming languages,” in 39th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Philadelphia, USA, 2012, pp. 217-230. doi: 10.1145/2103656.2103685.
[22]	Ryu SDN Framework Community. (2015, Jan. 29). Ryu OpenFlow controller [Online]. Available:
[23]	D. E.Taylor and J. S. Turner, “ClassBench: A Packet Classification Benchmark,” IEEE/ACM Transactions on Networking, vol. 15, no. 3, pp. 499-511, Jun. 2007. doi: 10.1109/TNET.2007.893156.
[24]	A. Lazaris, D. Tahara et al., “Tango: simplifying SDN programming with automatic switch behavior inference, abstraction, and optimization,” in ACM International on Conference on Emerging Networking Experiments and Technologies (CoNext), Sydney, Australia, 2014, pp. 199-211. doi: 10.1145/2674005.2675011.
[25]	C.-Y. Hong, S. Kandula, R. Mahajan, et al., “Achieving high utilization with software-driven WAN,” in ACM SIGCOMM, Hong Kong, China, 2013, pp. 15-26. doi: 10.1145/2486001.2486012.
[26]	H. H. Liu, X. Wu, M. Zhang, et al., “zUpdate: updating data center networks with zero loss,” ACM SIGCOMM, Hong Kong, China, 2013. doi: 10.1145/2534169.2486005.
[27]	M. Reitblatt, N. Foster, J. Rexford, C. Schlesinger,D. Walker, “Abstractions for network update,” in ACM SIGCOMM, Helsinki, Finland, 2012. doi: 10.1145/2342356.2342427.
[28]	N. P. Katta, J. Rexford et al., “Incremental consistent updates,” in Second Workshop on Hot Topics in Software Defined Networking (HotSDN), Hong Kong, China, 2013, pp. 49-54. doi: 10.1145/2491185.2491191.

Optimization Framework for Minimizing Rule Update Latency in SDN Switches

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 11

References 28

Related Articles 15

Recommended Articles

Metrics

[1]	JIA Min, SHU Yuejie, GUO Qing, GAO Zihe, XIE Suofei. DDoS Attack Detection Method for Space-Based Network Based on SDN Architecture [J]. ZTE Communications, 2020, 18(4): 18-25.
[2]	WU Hequan. Ten Reflections on 5G [J]. ZTE Communications, 2020, 18(1): 1-4.
[3]	BAI Jiasong, ZHANG Menghao, BI Jun. Survey of Attacks and Countermeasures for SDN [J]. ZTE Communications, 2018, 16(4): 3-8.
[4]	ZHANG Yunyong, XU Lei, TAO Ye. SDN Based Security Services [J]. ZTE Communications, 2018, 16(4): 9-14.
[5]	XU Xiaoqiong, YU Hongfang, YANG Kun. DDoS Attack in Software Defined Networks: A Survey [J]. ZTE Communications, 2017, 15(3): 13-19.
[6]	LIAO Lingxia, Victor C. M. Leung, LAI Chin-Feng. Evolutionary Algorithms in Software Defined Networks: Techniques, Applications, and Issues [J]. ZTE Communications, 2017, 15(3): 20-36.
[7]	WANG Yangyang, BI Jun. Survey of Mechanisms for Inter-Domain SDN [J]. ZTE Communications, 2017, 15(3): 8-12.
[8]	DONG Baihong, WU Weigang, YANG Zhiwei, LI Junjie. Software Defined Networking Based On-Demand Routing Protocol in Vehicle Ad-Hoc Networks [J]. ZTE Communications, 2017, 15(2): 11-18.
[9]	Zhi Liu, Xiang Wang, and Jun Li. From CIA to PDR:A Top-Down Survey of SDN Security for Cloud DCN [J]. ZTE Communications, 2016, 14(1): 54-60.
[10]	Qinghua Shen, Xuemin (Sherman) Shen, Tom H. Luan, and Jing Liu. MAC Layer Resource Allocation forWireless Body Area Networks [J]. ZTE Communications, 2014, 12(3): 13-21.
[11]	M. Boucadair and C. Jacquenet. Service Parameter Exposure and Dynamic Service Negotiation in SDN Environments [J]. ZTE Communications, 2014, 12(2): 8-17.
[12]	Xiongyan Tang, Pei Zhang, and Chang Cao. SDN-Based Broadband Network for Cloud Services [J]. ZTE Communications, 2014, 12(2): 18-22.
[13]	Jiandong Li, Peng Liu, and Hongyan Li. Software-Defined Cellular Mobile Network Solutions [J]. ZTE Communications, 2014, 12(2): 28-33.
[14]	Lianming Zhang, Jia Liu, and Kun Yang. VirtualizedWireless SDNs: Modelling Delay Through the Use of Stochastic Network Calculus [J]. ZTE Communications, 2014, 12(2): 50-56.
[15]	Wen Gao, Xuyan Li, Boyang Zhou, and Chunming Wu. Load Balancing Fat-Tree on Long-Lived Flows: Avoiding Congestion in a Data Center Network [J]. ZTE Communications, 2014, 12(2): 57-62.