Yassine Hadjadj-Aoul

Soraya Ait

Access Control in NB-IoT Networks: A Deep Reinforcement Learning Strategy

Keywords: cellular IoT, massive access, reinforcement learning, access control, congestion control

The Internet of Things (IoT) is a key enabler of the digital mutation of our society. Driven by various services and applications, Machine Type Communications (MTC) will become an integral part of our daily life, over the next few years. Meeting the ITU-T requirements, in terms of density, battery longevity, coverage, price, and supported mechanisms and functionalities, Cellular IoT, and particularly Narrowband-IoT (NB-IoT), is identified as a promising candidate to handle massive MTC accesses. However, this massive connectivity would pose a huge challenge for network operators in terms of scalability. Indeed, the connection to the network in cellular IoT passes through a random access procedure and a high concentration of IoT devices would, very quickly, lead to a bottleneck. The latter procedure needs, then, to be enhanced as the connectivity would be considerable. With this in mind, we propose, in this paper, to apply the access class barring (ACB) mechanism to regulate the number of devices competing for the access. In order to derive the blocking factor, we formulated the access problem as a Markov decision process that we were able to solve using one of the most advanced deep reinforcement learning techniques. The evaluation of the proposed access control, through simulations, shows the effectiveness of our approach compared to existing approaches such as the adaptive one and the Proportional Integral Derivative (PID) controller. Indeed, it manages to keep the proportion of access attempts close to the optimum, despite the lack of accurate information on the number of access attempts.

I. INTRODUCTION

IoT objects connections and especially Machine-to-Machine (M2M) communications are considered as one of the most important evolutions of the Internet. Supporting these devices is, however, one of the most important challenges facing network operators [START_REF] Ait | Random Access Preamble Design and Detection for 3GPP Narrowband IoT Systems[END_REF]Lin, Adhikary, and Eric Wang]. Indeed, the huge number of devices that might try to access the network at the same time could lead to heavy congestion or even total saturation, with all the consequences that this may entail. Indeed, as can be seen in Figure 1, a very limited number of devices simultaneously trying to access the network may drop network performance down to zero, regardless of the available access possibilities [START_REF] Bouzouita | On the risk of congestion collapse in heavily congested M2M networks[END_REF] Bouzouita, Hadjadj-Aoult, Zangar, and Tabbane]. Under these circumstances, it seems obvious that effective access control mechanisms are needed to maintain a reasonable number of access attempts.

The Third Generation Partnership Project (3GPP) identified the overloading of the random access network (RAN) as a priority at an early stage and proposed several solutions. Among the suggested approaches, the Access Class Barring (ACB), proposed in version 8, and its extension, the Extended Access Barring (EAB), proposed in version 11, are certainly the most effective strategies [3GPP(2011)]. Indeed, these approaches tackle the problem at its root by preventing even the attempts to access the network. However, these approaches only provide a framework for congestion control, without giving a ready-made solution. Indeed, the main idea behind the ACB is to calculate a blocking factor to prevent terminals from accessing the network, but no solution for the calculation of this factor has been proposed.

The blocking factor calculation requires a good knowledge of the number of terminals willing to attempt access in order to deduce the optimal blocking probability. This information is unfortunately not available in the network (i.e., the state of the network is not observable). In order to solve this problem, two important challenges must be addressed: (1) estimating the number of devices attempting the access simultaneously, and (2) designing an access control strategy for the dynamic generation of the blocking factor.

Several solutions have been proposed to estimate the number of devices willing to access the network [START_REF] Bouzouita | Estimating the number of contending IoT devices in 5G networks: Revealing the invisible[END_REF] Bouzouita, Hadjadj-Aoul, Zangar, and Rubino]. These estimators are, however, highly noisy and dependent on the blocking factor. On the other hand, many existing techniques are dependent on a particular traffic pattern, leading to improper actions when the traffic pattern changes. In reality, IoT objects do not follow a single model but a mixture of models making the prediction of this type of traffic very difficult sometimes. IoTs may follow, indeed, different laws at the same time: Poisson (e.g., credit machine in shops), Uniform (e.g., traffic lights), and Beta (e.g., event driven). Therefore, we propose, in this paper, exploiting the potential of the most advanced reinforcement learning techniques in order to take into account this complex reality and deduce a sub-optimal control strategy. More specifically, we exploit the Twin Delayed Deep Deterministic policy gradient algorithm (TD3) [START_REF] Fujimoto | Addressing Function Approximation Error in Actor-Critic Methods[END_REF] to produce, from past estimates, the optimal blocking factor regardless of the uncertainties on the number of devices willing to access the network.

The different findings of this paper are summarized in the following:

• We propose a detailed and up-to-date state of the art.

• We describe a fluid model of IoT access in NB-IoT networks.

• We formulated the problem of IoT access as a Markov Decision Process (MDP). • We design a specific reward function in order to guide the agent to improve the quality of the solutions. • We provide an in-depth analysis of the problem. The remainder of this paper is organized as follows: Section II provides the fundamentals of the random access procedure, addressed in this paper, and gives an overview of the main techniques for congestion control in IoT networks, with a focus on cellular IoT networks. Section III describes the network access model for IoT terminals. Section IV presents the details of the proposed control solution, based on the TD3 algorithm, adapted to solve the blocking factor calculation problem. Section V presents the simulation environment of the proposed approach and shows its efficiency compared to the existing one. Finally, the paper concludes with a summary of the main advantages and achievements of the proposed system in Section VI.

II. STATE OF THE ART

A. Random Access Fundamentals

The Narrowband Physical Random Access CHannel (NPRACH) has been completely redesigned in NB-IoT to improve network coverage and power consumption, but also to accommodate the narrowband nature of NB-IoT [START_REF] Ait | Random Access Preamble Design and Detection for 3GPP Narrowband IoT Systems[END_REF]. Indeed, in Long-Term Evolution (LTE), the PRACH channel alone occupies more bandwidth than NB-IoT as a whole (1.08 MHz vs. 180 kHz). Each NB-IoT terminal, willing to connect or resynchronize to the base station on its uplink, after a long period of inactivity, should perform a random access procedure. The first step of the latter consists of transmitting a sequence of preambles on one of the frequencies, periodically allocated to the NPRACH channel which is called the Random Access Opportunity (RAO). The preamble consists of a set of four groups of OFDM symbols, as shown in Figure 2. Each group of symbols consists of a cyclic prefix (CP) and a set of data symbols. In order to maintain the orthogonality of random access transmissions on different sub-carriers, the CP must be long enough to compensate for long round-trip times, especially in cells as large as those targeted in NB-IoT (up to 35 km) [3GPP(2015)]. The higher the number of data symbols, the lower the CP overflow. On the other hand, this number should be kept small in order to control interference. In NB-IoT, the number of data symbols is set to 5 and two CP lengths are defined for the two NPRACH channel formats, namely 266.7 s and 66.7 s [START_REF] Ait | Random Access Preamble Design and Detection for 3GPP Narrowband IoT Systems[END_REF]Lin, Adhikary, and Eric Wang], [ETSI(2020a)].

For coverage extension purposes, the preamble can be repeated k times

(k = 2 i , i = 0, • • • , 7) [ETSI(2020b)].
The sequence of preambles sent by the terminal therefore consists of 4 × 2 i groups of symbols. The network can thus define up to three different configurations of the NPRACH resource per cell, depending on the considered coverage classes. The number of repetitions k is therefore defined for each configuration.

Each symbol group is modulated on a different subcarrier than the others. The NPRACH channel uses only the single tone mode with a 3.75 kHz spacing. A frequency band of up to 48 subcarriers can then be allocated to this channel with a baseband of 12 subcarriers. Thus, 12, 24, 36, or 48 contiguous subcarriers are allocated to this channel in each coverage class. Therefore, the terminal has 12, 24, 36 or 48 orthogonal preambles and randomly selects one to be transmitted. In addition, as illustrated in Figure 2, NB-IoT defines two hopping patterns in the frequency band allocated to the NPRACH: (i) a fixed pattern for hops between different symbol groups constituting the same preamble and (ii) a pseudo-random pattern for the preamble repetitions. Thus, within a preamble, a jump of one subcarrier is applied between the first and the second group of symbols and between the third and the fourth group of symbols. Another hop of six subcarriers is also applied between the second and third group of symbols. A pseudorandom model, based on the cell identifier and the expected number of repetitions, is applied to choose the sub-carrier indexes at the beginning of the different repetitions of the preamble [START_REF] Ait | Random Access Preamble Design and Detection for 3GPP Narrowband IoT Systems[END_REF].

The random access procedure in NB-IoT, illustrated in Figure 3, is a four-step exchange between the terminal and the base station [START_REF] Etsi | Evolved Universal Terrestrial Radio Access (E-UTRA); Radio Resource Control (RRC)[END_REF]]:

• The terminal transmits the selected preamble at the first RAO and sets a timer to receive the Random Access Response (RAR); at the terminal side, the terminal continues waiting until the timer expires; • The terminal then sends a connection request, using the resource allocated to it, and re-arms a contention resolution timer. This request, named msg3, carries the identity of the terminal. This procedure fails if the terminal doesn't receive one of the two responses from the base station within the time windows defined by the two timers. Collisions between preambles, sent by different terminals, are often the cause of the failure. Indeed, if two or more terminals choose the same preamble on the same ROA, each of their access attempt fails.

