POMP:Protocol Oblivious SDN Programming with Automatic Multi-Table Pipelining Chunhui He Xinyu Feng School of Computer Science and Technology State Key Laboratory for Novel Software Technology University of Science and Technology of China Nanjing University hchunhuiemail.ustc.edu.cn xyfengenju.edu.cn Abstract-SDN programming has been challenging because 2)to design flow table layout and forwarding pipelines for programmers have to not only implement the control logic,but new generation SDN to achieve compact flow tables also handle low-level details such as the generation of flow tables and efficient forwarding.As we explain in Sec.III, and the communication between the controller and switches.New generation of SDN with protocol oblivious forwarding and multi- different forwarding pipelines may generate flow tables table pipelining introduces even more low-level details to consider with significantly different sizes We propose POMP,the first SDN programming environment 3)to implement parsers for packets with new header fields supporting both protocol oblivious forwarding and automatic to fit in the underlying protocol oblivious forwarding multi-table pipelining.POMP applies the static taint analysis mechanism.For instance,one needs to generate the technique to automatically infer compact and efficient multi-table pipelines from a data-plane agnostic network policy written by (offset,length)tuples required by POF [2]to the programmer.The runtime system tracks the execution of the locate packet fields. network policy,and automatically generates table entries.POMP There have been many languages proposed to simplify also introduces a novel notion of dependent labels in the taint analysis,which,combined with the runtime information of the SDN programming,but none of them address all the prob- network policy,can further reduce the number of table entries. lems above.Languages such as NetKAT [6],NetCore [7] Like P4,POMP supports protocol-oblivious programming by and Maple [5]try to address the first problem,but they providing a network protocol specification language.Parsers of are designed for Openflow and do not support multi-table packets can be automatically generated based on the protocol pipelining and protocol-oblivious forwarding.P4 [1]provides specification.POMP supports two main emerging SDN platforms, POF and P4,therefore network policies written in POMP are a header specification language for protocol independence. portable over any switches supporting POF or P4. Programmers can write a specification of the header format, from which P4 generate parsers automatically.But P4 is I.INTRODUCTION more of a low-level switch configuration language,and is not Software-Defined Networking (SDN)is a network archi- suitable for high-level controller programming. tecture that decouples control and forwarding.Distributed We propose POMP,a high-level programming environ- switches are managed by a logically-centralized controller, ment to simplify SDN programming.Following the idea of which can be implemented by software through SDN pro- Maple [5],POMP provides a set of APIs and a runtime system. gramming. Programmers can use the APIs to describe the network policy OpenFlow is the first SDN standard,but it only supports a by writing an algorithmic sequential program with a high-level predefined fixed set of networking protocols,and allows only a centralized view of the network environment.This high-level fixed single flow table.New generation of SDN platforms [1], network policy is data-plane agnostic.It is the runtime system [2],[3],[4]offer two new flexible features at the data-plane, that tracks the execution of the network policy and generates i.e.multi-table pipelining and protocol-oblivious forwarding. fow table entries automatically.POMP also makes significant The former allows multiple flow tables on switches to form a extensions to the above ideas in Maple to support automatic forwarding pipeline,which can be customized by users.The multi-table pipelining and protocol oblivious programming. latter supports customized packets for new protocols. As far as we know,POMP is the first high-level programming SDN programming has been challenging because the pro- environment that solves all the aforementioned problems.Our grammer has to not only implement the network policy (i.e. work on POMP makes the following new contributions: the control logic),but also handle low-level data-plane details. Specifically,one faces the following challenges: We apply the static taint analysis technique [8]to anal- yse the network policy's dependence over the fields of 1)to manually translate high-level network policies to flow table entries.It is error-prone,and makes network packets.Based on the fine-grained dependence relation we automatically generate compact and efficient multi- policies hard to write and read [5]. table pipelines.The analysis and the pipeline generation Corresponding author:Xinyu Feng.This work is supported in part by grants from National Natural Science Foundation of China(NSFC)under Grant Nos. IThe name POMP highlights the two key features of our work,i.e.protocol- 61379039and61632005. oblivious programming and multi-table pipelining
POMP: Protocol Oblivious SDN Programming with Automatic Multi-Table Pipelining Chunhui He School of Computer Science and Technology University of Science and Technology of China hchunhui@mail.ustc.edu.cn Xinyu Feng State Key Laboratory for Novel Software Technology Nanjing University xyfeng@nju.edu.cn Abstract—SDN programming has been challenging because programmers have to not only implement the control logic, but also handle low-level details such as the generation of flow tables and the communication between the controller and switches. New generation of SDN with protocol oblivious forwarding and multitable pipelining introduces even more low-level details to consider. We propose POMP, the first SDN programming environment supporting both protocol oblivious forwarding and automatic multi-table pipelining. POMP applies the static taint analysis technique to automatically infer compact and efficient multi-table pipelines from a data-plane agnostic network policy written by the programmer. The runtime system tracks the execution of the network policy, and automatically generates table entries. POMP also introduces a novel notion of dependent labels in the taint analysis, which, combined with the runtime information of the network policy, can further reduce the number of table entries. Like P4, POMP supports protocol-oblivious programming by providing a network protocol specification language. Parsers of packets can be automatically generated based on the protocol specification. POMP supports two main emerging SDN platforms, POF and P4, therefore network policies written in POMP are portable over any switches supporting POF or P4. I. INTRODUCTION Software-Defined Networking (SDN) is a network architecture that decouples control and forwarding. Distributed switches are managed by a logically-centralized controller, which can be implemented by software through SDN programming. OpenFlow is the first SDN standard, but it only supports a predefined fixed set of networking protocols, and allows only a fixed single flow table. New generation of SDN platforms [1], [2], [3], [4] offer two new flexible features at the data-plane, i.e. multi-table pipelining and protocol-oblivious forwarding. The former allows multiple flow tables on switches to form a forwarding pipeline, which can be customized by users. The latter supports customized packets for new protocols. SDN programming has been challenging because the programmer has to not only implement the network policy (i.e. the control logic), but also handle low-level data-plane details. Specifically, one faces the following challenges: 1) to manually translate high-level network policies to flow table entries. It is error-prone, and makes network policies hard to write and read [5]. Corresponding author: Xinyu Feng. This work is supported in part by grants from National Natural Science Foundation of China (NSFC) under Grant Nos. 61379039 and 61632005. 2) to design flow table layout and forwarding pipelines for new generation SDN to achieve compact flow tables and efficient forwarding. As we explain in Sec. III, different forwarding pipelines may generate flow tables with significantly different sizes. 3) to implement parsers for packets with new header fields to fit in the underlying protocol oblivious forwarding mechanism. For instance, one needs to generate the (offset, length) tuples required by POF [2] to locate packet fields. There have been many languages proposed to simplify SDN programming, but none of them address all the problems above. Languages such as NetKAT [6], NetCore [7] and Maple [5] try to address the first problem, but they are designed for Openflow and do not support multi-table pipelining and protocol-oblivious forwarding. P4 [1] provides a header specification language for protocol independence. Programmers can write a specification of the header format, from which P4 generate parsers automatically. But P4 is more of a low-level switch configuration language, and is not suitable for high-level controller programming. We propose POMP, a high-level programming environment to simplify SDN programming. Following the idea of Maple [5], POMP provides a set of APIs and a runtime system. Programmers can use the APIs to describe the network policy by writing an algorithmic sequential program with a high-level centralized view of the network environment. This high-level network policy is data-plane agnostic. It is the runtime system that tracks the execution of the network policy and generates flow table entries automatically. POMP also makes significant extensions to the above ideas in Maple to support automatic multi-table pipelining and protocol oblivious programming.1 As far as we know, POMP is the first high-level programming environment that solves all the aforementioned problems. Our work on POMP makes the following new contributions: • We apply the static taint analysis technique [8] to analyse the network policy’s dependence over the fields of packets. Based on the fine-grained dependence relation we automatically generate compact and efficient multitable pipelines. The analysis and the pipeline generation 1The name POMP highlights the two key features of our work, i.e. protocoloblivious programming and multi-table pipelining
From programmers'point of view,f(pkt,env)is in- header spec. network policy f(pkt,env) Taint Analysis voked upon the arrival of every packet pkt in each data- Parser Gen API Calls plane switch.f also takes a centralized view of the network environment env.It calculates the routing path and returns Parser Runtime System Pipeline the port number to forward the packet.The return value can packet-In flow entries also be 0 or negative,which means to drop the packet or P4 Compiler Switch Abstraction Layer to broadcast it,respectively.f may also call POMP APIs to modify the global environment or to modify fields of packets. P4 protocol. POF protocol What really happens is that the controller (the runtime P4 Switch POF Switch system)invokes f(pkt,env)when it receives a PacketIn Fig.1.Structure of POMP message,and passes the packet to f.The runtime then monitors the execution of f and generates an execution trace, which records the sequence of API calls made by f to read is done statically before the deployment of the controller, or update packet header fields or the environment data.Based therefore it does not introduce any runtime overhead. on the dependence between actions and values of packet fields We extend the taint analysis with a novel notion of reflected in the trace,the runtime automatically generates flow dependent labels,which further refines the dependence table entries and install them on switches. relation and allows it to be conditional upon the if So far the ideas all come from Maple,but Maple does not statement branches taken at runtime.Combining the support multi-table pipelining and protocol-oblivious forward- dependent labels with the runtime execution traces of the ing.As we demonstrate in Sec.III,the dependence derived network policy,the runtime system can further reduce the by Maple from the execution trace is way too imprecise and number of flow table entries.Our experiments show that, leads to flow tables with O(n2)forwarding rules for learning for learning switches,POMP generates flow tables with switches with n hosts,even though O(n)rules are sufficient. up to 47x fewer table entries and being 137x faster than POMP introduces a static taint analysis phase to analyse the the traditional single flow table (as generated in Maple). code of f,from which it infers the fine-grained dependence Inspired by P4,POMP incorporates a packet header spec- between actions and packet fields.Based on the fine-grained ification language,with which programmers can specify dependence,it automatically generates a multi-table pipeline. the format of packet headers.Based on the specification The runtime takes the multi-table pipeline into account and we can automatically generate parsers for packets.This generates table entries accordingly. makes POMP a protocol oblivious programming environ- To support protocol-oblivious programming,we follow the ment.Our runtime system can support two main emerging ideas in P4 and ask programmers to provide a header format SDN platforms:POF and P4.It makes network policies specification written in a specification language.Then the written in our language portable over any SDN chipsets parser generator automatically generates parsers for packets. and software switches that support POF or P4. POMP supports both POF and P4.For POF,the runtime In the remaining part of the paper,we give a system queries the parser to map the string field names to the overview and introduce a running example in Sec.II.We (offset,length)tuples.For P4,the generated parser present the taint analysis and the pipeline generation in and forwarding pipeline are fed into the P4 compiler to configure the switch.We also introduce a switch abstraction Sec.III,and propose the dependent labels and the runtime generation of table entries in Sec.IV.We then introduce the layer,which accepts P4 or POF messages separately and then packet parsing for protocol oblivious programming in Sec.V. converts them into a uniform format for the runtime system We show evaluation results in Sec.VI.Finally we discuss B.Learning Switches:a running example related work in Sec.VII and conclude in Sec.VIII. We use learning switches to demonstrate how the system II.OVERVIEW works.It is also used as a running example to illustrate the key ideas in the following sections.As shown in Fig.1,our system In this section we first give an overview of the system takes as inputs a protocol specification and a network policy structure of POMP.Then we introduce learning switches as f,which are shown in Figs.2 and 3 respectively.(Ignore the a running example used in the following sections. comments in Fig.3,which shows the result of taint analysis and is explained in Sec.II). A.System structure The protocol specification describes the eth and ipv4 Figure 1 shows the system structure.Following Maple,protocols.Each is defined by a header block.For each POMP allows programmers to implement the network policy header block,there are the fields section that describes as an algorithmic sequential program with a centralized view the fields of the protocol,and the next section that describes of the network environment.The network policy is imple-the inner protocols.For example,the eth protocol has three mented as a function f(pkt,env).It is a C program with fields:48 bits dst,48 bits src and 16 bits type.Depending API calls of the POMP library. on the values of type,the protocol follows the eth is ipv4
Fig. 1. Structure of POMP is done statically before the deployment of the controller, therefore it does not introduce any runtime overhead. • We extend the taint analysis with a novel notion of dependent labels, which further refines the dependence relation and allows it to be conditional upon the if statement branches taken at runtime. Combining the dependent labels with the runtime execution traces of the network policy, the runtime system can further reduce the number of flow table entries. Our experiments show that, for learning switches, POMP generates flow tables with up to 47x fewer table entries and being 137x faster than the traditional single flow table (as generated in Maple). • Inspired by P4, POMP incorporates a packet header specification language, with which programmers can specify the format of packet headers. Based on the specification we can automatically generate parsers for packets. This makes POMP a protocol oblivious programming environment. Our runtime system can support two main emerging SDN platforms: POF and P4. It makes network policies written in our language portable over any SDN chipsets and software switches that support POF or P4. In the remaining part of the paper, we give a system overview and introduce a running example in Sec. II. We present the taint analysis and the pipeline generation in Sec. III, and propose the dependent labels and the runtime generation of table entries in Sec. IV. We then introduce the packet parsing for protocol oblivious programming in Sec. V. We show evaluation results in Sec. VI. Finally we discuss related work in Sec. VII and conclude in Sec. VIII. II. OVERVIEW In this section we first give an overview of the system structure of POMP. Then we introduce learning switches as a running example used in the following sections. A. System structure Figure 1 shows the system structure. Following Maple, POMP allows programmers to implement the network policy as an algorithmic sequential program with a centralized view of the network environment. The network policy is implemented as a function f(pkt, env). It is a C program with API calls of the POMP library. From programmers’ point of view, f(pkt, env) is invoked upon the arrival of every packet pkt in each dataplane switch. f also takes a centralized view of the network environment env. It calculates the routing path and returns the port number to forward the packet. The return value can also be 0 or negative, which means to drop the packet or to broadcast it, respectively. f may also call POMP APIs to modify the global environment or to modify fields of packets. What really happens is that the controller (the runtime system) invokes f(pkt, env) when it receives a PacketIn message, and passes the packet to f. The runtime then monitors the execution of f and generates an execution trace, which records the sequence of API calls made by f to read or update packet header fields or the environment data. Based on the dependence between actions and values of packet fields reflected in the trace, the runtime automatically generates flow table entries and install them on switches. So far the ideas all come from Maple, but Maple does not support multi-table pipelining and protocol-oblivious forwarding. As we demonstrate in Sec. III, the dependence derived by Maple from the execution trace is way too imprecise and leads to flow tables with O(n 2 ) forwarding rules for learning switches with n hosts, even though O(n) rules are sufficient. POMP introduces a static taint analysis phase to analyse the code of f, from which it infers the fine-grained dependence between actions and packet fields. Based on the fine-grained dependence, it automatically generates a multi-table pipeline. The runtime takes the multi-table pipeline into account and generates table entries accordingly. To support protocol-oblivious programming, we follow the ideas in P4 and ask programmers to provide a header format specification written in a specification language. Then the parser generator automatically generates parsers for packets. POMP supports both POF and P4. For POF, the runtime queries the parser to map the string field names to the (offset, length) tuples. For P4, the generated parser and forwarding pipeline are fed into the P4 compiler to configure the switch. We also introduce a switch abstraction layer, which accepts P4 or POF messages separately and then converts them into a uniform format for the runtime system. B. Learning Switches: a running example We use learning switches to demonstrate how the system works. It is also used as a running example to illustrate the key ideas in the following sections. As shown in Fig. 1, our system takes as inputs a protocol specification and a network policy f, which are shown in Figs. 2 and 3 respectively. (Ignore the comments in Fig. 3, which shows the result of taint analysis and is explained in Sec. III). The protocol specification describes the eth and ipv4 protocols. Each is defined by a header block. For each header block, there are the fields section that describes the fields of the protocol, and the next section that describes the inner protocols. For example, the eth protocol has three fields: 48 bits dst, 48 bits src and 16 bits type. Depending on the values of type, the protocol follows the eth is ipv4
header eth fields header ipv4 "inport")combination,which leads to a packet-in message dst 48; fields sending to the controller,so that the controller can update src 48; type 16; tt1:8; the environment mac2port (line 6 in Fig.3). But still we do not need to exhaustively enumerate all the next select (type)( combination of“src”and“dst”(leading to O(n2)forwarding case 0x0800:ipv4; rules).Learning the topology needs to match "inport"and case 0x86dd:ipv6; "“src”but not“dst”,and the forwarding needs to match“dst" (and“ttl”for IPv44 packets)but not“src”.Each of the two start eth; functionalities requires O(n)rules respectively.Therefore we Fig.2.Header specification could greatly reduce the number of forwarding rules (i.e. flow table entries)if we can have multiple flow tables,each corresponds to one independent functionality only or ipv6.The start clause at the end indicates the name of the outmost protocol. To achieve this,we not only need the support of multi-table The network policy f is written in C with POMP primitives. forwarding pipelines on switches (which is available in the As shown in Fig.3,the f for learning switches first reads emerging SDN platforms),but also need to have more fine- the ingress port,the source address,the destination address grained dependence relation between the functionality and the packet header fields.Since Maple only tracks the execution and the type of the packet.It learns the source host,and remembers the ingress port in mac2port (line 6).Then it trace of f,it lets an action (e.g.the return of the value r looks up mac2port to find the port for destination (line 7) at line 23)depend on all earlier actions that read packets or and set the return value to the port number (line 9).If the environments (e.g.the read of "src"at line 4).This is overly result is 0,it means the port is unknown,so we set the return conservative and leads to imprecise dependence relation. value to negative (line 11)to broadcast the packet. As one of the major contributions of the work,we use For IPv4 packets,we also decrease thet(line 17)if it static taint analysis [to infer more fine-grained dependence is greater than 0.Otherwise we drop the packet by setting the relation.The analysis takes the function f as input and tracks return value to 0. the information flow from packets and environments to the Data-plane agnostic and protocol-oblivious network policy. actions that perform the functionalities (e.g.mod env (at Note that f does not describe forwarding pipelines and for- line 6),without actually running f.The result can be used to warding rules,which are automatically generated.Also it uses design multi-table forwarding pipelines. strings as field names to access packet header fields (e.g., read packet (pkt,"eth.dst")).Parsing is done au- A.Taint analysis tomatically to map field names to their offsets in packets. Taint analysis computes the information flow from sources III.PIPELINE GENERATION to sinks.In our settings,the sources are the ingress port, Following the idea of Maple by recording the execution packets'header fields,and environments.The sinks are the traces of f,we can derive the actions and their dependence operations that output information,including the return of over packet header fields,and generate a single flow table. routing decisions,and the update of packets and environments. Fig.4 shows the flow table for learning switches. Since all accesses of packets and environments must be made The match fields of the flow table come from through POMP APIs,they can be easily recognized in the read inport (and read packet (in the network code.In Table I,we list the APIs that obtain information policy f.There are two possible actions of the flow table.from the sources.We also assign labels to identify each The first is to modify the ttl field.and then to forward the source.Note that for test_equal(pkt,fld,v)(which packet.The second is to drop the packet. tests the equality between fld and v),we label the source However,such a flow table may cause unnecessarily large with test(fld)instead of fld.The latter means we need number of table entries.To see the problem,suppose there the exact value of the field fld,while the former means are n hosts in the network.When a host h;sends a packet we only care about certain property of fld.They indicate to hj,the controller has to install a flow entry that matches different number of entries in the flow table.Distinguish- “inport'”(represented as“inp”in the table),“src”and“dst”.ing them allows us to generate more compact forwarding This results in O(n)entries of the flow table. pipelines,which we explain below.The sinks are the API calls One may have noticed that,since the switch forwards of mod packet (pkt,fld,v)and mod_env(env, packets only based on the destination address,there is no var,key,v),and also the command return r. need to enumerate all combinations of"src"and "dst".An The process of the taint analysis propagates labels from apparent optimization might be omitting the match fields"src" sources to sinks.Our algorithm is mostly standard [8]except and"inport"by filling in*"in the table.But this is incorrect the extension with dependent labels.Here we only introduce because we do need to match the exact values of"src"and the rough idea of taint analysis based on the learning switches "inport"-we rely on a mismatch to detect a new ("src",example.Dependent labels are introduced later in Sec.IV
header eth { fields { dst : 48; src : 48; type : 16; } next select (type) { case 0x0800: ipv4; case 0x86dd: ipv6; ... } } header ipv4 { fields { ... ttl : 8; ... } ... } start eth; Fig. 2. Header specification or ipv6. The start clause at the end indicates the name of the outmost protocol. The network policy f is written in C with POMP primitives. As shown in Fig. 3, the f for learning switches first reads the ingress port, the source address, the destination address and the type of the packet. It learns the source host, and remembers the ingress port in mac2port (line 6). Then it looks up mac2port to find the port for destination (line 7) and set the return value to the port number (line 9). If the result is 0, it means the port is unknown, so we set the return value to negative (line 11) to broadcast the packet. For IPv4 packets, we also decrease the ttl (line 17) if it is greater than 0. Otherwise we drop the packet by setting the return value to 0. Data-plane agnostic and protocol-oblivious network policy. Note that f does not describe forwarding pipelines and forwarding rules, which are automatically generated. Also it uses strings as field names to access packet header fields (e.g., read_packet(pkt, "eth.dst")). Parsing is done automatically to map field names to their offsets in packets. III. PIPELINE GENERATION Following the idea of Maple by recording the execution traces of f, we can derive the actions and their dependence over packet header fields, and generate a single flow table. Fig. 4 shows the flow table for learning switches. The match fields of the flow table come from read_inport() and read_packet() in the network policy f. There are two possible actions of the flow table. The first is to modify the ttl field, and then to forward the packet. The second is to drop the packet. However, such a flow table may cause unnecessarily large number of table entries. To see the problem, suppose there are n hosts in the network. When a host hi sends a packet to hj , the controller has to install a flow entry that matches “inport” (represented as “in p” in the table), “src” and “dst”. This results in O(n 2 ) entries of the flow table. One may have noticed that, since the switch forwards packets only based on the destination address, there is no need to enumerate all combinations of “src” and “dst”. An apparent optimization might be omitting the match fields “src” and “inport” by filling in “*” in the table. But this is incorrect because we do need to match the exact values of “src” and “inport” — we rely on a mismatch to detect a new (“src”, “inport”) combination, which leads to a packet-in message sending to the controller, so that the controller can update the environment mac2port (line 6 in Fig. 3). But still we do not need to exhaustively enumerate all the combination of “src” and “dst” (leading to O(n 2 ) forwarding rules). Learning the topology needs to match “inport” and “src” but not “dst”, and the forwarding needs to match “dst” (and “ttl” for IPv4 packets) but not “src”. Each of the two functionalities requires O(n) rules respectively. Therefore we could greatly reduce the number of forwarding rules (i.e. flow table entries) if we can have multiple flow tables, each corresponds to one independent functionality only. To achieve this, we not only need the support of multi-table forwarding pipelines on switches (which is available in the emerging SDN platforms), but also need to have more finegrained dependence relation between the functionality and the packet header fields. Since Maple only tracks the execution trace of f, it lets an action (e.g. the return of the value r at line 23) depend on all earlier actions that read packets or environments (e.g. the read of “src” at line 4). This is overly conservative and leads to imprecise dependence relation. As one of the major contributions of the work, we use static taint analysis [8] to infer more fine-grained dependence relation. The analysis takes the function f as input and tracks the information flow from packets and environments to the actions that perform the functionalities (e.g. mod_env() at line 6), without actually running f. The result can be used to design multi-table forwarding pipelines. A. Taint analysis Taint analysis computes the information flow from sources to sinks. In our settings, the sources are the ingress port, packets’ header fields, and environments. The sinks are the operations that output information, including the return of routing decisions, and the update of packets and environments. Since all accesses of packets and environments must be made through POMP APIs, they can be easily recognized in the code. In Table I, we list the APIs that obtain information from the sources. We also assign labels to identify each source. Note that for test_equal(pkt, fld, v) (which tests the equality between fld and v), we label the source with test(fld) instead of fld. The latter means we need the exact value of the field fld, while the former means we only care about certain property of fld. They indicate different number of entries in the flow table. Distinguishing them allows us to generate more compact forwarding pipelines, which we explain below. The sinks are the API calls of mod_packet(pkt, fld, v) and mod_env(env, var, key, v), and also the command return r. The process of the taint analysis propagates labels from sources to sinks. Our algorithm is mostly standard [8] except the extension with dependent labels. Here we only introduce the rough idea of taint analysis based on the learning switches example. Dependent labels are introduced later in Sec. IV
if(pkt,env)【 2 inport read_inport (pkt); //inport<-{inport】 dst read_packet(pkt,"eth.dst"); //dst<-(dst】 src read packet (pkt,"eth.src"); /src <-(src) mod env(env,"mac2port",src,inport); /mod enve6 <-(src,inport) port read_env(env,"mac2port",dst); port <-(dst,env(mac2port)) if(port！=0){ /branche8 <-(dst,env(mac2port)) 9 上=port; /r <-(dst,env(mac2port)) else r =-inport; //r <-{dst,env(mac2port),inport) //r <-(dst,env(mac2port),inport) 14 if(test_equal(pkt,"eth.type",0x800))( /branche14 <-(test (type)) ttl read_packet (pkt,"eth.ipv4.ttl"); /ttl <-(test(type),ttl) if (!test_equal(pkt,"eth.ipv4.ttl",1)){//branche16 <-(test(ttl)) 17 mod_packet (pkt,"eth.ipv4.ttl",ttl -1);//mod_packete17 <-(test(type),ttl) 】else{ r=0: //r <(test (type),test(ttl)) 21 22 //r<-{dst, env(mac2port),inport,test (type),test(ttl)} return ri /return@23 <-(dst,env(mac2port),inport,test(type),test(ttl)) 24 Fig.3.Taint analysis for learning switches in POMP priority in_p src dst type ttl action merge the results.As an example,the label set for r at line 13 2 h2 hi 0x800 64 MOD FLD (tt1,63); is the union of the sets at lines 9 and 11 respectively.When OUT[1] 0x800 MOD FLD(ttl,63); analysing each branch,we also need to consider the label set OUT[2] of the boolean branch condition of the if statements.because h3 0x800 DROP of the implicit information flow caused by control dependence. Therefore the label set of variable r is the union of the label Fig.4.Flow table layout of learning switches sets of both inport and port. TABLE I B.Xgraphs and Pipeline Generation SOURCES AND SINKS Although the taint analysis generates dependence for each Source Label sink (at lines 6,17 and 23),we also need to maintain the read inport (pkt) inport control flow to decide the order of these actions in the read_packet(pkt,fld) fld forwarding pipeline.We let the taint analysis generate Xgraph, test_equal(pkt,fld,v) test(fld) read_env(env,var,key) env(var) an intermediate representation of both the control flow and (a)Sources and Labels the dependence (i.e.label sets).The Xgraph for our example Sink is shown in Fig.5.There are two types of nodes.The mod packet (pkt,fld,v) mod_env(env,var,key,v) square node represents an action corresponding to a sink. return r It records the name and the line number of the action (e.g. (b)Sinks mod_enve6 in the first node),and the corresponding label set (e.g.{src,inport in the first node).Each diamond node represents a branch.It records the label set of the branch Comments in Fig.3 demonstrates how we trace the infor- expression and the line number of the branch.The edges in mation flow.Every variable is assigned to a set of labels, the Xgraph represent the control flow. recording the information flowing into the variable Given the Xgraph,we can do a"node to node"translation For assignment statements,the label set of the variable on to generate the multi-stage forwarding pipeline.Fig.6 shows the left hand side is the union of the label sets of the variables the pipeline generated from Fig.5.For each square node in on the right and the set of sources accessed.For example, the Xgraph,we generate a flow table for the functionality.The the variable dst is assigned the label set fdst at line 7 match fields of the flow table are the packet header fields and (packet field prefix omitted in the label set to avoid clutter).the ingress port in the dependence set of the corresponding and port at line 4 is assigned {env(mac2port),dst}.Xgraph node.The action is translated from the corresponding which is obtained by fenv (mac2port)}Ulabel(dst). controller action in the Xgraph node,but not necessarily The label set of a sink is the union of the label set of its the same.For example,we translate the controller action arguments.The modenv (at line 6 is a sink.Its label set mod_env (in Fig.5 into a [GOTO]action,which does is the union of the label sets of src and inport. nothing and jumps to the next flow table on the pipeline.As For if statements,we analyse both branches and then we explained before,the only effect of this table is to generate
1 f(pkt, env) { 2 inport = read_inport(pkt); // inport <- {inport} 3 dst = read_packet(pkt, "eth.dst"); // dst <- {dst} 4 src = read_packet(pkt, "eth.src"); // src <- {src} 5 6 mod_env(env, "mac2port", src, inport); // mod_env@6 <- {src, inport} 7 port = read_env(env, "mac2port", dst); // port <- {dst, env(mac2port)} 8 if (port != 0) { // branch@8 <- {dst, env(mac2port)} 9 r = port; // r <- {dst, env(mac2port)} 10 } else { 11 r = -inport; // r <- {dst, env(mac2port), inport} 12 } 13 // r <- {dst, env(mac2port), inport} 14 if(test_equal(pkt, "eth.type", 0x800)) { // branch@14 <- {test(type)} 15 ttl = read_packet(pkt, "eth.ipv4.ttl"); // ttl <- {test(type), ttl} 16 if (!test_equal(pkt, "eth.ipv4.ttl", 1)) { // branch@16 <- {test(ttl)} 17 mod_packet(pkt, "eth.ipv4.ttl", ttl - 1); // mod_packet@17 <- {test(type), ttl} 18 } else { 19 r = 0; // r <- {test(type), test(ttl)} 20 } 21 } 22 // r <- {dst, env(mac2port), inport, test(type), test(ttl)} 23 return r; // return@23 <- {dst, env(mac2port), inport, test(type), test(ttl)} 24 } Fig. 3. Taint analysis for learning switches in POMP priority in p src dst type ttl action 1 2 h2 h1 0x800 64 MOD_FLD(ttl,63); OUT[1] 1 1 h1 h2 0x800 64 MOD_FLD(ttl,63); OUT[2] 1 1 h1 h3 0x800 1 DROP ... ... ... ... ... ... Fig. 4. Flow table layout of learning switches TABLE I SOURCES AND SINKS Source Label read_inport(pkt) inport read_packet(pkt, fld) fld test_equal(pkt, fld, v) test(fld) read_env(env, var, key) env(var) (a) Sources and Labels Sink mod_packet(pkt, fld, v) mod_env(env, var, key, v) return r (b) Sinks Comments in Fig. 3 demonstrates how we trace the information flow. Every variable is assigned to a set of labels, recording the information flowing into the variable. For assignment statements, the label set of the variable on the left hand side is the union of the label sets of the variables on the right and the set of sources accessed. For example, the variable dst is assigned the label set {dst} at line 7 (packet field prefix omitted in the label set to avoid clutter), and port at line 4 is assigned {env(mac2port), dst}, which is obtained by {env(mac2port)} ∪ label(dst). The label set of a sink is the union of the label set of its arguments. The mod_env() at line 6 is a sink. Its label set is the union of the label sets of src and inport. For if statements, we analyse both branches and then merge the results. As an example, the label set for r at line 13 is the union of the sets at lines 9 and 11 respectively. When analysing each branch, we also need to consider the label set of the boolean branch condition of the if statements, because of the implicit information flow caused by control dependence. Therefore the label set of variable r is the union of the label sets of both inport and port. B. Xgraphs and Pipeline Generation Although the taint analysis generates dependence for each sink (at lines 6, 17 and 23), we also need to maintain the control flow to decide the order of these actions in the forwarding pipeline. We let the taint analysis generate Xgraph, an intermediate representation of both the control flow and the dependence (i.e. label sets). The Xgraph for our example is shown in Fig. 5. There are two types of nodes. The square node represents an action corresponding to a sink. It records the name and the line number of the action (e.g. mod_env@6 in the first node), and the corresponding label set (e.g. {src, inport} in the first node). Each diamond node represents a branch. It records the label set of the branch expression and the line number of the branch. The edges in the Xgraph represent the control flow. Given the Xgraph, we can do a “node to node” translation to generate the multi-stage forwarding pipeline. Fig. 6 shows the pipeline generated from Fig. 5. For each square node in the Xgraph, we generate a flow table for the functionality. The match fields of the flow table are the packet header fields and the ingress port in the dependence set of the corresponding Xgraph node. The action is translated from the corresponding controller action in the Xgraph node, but not necessarily the same. For example, we translate the controller action mod_env() in Fig. 5 into a [GOTO] action, which does nothing and jumps to the next flow table on the pipeline. As we explained before, the only effect of this table is to generate
/learning topology * C.Optimizations depends:(src,inport) action:mod env6 The generated pipeline can be further optimized.From Fig.6 we can see the match fields in different flow tables have branch(test(type))@14 overlaps,which may cause these fields to be matched multiple times.If we can merge some of these tables into one,we can branch(test(ttl))@16 reduce the redundancy.Another advantage for the merge is to reduce the length of the pipeline,so that the execution time is /*decreasing TTL * reduced accordingly.However,we have to be careful with the depends:(test(type),ttl) merge to avoid unnecessary combination of different match action:mod_packet 17 fields.as shown in Fig.4. /forwarding packets * We do the optimization by first trying to merge the Xgraph depends:(dst,env(mac2port),inport,test(type),test(ttl)> nodes.We consider two situations.In the first situation,we action:return23 merge adjacent square nodes n and n2 if the dependence set Fig.5.The Xgraph for the example of one is a subset of the other,i.e.n.depends n2.depends or n2.depends En.depends,where L EL def Vh ELn.32 L2.E tid:0 fields:(src,inport) h l def h =la V(dh =test (f1d)Al=f1d). actions:{[GOTO]) As we explain before,since the label test (fld)refers to tid:1 certain properties of the value of the field only,while fld fields:(type) relies on the exact value,the former contains less information actions:([GOTO]) than the latter and thus we let test(fld)fld.The new node after the merge simply contains the union of the tid:2 fields:(ttl) dependence set and the union of the actions in n and n2. actions:{[GOTO]) In the second situation,we merge the diamond node b and the square nodes n and n2 in its branches,if each branch tid:3 has at most one square node(there could be an empty branch fields:(type,ttl) with no nodes,as shown in Fig.5),and the dependence sets of actions:{[MOD_FIELD(ttl);GOTO]) these two branches overlap.More formally,we do the merge if n.depends En2.depends or n2.depends En.depends, bd:4 fields:{dst,inport,type,ttl) (if there is an empty branch,we can view it as a dummy node actions:{[OUTPUT可，[DROP} with empty dependence set).Then we merge the three nodes (b,ni and n2)into n,where n.depends n1.depends U Fig.6.Multi-stage pipeline n2.depends Ub.depends.The action set of n is also a union of those of n and n2.For example,in Fig.5 the action of decreasing TTL at line 17 can share a flow table with the mismatches (and the corresponding PacketIn messages)for sibling empty branch,so that we can merge the square node fresh("src","inport")pairs and to let the controller to receive with its parent diamond node. the packet and execute the mod env ()action.The controller We repeat the above processes until there are no more action mod packet (is translated to the flow table ac- nodes that can be merged.For the Xgraph in Fig.5,we tion [MOD_FLD;GOTO],which modifies the corresponding eventually merge the two diamond nodes and the square node packet field and then jumps to the next table.The return for decreasing TTL.The new Xgraph has three square nodes action in the Xgraph is translated into a corresponding OUT only.The merge does not increase the number of table entries, or DROP flow table action. because it does not introduce new combination of fields. We also generate a flow table for each diamond node.The Then we translate the merged Xgraph into a forwarding match fields are the fields that the branch depends on.The pipeline.For the Xgraph in Fig.5,after merging we get an action of the table is [GOTO].The flow table can jump to optimized pipeline of flow tables shown in Fig.7.In addition different flow tables based on the values of the match fields. to the table layout,we also show some table entries to help Because we generate a separate flow table for each inde- understanding how this pipeline works(the generation of table pendent functionality,and our taint-analysis generates more entries is explained in the next section).Table 0 depends fine-grained dependence relation than Maple,we can avoid only on "inport"and "src",and the action is to jump to enumerating values of unnecessary combination of match Table 1 directly.Table I depends on the exact values of"ttl", fields.For learning switches,we can avoid the O(n2)table decrements it (if the value is greater than 1)and jumps to Table entries in Fig.4.The total number of possible entries of the 2,which then either drops the packet or send it out depending pipeline in Fig.6 is O(n). on whether“ttl”is1 or not
/* learning topology */ depends: {src, inport} action: mod_env@6 branch(test(type))@14 branch(test(ttl))@16 /* forwarding packets */ depends: {dst, env(mac2port), inport, test(type), test(ttl)} action: return@23 /* decreasing TTL */ depends: {test(type), ttl} action: mod_packet@17 Fig. 5. The Xgraph for the example tid: 0 fields: {src, inport} actions: {[GOTO]} tid: 1 fields: {type} actions: {[GOTO]} tid: 2 fields: {ttl} actions: {[GOTO]} tid: 4 fields: {dst, inport, type, ttl} actions: {[OUTPUT], [DROP]} tid: 3 fields: {type, ttl} actions: {[MOD_FIELD(ttl); GOTO]} Fig. 6. Multi-stage pipeline mismatches (and the corresponding PacketIn messages) for fresh (“src”, “inport”) pairs and to let the controller to receive the packet and execute the mod_env() action. The controller action mod_packet() is translated to the flow table action [MOD_FLD; GOTO], which modifies the corresponding packet field and then jumps to the next table. The return action in the Xgraph is translated into a corresponding OUT or DROP flow table action. We also generate a flow table for each diamond node. The match fields are the fields that the branch depends on. The action of the table is [GOTO]. The flow table can jump to different flow tables based on the values of the match fields. Because we generate a separate flow table for each independent functionality, and our taint-analysis generates more fine-grained dependence relation than Maple, we can avoid enumerating values of unnecessary combination of match fields. For learning switches, we can avoid the O(n 2 ) table entries in Fig. 4. The total number of possible entries of the pipeline in Fig. 6 is O(n). C. Optimizations The generated pipeline can be further optimized. From Fig. 6 we can see the match fields in different flow tables have overlaps, which may cause these fields to be matched multiple times. If we can merge some of these tables into one, we can reduce the redundancy. Another advantage for the merge is to reduce the length of the pipeline, so that the execution time is reduced accordingly. However, we have to be careful with the merge to avoid unnecessary combination of different match fields, as shown in Fig. 4. We do the optimization by first trying to merge the Xgraph nodes. We consider two situations. In the first situation, we merge adjacent square nodes n1 and n2 if the dependence set of one is a subset of the other, i.e. n1.depends v n2.depends or n2.depends v n1.depends, where L1 v L2 def = ∀l1 ∈ L1. ∃l2 ∈ L2. l1 v l2 l1 v l2 def = l1 = l2 ∨ (∃fld.l1 = test(fld) ∧ l2 = fld). As we explain before, since the label test(fld) refers to certain properties of the value of the field only, while fld relies on the exact value, the former contains less information than the latter and thus we let test(fld) v fld. The new node after the merge simply contains the union of the dependence set and the union of the actions in n1 and n2. In the second situation, we merge the diamond node b and the square nodes n1 and n2 in its branches, if each branch has at most one square node (there could be an empty branch with no nodes, as shown in Fig. 5), and the dependence sets of these two branches overlap. More formally, we do the merge if n1.depends v n2.depends or n2.depends v n1.depends, (if there is an empty branch, we can view it as a dummy node with empty dependence set). Then we merge the three nodes (b, n1 and n2) into n, where n.depends = n1.depends ∪ n2.depends ∪ b.depends. The action set of n is also a union of those of n1 and n2. For example, in Fig. 5 the action of decreasing TTL at line 17 can share a flow table with the sibling empty branch, so that we can merge the square node with its parent diamond node. We repeat the above processes until there are no more nodes that can be merged. For the Xgraph in Fig. 5, we eventually merge the two diamond nodes and the square node for decreasing TTL. The new Xgraph has three square nodes only. The merge does not increase the number of table entries, because it does not introduce new combination of fields. Then we translate the merged Xgraph into a forwarding pipeline. For the Xgraph in Fig. 5, after merging we get an optimized pipeline of flow tables shown in Fig. 7. In addition to the table layout, we also show some table entries to help understanding how this pipeline works (the generation of table entries is explained in the next section). Table 0 depends only on “inport” and “src”, and the action is to jump to Table 1 directly. Table 1 depends on the exact values of “ttl”, decrements it (if the value is greater than 1) and jumps to Table 2, which then either drops the packet or send it out depending on whether “ttl” is 1 or not
Flow Table 0: TABLE II priority in_p src action EXAMPLE OF AN EXECUTION TRACE h1 G0T0(1) 2 h2 G0T0(1) trace sub-trace 2 instrumentation 4 read_inport(pkt)==1; V Flow Table 1: read_packet(pkt,"dst")==h2: priority type ttl action read_packet(pkt,"src")==h1; 1 mod env(env,"mac2port",h1,1): 0x800 64 M0D_FLD(tt1,63);G0T0(2) read_ev(env,“"mac2port”,h2)==0: 0x800 1 G00(2) branch(8.false): test_equal(pkt,"type",Ox800)==true Flow Table 2: branch(14.true); priority in_p dst type action branch(16,false); 5 h2 0x800 DROP test_equal(pkt.“tt”",I)==true hi 0x800 oUT[1] return 0: 3 2 h3 0x800 0UT[1,3,4.··] 4+ *=4 Fig.7.Optimized flow table layout of leaming switches further refine the conservative dependence relation generated by the static taint analysis,as we pointed out at the end of Sec.III.This is achieved by extending the taint analysis However,Flow Table 2 may still contain more table entries algorithm with the more refined dependent labels.Below we than needed.When"ttl"is 1,the packet is always dropped, and the action is independent of“inport''and“dst”.So ideally explain in detail the dependent labels and the use of it together in the first row of the table,the first two columns should be"*" with runtime information to generate compact table entries. instead of the exact values.Unfortunately we cannot achieve A.Splitting the trace this effect because the label set generated by the taint analysis With multi-table pipelines,we need to derive sub-traces for the return value r is not precise enough-at the end from a full execution trace for individual flow tables.Given of the if statement we always merge the label sets of the the Xgraph and the corresponding pipeline generated by the two branches,leading to a conservative upper bound of the taint analysis,we can simply extract the events that correspond set of labels that may affect the value of r.Our idea to solve to those in the dependence set and the set of actions in each this problem is to introduce dependent labels to generate more Xgraph node.For instance,from the last square node in Fig.5 precise dependence relation,which allows us to fill "*"into (which corresponds to the layout of Flow Table 2 in Fig.7), the table to further reduce the size of tables.We explain the we can easily find all the relevant events in the trace shown details in the next section. in TableⅡ.We mark these events with√(ignore the“*”for IV.TABLE ENTRY GENERATION AND DEPENDENT LABELS now),which form the sub-trace for Flow Table 2.With this sub-trace we can generate the first row in the Flow Table 2. Following the idea of Maple,our system automatically However,when"ttl"is 1,we drop the packet regardless of populates flow table entries by discovering reusable network the values of“inport'”and“dst”,and the result of read_env. policy executions.When f is invoked,the runtime system Therefore the three events marked with "*in Table II tracks its execution,and records the trace consisting of events should be removed from the sub-trace,so that we can fill"*" accessing packets and the environment data.In the leftmost in the corresponding matching fields ("inport"and "dst")of column of Table II,we show a trace generated when f for the flow table entry.As we explained at the end of Sec.III,the learning switches is invoked with an IPv4 packet from h to conservative label set for the return value r should be blamed h2,and the field of"ttl"is 1 (so the packet is dropped). for the inclusion of the three events in the sub-trace.Knowing Maple derives the dependence between actions (such as the runtime value of"ttl",we should be able to infer that the dropping the packet)and the values of packet fields,from action in this case only depends on the testing of "type"and which the corresponding flow table entries are generated "ttl".But how do we take advantage of the runtime value to for the switches.(Maple actually also maintains historical generate the more precise dependence relation? execution traces,and merges all the traces into a trace tree.We follow the same mechanism.but omit the details of trace trees B.Dependent labels here to simplify the presentation.)This simple approach works To solve the problem above,we extend the labeling system for a monolithic flow table with large amount of unnecessary in the taint analysis with dependent labels.Labels and label table entries,but it cannot be applied directly in our setting sets are defined below: with multi-table pipelines.Since the linear-timed execution (Labels)I ::fld test (fld)...|Lan?L1:L2 trace contains all the events produced by f,how do we fit (LabSets)L ::(1,...,In} it into multiple flow tables? What's new here is the dependent label in the form of To solve this problem,we need to derive sub-traces from LaN?L1:L2.It is used to label variables at the end of the the global trace and assign a sub-trace to each flow table,from statement if(B)C1 else C2,starting at line number N in the which we generate the corresponding table entries.During code.L is the label set for B,and Li and L2 are the label sets this process,we also take advantage of the runtime values to assigned to the variables in the two branches respectively.As
Flow Table 0: priority in p src action 1 1 h1 GOTO(1) 1 2 h2 GOTO(1) ... ... ... ... Flow Table 1: priority type ttl action 1 0x800 64 MOD_FLD(ttl,63); GOTO(2) ... ... ... ... 1 0x800 1 GOTO(2) Flow Table 2: priority in p dst type ttl action 5 1 h2 0x800 1 DROP 3 2 h1 0x800 * OUT[1] 3 2 h3 0x800 * OUT[1,3,4...] ... ... ... ... ... ... Fig. 7. Optimized flow table layout of learning switches However, Flow Table 2 may still contain more table entries than needed. When “ttl” is 1, the packet is always dropped, and the action is independent of “inport” and “dst”. So ideally in the first row of the table, the first two columns should be “*” instead of the exact values. Unfortunately we cannot achieve this effect because the label set generated by the taint analysis for the return value r is not precise enough — at the end of the if statement we always merge the label sets of the two branches, leading to a conservative upper bound of the set of labels that may affect the value of r. Our idea to solve this problem is to introduce dependent labels to generate more precise dependence relation, which allows us to fill “*” into the table to further reduce the size of tables. We explain the details in the next section. IV. TABLE ENTRY GENERATION AND DEPENDENT LABELS Following the idea of Maple, our system automatically populates flow table entries by discovering reusable network policy executions. When f is invoked, the runtime system tracks its execution, and records the trace consisting of events accessing packets and the environment data. In the leftmost column of Table II, we show a trace generated when f for learning switches is invoked with an IPv4 packet from h1 to h2, and the field of “ttl” is 1 (so the packet is dropped). Maple derives the dependence between actions (such as dropping the packet) and the values of packet fields, from which the corresponding flow table entries are generated for the switches. (Maple actually also maintains historical execution traces, and merges all the traces into a trace tree. We follow the same mechanism, but omit the details of trace trees here to simplify the presentation.) This simple approach works for a monolithic flow table with large amount of unnecessary table entries, but it cannot be applied directly in our setting with multi-table pipelines. Since the linear-timed execution trace contains all the events produced by f, how do we fit it into multiple flow tables? To solve this problem, we need to derive sub-traces from the global trace and assign a sub-trace to each flow table, from which we generate the corresponding table entries. During this process, we also take advantage of the runtime values to TABLE II EXAMPLE OF AN EXECUTION TRACE trace sub-trace 2 instrumentation read inport(pkt) == 1; √ * read packet(pkt, “dst”) == h2; √ * read packet(pkt, “src”) == h1; mod env(env, “mac2port”, h1, 1); read env(env, “mac2port”, h2) == 0; √ * branch(8, false); test equal(pkt, “type”, 0x800) == true √ branch(14, true); branch(16, false); test equal(pkt, “ttl”, 1) == true √ return 0; √ further refine the conservative dependence relation generated by the static taint analysis, as we pointed out at the end of Sec. III. This is achieved by extending the taint analysis algorithm with the more refined dependent labels. Below we explain in detail the dependent labels and the use of it together with runtime information to generate compact table entries. A. Splitting the trace With multi-table pipelines, we need to derive sub-traces from a full execution trace for individual flow tables. Given the Xgraph and the corresponding pipeline generated by the taint analysis, we can simply extract the events that correspond to those in the dependence set and the set of actions in each Xgraph node. For instance, from the last square node in Fig. 5 (which corresponds to the layout of Flow Table 2 in Fig. 7), we can easily find all the relevant events in the trace shown in Table II. We mark these events with √ (ignore the “*” for now), which form the sub-trace for Flow Table 2. With this sub-trace we can generate the first row in the Flow Table 2. However, when “ttl” is 1, we drop the packet regardless of the values of “inport” and “dst”, and the result of read_env. Therefore the three events marked with “√ *” in Table II should be removed from the sub-trace, so that we can fill “*” in the corresponding matching fields (“inport” and “dst”) of the flow table entry. As we explained at the end of Sec. III, the conservative label set for the return value r should be blamed for the inclusion of the three events in the sub-trace. Knowing the runtime value of “ttl”, we should be able to infer that the action in this case only depends on the testing of “type” and “ttl”. But how do we take advantage of the runtime value to generate the more precise dependence relation? B. Dependent labels To solve the problem above, we extend the labeling system in the taint analysis with dependent labels. Labels and label sets are defined below: (Labels) l ::= fld | test(fld) | . . . | L@N ?L1 :L2 (LabSets) L ::= {l1, . . . , ln} What’s new here is the dependent label in the form of L@N ?L1 : L2. It is used to label variables at the end of the statement if(B) C1 else C2, starting at line number N in the code. L is the label set for B, and L1 and L2 are the label sets assigned to the variables in the two branches respectively. As
(test(type))014 start dst :48 src :48 {test(tt》@16 {t,env(mac2port》@8 type 16 eth type {dst,env(mac2port)>8 {t,env(mac2port)】 (inport) 0x86dd Y0x0800Qx0806 ist,env(mac2part)} (inport) ipv6 ipv4 arp Fig.8.Dependent label of r Fig.9.A parse graph we explain in Sec.III-A,the standard taint analysis algorithm example,the label set for the return command is the same merges the sets LI and L2 of the two branches when we reach with the set for the variable r,as shown in Fig.8.From the the end of the if statement.We generate the dependent label instrumented trace we know the branches taken for the if instead,which is a more refined view,saying the label set statements at lines 14 and 16.therefore we know the relevant depends on the value of the branch condition B containing labels are only those shown on the grey path in Fig.8.This information in L.If B holds the label set is L1,otherwise L2. allows us to remove the events labeled with"*"in the middle As an example,the if statement at line 8 in Fig.3 column of Table II.With this more compact sub-trace,in Flow assigns different values to r.We define the label set of r Table 2 of Fig.7 we can fill"*"into the first two fields of asL={),where l is a dependent label defined as the first row,which results in not only compact flow tables, port?r:(inr)and port is the label set but also much less mismatches and PacketIn messages. for port at line 8,i.e.Lport ={dst,env (mac2port)}. Similarly,the if statement at line 16 leaves r untouched in V.PACKET PARSING one branch,and assigns 0 to it in the other.So the label set of r is either the same as before (i.e.Lr1),or empty set (if it is POMP supports protocol oblivious programming.It uses reset to 0,which contains no source information).We define dotted paths of packet header fields to access pack- the label set as Lr2 ={l2),where the dependent label lr2 ets.For instance,the API call of readpacket (pkt, is defined as {test (tt1)?L:{}We can also give an "eth.ipv4.ttl")in Fig.3 accesses the "ttl"field of intuitive graphic view of dependent labels.Fig.8 shows the the ipv4 packet..In the dotted string path,“eth”and“ipv4" dependent label assigned to r at the end of the if statement represent protocol names and the last substring"ttl"is the field at line 14 (which is also the final label for r). name.The string path can be arbitrary for any user customized In the learning switches example,the extension of taint protocols.It is not limited to a predefined set of protocols. analysis with dependent labels affects only the labeling of To achieve this,the programmers provide protocol speci- r,whose value depends on the if statement branches taken fications,from which a parse graph is generated.The parse at runtime.Although it gives us a more refined view of graph serves both as a P4 parser,which can be compiled and information flow,the dependent label does not affect our deployed on P4 switches,or as an input to the runtime systems algorithm to generate pipelines shown in Sec.III because to parsing packets at the control plane. statically we do not know which branch will be taken and have to maintain a conservative view as before.The generated pipeline is the same as we have shown before. A.Protocol specification However,we can know which branch is taken at runtime, As shown in the learning switches example in Fig.2,a then we can derive more refined label sets from the dependent protocol specification consists of a set of header definitions label.This means we can find more precise sub-traces for and a starting protocol declaration.A header definition has different flow tables.However,to take advantage of dependent the following parts. labels.we need to instrument the code and the traces to remember which if statement branch is taken at runtime. header name:name of the protocol,e.g.eth and ipv4. fields:the layout of the header,consisting of a sequence C.Code and trace instrumentation of field names and the corresponding lengths in bits. We instrument the if statement in the code of the network next headers:the name of the next header,which could policy f to generate events showing which branch is taken at be conditional upon the value of certain field.For in- runtime.For the example execution trace shown in Table II, stance,if the type of eth is 0x800,the next header is we have three more events after the instrumentation,shown in ipv4;if it is 0x86dd,the next header is ipv6. the right column. The starting protocol declaration shows which protocol is With this instrumented trace and the dependent labels,we the outmost one,i.e.the one that needs to be parsed first.It can derive more compact sub-traces.In the learning switches is eth in our example
{test(type)}@14 {test(ttl)}@16 Y {dst, env(mac2port)}@8 N {dst, env(mac2port)}@8 Y {} N {dst, env(mac2port)} Y {inport} N {dst, env(mac2port)} Y {inport} N Fig. 8. Dependent label of r we explain in Sec. III-A, the standard taint analysis algorithm merges the sets L1 and L2 of the two branches when we reach the end of the if statement. We generate the dependent label instead, which is a more refined view, saying the label set depends on the value of the branch condition B containing information in L. If B holds the label set is L1, otherwise L2. As an example, the if statement at line 8 in Fig. 3 assigns different values to r. We define the label set of r as Lr1 = {lr1}, where lr1 is a dependent label defined as Lport@8 ?Lport : {inport}, and Lport is the label set for port at line 8, i.e. Lport = {dst, env(mac2port)}. Similarly, the if statement at line 16 leaves r untouched in one branch, and assigns 0 to it in the other. So the label set of r is either the same as before (i.e. Lr1), or empty set (if it is reset to 0, which contains no source information). We define the label set as Lr2 = {lr2}, where the dependent label lr2 is defined as {test(ttl)}@16 ?Lr1 : {}. We can also give an intuitive graphic view of dependent labels. Fig. 8 shows the dependent label assigned to r at the end of the if statement at line 14 (which is also the final label for r). In the learning switches example, the extension of taint analysis with dependent labels affects only the labeling of r, whose value depends on the if statement branches taken at runtime. Although it gives us a more refined view of information flow, the dependent label does not affect our algorithm to generate pipelines shown in Sec. III because statically we do not know which branch will be taken and have to maintain a conservative view as before. The generated pipeline is the same as we have shown before. However, we can know which branch is taken at runtime, then we can derive more refined label sets from the dependent label. This means we can find more precise sub-traces for different flow tables. However, to take advantage of dependent labels, we need to instrument the code and the traces to remember which if statement branch is taken at runtime. C. Code and trace instrumentation We instrument the if statement in the code of the network policy f to generate events showing which branch is taken at runtime. For the example execution trace shown in Table II, we have three more events after the instrumentation, shown in the right column. With this instrumented trace and the dependent labels, we can derive more compact sub-traces. In the learning switches Fig. 9. A parse graph example, the label set for the return command is the same with the set for the variable r, as shown in Fig. 8. From the instrumented trace we know the branches taken for the if statements at lines 14 and 16, therefore we know the relevant labels are only those shown on the grey path in Fig. 8. This allows us to remove the events labeled with “*” in the middle column of Table II. With this more compact sub-trace, in Flow Table 2 of Fig. 7 we can fill “*” into the first two fields of the first row, which results in not only compact flow tables, but also much less mismatches and PacketIn messages. V. PACKET PARSING POMP supports protocol oblivious programming. It uses dotted paths of packet header fields to access packets. For instance, the API call of read_packet(pkt, "eth.ipv4.ttl") in Fig. 3 accesses the “ttl” field of the ipv4 packet. In the dotted string path, “eth” and “ipv4” represent protocol names and the last substring “ttl” is the field name. The string path can be arbitrary for any user customized protocols. It is not limited to a predefined set of protocols. To achieve this, the programmers provide protocol speci- fications, from which a parse graph is generated. The parse graph serves both as a P4 parser, which can be compiled and deployed on P4 switches, or as an input to the runtime systems to parsing packets at the control plane. A. Protocol specification As shown in the learning switches example in Fig. 2, a protocol specification consists of a set of header definitions and a starting protocol declaration. A header definition has the following parts. • header name: name of the protocol, e.g. eth and ipv4. • fields: the layout of the header, consisting of a sequence of field names and the corresponding lengths in bits. • next headers: the name of the next header, which could be conditional upon the value of certain field. For instance, if the type of eth is 0x800, the next header is ipv4; if it is 0x86dd, the next header is ipv6. The starting protocol declaration shows which protocol is the outmost one, i.e. the one that needs to be parsed first. It is eth in our example
B.Parsing graphs and packet parsing 。“dep”/“nondep”:Enabling or disabling the use of From the protocol specification one can easily derive a dependent labels explained in Sec.IV-B. parse graph as in P4.As shown in Fig.9,the parse graph We run the learning switches example using different op- is a directed graph,where nodes represent protocols declared tions and different n(i.e.the number of hosts).We record the in the specification,and edges represent the ordering of number of flow tables.Then we use the"pingall"test provided protocols.The edges are generated from the next block of by Mininet to send packets among hosts.We record the total the specification,and the labels represents the corresponding number of flow table entries and number of packet-in events values of the field that one uses to determine the next protocol. generated during the test,and the execution time. The start node is specified by the start clause. A.The quality of pipelines Both the runtime system of POMP in the control plane and the data plane may use the parse graph for packet parsing. We use the number of flow tables and total number of table 1)Parsing in the control plane:The POMP runtime takes entries to evaluate the quality of pipelines.The result is shown the parse graph and a raw packet as input,and outputs a map in Table IⅢ，from which we can see: from field names to (offset,length)tuples,which can The total number of entries grows quadratically in single- be used to extract values of fields from the raw packet.As table,while it grows linearly in multi-table pipelines. explained before,we use dotted notations (e.g."eth.ipv4.ttl") POMP under the multi-opt-dep setting uses up to 47x for field names to avoid name clash.The parsing starts with fewer number of entries than single-table. the start node and traverses the parse graph.During the process ·Turning on“opt'”reduces the number of tables from5to it also maintains a current pointer pointing to the raw packet. 3.while the number of entries is about the same.This which is used to extract the value of certain field (e.g.type) is because the reduced flow tables (with tid 1 and 2 in to decide the next node to transit to. Fig.6)contain only 3 entries in total. The parsing process is invoked on receiving a Packet In Dependent labels (turning on "dep")save 66%-80% message.In the network policy f(pkt,env),when packet entries,comparing the last two rows of Table III. fields are accessed using string names,we lookup the map B.Performance generated by the parser to find the corresponding (offset, length)tuples,using which we can locate the field and do We use the execution time and the number of PacketIn the read/write of the field. events to evaluate the performance.The result is shown in Since the switch of POF uses (offset,length)tuples Tables IV and V.We also compare our learning switches in the flow table to access packet fields,the runtime system with the built-in learning functionality of Open vSwitch,a also needs to translate field names into (offset,length) production quality soft switch.Its profile is shown as "ovsk". when installing flow table entries for POF switches. From Tables IV and V we can see: 2)Parsing in the data plane:POF and P4 uses different Multi-table pipeline causes significantly less PacketIn strategies to achieve protocol independence.In POF,no parser messages than single table,and is up to 134x faster. is required in the data plane.We use (offset,length) ·Multi--table pipeline is20%-40%slower than“ovsk”. generated by the control plane parser to specify packet fields. This is unsurprising because"ovsk"is a pure data plane On the other hand,our parsing graph also serves as a P4 application,and there is no controller-switch communi- parser,which can be fed into the P4 compiler to generate a cation (i.e.no PacketIn messages). data plane parser.All incoming packets must be parsed at the Dependent labels help reducing the number of PacketIn data plane before being sent to the pipeline. events,thus improve the performance. Note that turning on "opt"alone is not helpful to reduce the VI.EVALUATION number of PacketIn messages.Since the pingall time is spent We compare the effects of different techniques we use, mostly by PacketIn messages,"opt"introduces no obvious and demonstrate that POMP generates high-quality forwarding decrease of pingall time either. pipelines.The evaluation setting is the following: VII.RELATED WORK Hardware:Intel Core I7 4712MQ 2.3GHz,8G RAM. In Sec.I we have pointed out the limitations of many Network Emulator:Mininet [9]. representative languages,including NetKAT [6].NetCore [7]. Switch:P4 bmv2 [10]Open vSwitch [11]2.6.2. Maple [5]and P4 [1].Here we compare our work with some Topology:Single 10 port switch with n hosts. more SDN programming languages. To show the effects of different techniques,POMP provides Magellan [12]also derives and populates multi-table three tunable options: pipelines from algorithmic policies,but it takes very different ·“multi”/“single”:Enabling or disabling the generation approaches from ours.It starts from extremely fine-grained of multi-table pipelines.The"single"option turns off the pipelines by treating every statement as a flow table.Then taint analysis and generates a single monolithic flow table. it recognizes the so called compact operations and merges ·“opt”/“nonopt'":Enabling or disabling the pipeline their corresponding flow tables with others,so that the number optimization shown in Sec.III-C. of flow tables is reduced without significantly increasing the
B. Parsing graphs and packet parsing From the protocol specification one can easily derive a parse graph as in P4. As shown in Fig. 9, the parse graph is a directed graph, where nodes represent protocols declared in the specification, and edges represent the ordering of protocols. The edges are generated from the next block of the specification, and the labels represents the corresponding values of the field that one uses to determine the next protocol. The start node is specified by the start clause. Both the runtime system of POMP in the control plane and the data plane may use the parse graph for packet parsing. 1) Parsing in the control plane: The POMP runtime takes the parse graph and a raw packet as input, and outputs a map from field names to (offset, length) tuples, which can be used to extract values of fields from the raw packet. As explained before, we use dotted notations (e.g. “eth.ipv4.ttl”) for field names to avoid name clash. The parsing starts with the start node and traverses the parse graph. During the process it also maintains a current pointer pointing to the raw packet, which is used to extract the value of certain field (e.g. type) to decide the next node to transit to. The parsing process is invoked on receiving a PacketIn message. In the network policy f(pkt, env), when packet fields are accessed using string names, we lookup the map generated by the parser to find the corresponding (offset, length) tuples, using which we can locate the field and do the read/write of the field. Since the switch of POF uses (offset, length) tuples in the flow table to access packet fields, the runtime system also needs to translate field names into (offset, length) when installing flow table entries for POF switches. 2) Parsing in the data plane: POF and P4 uses different strategies to achieve protocol independence. In POF, no parser is required in the data plane. We use (offset, length) generated by the control plane parser to specify packet fields. On the other hand, our parsing graph also serves as a P4 parser, which can be fed into the P4 compiler to generate a data plane parser. All incoming packets must be parsed at the data plane before being sent to the pipeline. VI. EVALUATION We compare the effects of different techniques we use, and demonstrate that POMP generates high-quality forwarding pipelines. The evaluation setting is the following: • Hardware: Intel Core I7 4712MQ 2.3GHz, 8G RAM. • Network Emulator: Mininet [9]. • Switch: P4 bmv2 [10] / Open vSwitch [11] 2.6.2. • Topology: Single 10 port switch with n hosts. To show the effects of different techniques, POMP provides three tunable options: • “multi” / “single”: Enabling or disabling the generation of multi-table pipelines. The “single” option turns off the taint analysis and generates a single monolithic flow table. • “opt” / “nonopt”: Enabling or disabling the pipeline optimization shown in Sec. III-C. • “dep” / “nondep”: Enabling or disabling the use of dependent labels explained in Sec. IV-B. We run the learning switches example using different options and different n (i.e. the number of hosts). We record the number of flow tables. Then we use the “pingall” test provided by Mininet to send packets among hosts. We record the total number of flow table entries and number of packet-in events generated during the test, and the execution time. A. The quality of pipelines We use the number of flow tables and total number of table entries to evaluate the quality of pipelines. The result is shown in Table III, from which we can see: • The total number of entries grows quadratically in singletable, while it grows linearly in multi-table pipelines. • POMP under the multi-opt-dep setting uses up to 47x fewer number of entries than single-table. • Turning on “opt” reduces the number of tables from 5 to 3, while the number of entries is about the same. This is because the reduced flow tables (with tid 1 and 2 in Fig. 6) contain only 3 entries in total. • Dependent labels (turning on “dep”) save 66% - 80% entries, comparing the last two rows of Table III. B. Performance We use the execution time and the number of PacketIn events to evaluate the performance. The result is shown in Tables IV and V. We also compare our learning switches with the built-in learning functionality of Open vSwitch, a production quality soft switch. Its profile is shown as “ovsk”. From Tables IV and V we can see: • Multi-table pipeline causes significantly less PacketIn messages than single table, and is up to 134x faster. • Multi-table pipeline is 20% - 40% slower than “ovsk”. This is unsurprising because “ovsk” is a pure data plane application, and there is no controller-switch communication (i.e. no PacketIn messages). • Dependent labels help reducing the number of PacketIn events, thus improve the performance. Note that turning on “opt” alone is not helpful to reduce the number of PacketIn messages. Since the pingall time is spent mostly by PacketIn messages, “opt” introduces no obvious decrease of pingall time either. VII. RELATED WORK In Sec. I we have pointed out the limitations of many representative languages, including NetKAT [6], NetCore [7], Maple [5] and P4 [1]. Here we compare our work with some more SDN programming languages. Magellan [12] also derives and populates multi-table pipelines from algorithmic policies, but it takes very different approaches from ours. It starts from extremely fine-grained pipelines by treating every statement as a flow table. Then it recognizes the so called compact operations and merges their corresponding flow tables with others, so that the number of flow tables is reduced without significantly increasing the
TABLE III THE QUALITY OF PIPELINE profile tables entries n=10n=20n=30n=40n=50n=100 single 121 44 961 1681 2601 1020 multi-nonopt-dep 43 63 83 103 123 223 multi-opt-nondep 120 232 350 460 570 1120 multi-opt-dep 40 60 0 100 120 220 TABLE IV notion of dependent labels to refine the label sets generated by PERFORMANCE:PINGALL TIME the taint analysis.The dependent labels are used at the runtime for flow table entry generation to further reduce the number of profile pingall time(s)】 n=10n=20n=30Tn=40n=50n=100 table entries.The evaluation results show that POMP generates single 0.60 6. 28 78 18T 2831 ovsk 0.10 0.60 high-quality forwarding pipelines.POMP pipeline for learning 13 2.4 3.7 15 multi-nonopt-dep 0.20 0.78 18 3.1 4.9 20 switches uses up to 47x fewer number of table entries.and is multi-opt-nondep 0.54 2.1 4.5 7.8 12 47 up to 137x faster than single table. multi-opt-dep 0.19 0.76 1.7 3.1 4.8 19 Note that,although the learning switches example is used throughout the paper to demonstrate the key ideas,POMP TABLE V is a general purpose language for SDN programming.In PERFORMANCE:NUMBER OF PACKETIN addition to these APIs used in learning switches,there are packet in profile more provided,including those for environment management. n=10 n=20 n=30 n=40 n=50n=100 single 117 423 939 1643 2549 10099 The set of POMP APIs is as expressive as those in Maple. multi-nonopt-dep 6 女 79 92 111 223 multi-opt-nondep 124 258 351 452 562 1134 REFERENCES multi-opt-dep 47 72 80 93 112 221 [1]P.Bosshart,D.Daly,G.Gibb,M.Izzard,N.McKeown,J.Rexford C.Schlesinger,D.Talayco,A.Vahdat,G.Varghese,and D.Walker "P4:Programming protocol-independent packet processors,"S/GCOMM number of table entries.Also,unlike POMP that generates flow Comput.Commun.Rev.,vol.44,no.3,pp.87-95,Jul.2014 [2]H.Song."Protocol-oblivious forwarding:Unleash the power of SDN table entries reactively at runtime,Magellan generates table through a future-proof forwarding plane,"in Proc.of HotSDN.2013. entries proactively by enumerating all possible executions of pp.127-132. the network policy before its deployment.Moreover.Magellan [3]P.Bosshart,G.Gibb,H.-S.Kim,G.Varghese,N.McKeown,M.Iz- zard,F.Mujica,and M.Horowitz,"Forwarding metamorphosis:Fast provides no mechanisms for protocol oblivious programming. programmable match-action processing in hardware for SDN,"in Proc. Concurrent NetCore [13]extends NetCore [7]to support ofS1 GCOMM,2013,pp.99-110. multi-tables,but it requires the programmer to manually define [4] M.Shahbaz,S.Choi,B.Pfaff,C.Kim,N.Feamster,N.McKeown,and J.Rexford,"Pisces:A programmable,protocol-independent software the layout of flow tables instead of generating it automatically switch."in Proc.of SIGCOMM.2016.pp.525-538. from high-level policies as we do in POMP. [5]A.Voellmy.J.Wang.Y.R.Yang.B.Ford,and P.Hudak,"Maple: Stateful NetKAT [14]and SNAP [15]extend NetKAT [6] Simplifying SDN programming using algorithmic policies,"in Proc.of SIGCOMM,2013.pp.87-98. and NetCore [7]respectively to support persistent states [6]C.J.Anderson,N.Foster,A.Guha,J.-B.Jeannin,D.Kozen, in emerging SDN data plane.They are for quite different C.Schlesinger,and D.Walker,"Netkat:Semantic foundations for purposes (to take advantage of the switch-local computation networks,"in Proc.of POPL,2014.pp.113-126. [7]C.Monsanto.N.Foster.R.Harrison.and D.Walker."A compiler power)and do not handle multi-table pipelines. and run-time system for network programming languages,"in Proc.of P4 Runtime [16]provides a way for control plane to control P0PL,2012,Pp.217-230. P4 switches.The programmer can use P4 Runtime APIs to [8]S.Hunt and D.Sands,"On flow-sensitive security types,"in Prof.of POPL,2006.pp.79-90. install flow table entries at runtime.In POMP,the programmer (9]B.Lantz,B.Heller,and N.McKeown,"A network in a laptop:Rapid doesn't use P4 Runtime APIs.The switch abstraction layer prototyping for software-defined networks,"in Proc.of Homets-IX. (see Fig.1)accepts entries generated by the runtime of POMP, 2010,Pp.191-19:6 [10]"P4 behavioral model,"https://github.com/p4lang/behavioral-model,ac- then calls P4 Runtime APIs to install entries for P4 switches. cessed:2017-07-31. [11]"Open vSwitch,"http://openvswitch.org/,accessed:2017-07-31. VIII.CONCLUSION [12]A.Voellmy,S.Chen,X.Wang,and Y.R.Yang."Magellan:Generating POMP is a general purpose SDN programming environment multi-table datapath from datapath oblivious algorithmic SDN policies,' supporting both protocol oblivious programming and auto- in Proc.of SIGCOMM,2016,pp.593-594. [13]C.Schlesinger,M.Greenberg.and D.Walker."Concurrent netcore: matic multi-table pipelining.It extends the C language with From policies to pipelines,"in Proc.of ICFP.2014.pp.11-24. a set of APIs and a runtime system to allow programmers to [14]J.McClurg,H.Hojjat,N.Foster,and P.Cemny,"Event-driven network programming,"in Proc.of PLDI,2016,pp.369-385. write algorithmic,data-plane agnostic network policy for SDN [15]M.T.Arashloo,Y.Koral,M.Greenberg.J.Rexford,and D.Walker, programming.It then applies static taint analysis techniques to "Snap:Stateful network-wide abstractions for packet processing."in automatically infers compact and efficient multi-table pipelines Proc.of SIGCOMM.2016,pp.29-43. [16]"P4 runtime,"https://p4.org/p4-runtime/,accessed:2017-12-27. from the high-level network policy.It also introduces a novel
TABLE III THE QUALITY OF PIPELINE profile # tables # entries n = 10 n = 20 n = 30 n = 40 n = 50 n = 100 single 1 121 441 961 1681 2601 10201 multi-nonopt-dep 5 43 63 83 103 123 223 multi-opt-nondep 3 120 232 350 460 570 1120 multi-opt-dep 3 40 60 80 100 120 220 TABLE IV PERFORMANCE: PINGALL TIME profile pingall time (s) n=10 n=20 n=30 n=40 n=50 n=100 single 0.60 6.1 28 78 181 2831 ovsk 0.10 0.60 1.3 2.4 3.7 15 multi-nonopt-dep 0.20 0.78 1.8 3.1 4.9 20 multi-opt-nondep 0.54 2.1 4.5 7.8 12 47 multi-opt-dep 0.19 0.76 1.7 3.1 4.8 19 TABLE V PERFORMANCE: NUMBER OF PACKETIN profile # packet in n=10 n=20 n=30 n=40 n=50 n=100 single 117 423 939 1643 2549 10099 multi-nonopt-dep 46 74 79 92 111 223 multi-opt-nondep 124 258 351 452 562 1134 multi-opt-dep 47 72 80 93 112 221 number of table entries. Also, unlike POMP that generates flow table entries reactively at runtime, Magellan generates table entries proactively by enumerating all possible executions of the network policy before its deployment. Moreover, Magellan provides no mechanisms for protocol oblivious programming. Concurrent NetCore [13] extends NetCore [7] to support multi-tables, but it requires the programmer to manually define the layout of flow tables instead of generating it automatically from high-level policies as we do in POMP. Stateful NetKAT [14] and SNAP [15] extend NetKAT [6] and NetCore [7] respectively to support persistent states in emerging SDN data plane. They are for quite different purposes (to take advantage of the switch-local computation power) and do not handle multi-table pipelines. P4 Runtime [16] provides a way for control plane to control P4 switches. The programmer can use P4 Runtime APIs to install flow table entries at runtime. In POMP, the programmer doesn’t use P4 Runtime APIs. The switch abstraction layer (see Fig. 1) accepts entries generated by the runtime of POMP, then calls P4 Runtime APIs to install entries for P4 switches. VIII. CONCLUSION POMP is a general purpose SDN programming environment supporting both protocol oblivious programming and automatic multi-table pipelining. It extends the C language with a set of APIs and a runtime system to allow programmers to write algorithmic, data-plane agnostic network policy for SDN programming. It then applies static taint analysis techniques to automatically infers compact and efficient multi-table pipelines from the high-level network policy. It also introduces a novel notion of dependent labels to refine the label sets generated by the taint analysis. The dependent labels are used at the runtime for flow table entry generation to further reduce the number of table entries. The evaluation results show that POMP generates high-quality forwarding pipelines. POMP pipeline for learning switches uses up to 47x fewer number of table entries, and is up to 137x faster than single table. Note that, although the learning switches example is used throughout the paper to demonstrate the key ideas, POMP is a general purpose language for SDN programming. In addition to these APIs used in learning switches, there are more provided, including those for environment management. The set of POMP APIs is as expressive as those in Maple. REFERENCES [1] P. Bosshart, D. Daly, G. Gibb, M. Izzard, N. McKeown, J. Rexford, C. Schlesinger, D. Talayco, A. Vahdat, G. Varghese, and D. Walker, “P4: Programming protocol-independent packet processors,” SIGCOMM Comput. Commun. Rev., vol. 44, no. 3, pp. 87–95, Jul. 2014. [2] H. Song, “Protocol-oblivious forwarding: Unleash the power of SDN through a future-proof forwarding plane,” in Proc. of HotSDN, 2013, pp. 127–132. [3] P. Bosshart, G. Gibb, H.-S. Kim, G. Varghese, N. McKeown, M. Izzard, F. Mujica, and M. Horowitz, “Forwarding metamorphosis: Fast programmable match-action processing in hardware for SDN,” in Proc. of SIGCOMM, 2013, pp. 99–110. [4] M. Shahbaz, S. Choi, B. Pfaff, C. Kim, N. Feamster, N. McKeown, and J. Rexford, “Pisces: A programmable, protocol-independent software switch,” in Proc. of SIGCOMM, 2016, pp. 525–538. [5] A. Voellmy, J. Wang, Y. R. Yang, B. Ford, and P. Hudak, “Maple: Simplifying SDN programming using algorithmic policies,” in Proc. of SIGCOMM, 2013, pp. 87–98. [6] C. J. Anderson, N. Foster, A. Guha, J.-B. Jeannin, D. Kozen, C. Schlesinger, and D. Walker, “Netkat: Semantic foundations for networks,” in Proc. of POPL, 2014, pp. 113–126. [7] C. Monsanto, N. Foster, R. Harrison, and D. Walker, “A compiler and run-time system for network programming languages,” in Proc. of POPL, 2012, pp. 217–230. [8] S. Hunt and D. Sands, “On flow-sensitive security types,” in Prof. of POPL, 2006, pp. 79–90. [9] B. Lantz, B. Heller, and N. McKeown, “A network in a laptop: Rapid prototyping for software-defined networks,” in Proc. of Hotnets-IX, 2010, pp. 19:1–19:6. [10] “P4 behavioral model,” https://github.com/p4lang/behavioral-model, accessed: 2017-07-31. [11] “Open vSwitch,” http://openvswitch.org/, accessed: 2017-07-31. [12] A. Voellmy, S. Chen, X. Wang, and Y. R. Yang, “Magellan: Generating multi-table datapath from datapath oblivious algorithmic SDN policies,” in Proc. of SIGCOMM, 2016, pp. 593–594. [13] C. Schlesinger, M. Greenberg, and D. Walker, “Concurrent netcore: From policies to pipelines,” in Proc. of ICFP, 2014, pp. 11–24. [14] J. McClurg, H. Hojjat, N. Foster, and P. Cern ˇ y, “Event-driven network ´ programming,” in Proc. of PLDI, 2016, pp. 369–385. [15] M. T. Arashloo, Y. Koral, M. Greenberg, J. Rexford, and D. Walker, “Snap: Stateful network-wide abstractions for packet processing,” in Proc. of SIGCOMM, 2016, pp. 29–43. [16] “P4 runtime,” https://p4.org/p4-runtime/, accessed: 2017-12-27