## 4 OpenFlow Flow Table Memory Management
### Flow Rule Caching  
The use of wildcard rule caching makes multiple flows aggregately, thereby reusing entries among different flows, communication overhead can be drastically reduced. In addition, the cost of policy enforcement and update can be reduced. However, wildcard rules are usually stored with different priorities assigned to resolve conflict between two or more overlapped packets. For example, let \(p\) represents a set of rules R (R1, R2, R3... RN) N-dimensional rules with the following priority order (R1 \(>\) R2 \(>\) R3 \(>\)... RN). There exists rule dependency if the match field of rule R1 overlap at the intersection field of rule R2, and rule R2 priority is higher than R1. Therefore, caching R2 only due to its high matching frequency without caching R1 may result in incorrect packet forwarding. Hence, it is not enough to simply cache the requested rule when there is no available correspondent rule, all other rules with higher priority must be installed to guarantee correct packet forwarding. In such a situation, an extra storage overhead is required, which increases flow table overflow [75]. This has widely gained researchers' interest, as summarize in Table 4.  
Alternatively, it is to rely on additional data paths to process the remaining traffic flow. The recent advancement of technology introduced software switching as part of the same commodity switch, which provides an alternative by storing a large number of rules. To some extent software switch has reduced the storage limitation problem; however, it does not support wildcard rules that match many headers fields. In this situation, the switch must resort to slow processing in user space to handle the first packet of each flow. This causes significant packet processing delay, which may not be suitable for some applications. Thus, based on the nature of the amount of traffic matching switch rule,Katta et al. [11] suggest another option to combine hardware and software (hybrid) switching to get the benefit of both without having to pay for their drawback. But this requires careful distribution of single rule table into multiple tables spanning across heterogeneous data paths to ensure that semantic of single-switch rule table are preserved in the distributed implementation. To some extent, this can offer large storage space to accommodate more traffic. However, the process of forwarding packet to software switch thereby copying it back to TCAMs flow table incurred additional packet processing delay. Such an additional delay is high, which amounts to at least 20 ms, [PERSON] et al. [76]. Subsequently, as the data flow request increases over time, the time augments. In contrast to hybrid switch, other solutions were proposed using commodity switches with no additional resources to use TCAM only to store rules. Rules are partitioned into two; heavy-hitting rules and others. the first partition stored heavy-hitting rules while the remaining rules are placed in the other partition [77]. Therefore, partition in TCAM only nullifies the additional packet processing delays experienced in the hybrid switch, however, the potential rule dependencies caused by wildcards to complicate the installation and removal of the rule. It is very common for higher priority rules to overlap at the intersection field with lower priority rules. When packet matched with multiple overlap rules, the higher priority would be the final match. As a result, a problem of rule dependencies issues arises [31]. Therefore, simply caching the requested rule could potentially lead to incorrect packet forwarding. In such a situation, an extra storage overhead is required, which increases flow table overflow [78]. Moreover, this will block the chance of other new incoming rule and cache miss will increase as well. Consequently, this situation will further increase the packet-in generation and update cost operation. An alternative method is to convert wildcard rules into new micro/exact rules without overlapping [75].