11 American Academic Scientific Research Journal for Engineering, Technology, and Sciences ISSN (Print) 2313-4410, ISSN (Online) 2313-4402 http://asrjetsjournal.org/ A Q-Learning Based Slice Admission Algorithm for Multi- Tier 5G Cellular Wireless Networks Elizabeth M. Okumu* Kabarak University, School of Science Engineering and Technology, P. O. Box Private Bag 20157, Nakuru 20100, Kenya Email: eokumu@kabarak.ac.ke Abstract Network slicing enables a 5G infrastructure provider (network infrastructure owner) to create multiple separate virtual networks, each tailored at a specific performance requirement, on a common physical network. In this context, slice admission algorithms are required to process slice requests received by the infrastructure provider. These algorithms are tailored to admit and allocate resources to network slices in a manner that results in the optimization of a given objective. In this paper, a Q-learning slice admission algorithm, which maximizes the infrastructure provider’s revenue, is designed. Results show that the designed algorithm learns from its environment, which enables it to acquire knowledge about the multi-tiered cellular network, thus allowing it make optimal slice admission decisions. The results further show that the designed algorithm has superior performance in terms of revenue achieved when compared to algorithms that admit, a) to maximize immediate rewards and b) slices in a random manner. Keywords: Network slice; 5G; Reinforcement learning; Slice admission; Resource allocation. 1. Introduction Fifth generation (5G) wireless networks are expected to accommodate a profusion of mobile devices and support a variety of services with unique performance requirements. The one-size-fits-all approach employed by traditional networks, e.g. 4G, is incapable of addressing these varying performance requirements. Software- defined radio (SDN) and network function virtualization (NFV) are enabling technologies for softwarized and virtualized networks [1,2,3]. By leveraging on the aforementioned technologies, 5G networks can address the divergent service requirements using network slicing. With network slicing, the physical network is sliced into multiple logical networks, each customized for a unique service requirement [4]. ------------------------------------------------------------------------ * Corresponding author. http://asrjetsjournal.org/ American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2021) Volume 82, No 1, pp 11-18 12 Network resources are dynamically allocated to network slices, depending on their service requirements, enabling the efficient deployment of the various services. Network slicing brings about a division of roles in the 5G network between infrastructure providers, who own and operate the physical network recourses, and slice tenants, who buy slices from the infrastructure providers, and then sell them to the end users. Slice admission algorithms are required for efficient allocation of resources, and to meet predetermined objectives for the infrastructure provider. The objectives can be broadly classified as revenue optimization, QoS control, inter- slice congestion control and slice fairness assurance [5]. The authors in [6] designed a revenue optimizing Q- learning algorithm for elastic and inelastic service types; slice requests that were not serviced were lost. In this paper, reinforcement learning techniques are used to develop an adaptive revenue optimizing slice admission algorithm for a multi-tied 5G wireless network. Network slice requests are placed on queues from where they are processed from. The designed Q-learning algorithm also ensures that the service requirements of the different slices are met. 1.1. Reinforcement Learning Reinforcement learning (RL) is a machine learning technique that enables an autonomous agent to select optimal actions without prior knowledge of the environment (system) [7]. The agent takes actions, observes the response from the environment and then automatically modifies its approach to achieve the optimal policy. In RL, the environment is modeled as a Markov Decision Process (MDP) [8]. MDPs model decision making in a discrete, stochastic environment under the control of a decision maker or agent. An MDP is defined by ο‚· A finite set of states, 𝑆, of the environment. ο‚· A finite set of actions, 𝐴 ο‚· A transition probability, 𝑃(𝑠, π‘Ž, 𝑠′), from state s to state 𝑠′ (𝑠, 𝑠′ ∈ 𝑆) when action π‘Ž ∈ 𝐴 is executed. ο‚· An immediate reward, π‘Ÿ, that is received after action π‘Ž is performed. The role of the agent is to learn a control policy πœ‹ used to select the next action π‘Žπ‘‘, given the current state 𝑠𝑑, at each discrete time step 𝑑; that is πœ‹(𝑠𝑑) = π‘Žπ‘‘ For an infinite time horizon MDP, the goal is to determine the optimal policy, πœ‹βˆ—, that maximizes the discounted cumulative reward, defined as π‘‰πœ‹(𝑠𝑑) = βˆ‘ π›Ύπ‘–π‘Ÿπ‘‘+𝑖 , ∞ 𝑖=0 βˆ€π‘  ∈ 𝑆 0 ≀ 𝛾 < 1 is the discount factor. Beginning at the state 𝑠𝑑 , the sequence of rewards π‘Ÿπ‘‘+𝑖 are generated by repeatedly selecting actions using the policy πœ‹. The optimal policy πœ‹βˆ—, that chooses the optimal action for each state, can be realized by learning the optimal value function given by [9] π‘‰βˆ—(𝑠) = max π‘Žπ‘‘ [π‘Ÿ(𝑠𝑑 , π‘Žπ‘‘) + π›Ύπ‘‰πœ‹(𝑠𝑑+1)] In Q-learning, the evaluation function to be learned is 𝑄(𝑠, π‘Ž), defined as 𝑄(𝑠, π‘Ž) = π‘Ÿ(𝑠𝑑 , π‘Žπ‘‘) + π›Ύπ‘‰πœ‹(𝑠𝑑+1). Thus, the optimal value function can be expressed as π‘‰βˆ—(𝑠) = maxπ‘Žπ‘‘ 𝑄(𝑠, π‘Ž). The Q values are stored in a large American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2021) Volume 82, No 1, pp 11-18 13 table, the Q-table, with a separate entry for each state-action pair. The optimal policy is now determined by finding the optimal values for all state-action pairs. The agent perceives its present state 𝑠, executes an action π‘Ž, receives a reward π‘Ÿ and moves to the next state 𝑠′. The Q table is then updated in an iterative manner after each action. If 𝑄𝑛(𝑠, π‘Ž) denotes the learned value after the π‘›π‘‘β„Ž iteration, then the entries in the Q table are updated using the following rule 𝑄𝑛(𝑠, π‘Ž) ← π‘„π‘›βˆ’1(𝑠, π‘Ž) + π›Όπ‘›βˆ’1 [π‘Ÿπ‘› + 𝛾 max π‘Žβ€² π‘„π‘›βˆ’1(𝑠′, π‘Žβ€²) βˆ’ π‘„π‘›βˆ’1(𝑠, π‘Ž)] 𝛼𝑛 ∈ [0,1] is the learning rate which has to satisfy the conditions βˆ‘ 𝛼𝑛 = ∞∞ 𝑛=0 and βˆ‘ 𝛼2 < ∞∞ 𝑛=0 [10]. The Q- learning algorithm belongs to the class of temporal difference algorithms, learns by reducing the differences between estimates made by the agent at different time units [9]. 2. Q-Learning Slice Admission Algorithm 2.1. System Model The network model is a multi-tiered 5G network consisting of a single macro-cell overlaid with 𝐡 small cells. The macro-cell has a capacity of πΆπ‘€π‘Žπ‘, while each small cell has a capacity of 𝐢𝑆𝑐. It is assumed that at any given time, a user in the cellular network can only communicate through a single base station, i.e. the macro- cell’s or one small cell’s. Geographically, it is assumed that the users are uniformly distributed among the small cells; the geographical position of a user is given with respect to the coverage area of the small cell the user is located in. It is assumed that all the small cells have equal coverage area and that the coverage areas do not overlap. In this paper, the focus is on three types of services, ultra-reliable low latency communication (uRLLC), enhanced mobile broadband (eMBB) and internet of things (IoT) services. The IoT devices are assumed to be low data rate sensors. We define an IoT user as a group of 𝑑𝑖 IoT devices; each IoT device requires a capacity of 𝐢𝑖/𝑑𝑖 , therefore the IoT user capacity requirement is 𝐢𝑖. The capacity required by uRRLC and eMMB users are 𝐢𝑒 and 𝐢𝑒 respectively. IoT and eMMB users are serviced through the macro-cell base station while the uRRLC users, due to the latency sensitive nature of uRLLC services, are serviced through the small cell base station whose coverage area they are located in. The network is assumed to be owned and operated by an infrastructure provider who provides network slices to tenants; the tenants in turn provide services to the end users. A network slice is defined as follows; ο‚· Service type π‘š ∈ [1, 2, 3]; the supported service types IoT, uRRLC and eMMB are represented by π‘š = 1, 2 π‘Žπ‘›π‘‘ 3 respectively. ο‚· Size 𝑛: this is the number of users the slice can support 2.2. The Q-Learning Algorithm Markov Decision Process theory (MDP) is used to model the system as a set of 𝑆 finite states and a set of 𝐴 finite actions. A state 𝑠 ∈ 𝑆 is defined as (𝑧1, … , π‘§π‘š) where π‘§π‘š is an n-tuple (π‘§π‘š1, π‘§π‘š2 … . . π‘§π‘šπ‘π‘š ) which describes the number slices of different sizes present in the system for service type π‘š. π‘π‘š represents the maximum slice size for service type π‘š. The states in the state space 𝑆 have to satisfy the following constraints American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2021) Volume 82, No 1, pp 11-18 14 𝐢𝑖 βˆ‘ 𝑛𝑧1𝑛 𝑁1 𝑛=1 + 𝐢𝑒 βˆ‘ 𝑛𝑧3𝑛 𝑁3 𝑛=1 ≀ πΆπ‘€π‘Žπ‘ 𝐢𝑒 βˆ‘ 𝑛𝑧2𝑛 𝑁2 𝑛=1 ≀ 𝐡𝐢𝑆𝑐 The slice requests submitted to the infrastructure provider are in of the form {π‘š, 𝑛, 𝑑}, where 𝑑 is the number of time units the slice is required for. Incoming slice requests are placed in queues depending on their type and size. A slice request of type π‘š and size 𝑛 is placed it the queue π‘„π‘šπ‘› . The slice admission algorithm retrieves the slice requests from the queues in a first in first out manner. If resources are available the slice request is processed and resources are allocated to the network slice; the slice request is then removed from the queue. A revenue (reward) of π‘Ÿ = π‘‘π‘›πœŒπ‘š, where πœŒπ‘š is the revenue (reward) per unit time for service type π‘š, is earned by the infrastructure provider. But if resources are not available, the slice request will not be serviced but will remain in the queue, and no reward will be earned. The possible actions, π‘Ž ∈ 𝐴 are defined as (π‘Ž1, π‘Ž2, π‘Ž3, 𝑅), where π‘Žπ‘š is an n-tuple (π‘Žπ‘š1, π‘Žπ‘š2, … . , π‘Žπ‘šπ‘π‘š ); the π‘›π‘‘β„Ž element of π‘Žπ‘š corresponds to the action of accepting a slice of size 𝑛 of service type π‘š. Based on the model described, the Q-learning algorithm is described in Table 1. Table 1: Q-Learning Algorithm For each (𝑠, π‘Ž) pair, initial the Q table entry 𝑄(𝑠, π‘Ž) to zero Observe the current state 𝑠 for 𝑛 = 1 to 𝐸 From state 𝑠 execute action π‘Ž Receive immediate reward π‘Ÿ Observe new state 𝑠′ Update the table entry 𝑄(𝑠, π‘Ž) as follows 𝑄𝑛(𝑠, π‘Ž) ← π‘„π‘›βˆ’1(𝑠, π‘Ž) + π›Όπ‘›βˆ’1 [π‘Ÿπ‘› + 𝛾 max π‘Žβ€² π‘„π‘›βˆ’1(𝑠′, π‘Žβ€²) βˆ’ π‘„π‘›βˆ’1(𝑠, π‘Ž)] Replace 𝑠 ← 𝑠′ End for The learning rate is determined as 𝛼𝑛 = 1 1 + 𝜏(𝑠, π‘Ž)⁄ , where 𝜏(𝑠, π‘Ž) is the number of times the action π‘Ž has been executed from state 𝑠 [9]. Choosing the action that maximizes 𝑄(𝑠, π‘Ž), exploits the knowledge of already visited states to maximize the overall revenue. Relying on exploitation will result in an algorithm that utilizes only (𝑠, π‘Ž) determined in the early stages, while failing to explore other (𝑠, π‘Ž) that may potentially yield higher rewards. In order to tradeoff between exploration and exploitation, a probabilistic approach is used to select actions. The probability of selecting action π‘Žπ‘–when in state 𝑠 is determined as follows [9] American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2021) Volume 82, No 1, pp 11-18 15 𝑃(π‘Žπ‘–\𝑠) = π‘˜π‘„(𝑠,π‘Žπ‘–) βˆ‘ π‘˜π‘„(𝑠,π‘Žπ‘—) 𝑗 The value the constant π‘˜ > 0 is varied (from small to large) so as to favor exploration in the early stages of the learning process, which then gradually shifts to exploitation. 𝐸 is used to indicate the end of an episode. 3. Simulation and Results In this section, the performance of the Q-Learning algorithm is evaluated via simulations, based on the following network settings and parameters. ο‚· The number of small cells is 𝐡 = 3 ο‚· πΆπ‘€π‘Žπ‘ = 3𝐢𝑆𝑐 ο‚· 𝐢𝑒 = 𝐢𝑆𝑐/2, 𝐢𝑒 = 1.5𝐢𝑒 and 𝐢𝑖 = 𝐢𝑒/2 ο‚· 𝑁1 = πΆπ‘€π‘Žπ‘/𝐢𝑖, 𝑁2 = 𝐡𝐢𝑆𝑐/𝐢𝑒 and 𝑁3 = πΆπ‘€π‘Žπ‘/𝐢𝑒 ο‚· Maximum slice size of 2, that is 𝑛 ∈ [1,2] ο‚· 𝜌2 = 4𝜌1, 𝜌3 = 3𝜌1 and 𝜌1 = 5 ο‚· The arrival rates for IoT, eMMB and uRLLC slice requests are 0.2, 0.35 and 0.35 respectively ο‚· Number of queues is 6, each queue is stores a maximum of 100 slice requests The performance of the Q-Learning slice admission algorithm is compared to 1) a greedy algorithm that admits slices that maximize the immediate reward, 2) an algorithm that admits slices in a random manner. Figure 1 shows the average cumulative revenue gained per slice request. Figure 1: Plot of average cumulative revenue against number of episodes It is observed that the Q-learning algorithm outperforms the greedy and random algorithms for episodes > 50. For episodes 1 βˆ’ 150, the Q-learning algorithm has not converged, this results in low average cumulative American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2021) Volume 82, No 1, pp 11-18 16 revenue value. But after convergence, the revenue value stabilizes to a maximum value that is greater than that of the other two algorithms. Figures 2(a), (b) and (c) show the slice admission rates for Q-learning, greedy and random algorithms, respectively. Figure 2: Average slice admission rate for (a) Q-learning (b) Greedy and (c) Random (a) (b) (c) American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2021) Volume 82, No 1, pp 11-18 17 The plots for admission rates for, (i) IoT slice requests of size 1 and 2 (πΌπ‘œπ‘‡1 π‘Žπ‘›π‘‘ πΌπ‘œπ‘‡2), (ii) eMMB slice requests of size 1 and 2 (𝑒𝑀𝑀𝐡1 π‘Žπ‘›π‘‘ 𝑒𝑀𝑀𝐡2) and (ii) uRRLC slice requests of size 1 and 2 (𝑒𝑅𝐿𝐿𝐢1 π‘Žπ‘›π‘‘ 𝑒𝑅𝐿𝐿𝐢2). From Figure 2(a), it is observed that the Q-learning algorithm, after convergence, maintains the admission rates for all slice request above 14%. Admission rates are dependent on the reward and slice size; a larger reward translates to higher admission rate while a bigger slice size reduces the admission rate. It is more difficult to allocate resources to a slice request with a larger size. It is evident that the Q-learning algorithm learns from the environment, enabling it to prioritize slice requests in a manner that results in maximized cumulative revenue and fair admission rates for the slices. The greedy algorithm, as seen in Figure 2(b), which maximizes immediate rewards, prioritizes 𝑒𝑅𝐿𝐿𝐢2, 𝑒𝑀𝑀𝐡2 and 𝑒𝑅𝐿𝐿𝐢1 at the expense of the other slice requests which have lower immediate rewards. This results in cumulative revenue that is high for initial episodes, and then decreases as the number of episodes increases. The random algorithm, as seen in Figure 2(c), maintains the admission rates between 14% and 19%. Since the algorithm selects slice requests in a random manner, the admission rate for each slice should be approximately 16.6%. But a selected slice will not necessarily be admitted because the resources may not be available, therefore the slice request do not have the same admission rate. 4. Conclusions In this paper, Q-learning based slice admission algorithm, that maximizes the revenue for a multi-tier 5G cellular wireless network infrastructure was designed and implemented. Results show that the algorithm’s capability to learn from the environment (network) allowing it to adaptively allocate resources, this enabled it provide revenue gains when compared to greedy and random slice admission algorithms. 5. Recommendations The Q-learning algorithm used in this study learns by maintaining and updating Q-values for all state-action pairs. If the wireless network is large in scale, as 5G networks tend to be, then the number of states can become quite large or even unlimited, negatively impacting algorithm efficiency. This issue can be overcome if Deep Q-learning, which combines Q-learning and deep learning techniques, is used. References [1]. ONF TR-526, β€œApplying SDN Architecture to 5G Slicing,” Apr. 2016. [2]. ETSI GS NFV 002, β€œNetwork Functions Virtualization (NFV); Architectural Framework,” v. 1.1.1, Dec. 2014. [3]. N. M. M. K. Chowdhury and R. Boutaba, β€œA Survey of Network Virtualization,” Computer Networks, vol. 54, no. 5, Apr. 2010, pp. 862–76 [4]. NGMN Alliance, β€œDescription of Network Slicing Concept,” Public Deliverable, 2016 [5]. M. O. Ojijo and O. E. Falowo, "A survey on slice admission control strategies and optimization schemes in 5g network", IEEE Access, vol. 8, pp. 14977-14990, 2020. [6]. D. Bega, M. Gramaglia, A. Banchs, V. Sciancalepore, K. Samdanis, and X. Costa-Perez, β€˜β€˜Optimising American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2021) Volume 82, No 1, pp 11-18 18 5G infrastructure markets: The business ofnetwork slicing,’’ inProc. IEEE INFOCOM, Atlanta, GA, USA, May 2017,pp. 1–9. [7]. R. S. Sutton and A. G. Barto, Reinforcement learning: An introduction. MIT press Cambridge, 1998. [8]. R. Bellman, β€œA markovian decision process,” DTIC, Tech. Rep., 1957. [9]. T. Mitchell. Machine Learning, McGraw-Hill, 1997. [10]. E. Even-Dar and Y. Mansour, β€œLearning rates for Q-learning,” Journal of Machine Learning Research, vol. 5, pp. 1–25, Dec. 2003.