Sabrine Aroua
email: sabrine.aroua@univ-lr.frgquadrio

Giacomo Quadrio

Yacine Ghamri-Doudane

Ombretta Gaggi
email: gaggi@math.unipd.it

Claudio Enrico Palazzi
email: cpalazzi@math.unipd.it

QoS-aware Reinforcement Learning for Multimedia Traffic Scheduling in Home Area Networks

Keywords: interactive multimedia, QoS, Reinforcement Learning (RL), wireless

Cloud-based interactive multimedia applications such as virtual games and video streaming are gaining high popularity. However, giving the high bandwidth consumption, the remote execution can negatively impact the quality of the multimedia traffic. In such a realm, data travel different communication networks from the cloud to the final users crossing the last meters the home's access point (AP). In such a scenario, the quality-of-service (QoS) support is a challenging task, particularly in the home network environment, with heterogeneous applications simultaneously running and consuming the available bandwidth. To address this issue, we propose ReiLeCS, a Reinforcement Learning-based Controller and Scheduler for interactive multimedia traffic in Home Area Networks (HAN). Through reinforcement learning and the maximization of a reward function, it enables the AP to schedule the arriving multimedia traffic from the cloud according to their required QoS. Simulation results using real multimedia traffic conditions demonstrate that ReiLeCS achieves better performances compared with existing packet scheduling policies.

I. INTRODUCTION

Cloud technologies represent a game changer in how we enjoy multimedia contents [START_REF] Lal | Understanding the impact of cloud-based services adoption on organizational flexibility: An exploratory study[END_REF]. The possibility to transfer the storage and the computational power to remote servers allows users to have access to services and experiences that, until a few years ago, would have required dedicated multimedia supports (e.g., DVDs) or dedicated hardware (e.g, game consoles). Instead, to enjoy them, tiny clients or any other device already present at home suffice.

The plethora of services that can be offered through the cloud is vast, but the most challenging are the interactive multimedia services (e.g., cloud gaming), which have to guarantee a reactive interaction with the users. For this reason, this new category of services requires both high amount of bandwidth and low end-to-end latency [START_REF] Quadrio | Network analysis of the steam in-home streaming game system[END_REF], [START_REF] Claypool | Thin to win? Network performance analysis of the OnLive thin client game system[END_REF]. This is not a simple task but some solutions are already being studied.

Figure 1 depicts a typical scenario for the remote fruition of multimedia contents. Relaying on remote execution, the data is usually generated and transmitted from the cloudserver to an access point (AP) of a home area network (HAN) which sends the data to the user's device. The data are transmitted from the cloud-server to the AP through data connections, e.g., fast optical connections or even mobile 4G This work is partially funded by the Department of Mathematics of the University of Padua through the BIRD191227 project. or 5G connections. However, when the data reach the HAN, smart home appliances and multiple users could be connected to the AP and intensively using the network to enjoy either high quality or interactive multimedia services [START_REF] Sabrine | A distributed cooperative spectrum resource allocation in smart home cognitive wireless sensor networks[END_REF]. A scenario that is more and more frequent, especially during these days where the COVID-19 pandemic drastically transformed the global network usage [START_REF] Bbc | Netflix to cut streaming quality in Europe for 30 days[END_REF], [START_REF] Nokia | Network traffic insights in the time of COVID-19: April 9 update[END_REF]. Therefore, the HAN available bandwidth could become crowded and the provision of the required QoS for multimedia applications challenging.

Therefore the AP must smartly deliver the multimedia traffic to the final users in order to guarantee a proper quality of experience (QoE), taking ito account the QoS requirements of each application and the available network resources. In this paper, we propose the Reinforcement Learning-based Controller and Scheduler (ReiLeCS) for interactive multimedia traffic in HANs. ReiLeCS enables the AP to adapt its multimedia traffic control and scheduling to the available bandwidth in the HAN in such a way to deliver the traffic flows according to their required QoS. We identify the QoS of the different services in terms of data-rate, latency and reliability.

We exploit the heterogeneous QoS requirements of the multimedia traffic and we classify them into multiple classes of traffic. Then, we formulate the scheduling problem as a Markov decision-based framework to which we associate a carefully designed reward function by considering the QoS requirements of every traffic class. ReiLeCS deploys Reinforcement Learning (RL) techniques to enable the AP to learn the policy that best and adequately delivers the traffic purely through experience [START_REF] Sutton | Reinforcement learning: An introduction[END_REF]. Our goal is to achieve a stable and balanced traffic scheduling with QoS support for a long time horizon by maximizing the expected cumulative discounted reward. Simulation results demonstrate that ReiLeCS consid-erably improves the system performance.

The paper is organized as follows. Section II overviews the related works. In Section III, we present the system model, then we describe our proposed solution, ReiLeCS, in Section IV. In Section V we provide and discuss our evaluation results. Finally, conclusions are drawn in Section VI.

II. RELATED WORK

As mentioned, the QoS and QoE requirements to properly enjoy interactive multimedia and high quality video streaming are not easy to reach; researchers have hence already focused their attention on this problem.

For instance, in Bujari et al. [START_REF] Bujari | Vegas over access point: Making room for thin client game systems in a wireless home[END_REF], the authors chose to deploy a TCP-Vegas like algorithm on the top of the home gateway in order to make different network flows coexist. The designed algorithm exploits the type of protocol that the different network flows uses to prioritize some packets. In Corbillon et al. [START_REF] Corbillon | Optimal set of 360-degree videos for viewport-adaptive streaming[END_REF] instead, the authors use a different approach based on statistics. Basically, it exploits the peculiarities of 360-degree virtual reality videos to design a statistical model able to reduce the bandwidth consumption and, at the same time, to maintain the video quality. The model performs a prediction of the user's head movements and transmits only the packets related to the portions of the 360 video that is most plausible that will be displayed. To prioritize packets only on the basis of the service's protocol could be a weak strategy in the presence of multiple interactive services running on the HAN. However, even if we are not considering 360 videos, the idea to exploit the specific peculiarities of the considered services is a good starting point to formulate our solution.

