Research On Optimal Placement Strategies For Forwarding Table Entries Based On Programmable Switches

Programmable switches are widely used in various fields such as load balancing,network measurement,distributed computing,and network function virtualization.High-level programming languages,such as P4,are emerging to describe how packets are handled by programmable switches.An important step in deploying a P4 program to a programmable switch is resource mapping,which consists of two parts:placing the packet header fields in the P4 program into the packet header vector of the programmable switch,and placing the forwarding table entries into the pipeline stage of the programmable switch.However,as the complexity of packet processing procedures increases in response to evolving business scenarios,the performance of the resource mapping algorithm faces significant challenges.This paper focuses on optimizing the placement strategies for forwarding table entries based on programmable switches and divides this research into two sub-problems,and the main contributions and innovations are as follows.(1)To address the optimal placement problem for packet header fields,this paper defines a parse graph to describe the whole process of packet header fields parsing,and designs an optimal strategy to maximize the packet header vector utilization based on the 0-1 planning algorithm,and also designs a BestWidthFit algorithm to obtain a feasible solution.(2)To address the optimal placement problem for forwarding table entries,this paper defines a table dependency graph to describe the attributes of each forwarding table and the control flow between forwarding tables.An integer programming-based algorithm is designed to solve the optimal strategies under three different objectives:optimal stage occupation,optimal table lookup delay,and optimal Gini coefficient.A FirstFit algorithm and a BestFit algorithm are also designed to obtain feasible solution policies.(3)The performance and resource consumption of the algorithms are evaluated under three realistic packet processing scenarios.The results demonstrate that the strategies based on both 0-1 planning algorithm and the integer planning algorithm can obtain optimal solutions under different objectives,while the proposed heuristics can obtain feasible solutions.The optimal solution can improve packet header vector utilization by up to 2.56%,reduce the number of occupied stages by 20%,reduce the table lookup delay by 37.21%,and reduce the Gini coefficient by 91.63%compared to the feasible solution.Moreover,this paper investigates the impact of changes in the number of stages and the minimum resource allocation unit on the algorithm’s performance,providing feasible ideas to improve deployability.