Each terminal, for which the access procedure has failed, observes a waiting time chosen uniformly and at random within a predefined interval, and then retransmits its preamble. The number of allowed retransmissions depends on the coverage class of the terminal. If this number is reached and the terminal still doesn't pass the access procedure, the terminal moves to the higher coverage class, if the latter is configured, or concludes to the definitive failure of the access procedure.

B. Related Work

Beyond the broadband generalization, 5G promises to improve our daily life through connected ecosystems. Indeed, 5G, via Massive Machine-Type Communications (mMTC), goes a lot further by enabling seamless and massive connectivity of things. If this vision of IoT seems very attractive, it also drives huge challenges, especially from the resource management point of view. Network operators have imperatively to scale their IoT networks in order to efficiently manage this excessively large number of sensors that should be connected, in the coming years.

As explained in Section II-A, IoT terminals connecting to the network should first initiate a random access procedure. However, the latter was initially designed for a limited number of terminals and the high density targeted by NB-IoT, and mMTC in general, can very quickly lead to a severe congestion. Indeed, the number of preambles available at each RAO being limited, the greater the number of terminals attempting to access the network, the greater the risk of collision, thus leading to the failure of the procedure for all the terminals having chosen the same preamble. The terminals that fail their access attempt can retransmit the preamble after observing a backoff time, but these retransmissions can also lead, on the one hand, to a spectral resource wasting, and, on the other hand, to increase energy consumption at the terminal level [START_REF] Harwahyu | Repetitions Versus Retransmissions: Tradeoff in Configuring NB-IoT Random Access Channels[END_REF].

Being a critical phase, the random access procedure has been the subject of numerous academic studies. Some of them, such as [START_REF] Baracat | NB-IoT Random Access Procedure Analysis[END_REF]], [START_REF] Jiang | RACH Preamble Repetition in NB-IoT Network[END_REF]Jiang, Deng, Condoluci, Guo, Nallanathan, and Dohler], [START_REF] Harwahyu | Optimization of Random Access Channel in NB-IoT[END_REF], have proposed analytical models for optimizing the success probability of the access attempts and the average access time in different network configurations and, in particular, under time constraints [START_REF] Harwahyu | Optimization of Random Access Channel in NB-IoT[END_REF]. Other works have focused on retransmissions. Thus, a Markov chain-based model was proposed to model the number of retransmissions in [START_REF] Harwahyu | Repetitions Versus Retransmissions: Tradeoff in Configuring NB-IoT Random Access Channels[END_REF] Harwahyu, Cheng, Tsai, Hwang, and Bianchi], [START_REF] Sun | Throughput Modeling and Analysis of Random Access in Narrowband Internet of Things[END_REF] Sun, Tong, Zhang, and He], and the authors proposed a model to find a trade-off between the number of repetitions planned in the physical layer and the number of retransmissions planned in the MAC layer and optimize these two values basing on a target successful probability. The study concluded that retransmissions considered in NPRACH can reduce the number of repetitions. These latter are only required under worse channel conditions.

In [START_REF] Ait | Random Access Preamble Design and Detection for 3GPP Narrowband IoT Systems[END_REF]Lin, Adhikary, and Eric Wang], [START_REF] Jeon | Effective Frequency Hopping Pattern for ToA Estimation in NB-IoT Random Access[END_REF]Jeon, Seo, and Jeong], [START_REF] Hwang | Efficient Detection and Synchronization of Superimposed NB-IoT NPRACH Preambles[END_REF]Hwang, Li, and Ma], the focus was on the transmission of the preamble and the estimation of the Time of Arrival (TA). Thus, a receiver-side detection algorithm, a new NPRACH frequency domain hopping model, and a Framework for the detection of multiple users have been proposed, respectively. In [Zhang et al.(5555)Zhang, Xie, and Wang], the TA of preambles that has suffered a collision is used to improve the performance of the random access procedure.

From the standardization side, congestion control at the network access level was identified early as a priority by the 3GPP and ETSI organizations [3GPP(2011)]. The cellular IoT, and particularly NB-IoT, therefore naturally inherit existing solutions. Among these solutions, we can find the ACB (Access Class Barring) mechanism and its extension EAB (Extended Access Barring), slotted random access, MTCspecific backoffs, dynamic allocation of resources, etc. [START_REF] Ali | LTE/LTE-A Random Access for Massive Machine-Type Communi-cations in Smart Cities[END_REF] Ali, Hossain, and Kim].

The ACB and EAB mechanisms are the ones that tackle the problem at its roots by blocking access to the network. The blocking parameters, namely the blocking probability p and a blocking time T b , are broadcasted in the System Information Block (SIB) at each RAO. Each terminal attempting to access the network generates an access probability q. If q < p, the terminal has permission to make its access attempt; otherwise, the latter is deferred for a time T b . In the EAB extension, the terminals are further classified within different priorities according to their QoS requirements and the EAB algorithm dynamically blocks low priority terminals based on the arrival rate by broadcasting a bitmap in SIB-14.

It seems clear that congestion control based on these mechanisms relies, entirely, on the blocking probability defined by the network. Indeed, if the blocking probability is too high, then a large number of terminals would pass the access control, thus leading to collisions and if, on the other hand, this probability is too small then, the collisions would be reduced, but a large number of terminals would switch to idle mode and this would lead to underused resources. Thus, it is essential to optimize the blocking probability to efficiently control the congestion at the access level.

A study of the performance of ACB and EAB was conducted in [START_REF] Toor | Comparative study of access class barring and extended access barring for machine type communications[END_REF]]. The comparison of the two techniques through simulation has shown that ACB is more suited to high delay constrained communications and EAB performs better in the case of energy-constrained terminals. However, the optimization of the blocking factor requires knowing the number of terminals willing to access the network at the base station level, which, in practice, is not the case. In fact, the base station doesn't know the number of terminals whose access attempts have been blocked.

Several mechanisms have been proposed to estimate the number of terminals attempting to access the network (including terminals blocked by the access control) in order to derive the blocking factor to be used. In [START_REF] Park | Adaptive Access Class Barring Method for Machine Generated Communications[END_REF]], considering the number of blocked terminals not known, the authors use a heuristic to adapt the probability of blocking. In [START_REF] Liu | Online Control of Preamble Groups with Priority in Massive IoT Networks[END_REF]Liu, Agiwal, Qu, and Jin], the proposed algorithm is based on a recursive Bayesian estimate of the active terminals in each class and based on this, preambles are allocated to the different classes. The algorithm was then improved by assigning an ACB blocking factor to each class, independently of the others, for better congestion control.

In [START_REF]Recursive Pseudo-Bayesian Access Class Barring for M2M Communications in LTE Systems[END_REF]Jin, Toor, Jung, and Seo], a recursive Bayesian estimate of active terminals, based on the number of unselected preambles, allows for calculating a blocking factor for sporadic terminal arrivals. In [START_REF] Cheng | Modeling and Analysis of an Extended Access Barring Algorithm for Machine-Type Communications in LTE-A Networks[END_REF]Cheng, Chen, Chen, and Wei], the performance of the EAB mechanism is studied for LTE-A networks. The optimal values of the paging cycle as well as the periodicity of SIB14 are then derived by an analytical model subjected to a targeted QoS constraints.

In this paper, we use on an estimator proposed in a previous work [START_REF] Bouzouita | Estimating the number of contending IoT devices in 5G networks: Revealing the invisible[END_REF]Bouzouita, Hadjadj-Aoul, Zangar, and Rubino] and, unlike the works cited above, we use reinforcement learning techniques, namely the TD3 algorithm, to derive an optimal blocking probability from a set of past estimates (an estimates' horizon). To our knowledge, this is the first time that the latter algorithm has been used in the management of massive accesses in NB-IoT networks.

III. A FLUID MODEL FOR IOT DEVICE ACCESS

The proposed model, which was firstly introduced in [START_REF] Bouzouita | Estimating the number of contending IoT devices in 5G networks: Revealing the invisible[END_REF]Bouzouita, Hadjadj-Aoul, Zangar, and Rubino], provides an overview of IoT devices executing the ACB algorithm. We consider in this work a simplification since we consider only one class of service.

During the random access attempt, the IoT devices compete for the same available preambles. As stated in the 3GPP standard, the number of preambles N must be an integer in the set {12, 24, 36, 48} [START_REF] Agiwal | Power Efficient Random Access for Massive NB-IoT Connectivity[END_REF] Agiwal, Maheshwari, and Jin].

In each Random Access CHannel (RACH) opportunity, these preambles are split into successful (i.e., chosen by only one device), collided (i.e., chosen by two or more devices) and idle (i.e., selected by none of the devices) preambles. In the following, we compute the average values of these quantities that we have determined in [START_REF] Bouzouita | Multiple Access Class Barring Factors Algorithm for M2M Communications in LTE-Advanced Networks[END_REF]Bouzouita, Hadjadj-Aoul, Zangar, Rubino, and Tabbane]. These quantities will be used by our algorithms.