Among the various techniques under consideration, one of the most promising regards acting directly on the scheduling algorithm that manages the packet transmission. In [START_REF] Hou | Scheduling of access points for multiple live video streams[END_REF] the authors try to manage multiple video streaming services in the same AP through the use of a scheduling policy called Earliest Positive-Debt Deadline First (EPDF). In this policy, the AP schedules first the packet with the earliest deadline from those whose associated clients possess strictly positive truncated time debts. A similar approach comes from [START_REF] Sandrasegaran | Delayprioritized scheduling for real time traffic in 3GPP LTE system[END_REF] where an algorithm called Delay-Prioritized Scheduling (DPS) is proposed for the management of real time traffic in 3GPP LTE systems. This strategy aims to maximize the throughput while satisfying the QoS requirements of the real time user's applications. To do that, the algorithm uses the instantaneous downlink signal-to-noise ratio values and the packet delay information of each user. These solutions cannot be directly applied to our scenario; yet, we agree that the focusing on the packet scheduling algorithm is an effective approach.

The scheduling algorithms can be enhanced with the aid of RL techniques. The authors of [START_REF] Chinchali | Cellular network traffic scheduling with deep reinforcement learning[END_REF] use RL to design a cellular network scheduler that dynamically adapts to the traffic variation and to different reward functions to optimally schedule Internet of Things traffic. In [START_REF] Shah | A cross-layer QoS-aware communication framework in cognitive radio sensor networks for smart grid applications[END_REF] RL is used to schedule the packets on the basis of specific QoS parameters of diverse smart grid applications that operate in cognitive radio sensor networks. The objective is to mitigate problems such as electromagnetic interference, equipment noise or obstructions. The objective of our research is clearly different; yet, the adopted QoS parameters are well suited for the interactive multimedia and the problem that we address.

The aforementioned approaches are not adequate for a dynamic scenario with multiple cloud-based interactive multimedia services running in the same HAN; nevertheless, the use of RL has been proven as a good decision maker in dynamic environments. This leads us to opt for a scheduling algorithm based on RL to take into account the specific QoS characteristics of the running services. The final objective is to help the AP to manage heterogeneous network flows and to guarantee the related QoS requirements.

III. SYSTEM MODEL

A. System Overview

We consider the HAN scenario where different users take advantage of the cloud computing technology and enjoy multiple multimedia applications (services). The users' devices are connected to the Internet through a local AP. They exploit the wireless HAN, e.g., Wi-Fi, to communicate with the AP which ensures the two way communication between the users' devices and the cloud-server. From one side, it transmits the users' computational requests to the cloud. Then, from the other side, it sends back the cloud responses to the final devices. In this contribution, we focus on the communication from the AP to the final users (downlink) as this has the highest requirements in terms of bandwidth resources. Our aim is to achieve an efficient data packet scheduling on the downlink. In Table I, we overview the most important multimedia applications, their packet inter-arrival times (λ) and their QoS specications attributed in terms of data rate (β), delay (τ ), and packet-error-rate (α). As shown in the table, the considered applications have heterogeneous QoS requirements. Thus, to fulfill our objective, we exploit this aspect and classify the received data packets into multiple classes of services.

In the rest of this section, we present the AP model for the traffic control into multiple classes of services. Then, we describe the mathematical formulation of our problem.

B. Access Point Model for Multiple Classes of Traffic

We consider m the number of interactive multimedia applications that the users enjoy at home. The AP classifies the data flows that arrive from the cloud into m classes according to the QoS requirements of each application. As depicted in Figure 2, the AP uses the set Q = {q 1 , . . . , q m } of m queues to store the different data flows before being scheduled to their final receiver. When a data packet of class i arrives to the AP, it is stored in the queue q i . Then, the AP proceeds to its scheduling and transmission. We characterize the QoS attributes (β i , τ i , α i ) of every class of traffic i by adequately chosen minimum and maximum threshold values

{(β min i , β max i ), (τ min i , τ max i ), (α min i , α max i )}.
The threshold interval of each attribute defines its tolerance in a class i in terms of data rate, latency and packet-error-rate.

To achieve an efficient scheduling of the data packets with the same QoS requirements, the AP schedules the packets stored in the same queue q i , according to the First Come First Served (FCFS) policy. We assume that time is divided into continuous scheduling periods (SP). During every SP, the AP aims at exploiting the available bandwidth and schedules the multiple classes of the data packets according to their QoS requirements. Therefore, at the beginning of every SP, the AP makes multiple consecutive scheduling decisions to transmit or not the first packet q 1 i from the head of every queue q i (i ∈ {1, . . . , m}). Then, as far as the AP senses available bandwidth, it continues to make new decisions. In this context, we denote by n the scheduling decision number n that AP makes during time and by b n the available bandwidth at the time this scheduling decision was taken.

Based on the described model, we present in the following the mathematical formulation of our scheduling problem.

C. Mathematical Formulation

Throughout the different scheduling decisions, the AP has to maximize the utility to send multimedia packets in the HAN subject to the data rate, latency and reliability constraints of the different classes of traffic. Therefore, we formulate the problem as:

Maximize ∞ n=1 m i=1 u n,i (β 1 i , τ 1 i , α 1 i ) (1a) subject to β 1 i ≤ b n , (1b) τ 1 i ≤ τ max i , (1c) α 1 i < α max i , ∀i ∈ {1, . . . , m}. (1d)
The objective function (1a) that the AP wants to maximize will be presented and designed in Section IV-B. Constraint (1b) ensures that during the scheduling decision n, a packet q 1 i is admitted only when its data rate requirement can be satised through the available bandwidth b n while the previously scheduled and transmitted packets continue to be served. Constraint (1c) makes sure that q 1 i can be delivered within the given ow delay. Similarly, constraint (1d) ensures that the packet error rate of q 1 i is under α max i . Formulation (1) presents a sequential decision making problem. Considering the dynamic arrival of packets, the variable bandwidth and the heterogeneous QoS requirements of the different traffic classes, the problem is difficult to solve. Thus, we opt for the use of a reinforcement learning (RL) approach. In essence, using such an approach, the AP learns the optimal policy via successive interactions with the environment and updates its knowledge through the reward feedback.

