## 4 OpenFlow Flow Table Memory Management
### Flow Rule Caching
However, each rule has tens of overlapping rules, slicing the long dependencies chain into non-overlap rules generates a large number of flow entries [78]. This would eventually overwhelm the switch flow table (TCAM) memory. In this way, the extra processing load on the controller to store and update rules is inevitable. Therefore, it is necessary to carefully handle dependency in order to avoid overwhelming the switch flow table memory and avert incorrect packet forwarding. Rule caching algorithms cannot blindly choose and cache the most frequently used rules. Hence, a scheme must be properly designed to choose the most frequently used rule and cache them in the TCAM flow table. Toward this goal, cover-set (CS) was proposed, and it is built based on the hybrid switch. CacheFlow in [11; 73] was the state of art work to design CS, it leveraged on direct acyclic graph (DAG) to represent the wildcard rule dependencies problem by splicing a long dependency chain. CS algorithm creates a small number of new rules that cover many low priority rules that overlapped with other higher priority rules. Rule weight is used to indicate how frequent the rule is being matched. Rules with higher weights are considered as heavy-hitting rules, therefore, such rules are cached in the TCAM flow table while the remaining sets of lower priority rules are forwarded to software switch. [PERSON] [73] noted that CacheFlow only considered a contribution value of each un-cached rule to select the heaviest hitting rules. In contrast, [PERSON] [73] proposed accumulated contribution value (ACV) for a set of rules to further improve the selection of most frequently used rules. The set of related rules that have maximum ACV are cached in TCAM until full. The work in [31] is another example of the CS algorithm. To some extent, CS can accommodate a large number of flow rules, but the merit comes with a cost. CS does not improve the efficiency of TCAM, instead it may increase the chance of flow table overflow as the number of long chain dependencies increase because of the large number of cover-set rules that must be stored in TCAM [77]. In addition, the process of forwarding packet to software switch, thereby copying it back to TCAMs flow table, incurred additional packet processing delay. In general, the weakness of cover-set and similarly [31; 72; 73] relies on their inherent architectures, as these solutions require the installation of software switch for every hardware switch [56] that might need a reorganization of the network cabling and additional resources to host the software switches [59]. In addition, it is difficult to determine the optimal number of needed software switches due to performance reasons. Moreover, forwarding rules that depend on the traffic characteristics must be kept in software switch kernel memory space, which is also limited. Furthermore, the process of software switches over a hardware switch increases packet processing delay to consult the controller and install the missing rules [77]. To this end, a greater number of update operations will be triggered, which also affect the stability of the systems. In contrast to cover-set, partition mechanism in the work of [75; 77; 78], caches flow rules in TCAM without using additional resources. It divides large dependent rules into sub-set and places the most frequent rules in the first partition and less frequent one in the second partition. CAB is the state-of-the-art wildcard rule caching using a partition. [PERSON] et al. [78] used a two-stage flow table pipelining to address the rule dependency problem. The main idea is to divide the flow rule into many small logical storages (buckets) and use a decision tree to partition rules. The design tries to ensure one bucket never overlaps with other buckets, but it is possible for rules to overlap with multiple rules in different buckets. In the first stage, bucket is cached while in the second stage all associated rules are stored.