Reliable controller placement in software-defined networks using reliability covering graph and irregular cellular learning automata

Software-defined networking is a new paradigm in network management that has received much attention in recent years. One of the important challenges in designing software-defined networks (SDNs) is the reliable controller placement problem (RCPP) that is the problem of finding the number and locations of controllers to satisfy the reliability requirements. The high complexity of exact reliability measurement led researchers to use estimation techniques that results in overestimating the number of controllers and incorrect placement. In this paper, we introduce a new concept named reliability covering graph (RCG) that enables us to use the exact reliability measurement (ERM) methods in solving the RCPP with desired level of complexity. To construct the RCG, for each candidate node, a subgraph with the adjustable radius r is extracted from the network graph. In the next step, the RCG is developed by calculating the exact reliability between the central node and any other nodes in the resulting subgraphs. In the last step, the RCG is converted to a machine learning tool named irregular cellular learning automata (ICLA) that determines the number and locations of controllers as well as the switches they cover. To study the efficiency of the proposed method, its performance is compared with the optimal results obtained from the ILP solver. The simulation results of 800 case studies on 100 standard topologies show that the average difference in results is 0.00125. Thanks to our innovative structure RCG, the number of controllers required is significantly reduced compared to previous methods.