網路功能虛擬化（Network Function Virtualization, NFV）在現代5G軟體定義網路（Software-Defined Networking, SDN）中扮演著關鍵的角色，其提供了一種多功能且具有成本效益的服務方案。服務供應商（Service Providers, SPs)的收益往往取決於他們能夠滿足的服務請求數量。然而，將虛擬網路功能（Virtual Network Functions, VNFs）部署在網路拓撲中是一項極為複雜的任務，並且已被證明是一個非常困難的NP-hard問題。此外，為了最大化利潤，SPs應該要根據每個VNF的使用情況來調整價格，因此本文引入了分級定價（Tiered Pricing）的概念。本研究的主要焦點是研究當代電腦網路中VNF的部署，同時考慮分級定價策略。本文透過考慮VNF的空間配置以及每個節點的有限容量，旨在優化SPs的利潤。本文提出了一個混合整數二次約束規劃（Mixed Integer Quadratic Constraint Programming, MIQCP）的問題，以最大化SPs的利潤為目標。MIQCP，是一種複雜的最佳化問題形式。在MIQCP中，需要找到一組變數的值，以在特定條件下最大化或最小化一個目標函數。這些變數可以是連續的，也可以是離散的整數。然而，令MIQCP問題更具挑戰性的是，它的約束條件是二次函數，在本文的問題中它包含了變數的平方項，因為在計算各請求所需的VNFs之間的傳輸延遲時，會利用到變數相乘。為了解決這個優化問題，本文提出了一個基於貪婪（Greedy）與模擬退火（Simulated Annealing, SA）的演算法，本文將貪婪演算法的結果作為模擬退火演算法的初始解，以進一步優化其性能。本文所提出的方法有效地考慮了VNF的需求以及服務功能練（Service Function Chain, SFC）的路徑，將VNFs有效地佈署在網路拓撲中。通過實驗結果的驗證，本文所提出的方法在最大化SPs的利潤方面是最優的。這項研究為SPs提供了一個能夠增大其利潤的方法，同時在提供成本效益的多功能服務方面保持了競爭力。

Network Function Virtualization (NFV) is crucial in modern 5G Software-Defined Networking (SDN), offering a versatile and cost-effective service solution. Service Providers' (SPs) revenue often depends on the number of service requests they can fulfill. However, deploying Virtual Network Functions (VNFs) in network topologies is an intricate task and has been proven to be a NP-hard problem. Furthermore, to maximize profits, SPs should adjust prices based on the usage of each VNF. Thus, we introduce the concept of Tiered Pricing. The primary focus of this study is to investigate the deployment of VNFs in contemporary computer networks while considering Tiered Pricing strategies. By considering the spatial arrangement of VNFs and each node's limited capacities, we aim to optimize SPs' profits. We formulate a Mixed Integer Quadratic Constraint Programming (MIQCP) problem to maximize SPs' profits. MIQCP is a complex optimization problem where a set of variable values must be found to maximize or minimize an objective function under specific conditions. These variables can be continuous or discrete integers. However, what adds to the challenge of the MIQCP problem is that its constraint conditions are quadratic functions, with our specific problem involving squared terms of variables. This complexity arises due to the utilization of variable multiplication when calculating the transmission delay between the required VNFs for each request. To address this optimization problem, we propose a hybrid algorithm based on Greedy and Simulated Annealing (SA), where the results from the Greedy algorithm are used as the initial solution for SA to enhance performance further. Our proposed approach effectively considers VNF demands and Service Function Chain (SFC) paths, efficiently deploying VNFs in network topologies. Through experimental validation, our method performs well in maximizing SPs' profits. This study offers SPs a means to maximize their profits while maintaining competitiveness in delivering cost-effective, multifunctional services.

