+
Skip to main content
Springer Nature Link
Log in

A density algorithm for controller placement problem in software defined wide area networks

  • Published:
The Journal of Supercomputing Aims and scope Submit manuscript

Abstract

Through decoupling the data plane from the control planes, the Software Defined Network (SDN) improves the network flexibility and has gained much attention from both academia and industry. In order to apply to Wide Area Network (WAN), the logically centralized and physically distributed multi-controller network architecture is proposed. In this situation, how many controllers are required and where they should be placed is a urgent problem to be solved, which is called the Controller Placement Problem (CPP). This paper discusses the joint optimization of latency and required number of controllers considering revenue cost and network architecture. We propose a Density-based Controller Placement Algorithm (DCPA), which can obtain the optimal number of controllers and then divides the entire network into multiple sub-networks adaptively. In each sub-network, the controllers are deployed with the purpose of minimizing the average propagation latency and the worst-case propagation latency between controllers and switches at the same time. We conduct experiments on 8 real network topologies from the OS3E and Internet Topology Zoo to evaluate the performance of algorithm. The results verify that DCPA can always find out the optimal solution with a low time consumption to reduce latency for different network scales, which reduces latency by up to 46, 11 and 7 when compared with Density-Based Controller Placement (DBCP), Pareto-based Optimal COntroller placement (POCO) and Clustering-based Network Partition Algorithm (CNPA), respectively, and reduce the load of controllers by up to 38, 20 and 13 when compared with DBCP, POCO and CNPA, respectively. As a result, our proposed DCPA can decrease the controller cost, propagation latency and controller load simultaneously when solving CPP.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+
from $39.99 /Month
  • Starting from 10 chapters or articles per month
  • Access and download chapters and articles from more than 300k books and 2,500 journals
  • Cancel anytime
View plans

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13

Similar content being viewed by others

Explore related subjects

Discover the latest articles, books and news in related subjects, suggested using machine learning.

Data Availability Statement

The data that support the findings of this study are available from the corresponding author, upon reasonable request.

