{'fraction_non_alphanumeric': 0.032042052336875786, 'fraction_numerical': 0.011175865615358245, 'mean_word_length': 4.550678675631105, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Structure-aware reinforcement learning for node-overload protection in mobile edge computing

Mobile Edge Computing (MEC) refers to the concept of placing computational capability and applications at the edge of the network, providing benefits such as reduced latency in handling client requests, reduced network congestion, and improved performance of applications. The performance and reliability of MEC are degraded significantly when one or several edge servers in the cluster are overloaded. Especially when a server crashes due to the overload, it causes service failures in MEC. In this work, an adaptive admission control policy to prevent edge node from getting overloaded is presented. This approach is based on a recently-proposed low complexity RL (Reinforcement Learning) algorithm called SALMUT (Structure-Aware Learning for Multiple Thresholds), which exploits the structure of the optimal admission control policy in multi-class queues for an average-cost setting. We extend the framework to work for node overload-protection problem in a discounted-cost setting. The proposed solution is validated using several scenarios mimicking real-world deployments in two different settings - computer simulations and a docker testbed. Our empirical evaluations show that the total discounted cost incurred by SALMUT is similar to state-of-the-art deep RL algorithms such as PPO (Proximal Policy Optimization) and A2C (Advantage Actor Critic) but requires an order of magnitude less time to train, outputs easily interpretable policy, and can be deployed in an online manner.


I. INTRODUCTION
I N the last decade, we have seen a shift in the computing paradigm from co-located datacenters and compute servers to cloud computing. Due to the aggregation of resources, cloud computing can deliver elastic computing power and storage to customers without the overhead of setting up expensive datacenters and networking infrastructures. It has specially attracted small and medium-sized businesses who can leverage the cloud infrastructure with minimal setup costs. In recent years, the proliferation of Video-on-Demand (VoD) services, Internet-of-Things (IoT), real-time online gaming platforms, and Virtual Reality (VR) applications has lead to a strong focus on the quality of experience of the end users. The cloud paradigm is not the ideal candidate for such latency-sensitive applications owing to the delay between the end user and cloud server.
This has led to a new trend in computing called Mobile Edge Computing (MEC) [1], [2], where the compute capabilities are moved closer to the network edges. It represents an essential building block in the 5G vision of creating large distributed, pervasive, heterogeneous, and multi-domain environments.
Harvesting the vast amount of the idle computation power and storage space distributed at the network edges can yield sufficient capacities for performing computation-intensive and latency-critical tasks requested by the end-users. However, it is not feasible to set-up huge resourceful edge clusters along all network edges that mimic the capabilities of the cloud due to the sheer volume of resources that would be required, which would remain underutilized most of the times. Due to the limited resources at the edge nodes and fluctuations in the user requests, an edge cluster may not be capable of meeting the resource and service requirements of all the users it is serving.
Computation offloading methods have gained a lot of popularity as they provide a simple solution to overcome the problems of edge and mobile computing. Data and computation offloading can potentially reduce the processing delay, improve energy efficiency, and even enhance security for computation-intensive applications. The critical problem in the computation offloading is to determine the amount of computational workload, and choose the MEC server from all available servers. Various aspects of MEC from the point of view of the mobile user have been investigated in the literature. For example, the questions of when to offload to a mobile server, to which mobile server to offload, and how to offload have been studied extensively. See, [3]- [7] and references therein.
However, the design questions at the server side have not been investigated as extensively. When an edge server receives a large number of requests in a short period of time (for example due to a sporting event), the edge server can get overloaded, which can lead to service degradation or even node failure. When such service degradation occurs, edge servers are configured to offload requests to other nodes in the cluster in order to avoid the node crash. The crash of an edge node leads to the reduction of the cluster capacity, which is a disaster for the platform operator as well as the end users, who are using the services or the applications. However, performing this migration takes extra time and reduces the resources availability for other services deployed in the cluster. Therefore, it is paramount to design pro-active mechanisms that prevent a node from getting overloaded using dynamic offloading policies that can adapt to service request dynamics.
The design of an offloading policy has to take into account the time-varying channel conditions, user mobility, energy supply, computation workload and the computational capabilities of different MEC servers. The problem can be modeled as a Markov Decision Process (MDP) and solved using dynamic programming. However, solving a dynamic program requires the knowledge of the system parameters, which are not typically known and may also vary with time. In such time-varying environments, the offloading policy must adapt to the environment. Reinforcement Learning (RL) [8] is a natural choice to design such adaptive policies as they do not need a model of the environment and can learn the optimal policy based on the observed per-step cost. RL has been successfully applied for designing adaptive offloading policies in edge and fog computing in [9]- [15] to realize one or more objectives such as minimizing latency, minimizing power consumption, association of users and base stations. Although RL has achieved considerable success in the previous work, this success is generally achieved by using deep neural networks to model the policy and the value function. Such deep RL algorithms require considerable computational power and time to train, and are notoriously brittle to the choice of hyper-parameters. They may also not transfer well from simulation to the real-world, and output policies which are difficult to interpret. These features make them impractical to be deployed on the edge nodes to continuously adapt to the changing network conditions.
In this work, we study the problem of node-overload protection for a single edge node. Our main contributions are as follows: • We present a mathematical model for designing an offloading policy for node-overload protection. The model incorporates practical considerations of server holding, processing and offloading costs. In the simplest case, when the request arrival process is time-homogeneous, we model the system as a continuous-time MDP and use the uniformization technique [16], [17] to convert the continuous-time MDP to a discrete-time MDP, which can then be solved using standard dynamic programming algorithms [18]. • We show that for time-homogeneous arrival process, the value function and the optimal policy are weakly increasing in the CPU utilization. • We design a node-overload protection scheme that uses a recently proposed low-complexity RL algorithm called Structure-Aware Learning for Multiple Thresholds (SALMUT) [19]. The original SALMUT algorithm was designed for the average cost models. We extend the algorithm to the discounted cost setup and prove that SALMUT converges almost surely to a locally optimal policy. • We compare the performance of Deep RL algorithms with SALMUT in a variety of scenarios in a simulated testbed which are motivated by real world deployments.
Our simulation experiments show that SALMUT performs close to the state-of-the-art Deep RL algorithms such as PPO [20] and A2C [21], but requires an order of magnitude less time to train and provides optimal policies which are easy to interpret. • We developed a docker testbed where we run actual workloads and compare the performance of SALMUT with the baseline policy. Our results show that SALMUT algorithm outperforms the baseline algorithm. A preliminary version of this paper appeared in [22], where the monotonicity results of the optimal policy (Proposition 1 and 2) were stated without proof and the modified SALMUT algorithm was presented with a slightly different derivation. However, the convergence behavior of the algorithm (Theorem 2) was not analyzed. A preliminary version of the comparison on SALMUT with state of the art RL algorithms on a computer simulation were included in [22]. However, the detailed behavioral analysis (Sec. V) and the results for the docker testbed (Sec. VI) are new.
The rest of the paper is organized as follows. We present the system model and problem formulation in Sec. II. In Sec. III, we present a dynamic programming decomposition for the case of time-homogeneous statistics of the arrival process. In Sec. IV, we present the structure aware RL algorithm (SALMUT) proposed in [19] for our model. In Sec. V, we conduct a detailed experimental study to compare the performance of SALMUT with other state-of-the-art RL algorithms using computer simulations. In Sec. VI, we compare the performance of SALMUT with baseline algorithm on the real-testbed. Finally, in Sec. VII, we provide the conclusion, limitations of our model, and future directions.

II. MODEL AND PROBLEM FORMULATION
A. System model A simplified MEC system consists of an edge server and several mobile users accessing that server (see Fig. 1). Mobile users independently generate service requests according to  a Poisson process. The rate of requests and the number of users may also change with time. The edge server takes CPU resources to serve each request from mobile users. When a new request arrives, the edge server has the option to serve it or offload it to other healthy edge server in the cluster. The request is buffered in a queue before it is served. The mathematical model of the edge server and the mobile users is presented below. 1) Edge server: Let ∈ {0, 1, . . . , X} denote the number of service requests buffered in the queue, where X denotes the size of the buffer. Let ∈ {0, 1, . . . , L} denote the CPU load at the server where L is the capacity of the CPU. We assume that the CPU has cores.
We assume that the requests arrive according to a (potentially time-varying) Poisson process with rate . If a new request arrives when the buffer is full, the request is offloaded to another server. If a new request arrives when the buffer is not full, the server has the option to either accept or offload the request.
The server can process up to a maximum of requests from the head of the queue. Processing each request requires CPU resources for the duration in which the request is being served. The required CPU resources is a random variable ∈ {1, . . . , R} with probability mass function . The realization of is not revealed until the server starts working on the request. The duration of service is exponentially distributed random variable with rate .
Let A = {0, 1} denote the action set. Here = 1 means that the server decides to offload the request while = 0 means that the server accepts the request.
2) Traffic model for mobile users: We consider multiple models for traffic. • Time-varying user set: In each of the scenarios above, we can consider the case when the number of users is not fixed and changes over time. We call them Scenario 4, 5, and 6 respectively. 3) Cost and the optimization framework: The system incurs three types of a cost: • a holding cost of ℎ per unit time when a request is buffered in the queue but is not being served. • a running cost of (ℓ) per unit time for running the CPU at a load of ℓ. • a penalty of (ℓ) for offloading a packet at CPU load ℓ. We combine all these costs in a cost function where denotes the action, [ ] + is a short-hand for max{ , 0} and 1{·} is the indicator function. Note that to simplify the analysis, we assume that the server always serves min{ , } requests. It is also assumed that (ℓ) and (ℓ) + (ℓ) are increasing in ℓ. The performance of a policy starting from initial state ( , ℓ) is given by where > 0 is the discount rate and the expectation is with respect to the arrival process, CPU utilization, and service completions.
The objective is to minimize the performance (2) for the different traffic scenarios listed above. We are particularly interested in the scenarios where the arrival rate and potentially other components of the model such as the resource distribution are not known to the system designer and change during the operation of the system.

