ZTE Communications ›› 2018, Vol. 16 ›› Issue (4): 15-29.DOI: 10.19729/j.cnki.1673-5188.2018.04.004
-
收稿日期:2018-07-17出版日期:2018-07-17发布日期:2018-10-25
Optimization Framework for Minimizing Rule Update Latency in SDN Switches
CHEN Yan1,2, WEN Xitao3, LENG Xue1, YANG Bo4, Li Erran Li5, ZHENG Peng6, HU Chengchen6
- 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-17Online:2018-07-17Published: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)
引用本文
. [J]. ZTE Communications, 2018, 16(4): 15-29.
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.
Figure 1. Overview of RuleTris optimization framework.
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 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.
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.
Example 2 of dependency construction in parallel composition: equivalent rule reduction. Figure 4.
Figure 5. Example of sequential composition.
Figure 5. Example of sequential composition.
Figure 6. Resolving mega dependency relations.
Figure 6. Resolving mega dependency relations.
Figure 7. Example of priority composition.
Figure 7. Example of priority composition.
Figure 8. Example of TCAM move optimization.
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 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 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.
Figure 11. Rule update overhead of single rule swaps with CacheFlow. Results are from hardware experiments.
| [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. |
| No related articles found! |
| 阅读次数 | ||||||
|
全文 |
|
|||||
|
摘要 |
|
|||||