References

  1. Shirmarz A, Ghaffari A (2020) An autonomic software defined network (SDN) architecture with performance improvement considering. J Inf Syst Telecommun 8(2):121–129

    Google Scholar 

  2. Yousaf FZ, Bredel M, Schaller S, Schneider F (2018) NFV and SDN - key technology enablers for 5G networks. IEEE J Selected Areas Commun 35(11):2468–2478

    Article  Google Scholar 

  3. Hu F, Hao Q, Bao K (2014) A survey on software-defined network and openflow: from concept to implementation. Commun Surv Tutor IEEE 16(4):2181–2206

    Article  Google Scholar 

  4. Kreutz D, Ramos F, Verissimo PE, Rothenberg C, Uhlig S (2014) Software-defined networking: a comprehensive survey. Proceedings of the IEEE 103(1):14–76

  5. Shirmarz A, Ghaffari A (2021) Taxonomy of controller placement problem (cpp) optimization in software defined network (sdn): a survey. J Ambient Intell Humanized Comput 12(12):10473–10498

    Article  Google Scholar 

  6. Sah DK, Praveen kD (2019) 5g applications and architectures. 5G Enabled Secure Wireless Networks :45-68

  7. Li Y, Guan S, Zhang C, Sun W (2020) Parameter optimization model of heuristic algorithms for controller placement problem in large-scale sdn. IEEE Access 8:151668–151680

    Article  Google Scholar 

  8. Guo Z, Liu R, Xu Y, Gushchin A, Walid A, Chao HJ (2017) Star: preventing flow-table overflow in software-defined networks. Comput Netw 125:15–25

    Article  Google Scholar 

  9. Das T, Sridharan V, Gurusamy M (2019) A survey on controller placement in sdn. IEEE Commun Surv Tutor 22(1):472–503

    Article  Google Scholar 

  10. Lange S, Gebert S, Zinner T, Tran-Gia P, Hock D, Jarschel M, Hoffmann M (2015) Heuristic approaches to the controller placement problem in large scale SDN networks. IEEE Trans Netw Serv Manag 12(1):4–17

    Article  Google Scholar 

  11. Wang G, Zhao Y, Huang J, Wu Y (2017) An effective approach to controller placement in software defined wide area networks. IEEE Trans Netw Serv Manag 15(1):344–355

    Article  Google Scholar 

  12. Liao J, Sun H, Wang J, Qi Q, Li K, Li T (2017) Density cluster based approach for controller placement problem in large-scale software defined networkings. Comput Netw 112:24–35

    Article  Google Scholar 

  13. Rodriguez A, Laio A (2014) Clustering by fast search and find of density peaks. Science 344(6191):1492–1496

    Article  Google Scholar 

  14. Heller B, Sherwood R, McKeown N (2012) The controller placement problem. ACM SIGCOMM Computer Commun Rev 42(4):473–478

    Article  Google Scholar 

  15. Han L, Li Z, Liu W, Dai K, Qu W (2016) Minimum control latency of SDN controller placement In: 2016 IEEE Trustcom/BigDataSE/ISPA, pp. 2175–2180 IEEE

  16. Wang G, Zhao Y, Huang J, Duan Q, Li J (2016) A k-means-based network partition algorithm for controller placement in software defined network In: 2016 IEEE International Conference on Communications (ICC), pp 1–6 IEEE

  17. Chen J, Xiong Y-J, Qiu X, He D, Yin H, Xiao C (2022) A cross entropy based approach to minimum propagation latency for controller placement in software defined network. Comput Commun 191:133–144

    Article  Google Scholar 

  18. Sallahi A, St-Hilaire M (2014) Optimal model for the controller placement problem in software defined networks. IEEE Commun Lett 19(1):30–33

    Article  Google Scholar 

  19. Sallahi A, St-Hilaire M (2016) Expansion model for the controller placement problem in software defined networks. IEEE Commun Lett 21(2):274–277

    Article  Google Scholar 

  20. Tanha M, Sajjadi D, Ruby R, Pan J (2018) Capacity-aware and delay-guaranteed resilient controller placement for software-defined wans. IEEE Trans Netw Serv Manag 15(3):991–1005

    Article  Google Scholar 

  21. Aoki H, Nagano J, Shinomiya N (2015) Network partitioning problem to reduce shared information in OpenFlow networks with multiple controllers In: Proc ICN, p. 262

  22. Nagano J, Shinomiya N (2015) Efficient information sharing among distributed controllers of openflow network with bi-connectivity In: 2015 International Conference on Computing, Networking and Communications (ICNC), pp 320–324 IEEE

  23. Chai R, Yang X, Du C, Chen Q (2021) Network cost optimization-based capacitated controller deployment for SDN. Comput Netw 197:108326

    Article  Google Scholar 

  24. Jafarian T, Masdari M, Ghaffari A, Majidzadeh K (2021) A survey and classification of the security anomaly detection mechanisms in software defined networks. Clust Comput 24(4):1–19

    Google Scholar 

  25. Zhang Y, Beheshti N, Tatipamula M (2011) On resilience of split-architecture networks In: 2011 IEEE Global Telecommunications Conference-GLOBECOM 2011, pp 1–6 IEEE

  26. Hu Y-N, Wang W-D, Gong X-Y, Que X-R, Cheng S-D (2012) On the placement of controllers in software-defined networks. J China Univ Posts Telecommun 19:92–171

    Article  Google Scholar 

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

    Article  Google Scholar 

  28. Liu J, Liu J, Xie R (2016) Reliability-based controller placement algorithm in software defined networking. Comput Sci Inf Syst 13(2):547–560

    Article  Google Scholar 

  29. Yao G, Bi J, Li Y, Guo L (2014) On the capacitated controller placement problem in software defined networks. IEEE Commun Lett 18(8):1339–1342

    Article  Google Scholar 

  30. Tanha M, Sajjadi D, Pan J (2016) Enduring node failures through resilient controller placement for software defined networks In: 2016 IEEE Global Communications Conference (GLOBECOM), pp 1–7 IEEE

  31. Yang S, Cui L, Chen Z, Xiao W (2020) An efficient approach to robust sdn controller placement for security. IEEE Trans Netw Serv Manag 17(3):1669–1682

    Article  Google Scholar 

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

  33. Lara A, Gutiérrez MA, Rincón EA (2018) A simulated annealing-based multiobjective optimization algorithm for political districting. IEEE Lat Am Trans 16(6):1723–1731. https://doi.org/10.1109/TLA.2018.8444392

    Article  Google Scholar 

  34. Xiao P, Qu W, Qi H, Li Z, Xu Y (2014) The SDN controller placement problem for WAN In: 2014 IEEE/CIC International Conference on Communications in China (ICCC), pp 220–224. IEEE

  35. Ding CH, He X, Zha H, Gu M, Simon HD (2001) A min-max cut algorithm for graph partitioning and data clustering In: Proceedings 2001 IEEE International Conference on Data Mining, pp 107–114 IEEE

  36. Xiao P, Li Z-y, Guo S, Qi H, Qu W-y, Yu H-s (2016) A k self-adaptive SDN controller placement for wide area networks. Front Information Technol Electron Eng 17(7):620–633

    Article  Google Scholar 

  37. Tian Z, Li X, Ju Y (2007) Spectral clustering based on matrix perturbation theory. Sci China Ser F Information Sci 50(1):63–81

    Article  MathSciNet  MATH  Google Scholar 

  38. Maity I, Dhiman R, Misra S (2022) Enplace: energy-aware network partitioning for controller placement in sdn IEEE Transactions on Green Communications and Networking

  39. Daniels R, Whittaker D (2021) Benchmarking the SDN Switch, Open Netw. Found. SDN Solution Showcase, Menlo Park, CA, USA. [Online]. Available:. https://www.opennetworking.org/images/stories/ sdn-solution-showcase/germany2015/Spirent%20-%20Benchmarking% 20the%20SDN%20Switch.pdf

  40. Corsa’s DP2100 SDN Switching and Routing Platform.: [Online] Available:. http://www.corsa.com/products/dp2100/ (2021)

  41. Barbehenn M (1998) A note on the complexity of dijkstra’s algorithm for graphs with weighted vertices. IEEE Trans Comput 47(2):263

    Article  MathSciNet  MATH  Google Scholar 

  42. Jalili A, Keshtgari M, Akbari R (2018) Optimal controller placement in large scale software defined networks based on modified nsga-ii. Appl Intell 48(9):2809–2823

    Article  Google Scholar 

  43. Kaneko H, Funatsu K (2015) Data density-based fault detection and diagnosis with nonlinearities between variables and multimodal data distributions. Chemom Intell Lab Syst 147:58–65

    Article  Google Scholar 

  44. Zhang Y, Chen S, Yu G (2016) Efficient distributed density peaks for clustering large data sets in mapreduce. IEEE Trans Knowl Data Eng 28(12):3218–3230

    Article  Google Scholar 

  45. Internet2 Open Science: [Online].Available:. http://www.internet2.edu/network/ose/ (2021)

  46. Internet Topology Zoo: [Online].Available:. http://www.topology-zoo.org/ (2021)

  47. Wang G, Zhao Y, Huang J, Winter RM (2017) On the data aggregation point placement in smart meter networks In: 2017 26th International Conference on Computer Communication and Networks (ICCCN), pp 1–6 IEEE