Let's define q N = 1 -1/N . The average number of successful preambles N S , during the RACH opportunities, is given as follows (this is a classic "balls into bins" problem):

N S = q x2-1 N x 2
(1)

x 2 x 2,L x 1 x 1,L p x 1 (1 -p) x 1 µ x 1,L θ 1 x 2 θ 2 x 2,L θ x 2 q x2-1 N x 2 λ Subsystem 1 Subsystem 2
Fig. 4: System model. Subsystem 1 represents the terminals that would like to connect; the objects in the state variable x 1 represent those that can try to connect with a probability p, in the case of a failure they go into the waiting state x 1,L for a back-off time duration. Subsystem 2 represents the objects coming from the different classes that can try to choose a preamble. In the case of a collision, they may attempt access a number of times. They leave subsystem 2 when they succeed in being the only ones to have chosen a preamble or when they reach the maximum number of attempts (with a rate of θ).

where x 2 represents the number of devices attempting the access. As demonstrated in [START_REF] Bouzouita | Estimating the number of contending IoT devices in 5G networks: Revealing the invisible[END_REF]Bouzouita, Hadjadj-Aoul, Zangar, and Rubino], Equation ( 1) is maximized (i.e., derivative equals to zero) when the number of devices x * 2 attempting access simultaneously is equal to

x * 2 = - 1 ln q N (2)
Knowing the optimal number of devices accessing the network, one can obtain the corresponding number of successes N * S , which can be given by

N * S = - 1 eq N ln q N (3)
The average number of idle preambles N I is given by the following equation:

N I = N q x2 N . (4)
From ( 1) and ( 4), we obtain the expected number of failed preambles N F :

N F = N -(N S + N I ) .
(5)

The modeled system is an approximation of reality in many ways, in particular with regard to the limited and fixed number of access attempts. However, we preferred to simplify the model to make it more tractable (see Figure 4). Furthermore, a system where devices often reach the maximum number of attempts is an unstable system, which we are naturally trying to avoid. On the other hand, the Coverage Enhancement (CE) strategy, as introduced in NB-IoT, is not considered in this work, although it will be investigated in future work.

The proposed model is a fluid one: the involved quantities and the whole numbers are seen as real (continuous) quantities. The parameters used are listed below:

x 1 (t) is the number of backlogged devices at time t; -x 1,L (t) is the number of blocked devices waiting for a re-attempt at time t, after having failed an ACB check; -x 2 (t) is the total number of devices from the different classes that pass the ACB check and wait to start Random Access (RA) attempt at time t; -x 2,L (t) is the number of blocked devices at time t after a failed RA attempt and waiting to try again; -λ is the arrival rate of devices. Different traffic patterns could be considered, depending on the type of IoT applications; -µ is the rate of ACB re-attempts; -θ 1 is the rate of RA failure, which is equal to 1 -q x2-1 N when θ is equal to 0 (see last item); -θ 2 is the rate of RA re-attempts; -θ is the rate at which the devices abort the transmission after reaching the maximum number of RA attempts; in a correctly dimensioned system, we should have θ = 0; -p is the ACB factor. Now, we are ready to describe the evolution of the state variables x 1 (t), x 1,L (t), x 2 (t), and x 2,L (t), based on the model depicted in Figure 4. The model's dynamics is described by the following system of differential equations:

                     dx 1 dt = λ -x 1 + µ x 1,L , (6)
dx 1,L dt = (1 -p) x 1 -µ x 1,L , (7)
dx 2 dt = p x 1 -(θ + θ 1 + q x2-1 N ) x 2 + θ 2 x 2,L , (8) dx 2,L dt = θ 1 x 2 -θ 2 x 2,L . (9)
with the constraints given below: -x 1 , x 1,L , x 2 and x 2,L should be non negative, -λ i > 0, θ 1 > 0, θ 2 > 0, µ > 0, and θ ≥ 0,

-0 ≤ p ≤ 1.
In what follows, we assume that θ = 0, in order to simplify the model. Indeed, a system where devices often reach the maximum number of attempts is an unstable system, which we naturally try to avoid.

The model described in ( 5) is nonlinear and non-affine in the control. It can be easily demonstrated that the model described is unobservable, given its state [x 1 x 1,L x 2 x 2,L ] which cannot be precisely known. It is also uncontrollable because the blocking factor p can only partially impact the state. These properties make the synthesis of an optimal controller guaranteeing the stability of the system, described above very complex.

Although the state is not observable, it is possible to produce an estimate of the average number of devices attempting access x2 by inverting Equations ( 1) and ( 4). This gives a very noisy measure, but may nevertheless be useful for blocking IoTs, as demonstrated in [START_REF] Bouzouita | Estimating the number of contending IoT devices in 5G networks: Revealing the invisible[END_REF].

IV. REINFORCEMENT LEARNING-BASED ACCESS CONTROLLER FOR IOT DEVICES

The difficulty of observing the state of the system, described in the previous section, led us to consider strategies for inferring the blocking factor even in the presence of very noisy measurements. In this sense, we have focused on deep learning techniques, which have been very effective in automatically extracting system features in the presence of noisy or even incomplete data [Rolnick et al.(2017)Rolnick, Veit, Belongie, and Shavit].

Given the lack of data, we considered the Reinforcement Learning techniques class. More specifically, we considered the Twin Delayed Deep Deterministic policy gradient algorithm (TD3) technique, which can address a continuous action space, and which has been shown to be more effective in learning speed and performance than existing approaches [START_REF] Fujimoto | Addressing Function Approximation Error in Actor-Critic Methods[END_REF].

We formulate, in what follows, the problem of access in IoT as a reinforcement learning problem, in which an agent iteratively finds a suboptimal blocking factor, leading to a reduction of access contention.

A. Problem Formulation

In reinforcement learning [Sutton and Barto(2018)], there are two main entities, an environment and an agent. The process of learning occurs through the interaction between these entities with the aim for the agent to optimize a total income. At each step t, the agent obtains a representation of the state s t of the environment and picks an action a t , based on it. The agent thereafter applies this action on the environment. As a consequence, the environment passes into a new state s t+1 and the agent receives a reward r t corresponding to this transition as well as the representation of the new state. This interaction can be modeled as a Markov Decision Process (MDP) M = (S, A, P, R), with S the state space, A the action space, P the transition dynamics, and R the revenue. The behavior of the agent is defined by its policy π : S → A, which allows a state to be associated with an action when it is a deterministic system, or a distribution of actions when it is stochastic. The objective of such a system is to find the optimal policy π * allowing for maximizing the cumulative revenue.

In the problem of IoT access control, we define an MDP, where the State, the Action, and the Revenue are defined as follows:

• State: Given the non-availability of the number of devices attempting the access at a given time k, the state we consider is based on the collected estimated values. Since a single measurement of this number is necessarily very noisy, we consider a series of several measurements, which we believe allow us to better reveal the current state of the network. The state s k is, thus, defined as the vector (x k 2 , xk-1 2 , . . . , xk-H+1

2

) where H represents the measurement horizon.

In our problem, k progresses according to the preambles' arrival, whose frequency is constant.

• Action: At each step, the agent has to select the blocking factor p that will be considered by the IoT objects. This value is continuous and deterministic, in the problem we are considering, i.e., the same state s k will always give the same action a k . • Revenue: This is a feedback signal received by the agent from the environment after the completion of an action. Thus, at step k, the agent obtains a revenue r k as a consequence of the action a k that was performed in the state s k . This revenue will allow the agent to be informed of the quality of the executed action. The objective of the agent is to maximize this revenue. Note that the maximum number of successes is equal to the number of available preambles N , so this metric could be used as a parameter for the calculation of the revenue, which is given by the following equation:

r k = 1 N H k i=k-H+1 N i S ( 10
)
where N i S represents the number of successes at step i. Revenue is, therefore, maximized when the average revenue over a window of length H is maximized. Unlike the measurement of the number of terminals attempting the access (x k 2 ), this measurement is not subject to noise, which allows a better quality of control. However, it should be noted that this is an indirect result of the number of attempts, making it more complex to handle. The objective of such a system is to find the probability of blocking that maximizes the average reward. This is equivalent to reducing the distance between the real number of terminals attempting the access and the optimum. In order to achieve this objective, we rely on the TD3 algorithm.

The TD3 algorithm is an Actor-Critic approach, where the actor is a neural network that decides in a particular state of the action to be taken; the Critic network allows for knowing the value of being in a state and to choose a particular action. TD3 solves the problem of overvaluation in value estimation [Thrun and Schwartz(1993)], by introducing two Critic networks and taking the minimum between the two estimates. This approach is particularly interesting in our case given the inherent presence of measurement errors.

B. Arrival Regulation System

The diagram in Figure 5 describes the system for controlling the number of attempts of IoT objects. This system is based on the diffusion of the blocking factor to the devices, through the System Information Blocks (SIBs) that are propagated, and, more specifically, through the SIB Type14 block, which allows for spreading the access blocking parameters [START_REF] Etsi | Evolved Universal Terrestrial Radio Access (E-UTRA); Radio Resource Control (RRC)[END_REF]].