B. Solution framework
When the model parameters ( , , , , ) are known and time-homogeneous, the optimal policy can be computed using dynamic programming. However, in a real system, these parameters may not be known, so we are interested in developing a RL algorithm which can learn the optimal policy based on the observed per-step cost.
In principle, when the model parameters are known, Scenarios 2 and 3 can also be solved using dynamic programming. However, the state of such dynamic programs will include the state of the system (for Scenario 2) or the states ( ) =1 of all users (for Scenario 3). Typically, these states change at a slow time-scale. So, we will consider reinforcement learning algorithms which do not explicitly keep track of the states of the user and verify that the algorithm can adapt quickly whenever the arrival rates change.

III. DYNAMIC PROGRAMMING TO IDENTIFY OPTIMAL ADMISSION CONTROL POLICY
When the arrival process is time-homogeneous, the process { , } ≥0 is a finite-state continuous-time MDP controlled through { } ≥0 . To specify the controlled transition probability of this MDP, we consider the following two cases.
First, if there is a new arrival at time , then We denote this transition function by + ( , ℓ | , ℓ, ). Note that the first term (ℓ − ℓ) denotes the probability that the accepted request required (ℓ − ℓ) CPU resources. Second, if there is a departure at time , We denote this transition function by − ( , ℓ | , ℓ). Note that there is no decision to be taken at the completion of a request, so the above transition does not depend on the action. In general, the reduction in CPU utilization will correspond to the resources released after the client requests are served. However, keeping track of those resources would mean that we would need to expand the state and include ( 1 , . . . , ) as part of the state, where denotes the resources required by the request which is being processed by CPU . In order to avoid such an increase in state dimension, we assume that when a request is completed, CPU utilization reduces by amount ℓ − ℓ with probability (ℓ − ℓ ). We combine (3) and (4) into a single controlled transition probability function from state ( , ℓ) to state ( , ℓ ) given by Let = + denote the uniform upper bound on the transition rate at the states. Then, using the uniformization technique [16], [17], we can convert the above continuous time discounted cost MDP into a discrete time discounted cost MDP with discount factor = /( + ), transition probability matrix ( , ℓ | , ℓ, ) and per-step cost Therefore, we have the following.
Theorem 1 Consider the following dynamic program where [ ] B denotes min{ , B}. Let ( , ℓ) ∈ A denote the argmin the right hand side of (6). Then, the time-homogeneous policy ( , ℓ) is optimal for the original continuous-time optimization problem.
PROOF The equivalence between the continuous and discrete time MDPs follows from the uniformization technique [16], [17]. The optimality of the time-homogeneous policy follows from the standard results for MDPs [18].
Thus, for all practical purposes, the decision maker has to solve a discrete-time MDP, where he has to take decisions at the instances when a new request arrives. In the sequel, we will ignore the 1/( + ) term in front of the per-step cost and assume that it has been absorbed in the constant ℎ, and the functions (·), (·).
When the system parameters are known, the above dynamic program can be solved using standard techniques such as value iteration, policy iteration, or linear programming. However, in practice, the system parameters may slowly change over time. Therefore, instead of pursuing a planning solution, we consider reinforcement learning solutions which can adapt to time-varying environments.
IV. STRUCTURE-AWARE REINFORCEMENT LEARNING Although, in principle, the optimal admission control problem formulated above can be solved using deep RL algorithms, such algorithms require significant computational resources to train, are brittle to the choice of hyperparameters, and generate policies which are difficult to interpret. For the aforementioned reasons, we investigate an alternate class of RL algorithms which circumvents these limitations.

