Fei Shen

Kenza Hamidouche
email: kenza.hamidouche@centralesupelec.fr

Ejder Baştug

Mérouane Debbah
email: merouane.debbah@huawei.com

A Stackelberg Game for Incentive Proactive Caching Mechanisms in Wireless Networks

In this paper, an incentive proactive cache mechanism in cache-enabled small cell networks (SCNs) is proposed, in order to motivate the content providers (CPs) to participate in the caching procedure. A network composed of a single mobile network operator (MNO) and multiple CPs is considered. The MNO aims to define the price it charges the CPs to maximize its revenue while the CPs compete to determine the number of files they cache at the MNO's small base stations (SBSs) to improve the quality of service (QoS) of their users. This problem is formulated as a Stackelberg game where a single MNO is considered as the leader and the multiple CPs willing to cache files are the followers. The followers game is modeled as a noncooperative game and both the existence and uniqueness of a Nash equilibrium (NE) are proved. The closed-form expression of the NE which corresponds to the amount of storage each CP requests from the MNO is derived. An optimization problem is formulated at the MNO side to determine the optimal price that the MNO should charge the CPs. Simulation results show that at the equilibrium, the MNO and CPs can all achieve a utility that is up to 50% higher than the cases in which the prices and storage quantities are requested arbitrarily.

I. INTRODUCTION

The ever increasing number of mobile phones and connected devices is expected to contribute to an 800% increase in mobile data traffic in the five upcoming years [START_REF]Cisco visual networking index: Global mobile data traffic forecast update[END_REF]. Bandwidth intensive applications such as video-on-demand traffic will represent more than 70% of the global generated data requests [START_REF]Cisco visual networking index: Global mobile data traffic forecast update[END_REF]. To support this growing traffic and offload macro base stations, short range small base stations (SBSs) are deployed closer to the end-users. However, these SBSs are connected to a core network via capacity-limited backhaul links which makes it difficult to meet users' requirements in terms of quality-ofservice (QoS), especially during peak hours. To deal with this problem, distributed caching at the network edge has recently been proposed as a promising solution [START_REF] Baştug | Living on the Edge: The role of proactive caching in 5G wireless networks[END_REF].

The idea of distributed caching consists in equipping the SBSs with storage units in which files are cached according to a placement policy. Thus, the SBSs can serve most of the requests locally without using the backhaul. However, for a successful deployment of proactive edge caching, the mobile network operators (MNOs) require cooperation of the content providers (CPs) to be able to cache their content at the SBSs [START_REF] Paschos | Wireless caching: Technical misconceptions and business barriers[END_REF]. To this end, incentive mechanisms must be developed by This research has been supported by the ERC Starting Grant 305123 MORE (Advanced Mathematical Tools for Complex Network Engineering), the U.S. NSF Grant CCF-1409228, and the projects 4GinVitro and BESTCOM.

the operators to incite CPs to share and cache their content. The MNO offers to the CPs the caching service that allows the CPs' users to improve their QoS and in return the CPs pay a price defined by the MNO depending on the amount of storage space requested by each CP.

Recently, several caching works have appeared from different aspects, such as optimal caching policies in layered video delivery [START_REF] Poularakis | Caching and operator cooperation policies for layered video content delivery[END_REF], device-to-device (D2D) networks [START_REF] Gregori | Wireless content caching for small cell and D2D networks[END_REF], hieararchical caching [START_REF] Ghoreishi | Provisioning cost-effective mobile video caching[END_REF], multi-cell scenario with limitedbackhaul [START_REF] Peng | Cache size allocation in backhaul limited wireless networks[END_REF] and so on (see [START_REF] Paschos | Wireless caching: Technical misconceptions and business barriers[END_REF] for detailed discussions). More relevantly, there exist some works focusing on economic aspect of caching in wireless D2D networks. In such networks, the operators define pricing scheme to motivate users to proactively download the most popular files and cache them in their devices to serve other users' requests. In [START_REF] Alotaibi | Towards a marketplace for mobile content: Dynamic pricing and proactive caching[END_REF], the authors proposed a smart pricing scheme to maximize the benefit of the operator and minimize the charged price to the users. Via D2D communications, users can trade their cached files to minimize their expected payments. On the other hand, the operator defines a dynamic pricing model that differentiates off-peak and peak time periods to maximize its own benefit. The authors in [START_REF] Chen | Caching Incentive Design in Wireless D2D Networks: A Stackelberg Game Approach[END_REF] formulated the cache incentive problem as a Stackelberg game in which the SBSs are the leaders and the users are the followers. In this model, the SBSs start by anticipating users' reactions and determine the optimal price that maximizes their offloaded traffic from to the users devices. Given a defined reward by the SBSs, users can then decide whether to help the SBSs by caching the files and serving other users or not.

Despite being interesting, all these works focused on cache incentive mechanisms in D2D wireless networks and ignored the role of CPs in the caching process. The main contribution of this work is to propose a new cache incentive mechanism between an MNO and multiple CPs. We formulate the cache incentive problem as a Stackleberg game in which the MNO is a leader and the CPs are the followers. The MNO predicts the requests profile of the CPs and define the price that maximizes its revenue. On the other hand, due to limited storage capacity of the SBSs, CPs cannot cache all their files, thus, the CPs compete to maximize the amount of storage space they request given the fixed price by the MNO. The competition between the CPs is formulated as a non-cooperative sub-game in which each CP aims to maximize the satisfaction of its users in terms of transmission rate. Both the existence and uniqueness of the Nash equilibrium (NE) are proved. The NE represents a state in which none of the CPs can improve its benefit by requesting a different amount of storage space given the requested amount by the other CPs fixed. We provide closed-form expressions of the storage amount the CPs must at the NE. Then, given the request profiles of the CPs, an optimization is formulated at the MNO to the price that should be charged to the CPs to maximize the MNO's revenue. Simulation results show that the MNO can get a revenue that is up to 50% higher compared to the case in which the prices are selected arbitrarily. at the equilibrium, we show that the CPs can achieve a utility that is 20% to 50% higher compared to the two cases in which half and the double of the storage space at the NE are requested by the CPs, respectively.

