A New Set Covering Controller Placement Problem Model for Large Scale SDNs
Subject Areas : Network Managementاحمد جلیلی 1 * , رضا اکبری 2 , منیژه کشتگری 3
1 - Shiraz University of Technology, Department of Computer Engineering & IT, Shiraz, Iran
2 - Shiraz University of Technology, Department of Computer Engineering & IT, Shiraz, Iran
3 - Shiraz University of Technology, Department of Computer Engineering & IT, Shiraz, Iran
Keywords: Software Defined Networks , Controller Placement Problem , Latency Constraint , Carrier Grade Requirement,
Abstract :
Software Defined Network (SDN) is an emerging architecture that can overcome the challenges facing traditional networks. SDN enables administrator/operator to build a simpler and manageable network. New SDN paradigms are encouraged to deploy multiple (rather than centralized) controllers to monitor the entire system. The Controller Placement Problem (CPP) is one of the key issues in SDN that affects every aspect of it such as scalability, convergence time, fault tolerance and node to controller latency. This problem has been investigated in diverse papers with their major attention paid on optimizing the location of an arbitrary number of controllers. The related works in this area get less attention to two following important issues. i) Bidirectional end-to-end latency between switch and its controller instead of propagation latency, ii) finding the minimal number of controllers that even is a prerequisite for locating them. In this paper, a Set Covering Controller Placement Problem Model (SCCPPM) to find the least number of required controllers with regard to carrier grade latency requirement is proposed. The new model is carried out on a set of 124 graphs from the Internet Topology Zoo and solve them with IBM ILOG CPLEX Optimization package. As expected, our results indicate that the number of required controllers for high resiliency is dependent on topology and network size. As well, in order to achieve carrier grade requirement, 86 percent of topologies must have more than one controller.
[1] Kreutz, D., Ramos, F. M., Verissimo, P. E., Rothenberg, C. E., Azodolmolky, S., & Uhlig, S. (2015). Software-defined networking: A comprehensive survey. Proceedings of the IEEE, 103(1), 14-76.
[2] Jain, S., Kumar, A., Mandal, S., Ong, J., Poutievski, L., Singh, A., and Zolla, J. (2013). B4: Experience with a globally-deployed software defined WAN. ACM SIGCOMM Computer Communication Review, 43(4), 3-14.
[3] Sezer, S., Scott-Hayward, S., Chouhan, P. K., Fraser, B., Lake, D., Finnegan, J., and Rao, N. (2013). Are we ready for SDN? Implementation challenges for software-defined networks. IEEE Communications Magazine, 51(7), 36-43.
[4] Kano, S., Miyazaki, K., Nagata, A., and Chugo, A. (2005, November). Shared segment recovery mechanism in optical networks. In 6th Asia-Pacific Symposium on Information and Telecommunication Technologies (pp. 415-420). IEEE.
[5] Laprie, J. (2005, July). Resilience for the scalability of dependability. In Fourth IEEE International Symposium on Network Computing and Applications (pp. 5-6). IEEE.
[6] Benzekki, K., El Fergougui, A., and Elbelrhiti Elalaoui, A. (2017). Software‐defined networking (SDN): a survey. Security and Communication Networks.
[7] Oliveira, D., Pourvali, M., Bai, H., Ghani, N., Lehman, T., Yang, X., and Hayat, M. (2017, March). A novel automated SDN architecture and orchestration framework for resilient large-scale networks. In SoutheastCon, 2017 (pp. 1-6). IEEE.
[8] Sharma, S., Staessens, D., Colle, D., Pickavet, M., and Demeester, P. (2013). OpenFlow: Meeting carrier-grade recovery requirements. Computer Communications, 36(6), 656-665.
[9] Jivorasetkul, S., Shimamura, M., and Iida, K. (2013, August). Better network latency with end-to-end header compression in SDN architecture. In Communications, Computers and Signal Processing (PACRIM), 2013 IEEE Pacific Rim Conference on (pp. 183-188). IEEE.
[10] Curtis, A. R., Mogul, J. C., Tourrilhes, J., Yalagandula, P., Sharma, P., and Banerjee, S. (2011). DevoFlow: Scaling flow management for high-performance networks. ACM SIGCOMM Computer Communication Review, 41(4), 254-265.
[11] Ng, E., Cai, Z., and Cox, A. L. (2010). Maestro: A system for scalable openflow control. Rice University, Houston, TX, USA, TSEN Maestro-Techn. Rep, TR10-08.
[12] Mambretti, J., Chen, J., Yeh, F., Grossman, R., Nash, P., Heath, A., and Zhang, Z. (2017, March). Designing and deploying a bioinformatics software-defined network exchange (SDX): Architecture, services, capabilities, and foundation technologies. In Innovations in Clouds, Internet and Networks (ICIN), 2017 20th Conference on (pp. 135-142). IEEE.
[13] Canini, M., Salem, I., Schiff, L., Schiller, E. M., and Schmid, S. (2017, June). A self-organizing distributed and in-band SDN control plane. In Distributed Computing Systems (ICDCS), 2017 IEEE 37th International Conference on (pp. 2656-2657). IEEE.
[14] Koponen, T., Casado, M., Gude, N., Stribling, J., Poutievski, L., Zhu, M., and Shenker, S. (2010, October). Onix: A distributed control platform for large-scale production networks. In OSDI (Vol. 10, pp. 1-6).
[15] Heller, B., Sherwood, R., and McKeown, N. (2012, August). The controller placement problem. In Proceedings of the first workshop on Hot topics in software defined networks (pp. 7-12). ACM.
[16] Zhang, Y., Cui, L., Wang, W., and Zhang, Y. (2017). A Survey on Software Defined Networking with Multiple Controllers. Journal of Network and Computer Applications.
[17] McKeown, N., Anderson, T., Balakrishnan, H., Parulkar, G., Peterson, L., Rexford, J., and Turner, J. (2008). OpenFlow: enabling innovation in campus networks. ACM SIGCOMM Computer Communication Review, 38(2), 69-74.
[18] Farahani, R. Z., Asgari, N., Heidari, N., Hosseininia, M., and Goh, M. (2012). Covering problems in facility location: A review. Computers & Industrial Engineering, 62(1), 368-407.
[19] Li, S., and Huang, Y. (2014). Heuristic approaches for the flow-based set covering problem with deviation paths. Transportation Research Part E: Logistics and Transportation Review, 72, 144-158.
[20] Ramos, R. M., Martinello, M., and Rothenberg, C. E. (2013, October). Slickflow: Resilient source routing in data center networks unlocked by openflow. In Local Computer Networks (LCN), 2013 IEEE 38th Conference on (pp. 606-613). IEEE.
[21] Yu, M., Rexford, J., Freedman, M. J., and Wang, J. (2010). Scalable flow-based networking with DIFANE. ACM SIGCOMM Computer Communication Review, 40(4), 351-362.
[22] Tootoonchian, A., Gorbunov, S., Ganjali, Y., Casado, M., and Sherwood, R. (2012). On Controller Performance in Software-Defined Networks. Hot-ICE, 12, 1-6.
[23] Killi, B., and Rao, S. Optimal Model for Failure Foresight Capacitated Controller Placement in Software Defined Networks, (2016, June), Communications Letters, IEEE, 20(6), 1108 - 1111.
[24] Sahoo, K. S., Sarkar, A., Mishra, S. K., Sahoo, B., Puthal, D., Obaidat, M. S., and Sadun, B. (2017). Metaheuristic Solutions for Solving Controller Placement Problem in SDN-based WAN Architecture.
[25] ul Huque, M. T. I., Si, W., Jourjon, G., and Gramoli, V. (2017). Large-Scale Dynamic Controller Placement. IEEE Transactions on Network and Service Management, 14(1), 63-76.
[26] Ruiz-Rivera, A., Chin, K. W., and Soh, S. (2015). Greco: an energy aware controller association algorithm for software defined networks. IEEE Communications Letters, 19(4), 541-544.
[27] He, K., Khalid, J., Das, S., Gember-Jacobson, A., Prakash, C., Akella, A., and Thottan, M. (2015, June). Latency in software defined networks: Measurements and mitigation techniques. In ACM SIGMETRICS Performance Evaluation Review (Vol. 43, No. 1, pp. 435-436). ACM.
[28] Kuźniar, M., Perešíni, P., and Kostić, D. (2015, March). What you need to know about SDN flow tables. In International Conference on Passive and Active Network Measurement (pp. 347-359). Springer International Publishing.
[29] Sood, K., Yu, S., Xiang, Y., and Cheng, H. (2016). A General QoS Aware Flow-Balancing and Resource Management Scheme in Distributed Software-Defined Networks. IEEE Access, 4, 7176-7185.
[30] Rechia, F. S. (2016). An Evaluation of SDN Based Network Virtualization Techniques (Doctoral dissertation, ARIZONA STATE UNIVERSITY). [31] P. Bernier, “NTT Recognized with IBC Award for SDN-based HDTV Service,” September 2013. [Online]. Available: http://www.sdnzone.com/topics/software-defined-network/articles/353466-ntt-recognized-with-ibc-award-sdn-based-hdtv.html.