A. Structure of the optimal policy
We first establish basic monotonicity properties of the value function and the optimal policy. Proposition 1 For a fixed queue length , the value function is weakly increasing in the CPU utilization ℓ.

PROOF The proof is present in Appendix A.
Proposition 2 For a fixed queue length , if it is optimal to reject a request at CPU utilization ℓ, then it is optimal to reject a request at all CPU utilizations ℓ > ℓ.
PROOF The proof is present in Appendix B.

B. The SALMUT algorithm
Proposition 2 shows that the optimal policy can be represented by a threshold vector = ( ( )) X =0 , where ( ) ∈ {0, . . . , L} is the smallest value of the CPU utilization such that it is optimal to accept the packet for CPU utilization less than or equal to ( ) and reject it for utilization greater than ( ). The SALMUT algorithm was proposed in [19] to exploit a similar structure in admission control for multi-class queues. It was originally proposed for the average cost setting. We present a generalization to the discounted-time setting.
Let ∇ denote the gradient with respect to . From Performance Derivative formula [23, Eq. 2.44], we know that where ( , ℓ) is the occupancy measure on the states starting from the initial state ( 0 , ℓ 0 ).
Thus, we can use the standard two time-scale Actor-Critic algorithm [8] to simultaneously learn the policy parameters and the action-value function as follows. We start with an initial guess 0 and 0 for the action-value function and the optimal policy parameters. Then, we update the action-value function using temporal difference learning: and update the policy parameters using stochastic gradient descent while using the unbiased estimator of ∇ ( ): where The complete algorithm is presented in Algorithm 1 and illustrated in Fig. 3.
PROOF The proof is present in Appendix C.

