Luigi Vigneri
email: luigi.vigneri@eurecom.fr

Rasyvoulos Spyropoulos
email: spyropou@eurecom.fr

Chadi Barakat
email: chadi.barakat@inria.fr

ality of Experience-Aware Mobile Edge Caching through a Vehicular Cloud

Densi cation through small cells and caching in base stations have been proposed to deal with the increasing demand for Internet content and the related overload on the cellular infrastructure. However, these solutions are expensive to install and maintain. Instead, using vehicles acting as mobile caches might represent an interesting alternative. In our work, we assume that users can query nearby vehicles for some time, and be redirected to the cellular infrastructure when the deadline expires. Beyond reducing costs, in such an architecture, through vehicle mobility, a user sees a much larger variety of locally accessible content within only few minutes. Unlike most of the related works on delay tolerant access, we consider the impact on the user experience by assigning di erent retrieval deadlines per content. In our paper, we provide the following contributions: (i) we model analytically such a scenario; (ii) we formulate an optimization problem to maximize the tra c o oaded while ensuring user experience guarantees; (iii) we propose a variable deadline policy; (iv) we perform realistic tracebased simulations, and we show that, even with low technology penetration rate, more than 60% of the total tra c can be o oaded which is around 20% larger compared to existing allocation policies.

INTRODUCTION