The rest of the paper is organized as follows. In Section II, we define the system and the caching models. The Stackelberg game is formulated in Section III, and the analysis is conducted in Section IV. The numerical results are presented in Section V. We finally draw conclusions in Section VI.

II. PRELIMINARIES A. System Model

We consider an heterogeneous network (HetNet) which consists of N cache-enabled SBSs and is controlled by one MNO. There are M CPs that are willing to cache their files in the HetNet in order to enhance the QoS of their users. Let N = {1, 2, . . . , N } denote the set of cacheenabled SBSs, each of which has a limited capacity s n , and M = {1, 2, . . . , M } denote the set of CPs. Each CP requests from the MNO to cache its q m most popular files. The N SBSs are connected to the MNO with a backhaul such as DSL, optical fibers or wireless backhaul. All the user equipments (UEs) communicate with the corresponding SBSs. If the desired files from the UEs are not cached in the SBSs, they are served by the MNO via the capacity-limited backhaul links. The system model is depicted in Fig. 1.

Each CP m has a local content catalog F m with F m files. The global files catalog is denoted F = F m , and all the files are assumed to have the same unit size. We assume that each file f i is cached by the MNO p fi times at the SBSs based on the popularity of the file. The goal of each CP is to cache its most popular files locally at the SBSs so that the users experience an improved data transmission rate. However, the The total caching copies of requested files of all CPs storage capacity of the SBSs is limited and not all the files can be cached with sufficient copies. The notations used in the rest of this paper is summarized in Table I.

B. Cache Incentive Model

We formulate the cache incentive problem as a Stackelberg game in which a non-cooperative game is involved as a subgame. As shown in Fig. 1, the Stackelberg game is played between the MNO and the M CPs. On the one hand, all the CPs wish to cache as many as possible files at the MNO's HetNet such that the QoS of their users (for example the delay) is improved. On the other hand, there exists a cost for caching. Therefore, the incentive proactive caching mechanism is controlled by a charge price determined by the MNO to optimize its revenue in the proposed Stackelberg game. The sequential game (Stackelberg) leads to a more competitive equilibrium than the simultaneous move game: The MNO plays as the leader providing the caching price π to all the CPs, while the CPs play as the followers reacting with their optimal number of files they want to cache based on the given price. Both the MNO and the CPs are rational and optimize their own utilities denoted as u o and u m , respectively. The strategy of the leader MNO is the caching price π and the strategies of the followers CPs are their the number of files they want to cache q m (π). It should be noted that the price defined by the MNO depends on the used caching policy and the storage capacity of all the SBSs.

Due to the limited caching capacity, the M CPs compete for the possible caching quantities. Therefore, a non-cooperative game is played as a sub-game among the M CPs. We assume that the file access probability of each file is perfectly known at all the entities (i.e., CPs and MNO). The strategies of the CPs are the quantity of their caching requests. Under the perfect knowledge of the access probability of each caching file, the CPs will choose to cache the first q * m files ordered with the highest access probability, i.e., popularity.

III. STACKELBERG GAME FORMULATION

In this section, we provide the utilities of the MNO and the CPs, respectively. The proposed Stackelberg game is played as follows. The leader plays first by providing its optimal strategy to all the followers after predicting the strategies of the followers. Then, the followers reply with their best strategies given the strategy of the leader. The result of the Stackelberg game is that both the leader and the followers optimize their utilities. The Stackelberg equilibrium is exactly the point that the leader wishes. The basic idea of the utilities for both the MNO and the CP can be formulated as a general function, such as U tility = Revenue -Cost. In the following, we will analyse the utilities of the MNO and the CPs, respectively.

A. Utility of the MNO

For the MNO, the main cost is the caching storage cost denoted as C o . This caching storage cost is a function of the caching capacity of all the SBSs and the number of times each file is cached. Therefore, the cost of caching all CPs files C o for the MNO can be defined as the following barrier function:

C o = 1 S-d(Q M ) if 0 < d(QM) ≤ S ∞ otherwise, (1)
where d(Q M ) is the amount of all the cached files by the MNO and is given by:

d(Q M ) = M m=1 fi∈Qm p fi , (2)
where p fi is the number of copies of file f i that are cached at the SBSs and defined by the MNO depending on the popularity of file f i . The caching capacity of the MNO is given by:

S = N n=1 s n . (3)
The revenue of the MNO in the caching problem is the total charge from all the CPs for caching their files. The price of caching one file is denoted by π and the number of files that is requested by a CP m to be cached is q m . Thus, the total revenue of the MNO can be given by

R o = π M m=1 q m (π). (4)
Now we obtain the utility function of the MNO in our proposed Stackelberg game as a function of the quantity of caching request from all the CPs, q = [q 1 , . . . , q M ].

u o (q(π)) = R o (q(π)) -C o (q(π)), (5)
where R o and C o are defined in ( 1) and ( 4), respectively.

B. Utility of the CPs

Given that the MNO fixes a price π for a storage unit, all the CPs reply with their quantity of caching request by optimizing their own utilities. We assume that each CP is independent of the others and makes its best strategy only based on its local information.

The cost of CPs for the caching requests are the charge paid to the MNO for their desired quantity of caching files. For each CP m, the cost C m is defined as

C m = πq m (π), (6)
where q m (π) is a function of the provided charge price π. C m is an increasing function of the caching quantity q m (π).

In fact, the CPs such as Facebook and Youtube are concerned about the satisfaction of their users. This user satisfaction, which can be the delay of downloading a file or the data throughput, is an increasing function of the caching request quantity q m of CP m and a decreasing function of the caching request quantities q -m of others because of the limited caching capacity. q -m is defined as the caching request quantities of all the other CPs except CP m, i.e., q -m = [q 1 , . . . , q m-1 , q m+1 , . . . , q M ].

The revenue of CPs can be easily defined as the satisfaction function of each CP. We assume that the q m files with the highest access probabilities in each CP m are requested. Then the satisfaction function of CP m is as follows, which is an increasing function of the caching request quantity.

R m = log 1 + q m 1 + 1 αm J m , (8)
where J m = l =m q l is the quantity of caching files requested by all the other CPs except CP m and α m is the amount of generated requests by the users of CP m. The satisfaction R m of a CP m was chosen as it is an increasing function of the number of files that are cached by a CP m as well as its traffic load α m . Indeed, the more files are cached at the SBSs and the higher the popularity of the files, the higher is the number of requests that can be served locally from the SBSs. Thus, more users of CP m can experience a higher transmission rate.