Our RL-based scheduler is presented in the next section.

IV. OUR REINFORCEMENT LEARNING APPROACH FOR MULTIMEDIA TRAFFIC SCHEDULING Reinforcement Learning (RL) is a set of techniques that allows an agent to take actions and interact with an environment so as to maximize a total reward. RL is always paired with a Markov Decision Process (MDP). Thus, in this paper, we need to first transform our packet scheduling problem into a MDP. Then, we can design our RL approach.

In this section, we first design the MDP and the reward function associated to our problem. Then, we present the learning mechanisms that we use in our solution.

A. Markov Decision Process Model Design

A typical MDP consists of the set (agent, state, action, reward) as shown in Figure 3.

In our approach, we present the MDP as:

• Agent: an agent is an entity that performs the learning task. In our Reinforcement Learning-based Controller and Scheduler (ReiLeCS), the smart home's AP is responsible for scheduling the sets of packets in the different queues and transmitting them over the available bandwidth. • State: a state of the system is the information that the agent can obtain when observing its surrounding environment. Before making the scheduling decision n, we define the system's state s n as: s n is composed of the available bandwidth (b n ) and the set {s n,1 , . . . , s n,m } where s n,i is the state of the queue q i (i ∈ {1, . . . , m}). We design s n,i as:

s n = (b n , s n,1 , s n,2 , . . . , s n,m ) (2)
s n,i = β 1 i , z 1 i τ max i , d n,i α max i (3)
In Formulation (3), β 1 i presents the data rate of q 1 i . If q i is empty then β 1 i equals 0. Instead, z 1 i presents the waiting time of the packet q 1 i in q i . Therefore, the quotient

z 1 i τ max i
measures whether the waiting time of q 1 i is below the maximum allowed delay τ max i . Similarly, the third element evaluates whether the AP exceeds the maximum threshold α max i in terms of packet error rate and d n,i presents the number of packets that have been dropped before making the scheduling decision n.

• Action: an action a n indicates how the agent responds to the observed state s n . In our system, an action a n is the set (a n,1 , . . . , a n,m ) where a n,i presents the AP scheduling decisions, to transmit the packet q 1 i or to keep it waiting till the next decision making.

• Reward: a reward represents an evaluation of the decision made by the agent. In our system, the AP uses the reward to evaluate the long-term performance of its scheduling decision. The design of the reward function is discussed in more details in the next section.

B. Reward Function

After every scheduling decision, the AP assesses the performance of the action a n on the state s n . It uses the reward function u n (a n , s ) that transforms the QoS performance of the multiple scheduled classes of traffic into a utility value. Specifically, u n (a n , s n ) can be expressed as:

u n (a n , s n ) = m i=1 u n,i (β 1 i , τ 1 i , α 1 i ) (4)
It is the sum of u n,i (i ∈ {1, . . . , m}) where u n,i measures the impact of the action a n,i on the state s n,i of the queue q i . We design u n,i as:

u n,i (β 1 i , τ 1 i , α 1 i ) = u send n,i (β 1 i ) -u dropped n,i (α 1 i ) -u stored n,i (τ 1 i ) (5) u send n,i , u dropped n,i and u stored n,i
are expressed in the equations ( 6), ( 7) and ( 8), respectively. More in detail, u send n,i expresses the bandwidth used to transmit packets from the queue q i . Instead, u dropped n,i presents an evaluation of the number of packets that have been dropped. In this study, a packet is considered to be lost if it is not scheduled and transmitted before its expiration time. The third value, u stored n,i , provides an evaluation of the scheduling decision on the delay of the head-of-queue packet q 1 i . It is involved in the utility function u n,i only if the AP decides to not transmit q 1 i , i.e., a n,i = 0. As the AP keeps q 1 i waiting for the following scheduling decisions, both its waiting time and u stored n,i increase.

u sent n,i (β 1 i ) = β 1 i a n,i (6)
u dropped n,i (α 1 i ) = d i (t) α i (7) u stored n,i (τ 1 i ) = z 1 i τ max i (1 -a n,i ) (8)
During a scheduling period, the AP aims at maximizing u n . Its goal is to maximize the bandwidth usage, minimize the waiting time of the different stored data packets in the m queues and minimize the number of dropped data packets. By using RL, the objective is to consider the different decisions made sequentially over time. As a consequence, our goal is to maximize the expected cumulative discounted reward r:

r = E[ ∞ t=0 γ t u n (a n , s n )] (9)
where γ ∈ (0, 1] is a factor discounting future rewards.

C. ReiLeCS

In this section, we present the Reinforcement Learning (RL) solution for our multimedia packet scheduling.

One of the dominant RL approach is the value function approach. For each state or state-action pair the value function, i.e., reward, is calculated. Thus, the agent takes advantages of its training period to discover possible state-action pairs and save their associated value functions in a table. As a consequence, the value function approach has several limitations, especially with models that require a large state space; it is limited to tasks with small numbers of states and actions.

In our case, during the scheduling decisions, a very large number of the encountered states may have never been experienced before (during the training phase). In fact, new users may join the network and use different multimedia services. Also, the available bandwidth can change due to interference or the deployment of new smart home appliances such as smart meters or smart surveillance camera. For these reasons, we use the linear gradient descent to get a compact and generalized representation of an estimated reward function [START_REF] Sutton | Reinforcement learning: An introduction[END_REF]. We express the reward function estimator as follows:

f (s n , θ) = θ T φ(s n ) = θ T ν (10)
In Equation ( 10), ν is the set of features of the state s n . The set of parameters θ presents the key of f (s n , θ) since this function faithfully approximates the reward function u n . Thus, the AP exploits the training phase and updates the weights θ in a way to minimize the error between u n and f . The set θ is updated as:

θ = θ + α(u n -f (s n , θ))ν ( 11
)
where α is the learning rate (α ∈ [0, 1]).

