Static Analysis on Programmable Data Plane: Towards Network Switch Parallelization

Abstract

Flexible and parallel packet processing is crucial for network switches to support various network services in high speed. While programmable data plane allows the flexible packet processing, lack of data dependence analysis on data plane programs limits parallelization of the packet processing. This thesis proposes static analysis and parallelization methods for the programmable data plane. The proposed analysis analyzes data dependence among packet processing tables, and finds pairs of data-independent tables. Furthermore, the proposed parallelization parallelizes the data-independent tables in full and staggered manners. This thesis evaluates the analysis and the parallelization on 14 sample P4_16 programs. The analysis finds 16 data-independent pairs among 37 tables, and the simulation of the parallelization reduces the number of stages in pipelines by 15.4%. This thesis will be useful to reduce latency of programmable network switches, and provide opportunities of parallelization and compiler optimizations.

빠르고 유연한 패킷 프로세싱은 다양한 네트워크 서비스를 빠른 속도로 제공하는 네트워크 스위치에 중요하다. 프로그래머블 데이터 평면은 패킷 프로세서의 유연성을 제공하지만, 데이터 평면 프로그램에 대한 데이터 의존성 분석이 없어 저지연성을 위한 병렬화 및 최적화를 데이터 평면 프로그램에 적용할 수 없다. 본 연구는 프로그래머블 데이터 평면에 대한 정적 분석과 병렬화를 제안한다. 본 연구의 정적 분석은 패킷 프로세싱 테이블 기능의 사용-정의와 테이블 간의 데이터 의존 관계를 분석하고, 본 연구의 병렬화는 데이터 의존 관계가 없는 테이블을 병렬화한다. 본 연구는 14개의 P4_16 샘플 프로그램에 정적 분석 및 병렬화를 적용하였고, 그 결과로 정적 분석은 37개의 테이블 중에서 7쌍의 테이블 단위 병렬화가 가능한 테이블과 9쌍의 키 매칭 단위 병렬화가 가능한 테이블을 찾아내었다. 또한 병렬화 시뮬레이션은 파이프 라인의 스테이지 개수를 기하평균 15.4% 줄였다. 본 연구는 프로그래머블 네트워크 스위치의 응답 시간을 줄이고 병렬화 및 컴파일러 최적화 기회를 제공하는 데 유용하다.