An efficient and coordinated mapping algorithm in virtualized SDN networks<FootNote> 1 Project supported by the National Natural Science Foundation of China (Nos. 61201209 and 61401499), the Natural Science Foundation of Shaanxi Province, China (No. 2015JM6340), and the Industrial Science and Technology Project of Shaanxi Province, China (No. 2016GY-087) </FootNote>

Abstract

Software-defined networking (SDN) enables the network virtualization through SDN hypervisors to share the underlying physical SDN network among multiple logically isolated virtual SDN networks (vSDNs), each with its own controller. The vSDN embedding, which refers to mapping a number of vSDNs to the same substrate SDN network, is a key problem in the SDN virtualization environment. However, due to the distinctions of the SDN, such as the logically centralized controller and different virtualization technologies, most of the existing embedding algorithms cannot be applied directly to SDN virtualization. In this paper, we consider controller placement and virtual network embedding as a joint vSDN embedding problem, and formulate it into an integer linear programming with objectives of minimizing the embedding cost and the controller-to-switch delay for each vSDN. Moreover, we propose a novel online vSDN embedding algorithm called CO-vSDNE, which consists of a node mapping stage and a link mapping stage. In the node mapping stage, CO-vSDNE maps the controller and the virtual nodes to the substrate nodes on the basis of the controller-to-switch delay and takes into account the subsequent link mapping at the same time. In the link mapping stage, CO-vSDNE adopts the k-shortest path algorithm to map the virtual links. The evaluation results with simulation and Mininet emulation show that the proposed CO-vSDNE not only significantly increases the long-term revenue to the cost ratio and acceptance ratio while guaranteeing low average and maximum controller-to-switch delay, but also achieves good vSDN performance in terms of end-to-end delay and throughput.

Keywords

Software-defined networking (SDN) / Network virtualization / Controller placement / Virtual network embedding / Coordination

References

[1] Andersen, D.G., 2002. Theoretical Approaches to Node Assignment. Available from http://www.cs.cmu.edu/~dga/papers/andersen-assign.ps [Accessed on <Date>Sept. 20, 2010</Date>].

[2] Blenk, A., Basta, A., Reisslein, M., , 2016. Survey on network virtualization hypervisors for software defined networking. IEEE Commun. Surv. Tutor., 18(1):655–685. http://dx.doi.org/10.1109/COMST.2015.2489183

[3] Bozakov, Z., Papadimitriou, P., 2012. AutoSlice: automated and scalable slicing for software-defined networks. Proc. ACM CoNEXT Student Workshop, p.3–4. http://dx.doi.org/10.1145/2413247.2413251

[4] Cheng, X., Su, S., Zhang, Z., , 2011. Virtual network embedding through topology-aware node ranking. ACM SIGCOMM Comput. Commun. Rev., 41(2):38–47. http://dx.doi.org/10.1145/1971162.1971168

[5] Corin, R.D., Gerola, M., Riggio, R., , 2012. VeRTIGO: network virtualization and beyond. European Workshop on Software Defined Networks, p.24–29. http://dx.doi.org/10.1109/EWSDN.2012.19

[6] Demirci, M., Ammar, M., 2014. Design and analysis of techniques for mapping virtual networks to software-defined network substrates. Comput. Commun., 45:1–10. http://dx.doi.org/10.1016/j.comcom.2014.03.008

[7] Di, H., Anand, V., Yu, H.F., 2014. Design of reliable virtual infrastructure with resource sharing. Comput. Netw., 62:137–151. http://dx.doi.org/10.1016/j.bjp.2013.09.022

[8] Ding, J., Huang, T., Liu, J., , 2015. Virtual network embedding based on real-time topological attributes. Front. Inform. Technol. Electron. Eng., 16(2):109–118. http://dx.doi.org/10.1631/FITEE.1400147

[9] Drutskoy, D., Keller, E., Rexford, J., 2013. Scalable network virtualization in software-defined networks. IEEE Internet Comput., 17(2):20–27. http://dx.doi.org/ 10.1109/MIC.2012.144

[10] Eppstein, D., 1998. Finding the k shortest paths. SIAM J. Comput., 28(2):652–673. http://dx.doi.org/10.1137/S0097539795290477

[11] Fischer, A., Botero, J.F., Till Beck, M., , 2013. Virtual network embedding: a survey. IEEE Commun. Surv. Tutor., 15(4):1888–1906. http://dx.doi.org/10.1109/SURV.2013.013013.00155