The approximator f (s n , θ) is differentiable. The derivative of f (s n , θ) with respect to θ is ν.

∂ f (s n , θ) ∂θ = ν (12)
In Algorithm 1, we present in details the ReiLeCS training algorithm. During every episode, i.e. a number (M ax) of sequential decisions, the AP discovers new states s n and at the same time updates the weight θ. The objective here is to enable the AP to make the optimal packet scheduling decision. Therefore, the AP needs to not only focuses on the immediate rewards but also the cumulative rewards on the long term. Thus, it has to avoid local optimal rewards and explore new actions that may yield higher rewards in the future. To this end, the AP uses the -Greedy algorithm to balance the exploitation-exploration trade-off (line9 -line13). end for 19: end for

V. PERFORMANCE EVALUATION

In this section, we present some numerical evidences to demonstrate the effectiveness of ReiLeCS. We first consider the scenario of a HAN where different users are enjoying the multimedia applications reported in Table I (m = 3). Then, in order to emulate realistic network traffic, we recorded real traffic measurement from Wireshark, the open-source packet analyzer, to generate the data sets that we have used to train and test our solution. Every data set is characterized by a number of users (from 1 to 5) per multimedia application.

First, we investigate the performance of the training algorithm, i.e., Algorithm 1. When the learning-rate α equals 0.01, we measure the convergence of the mean squared error (mse) between the reward u n and the estimated reward function f . Figure 4 shows the variation of mse according to the episode number. As can be observed, at the beginning of the training process, the achievable mse fluctuates widely. Then, after a sufficient number of episodes, this fluctuation becomes negligible and the mse converges to its optimal value. This is due to the fact that the AP continuously updates the weights θ based on the feedback error it receives (u n -f ). As a result, after a sufficient number of episodes, the AP acquires a good knowledge of the reward u n .

In Figure 5, we focus on the exploitation-exploration tradeoff. Thus, when the available network bandwidth equals 1300 Mbps and varying the values of , we measure the accumulated exploited data-rate. The chart shows that exploring new actions and states that do not result in the best reward can improve future scheduling decisions. For our approach the best usage of the bandwidth is achieved when equals 0.01. Then, as we increase , i.e., explore more random action and states, the performance degrades.

In Figure 6, we depict the variation of the accumulated datarate with the total available bandwidth and we compare the performance of ReiLeCS with the greedy scheduling policy and the random policy. When using the greedy scheduling policy, the AP focuses on maximizing the reward during the current scheduling decision n without considering its impact on future rewards. With the random policy, while the AP senses available bandwidth, it chooses the packet to transmit randomly, without taking into account any of the QoS requirements of the considered multimedia applications. As a result, the chart shows that our approach outperforms the greedy and the random policies. The greedy policy maximizes the instantaneous reward u n and does not explore new actions that may provide better scheduling decisions in the future. The random policy takes the decision even more blindly. ReiLeCS takes advantage of the -greedy algorithm; it explores new states and actions to avoid local optima with the hope of finding a global optimum. Finally, in Figure 7 we evaluate the capacity of ReiLeCS to satisfy the delay requirements of the considered applications. Since cloud gaming possesses the most challenging combination of small inter-arrival time λ i and stringent delay requirements (previously shown in Table I), we focus on the mean queuing time of the cloud gaming packets while varying the data sets (i.e., the number of users enjoying the applications). As reported in the chart, the measured delay increases with the number of users per application since the channel becomes more and more crowded. ReiLeCS and the greedy policy achieves an almost identical waiting time even if the former was able to exploit more bandwidth as shown in Figure 6. They both consider the QoS delay requirement during their scheduling decisions; thereby, they prioritize the scheduling of packet with the highest delay requirements. As foreseeable, for the various data sets, ReiLeCS outperforms the random policy since the latter completely ignores the QoS requirements. We can hence conclude that the estimated reward function f (s n , θ) succeeds in considering the heterogeneous QoS requirements of the applications and prioritizing the packet flows with with the most stringent requirements.

VI. CONCLUSION

In this paper, we proposed ReiLeCS, the Reinforcement Learning-based Controller and Scheduler for interactive multimedia traffic in HANs. In the context of cloud based multimedia content delivery, ReiLeCS enables a smart home's AP to schedule the cloud-generated multimedia packets according to their QoS requirements. To this aim, before being scheduled, the data packets are classified into multiple classes of services. Then, RL is employed to allow the AP to take proper scheduling decisions in order to maximize a reward function we designed to consider the QoS requirements. ReiLeCS aims at maximizing the expected cumulative reward. It exploits the -greedy algorithm to avoid local optima and improve future scheduling decisions. We evaluated ReiLeCS using real multimedia traffic conditions. The simulation results show that ReiLeCS is effectively trained to optimize multimedia traffic scheduling. Moreover, it demonstrates its capacity to consider the variant QoS requirements and to prioritize the scheduling of traffic with the most stringent QoS requirements.

Fig. 1 .

 1 Fig. 1. Architecture for remote multimedia run.

Fig. 2 .

 2 Fig. 2. Queuing model for multimedia traffic in the AP.

Fig. 3 .

 3 Fig. 3. MDP model.

Algorithm 1 θ

 1 ReiLeCS training algorithm. 1: Input: learning rate α, exploration probability 2: Initialization: Randomly initialize θ 3: for each episode do for n ∈ [1, . . . , M ax] do 6: while the bandwidth is available do 7: Observe the state s n 8:Choose a random probability p ( -greedy) = θ + α(u n -f (s n , θ))ν

Fig. 4 .Fig. 5 .

 45 Fig. 4. Convergence of the mean squared error of ReiLeCS.

Fig. 6 .

 6 Fig. 6. Bandwidth usage performance.

Fig. 7 .

 7 Fig. 7. Queuing time performance.

