An In-Switch Rule Caching and Replacement Algorithm in Software Defined Networks

In the software defined networks (SDN), the flow table of an OpenFlow switch is usually implemented by the ternary content addressable memory (TCAM). The TCAM has limited capacity which may cause the flow table overflow problem. To address the problem, related works perform a rule replacement scheme according to either the estimated next- packet arrival time of each flow or the hit count of each rule; however, it may remove a rule whose packets will soon arrive at a switch, especially when the network is unstable. This paper proposes a novel TCAM management scheme named in-switch rule caching and replacement (IRCR) to better deal with the flow table overflow problem. The IRCR replaces a rule according to the expected number of incoming matched flows (EIMF), which can be derived from the inter-arrival time distribution models of the corresponding flows. The uniqueness of the IRCR is that it is designed as an in-switch application to avoid link delays between controllers and switches. Using either captured real network traffic or uniform distribution traffic, the IRCR outperforms related works for both exactly matched rules and wildcard rules in terms of hit ratios. In addition, the IRCR has little overhead to the switch.