After receiving the blocking factor, the devices willing to make a transmission execute the ACB in order to proceed with the next steps, with a probability p, which is calculated by the proposed TD3-based controller. These devices can therefore attempt access by randomly selecting a preamble from the group of available preambles. Knowing the state of the preambles, the Base Station for 5G, also known as the gNodeB, can estimate the number of attempts that have been made. This estimate is very noisy, as the given model can only estimate averages in the case when there is at least one idle or successful preambles. To avoid too many variations in the estimate of the number of arrivals, we consider a moving average of this value.

The controller we have proposed receives these measures, together with the revenue, at the end of each access opportunity period. The revenue obtained will allow for determining the quality of the taken actions. These different elements are stored in a memory of past experiences. However, a random subset of this memory will allow for training the agent in a robust way, and choosing a new action.

These different actions are repeated periodically.

V. PERFORMANCE EVALUATION

After having described our proposed access controller, we evaluate, in this section, its performance, using a discrete-event simulator built under Simpy 1 .

We have considered an NB-IoT antenna in which the access requests arrive according to a Poisson's law with an average rate between two arrivals of 0.018 s. We considered a number 1 https://simpy.readthedocs.io/en/latest/ of preambles N equal to 12, with an arrival frequency equal to 0.1 s. In the considered system, each piece of equipment trying to access will be able to do it for a maximum of 16 times. Beyond this limit, the terminal abandons the transmission.

Unlike classical reinforcement learning problems, where the optimal value is generally not known, the optimum here is known and given by Equation (2). Thus, we compare the performance of our controller based on the TD3 technique to an adaptive approach, named ADAPT, and the Proportional Integral Derivative (PID) controller [Bouzouita et al.(2015)Bouzouita, Hadjadj-Aoul, Zangar, Tabbane, and Viho], which comes from control theory.

The adaptive approach consists of gradually increasing the probability of blocking when the number of attempts is above a predefined threshold higher than the optimal value, in order to block more devices. When the value is below a predefined threshold under the optimal value, the probability of blocking is gradually reduced, in order to let more devices attempt the access.

We considered a measurement horizon H equal to 10 for both the TD3 and the PID controllers. The use of a larger measurement window does not allow a significant performance improvement, which means that a window of 10 measurements sufficiently reflects the true state of the network.

Figure 6 shows the probability of blocking for the three considered strategies considered. The adaptive technique (see Figure 6a) starts with an access probability of 1 and adapts as traffic conditions change. The PID controller, in Figure 6b, has an access probability proportional to the estimation error, which makes the latter highly variable. For the strategy based on the TD3 algorithm, there is a first phase, lasting 1000 s, where the algorithm tries to explore the action space according to a uniform law (see Figure 6c). It is only after this phase that the algorithm begins to exploit its learning, which is refined as the experiments progress. One can note that, under TD3 (see Figure 6c), future actions are not related to past actions, contrary to the adaptive case. Indeed, the values of the actions can change completely, since they onhttps://www.overleaf.com/project/601056afa11a1d217c80c8acly depend on the state of the network, which can change very quickly.

Figure 7 describes the impact of the control strategies described earlier on the average access latency. We do not consider in these plots the devices having failed to transmit, after a maximum number of attempts. We can see in Figure 7a,b that the latency using ADAPT and PID is generally of the same order. Although the latency using TD3 is slightly lower during the exploration phase, it increases during the exploitation phase to reach a latency of an order of magnitude comparable to other approaches. This means that the TD3 algorithm has no advantage in terms of latency.

Although TD3 does not have a particular advantage in terms of latency, it can be seen in Figure 8 that, after an exploration phase, the revenue improves very significantly. This reward is clearly superior to the ADAPT and the PID controllers. Indeed, in a steady state, the average reward in TD3 is around 29.25% (see Figure 8c) while the reward for the ADAPT and the PID controllers is around 20.33% and the 22.84%, respectively (see Figure 8a,b).

We can see in Figure 9a that different strategies have different results in terms of the number of successful preambles. The average number of successful preambles for the ADAPT, PID, and TD3 techniques are 2.47, 2.74, and 3.52, respectively. Thus, the results obtained by ADAPT are the worst, followed by the PID controller, and finally the TD3-based strategy, which is clearly superior. These results represent a 42.51% improvement over the ADAPT strategy and a 22.16% improvement over the PID controller. The results obtained by TD3 are, thus, the closest to the optimum, which is equal to 4.61 that is obtained from Equation (3).

The number of access successes directly reflects the quality of the strategy to control the number of devices attempting the access. From Equation (3), one can compute the optimal number of attempts which corresponds to an average of 11.49 devices. With an average of 23.52 accesses, ADAPT is the worst performing strategy. The results of the PID controller are equal to 17.15 while the results of the TD3 strategy are equal to 15.70. It can also be seen that the number of abandons remains relatively high in ADAPT with 4.48% of the devices, while it is equal to 1.73% with the PID controller, and less than 0.63% for the TD3 strategy. This demonstrates the effectiveness of the proposed approach.

The results we have obtained in this paper show the superiority of the control through the reinforcement learning technique. This is due to several factors. The first factor concerns the variable being controlled. Indeed, the adaptive technique and the PID both use the control error, represented by the difference between the estimated value of the number of terminals accessing the network and the optimal number of terminals. The problem with this metric is the noise existing in the estimation of the number of terminals, as opposed to the number of successes, which is used in the revenue function, on which our solution is based. The second factor lies in the fact that deep learning techniques, in particular the TD3 algorithm on which our solution is based, allow us to better extract the true state of the network from noisy estimates, unlike the PID. The third factor resides in the fact that the learning technique, which we use, allows us to grasp a complex and highly nonlinear input pattern, which is not the case with the adaptive technique or even the PID.

It should be noted that, by using the reinforcement learning approach, we can improve performance as we attempt the access. The limitation remains, however, the estimation errors that lead to errors in the state representation, hence the importance of having accurate estimators.

VI. CONCLUSIONS

In this paper, we proposed a mechanism to control the congestion of the access network, which is considered as one of the most critical problems for IoT devices. We proposed to tackle the congestion at its root by effectively managing the random accesses of these devices through the use of the ACB mechanism.

The proposed access control mechanism is different from conventional methods, which are usually based on simple heuristics. Indeed, the proposed technique is based on recent advances in deep reinforcement learning, through the use of the TD3 algorithm. The proposed approach has, in addition, the advantage of learning from its environment and could therefore allow for adapting to the variation of the access pattern.

Simulation results show the superiority of the proposed approach, which manages to keep the number of access attempts close to the optimum, despite the lack of accurate data on the number of access attempts. This work also shows the potential to use learning techniques in environments where the state cannot be known precisely.

In our future work, we plan to improve the estimation of the number of attempts using learning techniques.

  Fig. 1: The average number of access successes as a function of the number of devices, for different access opportunities.

Fig. 2 :Fig. 3 :

 23 Fig. 2: Preamble sequence structure.

  Fig. 5: Arrival regulation system.

Fig. 6 :

 6 Fig.6: The access probability for the considered strategies.

Fig. 7 :

 7 Fig. 7: The average latency of the devices for the considered strategies.

Computing Machinery: New York, NY, USA, 2015;pp. 195-199, doi:10.1145


Hamza Ben-Ammar
email: hamza.ben-ammar@irisa.fr

Y Hadjadj-Aoul

Yassine Hadjadj

A GRASP-based Approach for Dynamic Cache Resources Placement in Future Networks

Keywords: Multi-cache systems, Cache allocation, Multi-objective optimization, GRASP, VNF placement

Dealing with the ever-increasing video traffic is certainly one of the major challenges facing Internet Service Providers (ISPs). In this context, the strategic placement of caches is seen as one of the most important remedies, especially with recent advances in the field of virtualization. Unlike the existing works, which only focus on the placement issue, we also consider the problem of determining the optimal amount of cache to place at each possible location. We formalize, in this paper, the problem of caches placement as a multi-objective optimization problem, in which we minimize both the average distance from which contents are retrieved and the peering links utilization. As the proposed problem is NP-hard, we propose to solve it using the Greedy Randomized Adaptive Search Procedure (GRASP) meta-heuristic. Simulations results reveal the quality of the obtained solutions compared to an exhaustive search method. At the same time, they reveal that the solution is not to put all resources at the edge or at the core, as some studies claim, but to partition them judiciously, which mainly depends on the objectives of the ISPs.

Introduction

The recent rise of Network Function Virtualization (NFV) enables Internet Service Providers (ISPs) to better leverage their infrastructures by enabling more dynamic/agile services' placement, with the ability of on-demand deployment [START_REF] Hawilo | Nfv: state of the art, challenges, and implementation in next generation mobile networks (vepc)[END_REF].

The expansion of virtualization to the field of content distribution offers new opportunities for ISPs to dynamically manage their shared storage assets [START_REF] Li | Caas: Caching as a service for 5g networks[END_REF]. . The question of caches' placement becomes, therefore, central given the limited resources and the continuous increase in data consumption [START_REF] Cisco | Cisco visual networking index: forecast and trends, 2017-2022[END_REF].

