Solving the controller placement problem (CPP) in an SDN architecture with multiple controllers has a significant impact on control overhead in the network, especially in multihop wireless networks (MWNs). The generated control overhead consists of controller-device and inter-controller communications to discover the network topology, exchange configurations, and set up and modify flow tables in the control plane. However, due to the high complexity of the proposed optimization model to the CPP, heuristic algorithms have been reported to find near-optimal solutions faster for large-scale wired networks. In this paper, the objective is to extend those existing heuristic algorithms to solve a proposed optimization model to the CPP in software- defined multihop wireless networking (SDMWN). Our results demonstrate that using ranking degrees assigned to the possible controller placements, including the average distance to other devices as a degree or the connectivity degree of each placement, the extended heuristic algorithms are able to achieve the optimal solution in small-scale networks in terms of the generated control overhead and the number of controllers selected in the network. As a result, using extended heuristic algorithms, the average number of hops among devices and their assigned controllers as well as among controllers will be reduced. Moreover, these algorithms are able tolower the control overhead in large-scale networks and select fewer controllers compared to an extended algorithm that solves the CPP in SDMWN based on a randomly selected controller placement approach.
KeywordsSoftware-defined Multihop Wireless Networking (SDMWN)Controller Placement Problem (CPP)Control OverheadHeuristic Algorithms
Zahmatkesh, A. and Kunz, T. (2017) Software Defined Multihop Wireless Networks: Promises and Challenges. Journal of Communications and Networks, 19, 546-554. https://doi.org/10.1109/JCN.2017.000094
Oktian, Y.E., Lee, S., Lee, H. and Lam, J. (2017) Distributed SDN Controller System: A Survey on Design Choice. Computer Networks, 121, 100-111. https://doi.org/10.1016/j.comnet.2017.04.038
Hu, T., Guo, Z., Yi, P., Baker, T. and Lan, J. (2018) Multi-Controller Based Software-Defined Networking: A Survey. IEEE Access, 6, 15980-15996. https://doi.org/10.1109/ACCESS.2018.2814738
Zhang, Y., Cui, L., Wang, W. and Zhang, Y. (2018) A Survey on Software Defined Networking with Multiple Controllers. Journal of Network and Computer Applications, 103, 101-118. https://doi.org/10.1016/j.jnca.2017.11.015
Heller, B., Sherwood, R. and McKeown, N. (2012) The Controller Placement Problem. Proceedings of the First Workshop on Hot Topics in Software Defined Networks, Helsinki, 13 August 2012, 7-12. https://doi.org/10.1145/2342441.2342444
Yao, G., Bi, J., Li, Y. and Guo, L. (2014) On the Capacitated Controller Placement Problem in Software Defined Networks. IEEE Communications Letters, 18, 1339-1342. https://doi.org/10.1109/LCOMM.2014.2332341
Sallahi, A. and St-Hilaire, M. (2015) Optimal Model for the Controller Placement Problem in Software Defined Networks. IEEE Communications Letters, 19, 30-33. https://doi.org/10.1109/LCOMM.2014.2371014
Sallahi, A. and St-Hilaire, M. (2017) Expansion Model for the Controller Placement Problem in Software Defined Networks. IEEE Communications Letters, 21, 274-277. https://doi.org/10.1109/LCOMM.2016.2621746
Hu, Y.N., Wang, W.D., Gong, X.Y., Que, X.R. and Cheng, S.D. (2012) On the Placement of Controllers in Software-Defined Networks. Journal of China Universities of Posts and Telecommunications, 19, 92-97. https://doi.org/10.1016/S1005-8885(11)60438-X
Lu, J., Zhang, Z., Hu, T., Yi, P. and Lan, J. (2019) A Survey of Controller Placement Problem in Software-Defined Networking. IEEE Access, 7, 24290-24307. https://doi.org/10.1109/ACCESS.2019.2893283
Abdel-Rahman, M.J., Mazied, E.A., Mackenzie, A., Midkiff, S., Rizk, M.R. and El-Nainay, M. (2017) On Stochastic Controller Placement in Software-Defined Wireless Networks. Proceedings of IEEE Wireless Communications and Networking Conference, WCNC, San Francisco, 19-22 March 2017, 1-6. https://doi.org/10.1109/WCNC.2017.7925942
Zhang, T., Giaccone, P., Bianco, A. and De Domenico, S. (2017) The Role of the Inter-Controller Consensus in the Placement of Distributed SDN Controllers. Computer Communications, 113, 1-13. https://doi.org/10.1016/j.comcom.2017.09.007
Zahmatkesh, A., Kunz, T. and Lung, C.-H. (2020) Cost-Effective Controller Placement Problem for Software Defined Multihop Wireless Networks. Proceedings of the Annual International Conference on Ad Hoc Networks (ADHOCNETS), Virtual Conference, November 2020, 1-17.
Das, T., Sridharan, V. and Gurusamy, M. (2020) A Survey on Controller Placement in SDN. IEEE Communications Surveys Tutorials, 22, 472-503. https://doi.org/10.1109/COMST.2019.2935453
Su, Z. and Hamdi, M. (2015) MDCP: Measurement-Aware Distributed Controller Placement for Software Defined Networks. Proceedings of the International Conference on Parallel and Distributed Systems, Melbourne, 14-17 December 2015, 380-387.
Yao, L., Hong, P., Zhang, W., Li, J. and Ni, D. (2015) Controller Placement and Flow Based Dynamic Management Problem towards SDN. Proceedings of IEEE International Conference on Communication Workshop, London, 8-12 June 2015, 363-368. https://doi.org/10.1109/ICCW.2015.7247206
Ashraf, U. (2018) Placing Controllers in Software-Defined Wireless Mesh Networks. Proceedings of International Conference on Computing, Mathematics and Engineering Technologies (iCoMET), Sukkur, January 2018, 1-4. https://doi.org/10.1109/ICOMET.2018.8346386
Obadia, M., Bouet, M., Rougier, J.L. and Iannone, L. (2015) A Greedy Approach for Minimizing SDN Control Overhead. Proceedings of the 2015 1st IEEE Conference on Network Softwarization (NetSoft), London, 13-17 April 2015, 1-5. https://doi.org/10.1109/NETSOFT.2015.7116135
Ur Rahman, S., Kim, G., Cho, Y. and Khan, A. (2017) Deployment of an SDN-Based UAV Network: Controller Placement and Tradeoff between Control Overhead and Delay. Proceedings of International Conference on Information and Communication Technology Convergence (ICTC), Jeju Island, 18-20 October 2017, 1290-1292. https://doi.org/10.1109/ICTC.2017.8190924
Dvir, A., Haddad, Y. and Zilberman, A. (2019) The Controller Placement Problem for Wireless SDN. Wireless Networks, 25, 4963-4978. https://doi.org/10.1007/s11276-019-02077-5
Kalupahana Liyanage, K.S., Ma, M. and Joo Chong, P.H. (2018) Controller Placement Optimization in Hierarchical Distributed Software Defined Vehicular Networks. Computer Networks, 135, 226-239. https://doi.org/10.1016/j.comnet.2018.02.022
Qin, Q., Poularakis, K., Iosidis, G., Kompella, S. and Tassiulas, L. (2018) SDN Controller Placement with Delay-Overhead Balancing in Wireless Edge Networks. IEEE Transactions on Network and Service Management, 15, 1446-1459. https://doi.org/10.1109/TNSM.2018.2876064
Fourer, R., Gay, D.M. and Kernighan, B.W. (2002) AMPL: A Modeling Language for Mathematical Programming. 2nd Edition, Duxbury Press, Scituate.
CPLEX: Ibm’s Linear Programming Solver. http://www.ilog.com/product/cplex
Czyzyk, J., Mesnier, M.P. and Moré, J.J. (1998) The NEOS Server. IEEE Journal on Computational Science and Engineering, 5, 68-75. https://doi.org/10.1109/99.714603
Gropp, W. and More, J.J. (1997) Optimization Environments and the NEOS Server. In: Buhman, M.D. and Iserles, A., Eds., Approximation Theory and Optimization, Cambridge University Press, Cambridge, 167-182.
Dolan, E.D. (2001) The NEOS Server 4.0 Administrative Quide. Technical Memorandum ANL/MCS-TM-250, Mathematics and Computer Science Division, Argonne National Laboratory, Lemont. https://doi.org/10.2172/822567
The NEOS Server for CPLEX/AMPL. https://neos-server.org/neos/solvers/lp:CPLEX/AMPL.html