e large di usion of handheld devices is leading to an exponential growth of the mobile tra c demand which is already overloading the core network [START_REF]Cisco. Cisco visual networking index: Global mobile data tra c forecast update[END_REF]. To deal with such a problem, several works suggest to store content in small cells (SCs) or user equipments. Recently, it has been proposed the use of private or public transportation as storage points and mobile relays (vehicular cloud) [1,2,[START_REF] Vigneri | Storage on wheels: O oading popular contents through a vehicular cloud[END_REF] controlled by mobile network operators (MNOs) through a cellular interface. In urban environments, the number of vehicles is expected to be considerably higher than in any envisioned SC deployment. Hence, the sheer number of vehicles along with the lower cost involved make this an interesting alternative.

In this paper, we exploit such a vehicular cloud to store popular content to o oad part of the mobile tra c demand. In our model, a user can query nearby vehicles to download a content with low delay (and at low cost for the MNO). However, since caches will be quite small compared to the daily catalogue, the user might not be inside the range of any cache storing the requested content at that time. To alleviate this, we propose that each request can be delayed for a small amount of time, if there is a local cache miss. Conversely, if the content is not found within a deadline, the user will be redirected to the cellular infrastructure. While the idea of delay tolerance has already been extensively discussed in literature, in this work we introduce three fundamental novelties:

Vehicle storage capacity "virtually" extended. Most of related works [START_REF] Balasubramanian | Augmenting Mobile 3G Using WiFi[END_REF][START_REF] Cai | Exploiting double opportunities for deadline based content propagation in wireless networks[END_REF][START_REF] Mehmeti | Is it worth to be patient? Analysis and optimization of delayed mobile data o oading[END_REF] require the user to move to encounter new base stations and see new caches. is is problematic as most users exhibit a nomadic behavior, staying in the same location for long periods. As a result, such delayed o oading architectures require deadlines in the order of half to a couple of hours to demonstrate performance bene ts [START_REF] Balasubramanian | Augmenting Mobile 3G Using WiFi[END_REF][START_REF] Lee | Mobile Data O oading: How Much Can WiFi Deliver[END_REF][START_REF] Mehmeti | Is it worth to be patient? Analysis and optimization of delayed mobile data o oading[END_REF]. Instead, when caches are on vehicles, especially in a dense urban environment, a user will see a much larger number of caches within the same amount of time, thus virtually extending the size of the accessible local storage. is leads to be er hit rates with considerably smaller deadlines.

Variable deadlines. e majority of edge caching related works aims at policies that exclusively minimize the load on the cellular infrastructure. In most delayed o oading se ings, the worst-case delay guarantee o ered to the user is usually xed for all content requests and set to large values. Conversely, in this work we allow the operator to set di erent deadlines for di erent content. is variability in the deadlines brings two advantages: rst, it allows to increase the percentage of the tra c o oaded as we will see in the rest of the paper; second, these deadlines can be adapted according to the speci c characteristics of the content (e.g., size) to improve user ality of Experience (QoE) as we explain below. User QoE-Aware o oading. We evaluate the user QoE according to the experienced slowdown which has recently become popular [START_REF] Harchol-Balter | Performance Modeling and Design of Computer Systems: eueing eory in Action[END_REF]. is metric relates the waiting delay with the "net" download time. For example, a user requesting a web page of a few megabytes (normally taking some seconds) will be quite frustrated if she has to wait an extra 1-2 minutes to encounter a vehicle caching that web page. However, a user downloading a large video or so ware le might not even notice an extra 1-2 minutes delay. Speci cally, in our framework an MNO can calibrate the user experience by se ing a required slowdown which upper bounds the tail behavior of the response time. Tuning the waiting time per content ensures maximum o oading with li le QoE degradation.

While there are a number of additional architectural and incentiverelated questions to consider, the main focus of this paper is on the modelling of the above scenario and on the formulation of a related (nontrivial) optimization problem. e main contributions of the paper can be summarized as follows:

• We model the problem of maximizing the percentage of tra c o oaded through the vehicular cloud considering the user QoE (captured by the slowdown metric) and a large range of realistic conditions (e.g., content of heterogeneous size), and we solve the corresponding optimization problem.

• We validate our ndings using simulations with real traces for vehicle mobility and content popularity. We show that, in an urban scenario, our system can achieve considerable o oading gains with modest technology penetration (less than 1% of vehicles participating in the cloud) and low mean slowdown (that leads to average deadlines of a few minutes). • We study the impact of di erent user QoE guarantees on operatorand user-related performance, and compare variable and xed deadline policies.

e rest of the paper is organized as follows: in Section 2, we compare our work with the previous literature; in Section 3, we de ne the system model with the main assumptions; then, in Section 4, we present the mathematical formulation of the problem, and we solve a reasonable approximation (since the original problem is hard); we validate our results through real trace-based simulations in Section 5; nally, we conclude our paper with a summary and future work in Section 6.

RELATED WORK

Caching at the edge of the network has been deeply investigated by researchers lately [START_REF] Golrezaei | Wireless Device-to-Device Communications with Distributed Caching[END_REF][START_REF] Poularakis | Video delivery over heterogeneous cellular networks: Optimizing cost and performance[END_REF]. Golrezaei et al. [11] propose to replace backhaul capacity with storage capacity at the SC access points (APs), called helpers; the challenge faced by the authors was in the analysis of the optimum way of assigning content to the helpers in order to minimize the expected download time. Poularakis et al. [START_REF] Poularakis | Video delivery over heterogeneous cellular networks: Optimizing cost and performance[END_REF] focus their a ention on video requests trying to optimize the service cost and the delivery delay; in their framework, prestored video les can be encoded with two di erent schemes in various qualities. While such distributed caching schemes for SCs provide very interesting theoretical insights and algorithms, they face some key shortcomings. A large number of SCs is required for an extensive enough coverage by SCs, which comes at a high cost [START_REF] Alliance | NGMN 5G White Paper[END_REF]. E.g., in a macro-cell of a radius of a few kilometers, it is envisioned to place 3-5 SCs, of range a few hundred meters. By contrast, in an urban environment, the same area will probably contain thousands of vehicles. Furthermore, the smaller size of edge caches and the smaller number of users per cell raise the question whether enough overlap in user demand would be generated locally to have a high enough hit ratio, when real tra c is considered.

To alleviate the aforementioned problem of requests overlap at a low cost, a number of works introduce delayed access. is can be seen as an enforced delay until a WiFi access point is encountered to o oad the cellular connection to a less loaded radio access technology [START_REF] Balasubramanian | Augmenting Mobile 3G Using WiFi[END_REF][START_REF] Mehmeti | Is it worth to be patient? Analysis and optimization of delayed mobile data o oading[END_REF], or until to reach peer nodes in a P2P infrastructure [START_REF] Cai | Exploiting double opportunities for deadline based content propagation in wireless networks[END_REF]. For example, Balasubramanian et al. [START_REF] Balasubramanian | Augmenting Mobile 3G Using WiFi[END_REF] develop a system to augment mobile 3G capacity with WiFi, using two key ideas: delay tolerance and fast switching. is enforced delay virtually extends the coverage of WiFi APs, allowing a larger ratio of connections to be o oaded than the mere physical coverage of WiFi APs allows. In other works [START_REF] Cai | Exploiting double opportunities for deadline based content propagation in wireless networks[END_REF][START_REF] Gao | Deadline-Sensitive Mobile Data O oading via Opportunistic Communications[END_REF] a di erent deadline is assigned to each content. However, these deadlines are problem input parameters and cannot be used to improve performance (e.g., the amount of data o oaded, QoE) as we do in our paper. Nevertheless, these approaches require the user to move in order to encounter new base stations and new caches. User mobility is o en nomadic and slow, requiring the respective algorithms to enforce very large delays (o en in the order of hours) before any performance improvement is perceived by the operator. Instead, in our paper we present two main novelties: (i) having the SC and cache move, the operator can o oad up to 60% of its tra c with minimum QoE impact; (ii) while other works consider pre-assigned deadlines, we allow variable delay tolerance per content, and also allow the operator to optimize it (by se ing an upper limit on the slowdown).

In a previous work, we have dealt with the idea of vehicular cloud used to o oad part of the tra c and accessible by handheld devices [START_REF] Vigneri | Storage on wheels: O oading popular contents through a vehicular cloud[END_REF]. However, the paper only mentions initial thoughts about the architecture without dealing with QoE or variable deadlines. e hype around vehicular networks as part of the cellular infrastructure has been con rmed by car manufacturers [1] or by the launch of new companies [2] that o er network connectivity to public and private transportation.

SYSTEM MODEL 3.1 Content access protocol

We consider a network with three types of nodes: • Infrastructure nodes (I): base stations or macro-cells; their role is to seed content into vehicles and to serve user requests when the deadline expires. • Helper nodes (H ): vehicles such as cars, buses, taxis, trucks, etc., where |H | = h; these are used to store popular content and to serve user requests at low cost through a direct vehicle to mobile node link. • End user nodes (U ): mobile devices such as smartphones, tablets or netbooks; these nodes request content to H and I nodes (the last ones are only contacted when the deadline expires and the content is still not entirely downloaded). e basic protocol is made up of three phases (Fig. 1): • (I → H ): I nodes place content in H nodes according to the chosen allocation policy. is policy is the main outcome of this paper. We refer to this phase as seeding which is repeated at the beginning of operator selected time windows to adjust to varying content access pa erns. If seeding is performed during o -peak times, the seeding cost can be considered equal to 0. In our work we will focus on this scenario1 . • (H → U): an end user node can request content i to the vehicles that are inside her communication range 2 . If content i is found, then the U node can download bytes from the vehicle during the contact. If the download is not terminated, then the requesting mobile user will query nearby vehicles for a time equal to i . is deadline is decided for that content i by the allocation policy during the seeding phase. e related local access cost is null.

• (I → U): in case of a content not successfully downloaded within a time i , the U node's request will be served (partially or entirely) by the cellular infrastructure. e related cost is equal to the number of bytes downloaded from I nodes.

Main assumptions

A.1 -Catalogue. Let K be the set of all possible contents that users might request (also de ned as "catalogue"), where |K | = k. Let further c be the size of the cache in each vehicle. We make the natural assumption that c k.

A content i ∈ K is of size s i (in MB)
and is characterized by a popularity value ϕ i measured as the expected number of requests within a seeding time window from all users and all cells.

A.2 -Inter-meeting times. We assume that the inter-meeting times T i j (t ) between a user requesting content i ∈ K and a vehicle j ∈ H are IID random variables characterized by a known cumulative distribution function (CDF) F T (t ) = P[T i j ≤ t] with mean rate λ. is model does not make any assumption on the individual user and vehicle mobility pa erns and can capture a number of inter-contact time models proposed in related literature such as exponential, Pareto, or mixed models [START_REF] Karagiannis | Power Law and Exponential Decay of Intercontact Times between Mobile Devices[END_REF].

A.3 -Cache model. Let x i denote the number of vehicles storing content i.

e vector x will be the control variable for our optimal cache allocation problem. We also assume H nodes to store the whole content, i.e., fractional storage is not allowed.

A.4 -Chunk download. Let b i j be the number of bytes downloaded from content i by a U node during the j t h meeting. b i j are positive IID continuous random variables having equal mean µ and variance σ 2 . Let further M i be a random variable counting the number of contacts within i . en, we de ne B i M i j=1 b i j as the number of bytes downloaded within i for content i.

A.5 -QoE metric. First, we de ne t i s i /r as the net download time of content i by a user, i.e., the amount of time it takes to download the content (excluding any potential waiting time to encounter vehicles holding the content), where r is the download rate from the cellular infrastructure. As for videos, t i can be thought of as the video duration (and r as the playout rate). en, we introduce the maximum slowdown per content imposed by our system when the content is fetched from the infrastructure that ties content download time to its size as

ω i i +t i t i = 1 + i s i /r
. e larger ω i is, the worse the impact of the allocation policy on user experience. is is in fact a worst case metric, because if the content is downloaded before the deadline expires, say at some time d i < i (i.e., there is a cache hit), the real slowdown is lower and equal to 1 + d i t i . Nevertheless, we choose to use the maximum slowdown in our theoretical framework as a more conservative approach for the user, and keep analysis simpler. Furthermore, since the operator's goal is to consider the global QoE (and not only per request), we consider a weighted average of the maximum slowdown according to the content popularity de ned as

Ω(y) = 1 k i=1 ϕ i • k i=1 ϕ i • ω i .
For simplicity, we will refer to Ω(y) as mean slowdown. An MNO can use this metric to calibrate the global user QoE of the system by se ing a parameter ω max > 1 that upper bounds the mean slowdown. is value can be seen as a sort of "budget" available to the MNO that can be reallocated between contents. Moreover, it can set a maximum tolerable deadline max to avoid excessively large deadlines for speci c content. We summarize the notation used in the paper in Table 1.

OPTIMAL CONTENT ALLOCATION 4.1 O loading optimization problem

e operator's goal is to de ne a policy to maximize the bytes o oaded through the vehicular cloud while satisfying storage capacity and user QoE requirements.

is policy should infer the optimal content allocation x and the optimal deadlines y to assign to the content catalogue. e number of bytes o oaded through the vehicular cloud per request is either equal to s i , if the content is entirely downloaded from vehicles, or to B i , otherwise. For popular content, we can consider the expected value of this quantity since the envisioned number of requests during a seeding time window is large. e following lemma captures these considerations in the objective function Φ(x, y) to be optimized:

Φ(x, y) k i=1 ϕ i • E [min{B i , s i }] , (1)
C 4.2. e objective function Φ(x, y) is equivalent to

Φ(x, y) ≡ k i=1 ϕ i • s i 0 1 -F B i (t ) dt, (2)
where F B i is the CDF of B i .

P . e objective function can be wri en as follows:

Φ(x, y) = k i=1 ϕ i • E [min{B i , s i }] = k i=1 ϕ i • s i 0 t • f B i (t ) dt + +∞ s i s i • f B i (t ) dt ,
where f B i is the PDF of B i . e rst integral becomes equal to

s i • F B i (s i ) - s i 0 F B i (t ) dt
by integration by parts, while the second integral is trivially equal to

s i • (1 -F B i (s i )).
A er simplifying the null terms, we obtain Eq. ( 2).

We formulate an optimization problem based on the following ideas: an ideal content allocation should replicate content with higher popularity in many di erent vehicles in order to increase the probability to nd it from a requesting user. Trivially, more replicas lead to smaller waiting times. However, if the marginal gain from extra replicas is nonlinear, it might be be er to also have some less popular content at the edge. As the storage capacity of each vehicle is limited, our objective is thus to nd the optimal replication factor per content to minimize the total load on the cellular infrastructure while accounting for end users QoE: P

1. e solution to the following optimization problem maximizes the bytes o oaded through the vehicular cloud:

maximize x∈X k ,y∈Y k k i=1 ϕ i • s i 0 1 -F B i (t ) dt (3)
subject to s t • x c • h, Ω(y) ≤ ω max ,
where

X {a ∈ R | 0 ≤ a ≤ h} and Y {b ∈ R | 0 ≤ b ≤ max }.
Each vehicle has a storage constraint and cannot store more than c contents. However, instead of considering h individual storage constraints, we only consider the global cache capacity of the vehicular cloud that corresponds to improve the tractability of the problem. Although the global capacity constraint introduces an error in the problem formulation, such an error is expected to be low when caches are large compared to the mean content size as we will explain at the end of this section (see randomized rounding).

Solving Problem (1) requires the knowledge of F B i and, therefore, of B i . We prove that the following theorem holds: L 4.3. B i can be approximated by a compound Poisson process as the number of vehicles participating in the vehicular cloud increases, if the mean inter-meeting rate with such vehicles is small.

P

. Assume that user m requests content i. Let {T i j (t ), t > 0, j ∈ H s.t. x i j = 1} be x i identical and independent renewal processes corresponding to the inter-contact times with vehicles storing content i.

e CDF of T i j is F T (t ) with mean λ (see Assumption A.2). Let further {T i (t ), t > 0} be the superposition of these processes. According to the Palm-Kintchine theorem [START_REF] Karlin | A First Course in Stochastic Processes[END_REF], {T i (t )} approaches a Poisson process with rate λ • x i if x i large3 and λ small. A Poisson process can be de ned as a counting process that represents the total number of occurrences up to time t. us, the total number of contacts within the deadline

M i = {T i ( i )} is again a Poisson process. Remember that B i M i j=1 b i j .
Observe that the reward (bytes downloaded) in each contact is independent of the inter-contact times, i.e., M i and b i j are independent, and b i j are IID random variables with same distribution. Since M i is a Poisson process, then B i is a compound Poisson process. L 4.4. e rst two moments of B i are given by:

E[B i ] = µ • λ • x i • i , Var[B i ] = (µ 2 + σ 2 ) • λ • x i • i . P .
e expected value of a compound Poisson process can be computed using conditional expectation, where the expectation is calculated using the Wald's equation. Similarly, it is possible to compute the moment of second order of B i , and then its variance using the total law of variance.

F B i (s i ) = 1 -L -1 e (b * i j (s )-1) •λ •x i • i /s (s i ), (4)
where b * i j (s) is the Laplace transform of b i j .

P

. A random sum of identically distributed random variables has a Laplace transform that is related to the transform of the summed random variables and of the number of terms in the sum

B * i (s) = M * i (b * i j (s)),
where

B * i (resp. b * i j ) is the Laplace transform of B i (resp. b i j ) and M * i is the Z-transform of M i .
Since the number of meetings within i is Poisson distributed (see proof of Lemma 4.3), we can write B * i (s) as follows:

B * i (s) = e (b * i j (s )-1) •λ •x i • i .
Moreover, it is well known that the CDF of a continuous random variable X is given by F

X (x ) = L -1 L {f X } s (s i ) where L -1 {F (s)}(t )
is the inverse Laplace transform of F (s). us, F B i (s i ) corresponds to Eq. ( 4).

All the quantities needed to solve the optimization problem are known, and can be plugged in Eq. ( 3). However, due to the large number of contents to consider, the related maximization problem cannot be solved e ciently. For this reason, further insights, approximations and speci c scenarios will be discussed in the rest of the paper.

QoE-Aware Caching (QAC)

Problem ( 1) is a mixed-integer nonlinear programming (MINLP) problem. MINLP refers to optimization problems with continuous and discrete variables and nonlinear functions in the objective function and/or the constraints. P . e problem is NP-hard since it includes mixed-integer linear programming as a subproblem [START_REF] Kannan | On the computational complexity of integer programming problems[END_REF].

What is more, this problem is in general non-convex. is means that the solution can be computed by global optimization methods, but this is generally not an e cient solution as it does not scale to a large number of contents. Similarly to a number of works we consider the continuous relaxation of a MINLP which is identical to the mixed-integer problem without the restriction that some variables must be integer. e continuous relaxation brings two fundamental advantages: rst, it is possible to evaluate the quality of a feasible set of solutions; second, it is much faster to optimize than the mixed-integer problem. According to this relaxation, we also introduce a new objective function Φ qac (•) that approximates Eq. ( 1) in order to convert the problem in a convex optimization problem, hence improving tractability. L 4.7. Eq. ( 1) can be approximated by

Φ qac (x, y) = k i=1 ϕ i • min{E[B i ], s i }. C 4.8
. Let e Φ qac -Φ be the error introduced by Lemma 4.7. e following statements hold:

(1) For a given E[B i ], as the content size s i tends to 0 or becomes large, the approximation becomes exact, i.e., e tends to 0.

e error e is equal to

e = k i=1 ϕ i • α (s i ) • |s i -E[B i ]| + σ B i • f B i (s i ) , where α (s i ) = min{F B i (s i ), 1 -F B i (s i )}. P . (1
) e following equivalences are true:

lim s i →0 Φ qac = lim s i →0 Φ = k i=1 ϕ i • s i lim s i →+∞ Φ qac = lim s i →+∞ Φ = k i=1 ϕ i • E[B i ].
(2) It is easy to see that

E[min{B i , s i }] = F B i (s i ) • E[B i |B i ≤ s i ] + s i • (1 -F B i (s i )). (5) E[B i |B i ≤ s i ] corresponds
Φ qac -Φ E[B i ] F B (s i )⋅(s i -E[B i ]) σ B ⋅ f B (s i )
Upper bound on the error 0 +∞ be considered as a normal distribution [START_REF] Schmidli | Lecture Notes on Risk eory[END_REF]. us, we can write its truncated mean as:

E[B i |B i ≤ s i ] = E[B i ] -σ B i • f B i (s i ) F B i (s i ) ,
where σ B i is the standard deviation of B i , and can be inferred from Corollary 4.4 4 . If E[B i ] > s i , the error e introduced by Φ qac can be evaluated as follows:

e = k i=1 ϕ i • | min{E[B i ], s i } -E[min{B i , s i }]| = k i=1 ϕ i • (s i -E[min{B i , s i }]). (6)
en, we compute the second term of Eq. ( 6) from Eq. ( 5), and, a er some calculations, we obtain:

e = k i=1 ϕ i • [(1 -F B i (s i )) • (E[B i ] -s i ) + σ B i • f B i (s i )].
Similarly, we compute e when E[B i ] ≤ s i .

A qualitative analysis of e can be found in Fig. 2, where we can see that the error is concentrated in the region where s i ≈ E[B i ], and it tends to 0 otherwise. Using the above approximation, Problem (1) can be converted in a convex optimization problem that can be solved extremely e ciently and reliably: P 2. Consider the approximation introduced by Lemma 4.7. en, the solution to the following convex optimization problem maximizes the bytes o oaded through the vehicular cloud:

maximize x∈ X k , ỹ∈ Ỹ k log k i=1 ϕ i • e xi + ˜ i , subject to xi + ˜ i ≤ log s i µ • λ , ∀i ∈ K, i s i • e xi ≤ c • h, Ω( ỹ) ≤ ω max , where xi log x i , ˜ i log i , X {a ∈ R | -∞ ≤ a ≤ log h}, Ỹ {b ∈ R | -∞ ≤ b ≤ log max }.

P

. We rewrite the objective function Φ qac (•) in an equivalent form that removes the min function:

Φ qac (x, y) = k i=1 ϕ i • min{E[B i ], s i } = k i=1 ϕ i • E[B i ], s. t. E[B i ] ≤ s i , ∀i ∈ K, (7)
where the equivalence is true since the related maximization problem will choose the control variables x and y such that 0 ≤ E[B i ] ≤ s i as any scenario where Lemma 4.4. According to Eq. ( 7), Problem (1) becomes maximize

E[B i ] > s i is suboptimal. Remember that E[B i ] = µ • λ • x i • i from
x∈X k ,y∈Y k k i=1 ϕ i • x i • i , subject to x i • i ≤ s i µ • λ , ∀i ∈ K, s t • x ≤ c • h, Ω(y) ≤ ω max .
e above optimization problem is a geometric program (GP). A GP is an optimization problem where the objective is a posynomial function 5 and the constraints are posynomial or monomial functions.

e main trick to solve a GP e ciently is to convert it to a nonlinear but convex optimization problem, since e cient solution methods for general convex optimization problem are well developed [START_REF] Boyd | Convex Optimization[END_REF]. e conversion of a GP to a convex problem is based on a logarithmic change of variables and on a logarithmic transformation of the objective and constraint functions. We apply the following transformations to the above optimization problem:

xi log x i ⇔ e xi x i ; ˜ i log i ⇔ e ˜ i i .
We obtain a problem expressed in terms of the new variables x and ỹ. By taking the logarithm of the objective function and of the constraints, it can be proved that the related problem is convex [START_REF] Boyd | Convex Optimization[END_REF].

While this problem seems more complicated in its formulation, NLP is far trickier and always involves some compromise such as accepting a local instead of a global solution. Conversely, a GP can actually be solved e ciently with any nonlinear solver (e.g., MAT-LAB, SNOPT) or with common optimizers for GP (e.g., MOSEK, GPPOSY). Finally, we use randomized rounding [START_REF] Raghavan | Randomized rounding: A technique for provably good algorithms and algorithmic proofs[END_REF] on the content allocation which is a widely used approach for designing and analyzing such approximation algorithms. We expect the rounding error to be low since the number of copies per content is usually large (then the decision whether rounding up or down has only a marginal e ect in the objective function). To validate this, in Table 2 we compare the objective value from our allocation to the one corresponding to the continuous solution of Problem (2) (we report the percentage of tra c o oaded). As the la er is an upper bound on the optimal solution of the mixed-integer problem, the actual performance gap is bounded by the values shown in Table 2. We refer to this policy as QoE-Aware Caching (QAC). 5 A posynomial function f (x ) is a sum of monomials:

f (x ) = K k =1 c k x a 1k 1 x a 2k 2 • • • x a nk n
, where c k > 0.

PERFORMANCE EVALUATION 5.1 Simulation setup

We build a trace-driven MATLAB simulator to validate our theoretical ndings. Our tool simulates YouTube requests in the centre of San Francisco over ve days. We use the following traces:

• Vehicle mobility. We use the Cabspo ing trace [START_REF] Piorkowski | DAD data set ep /mobility[END_REF] to simulate the vehicle behaviour; this trace records the GPS coordinates for 531 taxis in San Francisco with granularity of 1 minute. To improve the accuracy of our simulations, we increase the granularity to 10 seconds by linear interpolation. • User mobility. We use synthetic traces based on SLAW mobility model [START_REF] Lee | SLAW: A New Mobility Model for Human Walks[END_REF]. According to this model, users move in a limited and de ned area around popular places. e mobility is nomadic where users alternate between pauses (heavy-tailed distributed) and travelling periods at constant (but random) speed. • Content. We infer the number of requests per day from a database with statistics for 100.000 YouTube videos [START_REF] Zeni | YOUStatAnalyzer: a tool for analysing the dynamics of YouTube content popularity[END_REF]. To increase the number of simulations and to provide sensitivity analysis for content size, bu er capacity and cache density, we randomly select 10.000 contents from the catalogue. Inline with proposed protocols for vehicle communications (e.g., 802.11p, LTE ProSe), we consider short (100 m) or long (200 m) communication ranges between U and H nodes. As most wireless protocols implement some rate adaptation mechanism, our simulator also varies the communication rate according to the distance between the user and the vehicle she is downloading from, with a mean of 5 Mbps. We also set r = 1 Mbps which approximates the streaming of a 720p video (remember that r corresponds to the playout rate in the case of videos -see Assumption A.5). We set the cache size per vehicle in the range 0,1-1% of the total catalogue which is an assumption that has also been used in other works [START_REF] Golrezaei | Femtocaching and device-to-device collaboration: A new architecture for wireless video distribution[END_REF][START_REF] Poularakis | Video delivery over heterogeneous cellular networks: Optimizing cost and performance[END_REF] (we use 0,2% as a default value). We generate content size from either a truncated normal or a bounded Pareto distribution 6 (instead of using the content size from the YouTube trace) in order to experiment di erent characteristics of the catalogue. Finally, we consider ω max = 3 which corresponds to an average deadline of only a few minutes (compared to video durations that can go up to 1,5 hours).

Our simulator works as follows: rst, it generates a set of content requests concentrated at day-time; inter-arrival times between successive requests are exponentially distributed according to the IRM model [START_REF] Co Man | Operating systems theory[END_REF] which is the de facto standard in the analysis of storage systems. Next, the simulator associates to each request the coordinates (and the mobility according to the SLAW model) of the user requesting the content.

en, it allocates content in caches according to di erent allocation policies. For each request, a user downloads chunks of video when she is in the communication range of a vehicle storing the requested content. When the deadline expires, the potential remaining bytes are downloaded from the cellular infrastructure.

We consider and compare the following allocation policies: • QAC. is policy solves the optimization problem with a reasonable approximation for content of generic size. is policy is described in Section 4.2.

• FIXED. is policy solves the optimization problem when a content can be downloaded with large probability in on contact, and deadlines are xed. is policy is suitable for content of small size and is described in Vigneri et al. [START_REF] Vigneri | Storage on wheels: O oading popular contents through a vehicular cloud[END_REF]. • QAC-SC. is policy solves the optimization problem of FIXED when deadlines are variable. e problem is biconvex and is solved numerically.

• MP. is policy stores the most popular content in vehicle bu ers until caches are full while any other content gets 0 copies. Deadlines are xed. is policy is optimal for sparse scenarios where caches do not overlap. • RAND. Content is allocated randomly with xed deadlines.

Caching policies evaluation

In Fig. 3 we plot the amount of data o oaded for di erent allocation policies. is plot also includes the 95% con dence interval. e fraction of tra c o oaded by QAC is much larger (additional gains of around 20%) than any other policy in any situation. For instance, when long range communications are considered, o oading gains are in the order of 60% for QAC, and no more than 40% for QAC-SC, FIXED and MP. RAND policy performs poorly in any scenario. It is also interesting to note that, while QAC-SC is expected to bene t from the deadline variability, it performs similar to xed deadline policies since the assumption that a content can be downloaded in one contact is unrealistic for content of 200 MB. Not substantial differences have been observed for di erent content size distributions: however, from additional experiments we have noticed that, as the coe cient of variation of the content size distribution decreases (i.e., contents have similar size), the percentage of tra c o oaded by variable and xed deadline policies becomes similar.

Fig. 4 depicts the fraction of data o oaded by the vehicular cloud as a function of number of vehicles, bu er size and mean content size for long range communications when content size distribution is truncated normal. Speci cally, in Fig. 4a we perform sensitivity analysis according to the number of vehicles h in the cloud which varies from 100 to 500. When h is larger than 200, more than 40% of the tra c can be o oaded by QAC. While the number of envisioned connected vehicles in the centre of San Francisco is expected to be much larger, the low technology penetration rate analyzed still provides considerable amount of data o oaded. is result is important to promote the start up phase of the vehicular cloud. However, it is interesting to note that in a sparse scenario (h = 100), QAC performs poorly. is happens because the value of E[B i ] = λ • µ • x i • i that has been used in QAC holds only if the number of vehicles participating in the vehicular cloud is large (see Lemma 4.3). What is more, from Corollary 4.8, the error of the approximation used by QAC is proportional to the standard deviation of B i which increases in a sparse environment.

Fig. 4b compares di erent bu er capacities per vehicle. Bu er size goes from the 0,1% to the 1% of the catalogue (where h = 531). Interestingly, considerable performance gains can be achieved with very reasonable storage capacities. Here the simulations are performed on a set of 10.000 contents, but in a scenario with a larger realistic catalogue (e.g., 1000 times larger), it seems doable to store 0,1-0,5% of the contents needed to achieve good savings. E.g., if one considers an entire Torrent catalogue (∼3 PB) or the entire Net ix catalogue (∼3 PB), a mobile helper capacity of about 3 TB (0,1%) already su ces to o oad more than 40% of the total tra c for long range communications (while around 30% for xed deadline policies). Furthermore, as the bu er capacity increases, QAC-SC o oads much more tra c than FIXED, while this is less evident when the cache size per vehicle is lower. Basically, as the cache size increases, o oading gains are mainly provided by the deadline variability rather than the cache policy chosen.

In Fig. 4c we analyze the e ect of content size by varying the mean content size from 30 MB to 200 MB. As expected, for small content, QAC-SC o oads more tra c than any other policy. After this threshold, since the assumption of entire download of a content during a contact becomes inaccurate, this policy o oads less tra c. A similar behavior can be seen for FIXED that uses the same assumption. What is important to notice, however, is that the tra c o oaded by QAC is stable for any content size.

Finally, we perform an analysis of the user QoE by allowing different values of ω max . In Fig. 5, we show the upper bound on the mean slowdown ω max that an MNO should set in order to reach some speci c o oading gains, from 30% to 60%. We consider long range communications, and content size drawn from a truncated normal distribution with mean 200 MB, but similar results can be obtained for short range communications or other content size distributions. e required mean slowdown to o oad more tra c increases slowly for variable deadline policies while we notice an exponential growth for xed deadlines. Basically, Fig. 5 can be seen as a description of the e ect produced by additional gains on the QoE: for instance, an MNO should double the value of ω max (100% increase) with FIXED policy to o oad 10% more tra c, while the mean slowdown only increases in the range of 15-40% for QAC and QAC-SC to have the same improvement in the o oading gains.

is low impact on the slowdown highlights the advantages introduced by variable deadlines. Knowing the function that ties user 4a), bu er capacity (Fig. 4b) and mean content size (Fig. 4c) for long range communications. experience and slowdown (e.g., linear, logarithmic) can lead to a be er interpretation of the plot. However, this behavioural analysis goes beyond the scope of the paper.