On the other hand, the satisfaction of a CP m decreases as the number of files cached by the other CPs increases. In this case, less storage is available for CP m and a higher number of its requests need to be served through the backhaul. It should be noted that any other function that has the same properties as R m can be chosen as a satisfaction function.

Given the constraints on the caching capacity of the mobile network, now we obtain the utility function of each CP m as

u m = R m -C m , (9)
where the cost C m and the revenue R m are defined in ( 6) and (8), respectively. It is obvious that u m is a concave function of the quantity of the caching requests. Given the charge price from the MNO, all the CPs respond with their quantities of caching requests simultaneously by maximizing their own utilities. Due to the limited caching capacity S, all the CPs can be considered as competitive players competing for the caching quantities. Therefore, we can formulate the quantity optimization problem of CPs as a non-cooperative game G = G(M, Q, U) consisting of the following components:

• The set of players in G is the set M of CPs.

• Given the quantity profile q -m ∈ Q m = l =m Q l of the opponents of m, the feasible action set of CP in the the caching capacity

d(Q M ) ≤ S is Q M (q -m = {q m ∈ Q m : q m ≥ 0}. (10)
• The utility u m of player m is given by [START_REF] Chen | Caching Incentive Design in Wireless D2D Networks: A Stackelberg Game Approach[END_REF]. In this context, the most adopted solution concept is the NE.

Definition 1. A quantity profile q * is a NE of the caching request quantity game G if

q * m ∈ Q m (q * -m ), ∀m ∈ M, (11) u m (q * ) ≥ u m (q m , q * -m ), ∀q m ∈ Q m (q * -m ). (12)
Provided the utility functions for the MNO and CPs, the optimal strategies of the leader and the followers are derived in the next section. In the Stackelberg game, the followers' strategies are predicted before the leader makes its own strategy. Therefore, the optimal quantity of caching requests of the CPs is analyzed first.

IV. STACKELBERG GAME SOLUTION

In this section, we derive the solution of the proposed Stackelberg game. In the sequential (Stackelberg) game, the leader moves first by predicting the strategies of the followers. The followers reply by optimizing their own utilities given the strategy of the leader. The result of the game is that the followers play exactly what the leader wishes. Therefore, the optimal strategy of the followers should be predicted first. In the following, we obtain the optimal quantities of caching requests of the CPs in the closed form.

A. Optimal Quantity of Caching Request

The CPs optimize their strategies of the quantity of the caching requests and provide them to the MNO given the charge price π announced by the MNO. The optimal q m is obtained by solving the following problem. q m = arg max q u m subject to q ≥ 0.

(13)

Given the charge price for the caching files, the CPs compete for the quantity of caching requests, which formulates a noncooperative game. In the following, we find the solution for this non-cooperative game.

Proposition 1 (Best Response). Given the charge price π announced by the MNO, the best response (BR) of each CP is the quantity of caching files it requests, which is

q BR m = 1 π -1 - J m α m + , (14)
with α m ≥ M .

Proof. The BR of the caching request quantity q BR m is obtained by checking the first derivative of u m with respect to q m ,

∂u m ∂q m = α m α m + α m q m + J m -π = 0. ( 15
)
The second derivative of u m with respect to q m is

∂ 2 u m ∂q 2 m = -α 2 m (α m + α m q m + J m ) 2 < 0, (16)
which guarantees a global optimal of u m . Since the utility of each CP u m is a convex function of q m , ( 14) is proved. The function () + is to ensure the requested caching quantity to be a non-negative value.

Remark 1. The total quantity of the caching requests of all the other CPs can be learnt or fed back at each CP. The q BR m is based on the local information α m , q m and the feedback J m as a single value of the summation.

Now we prove that the proposed non-cooperative game admits a unique NE.

Theorem 1 (Nash Equilibrium). Given the charge price π announced by the MNO, the NE of each CP is the quantity of caching files it requests, which is

q N E m = D m D = ( 1 π -1)a m b m D , ( 17
)
where a m is

a m = 1 -1 αm -1-α 1 α 1 M l=2,l =m αm-α l (α l -1)αm if m = 1 1 -1 α 1 -1-α M α M M -1 l=2 α 1 -α l (α l -1)α 1 if m = 1 (18) and b m is b m = M l=2,l =m (1 -1 α l ) if m = 1 M -1 l=2 (1 -1 α l ) if m = 1 ( 19
)
and

D = 1 - 1 -α 1 α 1 M l=2 1 α l -1 M l=2 1 - 1 α l . ( 20
)
If M = 2, then M -1 l=2 α1-α l (α l -1)α1 = 0 and M -1 l=0 1 -1 α l = 1.
Proof. We give only the sketch of the proof due to the space limitations. The trick for finding the NE of the proposed noncooperative game is to jointly solve the M functions of the BR for all the CPs. The M functions of the BR can be formulated as a matrix function denoted as Dq = C where the matrix D and vectors q and C are as follows, respectively.

     1 1 α1 . . . 1 α1 1 α2 1 . . . 1 α2 . . . . . . . . . . . . 1 α M 1 α M . . . 1           q 1 q 2 . . . q M      =      1 π -1 1 π -1 . . . 1 π -1      . (21)
The NE quantity of each CP is solved by applying the Cramer's rule q m = det(Dm) det(D) , where det(D) is the determinant of matrix D and det(D m ) is the determinant of matrix D m which is formed by replacing the m-th column of D by the column vector C. Remark 2. In caching, there are two basic modes. One is coded caching in which the SBSs cache any number of bits from the files. In this case, the NE quantity derived in (17) is the actual quantity of files requested by CP m. The other one is uncoded caching, in which a given file can only be cached as a whole or equally divided chunks. In this case, the round function is applied to q N E m before CP m replies to the MNO in order to obtain the integer optimal quantity of caching request. In our model, we assume the uncoded caching case so that only integer quantity of caching requests are considered.

B. Optimal Charge Price

After predicting the strategy policies of the CPs, the MNO optimizes the charge price π by solving the following problem.

π * = arg max π u o (q(π)) subject to π ≥ 0. (22)
We observe from ( 1) and ( 2) that the quantity of caching request from each CP m exists in the size of the set Q m . Therefore, we assume that the number of copies of each file f i ∈ Q m that are cached are defined as the quantized vector given by:

p fi = [. . . , p m -∆p m , p m , p m + ∆p m , . . . ] (23)
with size of q m for each CP m. p m is the mean access probability of files requested by CP m and ∆p m is the step size.

Given the number of times p fi each file f i is cached as defined in (23), we obtain

fi∈Qm p fi = q N E m f (p m ), (24)
where f (p m ) is a function of the mean access probability p m with the following form

f (p m ) = pm when qm is odd, pm + ∆pm 2 when qm is even. (25)
Since the MNO can predict the NE quantities of all the CPs, which are functions of the charge price π, the utility function of the MNO is then

u o = π M m=1 q m (π) - 1 S - M m=1 q m (π)f (p m ) . (26)
By predicting the requesting q m (π) from each CP m, the MNO can make its own optimal strategy, which is the charge price π * . Here we analyse the case where the total caching requests do not exceed the caching capacity of the HetNet.

Proposition 2 (Optimal Price). The optimal charge price π * provided by the MNO to maximize its own utility u o is as follows.

π * = r t + r S + r , ( 27
)
where r is a function of α and t is a function of both α and p defined as

t = M m=1 a m b m D , (28)
and

r = M m=1 a m b m f (p m ) D . (29)
Proof. Since r and t are independent of the optimization objective π, we rewrite the utility function of MNO u o as

u o = (1 -π)t - 1 S -( 1 π -1)r . ( 30
)
Then the first derivative with respect to π is

∂u o ∂π = r (Sπ -(1 -π)r) 2 -t. (31)
The second derivative with respect to π is

∂ 2 u o ∂π 2 = -2r(Sπ -(1 -π)r)(S + r) (Sπ -(1 -π)r) 4 . ( 32
)
By observing that the MNO will definitely provide a price in order to ensure d(Q m ) ≤ S, Sπ -(1 -π)r > 0 and then To ensure a positive total charge and also that the total caching requests do not exceed the caching capacity S, i.e., the cost C o is a positive limited value, the charge price given by the MNO should be restricted in the following range.

Corollary 1. The caching capacity S of the HetNet can be fully exploited if the charge price given by the MNO follows the range r S + r < π < 1.

(33)

Proof. π < 1 is proved by ensuring 1 π -1 > 0 in (30). r S+r < π is proved by ensuring 1 S-( 1π -1)r > 0 in (30). Remark 3. The optimal price π * provided in (27) always satisfies the feasible price range in (33).

C. Example

In this part, we show the 2-CP case as an example to illustrate the incentive Stackelberg game on caching. The protocol of the proposed Stackelberg game played between the MNO and CPs and the non-cooperative game played among the CPs are described as follows.

• The MNO predicts the NE quantities of the caching requests from all the CPs before making its own strategy.

q N E 1 = ( 1 π )(α 1 -1)α 2 α 1 α 2 -1 , (34)
q N E 2 = ( 1 π )(α 2 -1)α 1 α 1 α 2 -1 . (35)
• The optimal charge price π * is the strategy of the MNO by maximizing its utility u o .

π * = r + r t r + S , (36)
where r = 2 m=1

(αm-1)α l =m α1α2-1 , t = 2 m=1 (αm-1)α l =m α1α2-1 f (p m ) and f (p m ) = p m + ∆pm 2 .
• Given the charge price for each file of the caching request, each CP chooses a quantity of caching files as its best response. • The BR quantities of both CPs converge to the NE quantities in (34) and (35), respectively. The resulting q N E m maximizes both the utilities of the MNO and CPs.

q BR 1 = ( 1 π -1) - q 2 α 1 q BR 2 = ( 1 π -1) - q 1 α 2 .
m (q * m ) u m (2q * m ) u m (q * m /2) (c)
V. NUMERICAL RESULTS In order to illustrate the outcome of the proposed gametheoretical cache problem, without loss of generality, we simulate the scenario of one MNO and 2 CPs with different parameters. We assume identical file size as 10GB for high quality videos.

Fig. 2a shows the BR dynamic of the non-cooperative game for the 2-CP case. The parameters of the simulations are as follows: α 1 = 5, α 2 = 7. The charge price provided by the MNO is set as π = 0.3. The initial value of CP 2 is set to be q int 2 = 0. We can observe that the proposed noncooperative game converges very rapidly. The convergence is irrespective of the initial points. The convergence values result in the same quantities as the theoretical NE solutions given in (17) in Thereom 1.

Fig. 2b shows the utility function of the MNO with respect to the charge price. We can see that the proposed utility of the MNO always admits a global optimum for different sets of parameters. The utilities of the MNO with higher caching capacity are higher. This is because more caching requests can be served and less caching cost is spent for the same amount of caching files. The difference of the starting points of the curves are due to the feasible price region in Corollary 1. The global optimum in Fig. 2b result in the same price derived in (27). With the optimum price, the utility of the MNO improves even up to 50% than arbitrary chosen prices.

Fig. 2c shows the utility of a single CP with respect to the total number of CPs M while the quantity of the caching request q m changes. The charge price is provided as the optimal price π * for different total number of CPs. The optimal quantity q * m is derived accordingly. The utilities with double quantity 2q * m and half quantity q * m 2 are provided for comparison, respectively. From Fig. 2c, we observe that the more CPs, the lower the utility u m of each CP. This is due to the increasing number of CPs which results in the increase of the amount of storage space that is requested by the CPs and thus, a higher price is charged by the MNO. Moreover, the utility of each CP decreases according to [START_REF] Alotaibi | Towards a marketplace for mobile content: Dynamic pricing and proactive caching[END_REF] when the total storage capacity allocated for the other CPs increases. We can also see that by requesting the optimal caching quantity q * m , each CP achieves 20% higher utility than requesting q * m 2 and up to 50% than requesting 2q * m .

VI. CONCLUSIONS

We have studied a Stackelberg game of proactive edge caching between the leader MNO and the followers CPs. The best response, the resulting NE caching quantities, and the optimum charge price have been derived in closed forms; and the convergence of our proposed incentive mechanism has been validated via numerical studies. These numerical results also showed that both the MNO and CPs can achieve up to 50% higher utilities in the proposed Stackelberg game. This clearly points out the need of incentive caching mechanisms in 5G wireless networks.

Figure 1 :

 1 Figure 1: An illustration of the system model.

∂ 2 uo ∂π 2 <

 2 0, which guarantees a global maximum π * . By solving ∂uo ∂π = 0 in (31), we get the value of π * in (27), which completes the proof.Notice that the charge price should be a positive value π * > 0, therefore the result -

α1 = 4 ,

 4 α2 = 2.0, S = 100GB α1 = 3, α2 = 2.5, S = 100GB α1 = 4, α2 = 2.0, S = 150GB α1 = 3, α2 = 2.5, S = 150GB

Figure 2 :

 2 Figure 2: Numerical results for a) convergence of the best response for 2-CP case, b) utility function of the MNO with respect to charge price π for 2-CP case, and c) utility of CP with respect to the total number of CPs M .

