Efficient greedy heuristic approach for fault-tolerant distributed controller placement in scalable SDN architecture

Software-Defined Network (SDN) enables a centralized networking architecture that employs controllers to administer a global view of the network. However, the architecture of SDN and OpenFlow are susceptible to scalability and reliability issues. In fact, the problem of determining the requisite number of controllers and their locations in SDNs while maximizing the fault tolerance, i.e., Controller Placement Problem (CPP), is NP-hard. Besides, the communication latency between the forwarding nodes and the controllers are usually very high in large-scale SDNs due to sparse deployment. This paper first formulates the CPP as Nonlinear Programming (NLP). Then, we present an efficient greedy heuristic method that employs a local Optimized High Degree and Independent Dominating Set (OHDIDS) strategy to address these issues. In particular, we examine the CPP based on Silhouette analysis, Gap Statistics, and Faster Partitioning Around Medoids (FPAM) techniques. We conduct extensive experiments using Internet Topology Zoo and Mininet network simulators to show the efficacy of the proposed method with various network topologies. The proposed method outperforms the state-of-the-art methods in terms of the minimum number of controllers, average-case and worst-case latency, and reliability. We observed that our method reduces the average communication latency by 57%\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$57\%$$\end{document} when two controllers are used rather than a single controller. Moreover, it achieves a performance gain of up to 19.31%\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$19.31\%$$\end{document} in terms of average propagation latency.