CONCLUSION AND FUTURE WORK

Compared to similar works in mobile edge computing, this work introduces several contributions: (i) it considers mobile relays (vehicles) that virtually increase the cache size seen by pedestrian users; (ii) while the majority of the works consider xed deadlines, our paper deals with variable deadlines by introducing a QoE metric; (iii) the generic model includes per chunk-level downloads from vehicles. In the paper, we propose a caching policy that can be adopted by MNOs. is policy has been largely validated analytically and through real trace simulations. e comparison with traditional approaches shows a large increment in the percentage of tra c o oaded. We have also given insights to an operator on how to set the QoE parameters. As future work, it would be interesting to tune the user QoE taking into account the content type along with the content size. While we have shown that QAC performs well in the majority of the situations, it would be interesting to study closer approximations for the generic formulation of the problem.

Figure 1 :

 1 Figure 1: Communication protocol.

L 4 . 1 .

 41 Given the previous assumptions, the amount of bytes o oaded through the vehicular cloud during a seeding time window is given by

L 4 . 5 .

 45 e CDF of B i is given by

T 4 . 6 .

 46 Problem (1) is an NP-hard combinatorial problem.

Figure 2 :

 2 Figure 2: Error introduced by Φ qac (x, y) in Lemma 4.7 for a xed value of E[B i ].