Table I :

 I List of Notations.

	N = {1, 2, . . . , N }	set of SBSs
	M = {1, 2, . . . , M }	set of CPs
	qm	The number of files that CP m wants to cache
	p f i	The number of cached copies of file fi
	sn	The cache size of each SBS n
	π	The charged price for caching a given file
	uo	The utility of MNO
	um	The utility of CPs
	Qm	The set of files requested by each CP m
	pm	The mean access probability of CP m's files
	d(Qm)


Engin Zeydan
email: engin.zeydan@avea.com.tr

Ejder Bastug

Manhal Mehdi Bennis
email: bennis@ee.oulu.fi

Abdel Kader

Ilyas Alper Karatepe

Ahmet Salih Er
email: ahmetsalih.er@avea.com.tr

Merouane Debbah
email: merouane.debbah@centralesupelec.fr

Ejder Baştug

Alper Karatepe
email: alper.karatepe@avea.com.tr

Ahmet Salih

Mérouane Debbah

Big data caching for networking: moving from cloud to edge

Edge caching, machine learning, context-awareness, 5G.

I. INTRODUCTION

Nowadays, wireless data traffic is experiencing a tremendous growth due to pervasive mobile devices, ubiquitous social networking and resource-intensive applications of end-users with anywhere-anytime-to-anything connectivity. This unprecedented increase in data traffic chiefly driven by mobile video, online social media and over-the-top (OTT) applications are compelling mobile operators to look for innovative ways to manage their increasingly complex networks and scarce backhaul resources. In fact, a major driver of this backhaul problem is wireless video on-demand traffic in which users access contents whenever they wish in an asynchronous fashion (unlike live-streaming and digital TV), and has unique characteristics (i.e., users' demands concentrates on a small set of popular contents, resulting in heavy-tail distribution) [START_REF] Gsma | GSMA, The Mobile Economy[END_REF]. The explosion of data traffic stemming from diverse domains (i.e., healthcare, machine-to-machine communication, connected cars, etc.) with different characteristics (i.e., structured/non-structured) falls into the framework of big data [START_REF] Lynch | Big data: How do your data grow?[END_REF]. Indeed the potential offered by big data has spurred great interest from industry, government and academics (see [START_REF] Hu | Toward scalable systems for big data analytics: A technology tutorial[END_REF] and references therein).

At the same time, mobile cellular networks are moving toward the next generation 5G wireless networks, in which ultra-dense networks, massive-multiple-input multiple-output (MIMO), millimeter-wave communication, edge caching, device-to-device communications are heavily investigated (see [START_REF] Andrews | What will 5G be?[END_REF] and references therein). In contrast to the base-station centric architectures (possibly) designed for dump mobile terminals where requests are satisfied in a reactive way, 5G networks will be user-centric, context-aware and proactive in nature.

Driven by the surge of social and mobile applications, today's mobile network architectures ought to contemplate a new paradigm shift. Indeed, the era of collecting and storing information in data centers for data analysis and decision making has dawned. Telcos are looking for decentralized and flexible network architectures where predictive resource management plays a crucial role, thanks to the recent advances in storage/memory, context-awareness and edge/cloud computing [START_REF] Paschos | Wireless caching: Technical misconceptions and business barriers[END_REF]- [START_REF] Bonomi | Fog computing and its role in the internet of things[END_REF]. In the wireless world, big data brings about a new kind of information sets to network planning which can be inter-connected to get a better understanding of users' behaviour and network characteristics (i.e. location, user velocity, social geo-data, etc.).

In light of this, this work investigates the exploitation of big data in mobile cellular networks from a proactive caching point of view. Because human behaviour is highly predictable and June 6, 2016 DRAFT large amount of data is streaming through operators' networks, this paper proposes a proactive caching architecture. This architecture optimizes 5G wireless networks where large amount of available data is exploited by harnessing big data analytics and machine learning tools for content popularity estimation. We also show how this new architecture can be exploited for caching at the edge (particularly at base stations (BSs)), yielding higher users' satisfactions and backhaul offloading gains by moving contents closer to users. Nowadays, it is common to have terabytes of data per second flowing in a typical mobile operator consisting of 10 -20 million subscribers, which translates into roughly exabytes monthly. As a real-world example, we process a large amount of data collected on a big data-platform from one of the major mobile networks in Turkey with 17 millions of subscribers. These traces are collected from several BSs in hours of time interval and analysed inside the network to ensure privacy concerns and regulations. To the best of our knowledge, this is perhaps the first attempt to showcase the potential of big data for caching in 5G mobile networks.

A. Prior Work and Our Contribution

Not surprisingly, the exploitation of big data in mobile computing has been investigated recently in many works (see [START_REF] Bi | Wireless communications in the era of big data[END_REF] for example). Caching at the edge of mobile wireless networks (namely BSs and user equipments) is also of high interest as evidenced in [START_REF] Paschos | Wireless caching: Technical misconceptions and business barriers[END_REF], [START_REF] Ji | Wireless device-to-device caching networks: Basic principles and system performance[END_REF], [START_REF] Poularakis | Caching and operator cooperation policies for layered video content delivery[END_REF].

Briefly, technical misconceptions of caching for 5G networks are introduced in [START_REF] Paschos | Wireless caching: Technical misconceptions and business barriers[END_REF]. A study on improving the video transmission in cellular networks via asynchronous content reuse of cacheenabled devices is given in [START_REF] Ji | Wireless device-to-device caching networks: Basic principles and system performance[END_REF]. Cooperative caching for delivering layered videos to mobile users is studied in [START_REF] Poularakis | Caching and operator cooperation policies for layered video content delivery[END_REF].

Compared to existing works, our main contribution is to highlight and assess the potential gains of big data processing techniques for cache-enabled wireless networks, by using real traces of mobile users collected from BSs in a large urban area.

BENEFITS

Today's networking requirements are getting software-defined in order to be more scalable and flexible against big data. Tomorrow's big networks will be even more complex and interconnected. For that matter, MOs' data centers and network infrastructures will need to monitor traffic patterns of tens of millions of clients using possible collection units of user statistics data (e.g. location, traffic demand pattern, capability, etc) for proper analysis.

A. Current Challenges and Trends in Big Data Networking

Recently, data traffic patterns inside mobile operators' data centers have changed dramatically.

Big data has enabled high traffic exchange between gateway elements at backhaul. Although wireless technology has improved tremendously from 2G to 4G, backhaul connections of cellular networks have not seen such a rapid evolution. Hence, the mobile backhaul intra-traffic is slowly becoming larger than the inter-traffic between mobile backhaul elements and end-users. Indeed, in today's carrier networks, in addition to handling mobile users' traffic via mobile backhaul, fetching data from a number of different backend, database and cache servers, as well as the data generated by gateway and backhaul elements also contribute to this traffic load within the operator's infrastructure. In fact, interactions of user terminal (UT) triggers various interactions with hundreds of servers, routers and switches inside the backhaul and core network. For example, for an original user's HTTP request of 1 KByte, the intranet data traffic can increase up to 930x [START_REF] Farrington | Facebook's data center network architecture[END_REF]. This is contrary to the traditional carrier network architecture which assumes client and wireless access nodes as bottlenecks lacking computational overhead rather than the backhaul infrastructure. Moreover, since data growth is a major challenge in today's mobile infrastructures, managing this big data-driven networks in cloud environments is a pressing issue. For this reason, mobile edge computing (sometimes nicknamed "Fog" computing) is yet another emerging technology where edge devices provide cloud-computing like capabilities within the radio access network to carry out functionalities such as communication, storage and control [START_REF] Bonomi | Fog computing and its role in the internet of things[END_REF]. However June 6, 2016 DRAFT

for 5G networks, it should be noted that deploying distributed cloud computing capabilities near to each BSs site (especially at locations where traffic volume is relatively low) may also increase the deployment cost considerably compared to centralised computing solutions due to availability of hundreds of sites in a typical MO. Moreover, for modelling and prediction of spatio-temporal users' behaviour in user-centric 5G networks, network traffic arriving to a centralized location needs to be scaled out horizontally across servers and racks which is only feasible inside the core-site of a MO for proper analysis rather than distributed locations with relatively low traffic.

B. When Big Data Analytics Meets Caching: A Hadoop Case Study

Owing to the recent developments in networking technology and standards as well as new forms of personal communications, big data has gained increased popularity especially inside data centers and mobile operators. With the enormous challenges of big data inside networking world, it is evident that the only way to cope with the growing network data traffic is through better data management and movement of data from cloud into the edge. In recent years, Hadoop has been successful as a big data management software solution offering dramatic cost savings over traditional tier-one database infrastructures, processing capabilities of various data formats and parallel processing over multiple nodes. Additionally, advanced analytic techniques in machine learning in conjunction with non-relational databases that can exploit big data (e.g. NoSQL databases) have increased the opportunity of understanding big data.

It is clear that moving contents' proximity to the edge is important whenever user's connectivity times out while performing streaming and/or downloading activities. To mitigate this, allowing data to be closer to users by reducing the distance of content to users and pushing the right content and applications at the edge yield better user experience. For instance, allowing Hadoop's distributed data processing engine for analyzing users' behaviour from enormous amount of streaming data (through the core site of MOs) as well as exploiting proactively caching strategic contents at edges (e.g. at BSs) can ease the backhaul traffic and improve users' QoE by latency reduction. The following section discusses Hadoop-based big data processing platform and its relation with edge caching, as one way of dealing with big data inside MOs.

III. BIG DATA-AIDED CACHE-ENABLED ARCHITECTURE

The goal of this section is to investigate a new practical system architecture to gather, analyze, and proactively tackle the skyrocketing data surge. Motivated by the highly predictable June 6, 2016 DRAFT human behavior, the proposed architecture collects contextual information (e.g. user's viewing history and location information) and predicts users' spatio-temporal demand to proactively cache judiciously selected contents at the network edge. The proposed architecture parallelizes the computation and execution of the content prediction algorithms at core site and cache placement at BSs. By doing so, users' demands are highly satisfied yielding low latency and higher QoE.

A. Cache-Enabled BSs

Let us assume a small cell network composed of N small cells, where backhaul link and wireless link capacities of small cell n are denoted by C n and C n respectively. We assume that C n < C n reflecting a limited backhaul capacity scenario [START_REF] Andrews | What will 5G be?[END_REF]. A set of users are requesting a total number of D contents during T time duration from a library of F = {1, . . . , F } where each content f in this library has a size of L(f ) with L min < L(f ) < L max and finite bit-rate requirement of B(f ) during its delivery. To offload the capacity-limited backhaul, small base stations (SBSs) are equipped with finite storage capacity and cache a subset of contents from June 6, 2016 DRAFT the library F. However, due to the sheer volume of contents and users, it is very challenging to process and extract useful information to cache users' all contents at BSs, mainly due to limited storage constraints and lack of sufficient backhauls.

As alluded to earlier, minimizing the backhaul load via edge caching is very challenging. In this regard, a joint optimization of content popularity matrix (denoted by P where columns are contents, and rows are users or BSs depending on the scenario) and content cache placement at specific small cells are required while considering content sizes, bit rate requirements, backhaul, etc. Moreover, limited storage capacities of SBSs, the backhaul and wireless links, large library size and number of users with unknown ratings (i.e. empirical value of content popularity) have to be considered while dealing with a non-tractable cache decision [START_REF] Ji | Wireless device-to-device caching networks: Basic principles and system performance[END_REF]. Assuming that this non-tractable cache placement can be handled with greedy or approximate approaches (see [START_REF] Ji | Wireless device-to-device caching networks: Basic principles and system performance[END_REF], [START_REF] Poularakis | Caching and operator cooperation policies for layered video content delivery[END_REF]), the SBSs learn and estimate the sparse content popularity/ratings. The following subsection is dedicated to this task.

B. Big Data Platform for Analysis

In this section, a general big data processing framework for analyzing users' data traffic is discussed. The purpose of this platform is to store users' data traffic and extract useful information for proactive caching decisions. Supposing that Hadoop is deployed inside the core site of a MO, some of the requirements of this platform for our analysis are as follows:

i) Huge Data Volume Processing in Less Time: In order to make proactive caching decisions, data processing platform inside the mobile core network infrastructure should be capable of reading and combining data from disparate data sources and delivering intelligent insights quickly and reliably. For this reason, after mirroring the data streaming interface through network analyzing tools, the collected raw data need to be exported into a big data storage platform such as Hadoop Distributed File System (HDFS) via enterprise data integration methods (such as Spring Integration) for detailed analysis.

ii) Cleansing, Parsing and Formatting Data: Data cleansing is an essential part of the data analysis process. In fact, before performing any machine learning and statistical analysis on data, data itself has to be cleaned and usually this process takes more time than the machine learning analysis. Indeed, there are multiple steps involved in data cleansing process. First, raw data needs to be cleaned. The raw data itself might contain some malfunctioning, inappropriate and inconsistent packets with incorrect character encodings, etc. which need June 6, 2016 DRAFT to be eliminated. The next step is to extract the relevant fields from the raw data itself.

