Varna-based optimization: a novel method for capacitated controller placement problem in SDN

Abstract

Recently, software defined networking (SDN) is a promising paradigm shift that decouples the control plane from the data plane. It can centrally monitor and control the network through softwarization, i.e., controller. Multiple controllers are a necessity of current SDN basedWAN. Placing multiple controllers in an optimum way is known as controller placement problem (CPP). Earlier, solutions of CPP only concentrated on propagation latency but overlooked the capacity of controllers and the dynamic load on switches, which is a significant factor in real networks. In this paper, we develop a novel optimization algorithm named varna-based optimization (VBO) and use it to solve CPP. To the best of our knowledge, this is the first attempt to minimize the total average latency of SDN along with the implementation of TLBO and Jaya algorithms to solve CPP for all twelve possible scenarios. Our experimental results show that TLBO outperforms PSO, and VBO outperforms TLBO and Jaya algorithms in all scenarios for all topologies.

Keywords

SDN / controller placement / CPP / latency / VBO

References

[1] Fundation O N. Software-defined networking: the new norm for networks. ONF White Paper, 2012, 2: 2–6

[2] Fundation O N. SDN Architecture Overview, version 1.0. ONF White Paper, 2013, 1–5

[3] Jammal M, Singh T, Shami A, Asal R, Li Y. Software defined networking: state of the art and research challenges. Computer Networks, 2014, 72: 74–98

[4] Farhady H, Lee H, Nakao A. Software-defined networking: a survey. Computer Networks, 2015, 81: 79–95

[5] Singh A K, Srivastava S. A survey and classification of controller placement problem in SDN. International Journal of Network Management, 2018, 28(3): e2018

[6] Hakiri A, Gokhale A, Berthou P, Schmidt D C, Gayraud T. Software defined networking: challenges and research opportunities for future internet. Computer Networks, 2014, 75: 453–471

[7] Gong Y, Huang W, Wang W, Lei Y. A survey on software defined networking and its applications. Frontiers of Computer Science, 2015,9(6): 827–845

[8] Heller B, Sherwood R, McKeown N. The controller placement problem. In: Proceedings of the 1st Workshop on Hot Topics in Software Defined networks. 2012, 7–12

[9] Ahmed R, Boutaba R. Design considerations for managing wide area software defined networks. IEEE Communications Magazine, 2014, 52(7): 116–123

[10] Lange S, Gebert S, Spoerhase J, Rygielski P, Zinner T, Kounev S, Tran-Gia P. Specialized heuristics for the controller placement problem in large scale SDN networks. In: Proceedings of the 27th International Teletraffic Congress. 2015, 210–218

[11] Tootoonchian A, Gorbunov S, Ganjali Y, Casado M, Sherwood R. On controller performance in software-defined networks. In: Proceedings of the 2nd USENIX Conference on Hot Topics in Management of Internet, Cloud and Enterprise Networks and Services. 2012

[12] Schmid S, Suomela J. Exploiting locality in distributed SDN control. In: Proceedings of the 2nd ACM SIGCOMMWorkshop on Hot Topics in Software Defined Networking. 2013, 121–126

[13] Gao C, Wang H, Zhu F, Zhai L, Yi S. A particle swarm optimization algorithm for controller placement problem in software defined network. In: Proceedings of International Conference on Algorithms and Architectures for Parallel Processing. 2015, 44–54

[14] Dixit A, Hao F, Mukherjee S, Lakshman T, Kompella R. Towards an elastic distributed SDN controller. ACM SIGCOMM Computer Communication Review, 2013, 43(4): 7–12

[15] Gupta D, Jahan R. Inter-SDN controller communication: using border gateway protocol. White Paper by Tata Consultancy Services (TCS), 2014, 1–16

[16] Casado M, Freedman M J, Pettit J, Luo J, McKeown N, Shenker S. Ethane: taking control of the enterprise. ACM SIGCOMM Computer Communication Review, 2007, 37(4): 1–12

[17] Ng E, Cai Z, Cox A. Maestro: a system for scalable openflow control. Rice University, Houston, TX, USA, TSEN Maestro-Techn Rep, TR10-08, 2010

[18] Sherwood R, Kok-kiong Y. Cbench: an open-flow controller benchmarker, 2010

[19] Bari M F, Roy A R, Chowdhury S R, Zhang Q, Zhani M F, Ahmed R, Boutaba R. Dynamic controller provisioning in software defined networks. In: Proceedings of the 9th International Conference on Network and Service Management. 2013, 18–25

[20] Cheng T Y, Wang M, Jia X. QoS-guaranteed controller placement in SDN. In: Proceedings of the Global Communications Conference. 2015, 1–6

[21] Liu J, Liu J, Xie R. Reliability-based controller placement algorithm in software defined networking. Computer Science and Information Systems, 2016, 13(2): 547–560

[22] Yao L, Hong P, Zhang W, Li J, Ni D. Controller placement and flowbased dynamic management problem towards SDN. In: Proceedings of the IEEE International Conference on Communication Workshop. 2015, 363–368

[23] Xiao P, Li Z Y, Guo S, Qi H, Qu W Y, Yu H S. A K self-adaptive SDN controller placement for wide area networks. Frontiers of Information Technology & Electronic Engineering, 2016, 17: 620–633

[24] Cheng G, Chen H, Hu H, Lan J. Dynamic switch migration towards a scalable SDN control plane. International Journal of Communication Systems, 2016, 29(9): 1482–1499

[25] Hock D, Hartmann M, Gebert S, Zinner T, Tran-Gia P. POCOPLC: enabling dynamic pareto-optimal resilient controller placement in SDN networks. In: Proceedings of IEEE Conference on Computer Communications Workshops. 2014, 115–116