TABLE I MULTIMEDIA

 I APPLICATIONS AND THEIR QOS SPECIFICATIONS.

	Input flow	Traffic classifier	Service queues Scheduler
			Service	β (Mbps)	τ (ms)	α (%)	λ (ms)
			Cloud Gaming (1080p)	10 to 15 (DWN) 0.5 to 1 (UP)	≤ 160	1	0.92
			4K Video Streaming	20 to 25 (DWN)	Preload is possible	1	0.76
			Online Gaming	1.5 to 3 (DWN) 0.5 to 1 (UP)	≤ 160	5	17.06


Hamza Ben-Ammar
email: hamza.ben_ammar@univ-lr.fr

Yacine Ghamri-Doudane

An ICN-based Approach for Service Caching in Edge/Fog Environments

Keywords: Service Caching, Edge Computing, Fog Computing, Information-Centric Networking

Edge and Fog computing represent today a realistic alternative to traditional cloud data centers in order to support data-intensive and time-sensitive applications, such as those laying under the Internet of Things (IoT) umbrella. One of the main problems associated to this is the service placement problem, or how to efficiently manage the available computing and storage resources while deploying the plethora of application services, to be made available to clients, at the network edge/fog? Due to the similarities shared by this problem and the traditional data caching problem, multiple researches started looking at the adaptation of the Information-Centric Networking (ICN) paradigm to answer the aforementioned question, giving birth to what we depict as an ICN-Edge/Fog architecture. Leveraging such an architecture, we propose in this paper a novel service caching strategy, called 3Q, that is the first to argue on the caching of both, the service instances, consuming computing resources, as well as their associated source codes, consuming storage resources. Being characterized by its low-complexity and its low-overhead, 3Q proves to achieve near-optimal results in terms of cached services hits, latency and cloud usage.

I. INTRODUCTION

Edge Computing (EC) and Fog Computing (FC) [START_REF] Yousefpour | All one needs to know about fog computing and related edge computing paradigms: A complete survey[END_REF] are promising paradigms aiming at overwhelming some of the limitations faced by traditional cloud data centers, especially those related to the support of time-sensitive applications and eco-responsibility (as cloud data centers have an important energy footprint). However, EC and FC solutions face stringent challenges in terms of resources allocation for the support of heterogeneous applications at the network edge/fog. Indeed, they are composed of multiple distributed nodes that are characterized by their very limited computing and storage resources, in comparison to those available in centralized (and geographically localized) cloud data centers. A relevant issue that needs to be addressed is the service placement problem (SPP), which relates to the process of determining where to place different services, namely their instances (i.e. computing resource consumption) as well as their associated source codes (i.e. storage resource consumption). Such a service placement needs to answer the question of how to distribute workloads of a placed application on multiple locations. In this paper, one of our arguments is that such a workload is not only to be considered in terms of computing resources, as mostly considered in the literature, but also in terms of storage resources as well (i.e. for source codes storage).

Several existing works have addressed the service placement problem in edge and fog environments and more generally in network architectures having distributed and limited computational and storage resources [START_REF] Salaht | An overview of service placement problem in fog and edge computing[END_REF]. They can be classified following multiple criteria: single or multi-objective optimization, centralized or distributed solution, etc. More precisely, SPP has been studied from different angles, that led to various proposals, such as integer programming [START_REF] Tinini | Optimal placement of virtualized bbu processing in hybrid cloud-fog ran over twdm-pon[END_REF], meta-heuristics [START_REF] Skarlat | Optimized iot service placement in the fog[END_REF] or constrained optimization [START_REF] Salaht | Service placement in fog computing using constraint programming[END_REF]. The problem of how to optimize the placement of services in the edge/fog computing environment shares few similarities with the well-investigated problem of cache management [START_REF] Ben-Ammar | A versatile markov chain model for the performance analysis of CCN caching systems[END_REF], [START_REF] Ben-Ammar | A GRASP-based approach for dynamic cache resources placement in future networks[END_REF], which started with computer architecture and continued later with web caching to then regain new interests with the arrival of the ICN paradigm [START_REF] Xylomenos | A survey of informationcentric networking research[END_REF]. These similarities led researchers to wisely think about combining both approaches, including the design of specific and efficient network architectures allowing to combine both, such as the one in [START_REF] Mastorakis | ICedge: When edge computing meets information-centric networking[END_REF], where the main idea is to handle the "low-level" network communication operations on behalf of applications. This includes some basic tasks such as enabling the users requests to invoke applications hosted at edge and fog nodes, delivering the applications from selected nodes in a timely manner and allowing the reuse of computing results by other similar tasks.

In this paper, our objective is to revisit the service placement problem while an ICN-based Edge/Fog architecture is deployed. More precisely, we argue that a caching strategy in such a context must rely on two main features: (i) handling the caching of both, the service instances as well as their source codes (or software images), and (ii) keeping the overhead as low as possible by adopting a strategy that does not require any explicit cooperation among nodes. So, we propose in this paper 3Q, a low-complexity caching strategy that uses three queues at each edge/fog node, in order to manage which services to admit in the service instances cache and which one to admit to the source code cache. Extensive evaluations show that such a simple caching strategy proves to have cached services hits, latency and cloud usage performances that are close to the ones obtained by an optimal (oracle) strategy.

The remainder of the paper is organized as follows. Section II reviews the main related work. This is followed in Section III by our proposal for Service Placement in an ICNbased Edge/Fog architecture. In Section IV, we analyze the performance of our proposal. Finally, Section V concludes this paper and presents some future research directions.

II. RELATED WORK

Several papers have presented different solutions to the SPP problem. In [START_REF] Skarlat | Optimized iot service placement in the fog[END_REF], the authors propose a genetic algorithm to maximize the instances of deployed services in the fog nodes as an alternative to the cloud. The authors in [START_REF] Salaht | Service placement in fog computing using constraint programming[END_REF] handled the SPP problem in Fog Computing by providing a generic and evolving constraint programming model. In [START_REF] Tinini | Optimal placement of virtualized bbu processing in hybrid cloud-fog ran over twdm-pon[END_REF], a framework based on Network Functions Virtualization (NFV) is proposed to deploy in the fog nodes, services provided by the cloud. In their work, the deployment problem is formulated as an Integer-Linear Programming (ILP) problem. These proposals are examples of interesting solutions to the SPP problem. However, they all significantly increase the network overhead, as they require centralized information to be collected as well as a collaboration among network nodes.

