/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 ac￾tion [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 inde￾pendent 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