Byzantine-Resilient Controller Mapping and Remapping in Software Defined Networks

In software-defined networks, a compromised controller that is Byzantine in nature would issue inconsistent messages selectively to its communicating nodes. Defending against such threats is very challenging since the infected messages look legitimate. To defend against $f$ simultaneous controller failures using the conventional Byzantine fault tolerance approach requires a switch to be mapped to $3f+1$ controllers. This approach increases the network load due to multiple requests from switches and also requires a large number of controllers for the entire network. In this paper, we propose a novel primary-backup controller mapping approach in which a switch is mapped to only $f+1$ primary and $f$ backup controllers to defend against $f$ simultaneous controller failures. We develop an optimization programming formulation for the switch-controller mapping problem that minimizes the number of controllers required considering latency and capacity constraints. We also develop an optimization programming formulation for the remapping problem upon a controller failure, minimizing the number of remappings of unaffected switches. Since the optimization formulations are computationally prohibitive, we develop heuristic algorithms for both problems. The performance study shows that the optimal mapping requires up to 50% fewer controllers compared to an existing scheme and the heuristics perform within $8\%$ of the optimum.