V. NUMERICAL EXPERIMENTS -COMPUTER SIMULATIONS
In this section, we present detailed numerical experiments to evaluate the proposed reinforcement learning algorithm on various scenarios described in Sec. II-A.
The CPU running cost is modelled such that it incurs a positive reinforcement for being in the optimal CPU range, and a high cost for an overloaded system.
The offload penalty is modelled such that it incurs a fixed cost for offloading to enable the offloading behavior only when the system is loaded and a very high cost when load is system is idle to discourage offloading in such scenarios.
The probability mass function of resources requested per request is as follows Rather than simulating the system in continuous-time, we simulate the equivalent discrete-time MDP by generating the next event (arrival or departure) using a Bernoulli distribution with probabilities and costs described in Sec. III. We assume that the parameter 1/( + ) in (6) has been absorbed in the cost function. We assume that the discrete time discount factor = /( + ) equals 0.95.

A. Simulation scenarios
We consider a number of traffic scenarios which are increasing in complexity and closeness to the real-world setting. Each scenario runs for a horizon of = 10 6 . The scenarios capture variation in the transmission rate and the number of users over time, their realization can be seen in Fig. 4.
The evolution of the arrival rate and the number of users for the more dynamic environments is shown in Fig. 4. a) Scenario 1: This scenario tests how the learning algorithms perform in the time-homogeneous setting. We consider a system with = 24 users with arrival rate = 0.25. Thus, the overall arrival rate = = 6. b) Scenario 2: This scenario tests how the learning algorithms adapt to occasional but significant changes to arrival rates. We consider a system with = 24 users, where each user generates requests at rate low = 0.25 for the interval (0, 3.33 × 10 5 ], then generates requests at rate high = 0.375 for the interval (3.34 × 10 5 , 6.66 × 10 5 ], and then generates requests at rate low again for the interval (6.67 × 10 5 , 10 6 ]. c) Scenario 3: This scenario tests how the learning algorithms adapt to frequent but small changes to the arrival rates. We consider a system with = 24 users, where each user generates requests according to rate ∈ { low , high } where low = 0.25 and high = 0.375. We assume that each user starts with a rate low or high with equal probability. At time intervals × 10 4 , each user toggles its transmission rate with probability = 0.1.