In this stage, the required headers from control and data packets that will be analyzed in later stages are extracted based on the data analysis and modeling requirements. Finally, the parsed data needs to be encoded accordingly (e.g. in Avro or Parquet format) for appropriate storage inside HDFS.

iii) Data Analysis: Using the formatted data in HDFS, different data analytics techniques can be applied over header or/and payload information of both control and data planes using high level query languages such as Hive Query language (HiveQL) and Pig Latin. The aim of such a step is to find relationships between control and data packets, e.g. the location or Mobile Subscriber Integrated Services for Digital Network Number (MSISDN) of users (that are present in control packets but not in data packets) to the requested content (that are present only in data packets) through successive Map-Reduce operations.

iv) Statistical analysis and visualizations: After machine learning analysis is done to predict the spatio-temporal user behaviour for proactive caching decisions, the results of the analysis can be stored and reused. Moreover, the results can be re-formatted to be used for further analysis using appropriate Extract, Transform and Load (ETL) tools, and can be input to other processing systems such as Apache Spark's MLlib, etc. In addition, visualizations such as graphs and tables can be used to represent the data in a visual format for ease of understanding.

In such a platform, machine learning techniques which lie at the heart of recommendationbased engines can be applied so that users' strategic contents can be inferred from a large amount of available data. In what follows, as a practical case study, we first analyse huge amount of users' traffic on such a big data platform and use this data to estimate the content popularity matrix P, which is essentially required for caching decision. Subsequently, we conduct a numerical study for showcasing the gains of caching at BSs.