[12] Heller, B., Sherwood, R., McKeown, N., 2012. The controller placement problem. ACM SIGCOMM Comput. Commun. Rev., 42(4):473–478. http://dx.doi.org/10.1145/2377677.2377767

[13] Hu, Y., Wang, W., Gong, X., , 2013. Reliability-aware controller placement for software-defined networks. Proc. IFIP/IEEE Int. Symp. on Integrated Network Management, p.672–675.

[14] Khan, A., Zugenmaier, A., Jurca, D., , 2012. Network virtualization: a hypervisor for the Internet? IEEE Commun. Mag., 50(1):136–143. http://dx.doi.org/10.1109/MCOM.2012.6122544

[15] Koponen, T., Amidon, K., Balland, P., , 2014. Network virtualization in multi-tenant datacenters. USENIX Conf. on Networked System Design and Implementation, p.203–216.

[16] Lantz, B., Heller, B., McKeown, N., 2010. A network in a laptop: rapid prototyping for software-defined networks. Proc. 9th ACM SIGCOMM Workshop on Hot Topics in Networks, p.19:1–19:6. http://dx.doi.org/10.1145/1868447.1868466

[17] Li, X.L., Wang, H.M., Guo, C.G., , 2012. Topology awareness algorithm for virtual network mapping. J. Zhejiang Univ.-Sci. C (Comput. & Electron.), 13(3):178–186. http://dx.doi.org/10.1631/jzus.C1100282

[18] Li, X.L., Wang, H.M., Ding, B., , 2014. Resource allocation with multi-factor node ranking in data center networks. Fut. Gener. Comput. Syst., 32:1–12. http://dx.doi.org/10.1016/j.future.2013.09.028

[19] Liu, S.H., Cai, Z.P., Xu, H., , 2015. Towards securityaware virtual network embedding. Comput. Netw., 91:151–163. http://dx.doi.org/10.1016/j.comnet.2015.08.014

[20] McKeown, N., Anderson, T., Balakrishnan, H., , 2008. OpenFlow: enabling innovation in campus networks. ACM SIGCOMM Comput. Commun. Rev., 38(2):69–74. http://dx.doi.org/10.1145/1355734.1355746

[21] Mijumbi, R., Serrat, J., Rubio-Loyola, J., , 2014. Dynamic resource management in SDN-based virtualized networks. Int. Conf. on Network and Service Management, p.412–417. http://dx.doi.org/10.1109/CNSM.2014.7014204

[22] Salvadori, E., Corin, R.D., Broglio, A., , 2011. Generalizing virtual network topologies in OpenFlow-based networks. IEEE Global Telecommunications Conf., p.1–6. http://dx.doi.org/10.1109/GLOCOM.2011.6134525

[23] Schrijver, A., 1998. Theory of Linear and Integer Programming. Wiley, New York, USA.

[24] Sherwood, R., Gibb, G., Yap, K.K., , 2010. Can the production network be the testbed? 9th USENIX Symp. on Operating System Design and Implementation, p.1–6.

[25] Su, S., Zhang, Z.B., Liu, A.X., , 2014. Energy-aware virtual network embedding. IEEE/ACM Trans. Netw., 22(5):1607–1620. http://dx.doi.org/10.1109/TNET.2013.2286156

[26] Wang, A.J., Iyer, M., Dutta, R., , 2013. Network virtualization: technologies, perspectives, and frontiers. J. Lightw. Technol., 31(4):523–537.http://dx.doi.org/10.1109/JLT.2012.2213796

[27] Wang, Z.M., Wu, J.X., Wang, Y., , 2014. Survivable virtual network mapping using optimal backup topology in virtualized SDN. China Commun., 11(2):26–37. http://dx.doi.org/10.1109/CC.2014.6821735

[28] Zegura, E.W., Calvert, K.L., Bhattacharjee, S., 1996. How to model an internetwork. 15th Annual Joint Conf. of the IEEE Computer and Communications Societies, p.594–602. http://dx.doi.org/10.1109/INFCOM.1996.493353

[29] Zhou, B., Gao, W., Zhao, S., , 2014. Virtual network mapping for multi-domain data plane in software-defined networks. Int. Conf. on Wireless Communications, Vehicular Technology, Information Theory and Aerospace & Electronic Systems, p.1–5. http://dx.doi.org/10.1109/VITAE.2014.6934439

RIGHTS & PERMISSIONS

2016 Zhejiang University and Springer-Verlag Berlin Heidelberg