Several studies in the literature have dealt with the problem of caches' placement, but the results are, somehow, equivocal. In fact, some studies point out the effectiveness of caching at the edge of the network to bring content closer to end-users [START_REF] Bastug | Living on the edge: The role of proactive caching in 5g wireless networks[END_REF]. This allows popular contents to be retrieved much faster while significantly reducing the intra and inter ISPs amount of exchanged traffic. Some other studies highlighted the benefit of caching at the core of the network (i.e. at the Point of Presence (POP) level) [START_REF] Araldo | Cost-aware caching: Caching more (costly items) for less (isps operational expenditures)[END_REF] [START_REF] Rossi | On sizing ccn content stores by exploiting topological information[END_REF], this minimizes the use of peering links given the complete absence of redundancy between caches, which guarantee reduced costs for ISPs and good quality for contents providers. Consequently, the real problem is not to place all the content at the edge or at the core of the network, but rather to manage it efficiently, in such a way that it sometimes guarantees the contradictory objectives of the various stakeholders.

The deployment of an optimal caching system within a network infrastructure, up to the edge, is a very complex problem and remains an open issue [START_REF] Reddy | Effects of storage heterogeneity in distributed cache systems[END_REF]. Unlike the vast majority of existing work, we are not only interested in the spatial placement of caches in an infrastructure, but also in determining the optimal amount of cache to be placed at the different locations of the network, which makes the placement problem even harder.

We formalize the problem of caches placement as a multi-objective optimization problem, in which we aim to satisfy two conflicting objectives. The first objective is to minimize the average distance from which contents are retrieved, which tends to put the contents at the edge. The second objective is to minimize the content provider's load (i.e. peering links' utilization), which tends to put the contents at the core of the network. Since measuring these objectives is not easy in a practical use case, we consider a mathematical model that we have developed [START_REF] Ben-Ammar | On the performance analysis of distributed caching systems using a customizable markov chain model[END_REF], and that can easily be adapted to different caching strategies.

The problem being NP-hard, as explained in this paper, the resolution of the optimization problem can only be done for small and unrealistic network configurations. In this respect, we propose in the following to solve the problem using the Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic [START_REF] Feo | Greedy randomized adaptive search procedures[END_REF], which has demonstrated its effectiveness in resolving different types of combinatorial optimization problems.

In this paper, we propose new extensions and substantial improvements of our previous work [START_REF] Ben-Ammar | Efficiently allocating distributed caching resources in future smart networks[END_REF], which are summarized in the following points:

-We propose a detailed and up to date state of the art.

-We describe the solution in more detail by introducing three new algorithms, one explaining the adaptation of GRASP to the problem of cache placement, a second algorithm describing the construction phase and a third one describing the local search strategy.

-We analyze the complexity of the considered cache placement problem.

-We provide more results and an in-depth analysis of the problem.

The reminder of this paper is organized as follows. In section 2, we present the related work. Section 3 provides the detailed description of the cache placement problem and the proposed solutions. Then, the evaluation of our proposal is expressed in section 4. Finally, section 5 summarizes the achievements in this paper and introduces our future work.

Related Work

Many studies have investigated the problem of cache resources allocation and placement in the context of multi-cache networks [START_REF] Sahoo | A survey on replica server placement algorithms for content delivery networks[END_REF] (e.g., Content Delivery Networks "CDN", Information Centric Networking "ICN", etc.).

The work presented in [START_REF] Krishnan | The cache location problem[END_REF] by Krishnan et al. was one of the earliest studies that tackled the problem of the optimal cache resources placement. They examined the cache location problem in the case of transparent in-route caches in the context of web caching. The problem was modeled as a k-median problem, where the objective is to minimize the network traffic flow, and solutions were proposed based on dynamic programming and greedy heuristics. The classic k-median problem consists on finding k centers (i.e. cache resources) such that the clusters they form are the most compact (i.e. lower cost). The authors in [START_REF] Laoutaris | On the optimization of storage capacity allocation for content distribution[END_REF] and [START_REF] Laoutaris | Joint object placement and node dimensioning for internet content distribution[END_REF] studied the storage capacity allocation in hierarchical content distribution systems through a multi-commodity problem, which generalizes the single commodity k-median problem. They propose a two-step algorithm capable of solving such problems when tree graphs are considered, which has been extended through approximations to cover the case of general graphs. They also provided a greedy algorithm due to the high complexity of the exact solution. The authors in [START_REF] Jamin | Constrained mirror placement on the internet[END_REF] addressed the problem of placing mirrors of Internet content on a restricted set of hosts through modeling it as a slightly different version of the minimum k-center problem, considering the latency as the cost function to be optimized. In the minimum k-center problem, which is an NP-complete one, the objective is to find a placement of a given number of centers (i.e. content servers) such that the maximum distance from a node (i.e. end-user) to the nearest center is minimized. They proposed a greedy algorithm and a heuristic based on nodes' degree to solve the problem.

Later on, and with the proliferation of Content Delivery Networks, many works have focused on replica server (or cache resources) placement solutions in traditional and emerging CDN-based paradigms (cloud-based CDN, NFVbased CDN, etc.). In [START_REF] Yin | Netclust: A framework for scalable and pareto-optimal media server placement[END_REF], the authors proposed a solution to the media server placement problem by modeling it using the uncapacitated facility location problem. To ensure the scalability of their algorithm, they have considered the case where all the end-users locations can be potential placement of replica servers. In [START_REF] Rodolakis | Replicated server placement with qos constraints[END_REF], Rodolakis et al. introduced polynomial and pseudo-polynomial algorithms to solve the replica server placement problem using the splittable soft capacitated facility location model. Their aim is to find the best location of replica servers and the number of servers that should be used and assigned to end-users groups in a way that minimizes the cost and satisfies the Quality of Service (QoS). In [START_REF] Chen | Intra-cloud lightning: Building cdns in the cloud[END_REF], Chen et al. studied the problem of building distribution paths and placing Web server replicas in cloud CDNs to minimize the cost incurred on the CDN providers while satisfying QoS requirements for user requests. They provide an ILP formulation of the problem that happened to be NP-hard, and propose offline and online heuristics to solve it. In [START_REF] Benkacem | Optimal vnfs placement in cdn slicing over multi-cloud environment[END_REF], the authors presented a CDNaaS platform (CDN as a Service) that enables the creation of CDN slices across multiple cloud domains and the deployment of virtual resources (including virtual caches) from multiple IaaS providers (Infrastructure as a Service), where different VNFs (Virtual Network Functions) are running. They studied in their work the optimal placement of these VNFs by modeling this problem as two distinct Linear Integer problems, where the aim is to minimize the incurred cost of resource placement and maximize the Quality of Experience (QoE) of the virtual streaming service. By means of the bargaining game theory, they proposed a solution that ensures a fair trade-off between the cost and the QoE.

The study in [START_REF] Rossi | On sizing ccn content stores by exploiting topological information[END_REF] was probably the first attempt to investigate the cache allocation problem in Content Centric Networking (CCN). They used in their study different metrics to measure the centrality of routers like degree, closeness and betweenness in order to decide where the cache should be distributed along the network's nodes. They suggest that deploying more cache resources at the core nodes of the network is better than a placement at the edge. In later works [START_REF] Psaras | In-network cache management and resource allocation for information-centric networks[END_REF] [21], the authors have concluded the opposite, suggesting that placing larger caches at the edge is more effective. Wang et al., in their work [START_REF] Wang | Design and evaluation of the optimal cache allocation for content-centric networking[END_REF], have studied the impact of content popularity distribution on caching performance in CCN. They show that placing caches into the network core is better suited for content requests with uniform distribution and that in case of highly skewed popularity demands patterns, pushing cache resources to the edge yields better performance.

Considering a single metric or objective when dealing with the cache allocation problem clearly reduces the complexity of the problem, but has led many studies to find results that appear contradictory. There are many aspects in our proposal in this matter that makes it different from the existing works. We propose a versatile solution that takes into account at the same time more than one performance metric to solve the cache allocation problem and it can be tuned in order to seek some specific results. Moreover, the proposed tool builds a solution by measuring the contribution of all the nodes by the means of an analytic model capable of estimating the network performance, which will allow to take into account the impact of a node's performance on the others. In addition, more than one solution can be generated for the same use case, which gives more flexibility and enables adapting to additional constraints. We will see later that placing most (or all) of the cache resources at the edge or in the network core cannot be an absolute solution since it will depend on what performance metrics we try to optimize and what outcomes we aim to obtain.

3 Multi-objective cache placement strategy

Motivations

During the last decade, ISPs and CPs infrastructures underwent a major metamorphosis driven by new networking paradigms, namely: Software Defined Networks (SDN) [START_REF] Matias | Toward an sdn-enabled nfv architecture[END_REF] and Network Function Virtualization (NFV) [START_REF] Han | Network function virtualization: Challenges and opportunities for innovations[END_REF]. The upcoming advent of 5G will certainly represent the most important achievement of this evolution [START_REF] Andrews | What will 5g be?[END_REF]. In this context, static (planning) or dynamic (ondemand) network resources placement, especially caching, remains an open issue. Indeed, co-locating caching resources at the core of the network optimizes caches, but not the network. Distributing caches optimizes network resources, but reduces the efficiency of caches, due to the existing redundancy at the edge. The optimal placement of caching resources is one of the most important issues to address in multi-cache networks in general, especially due to the very expensive cost of deploying distributed storage capacities along the network.

