Network slicing for service-oriented networks under resource constraints

Nan Zhang; Ya Feng Liu; Hamid Farmanbar; Tsung Hui Chang; Mingyi Hong; Zhi Quan Luo

doi:10.1109/JSAC.2017.2760147

Network slicing for service-oriented networks under resource constraints

Nan Zhang, Ya Feng Liu, Hamid Farmanbar, Tsung Hui Chang, Mingyi Hong, Zhi Quan Luo

Electrical and Computer Engineering

Research output: Contribution to journal › Article › peer-review

78 Scopus citations

Abstract

To support multiple on-demand services over fixed communication networks, network operators must allow flexible customization and fast provision of their network resources. One effective approach to this end is network virtualization, whereby each service is mapped to a virtual subnetwork providing dedicated on-demand support to network users. In practice, each service consists of a prespecified sequence of functions, called a service function chain (SFC), while each service function in a SFC can only be provided by some given network nodes. Thus, to support a given service, we must select network function nodes according to the SFC and determine the routing strategy through the function nodes in a specified order. A crucial network slicing problem that needs to be addressed is how to optimally localize the service functions in a physical network as specified by the SFCs, subject to link and node capacity constraints. In this paper, we formulate the network slicing problem as a mixed binary linear program and establish its strong NP-hardness. Furthermore, we propose efficient penalty successive upper bound minimization (PSUM) and PSUM-R(ounding) algorithms, and two heuristic algorithms to solve the problem. Simulation results are shown to demonstrate the effectiveness of the proposed algorithms.

Original language	English (US)
Article number	8058426
Pages (from-to)	2512-2521
Number of pages	10
Journal	IEEE Journal on Selected Areas in Communications
Volume	35
Issue number	11
DOIs	https://doi.org/10.1109/JSAC.2017.2760147
State	Published - Nov 2017

Bibliographical note

Funding Information:
Manuscript received April 1, 2017; revised September 12, 2017; accepted September 25, 2017. Date of publication October 5, 2017; date of current version December 1, 2017. This work was supported in part by the Natural Science Foundation of China under Grant 61571384, Grant 61571385, and Grant 11671419, in part by the Natural Science Foundation under Grant CCF-1526434 and Grant CCF-1526078, in part by AFOSR under Grant 15RT0767, and in part by CUHK (SZ) President Fund under Grant PF.01.000183. (Corresponding author: Ya-Feng Liu.) N. Zhang is with the School of Mathematical Sciences, Peking University, Beijing, China (e-mail: zhangnan625@pku.edu.cn).

Publisher Copyright:
© 1983-2012 IEEE.

Keywords

Network function virtualization
Software defined network
Traffic engineering

Publisher link

10.1109/JSAC.2017.2760147

Find It

Find It at U of M Libraries

Cite this

@article{203ec399128c4d2f98b550fed338e6d8,

title = "Network slicing for service-oriented networks under resource constraints",

abstract = "To support multiple on-demand services over fixed communication networks, network operators must allow flexible customization and fast provision of their network resources. One effective approach to this end is network virtualization, whereby each service is mapped to a virtual subnetwork providing dedicated on-demand support to network users. In practice, each service consists of a prespecified sequence of functions, called a service function chain (SFC), while each service function in a SFC can only be provided by some given network nodes. Thus, to support a given service, we must select network function nodes according to the SFC and determine the routing strategy through the function nodes in a specified order. A crucial network slicing problem that needs to be addressed is how to optimally localize the service functions in a physical network as specified by the SFCs, subject to link and node capacity constraints. In this paper, we formulate the network slicing problem as a mixed binary linear program and establish its strong NP-hardness. Furthermore, we propose efficient penalty successive upper bound minimization (PSUM) and PSUM-R(ounding) algorithms, and two heuristic algorithms to solve the problem. Simulation results are shown to demonstrate the effectiveness of the proposed algorithms.",

keywords = "Network function virtualization, Software defined network, Traffic engineering",

author = "Nan Zhang and Liu, {Ya Feng} and Hamid Farmanbar and Chang, {Tsung Hui} and Mingyi Hong and Luo, {Zhi Quan}",

note = "Funding Information: Manuscript received April 1, 2017; revised September 12, 2017; accepted September 25, 2017. Date of publication October 5, 2017; date of current version December 1, 2017. This work was supported in part by the Natural Science Foundation of China under Grant 61571384, Grant 61571385, and Grant 11671419, in part by the Natural Science Foundation under Grant CCF-1526434 and Grant CCF-1526078, in part by AFOSR under Grant 15RT0767, and in part by CUHK (SZ) President Fund under Grant PF.01.000183. (Corresponding author: Ya-Feng Liu.) N. Zhang is with the School of Mathematical Sciences, Peking University, Beijing, China (e-mail: zhangnan625@pku.edu.cn). Publisher Copyright: {\textcopyright} 1983-2012 IEEE.",

year = "2017",

month = nov,

doi = "10.1109/JSAC.2017.2760147",

language = "English (US)",

volume = "35",

pages = "2512--2521",

journal = "IEEE Journal on Selected Areas in Communications",

issn = "0733-8716",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "11",

}

