TY - JOUR
T1 - Profit maximization for admitting requests with network function services in distributed clouds
AU - Ma, Yu
AU - Liang, Weifa
AU - Xu, Zichuan
AU - Guo, Song
N1 - Publisher Copyright:
© 1990-2012 IEEE.
PY - 2019/5/1
Y1 - 2019/5/1
N2 - Traditional networks employ expensive dedicated hardware devices as middleboxes to implement Service Function Chains of user requests by steering data traffic along middleboxes in the service function chains before reaching their destinations. Network Function Virtualization (NFV) is a promising virtualization technique that implements network functions as pieces of software in servers or data centers. The integration of NFV and Software Defined Networking (SDN) further simplifies service function chain provisioning, making its implementation simpler and cheaper. In this paper, we consider dynamic admissions of delay-aware requests with service function chain requirements in a distributed cloud with the objective to maximize the profit collected by the service provider, assuming that the distributed cloud is an SDN that consists of data centers located at different geographical locations and electricity prices at different data centers are different. We first formulate this novel optimization problem as a dynamic profit maximization problem. We then show that the offline version of the problem is NP-hard and formulate an integer linear programming solution to it. We third propose an online heuristic for the problem. We also devise an online algorithm with a provable competitive ratio for a special case of the problem where the end-to-end delay requirement of each request is negligible. We finally evaluate the performance of the proposed algorithms through experimental simulations. The simulation results demonstrate that the proposed algorithms are promising.
AB - Traditional networks employ expensive dedicated hardware devices as middleboxes to implement Service Function Chains of user requests by steering data traffic along middleboxes in the service function chains before reaching their destinations. Network Function Virtualization (NFV) is a promising virtualization technique that implements network functions as pieces of software in servers or data centers. The integration of NFV and Software Defined Networking (SDN) further simplifies service function chain provisioning, making its implementation simpler and cheaper. In this paper, we consider dynamic admissions of delay-aware requests with service function chain requirements in a distributed cloud with the objective to maximize the profit collected by the service provider, assuming that the distributed cloud is an SDN that consists of data centers located at different geographical locations and electricity prices at different data centers are different. We first formulate this novel optimization problem as a dynamic profit maximization problem. We then show that the offline version of the problem is NP-hard and formulate an integer linear programming solution to it. We third propose an online heuristic for the problem. We also devise an online algorithm with a provable competitive ratio for a special case of the problem where the end-to-end delay requirement of each request is negligible. We finally evaluate the performance of the proposed algorithms through experimental simulations. The simulation results demonstrate that the proposed algorithms are promising.
KW - Network function virtualization
KW - distributed data centers
KW - online algorithms
KW - profit maximization
KW - request admission scheduling
KW - service function chain consolidation
KW - software defined networking
UR - http://www.scopus.com/inward/record.url?scp=85054477184&partnerID=8YFLogxK
U2 - 10.1109/TPDS.2018.2874257
DO - 10.1109/TPDS.2018.2874257
M3 - Article
SN - 1045-9219
VL - 30
SP - 1143
EP - 1157
JO - IEEE Transactions on Parallel and Distributed Systems
JF - IEEE Transactions on Parallel and Distributed Systems
IS - 5
M1 - 8482326
ER -