d) Scenario 4:
This scenario tests how the learning algorithm adapts to change in the number of users. In particular, we consider a setting where the system starts with 1 = 24 user. At every 10 5 time steps, a user may leave the network, stay in the network or add another mobile device to the network with probabilities 0.05, 0.9, and 0.05, respectively. Each new user generates requests at rate . e) Scenario 5: This scenario tests how the learning algorithm adapts to large but occasional change in the arrival rates and small changes in the number of users. In particular, we consider the setup of Scenario 2, where the number of users change as in Scenario 4. f) Scenario 6: This scenario tests how the learning algorithm adapts to small but frequent change in the arrival rates and small changes in the number of users. In particular, we consider the setup of Scenario 3, where the number of users change as in Scenario 4.

B. The RL algorithms
For each scenarios, we compare the performance of the following policies 1) Dynamic Programming (DP), which computes the optimal policy using Theorem 1. 2) SALMUT, as described in Sec. IV-B. 3) Q-Learning, using (14). 4) PPO [20], which is a family of trust region policy gradient method and optimizes a surrogate objective function using stochastic gradient ascent. 5) A2C [21], which is a two time-timescale learning algorithms where the critic estimates the value function and actor updates the policy distribution in the direction suggested by the critic. 6) Baseline, which is a fixed-threshold based policy, where the node accepts requests when ℓ < 18 (non-overloaded state) and offloads requests otherwise. Such static policies are currently deployed in many real-world systems. For SALMUT, we use ADAM [24] optimizer with initial learning rates ( 1 = 0.03, 2 = 0.002). For Q-learning, we use Stochastic Gradient Descent with 1 = 0.01. We used the stable-baselines [25] implementation of PPO and A2C with learning rates 0.0003 and 0.001 respectively.

C. Results
For each of the algorithm described above, we train SALMUT, Q-learning, PPO, and A2C for 10 6 steps. The performance of each algorithm is evaluated every 10 3 steps using independent rollouts of length = 1000 for 100 different random seeds. The experiment is repeated for the 10 sample paths and the median performance with an uncertainty band from the first to the third quartile are plotted in Fig. 5.
For Scenario 1, all RL algorithms (SALMUT, Q-learning, PPO, A2C) converge to a close-to-optimal policy and remain stable after convergence. Since all policies converge quickly, SALMUT, PPO, and A2C are also able to adapt quickly in Scenarios 2-6 and keep track of the time-varying arrival rates and number of users. There are small differences in the performance of the RL algorithms, but these are minor. Note that, in contrast, Q-learning policy does not perform well when the dynamics of the requests changes drastically, whereas the baseline policy performs poorly when the server is overloaded.
The plots for Scenario 1 (Fig. 5a) show that PPO converges to the optimal policy in less than 10 5 steps, SALMUT and A2C takes around 2 × 10 5 steps, whereas Q-learning takes around 5 × 10 5 steps to converge. The policies for all the algorithms remain stable after convergence. Upon further analysis on the structure of the optimal policy, we observe that the structure of the optimal policy of SALMUT (Fig. 6b) differs from that of the optimal policy computed using DP (Fig. 6a). There is a slight difference in the structure of these policies when buffer size (x) is low and CPU load (ℓ) is high, which occurs because these states are reachable with a very low probability and hence SALMUT doesn't encounter these states in the simulation often to be able to learn the optimal policy in these states. The plots from Scenario 2 (Fig. 5b) show similar behavior when is constant. When changes significantly, we observe all RL algorithms except Q-learning are able to adapt to the drastic but stable changes in the environment. Once the load stabilizes, all the algorithms are able to readjust to the changes and perform close to the optimal policy. The plots from Scenario 3 (Fig. 5c) show similar behavior to Scenario 1, i.e. small but frequent changes in the environment do not impact the learning performance of reinforcement learning algorithms.
The plots from Scenario 4-6 ( Fig. 5d-5f) show consistent performance with varying users. The RL algorithms including Q-learning show similar performance for most of the time-steps except in Scenario 5, which is similar to the behavior observed in Scenario 2. The Q-learning algorithm also performs poorly when the load suddenly changes in Scenarios 4 and 6. This could be due to the fact that Q-learning takes longer to adjust to a more aggressive offloading policy.

