Rule Caching Problem in Software Defined Networking

What is it about?

Each network flow in SDN networks, is associated with a set of rules, such as packet forwarding, dropping and modifying, that should be installed at switches in terms of flow table entries along the flow path. SDN-enabled switches maintain flow rules in their local Ternary Content Addressable Memory (TCAM), which support high-speed parallel lookup. In practice, network flow shows various traffic patterns. For example, some are burst transmission while the others have consecutive packet transmissions for a long time. For consecutive transmission, only the first packet experiences the delay of remote processing at the SDN controller, and the rest will be processed by local rules at SDN switches. However, for burst transmission, the corresponding rules cached in switches will be removed between two batches of packets if their interval is greater than the rule expiration time. As a result, remote packet processing would be incurred by the first packet of each batch, leading to a long delay and high processing burden on the SDN controller. A simple approach to reduce the overhead of remote processing is to cache rules at switches within the lifetime of network flow, ignoring the rule expiration time. Unfortunately, SDN switches are equipped with limited-space TCAMs because they are expensive hardware and extremely power-hungry. For instance, it is reported that TCAMs are 400 times more expensive and 100 times more power-consuming per Mbit than RAM-based storage. Since TCAM space is shared by multiple flow in networks, it is inefficient and even infeasible to maintain all rules at local switches. This dilemma motivates us to investigate efficient rule caching schemes for SDN to strive for a fine balance between network performance and TCAM usage.

Featured Image

Why is it important?

(1) This article has been viewed as the first study that focuses on the forwarding-rule caching problem with the objective to minimize the total cost of remote processing and local forwarding table occupation. (2) We propose an offline algorithm by adopting a greedy strategy if the network traffic is given in advance. We also devise two online algorithms with guaranteed competitive ratios. (3) Then, we conduct extensive simulations using real network traffic traces to evaluate the performance of our algorithm proposed. The simulation results demonstrate that our algorithms can remarkably reduce the total cost, and the solutions obtained are near optimal.

Perspectives