TY - JOUR

T1 - Network slicing for service-oriented networks under resource constraints

AU - Zhang, Nan

AU - Liu, Ya Feng

AU - Farmanbar, Hamid

AU - Chang, Tsung Hui

AU - Hong, Mingyi

AU - Luo, Zhi Quan

N1 - Funding Information: Manuscript received April 1, 2017; revised September 12, 2017; accepted September 25, 2017. Date of publication October 5, 2017; date of current version December 1, 2017. This work was supported in part by the Natural Science Foundation of China under Grant 61571384, Grant 61571385, and Grant 11671419, in part by the Natural Science Foundation under Grant CCF-1526434 and Grant CCF-1526078, in part by AFOSR under Grant 15RT0767, and in part by CUHK (SZ) President Fund under Grant PF.01.000183. (Corresponding author: Ya-Feng Liu.) N. Zhang is with the School of Mathematical Sciences, Peking University, Beijing, China (e-mail: zhangnan625@pku.edu.cn). Publisher Copyright: © 1983-2012 IEEE.

PY - 2017/11

Y1 - 2017/11

N2 - To support multiple on-demand services over fixed communication networks, network operators must allow flexible customization and fast provision of their network resources. One effective approach to this end is network virtualization, whereby each service is mapped to a virtual subnetwork providing dedicated on-demand support to network users. In practice, each service consists of a prespecified sequence of functions, called a service function chain (SFC), while each service function in a SFC can only be provided by some given network nodes. Thus, to support a given service, we must select network function nodes according to the SFC and determine the routing strategy through the function nodes in a specified order. A crucial network slicing problem that needs to be addressed is how to optimally localize the service functions in a physical network as specified by the SFCs, subject to link and node capacity constraints. In this paper, we formulate the network slicing problem as a mixed binary linear program and establish its strong NP-hardness. Furthermore, we propose efficient penalty successive upper bound minimization (PSUM) and PSUM-R(ounding) algorithms, and two heuristic algorithms to solve the problem. Simulation results are shown to demonstrate the effectiveness of the proposed algorithms.

AB - To support multiple on-demand services over fixed communication networks, network operators must allow flexible customization and fast provision of their network resources. One effective approach to this end is network virtualization, whereby each service is mapped to a virtual subnetwork providing dedicated on-demand support to network users. In practice, each service consists of a prespecified sequence of functions, called a service function chain (SFC), while each service function in a SFC can only be provided by some given network nodes. Thus, to support a given service, we must select network function nodes according to the SFC and determine the routing strategy through the function nodes in a specified order. A crucial network slicing problem that needs to be addressed is how to optimally localize the service functions in a physical network as specified by the SFCs, subject to link and node capacity constraints. In this paper, we formulate the network slicing problem as a mixed binary linear program and establish its strong NP-hardness. Furthermore, we propose efficient penalty successive upper bound minimization (PSUM) and PSUM-R(ounding) algorithms, and two heuristic algorithms to solve the problem. Simulation results are shown to demonstrate the effectiveness of the proposed algorithms.

KW - Network function virtualization

KW - Software defined network

KW - Traffic engineering

UR - http://www.scopus.com/inward/record.url?scp=85031809705&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85031809705&partnerID=8YFLogxK

U2 - 10.1109/JSAC.2017.2760147

DO - 10.1109/JSAC.2017.2760147

M3 - Article

AN - SCOPUS:85031809705

SN - 0733-8716

VL - 35

SP - 2512

EP - 2521

JO - IEEE Journal on Selected Areas in Communications

JF - IEEE Journal on Selected Areas in Communications

IS - 11

M1 - 8058426

ER -

Network slicing for service-oriented networks under resource constraints

Abstract

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this