In previous works that addressed the cache allocation problem, only one performance gain metric is generally considered (e.g. access latency, cache hit, etc.) to find a storage distribution solution or to compare between different possibilities. In this work, which was introduced in [START_REF] Ben-Ammar | Efficiently allocating distributed caching resources in future smart networks[END_REF], we use jointly the following two performance metrics to evaluate the cache gain: content provider load and average distance ratio. The first metric represents the amount of contents that were served by the origin server over all the requests sent in the network. The second one depicts the average distance travelled to get contents in the network over the obtained distance without caching. We chose these two metrics for their importance in representing the cost and gain obtained from the use of the in-network caching. A high content provider load means most of the requested contents are not served by the intermediate caches, and thus retrieved from their original location. Accessing the main source of contents is very expensive for network operators, and this is why it is important for them to keep the content provider load as low as possible. On the other hand, a low average distance to get contents means a better Quality of Experience for users (QoE). Hence, a good cache allocation strategy should find the best trade-off between these two metrics.

System assumptions

Let G = (V, E) be the graph representing a general network of caches, where V = {v 1 , ..., v M } depicts the nodes of the network and E ⊂ V × V is the set of links connecting the nodes. Each node in the network is equipped with

X Cache placement configuration f 1 (X) Content provider load of a cache configuration X f 2 (X)
Average distance ratio of a cache configuration X Tc

Represents the total cache resources to be distributed in the network P hit (r)

Hit probability of content cr P miss (r)

Miss probability of content cr Dist(i)

Distance from where the clients requests were generated to the node v i λ GRASP parameter a caching module used to store contents locally. Let C = {c 1 , ..., c R } be the set of the catalog's contents available for the users. We assume that all the accessible contents in the system have an identical size and are divided into small packets or chunks, which are in turn of the same size. The cache capacity is then expressed in terms of the number of contents or chunks that can be stored. All the available contents are stored permanently at one or more servers attached to some nodes within the network (i.e. origin server(s)). In the rest of the paper and for the sake of readability, we will use the term node/cache interchangeably as well as the terms rank/popularity and content/item/object.

Clients are attached to the network nodes, sending requests into the network looking for contents. The pattern of these requests is characterized by the Independent Reference Model (IRM) [START_REF] Dan | An approximate analysis of the LRU and FIFO buffer replacement schemes[END_REF]. By considering the IRM model, users generate an independent and identically distributed sequence of requests from the catalog C of R objects. Specifically, the probability p r to request an item c r from the set of available contents in the network is constant and follows a popularity law, where the contents are ranked decreasingly according to their popularity from 1 to R. Since about 80% of Internet traffic is generated by video related applications [START_REF] Cisco | Cisco visual networking index: forecast and trends, 2017-2022[END_REF], we address in our work videos services, where the contents feature a skewed popularity distribution. As already argued in many previous studies [START_REF] Fricker | Impact of traffic mix on caching performance in a content-centric network[END_REF], the latter fits the Zipf law: the probability to request the content of rank r is: p r = r -α / R i=1 i -α , where α, the skew of the distribution, depends on the type of the accessible objects [START_REF] Fricker | A versatile and accurate approximation for LRU cache performance[END_REF]. In the present work, the LRU algorithm is used to manage the node's content store and two caching schemes will be considered: Leave Copy Everywhere (LCE) [START_REF] Jacobson | Networking named content[END_REF] [START_REF] Ben-Ammar | A Markov chain-based Approximation of CCN caching Systems[END_REF] and Two Queue (2Q) [START_REF] Johnson | 2q: A low overhead high performance buffer management replacement algorithm[END_REF]. Under the LCE scheme, every data packet is always stored once received by a caching node. When the 2Q algorithm is used, the incoming contents are filtered to admit in the cache only the most popular ones.

Problem formulation

A cache allocation solution, which could be handled by an NFV orchestrator, can be defined by a vector X = (x 1 , . . . , x M ), where x i represents the amount of storage capacity placed in node v i . To compute the content provider load or the average distance ratio of a configuration of caches X, we use our model MACS (Markov chain-based Approximation of Caching Systems) [START_REF] Ben-Ammar | On the performance analysis of distributed caching systems using a customizable markov chain model[END_REF] [START_REF] Ben-Ammar | A versatile markov chain model for the performance analysis of CCN caching systems[END_REF]. MACS is an analytic tool that allows us to estimate the cache hit ratio of an interconnection of caches, which can be used to compute other performance metrics like the content provider load and the average distance ratio. By using MACS and for each cache allocation configuration X, we can evaluate the performance of the whole system in its steady-state and not just during a transient phase. This is opposed to the simplified and use case-specific models used to deal with the deployment of caches in previous works dealing with the cache placement problem.

Since in this work the caching capacity is expressed in terms of the number of contents that can be stored, then we have x i ∈ N. As we measure the caching gain through evaluating the content provider load and the average distance ratio in the network, our objective is to find a cache distribution solution such that the evaluation metrics that we have chosen are optimized (i.e. minimized). The cache placement is then formulated as a multi-objective optimization problem as follows:

min f 1 (X), f 2 (X) s.t. M i=1 x i ≤ T c , x i ∈ N for all i. (1)
The value of T c represents the total cache resources to be distributed in the network. The expressions f 1 (X) and f 2 (X) are both expressed as a percentage and represent, respectively, the content provider load and the average distance ratio of a cache placement configuration X using MACS. The primary function of MACS is to calculate the cache hit ratio of the network's nodes. Then, we can compute f 1 (X) and f 2 (X) as follows:

f 1 (X) = 100 × s i=1 P miss (i), f 2 (X) = 100 × s i=1 P hit (i) × Dist(i) × i-1 j=1 P miss (j) Dist(s)
.

(

) 2
The values P miss (i) and P hit (i) represent, respectively, the cache hit and cache miss of a network's node v i . The expression Dist(i) is the distance from where the clients requests were generated to the node v i . The index s represents the nearest node v s to the clients to which a content provider is attached (i.e. where a permanent copy of the contents is available). In the definition of f 1 (X) and f 2 (X) and for sake of clarity, we supposed that the network is formed by a line of s nodes numbered from 1 to s where the clients are attached to node v 1 and the content repository is located just after node v s . It has to be noted that of course, we can compute these metrics in any type of network topology and that we could consider the delay between nodes instead of distance and thus calculate the average network delay. Since here we are dealing with a multi-objective optimization problem, in which we want to minimize f 1 (X) and f 2 (X), the solutions will be a set of efficient points usually called the Pareto frontier. Pareto efficiency or optimality implies that a solution to a multi-objective problem is such that no single objective can be improved without deteriorating another one. In our case, a solution X * is said to be efficient if there is no other solution X such that

f 1 (X) < f 1 (X * ) and f 2 (X) ≤ f 2 (X * ) at the same time, or f 2 (X) < f 2 (X * ) and f 1 (X) ≤ f 1 (X * ).
Given that integer nonlinear programming is an NPhard problem, solving the cache allocation problem as we modeled below will come at a very high computational cost. More specifically and due to the nonlinearity of the objective functions, we need to perform an exhaustive search method in order to enumerate all possible candidates that respect the problem constraints and find the set of optimal cache distributions. If we look closely to our formulation of the problem, the task of enumerating all possible candidates comes down to computing the weak composition of an integer n into k parts, i.e., writing n as the sum of a sequence of non-negative integers. A weak composition C n,k [START_REF] Page | Generalized algorithm for restricted weak composition generation[END_REF] has a cardinality of 3.4 Solving cache allocation problem using GRASP

|C n,k | = n + k -1 k -1 = (n + k -1)! n!(k -1)! . (3)

Mono-objective GRASP

The Greedy Randomized Adaptive Search Procedure or GRASP [START_REF] Feo | Greedy randomized adaptive search procedures[END_REF] is an iterative process, where each iteration consists basically of two steps: construction and local search. The construction phase seeks to build a feasible solution using a greedy randomized approach, whose neighborhood will be investigated during the local search in order to find a local optimum. The pseudo-code of Algorithm 1 depicts the main blocks of a mono-objective GRASP procedure, where Max_Iterations is the number of iterations that are performed (later, we will see the role of the parameter λ and the case of multi-objective GRASP). The best overall solution is, then, kept as the final result. return Best_Solution; 13: end function the solution S to be built during the construction phase is defined by a vector X = (x 1 , . . . , x M ), where x i represents the amount of storage capacity placed in node v i . Initially, no cache resources are allocated to the nodes, so at the beginning, S = (0, . . . , 0). The set CS will contain the candidate elements, which will be used for the solution S. In our case and at each step, CS will contain a set of cache placement configurations X i where a partial resource that we denote P c , is taken from the total available cache T c and allocated to one of the network's nodes. If we have, for example, a network with three nodes, T c = 100 and P c = 10, the initial candidate set will then be: CS = {(10, 0, 0), (0, 10, 0), (0, 0, 10)}.

