## 4 OpenFlow Flow Table Memory Management
### Flow Rule Split and Distribute  
Endpoint policies like firewall, load balancer rules are enforced at edge switches. These policies always generate many forwarding rules. Due to insufficient flow table space (TCAM), a set of rules are usually split into small sub-tables and distributed over the network in a way that satisfies policies. The common objective of distributing schemes is to minimize the number of entry rules for realizing policies in each switch. This way, optimization models are presented to decides which rules to be placed on which switch while respecting memory constraint and rule dependency. [PERSON] in [70] is an example of such a scheme, [PERSON] designed a scheme to share rules to individual ingress switch, thereafter, distribute across the network, such switches in the network have smaller sub-tables. They formulate two greedy approaches using a rainbow path coloring problem to optimize the entries in the sub-table. However, balancing the size of each sub-table and reduce rule redundancy concern is noted as the shortcoming of the solution [72]. To address such challenges, [PERSON] et al. [72] present a sub-table allocation algorithm (SA) and size-balancing sub-table partition (SSP) algorithm. This way, the idea of coloring is extended to maximize the number of sub-tables (i.e., number of colors). SA algorithm can partition a large number of sub-tables to reduce table size. Experimentally optimal result were achieved in small network topology, although, compared to Palette [70], SSP can balance all the sub-table sizes with low rule overhead. Moreover, SA plus SSP may occupy little TCAM space to store rules regardless of the topology size. However, the arrival of massive flows in a dynamic large-scale network may impair the stability of the system.  
[PERSON] et al. [73] formalize a split model as decomposition on overlapping rectangles with linear programming (LP) to assign sub rectangles to switches. However, it introduces unwanted traffic because policy enforcement is executed at several hosts after packets entered the network [74], moreover, it may not be possible for distribution to ensure feasible space allocation for each switch in the network. In a similar effort, one big switch (OBS) in [69] considered rule distribution problem under heterogeneous flow rule policy. The author introduces the LP base rule partition approach with two heuristics for rule allocation to calculate suitable rule space allocations for each flow path in each switch and therefore only the rules that affect packets traversing are installed. However, OBS represents endpoint policy rules by five dimensions, the computation cost of table decomposition is impractical [72]. The work of [PERSON] et al. [74] presents table decomposition and sub table allocation for heterogeneous flow table with efficient rule distribution method to balance the number of rules stored along with a path. However, the method may cause incorrect packet forwarding due to the rule dependency problem [72].  
Conversely, [PERSON] et al. [71] proposed OFFICER as a linear optimization model for sub-table allocation under memory and link capacity constraint aimed to calculate and implement efficient forwarding rules in switch memory. OFFICER treats the network as Blackbox, which must satisfy the endpoint policy imposed by the operator, thereby obtaining the maximum from available resources through the adaptation of routes. Therefore, in general, splitting and distributing entries among data forwarding elements can maximize entries. However, it introduces more traffic overhead in the switches to maintain the distribution of forwarding entries, especially when the network topology dynamically changes over time. Moreover, the distribution scheme may be a bottleneck in large scale-network with massive flow arrivals.