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 for￾warding 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 au￾tomatically 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 fine￾grained 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. Distinguish￾ing 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