[1] S. Al-Sarawi, M. Anbar, R. Abdullah, and A. B. Al Hawari, "Internet of things market analysis forecasts, 2020–2030," in 2020 Fourth World Conference on smart trends in systems, security and sustainability (WorldS4), 2020: IEEE, pp. 449-453.
[2] N. Alliance, "5G white paper," Next generation mobile networks, white paper, vol. 1, no. 2015, 2015.
[3] S. Zhang, "An overview of network slicing for 5G," IEEE Wireless Communications, vol. 26, no. 3, pp. 111-117, 2019.
[4] A. M. Medhat, T. Taleb, A. Elmangoush, G. A. Carella, S. Covaci, and T. Magedanz, "Service function chaining in next generation networks: State of the art and research challenges," IEEE Communications Magazine, vol. 55, no. 2, pp. 216-223, 2016.
[5] S. Abdelwahab, B. Hamdaoui, M. Guizani, and T. Znati, "Network function virtualization in 5G," IEEE Communications Magazine, vol. 54, no. 4, pp. 84-91, 2016.
[6] J. G. Herrera and J. F. Botero, "Resource allocation in NFV: A comprehensive survey," IEEE Transactions on Network and Service Management, vol. 13, no. 3, pp. 518-532, 2016.
[7] J. Sherry, S. Ratnasamy, and J. S. At, "A survey of enterprise middlebox deployments," EECS Department, University of California, Berkeley, Tech. Rep. UCB/EECS-2012-24, 2012.
[8] J. Garay, J. Matias, J. Unzilla, and E. Jacob, "Service description in the NFV revolution: Trends, challenges and a way forward," IEEE Communications Magazine, vol. 54, no. 3, pp. 68-74, 2016.
[9] G. Etsi, "Network Functions Virtualization (NFV); Architectural Framework," ETsI Gs NFV, vol. 2, p. V1, 2014.
[10] J. Soares et al., "Toward a telco cloud environment for service functions," IEEE Communications Magazine, vol. 53, no. 2, pp. 98-106, 2015.
[11] S. Zhang and B. Lin, "Impact of tiered pricing system on China's urban residential electricity consumption: Survey evidences from 14 cities in Guangxi Province," Journal of Cleaner Production, vol. 170, pp. 1404-1412, 2018.
[12] I. I. Cplex, "V12. 1: User’s Manual for CPLEX," International Business Machines Corporation, vol. 46, no. 53, p. 157, 2009.
[13] H. Hawilo, A. Shami, M. Mirahmadi, and R. Asal, "NFV: state of the art, challenges, and implementation in next generation mobile networks (vEPC)," IEEE network, vol. 28, no. 6, pp. 18-26, 2014.
[14] Y. Yue et al., "Delay-aware and Resource-efficient VNF placement in 6G Non-Terrestrial Networks," in 2023 IEEE Wireless Communications and Networking Conference (WCNC), 2023: IEEE, pp. 1-6.
[15] P. Jin, X. Fei, Q. Zhang, F. Liu, and B. Li, "Latency-aware VNF chain deployment with efficient resource reuse at network edge," in IEEE INFOCOM 2020-IEEE Conference on Computer Communications, 2020: IEEE, pp. 267-276.
[16] M. Emu, P. Yan, and S. Choudhury, "Latency aware VNF deployment at edge devices for IoT services: An artificial neural network based approach," in 2020 IEEE International Conference on Communications Workshops (ICC Workshops), 2020: IEEE, pp. 1-6.
[17] C. Yang, B. Hu, Y. Feng, H. Huang, H. Lai, and J. Tan, "An online service function chain orchestration method for profit maximization in edge computing networks," Engineering Reports, p. e12653, 2023.
[18] M. Golkarifard, C. F. Chiasserini, F. Malandrino, and A. Movaghar, "Dynamic VNF placement, resource allocation and traffic routing in 5G," Computer Networks, vol. 188, p. 107830, 2021.
[19] F. Paganelli, P. Cappanera, A. Brogi, and R. Falco, "Profit-aware placement of multi-flavoured VNF chains," in 2021 IEEE 10th International Conference on Cloud Networking (CloudNet), 2021: IEEE, pp. 48-55.
[20] Y. Ma, W. Liang, Z. Xu, and S. Guo, "Profit maximization for admitting requests with network function services in distributed clouds," IEEE Transactions on Parallel and Distributed Systems, vol. 30, no. 5, pp. 1143-1157, 2018.
[21] G. A. Mills-Tettey, A. Stentz, and M. B. Dias, "The dynamic hungarian algorithm for the assignment problem with changing costs," Robotics Institute, Pittsburgh, PA, Tech. Rep. CMU-RI-TR-07-27, 2007.
[22] Z. Abbasi, M. Shirazipour, and A. Takacs, "An Optimization Case in Support of Next Generation {NFV} Deployment," in 7th USENIX Workshop on Hot Topics in Cloud Computing (HotCloud 15), 2015.
[23] L. Yala, P. A. Frangoudis, and A. Ksentini, "Latency and availability driven VNF placement in a MEC-NFV environment," in 2018 IEEE Global Communications Conference (GLOBECOM), 2018: IEEE, pp. 1-7.
[24] Y.-C. Tai and L.-H. Yen, "Network service embedding in multiple edge systems: profit maximization by federation," in ICC 2021-IEEE International Conference on Communications, 2021: IEEE, pp. 1-6.
[25] H. Moens and F. De Turck, "VNF-P: A model for efficient placement of virtualized network functions," in 10th international conference on network and service management (CNSM) and workshop, 2014: IEEE, pp. 418-423.
[26] S. Mehraghdam, M. Keller, and H. Karl, "Specifying and placing chains of virtual network functions," in 2014 IEEE 3rd international conference on cloud networking (CloudNet), 2014: IEEE, pp. 7-13.
[27] M. Bunyakitanon, X. Vasilakos, R. Nejabati, and D. Simeonidou, "End-to-end performance-based autonomous VNF placement with adopted reinforcement learning," IEEE Transactions on Cognitive Communications and Networking, vol. 6, no. 2, pp. 534-547, 2020.
[28] J. Pei, P. Hong, M. Pan, J. Liu, and J. Zhou, "Optimal VNF placement via deep reinforcement learning in SDN/NFV-enabled networks," IEEE Journal on Selected Areas in Communications, vol. 38, no. 2, pp. 263-278, 2019.
[29] C.-C. Yang, S. Padhy, and J. Chou, "A Hybrid Virtual Network Function Placement Strategy for Maximizing the Profit of Network Service Deployment Over Time-Varying Workloads," IEEE Access, vol. 9, pp. 99983-99994, 2021.
[30] J. Xu and J. A. Fortes, "Multi-objective virtual machine placement in virtualized data center environments," in 2010 IEEE/ACM int'l conference on green computing and communications & int'l conference on cyber, physical and social computing, 2010: IEEE, pp. 179-188.
[31] S. Dasgupta and S. Titman, "Pricing strategy and financial policy," The Review of Financial Studies, vol. 11, no. 4, pp. 705-737, 1998.
[32] K. Schoengold and D. Zilberman, "The economics of tiered pricing and cost functions: Are equity, cost recovery, and economic efficiency compatible goals?," Water Resources and Economics, vol. 7, pp. 1-18, 2014.
[33] Y. Wu, W. Zheng, Y. Zhang, and J. Li, "Reliability-aware VNF placement using a probability-based approach," IEEE Transactions on Network and Service Management, vol. 18, no. 3, pp. 2478-2491, 2021.
[34] A. Bundy and L. Wallen, "Breadth-first search," Catalogue of artificial intelligence tools, pp. 13-13, 1984.
[35] G. Gallo and S. Pallottino, "Shortest path algorithms," Annals of operations research, vol. 13, no. 1, pp. 1-79, 1988.