Each candidate is then evaluated with a greedy function in order to build a restricted candidate list RCL, which will contain some of the candidate set who have the best evaluation values (e.g., RCL = {(10, 0, 0), (0, 10, 0)}). The limitation criteria of the list cardinality can be either based on the number of elements or based on their quality, as we did in Algorithm 2 (line 18). The elements added to the RCL list will then be those having an evaluation value inferior to the threshold (i.e., f (X) ∈ [f min , f min + λ(f max -f min )]). The value of λ will control the insertion condition of candidate elements to RCL (λ ∈ [0, 1]). The case λ = 1 is equivalent to a random construction, while λ = 0 corresponds to a pure greedy algorithm. Once RCL is built, one element is randomly selected and added to the solution S being built. The candidate list CS and the evaluation function f (CS) are then updated and the construction is repeated (line 7 to 24) until the total use of the cache budget T c . If we consider for example that the second element from RCL has been chosen, the current partial solution will then be S = (0, 10, 0) and the new candidate list will contain: CS = {(10, 10, 0), (0, 20, 0), (0, 10, 10)}.

Once the cache budget T c is distributed, the local search will seek to improve the generated solution (e.g., S = (20, 40, 40)) by evaluating its neighborhood (Algorithm 3). The efficiency of a local search method depends on many aspects, such as the neighborhood structure of the considered solution, the neighbors search technique and the starting solution itself. Two methods can be used for the neighborhood search: the best-improving strategy Algorithm 2 Construction phase 1: function Greedy_Randomized_Construction(λ) 2:

for i = 1, . . . , M do 3:

x i ← 0; // Cache allocated for each node v i 4:

end for 5:

S ← (x 1 , . . . , x M ); // Current solution 6:

CS ← ∅; // Initial candidate set CS 7:

while Tc = 0 do // Construction of the solution S 8:

Tc ← Tc -Pc 9:

for i = 1, . . . , M do // Create candidate set CS 10:

x i ← x i + Pc; 11:

X ← (x 1 , . . . , x M ); 12:

CS ← CS ∪ {X}; 13:

x i ← x i -Pc; 14:

end for 15:

Evaluate the incremental costs f (X) ∀X ∈ CS; 16:

f min ← min{f (X) | X ∈ CS}; 17: f max ← max{f (X) | X ∈ CS}; 18: RCL ← {X ∈ CS|f (X) ≤ f min + λ(f max -f min )}; 19:
Select an element X * from the RCL at random; 20:

S ← {X * = (x * 1 , . . . , x * M )}; 21:

for i = 1, . . . , M do 22:

x i ← x * i ; 23:

end for 24:

end while 25:

return S; 26: end function or the first-improving one. The best-improving strategy consists on investigating all the neighbors and the current solution will then be replaced by the best neighbor found. In the case when a first-improving method is used, the current solution will be replaced by the first neighbor whose evaluation value is better. In our case, we used for the neighborhood search a bestimproving strategy as follows: starting from the solution generated by the greedy randomized construction, we transfer an amount of cache P c from one node to another and explore all the possible cases looking for a cache configuration whose evaluation function value is better than the current one (e.g., Neighbor(S) = {(10, 50, 40), [START_REF] Ben-Ammar | A Markov chain-based Approximation of CCN caching Systems[END_REF][START_REF] Ben-Ammar | A Markov chain-based Approximation of CCN caching Systems[END_REF]40), etc.}). We repeat these steps until the current solution can no longer be improved, which then will be returned as the output of the local search procedure of GRASP.

As for the complexity of GRASP algorithms (i.e. construction and local search) applied to our formulation of the cache allocation problem, we have a complexity of O(T c M ) for the construction phase and O(M 2 ) for the local search phase.

Multi-objective GRASP

In single-objective GRASP, only one greedy function is used to evaluate the candidate solutions during the construction and local search phases. In multi-objective GRASP [START_REF] Marti | Multiobjective grasp with path relinking[END_REF], we have in the general case k greedy functions (x 1 , . . . , x M ) ← S; 4:

for i = 1, . . . , M do 5:

x i ← x i -Pc; 6:

for j = 1, . . . , i -1 do // Cache transfer 7:

x j ← x j + Pc; 8:

if f (x 1 , . . . , x M ) < f (S) then 9:

S ← (x 1 , . . . , x M ) 10:

end if 11:

x j ← x j -Pc; 12:

end for 13:

for j = i + 1, . . . , M do // Cache transfer 14:

x j ← x j + Pc; 15:

if f (x 1 , . . . , x M ) < f (S) then 16:

S ← (x 1 , . . . , x M ) 17:

end if 18:

x j ← x j -Pc; 19:

end for 20:

end for 21:

while Solution S is not locally optimal 22: return S; 23: end function

(f 1 (X), f 2 (X), . . . , f k (X)).
The evaluation of a candidate element X and the different objective functions can be achieved using the following two ways:

-Pure construction/local search: this method consists on using one single objective during each phase of the solution generation. The selection of which evaluation function to be used in each iteration can be done using either a pure-random approach or a pure-ordered approach. In the first method, the entire construction or local search is guided by only one single evaluation function that we select randomly from the set of the objective functions (f 1 (X), . . . , f k (X)). In the second method, we select a greedy function in an ordered way and one at a time and use it in all the steps of the construction phase or the local search. In other words, the candidate elements are evaluated with f 1 (X) during the first iteration. Then, we use f 2 (X) in the second iteration, and so on until we reach the k +1 th iteration, in which we go back again to f 1 (X). -Combined construction/local search: this method consists on using more than one greedy function in each iteration following either a sequential combined approach or weighted combined approach. Using a sequential combined method means that each step of the construction or local search is guided by a different evaluation function, which can be chosen randomly or in an ordered way. When the weighted combined method is applied, a weighted combination of the objective functions is used in each step of the construction or local search1 . We can either change the weights between the steps of each phase or keep them the same during the whole process. It has to be noted that the weights can help us scale evaluations functions having significantly varied magnitudes into similar and comparable ones. In addition, some greedy functions in multi-objective optimization can be minimized while others maximized. In this case, the weights can take positive and negative values in order to take into account this fact.

In our case, we have two evaluation functions to be used in the multiobjective GRASP: f 1 (X) and f 2 (X) and there are many methods that can be used to compute the outcome of each configuration in the construction and local search phases. For example, one can use f 1 (X) in the construction phase and f 2 (X) during the local search and vice versa, or choose randomly between the objective functions during each GRASP iteration. We can also consider a weighted combined method (f (X) = w 1 f 1 (X)+w 2 f 2 (X)). The choice of which method to be used to evaluate a candidate solution (or partial solution) can depend on some desired results that should be achieved or some constraints that should be respected.

In our work, we considered two methods to generate the solutions based on the defined objective functions f 1 (X) and f 2 (X). In the first method, which matches a pure-ordered approach, we use in each iteration one objective function (f 1 (X) or f 2 (X)) during the construction phase. The other one is then used during the local search. Then, we alternate between the selected functions for each phase in the next iteration. For example, if we chose in the first iteration respectively f 1 (X) and f 2 (X) for the construction and local search phases then, in the second iteration, we use f 1 (X) in the local search and f 2 (X) in the construction phase, etc. This approach will allow us to produce diversified solutions of good quality. In the second method, we used a weighted combination of the evaluation functions as follows:

f (X) = 0.5 × |f 1 (X) -100| |Opt(f 1 (X)) -100| + |f 2 (X) -100| |Opt(f 2 (X)) -100| × 100. (4)
The expressions Opt(f 1 (X)) and Opt(f 2 (X)) represent respectively the theoretical optimal values of the metrics f 1 (X) and f 2 (X) for a fixed cache resources budget T c . More specifically, Opt(f 1 (X)) is obtained by allocating all the available cache resources at the root node and then, computing the content provider load. As for Opt(f 2 (X)), it is obtained by computing the average distance ratio metric where all the total cache resources are placed at one-hop from the clients. Since here we want to minimize f 1 (X) and f 2 (X) (expressed as percentages), then the range of values taken by these functions is: [Opt(f i (X)), 100] for i in {1, 2}. The value 100 represents the worst case, i.e., where no cache resources were allocated and thus, all the contents are retrieved from the main source and the average distance to get objects is not reduced. So, what we did is to compute how much improvement can be achieved in each of these performance metrics relatively to the optimal values that can be reached. For example, and for a certain configuration X = (x 1 , . . . , x M ), if we have f 1 (X) = 40% and Opt(f 1 (X)) = 20%, then (|40-100|/|20-100|)×100 = 75%. This value means that we have achieved 75% of the optimal outcome of the content provider load.

The evaluation function f (X) can be seen as a ratio of efficiency where the aim is to improve as much as possible the network's overall performance. It is also a mean to scale the evaluation functions f 1 (X) and f 2 (X) into similar and comparable magnitudes. In addition, the weighting coefficients (fixed to 0.5 in our case) can be tuned in order to give more importance to one metric over the other. In the case where the weighted combined approach defined by f (X) is adopted, the cache placement is formulated as the following optimization problem: max f (X)

s.t. M i=1 x i ≤ T c , x i ∈ N for all i. (5)

Performance evaluation

In this section, we present the evaluation results of the cache allocation problem using the methods presented previously. We will expose at first different results comparing the outcomes of the metaheuristic to the optimal solutions (i.e. obtained using an exhaustive search approach). Then, we will display some of the results obtained using our application of GRASP to the problem that we have formulated, to have an idea about the solutions that can be proposed by our approaches.