Figure 3 :

 3 Figure 3: O loading gains.

  O loading gain vs. h (c = 0, 2% • k).

  O loading gain vs. c (h = 531).

  O loading gain vs. mean content size.

Figure 4 :

 4 Figure 4: Fraction of tra c o loaded as a function of vehicle density (Fig.4a), bu er capacity (Fig.4b) and mean content size (Fig.4c) for long range communications.

Figure 5 :

 5 Figure 5: Mean slowdown needed to reach speci c o loading gains for long range communications.

Table 1 :

 1 Notation used in the paper.

	CONTROL VARIABLES
	x i	Number of replicas stored for content i
	i	Deadline for content i
	CONTENT
	k	Number of content in the catalogue
	ϕ i	Number of requests for content i
	s i	Size of content i
	c	Bu er size per vehicle
	MOBILITY
	T i j	Inter-meeting time between U and H nodes
	λ	Mean inter-meeting rate with vehicles
	M i	Number of contacts within i
	h	Number of vehicles
	CHUNK DOWNLOAD
	b i j	Bytes downloaded per contact
	µ	Mean of b i j
	σ 2	Variance of b i j
	B i	Total bytes downloaded for content i
	f B i	Probability density function of B i
	F B i	Cumulative density function of B i
	QOE PARAMETERS