IV. A PRACTICAL CASE STUDY

Data streaming traces for this practical case study are collected from one of the regional core district of mobile operator's network which consists of more than 10 regional core areas in Turkey. A mirroring procedure is initialized for transferring streaming traces into the big data platform in the core network. A fast speed of 200 Mbit/sec at peak hours is observed through one of the mirrored interfaces in the core network. The total average traffic over all regional June 6, 2016 DRAFT areas consists of approximately over 15 billions of packets in the uplink and over 20 billions of packets in the downlink direction daily. This is equivalent to almost 80 TByte of total data. 1This mirrored network traffic is analyzed on the data processing platform which is essentially based on Hadoop. In particular, the big data platform is composed of Cloudera's Distribution Including Apache Hadoop (CDH4) version on four nodes including one cluster name node, with each node empowered with INTEL Xeon CPU E5-2670 running @2.6 GHz, 32 Core CPU, 132

GByte RAM, 20 TByte hard disk. As stated before, the platform is in charge of extracting the useful information from raw data. In our analysis, the traffic of approximately 7 hours (starting from 12 pm to 7 pm on Saturday 21'st of March 2015) is collected. 2 The traces processed on the big data platform have approximately four millions of HTTP content requests, and stored in a comma-separated text file format after following steps (i) and (ii) as described in Section III-B. After some post processing (i.e., calculating content sizes), the final-traces table/file which includes arrival time (abbreviated as FRAME-TIME), requested content (abbreviated as HTTP-URI) and content size (abbreviated as SIZE) is obtained, and is used in the rest of this study. The detailed description of the data extraction process is given in [START_REF] Baştug | Big data meets telcos: A proactive caching perspective[END_REF]. Note that the data extraction process is specific to our scenario for proactive caching. However, similar studies in terms of usage of big data platform and exploitation of big data analytics for telecom operators can be found in the literature (see [START_REF] Celebi | On use of big data for enhancing network coverage analysis[END_REF] for instance).

A. System Parameters and Studied Methods

In the numerical setup, we assume that D contents are requested from the processed data (namely from final-traces table) over a time interval of 6 hours 47 minutes. Information on FRAME-TIME, HTTP-URI and SIZE are also taken from the final-traces table. Then, the requests are pseudo-randomly assigned to N BSs. The wireless link capacities of small cells, backhaul link and storage capacities are set to identical values within each other for ease of revealing the caching gains. The list of simulation parameters are summarized in Table I. The global procedure contains the following two major steps: • Caching strategic contents: The cache decision procedure at the base stations is made by storing the most-popular contents greedily at the SBSs until no storage space remains as in [START_REF] Baştug | Big data meets telcos: A proactive caching perspective[END_REF]. 4 .

As regards to the performance metrics: i) request satisfaction, as QoE metric, is defined as the amount of contents delivered at a given target rate, and ii) backhaul load corresponds 3 Regularized SVD is chosen due to its outperforming performance with respect to other CF methods [START_REF] Lee | A comparative study of collaborative filtering algorithms[END_REF]. 4 This greedy approach is chosen for ease of exposition. Once can also employ online cache placements strategies (e.g. least recently used (LRU), least frequently used (LFU)).

