MSSA: Constant Time State Search through Multi-Scope State Area
Source abstract
Abstract
In the stateful data plane, the switch can record the state and forward packets based on the local state. This approach makes it possible to integrate complex network applications into the data plane, thus reducing the amount of communication required between the switch and the controller. However, due to the time it takes to look up the state for packets, packet-forwarding latency has increased. With increased network traffic, a large number of states may be recorded in the switch, and the problem of increased packet-forwarding latency caused by the lookup state becomes more serious. In this paper, we propose the multi-scope state area (MSSA) for recording state inside the switch, which can achieve a fixed-time state lookup in a large-scale state. MSSA divides the state sharing scope by associating with the switch’s multiple match–action tables, and the shared scope is used to determine the state area for recording state. When processing a packet, the state required will only be in a limited number of states that are recorded in a few state areas. We implemented a prototype pipeline that supports MSSA based on Intel’s DPDK framework and investigated the effect of state type, number, location, and comparison method on state search/insertion time. The results show that the cost of MSSA search state is constant, regardless of the number of states, and MSSA has a high space utilization rate.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Software-Defined Networks and 5G · Network Traffic and Congestion Control · Software System Performance and Reliability
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
The Institute of Acoustics of the Chinese Academy of Sciences, University of Chinese Academy of Sciences, Beijing 100190, China
References (46)
Show source-provided references
1. Congestion control for high bandwidth-delay product networks10.1145/964725.633035 ↗
2. Tai, C.-H., Zhu, J., and Dukkipati, N. (2008, January 13–18). Making large scale deployment of RCP practical for real networks. Proceedings of the IEEE INFOCOM 2008—The 27th Conference on Computer Communications, Phoenix, AZ, USA.10.1109/INFOCOM.2008.285 ↗
3. Finishing flows quickly with preemptive scheduling10.1145/2377677.2377710 ↗
4. Alizadeh, M., Greenberg, A., Maltz, D.A., Padhye, J., Patel, P., Prabhakar, B., Sengupta, S., and Sridharan, M. (September, January 30). Data center tcp (dctcp). Proceedings of the ACM SIGCOMM 2010 Conference, New York, NY, USA.10.1145/1851182.1851192 ↗
5. Sivaraman, A., Subramanian, S., Agrawal, A., Chole, S., Chuang, S.-T., Edsall, T., Alizadeh, M., Katti, S., McKeown, N., and Balakrishnan, H. (2015, January 16–17). Towards programmable packet scheduling. Proceedings of the 14th ACM Workshop on Hot Topics in Networks, Philadelphia, PA, USA.10.1145/2834050.2834106 ↗
6. Yu, M., Jose, L., and Miao, R. (2013, January 2–5). Software Defined Traffic Measurement with OpenSketch. Proceedings of the 10th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 13), Lombard, IL, USA.
7. New directions in traffic measurement and accounting: Focusing on the elephants, ignoring the mice10.1145/859716.859719 ↗
8. Estan, C., Varghese, G., and Fisk, M. (2003, January 27–29). Bitmap algorithms for counting active flows on high speed links. Proceedings of the 3rd ACM SIGCOMM Conference on Internet Measurement, Miami Beach, FL, USA.10.1145/948224.948225 ↗
9. The BLUE active queue management algorithms10.1109/TNET.2002.801399 ↗
10. Random Early Detection Gateways for Congestion Avoidance10.1109/90.251892 ↗
11. An adaptive virtual queue (AVQ) algorithm for active queue management10.1109/TNET.2004.826291 ↗
12. Controlling queue delay10.1145/2209249.2209264 ↗
13. Pan, R., Natarajan, P., Piglione, C., Prabhu, M.S., Subramanian, V., Baker, F., and VerSteeg, B. (2013, January 8–11). PIE: A lightweight control scheme to address the bufferbloat problem. Proceedings of the 2013 IEEE 14th International Conference on High Performance Switching and Routing (HPSR), Taipei, Taiwan.10.1109/HPSR.2013.6602305 ↗
14. Bilge, L., Kirda, E., Kruegel, C., and Balduzzi, M. (2011, January 6–9). EXPOSURE: Finding Malicious Domains Using Passive DNS Analysis. Proceedings of the Network and Distributed System Security Symposium, NDSS 2011, San Diego, CA, USA.
15. CONGA: Distributed congestion-aware load balancing for datacenters10.1145/2740070.2626316 ↗
16. Barbette, T., Tang, C., Yao, H., Kostić, D., Maguire, G.Q., Papadimitratos, P., and Chiesa, M. (2020, January 25–27). A high-speed load-balancer design with guaranteed per-connection-consistency. Proceedings of the 17th USENIX Symposium Networked Systems Design Implementation, NSDI 2020, Santa Clara, CA, USA.
17. Miao, R., Zeng, H., Kim, C., Lee, J., and Yu, M. (2017, January 21–25). Silkroad: Making stateful layer-4 load balancing fast and cheap using switching asics. Proceedings of the SIGCOMM 2017 ACM Special Interest Group Data Communication, Los Angeles, CA, USA.10.1145/3098822.3098824 ↗
18. Katta, N., Hira, M., Kim, C., Sivaraman, A., and Rexford, J. (2016, January 14–15). HULA: Scalable load balancing using programmable data planes. Proceedings of the SOSR ′16: Symposium on SDN Research, Santa Clara, CA, USA.10.1145/2890955.2890968 ↗
19. Sivaraman, A., Cheung, A., Budiu, M., Kim, C., Alizadeh, M., Balakrishnan, H., Varghese, G., McKeown, N., and Licking, S. (2016, January 22–26). Packet transactions: High-level programming for line-rate switches. Proceedings of the SIGCOMM 2016—2016 ACM Conference of the ACM Special Interest Group on Data Communication, Florianopolis, Brazil.10.1145/2934872.2934900 ↗
20. Feamster, N., and Rexford, J. (2018, January 16). Why (and how) networks should run themselves. Proceedings of the Applied Networking Research Workshop, Montreal, QC, Canada.10.1145/3232755.3234555 ↗
21. ZeroSDN: A Highly Flexible and Modular Architecture for Full-Range Distribution of Event-Based Network Control10.1109/TNSM.2018.2873886 ↗
22. A Survey on the Security of Stateful SDN Data Planes10.1109/COMST.2017.2689819 ↗
23. A survey on stateful data plane in software defined networks10.1016/j.comnet.2020.107597 ↗
24. Openstate: Programming platform-independent stateful openflow applications inside the switch10.1145/2602204.2602211 ↗
25. Bianchi, G., Bonola, M., Pontarelli, S., Sanvito, D., Capone, A., and Cascone, C. (2021, November 19). Open Packet Processor: A Programmable Architecture for Wire Speed Platform-Independent Stateful in-Network Processing. Available online: http://arxiv.org/abs/1605.01977.
26. Flow-level state transition as a new switch primitive for SDN10.1145/2740070.2631439 ↗
27. Zhu, S., Bi, J., Sun, C., Wu, C., and Hu, H. (2015, January 10–13). SDPA: Enhancing stateful forwarding for software-defined networking. Proceedings of the 2015 IEEE 23rd International Conference on Network Protocols (ICNP), San Francisco, CA, USA.10.1109/ICNP.2015.45 ↗
28. Pontarelli, S., Bifulco, R., Bonola, M., Cascone, C., Spaziani, M., Bruschi, V., and Huici, F. (2019, January 26–28). Flowblaze: Stateful packet processing in hardware. Proceedings of the 16th USENIX Symposium Networked Systems Design Implementation, NSDI 2019, Boston, MA, USA.
29. Alagar, V.S., and Periyasamy, K. (2011). Extended Finite State Machine. Specification of Software Systems, Springer.10.1007/978-0-85729-277-3 ↗
30. P4: Programming protocol-independent packet processors10.1145/2656877.2656890 ↗
31. Introduction to automata theory, languages, and computation10.1145/568438.568455 ↗
32. Cuckoo hashing10.1007/3-540-44676-1_10 ↗
33. Németh, F., Chiesa, M., and Rétvári, G. (2019, January 9–12). Normal forms for match-action programs. Proceedings of the 15th International Conference on Emerging Networking Experiments and Technologies, Orlando, FL, USA.10.1145/3359989.3365417 ↗
34. Jose, L., Yan, L., Varghese, G., and McKeown, N. (2015, January 4–6). Compiling packet programs to reconfigurable switches. Proceedings of the 12th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 15), Oakland, CA, USA.
35. (2021, November 04). OpenFlow v1.1. Open Networking Fundation. Available online: https://opennetworking.org/wp-content/uploads/2014/10/openflow-spec-v1.4.0.pdf.
36. Forwarding metamorphosis: Fast programmable match-action processing in hardware for SDN10.1145/2534169.2486011 ↗
37. (2021, November 04). Open vSwitch. Open Networking Fundation. Available online: https://www.openvswitch.org/.
38. Molnár, L., Pongrácz, G., Enyedi, G., Kis, Z.L., Csikor, L., Juhász, F., Kőrösi, A., and Rétvári, G. (2016, January 22–26). Dataplane specialization for high-performance OpenFlow software switching. Proceedings of the SIGCOMM 2016—2016 ACM Conference Special Interest Group on Data Communication, Florianopolis, Brazil.10.1145/2934872.2934887 ↗
39. (2021, November 04). “Tipsy: Telco Pipeline Benchmarking System”. Available online: https://github.com/hsnlab/tipsy.
40. Barbette, T., Soldani, C., and Mathy, L. (2015, January 7–8). Fast userspace packet processing. Proceedings of the ANCS 2015—11th 2015 ACM/IEEE Symposium on Architectures for Networking and Communications Systems, Oakland, CA, USA.10.1109/ANCS.2015.7110116 ↗
41. Han, S., Jang, K., Panda, A., Palkar, S., Han, D., and Ratnasamy, S. (2015). SoftNIC: A Software NIC to Augment Hardware, EECS Department, University of California. Tech. Rep. UCB/EECS-2015-155.
42. Panda, A., Han, S., Jang, K., Walls, M., Ratnasamy, S., and Shenker, S. (2016, January 2–4). NetBricks: Taking the V out of {NFV}. Proceedings of the 12th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 16), Savannah, GA, USA.
43. Bifulco, R., and Retvari, G. (2018, January 18–20). A survey on the programmable data plane: Abstractions, architectures, and open problems. Proceedings of the 2018 IEEE 19th International Conference on High Performance Switching and Routing (HPSR), Bucharest, Romania.10.1109/HPSR.2018.8850761 ↗
44. Hauser, F., Häberle, M., Merling, D., Lindner, S., Gurevich, V., Zeiger, F., Frank, R., and Menth, M. (2021, November 19). A Survey on Data Plane Programming with P4: Fundamentals, Advances, and Applied Research. Available online: http://arxiv.org/abs/2101.10632.
45. Jing, L., Chen, X., and Wang, J. (2021). Design and Implementation of Programmable Data Plane Supporting Multiple Data Types. Electronics, 10.10.3390/electronics10212639 ↗
46. (2021, November 16). “Cuckoo-hash”. Available online: https://github.com/kroki/Cuckoo-hash.