r Download rate from cellular infrastructure (or playout rate for videos) Ω Mean slowdown max Maximum deadline ωmax Upper bound on the mean slowdown

Table 2 :

 2 Estimated o loading gains of rounded allocation vs. continuous relaxation for di erent cache sizes (in percentage of the catalogue size).

	Cache size	0,1%	0,2%	0,5%	1%
	Rounded (QAC)	34,25%	44,10%	52,88%	60,75%
	Continuous	34,29%	44,12%	52,89%	60,75%

e generic case (i.e., non-null seeding cost) is a straightforward extension when seeding time windows are large enough to amortize content seeding.

e communication range size depends on the physical layer technology used between U and H nodes.

While this assumption (i.e., x i large) might not always be true, exponential intermeeting times have been largely used in literature and considered as a good approximation, especially in the tail of the distribution[START_REF] Conan | Characterizing Pairwise Inter-contact Pa erns in Delay Tolerant Networks[END_REF].

Note that σ B i σ that is the standard deviation for a single contact.

Since content size and popularity are not correlated (from the analysis of the trace), we randomly assign content size to the catalogue.

ACKNOWLEDGMENT

is work was funded by the French Government (National Research Agency, ANR) through the "Investments for the Future" Program reference #ANR-11-LABX-0031-01.


Luigi Vigneri
email: luigi.vigneri@eurecom.fr

Salvatore Pecoraro
email: salvatore.pecoraro@eurecom.fr

Rasyvoulos Spyropoulos
email: thrasyvoulos.spyropoulos@eurecom.fr

Chadi Barakat
email: chadi.barakat@inria.fr

Per-Chunk Caching for Video Streaming from a Vehicular Cloud

Caching content at the edge of mobile networks is considered as a promising way to deal with the data tsunami. In addition to caching at xed base stations or user devices, it has been recently proposed that an architecture with public or private transportation acting as mobile relays and caches might be a promising middle ground. In previous work, we have assumed users are streaming video les and have analyzed how many replicas of each video le to cache in such a vehicular eet working towards minimizing the amount of bits per le downloaded from (expensive) infrastructure links. However, this work has been assuming that a vehicle will store the entire content, or none of it. In practice, later chunks have an inherent "delay tolerance" as there is more time to nd them before they must be played out. What is more, numerous studies as well as everyday experience suggest that most les (e.g., YouTube) are not entirely watched. is makes the previous policies suboptimal, as fewer (or no) replicas could be allocated to late chunks of a le and more to the most popular chunks. In this work, we formulate an optimization problem to compute the optimal allocation per-chunk, to minimize the load on the cellular infrastructure, and we show that signi cant performance gains can be achieved compared to per-content allocation policies.

INTRODUCTION

e recent di usion of handheld devices is driving an exponential increase of the mobile tra c demand which is already overloading the cellular infrastructure [START_REF]Cisco Visual Networking Index: Global Mobile Data Tra c Forecast Update[END_REF]. Mobile network operators are trying to keep up by deploying small cells in urban environments and by edge caching (at femtocells, Wi-Fi access points or even user equipments) [START_REF] Golrezaei | Wireless Device-to-Device Communications with Distributed Caching[END_REF][START_REF] Poularakis | Video delivery over heterogeneous cellular networks: Optimizing cost and performance[END_REF]. Recently, both industry [1] and academia [START_REF] Vigneri | Storage on Wheels: O oading Popular Contents rough a Vehicular Cloud[END_REF] have proposed to use vehicles acting as mobile relays to store replicas of popular content. anks to their intrinsic mobility, vehicles can increase the "e ective" storage capacity a user has access to (since a user can meet a larger number of vehicles, compared to xed small cells, in the same time interval [START_REF] Vigneri | Storage on Wheels: O oading Popular Contents rough a Vehicular Cloud[END_REF]) and also have favorable characteristics in terms of CAPEX/OPEX compared to xed outdoors small cells.

In our previous studies, we have considered the problem of downloading whole content [START_REF] Vigneri | Storage on Wheels: O oading Popular Contents rough a Vehicular Cloud[END_REF] or streaming videos [START_REF] Vigneri | Streaming Content from a Vehicular Cloud[END_REF] from vehicles acting as mobile caches (vehicular cloud). Intuitively, the rough tradeo is the following: the higher the number of vehicles caching a content, the higher the chance that this content (or chunk) will be downloaded from such a vehicle "on time" (rather than from expensive macro-cell links); however, the marginal bene t of each extra replica is decreasing, creating a non-trivial tradeo between content popularity and caching policy. In our la er work [START_REF] Vigneri | Streaming Content from a Vehicular Cloud[END_REF], we have further assumed that content is streamed chunk-by-chunk, and if a chunk (e.g., corresponding to the 30th minute of a video) can be downloaded from an encountered vehicle before it must be played (i.e., up to 30 minutes a er the user starts watching the content) this is data tra c that is o oaded from the main infrastructure without any visible impact on the user.

