隨著網路的蓬勃發展，使用者對網路服務的需求日漸增大，使用者根據自身使用服務的不同，會有不同的服務品質要求；5G網路透過網路切片來滿足不同的服務品質需求與資源分配，而且由於網路切片能夠有效地區隔資源，所以能夠滿足多租戶範例。在多租戶的情境下，每個租戶都會提出網路切片請求，但根據觀察過去的歷史資料，網路切片請求可能會有超額預定的情況發生，所以必須要有預測機制來修正網路切片的資源使用量；因此，對雲端供應商而言，在滿足租戶服務等級協議的前提下，如何有效地利用資源將會是一個重要的議題。
本研究將網路切片之間資源分配與利用問題定義為二維裝箱問題，並且基於網路切片請求之二維裝箱問題提出兩個概念：(1) 時間連續性資源區塊 (2) 滑動資源區塊，藉此來最大化資源利用率。為了將此問題應用於5G核心網路，本研究在5G雲原生核心網路環境提出基於利用率預測之網路切片調度架構，並提出二維網路切片裝箱演算法來解決此問題，此演算法基於修改二元樹裝箱演算法來滿足上述提到的兩個概念，並且透過兩層式裝箱架構達到最大化資源利用率與最大化收益。本系統透過Kubernetes與NCTU free5GC將5G核心網路建構於實際雲原生之環境，並且透過Prometheus與Grafana將網路切片之間的調度結果圖形視覺化。實驗部分將比較不同走訪順序之二元樹裝箱演算法，在不同網路切片請求資料情境與是否有預測資料差異上的差異。

Users’ demands for network service are growing along with flourishing technology. There are many Qualities of Service (QoS) requirements according to the service which user uses. 5G network satisfies QoS requirements and resource allocation of various services by network slicing, and network slicing enables the multi-tenancy paradigm owing to the resource partitioning. In the environment of multi-tenancy, tenants will propose the network slice request to use the network slice, but there might be a situation of overbooking of the network slice request, when observing the history data of past resource utilization. As a result, there must be a forecasting mechanism to adjust the resource requirement of network slice. Therefore, for cloud providers, how to effectively use resources will be an important issue under the premise of satisfying the Service Level Agreement (SLA) of each tenant.
In this thesis, we define two-dimensional bin packing problem for resource allocation and utilization between network slices, and we also propose two concepts: (1) time continuity resource blocks, (2) sliding dependent resource blocks, which are based on two-dimensional bin packing problem for network slice request, to maximize the resource utilization. In order to apply this problem to 5G core network, we propose Network Slicing Orchestration Architecture in 5G cloud-native core network based on utilization forecasting and solving this problem by two-dimensional Network Slicing Bin Packing Algorithm. This algorithm is based on binary tree bin packing algorithm, and is modified to suit the requirements of two concepts that we mention above; moreover, it maximizes the resource utilization and profit further by two-layer bin packing architecture. We implement 5G core network in real world cloud-native environment through Kubernetes and NCTU free5GC, and use Prometheus and Grafana to visualize the results of orchestration between network slices. In the experiment, we compare the variation of different tree traversal of binary tree bin packing algorithm and whether forecasted data is existed or not in different network slice request dataset.

