Position-aware packet loss optimization on service function chain placement

Abstract

The advent of Network Function Virtualization (NFV) and Service Function Chains (SFCs) unleashes the power of dynamic creation of network services using Virtual Network Functions (VNFs). This is of great interest to network operators since poor service quality and resource wastage can potentially hurt their revenue in the long term. However, the study shows with a set of test-bed experiments that packet loss at certain positions (i.e., different VNFs) in an SFC can cause various degrees of resource wastage and performance degradation because of repeated upstream processing and transmission of retransmitted packets.
To overcome this challenge, this study focuses on resource scheduling and deployment of SFCs while considering packet loss positions. This study developed a novel SFC packet dropping cost model and formulated an SFC scheduling problem that aims to minimize overall packet dropping cost as a Mixed-Integer Linear Programming (MILP) and proved that it is NP-hard. In this study, Palos is proposed as an efficient scheme in exploiting the functional characteristics of VNFs and their positions in SFCs for scheduling resources and deployment to optimize packet dropping cost. Extensive experiment results show that Palos can achieve up to 42.73% improvement on packet dropping cost and up to 33.03% reduction on average SFC latency when compared with two other state-of-the-art schemes.

Keywords

Network function virtualization / Resource scheduling / SFC deployment / Packet loss

References

[1] L. Askari, M. Tamizi, O. Ayoub, M. Tornatore, Protection strategies for dynamic VNF placement and service chaining, in: International Conference on Computer Communications and Networks (ICCCN), IEEE, 2021, pp. 1-9.

[2] J. Sun, F. Liu, H. Wang, M. Ahmed, Y. Li, M. Liu, Efficient VNF placement for Poisson arrived traffic, IEEE Trans. Network. Service Manage. 18 (2021) 4277-4293.

[3] W. Liang, L. Cui, F.P. Tso, Low-latency service function chain migration in edge-core networks based on open Jackson networks, J. Syst. Architect. 124 (2022) 102405.

[4] Y. Jiang, X. Wang, T. Zhao, Y. Wang, P. Yu, Deployment algorithm of service function chain with packet loss rate optimization, in: Proceedings of the 9th International Conference on Computer Engineering and Networks, Springer, 2021, pp. 635-645.

[5] T. Subramanya, D. Harutyunyan, R. Riggio, Machine learning-driven service function chain placement and scaling in MEC-enabled 5G networks, Comput. Network. 166 (2020) 106980.

[6] M.A. Khoshkholghi, M.G. Khan, K.A. Noghani, J. Taheri, D. Bhamare, A. Kassler, Z. Xiang, S. Deng, X. Yang, Service function chain placement for joint cost and latency optimization, Mobile Network. Appl. 25 (2020) 2191-2205.

[7] W. Hajji, T.A. Genez, F.P. Tso, L. Cui, I. Phillips, Dynamic network function chain composition for mitigating network latency, in: IEEE Symposium on Computers and Communications (ISCC), IEEE, 2018, pp. 316-321.

[8] L. Cui, F.P. Tso, S. Guo, W. Jia, K. Wei, W. Zhao, Enabling heterogeneous network function chaining, IEEE Trans. Parallel Distr. Syst. 30 (2019) 842-854.

[9] M.F. Bari, S.R. Chowdhury, R. Ahmed, R. Boutaba, On orchestrating virtual network functions, in: The 11th International Conference on Network and Service Management (CNSM), IEEE, 2015, pp. 50-56.

[10] C. Li, L. Cui, A novel NFV schedule optimization approach with sensitivity to packets dropping positions, in: Proceedings of the Workshop on Theory and Practice for Integrated Cloud, Fog and Edge Computing Paradigms, 2018, pp. 23-28.

[11] S.G. Kulkarni, W. Zhang, J. Hwang, S. Rajagopalan, K. Ramakrishnan, T. Wood, M. Arumaithurai, X. Fu, NFVnice: dynamic backpressure and scheduling for NFV service chains, IEEE/ACM Trans. Netw. 28 (2020) 639-652.

[12] C. Pham, N.H. Tran, S. Ren, W. Saad, C.S. Hong, Traffic-aware and energy-efficient vNF placement for service chaining: joint sampling and matching approach, IEEE Trans. Service Comput. 13 (2017) 172-185.

[13] S. Ahvar, M.M. Mirzaei, J. Leguay, E. Ahvar, A.M. Medhat, N. Crespi, R. Glitho, SET: a simple and effective technique to improve cost efficiency of VNF placement and chaining algorithms for network service provisioning, in: The 4th IEEE Conference on Network Softwarization and Workshops (NetSoft), IEEE, 2018, pp. 293-297.