However, in that work we have made the simplifying assumption that either all chunks or no chunks of a content must be cached in a vehicle. Said otherwise, every chunk of a content must have the same number of replicas. Yet, as evident by the above example, early chunks have a smaller chance to be downloaded from a vehicle than later chunks, due to the larger inherent delay tolerance of the la er. At the same time, common experience as well as recent measurements suggest that a lot of video content (e.g., YouTube les) are only partially watched as users o en abandon the playout of a video before it ends. ese two opposing "forces" call for a perchunk optimization policy: (i) the former suggests that it is perhaps wasteful to cache too many of the early chunks and give instead more space to later ones that have a higher chance to be o oaded; (ii) the la er suggests that early chunks have di erent popularity than later chunks and thus perhaps deserve more storage space. Our goal in this paper is to address this tradeo and propose per-chunk cache allocation policies that outperform existing ones. To our best knowledge, this is the rst work to consider per-chunk caching in such a vehicular context. We make the following contributions:

• Modelling. We model the video streaming of content 1 when chunks can be opportunistically downloaded from nearby vehicles. In Section 2 we state the main assumptions, and we formulate an optimization problem to compute an allocation (per-chunk) maximizing the expected amount of o oaded tra c as a function of network characteristics (e.g., vehicle density, chunk popularity). • Optimization. In Section 3, based on this model, we propose two appropriate approximations according to the download rate from vehicles. We show that these problems are NP-hard, and we solve a related continuous relaxation. • Performance analysis. In Section 4 we validate our theoretical results using real traces for content popularity and vehicle mobility, and show that our system can o oad up to 45% of streamed data in realistic scenarios even with modest technology penetration, which is more than 10% larger than traditional content caching techniques.

Finally, we conclude our paper in Section 5 with a summary and future work.

SYSTEM MODEL

We introduce here the system model and related assumptions.

Video Streaming Model

We consider a network with three types of nodes:

• Infrastructure nodes (I). Base stations or macro-cells. ey provide full coverage and can serve any content request.

Main Assumptions

A.1 -Catalogue. Let K be the set of all possible contents that users might request (also de ned as "catalogue") where |K | = k. A content i ∈ K is divided into s chunks of equal size. Each chunk is characterized by a popularity value ϕ i j measured as the expected number of requests within a seeding time window from all users and all cells. Similar to a number of works on edge caching [START_REF] Golrezaei | Femtocaching and Device-to-Device Collaboration: A New Architecture for Wireless Video Distribution[END_REF][START_REF] Poularakis | Video delivery over heterogeneous cellular networks: Optimizing cost and performance[END_REF], we assume this time window to be a system parameter chosen by the cellular operator. Every time window, the cellular operator refreshes its caches installed in vehicles according to the new estimated popularity 3 .

A.2 -Mobility model. We assume that the inter-meeting times T i j between a user requesting chunk j of content i ∈ K and any vehicle storing such a chunk are independent and identically distributed random variables characterized by an exponential distribution 4 with mean rate λ. Exponential inter-meeting times have been largely used in literature and considered as a good approximation, especially in the tail of the distribution [START_REF] Vania | Characterizing Pairwise Inter-contact Pa erns in Delay Tolerant Networks (Autonomics)[END_REF][START_REF] Karagiannis | Power Law and Exponential Decay of Intercontact Times between Mobile Devices[END_REF].

A.3 -Cache model. Let x (w ) i j ∈ {0, 1}, i ∈ K , j ∈ {0, .
. . , s}, w ∈ H be an indicator variable denoting if helper node w stores chunk j of content i. Let further x i denote the number of H nodes storing content i:

x i j = w ∈H x (w ) i j .
e matrix x will be the control variable for our optimal cache allocation problem. A.4 -Content download rate. We assume r I = r P + ϵ (ϵ > 0 small) in order to limit the access to the cellular infrastructure to the minimum required to ensure smooth playout (for simplicity, we assume ϵ equal to 0). We also assume that the download from the helper nodes is faster than r I , i.e., r H ≥ r I > r P . ese are reasonable assumptions due to the reduced communication distance: scenarios where r I (and/or r H ) are lower than the playout rate require initial bu ering which is known to signi cantly degrade QoE [START_REF] Hossfeld | Initial delay vs. interruptions: Between the devil and the deep blue sea[END_REF], and are orthogonal issues to the problem addressed in this paper. A.5 -Data o loading. A request for content i will download a number of chunks from H nodes. is number is a random variable that depends on x i j as well as random mobility variables (intercontact times and contact durations).

e notation used in the paper is summarized in Table 1.

Problem formulation

Given the above assumptions, we can propose a policy where: (i) the user's video is never interrupted provided the infrastructure can guarantee at least the playout rate (if that is not the case, then this is an issue of the infrastructure); (ii) while the user is watching the video, future parts of it are actually downloaded from locally encountered caches (in principle pre-fetched) thus o oading some tra c from the infrastructure. As long as the playout bu er remains non-empty, I nodes never need to be accessed. And when they do, we ensure that the minimum necessary amount of bytes is downloaded from the infrastructure (r I = r P + ϵ). e goal of the paper is to nd the allocation that minimizes the number chunks downloaded from the cellular infrastructure needed to ensure uninterrupted streaming. us, we formulate the following optimization problem according to the previous assumptions: P 1. e solution to the following optimization problem maximizes the expected number of chunks o oaded through the vehicular cloud: maximize

x∈X k ×s k i=1 s j=1 ϕ i j • (j-1) •τ 0 P[A i j | x, t] dt, (1)
subject to k i=1 s j=1 x (w ) i j ≤ c, ∀w ∈ H , (2)
where A i j is the event that chunk j of content i is o oaded through the vehicular cloud, P[A i j | x, t] is the probability of downloading chunk j of video i at time t, given caching allocation x, and X {a ∈ N | 0 ≤ a ≤ h} is the feasible region for the control variable x.

e objective function counts the number of chunks downloaded from the cellular infrastructure in a seeding time window for the entire catalogue. For each content, this is equivalent to the content popularity times the probability to download a chunk before it must be played out. Since each chunk has a duration of τ seconds this time is equal to (j-1)•τ (for the j-th chunk of a content). e number of replicas is bounded by the number of vehicles participating in the vehicular cloud. What is more, each vehicle has a storage constraint and cannot store more than c bytes (see Eq. ( 2)).

ANALYTICAL MODEL

Problem (1) is hard to solve for a number of reasons: it is basically a discrete optimization problem, and the probability to download a given chunk depends on the probability to download past chunks and is hard to derive analytically, in general. Instead, we propose two approximate ways to solve the problem, namely for in nite (Section 3.1) and limited contact bandwidth (Section 3.2) (between users and vehicles).

In nite bandwidth

We introduce the following de nition: De nition 3.1 (In nite bandwidth). Assume that a user is streaming content i. If a vehicle storing a subset of chunks for content i comes in range to the user, in the in nite bandwidth scenario we assume the user is able to download all these chunks. Note, we do not require that this is true in a real setup. We simply say that our policy will assume so, for simplicity (and thus might not always be optimal). is assumption becomes more accurate if for example there are many vehicles and many contents to ensure each one stores only few chunks per content 5 , and of course depends also on the content size and download rate between H and I nodes. According to De nition 3.1, Problem (1) can be rewri en as follows:

ϕ i j • (1 -e -λ •(j-1) •τ •x i j ), subject to k i=1 s j=1 x (w ) i j ≤ c, ∀w ∈ H . (3)
P . When there is in nite bandwidth per contact

P[A i j | x, t] = P[A i j | x].
Assuming further exponential inter-contact times, the probability to nd a vehicle storing chunk ij before its playout time is

(j-1) •τ 0 P[A i j | x] = P[T i j < (j -1) • τ ] = 1 -e -λ •(j-1) •τ •x i j ,
where the second equivalence is true because T i j follows an exponential distribution with rate λ times x i j replicas for the given chunk. e constraints simply ensure the capacity of each vehicle is not violated.

