Open AccessData compression algorithms for flow tables in Network Processor RuNPU
Author(s) -
Nikita Igorevitch Nikiforov,
Dmitry Volkanov
Publication year - 2021
Publication title -
trudy instituta sistemnogo programmirovaniâ ran/trudy instituta sistemnogo programmirovaniâ
Language(s) - English
Resource type - Journals
eISSN - 2220-6426
pISSN - 2079-8156
DOI - 10.15514/ispras-2021-33(4)-6
Subject(s) - computer science , header , data compression , table (database) , data flow diagram , algorithm , process (computing) , flow network , parallel computing , associative property , data structure , theoretical computer science , programming language , data mining , database , computer network , mathematical optimization , mathematics , pure mathematics
This paper addresses the problem of packet classification within a network processor (NP) architecture without the separate associative device. By the classification, we mean the process of identifying a packet by its header. The classification stage requires the implementation of data structures to store the flow tables. In our work, we consider the NP without the associative memory. Flow tables are represented by an assembly language program in the NP. For translating flow tables into assembly language programs, a tables translator was used. The main reason for implementing data compression algorithms in a flow tables translator is that modern flow tables can take up to tens of megabytes. In this paper, we describe the following data compression algorithms: Optimal rule caching, recursive end-point cutting and common data compression algorithms. An evaluation of the implemented data compression algorithms was performed on a simulation model of the NP.