Simulation configuration

The different evaluations were conducted on a typical three-level network that contains 21 nodes forming a perfect 4-ary tree topology where the distance and the latency between each two adjacent nodes are the same (see Figure 1). We considered in our experiments a catalog of contents containing 20, 000 1-chunk sized objects whose popularity distribution follows the Zipf's law. Permanent copies of the available contents are hosted on one repository attached to the root node of the network, and the users are attached to the network's leaves (i.e. level 1 of the network). Following common practice [START_REF] Dan | An approximate analysis of the LRU and FIFO buffer replacement schemes[END_REF]- [START_REF] Che | Hierarchical web caching systems: modeling, design and experimental results[END_REF], we assume in this work that after a cache miss and when a content is decided to be cached by a node, it will be downloaded instantaneously. The contents requested by the different clients are

Tc = 20% α = 1.0 α X f 1 (X) f 2 (X) Tc X f 1 (X) f 2 (X)
forwarded according to the Shortest Path Routing (SPR) algorithm [START_REF] Wang | Ospfn: An ospf based routing protocol for named data networking[END_REF]. With SPR, when a client's interest cannot be satisfied by a node, it is forwarded along the shortest path to the closest permanent copy of the requested content.

We tested different values of the Zipf law's skew parameter α going from 0.8, corresponding to User Generated Contents (UGC) like Youtube, to 1.2, corresponding to a Video on Demand (VoD) service [START_REF] Guillemin | Volatility of youtube content in orange networks and consequences[END_REF].

The parameter λ that controls the amounts of greediness and randomness in GRASP was set to 0.5. Indeed, by choosing a greedy approach (λ = 0), there is a high chance to stick at a local minimum. Besides, by choosing a completely random approach (λ = 1) one risks to not converge towards the good solution. A λ in between allows to correctly explore the space of solutions.

The total cache T c is expressed as a ratio of the catalog size. Two caching strategies were used during the experiments: LCE and 2Q. The 2Q policy is, of course, more efficient than LCE as it was shown in [START_REF] Ben-Ammar | On the performance analysis of distributed caching systems using a customizable markov chain model[END_REF] but the aim here is to see the behavior of our model where different caching strategies are used. As we mentioned previously, the network performance is evaluated using the content provider load and average distance ratio metrics. For the sake of simplicity, the cache resources are allocated in a way that the nodes located on the same level of the network have the same cache size. Since there are 16 nodes on the first level of the network, P c should be a multiple of 16 and in our case, it was set to 16. Thus, a cache resource placement can be described as X = (x 1 , x 2 , x 3 ), where x i represents the total cache allocated at level i of the network.

Model results and analysis

In Figures 23, we compare the network's performance metrics of the different cache distribution solutions generated by GRASP (20 iterations) with

Tc = 20% α = 1.0 α X f 1 (X) f 2 (X) Tc X f 1 (X) f 2 (X)
the Pareto front using the separate evaluation functions approach (content provider load and average distance ratio metrics). We can see from the plots how the solutions produced by GRASP, independently from the used caching scheme, are very close to the set of dominant points in the different tested scenarios, which reflects the good quality of the metaheuristic outcomes.

In Figure 4-5, we compare the solutions obtained using the weighted combined approach with the optimal values (only the best solution obtained with GRASP is shown). The results in these graphs also show the efficiency of the metaheuristic in giving solutions close to the optimal ones. When the Zipf's parameter α is set to 0.8, we observe that the solutions generated by GRASP are not as close to the optimal values as the results obtained in the other cases. Having a low value of α (α < 1) means a lower difference in popularity between the different contents, which makes it more difficult to construct cache distribution solutions approaching the optimal performance. In Tables 23, we display the cache allocation solutions generated by GRASP (only the results of four iterations of GRASP are shown) using separate evaluation functions approach and testing two different caching schemes: LCE (Table 2) and 2Q (Table 3). Depending on the Zipf law's parameter α, the total cache resources available T c and the adopted caching strategy, different solutions are generated using the proposed GRASP-based algorithms. The choice of the final solutions between the different proposed ones can be based on some constraints that should be respected. For example, and under the LCE policy, if T c = 20% and α = 1.2 (Table 2) and if the priority is to minimize the content provider load (f 1 (X)), then the allocation X = (1088, 800, 2208) is the best one. In case when the 2Q scheme is used, if α = 1.0 and T c = 15% (Table 3) and one wants to minimize first the average distance ratio (f 2 (X)), then the allocation X = (1408, 768, 896) is the one to choose.

Tc = 20% α = 1.0 α X f (X) Tc X f (
Tc = 20% α = 1.0 α X f (X) Tc X f (X)
In Tables 45, we expose the cache allocation solutions generated by GRASP using a weighted combined evaluation approach. In this scenario, the objective is to optimize the overall network performance without considering separately the evaluation metrics. The proposed solution will be the cache allocation that gives the best outcome. For example, and under the LCE strategy, if T c = 20% and α = 1.0 (Table 4), the solution X = (1056, 816, 2224) is the best one. In case when the 2Q scheme is used and if we have for example α = 1.0 and T c = 25% then, the cache distribution X = (1328, 1056, 2736) is the best solution generated by GRASP.

If we compare between LCE and 2Q in terms of network performance when different cache allocation solutions are used, the 2Q policy generally has better outcomes than LCE. However, in some cases the LCE strategy presents better results. For example, if we look at Tables 2-3 and in the case where α = 1.0 and T c = 25%, the cache allocation X = (1264, 1184, 2672) when LCE is used achieves better performance than the cache allocation X = (64, 3200, 1856) when 2Q is applied. This result reinforces the importance of the cache's resources placement in distributed networks and how it can affect drastically the network performance.

We can see from the different presented results that there is no absolute solution for the cache allocation problem and it is not a question about whether to cache at the edge or in the core. Depending on the network's configuration and the objectives that one wants to achieve, multiple solutions can be adopted. Other metrics can be used as evaluation functions during the building of the solutions instead of those that we used in this work. The aim of our proposal is to give a tool capable of efficiently allocating distributed caching resources and versatile enough to adapt to specific desired network performance and constraints.

Conclusion

In this paper, the optimal placement of caching resources is investigated. The cache allocation issue is one of the most important problems to address when studying multi-cache networks because of the expensive cost of deploying distributed storage resources along the network. This issue is all the more important in the context of NFV, where placement is undoubtedly one of the most important keys for network optimization. In this regard, we propose an approach that solves the trade-off between minimizing the number of requests served at the origin server and minimizing the distance to retrieve contents. To do so, we modelled the cache allocation problem as a multi-objective integer nonlinear program, where our analytical tool MACS is used to evaluate the objective functions. Our formulation of the problem turned out to be an NP-hard problem. Thus, we proposed an adaptation of the metaheuristic GRASP to solve the problem using different evaluation functions to generate the solutions. The tests carried out were able to show the closeness of the results obtained compared to an optimal approach, in the case of different traffic patterns and cache sizes. By analyzing the different obtained results, we have shown that there is no absolute solution for the cache allocation problem and in contrast to the conclusions made in previous works, it is not a question about whether to cache at the edge or in the core of the network. The distribution of cache resources will depend on the network's configuration and the objectives that one wants to achieve. The versatility of our proposal allows it to be applied to any arbitrary network topology, and it can include other cost functions to be used as objective functions like, for example, the financial cost of cache resources deployment and management. This will allow us to study caching from an economic point of view, which will be the scope of our future work.

  In our case, n = T c and k = M , where the set of M non-negative integers has a sum equal to T c and represents the cache resources allocated to each node of the network. It is clear that |C n,k | is huge for high values of n and k. Therefore, we propose the use of the meta-heuristic GRASP to solve the cache placement problem (see the model (1)).

Algorithm 3

 3 Local search phase 1: function Local_Search(S) 2: do 3:

Fig. 1 :

 1 Fig. 1: An example of a network architecture for content delivery with cache-enabled nodes.

Fig. 2 :

 2 Fig. 2: Comparison between the Pareto front and GRASP solutions under the LCE scheme.

Fig. 3 :

 3 Fig. 3: Comparison between the Pareto front and GRASP solutions under the 2Q scheme.

Fig. 4 :Fig. 5 :

 45 Fig.4: Performance optimization vs total cache size using GRASP compared to the optimal values under the LCE scheme.

Table 1 :

 1 Summary of the notations.

	Term	Desciption
	M	Number of nodes in the network
	R	Number of items in the catalog
	N	Cache size
	cr	Content with a popularity/rank r
	pr	Probability to request an item cr
	α	Zipf law distribution parameter

Table 2 :

 2 Cache allocation solutions using GRASP with two separate evaluation functions when LCE is used.

Table 3 :

 3 Cache allocation solutions using GRASP with two separate evaluation functions when 2Q is used.

Table 4 :

 4 Cache allocation solutions using GRASP with weighted combined evaluation function when LCE is used.

Table 5 :

 5 Cache allocation solutions using GRASP with weighted combined evaluation function when 2Q is used.

	X)

Weighted combined construction: f (X) = k i=1 w i f i (X), where w i is the weight of the evaluation function f i (X).