To the best of our knowledge, there are only few studies that dealt with the Service Placement Problem in edge/fog environments that are built following the ICN principles and proposing online and distributed caching and cahe replacement strategies that are characterized by their low overhead. Hou et al. [START_REF] Hou | Asymptotically optimal algorithm for online reconfiguration of edge-clouds[END_REF] tackled in their paper the service provisioning problem in edge-clouds from a theoretical point of view. They propose an online algorithm for the dynamic reconfiguration of edgeclouds where their limited capacity, operational costs and the unknown arrival patterns of requests are considered. Their solution, named retrospective download with least recently used, is an LRU-based replacement strategy with low complexity where the history of previously requested services is used to decide which service to replace in the edge-cloud when it reaches its maximum capacity. However, the edge nodes in their system model are not geographically distributed as they are considered as forming a single entity. In [START_REF] Ascigil | On uncoordinated service placement in edge-clouds[END_REF], the authors argue that the SPP is similar to the resource storage allocation problem and studied it as such. Using the principles of cache management and by considering delay-sensitive services, they propose an uncoordinated resource allocation where the edgecloud nodes are used as on-path opportunistic resources. Their solution is based on the combination of well-known scheduling strategies and cache replacement strategies. Nevertheless, they suppose in their work that the source code necessary to instantiate the different proposed services/applications are available in advance in every edge/fog node of the network.

III. TOWARDS AN ICN-BASED SERVICE INSTANCES AND SOURCE CODES CACHING STRATEGY

A. System model

We consider in this work an ICN-based Edge/Fog Computing environment, similar to the one presented in [START_REF] Mastorakis | ICedge: When edge computing meets information-centric networking[END_REF], and we use one of the most popular concrete implementations of ICN, which is the Named-Data Networking [START_REF] Jacobson | Networking named content[END_REF], also known as Content-Centric Networking or CCN.

Edge and Fog computing are natively service-centric architectures where clients, asking for specific services from the edge of the network, can get it from any edge/fog node offering the service in the network. The ICN paradigm matches perfectly the objective and the mechanisms of EC and FC through the use at the network layer of application-defined naming. Let's recall that in CCN, the content's name (services in our case) is the only identifier of a specific data (respectively, a service in our case). To request and retrieve data, two types of packets are commonly used [START_REF] Jacobson | Networking named content[END_REF]: Interest Packets and Data Packets. Users ask for specific data by sending Interest packets, which are forwarded towards the data sources using the Forwarding Information Base (FIB). A record of the forwarded Interests is kept in the Pending Interest Table (PIT) in order to keep track of the Interests waiting for a data packet. When a node receives multiple requests for the same data, the Interest packets are aggregated in one entry in the PIT and only the first one is routed. Once the request is found, it is automatically routed back to the clients on the reverse path. All the nodes along this path can store a copy of the requested data to answer future demands. In our case, clients requests regards the available running services in the network.

Let G = (V, E) be the graph representing an ICN-Edge/Fog network, 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 has computation capabilities (CPU and RAM) to run the services and storage capacity to host their source codes allowing to instantiate pre-installed services as an answer to client requests. Unlike ICN, where each node has only one cache to save in the network copies of the flowing data packets, every node in our work will have two separate caches: one to host the running services available to the users and the other is used to store the source codes. Let S = {s 1 , . . . , s R } be the set of services available to the users. We assume that all the accessible applications in the system along with their source codes have an identical size. The node capacity is then expressed in terms of the number of maximum running services and the number of application source codes (or software images, in case where containers are used) that can be stored. The pattern of the interests sent by the users is depicted by the Independent Reference Model (IRM) [START_REF] Flajolet | Birthday paradox, coupon collectors, caching algorithms and self-organizing search[END_REF] where these are generated in a independent and identical distributed sequence of requests. More precisely, the probability p r to request an item s r from the catalog S of R services follows a popularity law in which the items composing the catalog of services are ranked decreasingly according to their popularity from 1 to R. All the available services are hosted permanently at one or more servers within the network. In the rest of the paper and for the sake of readability, we will use the term service/application interchangeably as well as the terms rank/popularity and source code/image.

B. Service caching and management

In this work, our aim is to propose an online strategy with low-complexity using ICN's on-path caching feature to decide how the services and their images are cached and managed within the network. The intended objectives are to reduce the cloud load, minimize the average distance and delay for the users to get their requested applications and improve the efficiency of the edge/fog nodes resources. We assume that all the services available for the users and their source codes are initially only hosted in the cloud. In order for any node wanting to serve a specific application upon the reception of an interest for it, it has first to download from the cloud the corresponding source code in order to be able to instantiate the service afterword.

Whenever a client sends a request asking for a specific service, the first node that receives it will check whether it has the application available in its cache. If there is a hit, then this node will provide the requested service. In case of a miss, we suppose that even if a node has an image of the demanded application in its cache, launching the service takes more time than getting it from an another node or the cloud. The user's demand will then be forwarded to the next nodes toward the cloud checking for the presence of the application. Once it is found, it is sent in the reverse path towards the end user and following the adopted caching policy, the service's image is cached or not at each node that receives it in order to create an instance of the service. Once one of the node's caches is full and a new caching decision is to be enforced, then one item has to be selected for eviction to make room for the new element to be cached.

The caching scheme has to manage basically two aspects of the services cache and the source code store: the cache replacement policy and the caching decision. The first one is the algorithm responsible for managing the cache. When the cache is full, an item is chosen by the algorithm to be discarded. To achieve this, one can cite the following existing algorithms: First In First Out (FIFO), Least Frequently Used (LFU), Least Recently Used (LRU), to name a few. The second one determines which object should be cached and at which node. In other words, whenever a service requested by an end user is travelling towards its destination node, an intermediate node has to choose whether to ask for its source code in order to launch the application locally. This depends on the implemented caching strategy. Among the examples of such strategies that are commonly used in ICN, we can cite the Leave Copy Everywhere (LCE) [START_REF] Laoutaris | The LCD interconnection of LRU caches and its analysis[END_REF], the Leave Copy Down (LCD) [START_REF] Laoutaris | The LCD interconnection of LRU caches and its analysis[END_REF] and the Two Queue (2Q) [START_REF] Johnson | 2Q: A low overhead high performance buffer management replacement algorithm[END_REF], for instance. Schemes like these three examples have the specificity of being of low-complexity and of low-induced network overhead as there is no information exchange or cooperation between the different nodes, which is our aim in this work.

C. LCE and LCD

In multi-cache systems in general and more specifically in ICN, the default caching strategy that can be used is the Leave Copy Everywhere (LCE) where every data packet received by each node along the downloading path is systematically cached. It is a very basic mechanism that does not imply any overhead or communication cost. Such schemes can be used in performance evaluation campaigns to have the lower bound values in terms of performance. Another interesting technique having a low overhead cost but with a better efficiency is the Leave Copy Down (LCD). Instead of saving a copy of the data packet in all intermediates node caches as in LCE, LCD consists on performing the caching operation only in the immediate downstream node on the path from the hit location. This mechanism creates a kind of filtering system where contents gradually move towards the users with the popular ones to be the first to be cached as close as possible to clients.

D. 2Q algorithm

On the basis of the algorithm named LRU-K presented in [START_REF] O'neil | The LRU-K page replacement algorithm for database disk buffering[END_REF], Johnson et al. proposed the Two Queue scheme (2Q). LRU-K is basically an enhancement of the classical LRU algorithm while keeping track of the timing of the K last occurrences of each element entering the cache, thus allowing to have an estimation of their reference inter-arrival times. The item whose K th most recent access is furthest in the past will then be evicted when the cache is full (LRU-1 is equivalent to the classical LRU). It is shown that the most important gain of the LRU-K method is achieved when K = 2 (LRU-2) [START_REF] O'neil | The LRU-K page replacement algorithm for database disk buffering[END_REF], but with the cost of having a relatively high complexity, as each item access requires log(N ) operations to manipulate a priority queue (N being the cache size). 2Q is similar and performs as well as the LRU-2 algorithm but unlike the latter, it has a constant complexity time overhead. Instead of cleaning cold elements from the main buffer like LRU-2, 2Q admits to the cache only the ones that are more likely to be requested in the near future. When a request is received by a cache using 2Q, the requested object's hash is first placed in a virtual cache (called A1), which is managed as a FIFO queue. If an item is requested during its A1 residency, it is then promoted to the main cache (called Am). The authors, then, propose another version of 2Q in which the A1 queue is partitioned into A1in and A1out. The A1in queue along with Am form the physical cache and A1out is a virtual cache, which will contain only items hashes. The most recent first accesses are stored in A1in, which is managed as a FIFO queue. When objects are evicted from A1in, they are remembered in A1out. Upon arrival of a request and if it is present in the A1out queue, then it is cached in Am. The item to be discarded in 2Q is chosen either from A1in or Am. One should also note that the sizes of the different queues (A1in, A1out and Am) are sensitive to the requests patterns and should be tuned carefully.

E. 3Q: a 2Q-inspired algorithm for service caching

In this paper we propose a caching scheme that we call 3Q, which is similar to the first version of 2Q but where the virtual buffer and the main store are both managed using LRU. The virtual cache's role is to allow only popular services to be cached by detecting the services that are requested more than once within a short period of time. The 2Q algorithm was initially proposed in the context of page replacement algorithms for computer operating systems and it was then shown to be efficient in ICN [START_REF] Ben-Ammar | On the performance analysis of distributed caching systems using a customizable markov chain model[END_REF]. We believe that adopting a 2Q like algorithm in the context of services placement in an ICN-Edge/Fog architecture can also lead to very good performance. As it was explained earlier, each node in the network has to have the service's source code in order to instantiate it and be able to provide it to users. So, in addition to the virtual cache (VC) and the main cache (MC) that hosts the services, there is an auxiliary cache (AC) for the source codes, thus having three queue in total for each node (see Figure 1). Once a node receives the request issued from a client looking for a specific service, it checks if it has a copy running in the MC. If there is a hit, then it provides the application to the user. In case of a miss, it looks for the presence of its source code in the AC. If a copy is found, it instantiates the corresponding service, but the interest is also sent upward to other nodes since we assume that loading an application from its source code or from its image takes more time than getting it from another node or even from the cloud. If not, it is the turn of the VC to be checked. If there is a hit and while the node forwards the interest to the other nodes toward the cloud, it also asks for the service's source code (which can be received from one of the upward nodes or the cloud) in order to save it in the AC and then instantiate a copy of it in the MC.

In case of a miss, a hash value of the requested application is saved in the VC waiting to be requested again while being present in this buffer and thus to trigger its caching. Here again, the interest is forwarded upward.

F. Optimal caching strategy (OPT)

When designing a caching scheme, the aim is generally to maximize the overall hit ratio in order to reduce the cloud load and maximize the cache hits at the nodes close to users, which reduces the average latency to get a requested object. This is achieved by creating a mechanism that tries to detect and cache the most popular and requested data packets as near as possible to end users and to have the lowest possible redundancy between neighboring nodes. In this case, an "optimal" strategy (that we call OPT) works as follow: if we suppose that the services popularities are known in advance and that all the caches of services of the network's nodes have the same size C, then the most C popular services (s 1 , . . . , s C ) are exclusively cached at the nodes located at a one-hop distance from the users, then the second C popular items (s C+1 , . . . , s 2C ) are cached at a 2-hop distance, etc. Such strategy gives the upper bound in terms of performance.

IV. RESULTS

A. Evaluation settings

