JZUS - Journal of Zhejiang University SCIENCE

ENGINEERING Information Technology & Electronic Engineering

Accepted manuscript available online (unedited version)

An efficient and coordinated mapping algorithm in virtualized SDN networks

Author(s): Shui-qing Gong, Jing Chen , Qiao-yan Kang, Qing-wei Meng, Qing-chao Zhu , Si-yi Zhao
Affiliation(s): College of Information and Navigation, Air Force Engineering University, Xi’an 710077, China
Corresponding email(s): gsq0121@126.com
Key Words: Software-defined networking (SDN), Network virtualization, Controller placement, Virtual network embedding, Coordination

Share this article to： More <<< Previous Paper \|

Shui-qing Gong, Jing Chen , Qiao-yan Kang, Qing-wei Meng, Qing-chao Zhu , Si-yi Zhao. An efficient and coordinated mapping algorithm in virtualized SDN networks[J]. Frontiers of Information Technology & Electronic Engineering,in press.https://doi.org/10.1631/FITEE.1500387

@article{title="An efficient and coordinated mapping algorithm in virtualized SDN networks",
author="Shui-qing Gong, Jing Chen , Qiao-yan Kang, Qing-wei Meng, Qing-chao Zhu , Si-yi Zhao",
journal="Frontiers of Information Technology & Electronic Engineering",
year="in press",
publisher="Zhejiang University Press & Springer",
doi="https://doi.org/10.1631/FITEE.1500387"
}

%0 Journal Article
%T An efficient and coordinated mapping algorithm in virtualized SDN networks
%A Shui-qing Gong
%A Jing Chen
%A Qiao-yan Kang
%A Qing-wei Meng
%A Qing-chao Zhu
%A Si-yi Zhao
%J Frontiers of Information Technology & Electronic Engineering
%P 701-716
%@ 2095-9184
%D in press
%I Zhejiang University Press & Springer
doi="https://doi.org/10.1631/FITEE.1500387"

TY - JOUR
T1 - An efficient and coordinated mapping algorithm in virtualized SDN networks
A1 - Shui-qing Gong
A1 - Jing Chen
A1 - Qiao-yan Kang
A1 - Qing-wei Meng
A1 - Qing-chao Zhu
A1 - Si-yi Zhao
J0 - Frontiers of Information Technology & Electronic Engineering
SP - 701
EP - 716
%@ 2095-9184
Y1 - in press
PB - Zhejiang University Press & Springer
ER -
doi="https://doi.org/10.1631/FITEE.1500387"

Abstract
Chinese Summary
Academic Network
Reviewer Comment

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.

Abstract: This paper formulates the SDN controller placement and the virtual network embedding as an integer linear programming with objectives to minimize the embedding cost and the controller-to-switch delay for each request vSDN. The authors propose a two-phase embedding algorithm which consists of a node mapping stage and a link mapping stage. Authors claimed that simulation results show the proposed vSDNE approach significantly increases the long-term revenue to cost ratio and acceptance ratio while guaranteeing a lower controller-to-switch delay. It is a well written paper and the presented approach sounds standard. The goal is very all-encompassing. The authors provide a reasonable solution strategy to the problem.

面向虚拟SDN网络的高效协调映射算法

目的：针对SDN网络虚拟化环境，考虑虚拟网络映射和控制器部署，以最小化交换机到控制器的平均时延和映射开销为目标，建立虚拟SDN网络(vSDN)映射问题的数学模型，并提出一种高效协调的虚拟SDN网络映射算法。
创新点：基于底层节点和链路的可用资源数量、底层节点间的时延和距离等因素，提出一种支持时延优化的高效协调虚拟SDN网络映射算法。
方法：将vSDN中的控制器作为一个特殊的虚拟节点，在vSDN映射过程中同时进行控制器的优化部署，并以最小化交换机到控制器的平均时延和底层SDN网络映射开销为目标，建立vSDN映射的整数线性规划模型，并提出一种支持时延优化的高效协调vSDN映射算法。该算法在节点映射阶段首先进行控制器的部署，然后进行虚拟节点的映射。在控制器部署过程中，考虑底层节点可用资源和节点之间的通信时延，引入控制器位置选择因子(CLSF)对底层节点进行排序，并将vSDN的控制器映射到CLSF值最大的底层节点上。在虚拟节点映射过程中，首先构建虚拟节点的映射树，并考虑底层节点可用资源、底层节点到控制器的时延和距离等因素，引入节点映射因子(NR)对底层节点进行排序。然后按照广度优先搜索策略将虚拟节点映射至NR值最大的底层节点上。节点映射完成后，采用k最短路径法映射虚拟链路。
结论：本文提出的虚拟SDN网络映射算法能够有效协调控制器部署、虚拟节点映射和链路映射三个阶段，保持了较高的映射收益开销比和vSDN请求接受率，并有效降低了交换机到控制器的时延(图3-6)。