[1] A. Gupta and R. K. Jha, "A Survey of 5G Network: Architecture and Emerging Technologies," IEEE Access, vol. 3, pp. 1206-1232, 2015.
[2] E. Hossain and M. Hasan, "5G Cellular: Key Enabling Technologies and Research Challenges," IEEE Instrumentation & Measurement Magazine, vol. 18, no. 3, pp. 11-21, 2015.
[3] R. Mijumbi, J. Serrat, J. Gorricho, N. Bouten, F. De Turck and R. Boutaba, "Network Function Virtualization: State-of-the-Art and Research Challenges," IEEE Communications Surveys & Tutorials, vol. 18, no. 1, pp. 236-262, 2016.
[4] S. O. Oladejo and O. E. Falowo, "5G Network Slicing: A Multi-Tenancy Scenario," 2017 Global Wireless Summit (GWS), pp. 88-92, 2017.
[5] J. Prados-Garzon, A. Laghrissi, M. Bagaa, T. Taleb and J. M. Lopez-Soler, "A Complete LTE Mathematical Framework for the Network Slice Planning of the EPC," IEEE Transactions on Mobile Computing, vol. 19, no. 1, pp. 1-14, 2020.
[6] J. X. Salvat, L. Zanzi, A. Garcia-Saavedra, V. Sciancalepore and X. Costa-Pérez, "Overbooking Network Slices through Yield-driven End-to-End Orchestration," Proceedings of the 14th International Conference on emerging Networking EXperiments and Technologies, pp. 353-365, 2018.
[7] Binary Tree Bin Packing Algorithm, Available on July 13, 2021: https://codeincomplete.com/articles/bin-packing/
[8] Prometheus, Available on July 13, 2021: https://prometheus.io
[9] Grafana, Available on July 13, 2021: https://grafana.com/grafana/
[10] S. Nanda and T. Chiueh, "A Survey on Virtualization Technologies," RPE Report, pp. 1-42, 2005.
[11] H.-J. Ku, J.-H. Jung and G.-I. Kwon, "A Study on Reinforcement Learning based SFC Path Selection in SDN/NFV," International Journal of Applied Engineering Research, vol. 12, no. 12, pp. 3439-3443, 2017.
[12] B. Dab, I. Fajjari, M. Rohon, C. Auboin and A. Diquélou, "Cloud-native Service Function Chaining for 5G based on Network Service Mesh," ICC 2020 - 2020 IEEE International Conference on Communications (ICC), pp. 1-7, 2020.
[13] A. Abdelsalam, F. Clad, C. Filsfils, S. Salsano, G. Siracusano and L. Veltri, " Implementation of Virtual Network Function Chaining through Segment Routing in a Linux-based NFV Infrastructure," 2017 IEEE Conference on Network Softwarization (NetSoft), pp. 1-5, 2017.
[14] D. Lee, J. -H. Yoo and J. W. -K. Hong, "Deep Q-Networks based Auto-scaling for Service Function Chaining," 2020 16th International Conference on Network and Service Management (CNSM), pp. 1-9, 2020.
[15] S. I. Kim and H. S. Kim, "A Research on Dynamic Service Function Chaining Based on Reinforcement Learning Using Resource Usage," 2017 Ninth International Conference on Ubiquitous and Future Networks (ICUFN), pp. 582-586, 2017.
[16] G. Li, H. Zhou, B. Feng, G. Li, T. Li, Q. Xu and W. Quan, "Fuzzy Theory Based Security Service Chaining for Sustainable Mobile-Edge Computing," Mobile Information Systems, vol. 2017, pp. 1-13, 2017.
[17] S. Park, H. -G. Kim, J. Hong, S. Lange, J. -H. Yoo and J. W. -K. Hong, "Machine Learning-based Optimal VNF Deployment," 2020 21st Asia-Pacific Network Operations and Management Symposium (APNOMS), pp. 67-72, 2020.
[18] S. Pandey, J. W. -K. Hong and J. -H. Yoo, "Q-Learning based SFC deployment on Edge Computing Environment," 2020 21st Asia-Pacific Network Operations and Management Symposium (APNOMS), pp. 220-226, 2020.
[19] Y. -T. Chen and W. Liao, "Mobility-Aware Service Function Chaining in 5G Wireless Networks with Mobile Edge Computing," ICC 2019 - 2019 IEEE International Conference on Communications (ICC), pp. 1-6, 2019.
[20] B. Han, V. Gopalakrishnan, L. Ji and S. Lee, "Network Function Virtualization Challenges and Opportunities for Innovations," IEEE Communications Magazine, vol. 53, no. 2, pp. 90-97, 2015.
[21] Linux New API (NAPI), Available on July 13, 2021: https://wiki.linuxfoundation.org/networking/napi
[22] Data Plane Development Kit (DPDK), Available on July 13, 2021: https://www.dpdk.org
[23] free5GC, Available on July 13, 2021: https://www.free5gc.org/
[24] S. Kekki, W. Featherstone, Y. Fang, P. Kuure, A. Li, A. Ranjan, D. Purkayastha, F. Jiangping, D. Frydman, G. Verin, K. -W. Wen, K. Kim, R. Arora, A. Odgers, L. M. Contreras and S. Scarpina, "MEC in 5G networks," ETSI White Paper, no. 28, pp. 1-28, 2018.
[25] MongoDB, Available on July 13, 2021: https://www.mongodb.com/
[26] sysctl, Available on July 13, 2021: https://en.wikipedia.org/wiki/Sysctl
[27] Linux iptalbes, Available on July 13, 2021: https://en.wikipedia.org/wiki/Iptables
[28] 3GPP TR 28.801, "3rd Generation Partnership Project; Technical Specification Group Services and System Aspects; Telecommunication management; Study on management and orchestration of network slicing for next generation network (Release 15)," v15.1.0, 2018.
[29] ETSI TS 123 003, "Digital cellular telecommunications system (Phase 2+) (GSM); Universal Mobile Telecommunications System (UMTS); Numbering, addressing and identification (3GPP TS 23.003 version 15.4.0 Release 15)," v15.4.0, 2018.
[30] ETSI GR NFV-EVE 012, "Network Functions Virtualisation (NFV) Release 3; Evolution and Ecosystem; Report on Network Slicing Support with ETSI NFV Architecture Framework," v3.1.1, 2017.
[31] ETSI TS 138 300, "5G; NR; Overall description; Stage-2 (3GPP TS 38.300 version 15.5.0 Release 15)," v15.5.0, 2019.
[32] ETSI TS 123 501, "5G; System architecture for the 5G System (5GS) (3GPP TS 23.501 version 16.6.0 Release 16)," v16.6.0, 2020.
[33] I. M. A. Jawarneh, P. Bellavista, F. Bosi, L. Foschini, G. Martuscelli, R. Montanari and A. Palopoli, "Container Orchestration Engines: A Thorough Functional and Performance Comparison," ICC 2019 - 2019 IEEE International Conference on Communications (ICC), pp. 1-6, 2019.
[34] MetalLB, Available on July 13, 2021: https://metallb.universe.tf/
[35] Container Network Interface, Available on July 13, 2021: https://github.com/containernetworking/cni
[36] Multiple network interfaces overview and examples, Available on July 13, 2021: https://cloud.google.com/vpc/docs/multiple-interfaces-concepts
[37] Cloud Native Networking Design, Available on July 13, 2021: https://docs.vmware.com/en/VMware-Telco-Cloud-Platform---5G-Edition/1.0/telco-cloud-platform-5G-edition-reference-architecture-guide-10/GUID-81109C7A-A6F9-4FEA-A9F3-443D919BF19A.html
[38] Multus-CNI, Available on July 13, 2021: https://github.com/k8snetworkplumbingwg/multus-cni
[39] Kube-OVN, Available on July 13, 2021: https://github.com/kubeovn/kube-ovn
[40] S. Dutta, T. Taleb and A. Ksentini, "QoE-aware Elasticity Support in Cloud-Native 5G Systems," ICC 2016 - 2016 IEEE International Conference on Communications (ICC), pp. 1-6, 2016.
[41] T. Taleb, A. Ksentini and B. Sericola, "On Service Resilience in Cloud-Native 5G Mobile Systems," IEEE Journal on Selected Areas in Communications, vol. 34, no. 3, pp. 483-496, 2016.
[42] A. Shorov, "5G Testbed Development for Network Slicing Evaluation," 2019 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (EIConRus), pp. 39-44, 2019.
[43] D. Lake, G. Foster, S. Vural, Y. Rahulan, B. -H. Oh, N. Wang and R. Tafazolli, "Virtualising and Orchestrating a 5G Evolved Packet Core Network," 2017 IEEE Conference on Network Softwarization (NetSoft), pp. 1-5, 2017.
[44] S. Chen, C. -N. Lee and M. -F. Lee, "Realization of 5G Network Slicing Using Open Source Softwares," 2020 Asia-Pacific Signal and Information Processing Association Annual Summit and Conference (APSIPA ASC), pp. 1549-1556, 2020.
[45] K. Samdanis, X. Costa-Perez and V. Sciancalepore, "From Network Sharing to Multi-Tenancy: The 5G Network Slice Broker," IEEE Communications Magazine, vol. 54, no. 7, pp. 32-39, 2016.
[46] V. Sciancalepore, K. Samdanis, X. Costa-Perez, D. Bega, M. Gramaglia and A. Banchs, "Mobile Traffic Forecasting for Maximizing 5G Network Slicing Resource Utilization," IEEE INFOCOM 2017 - IEEE Conference on Computer Communications, pp. 1-9, 2017.
[47] L. Zanzi, J. X. Salvat, V. Sciancalepore, A. G. Saavedra and X. Costa-Perez, "Overbooking Network Slices End-to-End: Implementation and Demonstration," ACM SIGCOMM 2018 Conference on Posters and Demos (SIGCOMM '18), pp. 144–146, 2018.
[48] L. Zanzi, J. X. Salvat, V. Sciancalepore, A. Garcia-Saavedra and X. Costa-Pérez, "Latency-driven Network Slices Orchestration," IEEE INFOCOM 2019 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pp. 965-966, 2019.
[49] K. Katsalis, N. Nikaein, E. Schiller, A. Ksentini and T. Braun, "Network Slices toward 5G Communications: Slicing the LTE Network," IEEE Communications Magazine, vol. 55, no. 8, pp. 146-154, 2017.
[50] X. Li, R. Ni, J. Chen, Y. Lyu, Z. Rong and R. Du, "End-to-End Network Slicing in Radio Access Network, Transport Network and Core Network Domains," IEEE Access, vol. 8, pp. 29525-29537, 2020.
[51] F. Meneses, M. Fernandes, D. Corujo and R. L. Aguiar, "SliMANO: An Expandable Framework for the Management and Orchestration of End-to-end Network Slices," 2019 IEEE 8th International Conference on Cloud Networking (CloudNet), pp. 1-6, 2019.
[52] K. Abbas, M. Afaq, T. A. Khan, A. Rafiq and W. -C. Song, "Slicing the Core Network and Radio Access Network Domains through Intent-Based Networking for 5G Networks," Electronics, vol. 9, no. 10, pp. 1710, 2020.
[53] A. Lodi, S. Martello and D. Vigo, "Recent Advances on Two-Dimensional Bin Packing Problems," Discrete Applied Mathematics, vol. 123, no. 1-3, pp. 379-396, 2002.
[54] 5G NR Cell Global Identity (NCGI) Planning and Calculations, Available on August 7, 2021: https://www.techplayon.com/5g-nr-cell-global-identity-planning/
[55] Selecting a container runtime for use with Kubernetes, Available on August 9, 2021: https://joejulian.name/post/Kubernetes-container-engine-comparison/
[56] Kubernetes DaemonSet, Available on August 9, 2021: https://Kubernetes.io/docs/concepts/workloads/controllers/daemonset/
[57] gtp5g Kernel Module, Available on August 10, 2021: https://github.com/PrinzOwO/gtp5g
[58] UERANSIM, Available on August 11, 2021: https://github.com/aligungr/UERANSIM
[59] Free5GC Compose, Available on August 15, 2021: https://github.com/free5gc/free5gc-compose
[60] Kubernetes configMap, Available on August 15, 2021: https://Kubernetes.io/docs/concepts/storage/volumes/#configmap
[61] Services without selectors, Available on August 15, 2021: https://Kubernetes.io/docs/concepts/services-networking/service/#services-without-selectors
[62] Kubernetes Feature Gates, Available on August 15, 2021: https://Kubernetes.io/docs/reference/command-line-tools-reference/feature-gates/
[63] Prometheus Architecture, Available on August 15, 2021: https://prometheus.io/docs/introduction/overview/