Problem ( 2) is an NP-hard combinatorial problem, when the allocation variables x i j are integer, as it is a bounded knapsack problem (BKP) with a nonlinear objective function [START_REF] Martello | Knapsack Problems: Algorithms and Computer Implementations[END_REF]. A standard approach in such cases is to consider a continuous relaxation of the problem. is not only converts the problem to a convex one (as we will see), that can be solved e ciently, but also can be solved analytically, giving valuable insights into the optimal allocation. Furthermore, we can replace the individual capacity constraint of Eq. ( 2) with a global capacity constraint, i.e., k i=1 s j=1

x i j ≤ c • h. (4)
It is easy to see that, if x is fractional, any allocation that ts the global capacity is also a feasible allocation, given the assumption of IID mobility 6 . We can prove the following result: T 3.2. e solution of Problem (2) when x is real is given by

x i j =            0, if ϕ i j < L, 1 λ •(j-1) •τ • ln λ •(j-1) •τ •ϕ i j ρ , if L ≤ ϕ i j ≤ U , h, if ϕ i > U ,
where ρ is an appropriate Lagrange multiplier, 2) is a convex optimization problem since its objective function is convex (because it is the sum of convex functions), the constraint is linear and the set of feasible solutions is convex. We solve it by Karush-Kuhn-Tucker (KKT) conditions. For such a convex problem, this method provides necessary and sucient conditions for the stationary points to be optimal solutions. e KKT conditions for Problem (2) are