关键词组：软件定义网络；网络虚拟化；控制器部署；虚拟网络映射；协调

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

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

[2]Blenk, A., Basta, A., Reisslein, M., et al., 2016. Survey on network virtualization hypervisors for software defined networking. IEEE Commun. Surv. Tutor., 18(1):655-685.

[3]Bozakov, Z., Papadimitriou, P., 2012. AutoSlice: automated and scalable slicing for software-defined networks. Proc. ACM CoNEXT Student Workshop, p.3-4.

[4]Cheng, X., Su, S., Zhang, Z., et al., 2011. Virtual network embedding through topology-aware node ranking. ACM SIGCOMM Comput. Commun. Rev., 41(2):38-47.

[5]Corin, R.D., Gerola, M., Riggio, R., et al., 2012. VeRTIGO: network virtualization and beyond. European Workshop on Software Defined Networks, p.24-29.

[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.

[7]Di, H., Anand, V., Yu, H.F., 2014. Design of reliable virtual infrastructure with resource sharing. Comput. Netw., 62:137-151.

[8]Ding, J., Huang, T., Liu, J., et al., 2015. Virtual network embedding based on real-time topological attributes. Front. Inform. Technol. Electron. Eng., 16(2):109-118.

[9]Drutskoy, D., Keller, E., Rexford, J., 2013. Scalable network virtualization in software-defined networks. IEEE Internet Comput., 17(2):20-27.

[10]Eppstein, D., 1998. Finding the k shortest paths. SIAM J. Comput., 28(2):652-673.

[11]Fischer, A., Botero, J.F., Till Beck, M., et al., 2013. Virtual network embedding: a survey. IEEE Commun. Surv. Tutor., 15(4):1888-1906.

[12]Heller, B., Sherwood, R., McKeown, N., 2012. The controller placement problem. ACM SIGCOMM Comput. Commun. Rev., 42(4):473-478.

[13]Hu, Y., Wang, W., Gong, X., et al., 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., et al., 2012. Network virtualization: a hypervisor for the Internet IEEE Commun. Mag., 50(1):136-143.

[15]Koponen, T., Amidon, K., Balland, P., et al., 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.

[17]Li, X.L., Wang, H.M., Guo, C.G., et al., 2012. Topology awareness algorithm for virtual network mapping. J. Zhejiang Univ.-Sci. C (Comput. & Electron.), 13(3):178-186.

[18]Li, X.L., Wang, H.M., Ding, B., et al., 2014. Resource allocation with multi-factor node ranking in data center networks. Fut. Gener. Comput. Syst., 32:1-12.

[19]Liu, S.H., Cai, Z.P., Xu, H., et al., 2015. Towards security-aware virtual network embedding. Comput. Netw., 91:151-163.

[20]McKeown, N., Anderson, T., Balakrishnan, H., et al., 2008. OpenFlow: enabling innovation in campus networks. ACM SIGCOMM Comput. Commun. Rev., 38(2):69-74.

[21]Mijumbi, R., Serrat, J., Rubio-Loyola, J., et al., 2014. Dynamic resource management in SDN-based virtualized networks. Int. Conf. on Network and Service Management, p.412-417.

[22]Salvadori, E., Corin, R.D., Broglio, A., et al., 2011. Generalizing virtual network topologies in OpenFlow-based networks. IEEE Global Telecommunications Conf., p.1-6.

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

[24]Sherwood, R., Gibb, G., Yap, K.K., et al., 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., et al., 2014. Energy-aware virtual network embedding. IEEE/ACM Trans. Netw., 22(5):1607-1620.

[26]Wang, A.J., Iyer, M., Dutta, R., et al., 2013. Network virtualization: technologies, perspectives, and frontiers. J. Lightw. Technol., 31(4):523-537.

[27]Wang, Z.M., Wu, J.X., Wang, Y., et al., 2014. Survivable virtual network mapping using optimal backup topology in virtualized SDN. China Commun., 11(2):26-37.

[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.

[29]Zhou, B., Gao, W., Zhao, S., et al., 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.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

- Go to

面向虚拟SDN网络的高效协调映射算法

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference