A method of implementing packet-processing systems whose input-output behavior is described with an algorithmic policy (AP), comprising the following steps:
- defining, by a user, an AP program implementing a packet-processing function, wherein the AP program is written in a Turing-complete and datapath-oblivious language having no specialized datapath operations comprising flow table lookups and flow table updates, and wherein the program supports complex data structures, has per-packet-scoped variables and has inter-packet state variables;
- performing, by a compiler, the steps of:
- translating the AP program into a linear intermediate representation (IR) consisting of conditional and unconditional lump instructions, read and write instructions on input, output, per-packet-scoped and inter-packet state variables, and arithmetic instructions, the linear IR having no declarations of table pipeline design and no flow table operations;
- identifying a plurality of compact-mappable statements in the IR, where each compact-mappable statement falls into one of three categories consisting of:
- a state variable table lookup, a Boolean expression, and flow table-compatible arithmetic;
- analyzing the linear IR to identify a set of regions, the identifying including, for each region, selecting a region entry instruction that begins the region, wherein each region consists of the instructions starting from the region's entry instruction without traversing another region's entry instruction, and the selections are based on the identified compact-mappable statements and ensure that no possible execution of the linear IR can result in a region entry instruction being executed more than once;
- assigning a datapath resister to each per packet-scoped variable in the linear IR;
- and producing a synthesized table pipeline design comprising definitions of multiple flow tables and control flow amongst the multiple flow tables, wherein there is a respective flow table produced for each region and the match attributes for a region's flow table consist of the packet attributes in the inputs of the region and the datapath registers in the inputs of the region;
- performing, by a runtime controller, the steps of:
- receiving the synthesized table pipeline design and the AP program;
- establishing a communication session with a datapath component using a target-specific protocol;
- storing current values for state variables of the AP program, wherein the current values are continuously updated as the datapath component processes packets;
- initially, and in response to changes in the values of state variables and in response to observations of packet arrivals at the specific datapath component, populating the multiple flow tables with rule entries based on the stored current values, wherein the entries for each region's flow table simulate the effect of some or all possible executions of the instructions of the region, wherein for each flow table entry and each possible packet attribute that can be processed by that flow table entry, there is at least one possible execution of the region in which at the start of execution of the region entry instruction the values of the region's input variables equal the values of the packet's input attributes;
- and
- in response to the populating, translating the populated flow tables of the synthesized table pipeline design into a target-specific table design for the datapath component and configuring the data path component with the translated table design;
- and
- processing packets via the datapath component in accordance with the rules of the translated table design, wherein the datapath component processes packets with the same outcomes as would be computed by the AP program if executed on the packet with the state variables taking their current values.