L ρ λ •(j-1) •τ , U ρ •e h•λ•(j-1)•τ λ •(j-1) •τ . P . Problem (
           l i j • x i j = 0 m i j • (h -x i j ) = 0 ρ • c • h -k i=1 s j=1 x i j = 0
where l i j and m i j are appropriate Lagrange multipliers related to the bounds of x. e related Lagrangian function L(x) is

L(x) = k i=1 s j=1 ϕ i j • (1 -e -λ •(j-1) •τ •x i j ) + l i j • x i j + + k i=1 s j=1 m i j • (h -x i j ) + ρ • c • h - k i=1 s j=1 x i j .
We compute the stationary points by computing the derivative of the Lagrangian function for each content i. Since the problem is convex, these points are also global solutions.

dL(x) dx i j = λ • (j -1) • τ • ϕ i j • e -λ •(j-1) •τ •x i j + l i j -m i j -ρ = 0.
Making explicit x, we obtain:

x i j = 1 λ • (j -1) • τ • ln λ • (j -1) • τ • ϕ i j ρ -l i j + m i j .
en, the system constraints create three regimes depending on the content popularity: • Low popularity. e optimal allocation x must be greater or equal to 0. According to the KKT conditions, we have two cases that satisfy the constraint: (i) x i j > 0, l i j = 0; (ii) x i j = 0, l i j > 0. e threshold between case (i) and (ii) depends on the content popularity: speci cally, a content will get more than 0 copies when its popularity is higher than L which can be easily computed when x i j > 0:

1 λ • (j -1) • τ • ln λ • (j -1) • τ • ϕ i j ρ > 0 ϕ i j > ρ λ • (j -1) • τ L.
• High popularity. e content allocation is upper bounded by the number vehicles h participating in the cloud. Similarly to the previous scenario, due to the KKT conditions, the constraint is satis ed when: (i)

x i < h, m i = 0; (ii) x i = h, m i > 0: ϕ i j < ρ • e h •λ •(j-1) •τ λ • (j -1) • τ U .
• Medium popularity. In all the other cases (i.e., when U ≤ ϕ i j ≤ L), the optimal allocation is proportional to the logarithm of the content popularity.

As a nal step, we use randomized rounding [START_REF] Raghavan | Randomized rounding: A technique for provably good algorithms and algorithmic proofs[END_REF] to go back to an integer allocation, which is a widely used approach for designing and analyzing such approximation algorithms. Furthermore, when cache sizes are large enough, such methods are expected to introduce very small approximation errors.

Limited bandwidth

e in nite bandwidth model provides some initial insights on a per-chunk allocation for content streaming. In reality, contact duration (or equivalently the available bandwidth between U and H ) is limited and only a few chunks can be downloaded per contact. In this subsection, we describe a model that exploits such a limited bandwidth to improve the previous problem formulation. We introduce the following de nition: De nition 3.3 (Limited bandwidth). Assume that a given user requests content i. Assume further that the playout of such a content has started at time 0, and a vehicle is met at time t. In the limited bandwidth scenario, the user is able to download a chunk j of content i with probability p i j (z) during a contact, where z j •τ -t is the residual playout time, and p i j (z) is non-decreasing in z.

As an example, assume that a content i is split in 10 chunks which are stored in all vehicles. Assume that, at time 0 (i.e. when the user starts watching), a user is in the communication range of a vehicle storing chunks 1 to 5. Since chunks are downloaded in order (this is the optimal policy to avoid missing deadlines), it is easy to see that the probability to download chunk 1 (p i1 (0)) is higher than the probability to download chunk 5, as the contact with that vehicle might end before all chunks before 5 are downloaded. However, if the user is currently watching chunk 3 and encounters the same vehicle, only chunks 4 and 5 need to be downloaded, hence increasing the chances of ge ing 5 before the contact is over.

Probability p i j (z) is very hard to model analytically, because it depends on vehicle mobility, allocation of earlier chunks to vehicles and residual playout time z. To simplify things, we can assume as a rst step that this probability is independent of the allocation, but is a given (non-decreasing) function of time (this function could be estimated, for example, as the mean over a number of contact sample paths, for a given allocation). In that case, we can write the following optimization problem: P 3. Consider the limited bandwidth scenario. e solution to the following optimization problem maximizes the expected number of bytes o oaded through the vehicular cloud:

maximize x∈X k ×s k i=1 s j=1 ϕ i j • (1 -e -Q i j •λ •(j-1) •τ •x i j ), subject to k i=1 s j=1 x (w ) i j ≤ c, ∀w ∈ H , (5)
where

Q i j 1 (j-1) •τ • (j-1) •τ 0 p i j (z) dz. P .
In the limited bandwidth model, a chunk can be downloaded with probability p i j (z) ≤ 1 during a meeting. If the contacts with vehicles storing the requested content follow a Poisson process having mean rate λ • x i j , as we have assumed, p i j (z) introduces a thinning of the original Poisson process and leads to a Poisson process with rate p i j (t ) • λ • x i j . e la er is the rate of successful contacts (i.e., contacts with vehicles storing chunk ij, and which are long enough to download chunk ij. We can further make a mean value approximation and replace this time-dependent probability with its mean over the entire playout interval:

Q i j 1 (j -1) • τ • (j-1) •τ 0 p i j (z) dz
is basically introduces one "thinning" parameter for each content chunk, Q i j . e rest of the proof then continues as in the case of Problem ( 2). e following result then holds, in terms of the optimal allocation for this limited bandwidth case. e proof follows that of eorem 3.2 replacing λ with Q i j λ, and is omi ed. T 3.4. e solution of Problem (2) when x is real is given by

x i j =            0, if ϕ i j < L, 1 Q i j •λ •(j-1) •τ • ln Q i j •λ •(j-1) •τ •ϕ i j ρ , if L ≤ ϕ i j ≤ U , h, if ϕ i > U ,
where

L ρ Q i j •λ •(j-1) •τ and U ρ •e h•Q i j •λ•(j-1)•τ Q i j •λ •(j-1) •τ .
As is evident by the above equations, the optimal allocation is now dependent on another chunk-dependent parameter, Q i j .

SIMULATIONS 4.1 Simulation setup

To validate our results, we perform simulations based on real traces for (i) mobility and (ii) content popularity:

• Mobility: We use the Cabspo ing trace [START_REF] Piorkowski | DAD data set ep /mobility[END_REF] to simulate the vehicle behaviour; this trace records the GPS coordinates for 531 taxis in San Francisco for more than 3 weeks with granularity of 1 minute. In order to improve the accuracy of our simulations, we increase the granularity to 10 seconds by linear interpolation. We extrapolate the mobility statistics (e.g., λ) from the analysis of the Cabspo ing trace to compute the optimal allocation. • Content popularity: We infer the number of requests per day from a database with statistics for 100.000 YouTube videos [START_REF] Ma Ia Zeni | YOUStatAnalyzer: a Tool for Analysing the Dynamics of YouTube Content Popularity[END_REF]. e database includes static (e.g., title, description, author, duration) and dynamic information (e.g., daily and cumulative views, shares, comments). Data is worldwide, and we scale it linearly according to the estimated population of the centre of San Francisco. We assume that each content is split into 10 chunks of equal size, and that the internal chunk popularity follows a Zipflike distribution [START_REF] Lim | Inter-Chunk Popularity-Based Edge-First Caching in Content-Centric Networking[END_REF]. We build a MATLAB simulator as follows: rst, we generate a set of requests, and we associate a random location (in GPS coordinates) to each one. e number of requests per content per day is given by the YouTube trace. en, we store chunks in vehicles according to chosen allocation policy. For each request, we simulate the playout of the video; the end user bu er will be opportunistically lled when the vehicular cloud can be contacted, according to the mobility provided by the Cabspo ing trace. e number of chunks downloaded per contact depends on the contact duration and on the distance between user and vehicle. In our simulations, we assume that end users can contact the vehicular cloud with either short (100 m) or long (200 m) range communications. e user abandons the playout of the video with some probability: speci cally, when a user watches a chunk, she decides to watch the following chunk with probability w or to abandon the playout with probability 1 -w.

In order to increase the number of simulations and to provide sensitivity analysis for content size and bu er capacity, we limit the number of content to 10.000. We scale down the vehicle storage capacity c to ensure that 0,1% of the total catalogue ts in each cache (i.e., 10 entire contents). We compare the following allocation policies: • Per Chunk Caching (PCC). is policy allocates chunks of popular content according to the model described in Section 3.1. • Generic Tra c (GT). is policy allocates videos optimally according to the Generic Tra c policy described in Section 3.2 of Vigneri et al. [START_REF] Vigneri | Streaming Content from a Vehicular Cloud[END_REF]. • Low Tra c (LT). is policy allocates videos optimally according to the Low Tra c policy described in Section 3.1 of Vigneri et al. [START_REF] Vigneri | Streaming Content from a Vehicular Cloud[END_REF].

Our main goal in this preliminary evaluation is to highlight the improvements, in terms of number of chunks o oaded, brought by caching per chunk compared to per content, in a relatively realistic scenario. We therefore focus on the simpler unlimited bandwidth policy. Once more, we stress that the actual contacts in the simulator do not have unlimited bandwidth, but only that our allocation policy is designed making this simplifying assumption. Nevertheless, even this suboptimal policy already brings considerable gains. Taking the limited bandwidth explicitly into account can provide additional gains, but requires a careful tuning of the p i j (z) function and is deferred to future work.

Performance evaluation

In Figure 1 we plot the percentage of chunks o oaded for di erent allocation policies when communication range is 100 m or 200 m. Speci cally, when fractional storage is allowed (PCC), 10% more tra c can be o oaded (from 35% to 45%), a relative improvent of around 30%. As already mentioned, this happens because later chunks have less probability to be watched which is not taken into account by LT and GT policies. Rather, PCC replaces some of these chunks, that are not likely to be watched, with some others. Such a replacement brings interesting o oading gains. What is more, the way content is allocated into vehicles (chunks of the same content in the same vehicle vs. chunks of the same content spread over all vehicles) can largely a ect the amount of data o oaded, and can be used by an operator to further increase performance. Because of the large number of requests in the period considered, the con dence interval is too small to be distinguishable and hence is ignored.

In Figure 2 we perform sensitivity analysis according to the probability of viewing the subsequent chunk when communication range is 200 m. We analyse the range 0, 80 -0, 95 (i.e., a video is entirely played out from 10 to 60 % of times). Similarly to the previous scenario, PCC provides a relative improvement of at least 30% (or 10% in absolute values) in all scenarios. What is more, the e ciency of the policy improves as the abandonment probability increases. Although this con rms the e ectiveness of our proposal, we believe that a ner per chunk policy (e.g., limited bandwidth with an appropriate function p i j (t )) would provide even larger gains. Interestingly, considerable gains are achieved with very reasonable storage capacities. Here the simulations are performed on a set of 10.000 contents, but in a scenario with a larger realistic catalogue (e.g., 1000 times larger), it seems doable to store 0,1 % of the catalogue. E.g., if one considers an entire Torrent or Net ix catalogue (∼3 PB), a vehicle cache of about 3 TB already su ces to o oad more than 40 % of the total tra c for long range communications (and 30%for short range).

CONCLUSION

In this paper, we have introduced a per chunk allocation policy for video streaming from a vehicular cloud. We have shown that the related optimization problem is hard, and we have solved two reasonable approximations that make di erent assumptions about the number of chunks that can be downloaded per contact. e simulations performed have con rmed that caching policies that di erentiate between chunks can o oad much more tra c, compare to policies that treat all chunks of the same content the same. A number of interesting problems remain open, such as the proper modeling of the per chunk download success probability, as well as the speci c allocation of chunks to vehicles, given that the number of replicas needed are known.

P 2 .

 2 Consider the in nite bandwidth scenario. e solution to the following optimization problem maximizes the expected number of bytes o oaded through the vehicular cloud: maximize

Figure 1 :

 1 Figure 1: Percentage of chunks o loaded through the vehicular cloud for short and long range communications.

Figure 2 :

 2 Figure 2: Percentage of chunks o loaded through the vehicular cloud according to the probability of watching the subsequent chunk.

  • Helper nodes (H ). Vehicles such as cars, buses, taxis, trucks, etc., where |H | = h. ese are used to store popular content and to serve user requests at low cost through a direct vehicle to mobile node link.

	• End user nodes (U). Mobile devices such as smartphones, tablets
	or netbooks. ese nodes request (non-live) video content for
	streaming to H and I nodes.
	Each video consists of a number of small chunks that are down-
	loaded into a U node's playout bu er in order and consumed for
	playout as follows:
	• Helper download. When a U node is in range of an H node
	that stores the requested chunks, the next chunks not yet in
	the playout bu er are downloaded at low cost. e number of
	chunks that can be downloaded during a contact depends on the
	download rate, the contact duration, etc.
	• Infrastructure download. When a U node is not in range of
	an H node that stores the requested content and its playout
	bu er is (almost) empty, new chunks are downloaded from the
	infrastructure at a mean rate r I until another H node storing
	the content is encountered. e communication between U and
	I nodes has a high cost in terms of energy consumption and
	bandwidth of the backhaul links [4].
	• Playout. Chunks in the playout bu er are consumed at a mean
	viewing playout rate r P . For simplicity, we assume that each
	chunk corresponds to a xed video duration of τ seconds, and
	has the same size in terms of bytes 2 .

Table 1 :

 1 Notation used in the paper.

	CONTROL VARIABLES
	x i	Number of replicas stored for content i
	CONTENT
	k	Number of content in the catalogue
	ϕ i j	Request rate for chunk j of content i
	s i	Number of chunks of content i
	c	Bu er size per vehicle
	MOBILITY
	λ	Mean inter-meeting rate between U and H nodes
	h	Number of vehicles
	CHUNK DOWNLOAD
	r H	Mean download rate from H nodes
	r I	Mean download rate from I nodes (equal to r P )

Note that this scenario does not include live content streaming which is not usually amenable to caching, and is o en optimized using multicast techniques.

is is in general not the case as the actual size depends on the compression factor, type of frame, etc. However, we are interested rst in an average case analysis and such di erences cancel themselves out when considering enough chunks.

Several studies have con rmed that simple statistical models (e.g., ARMA models) along with content type characteristics can help to have good estimation of the request rate, at least in the immediate future[START_REF] Lee | An Approach to Model and Predict the Popularity of Online Contents with Explanatory Factors[END_REF][START_REF] Szabo | Predicting the popularity of online content[END_REF].

In case of heterogeneous mobility, λ could be seen as the average among the various λ i j , which works well as a rst order approximation[START_REF] Sermpezis | Delay Analysis of Epidemic Schemes in Sparse and Dense Heterogeneous Contact Networks[END_REF].

e speci c allocation of chunks per vehicle is a di erent problem that is le as a future work.

We de ne feasible an allocation that satis es the individual capacity constraint of Eq. (2).

ACKNOWLEDGEMENT

is work was funded by the French Government (National Research Agency, ANR) through the "Investments for the Future" Program reference #ANR-11-LABX-0031-01.