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.AsFlow 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