D. Analysis of Training Time and Policy Interpretability
The main difference among these four RL algorithms is the training time and interpretability of policies. We ran our experiments on a server with Intel(R) Xeon(R) Gold 6148 CPU @ 2.40GHz processor. The training time of all the RL algoirthms is shown in Table II. The mean training time is computed based on a single scenario over different runs and averaged across all the six scenarios. SALMUT is about 28 times faster to train than PPO and 17 times faster than A2C. SALMUT does not require a non-linear function approximator such as Neural Networks (NN) to represent its policy, making the training time for SALMUT very fast. We observe that Q-learning is around 1.5 times faster than SALMUT as it does not need to update its policy parameters separately. Even though Q-learning is faster than SALMUT, Q-learning does not converge to an optimal policy when the request distribution changes.
By construction, SALMUT searches for (randomized) threshold based policies. For example, for Scenario 1, SALMUT converges to the policy shown in Fig. 6b. It is easy for a network operator to interpret such threshold based strategies and decide whether to deploy them or not. In contrast, in deep RL algorithms such as PPO and A2C, the policy is parameterized using a neural network and it is difficult to visualize the learned weights of such a policy and decide whether the resultant policy is reasonable. Thus, by leveraging on the threshold structure of the optimal policy, SALMUT is able to learn faster and at the same time provide threshold based policies which are easier to interpret. The policy of SALMUT is completely characterized by the threshold vector , making it storage efficient too. The threshold-nature of the optimal policy computed by SALMUT, can be easily interpreted by just looking at the threshold vector (see Fig. 6b), making it easy to debug and estimate the behavior of the system operating under such policies. However, the policies learned by A2C and PPO are the learned weights of the NN, which are undecipherable and may lead to unpredictable results occasionally. It is very important that the performance of real-time systems be predictable and reliable, which has hindered the adoption of NNs in real-time deployments.

E. Behavioral Analysis of Policies
We performed further analysis on the behavior of the learned policy by observing the number of times the system enters into an overloaded state and offloads incoming request. Let us define ov to be the number of times the system enters into an overloaded state and off to be the number of times the system offloads requests for every 1000 steps of training iteration. We generated a set of 10 6 random numbers between 0 and 1, defined by , where is the step count. We use this set of random numbers to fix the trajectory of events (arrival or departure) for all the experiments in this section. Similar to the experiment in the previous section, the number of users and the arrival rate are fixed for 1000 steps and evolve according to the scenarios described in Fig. 4. The event is set to arrival if is less than or equal to /( + min{ , } ), and set to departure otherwise. These experiments were carried out during the training time for 10 different seeds. We plot the median of the number of times a system goes into an overloaded state (Fig. 7) and the number of requests offloaded by the system (Fig. 8) along with the uncertainty band from the first to the third quartile for every 1000 steps.
We observe in Fig. 7, that all the algorithms (SALMUT, Q-learning, PPO, A2C) learn not to enter into the overloaded state. As seen in the case of total discounted cost (Fig. 5), PPO learns it instantly, followed by SALMUT, Q-learning, and A2C. The observation is valid for all the different scenarios we tested. We observe that for Scenario-4, PPO enters the overloaded state at around 0.8 × 10 6 which is due to the fact the increases drastically at that point (seen in Fig. 4d) and we also see its effect on the cost in Fig. 5d at that time. We also observe that SALMUT enters into overloaded states when the request distribution changes drastically in Scenario 2 and 5. It is able to recover quickly and adapt its threshold policy to a more aggressive offloading policy. The baseline algorithms, on the other hand, enters into the overloaded state quiet often.
We observe in Fig. 8, that the algorithms (SALMUT, PPO, A2C) learn to adjust their offloading rate to avoid overloaded state. The number of times requests have been offloaded is directly proportional to the total arrival rate of all the users at that time. When the arrrival rate increases, the number of times the offloading occurs also increases in the interval. We see that even though the offloaded requests are higher for the RL algorithms than the baseline algorithm in all scenarios and timesteps, the difference between the number of times they offload is not significant implying that the RL algorithms learn policies that offload at the right moment as to not lead the system into an overloaded state. We perform further analysis of this behavior for the docker-testbed (see Fig. 13) and the results are similar for the simulations too.