June 6, 2016 DRAFT to the percentage of the traffic passing over the backhaul links over the total possible traffic volume induced by the content requests. A detailed analytical formulas of request satisfaction and backhaul load can be found in [START_REF] Baştug | Big data meets telcos: A proactive caching perspective[END_REF].

B. Numerical Results and Discussions

In this section, based on the available information in the final-traces table, we conduct a numerical study to reveal the gains of caching. The impact of storage size on the users' request satisfaction is plotted in Fig. 2. Therein, 0% of storage size corresponds to no caching, whereas 100% of storage is equivalent to caching the entire library (17.7 GByte). In the figure, we note that the users' request satisfaction has a monotonically increasing behaviour, and somewhat intuitive, 100% of satisfaction is achieved in both methods when the complete content catalog (with 100% of storage size) is stored by fixing parameters in our setting to plausible (and realistic) values in order to see the regimes where 100% satisfaction is achieved. However, a performance gap between the ground truth and CF is observed until 79% of storage size which is mainly due to the estimation errors. For instance, when the BSs have 40% of storage size for caching, the ground truth yields 89% of satisfaction whereas the performance of CF stays at 75%. see that both methods yield less backhaul load (namely higher offloading gains). For instance, having 79% of storage size at BSs, both methods offload 98% of backhaul. However, the ground truth outperforms the CF method since it has complete information of the content ratings. On the other hand, after a certain storage size, a dramatical decrease of backhaul is observed in both approaches. Compared to previous works which mostly consider identical content sizes, we are dealing with real traces with non-identical content sizes.

