Fault tolerance in TCAM-limited software defined networks

In Software Defined Networks (SDNs), while a proactive fault tolerance based on the local rerouting approach enables fast failure recovery, it requires to install forwarding rules for the backup paths in the switch Ternary Content Addressable Memory (TCAM) in advance. Since the TCAM size is limited and forwarding rules are long, using large number of forwarding rules for backup paths leads to frequent eviction of flows at the switches. To guarantee the bandwidth requirement for a flow upon a link failure, bandwidth reservation is also required on the backup path. Inefficient backup bandwidth usage will cause rejection of increased number of flows. In this paper, we address the problem of proactive fault tolerance in SDNs, considering the above challenges by adopting the local rerouting approach. We develop an optimization programming formulation that determines the set of backup paths to protect a flow while minimizing the number of additional rules and bandwidth required for the backup paths. Since this problem is computationally prohibitive, we develop two heuristic algorithms, namely Forward Local Rerouting (FLR) and Backward Local Rerouting (BLR) to compute backup paths so as to improve TCAM and bandwidth usage efficiency. We propose a flexible adaptive failure recovery framework that takes the decision of using FLR or BLR based on the network state. We evaluate the proposed algorithms through simulations and compare their performance with the optimal solution. The results show that the proposed algorithms perform very close to the optimal solution and reduce the number of additional rules required to protect a flow by up to 75% compared to the approaches that do not consider the limited size of TCAM. The results also show that the proposed algorithms are effective in terms of backup bandwidth efficiency and meet the carrier-grade requirement with the recovery time below 50 ms.