Controller Placement with Optimal Availability

Abstract

The controller placement problem concerns the placement of controllers on Software-Defined Networks such that a pre-defined objective is optimized. In this thesis, we conduct research on the controller placement problem with network availability as the performance metric. Unlike other approximate evaluations, we compute the exact value with the path decomposition algorithm, which allows us to accurately measure the quality of different placements. After that, we investigate on the graph metrics' effect on network availability and develop a placement strategy based on degree and distance. Greedy algorithm and genetic algorithm are also introduced to address the controller placement problem. We analyze the optimal placement of OS3E network and other 100 real-world networks. We find that different placements affect availability a lot, which indicates that it is necessary to find a strategy to place controller such that a near-optimal placement is achieved. Finally, four placement strategies are tested on Erdős–Rényi random graphs, Barabási–Albert random graphs, and 155 real-world graphs from the Topology Zoo. Results show that the performance of these four strategies is almost same for most networks. However, the complexity of these four methods is very different, which suggests that the controller placement strategy based on graph metrics is efficient.