VI. TESTBED IMPLEMENTATION AND RESULTS
We test our proposed algorithm on a testbed resembling the MEC architecture in Fig. 1, but without the core network and backend cloud server for simplicity. We consider an edge node which serves a single application. Both the edge nodes and clients are implemented as containerized environments in a virtual machine. The overview of the testbed is shown in Fig. 9. The load generator generates requests for each client independently according to a time-varying Poisson process. The requests at the edge node are handled by the controller which decides either to accept the request or offload the request based on the policy for the current state of the edge node. If the action is "accept", the request is added to the request queue of the edge node, otherwise the request is offloaded to another healthy edge node via the proxy network. The Key Performance Indicator (KPI) collector copies the KPI metrics into a database at regular intervals. The RL modules uses these metrics to update its policies. The Subscriber/Notification (Sub/Notify) module notifies the controller about the updated policy. The controller now uses the updated policy to serve all future requests.
In our implementation, the number of clients served by an edge node and the request rate of the clients is constant for at-least 100 seconds. We define a step to be the execution of the testbed for 100 seconds. Each request runs a workload on the edge node and consumes CPU resources , where is a random variable. The states, actions, costs, next states for each step are stored in a buffer in the edge node. After the completion of a step, the KPI collector copies these buffers into a database. The RL module is then invoked, which loads its most recent policy and other parameters, and trains on this new data to update its policy. Once the updated policy is generated, it is copied in the edge node and is used by the controller for serving the requests for the next step.
We run our experiments for a total of 1000 steps, where and evolve according to Fig. 4 for different scenarios, similar to the previous set of experiments. We consider an edge server with buffer size X = 20, CPU capacity L = 20, = 2 cores, service-rate = 3.0 for each core, holding cost ℎ = 0.12. The CPU capacity is discretized into 20 states for utilization 0 − 100%, similar to the previous experiment. The CPU running cost is (ℓ) = 30 for ℓ ≥ 18, (ℓ) = −0.2 for 6 ≤ ℓ ≤ 17, and (ℓ) = 0 otherwise. The offload penalty is = 1 for ℓ ≥ 3 and = 10 for ℓ < 3. We assume that the discrete time discount factor = /( + ) equals 0.99.