Download references

Acknowledgements

This work is supported by Science and Technology Commission of Shanghai Municipality (STCSM) under grant No.19YF1418300.

Author information

Authors and Affiliations

  1. School of Electronic and Electrical Engineering, Shanghai University of Engineering Science, No.333 Longteng Road, Shanghai, 201620, Shanghai, China

    Dun He, Jue Chen & Xihe Qiu

Authors
  1. Dun He
    View author publications

    Search author on:PubMed Google Scholar

  2. Jue Chen
    View author publications

    Search author on:PubMed Google Scholar

  3. Xihe Qiu
    View author publications

    Search author on:PubMed Google Scholar

Corresponding author

Correspondence to Jue Chen.

Ethics declarations

Conflict of interest

The authors declare that they have no conflicts of interest to this work. We declare that we do not have any commercial or associative interest that represents a conflict of interest in connection with the work submitted.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

He, D., Chen, J. & Qiu, X. A density algorithm for controller placement problem in software defined wide area networks. J Supercomput 79, 5374–5402 (2023). https://doi.org/10.1007/s11227-022-04873-x

Download citation

  • Accepted:

  • Published:

  • Version of record:

  • Issue date:

  • DOI: https://doi.org/10.1007/s11227-022-04873-x

Keywords

点击 这是indexloc提供的php浏览器服务，不要输入任何密码和下载