We evaluate in this section the performance of 3Q and compare it to the following caching strategies: LCE, LCD and OPT. As for the cache replacement policy, we will focus in this work on LRU to manage each node's caches. We could have considered other cache management algorithms like FIFO, Random or LFU but LRU is known to perform much better than FIFO and Random. As for LFU, it requires a more complex replacement process and do not adapt very well in time with the popularity variations of the elements to be cached.

The different evaluations are conducted using ccnSim [START_REF] Chiocchetti | ccnSim: An highly scalable ccn simulator[END_REF], a discrete-event and chunk-level simulator of CCN (ccnSim was modified in order to handle the management of services instead of contents). We use during the simulations a complete binary tree network topology containing 31 nodes (with a total of five levels). The root node is attached to the back-end cloud system, which hosts all the services available to the users and their source codes. The clients, attached to the leaves nodes of the network, generate their requests for the different services according to a Poisson process with a rate of 1 request/sec (this rate corresponds to each aggregation of users attached to each leaf node). We consider in the topology a uniform latency of 25 ms between each two nodes except for the interconnection between the root and its child nodes where the latency is set to 100 ms (to represent a higher latency to access the back-end cloud system compared to the hop-to-hop node latency). For our simulations, we consider a catalog of services containing 10000 services whose popularity distribution follows the Zipf's law, where each service has a probability to be requested that is equal to: p r = r -α / R i=1 i -α , α being the skew of the distribution. The Zipf's law has been used in many fields, including the modeling of the services popularity distribution in Cloud and Edge/Fog Computing [START_REF] Li | Service popularity-based smart resources partitioning for fog computing-enabled industrial internet of things[END_REF]. We suppose that the network's nodes have service cache sizes following the uniform distribution, with values varying from 50 to 250, and source code caches having its double in size, as storage capacity is generally greater than computation capacity according to price trends. The size of the virtual cache in 3Q is also a parameter to be tuned, which was set to 10% of the services cache size (we obtained the best results using this value). We tested different values of the Zipf's law parameter α (0.8, 1.0 and 1.2). The numerical results depicted in Figure 2 and Figure 3 represent the mean values taken over 30 simulation runs (using a confidence interval of 95%) and in which 2 × 10 6 requests from users are sent in the network after the system reaches stability (i.e. after all service caches become full).

B. Results and analysis

We display in Figure 2 the average service cache hit for the entire network (2(a), 2(b) and 2(c)) as well as for the edge nodes only (2(d), 2(e), and 2(f)) to highlight the efficiency of cache resource usage. We can see from the results how using low cost strategies (LCD and 3Q), i.e. strategies that do not require any sort of cooperation and information exchange between nodes, can be effective as the cache hit performance is greatly improved compared to LCE, which is the default caching technique. We denote, however, a superiority of 3Q over LCD. This is even more clear when we focus on the cache hit performance of the edge nodes only (2(d), 2(e), and 2(f)) as the performance of 3Q, and at slightly lower extent LCD, are very close to OPT. This also illustrates the difficulty of taking an efficient advantage of the nodes resources located at higher levels of the network topology, resulting in lower performance compared to edge nodes, which have the chance to serve more popular services as they are the first to receive the clients requests. Furthermore, one should note that the performances are heavily impacted by the service popularity distribution and the cache size. Lower value of α means less difference in the service popularity, and vice-versa, which makes it more difficult to have multiple hits for the same item in the cache (and vice-versa). As for the cache size, a lower value means a higher probability of discarding from the cache running services that could be requested in the near future. the solicitation of the back-end cloud is decreased due to the caching process at the edge/fog nodes. The results shows how 3Q outperforms the other caching strategies achieving performances close to those of OPT. For example, 3Q achieves 96% of the OPT performance in terms of latency reduction ratio when α and the cache size are set respectively to 1.2 and 250. These results indicate clearly that 3Q is more successful compared to LCE and LCD in serving most popular services, especially in the lower levels of the network topology.

Overall, we can conclude from these results that an uncoordinated caching strategy, like 3Q, can achieve near optimal performance as defined by OPT.

V. CONCLUSION AND FUTURE WORK

We studied in this paper the service placement problem in the context of Edge/Fog computing environments. We started first by highlighting how the ICN paradigm can be used to tackle this problem from a new perspective. By leveraging the in-network caching feature of ICN, the services along with their source codes (or software images) can be managed at the Edge and Fog nodes using a specifically designed caching strategy. To keep the network overhead as low as possible, we focused on caching schemes that does not require explicit cooperation between nodes. To do so, we proposed in this paper a service caching strategy called 3Q, an extension of a caching algorithm called 2Q that was shown to be efficient for data caching in ICN. 3Q works in a distributed manner where each node within the network is autonomous, inducing only a marginal control overhead and cost. The conducted simulations showed the closeness of our proposal to an optimal solution, i.e. a solution knowing the popularity distribution of the services in advance, in terms of cached services hits, latency and cloud usage. As per our future works, we aim to explicitly incorporate the QoS requirements (e.g. deadline satisfaction) in the service caching process. We also aim at developing analytical tools in order to quantify the cost/efficiency ratio when studying and using caching strategies and their network overhead impact.

Figure 2 .

 2 Figure 2. Average cache services hit in all the network and at the leaves nodes.

Figure 3

 3 Figure 3 depicts the network performance in terms of latency reduction ratio (3(a) and 3(b)), cloud services load reduction ratio (3(c) and 3(d)) and cloud source code load reduction ratio (3(e) and 3(f)). These are obtained while considering various values of α and the cache size. The cloud load reduction metric represents how much (in percentage)the solicitation of the back-end cloud is decreased due to the caching process at the edge/fog nodes. The results shows how 3Q outperforms the other caching strategies achieving performances close to those of OPT. For example, 3Q achieves 96% of the OPT performance in terms of latency reduction ratio when α and the cache size are set respectively to 1.2 and 250. These results indicate clearly that 3Q is more successful compared to LCE and LCD in serving most popular services, especially in the lower levels of the network topology.

  size (%)Cloud images load reduction (%)(f) α = 1.2

Figure 3 .

 3 Figure 3. Network performance comparison in terms of latency and cloud load.