A. Results
We run the experiments for SALMUT and baseline algorithm for a total of 1000 steps. We do not run the simulations for PPO and A2C algorithms in our testbed as these algorithms cannot be trained in real-time because the time they require to process each sample is more than the sampling interval. The performance of SALMUT and baseline algorithm is evaluated at every step by computing the discounted total cost for that step using the cost buffers which are stored in the database. The experiment is repeated 5 times and the median performance with an uncertainty band from the first to the third quartile are plotted in Fig. 10 along with the total request arrival rate ( ) in gray dotted lines. For Scenario 1 (Fig. 10a), we observe that the SALMUT algorithm outperforms the baseline algorithm right from the start, indicating that SALMUT updates its policy swiftly at the start and slowly converges towards optimal performance, whereas the baseline incurs high cost throughout. Since SALMUT policies converge towards optimal performance after some time, they are also able to adapt quickly in Scenarios 2-6 ( Fig. 10b-10f) and keep track of the time-varying arrival rates and number of users. We observe that SALMUT takes some time to learn a good policy, but once it learns the policy, it adjusts to frequent but small changes in and very well (see Fig. 10c and 10d). If the request rate changes drastically, the performance decreases a little (which is bound to happen as the total requests to process are much larger than the server's capacity) but the magnitude of the performance drop is much lesser in SALMUT as compared to the baseline, seen in Fig. 10b, 10e and 10f. It is because the baseline algorithms incur high overloading cost for these requests whereas SALMUT incurs offloading costs for the same requests. Further analysis on this is present in Section 4.2.2. . Comparing the number of times the system goes into the overloaded state at each step in the end-to-end testbed we created. We also plot the total request arrival rate ( ) on the right-hand side of y-axis in gray dotted lines.

B. Behavioral Analysis
We perform behavior analysis of the learned policy by observing the number of times the system enters into an overloaded state (denoted by ov ) and the number of incoming request offloaded by the edge node (denoted by off ) in a window of size 100. These plots are shown in Fig. 11 & 12.
We observe from Fig. 11 that the number of times the edge node goes into an overload state while following policy executed by SALMUT is much less than the baseline algorithm. Even when the system goes into an overloaded state, it is able to recover quickly and does not suffer from performance deterioration. From Fig. 12b and 12e we can observe that in Scenarios 2 and 5, when the request load increases drastically (at around 340 steps), off increases and its effects can also be seen in the overall discounted cost in Fig. 10b and 10e at around the same time. SALMUT is able to adapt its policy quickly and recover quickly. We observe in Fig. 12 that SALMUT performs more offloading as compared to the baseline algorithm.
A policy that offloads often and does not go into an overloaded state may not necessarily minimize the total cost. We did some further investigation by visualizing the scatterplot (Fig. 13) of the overload count ( ov ) on the y-axis and the offload count ( off ) on the x-axis for both SALMUT and the baseline algorithm for all the scenarios described in Fig. 4. Comparing the number of times the system performs offloading at each step in the end-to-end testbed we created. We also plot the total request arrival rate ( ) on the right-hand side of y-axis in gray dotted lines. We observe that SALMUT keeps ov much lower than the baseline algorithm at the cost of increased off . We observe from Fig. 13 that the slope for the plot is linear for baseline algorithms because they are offloading reactively. SALMUT, on the other hand, learns a behavior that is analogous to proactive offloading, where it benefits from the offloading action it takes by minimizing ov .
VII. CONCLUSION AND LIMITATIONS In this paper we considered a single node optimal policy for overload protection on the edge server in a time varying environment. We proposed a RL-based adaptive low-complexity admission control policy that exploits the structure of the optimal policy and finds a policy that is easy to interpret. Our proposed algorithm performs as well as the standard deep RL algorithms but has a better computational and storage complexity, thereby significantly reducing the total training time. Therefore, our proposed algorithm is more suitable for deployment in real systems for online training.
The results presented in this paper can be extended in several directions. In addition to CPU overload, one could consider other resource bottlenecks such as disk I/O, RAM utilization, etc. It may be desirable to simultaneously consider multiple resource constraints. Along similar lines, one could consider multiple applications with different resource requirements and different priority. If it can be established that the optimal policy in these more sophisticated setup has a threshold structure similar to Proposition 2, then we can apply the framework developed in this paper.
The discussion in this paper was restricted to a single node. These results could also provide a foundation to investigate node overload protection in multi-node clusters where additional challenges such as routing, link failures, and network topology shall be considered.
APPENDIX C PROOF OF OPTIMALITY OF SALMUT PROOF The choice of learning rates implies that there is a separation of timescales between the updates of (14) and (15). In particular, since 2 / 1 → 0, iteration (14) evolves at a faster timescale than iteration (15). Therefore, we first consider update (15) under the assumption that the policy , which updates at the slower timescale, is constant. We first provide a preliminary result.

Lemma 2 Let
denote the action-value function corresponding to the policy . Then, is Lipscitz continuous in .
PROOF This follows immediately from the Lipscitz continuity of in .
Hatem Abou-Zeid is a 5G Systems Developer at Ericsson Canada. He has 10+ years of R&D experience in communication networks spanning radio access networks, routing, and traffic engineering. He currently leads 5G system designs and intellectual property development in the areas of network intelligence and low latency communications. He serves on the Ericsson Government Industry Relations and University Engagements Committee where he directs academic research partnerships on autonomous networking and augmented reality communications. His research investigates the use of reinforcement learning, stochastic optimization, and deep learning to architect robust 5G/6G networks and applications -and his work has resulted in 60+ filed patents and publications in IEEE flagship journals and conferences. Prior to joining Ericsson, he was at Cisco Systems designing scalable traffic engineering and IP routing protocols for service provider and data-center networks. He holds a Ph.D. in Electrical and Computer Engineering from Queen's University. His collaborations with industry through a Bell Labs DAAD RISE Fellowship led to the commercialization of aspects of predictive video streaming, and his Thesis was nominated for an Outstanding Thesis Medal.
Emmanuel Thepie Fapi is currently a Data Scientist with Ericsson Montreal, Canada. He holds a master's degree in engineering mathematics and computer tools from Orleans University in France and a PhD in signal processing and telecommunications from IMT Atlantique in France (former Ecole des Telecommunications de Bretagne) in 2009. From 2010 to 2016 he worked with GENBAND US LLC, QNX software System Limited as audio software developer, MDA system as analyst and EasyG as senior DSP engineer in Vancouver, Canada. In 2017 he joined Amazon Lab 126 in Boston, USA as audio software developer for echo dot 3rd generation. His main areas of interest are 5G network, anomaly detection-based AI/ML, multi-resolution analysis for advanced signal processing, real-time embedded OS and IoT, voice and audio quality enhancement.
Hakimeh Purmehdi is a data scientist at Ericsson Global Artificial Intelligence Accelerator, which leads innovative AI/ML solutions for future wireless communication networks. She received her Ph.D. degree in electrical engineering from the Department of Electrical and Computer Engineering, University of Alberta, Edmonton, AB, Canada. After completing a postdoc in AI and image processing at the Radiology Department, University of Alberta, she co-founded Corowave, a startup to develop bio sensors to monitor human vital signals by leveraging radio frequency technology and machine learning. Before joining Ericsson, she was with Microsoft Research (MSR) as a research engineer, and contributed in the development of TextWorld, which is a testbed for reinforcement learning research projects. Her research focus is basically on the intersection of wireless communication (5G and beyond including resource management and edge computing), AI solutions (such as online learning, federated learning, reinforcement learning, deep learning), optimization, and biotech.