[26] Lange S, Gebert S, Zinner T, Tran-Gia P, Hock D, Jarschel M, Gebert S. Heuristic approaches to the controller placement problem in large scale SDN networks. IEEE Transactions on Network and Service Management, 2015, 12(1): 4–17

[27] Perrot N, Reynaud T. Optimal placement of controllers in a resilient SDN architecture. In: Proceedings of the 12th IEEE International Conference on Design of Reliable Communication Networks. 2016, 145–151

[28] Hu Y, Luo T, Beaulieu N C, Deng C. The energy-aware controller placement problem in software defined networks. IEEE Communications Letters, 2017, 21(4): 741–744

[29] Sherwood R, Gibb G, Yap K K, Appenzeller G, Casado M, McKeown N, Parulkar G. FlowVisor: a network virtualization layer. OpenFlow Switch Consortium, Tech. Rep., 2009, 1–14

[30] Liao J, Sun H, Wang J, Qi Q, Li K, Li T. Density cluster based approach for controller placement problem in large-scale software defined networkings. Computer Networks, 2017, 112: 24–35

[31] Yao G, Bi J, Li Y, Guo L. On the capacitated controller placement problem in software defined networks. IEEE Communications Letters, 2014, 18(8): 1339–1342

[32] Knight S, Nguyen H X, Falkner N, Bowden R, Roughan M. The internet topology zoo. IEEE Journal on Selected Areas in Communications, 2011, 29(9): 1765–1775

[33] Hock D, Hartmann M, Gebert S, Jarschel M, Zinner T, Tran-Gia P. Pareto-optimal resilient controller placement in SDN-based core networks. In: Proceedings of the 25th IEEE International Teletraffic Congress. 2013, 1–9

[34] Jalili A, Ahmadi V, Keshtgari M, Kazemi M. Controller placement in software-defined WAN using multi objective genetic algorithm. In: Proceedings of the 2nd IEEE International Conference on Knowledge-Based Engineering and Innovation. 2015, 656–662

[35] Liu S, Wang H, Yi S, Zhu F. NCPSO: a solution of the controller placement problem in software defined networks. In: Proceedings of the International Conference on Algorithms and Architectures for Parallel Processing. 2015, 213–225

[36] Hock D, Gebert S, Hartmann M, Zinner T, Tran-Gia P. POCO framework for Pareto-optimal resilient controller placement in SDN based core networks. In: Proceedings of 2014 IEEE Network Operations and Management Symposium. 2014, 1–2

[37] Sallahi A, St-Hilaire M. Optimal model for the controller placement problem in software defined networks. IEEE Communications Letters, 2015, 19(1): 30–33

[38] Sallahi A, St-Hilaire M. Expansion model for the controller placement problem in software defined networks. IEEE Communications Letters, 2017, 21(2): 274–277

[39] Eberhart R, Kennedy J. A new optimizer using particle swarm theory. In: Proceedings of the 6th IEEE International Symposium on Micro Machine and Human Science. 1995, 39–43

[40] Rao R V, Savsani V J, Vakharia D. Teaching-learning-based optimization: a novel method for constrained mechanical design optimization problems. Computer-Aided Design, 2011, 43(3): 303–315

[41] Rao R V. Jaya: a simple and new optimization algorithm for solving constrained and unconstrained optimization problems. International Journal of Industrial Engineering Computations, 2016, 7(1): 19–34

[42] Akay B, Karaboga D. Artificial bee colony algorithm for large-scale problems and engineering design optimization. Journal of Intelligent Manufacturing, 2012, 23(4): 1001–1014

[43] Liang J, Runarsson T P, Mezura-Montes E, Clerc M, Suganthan P, Coello C C, Deb K. Problem definitions and evaluation criteria for the CEC 2006 special session on constrained real-parameter optimization. Journal of Applied Mechanics, 2006, 41(8): 8–31

[44] Hu Y, Wendong W, Gong X, Que X, Shiduan C. Reliability-aware controller placement for software-defined networks. In: Proceedings of IFIP/IEEE International Symposium on Integrated Network Management. 2013, 672–675

[45] Hu Y, Wang W, Gong X, Que X, Cheng S. On reliability-optimized controller placement for software-defined networks. China Communications, 2014, 11(2): 38–54

[46] Hu Y N, Wang W D, Gong X Y, Que X R, Cheng S D. On the placement of controllers in software-defined networks. The Journal of China Universities of Posts and Telecommunications, 2012, 19: 92–171

[47] Guo M, Bhattacharya P. Controller placement for improving resilience of software-defined networks. In: Proceedings of the 4th IEEE International Conference on Networking and Distributed Computing. 2013, 23–27

[48] ILOG I. CPLEX optimizer. 2012

[49] Ul Huque M T I, Jourjon G, Gramoli V. Revisiting the controller placement problem. In: Proceedings of the 40th IEEE Conference on Local Computer Networks. 2015, 450–453

[50] Ul Huque M T I, Si W, Jourjon G, Gramoli V. Large-scale dynamic controller placement. IEEE Transactions on Network and ServiceManagement, 2017, 14(1): 63–76

[51] Xiao P, Qu W, Qi H, Li Z, Xu Y. The SDN controller placement problem for WAN. In: Proceedings of 2014 IEEE/CIC International Conference on Communications in China. 2014, 220–224

[52] Lantz B, Heller B, McKeown N. A network in a laptop: rapid prototyping for software-defined networks. In: Proceedings of the 9th ACMSIGCOMM Workshop on Hot Topics in Networks. 2010, 1–6

RIGHTS & PERMISSIONS

2019 Higher Education Press and Springer-Verlag GmbH Germany, part of Springer Nature