An Approach to the Translation of Software-Defined Network Switch Flow Table into Network Processing Unit Assembly Language
https://doi.org/10.15514/ISPRAS-2020-32(3)-7
Abstract
This paper considers the OpenFlow 1.3 switch based on a programmable network processing unit (NPU). OpenFlow switch performs flow entry lookup in a flow table by the values of packet header fields to determine actions to apply to incoming packet (classification). In the considered NPU assembly language, lookup operation may be implemented on the basis of search trees. But these trees cannot be directly used for OpenFlow classification because of compared operands width limitation. In this paper, we propose flow table representation designed for easy translation into NPU search trees. Another goal was to create a compact program that fits in NPU memory. Another NPU limitation requires program updating after each flow table modification. Consequently, the switch must maintain the current flow table state to provide a fast NPU program update. We developed algorithms for incremental update of flow table representation (flow addition and removal). To evaluate the proposed flow table translation approach, a set of flow tables was translated into NPU assembly language using a simple algorithm (based on related work) and an improved algorithm (our proposal). Evaluation was performed on the NPU simulation model and showed that our approach effectively reduces program size.
About the Authors
Andrei Aleksandrovich MARKOBORODOV
Lomonosov Moscow State University
Russian Federation
Student of the faculty of the CMC
Russian Federation
Student of the faculty of the CMC
Julia Alexandrovna SKOBTSOVA
Lomonosov Moscow State University
Russian Federation
Specialist, faculty of the CMS, department of automation of computer systems, laboratory of computer systems
Russian Federation
Specialist, faculty of the CMS, department of automation of computer systems, laboratory of computer systems
Dmitry Yuryevitch VOLKANOV
Lomonosov Moscow State University
Russian Federation
Сandidate of physical and mathematical sciences, associate professor
Russian Federation
Сandidate of physical and mathematical sciences, associate professor
References
1. Open Networking Foundation. Software-defined networking: the new norm for networks. ONF white paper, 2012. Available at: https://www.opennetworking.org/images/stories/downloads/sdn-resources/white-papers/wp-sdn-newnorm.pdf.
2. Open Networking Foundation. OpenFlow switch specification version 1.3.0. 2012. Available at: https://www.opennetworking.org/wp-content/uploads/2014/10/openflow-spec-v1.3.0.pdf.
3. Giladi R. Network processors: architecture, programming, and implementation. Morgan Kaufmann, 2008, 736 p.
4. Orphanoudakis T., Perissakis S. Embedded multi-core processing for networking. In Embedded Multi-Core Systems, CRC Press, 2010, pp. 399–463.
5. Bifulco R., Rtvri G. A survey on the programmable data plane: abstractions, architectures, and open problems. In Proc. of the IEEE 19th International Conference on High Performance Switching and Routing (HPSR), 2018, pp. 1–7.
6. Taylor D., Turner J. Scalable packet classification using distributed crossproducting of field labels. In Proc. of the IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies, 2005, pp. 269-280.
7. Kekely M., Korenek J. Packet classification with limited memory resources. In Proc. of the Euromicro Conference on Digital System Design (DSD), 2017, pp. 179–183.
8. Bloom B. H. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, vol. 13, no. 7, 1970, pp. 422–426.
9. Gupta P., McKeown N. Classifying packets with hierarchical intelligent cuttings. IEEE Micro, 2000, vol. 20, no. 1, pp. 34–41.
10. Singh S., Baboescu F., Varghese G., Wang J. Packet classification using multidimensional cutting. In Proc. of the 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, 2003, pp. 213–224.
11. Qi X., Xu L., Yang B. Packet classification algorithms: from theory to practice. In Proc. of the IEEE International Conference on Computer Communications (IEEE INFOCOM), 2009, pp. 648–656.
12. Li W., Li X., Li H., Xie G. CutSplit: a decision-tree combining cutting and splitting for scalable packet classification. In Proc. of the IEEE International Conference on Computer Communications (IEEE INFOCOM), 2018, pp. 2645–2653.
Review
For citations:
MARKOBORODOV A.A., SKOBTSOVA J.A., VOLKANOV D.Yu. An Approach to the Translation of Software-Defined Network Switch Flow Table into Network Processing Unit Assembly Language. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2020;32(3):79-89. https://doi.org/10.15514/ISPRAS-2020-32(3)-7
Email this article 