[14] F. Schardong, I. Nunes, A. Schaeffer-Filho, A distributed NFV orchestrator based on BDI reasoning, in: IFIP/IEEE Symposium on Integrated Network and Service Management (IM), IEEE, 2017, pp. 107-115.

[15] Q. Zhang, Y. Xiao, F. Liu, J.C. Lui, J. Guo, T. Wang, Joint optimization of chain placement and request scheduling for network function virtualization, in: IEEE 37^thInternational Conference on Distributed Computing Systems (ICDCS), IEEE, 2017, pp. 731-741.

[16] T. Wang, F. Liu, J. Guo, H. Xu, Dynamic SDN controller assignment in data center networks: stable matching with transfers, in: The 35th Annual IEEE International Conference on Computer Communications, IEEE, 2016, pp. 1-9.

[17] X. Li, C. Qian, Low-complexity multi-resource packet scheduling for network function virtualization, in: IEEE Conference on Computer Communications (INFOCOM), IEEE, 2015, pp. 1400-1408.

[18] J.F. Shortle, J.M. Thompson, D. Gross, C.M. Harris, Fundamentals of Queueing Theory, vol. 399, John Wiley & Sons, 2018, https://doi.org/10.1002/9781119453765.

[19] C. Chekuri, S. Khanna, A polynomial time approximation scheme for the multiple knapsack problem, SIAM J. Comput. 35 (2005) 713-728.

[20] G.D. Forney, The Viterbi algorithm, Proc. IEEE 61 (1973) 268-278.

[21] R. Mijumbi, J. Serrat, J.-L. Gorricho, N. Bouten, F. De Turck, S. Davy, Design and evaluation of algorithms for mapping and scheduling of virtual network functions, in: Proceedings of the 1st IEEE Conference on Network Softwarization (NetSoft), IEEE, 2015, pp. 1-9.

[22] L. Qu, C. Assi, K. Shaban, Delay-aware scheduling and resource optimization with network function virtualization, IEEE Trans. Commun. 64 (2016) 3746-3758.

[23] A. Anthony, S.R. Chowdhury, T. Bai, R. Boutaba, J. Francois, Non-intrusive and workflow-aware virtual network function scheduling in user-space, IEEE Trans. Cloud. Comput. (2020), https://doi.org/10.1109/TCC.2020.3024232,1-1.

[24] H. Yao, M. Xiong, H. Li, L. Gu, D. Zeng, Joint optimization of function mapping and preemptive scheduling for service chains in network function virtualization, Future Generat. Comput. Syst. 108 (2020) 1112-1118.

[25] C. Pham, N.H. Tran, C.S. Hong, Virtual network function scheduling: a matching game approach, IEEE Commun. Lett. 22 (2017) 69-72.

[26] Y. Zhang, F. He, T. Sato, E. Oki, Optimization of network service scheduling with resource sharing and preemption, in: IEEE 20th International Conference on High Performance Switching and Routing (HPSR), IEEE, 2019, pp. 1-6.

[27] L. Zhang, B. Cao, Y. Li, M. Peng, G. Feng, A multi-stage stochastic programming-based offloading policy for fog enabled iot-ehealth, IEEE J. Sel. Area. Commun. 39 (2021) 411-425.

[28] Y. Li, S. Xia, M. Zheng, B. Cao, Q. Liu, Lyapunov optimization-based trade-off policy for mobile cloud offloading in heterogeneous wireless networks, IEEE Trans. Cloud. Comput. 10 (2022) 491-505.

[29] B. Cao, L. Zhang, Y. Li, D. Feng, W. Cao, Intelligent offloading in multi-access edge computing: a state-of-the-art review and framework, IEEE Commun. Mag. 57 (2019) 56-62.

[30] D. Harutyunyan, N. Shahriar, R. Boutaba, R. Riggio, Latency and mobility-aware service function chain placement in 5G networks, IEEE Trans. Mobile Comput. (2020), https://doi.org/10.1109/TMC.2020.3028216,1-1.

[31] L. Liu, S. Guo, G. Liu, Y. Yang, Joint dynamical VNF placement and SFC routing in NFV-enabled SDNs, IEEE Trans. Network. Service Manage. 18 (2021) 4263-4276.

[32] M. Wang, B. Cheng, S. Wang, J. Chen, Availability-and traffic-aware placement of parallelized SFC in data center networks, IEEE Trans. Network. Service Manage. 18 (2021) 182-194.