In the simplest form, one can write the backhaul load of a particular content as load = popularity × size, if not cached. Therefore, a relatively less popular but very big-sized contents might lead to such a behaviour on the backhaul load, if not cached at the SBSs. This points out the importance of taking into account contents sizes in caching decision which reflects a more practical/realistic characterization of backhaul usage.

Fig. 3 illustrates the evolution of users' request satisfaction with respect to the backhaul capacity ratio, defined as the ratio of total backhaul link capacity n C n over total wireless link capacity n C n . It is clear from the figure that increasing the backhaul link capacity yields higher satisfactions, both in ground truth and CF approaches. This is due to the fact that bottleneck in the backhaul becomes less relevant with the increment of this ratio. The above performance results demonstrate the case with 30% of rating density in CF.

However, it is clear that increasing the training rating density of CF, less estimation error and hence closer satisfaction gains to ground truth is expected. In order to show this, Fig. 4 demonstrates the effect of training rating density on root-mean-square error (RMSE) where the error is defined as the root-mean-square of the difference between users' content satisfaction of the ground truth and CF approaches over all possible storage sizes.

V. CONCLUSIONS AND FUTURE WORK

In this paper, we have introduced a proactive caching architecture for 5G wireless networks by processing a huge amount of available data on a big data platform, and leveraging machine learning tools for content popularity predictions. Additionally, relying on this prediction and using extracted traffic information from this data, the gains of caching have been investigated throughout numerical studies. One possible direction of this work is to investigate the proposed big data analysis framework in a real-time fashion. For this, recent frameworks that exist in Hadoop eco-system such as Apache Spark and its built-in libraries Spark Streaming for realtime data processing and MLLib for machine learning libraries are of interest.

Fig. 1 Figure 1 :

 11 Fig.1shows such combined network architecture where a big data platform deployed at core site is in charge of tracking/predicting users' demand, whereas cache-enabled BSs store the strategic contents predicted by the big data platform. The following sections examine the architecture details.

Figure 2 :

 2 Figure 2: Numerical results for proactive caching at the base stations.

Fig. 2

 2 Fig. 2 also shows the impact of storage size on the backhaul load/usage. In the figure, we

Figure 3 :

 3 Figure 3: Evolution of satisfaction with respect to the normalized backhaul capacity.

Fig. 4 Figure 4 :

 44 Figure 4: Change of the RMSE with respect to the training density.

Table I :

 I List of simulation parameters. Estimation of content popularity P (where columns are contents, and rows are BSs): This is done on the big data platform by processing large amount of collected data and exploiting machine learning tools. Two methods are examined in the numerical setup: i) Ground Truth: The P matrix is constructed by considering all available information in the final-traces table. The matrix has 6.42% of rating density in total.ii) Collaborative Filtering: 30% ratings available in the final-traces table are picked uniformly at random for training of P matrix estimation. Then, the remaining missing entries/ratings in the traces are predicted via the regularized singular value decomposition (SVD) from collaborative filtering (CF) methods[START_REF] Lee | A comparative study of collaborative filtering algorithms[END_REF].

	Parameter	Description	Value
	T	Time duration	6 hours 47 minutes
	D	Nr. of requests	422529
	F	Nr. of contents	16419
	N	Nr. of small cells	16
	L min	Min. size of a content	1 Byte
	Lmax	Max. size of a content	6.024 GByte
	B(f )	Bitrate of content f	4 Mbyte/s
	n Cn	Total backhaul link capacity	3.8 Mbyte/s
	n C n	Total wireless link capacity	120 Mbyte/s
	•

  3

In fact, the general trend of data in the network is following an exponential growth, i.e., in

2012, the total average data traffic per day was over 7 TByte in both uplink and downlink.[START_REF] Gsma | GSMA, The Mobile Economy[END_REF] Note that the size of raw data is around 1.2 TByte for observed time duration T , and for offline processing, it can take up-to five days to extract the relevant headers from this data using a single server. June 6, 2016 DRAFT

June 6, 2016 DRAFT

This research has been supported by the ERC Starting Grant 305123 MORE (Advanced Mathematical Tools for Complex Network Engineering), the SHARING project under the Finland grant 128010 and TUBITAK TEYDEB 1509 project grant, numbered 9120067 and the project BESTCOM. Some technical details and procedures in this work are omitted due to space and format limitations.