Data compression algorithms for flow tables in network processor RuNPU

Данная статья посвящена проблемам классификации пакетов в архитектуре сетевого процессорного устройства (СПУ) без выделенного ассоциативного устройства. Под классификацией мы понимаем процесс идентификации пакета по его заголовку. На этапе классификации требуется реализация структур данных для хранения таблиц потоков. В данной работе рассматривается СПУ без адресуемой памяти, а таблицы потоков представляются в виде программы на языке ассемблера СПУ. Для перевода таблиц потоков в программу на языке ассемблера используется транслятор таблиц потоков. Необходимость реализации алгоритмов сжатия данных в трансляторе таблиц потоков обуславливается тем, что современные таблицы потоков могут занимать память объёмом до десятков мегабайт. В настоящей статье рассматриваются следующие алгоритмы сжатия данных: алгоритм оптимального кэширования, рекурсивного отсечения и общие алгоритмы сжатия данных. Оценка реализованных алгоритмов сжатия данных проводилась на имитационной модели СПУ.