Alpha Fair Coded Caching
Apostolos Destounis Mari Kobayashi Georgios Paschos Asma Ghorbel



Alpha Fair Coded Caching
    Apostolos Destounis^1,
		Mari Kobayashi^2, 
		Georgios Paschos ^1,
		Asma Ghorbel^2 
		

		^1 France Research Center, Huawei Technologies Co. Ltd., email: firstname.lastname@huawei.com
			
		
		
	^2Centrale-Supélec, 
		France, email: firstname.lastname@centralesupelec.fr
	

    
======================================================================================================================================================================================================================================================================================






The performance of existing coded caching schemes is  sensitive to worst channel quality, a problem which is exacerbated when communicating over fading channels.
In this paper we address this limitation in the following manner:  in short-term, we allow transmissions to subsets of users with good channel quality, avoiding users with fades, while in long-term we ensure fairness across the different users. 
Our online scheme combines (i) joint scheduling and power control for the broadcast channel with fading, and (ii) congestion control for ensuring the optimal long-term average performance.
We restrict the caching operations to the decentralized scheme of <cit.>, 
and subject to this restriction we prove that our scheme  has near-optimal overall performance with respect to the convex alpha-fairness coded caching optimization.
By tuning the coefficient  alpha, the operator can differentiate user performance with respect to  video delivery rates achievable  by coded caching.
 We demonstrate via simulations our scheme's  superiority  over legacy coded caching and  unicast opportunistic scheduling, which are identified as special cases of our general framework.


Broadcast channel, coded caching, fairness, Lyapunov optimization.
 




§ INTRODUCTION

A key challenge for the  future wireless networks is the increasing video traffic demand, which reached 70% of total mobile IP traffic in 2015 <cit.>.
Classical downlink systems cannot meet this demand since they have limited resource blocks, and therefore as the number of simultaneous video transfers  K increases,  the  per-video throughput  vanishes as 1/K.
Recently it was shown that scalable per-video throughput can be achieved if the communications are synergistically designed with caching at the receivers. 
Indeed, the recent  breakthrough of coded caching <cit.> has inspired a  rethinking of  wireless downlink. 
Different video sub-files are cached at the receivers, and video requests are served by coded multicasts. 

By careful selection of sub-file caching and exploitation of the  broadcast  wireless channel,   the transmitted signal is simultaneously
useful for decoding at users with  different  video requests. 
Although this scheme–theoretically proved to scale well–can potentially resolve the future downlink bottleneck, several limitations hinder its applicability in practical systems <cit.>. In this work, we take a closer look to the limitations that arise from the fact that coded caching was originally designed for a symmetric error-free shared link. 

If instead we consider a realistic model for the wireless channel, 
 we observe that a naive application of coded caching faces a short-term limitation: since the channel qualities of the users fluctuate over time and our transmissions need to reach all users, the transmissions need to be designed for  the worst channel quality. This is in stark contrast with standard  downlink techniques, like opportunistic scheduling <cit.>, which serve the user with the best instantaneous channel quality. 
Thus, a first challenge is to discover a way to allow coded caching technique to opportunistically exploit the fading of the wireless channel. 


Apart from the fast fading consideration, there is also a long-term limitation due to the network topology. The user locations might vary, which leads to consistently poor channel quality for the ill-positioned users. 
The classical coded caching scheme is designed to deliver 
equal video shares to all users,
which leads to ill-positioned users consuming most of the air time and hence driving the
overall system performance to low efficiency. In the literature, this problem has been resolved by the use of fairness among user throughputs <cit.>. 
By allowing poorly located users to receive less throughput than others, precious airtime is saved and the overall system performance is greatly increased. Since the sum throughput rate and equalitarian fairness are typically the two extreme cases, past works have proposed the use of alpha-fairness <cit.> which allows  to select the coefficient α and drive the system to any desirable  tradeoff point in between of the two extremes. 
Previously, the alpha-fair objectives have been studied in the context of (i) multiple user activations <cit.>, (ii) multiple antennas <cit.> and (iii) broadcast channels <cit.>. However, here the fairness problem is further complicated by the interplay between scheduling and the coded caching operation. In particular, we wish to shed light into the following questions: what is the right user grouping and how we should design the codewords to achieve our fairness objective while adapting to changing channel quality?


To address these questions, we study the content delivery over a realistic block-fading broadcast channel, where the channel quality varies across users and time. 
In this setting, 
we design a scheme that decouples transmissions from coding. In the transmission side, we select the multicast user set dynamically depending on the instantaneous channel quality and user urgency captured by queue lengths. In the coding side, we adapt the codeword construction of <cit.> depending on how fast the transmission side serves each user set. Combining with an appropriate congestion controller, we show that this approach yields our alpha-fair objective.
More specifically, our approaches and contributions are summarized below:


  1) We impose a novel queueing structure which decomposes the channel scheduling from the codeword construction. Although it is clear that the codeword construction needs to be adaptive to channel variation, our scheme ensures this through our backpressure that connects the user queues and the codeword queues. Hence, we are able to show that this decomposition is without loss of optimality.

  2) We then provide an online policy consisting of (i) admission control of new files into the system; (ii) combination of files to perform coded caching; (iii) scheduling and power control of codeword transmissions to subset of users on the wireless channel. We prove that 
the long-term video delivery rate vector achieved by our scheme is a near optimal solution to the alpha-fair optimization problem under the specific coded caching scheme <cit.>. 

  3) Through numerical examples, we demonstrate the superiority of our approach versus (a) opportunistic scheduling with unicast transmissions and classical network caching (storing a fraction of each video), (b) standard coded caching based on transmitting-to-all.





 §.§ Related work


Since coded caching was first proposed <cit.> and its potential was recognized by the community, 
substantial efforts have been devoted to quantify the gain in realistic scenarios, including decentralized
placement <cit.>, non-uniform popularities <cit.>, and device-to-device (D2D)  networks <cit.>.
A number of recent works replace the original perfect shared link with wireless channels <cit.>.
Commonly in the works with wireless channels, 
the performance of coded caching is limited by the user in the worst channel condition because the wireless multicast capacity is determined by the worst user <cit.>. This limitation of coded caching has been recently highlighted in  <cit.>, while similar conclusions and some directions are given in  <cit.>. Our work is the first to addresses this aspect by jointly designing the transmissions over the broadcast channel and scheduling appropriate subsets of users.


Most past works deal with offline caching in the sense that both cache placement and delivery phases are performed once and do not capture the random and asynchronous nature of video traffic. 
The papers <cit.> addressed partly the online nature by studying cache eviction strategies, and delay aspects. 
In this paper, we explore a different online aspect. Requests for video files arrive in an online fashion, and transmissions are scheduled over time-varying wireless channels.

Online transmission scheduling over wireless channels has been extensively studied in the context of opportunistic scheduling <cit.> and network utility maximization <cit.>. Prior works emphasize two fundamental aspects: (a) the balancing of user rates according to  fairness and efficiency considerations, and (b) the opportunistic exploitation of the time-varying fading channels.
Related to our work are the studies of wireless downlink with broadcast degraded channels; <cit.> gives a maxweight-type of policy and <cit.> provides a throughput optimal policy based on a fluid limit analysis.
Our work is the first to our knowledge that studies coded caching in this setting.
The new element in our study is the joint consideration of user scheduling with codeword construction for the coded caching delivery phase.
 






§ SYSTEM MODEL AND PROBLEM FORMULATION

We study a wireless downlink consisting of a base station and K users. 
The users are interested in downloading files over the wireless channel.



 §.§ Fair file delivery


The performance metric is the time average delivery rate of files to user k, denoted by r_k. Hence our objective is expressed with respect to the vector of delivery rates . 
We are interested in the fair file delivery problem:

    r^* =    max_r∈Λ∑_k=1^Kg(r_k),


where Λ denotes the set of all feasible delivery rate vectors–clarified in the following subsection–and the utility function corresponds to the alpha fair family of  concave functions obtained by choosing: 

    g(x) = (d+x)^1-α/1-α, α≠ 1
    log(1+x/d), α = 1



for some arbitrarily small d>0 (used to extend the domain of the functions to x=0).  Tuning the value of α changes the shape of the utility function and consequently drives the system performance r^* to different  points: (i) α=0 yields max sum delivery rate, (ii)  α→∞ yields max-min delivery rate <cit.>, (iii)   α = 1 yields proportionally fair delivery rate <cit.>.
Choosing α∈ (0,1) leads to a tradeoff between max sum and proportionally fair delivery rates.

The optimization  (<ref>)  is designed to allow us tweak the performance of the system;  we highlight its  importance by an example.
Suppose that for a 2-user system Λ is given by the convex set shown on figure <ref>.

Different boundary points are obtained as solutions to (<ref>).
If we choose α=0, the system is operated at the point that maximizes the sum r_1+r_2. The choice α→∞ leads to the maximum r such that r_1=r_2=r, while α=1 maximizes the sum of logarithms. 
The  operation point A is obtained when we always broadcast to all users at the weakest user rate and use <cit.> for coded caching transmissions.
Note that this results in a significant loss of efficiency due to the variations of the fading channel, and consequently A lies in the interior of Λ.
We may infer that the point α→∞ is obtained by avoiding transmissions to users with  instantaneous poor channel quality but still balancing their throughputs in the long run.




 §.§ Transmission model



To analyze the set of feasible rate vectors Λ  we need to zoom in the detailed model of transmissions.

Caching model.
There are N equally popular files W_1, …, W_N, each F bits long.
The files are available to the base station.  User k is equipped with cache memory Z_k of MF bits, where  M∈ [0,N].
Caching placement is performed during off-peak hour, and the goal is to fill the caches up to the memory constraint with selected bits.  To this end, we need to select K caching functions ϕ_k: _2^NF→_2^MF which map the files W_1, …, W_N into the cache contents 

    Z_k ϕ_k(W_1,…, W_N),   ∀ k=1,…,K.

The caching functions can be used to cache a few entire files, or a small fraction from each file, or even  coded combinations of subfiles <cit.>.
It is important to note that the caching functions are selected once, without knowledge of future requests, and are  fixed throughout our system operation.[A reasonable  extension is to enable  infrequent updates of the caching placement phase.]

Downlink channel model. We consider a standard block-fading broadcast channel, such that the channel state remains constant over a slot of T_ slot channel uses  and changes from one slot to another in an i.i.d. manner. 
The channel output of user k in any channel use of slot t is given by  

    _k(t)=√(h_k(t))(t)+_k(t),

where the channel input ∈^T_ slot is subject
to the power constraint [‖‖^2] ≤ PT_ slot; _k(t)∼_(0, _T_ slot) are additive white Gaussian noises with covariance matrix identity of size T_ slot, assumed independent of each other; {h_k(t)∈} are channel fading coefficients ∼β_k^2exp(1) independently distributed across time and users, with β_k denoting the path-loss parameter of user k. 

Encoding and transmissions.  The transmissions aim to contribute information towards the delivery of a specific vector of file requests (t), where d_k(t)∈{1, …, N} denotes 
the index of the requested file by user k in slot t. Here N is the video library size, typically in the order of 10K. The requests are generated randomly, and whenever a file is delivered to user k, the next request of this user will be for another randomly selected file. 

At each time slot, the base station observes the channel state (t)=(h_1(t), …,h_K(t))  and the request vector up to t, ^t, 
constructs a transmit symbol using the encoding function f_t:{1,..,N}^Kt×^K→^T_ slot. 
 
    (t) = f_t ( ^t,(t)),

 
  Finally, it transmits a codeword (t) for the T_ slot channel uses  over the fading broadcast channel in slot t . 
  The encoding function may be chosen at each slot  to contribute information to a selected subset of users 𝒥(t)⊆{1,…,K}. This allows several possibilities, e.g. to send more information to a small set of users with good instantaneous channel qualities, or less information to a large set that includes users with poor quality. 

Decoding.
At slot t, each user k observes the local cache contents Z_k and the sequence of channel outputs so far y_k(τ),  τ=1,…,t and employs a decoding function ξ_k to determine the decoded files.
Let D_k(t) denote the number of files decoded by user k after t slots.
The decoding function ξ_k is a mapping

  
    ξ_k: ^T_slott×^Kt×_2^FM×{1,..,N}^Kt→_2^FD_k(t).

The decoded files of user k at slot t are given by ξ_k(y_k^T_ slott, Z_k, ^t, ^t),
and depend on the channel outputs and states up to t, the local cache contents, and the requested files of all users up to t. 
A file is incorrectly decoded if it does not belongs to the set of requested files. The number of incorrectly decoded files are then given by |∪_t{ξ_k(t)}∖ d_k^t| and
the number of correctly decoded files at time t is: 

    C_k(t)= D_k(t)- |∪_t{ξ_k(t)}∖ d_k^t|



A rate vector =(r_1,…, r_K) is said to be feasible ∈Λ if there exist functions ([ϕ_k], [f_t], [ξ_k])  such that:




    r_k=lim sup_t→∞C_k(t)/t,


where the rate is measured in file/slot. 


In contrast to past works which study the performance of one-shot coded caching <cit.>, our rate metric measures the ability of the system to continuously deliver files to users.




 §.§ Code-constrained rate region

Finding the optimal policy is very complex. 
In this paper, we restrict the problem to specific class of policies given by the following mild assumptions: 

The admissible policies have the following characteristics: 


  * The caching placement and delivery follow the decentralized scheme <cit.>.

  * The users request distinct files, i.e., the ids of the requested files of any two users are different.


Since we restrict our action space, the delivery rate feasibility region, Λ^CC, of the class of policies Π^CC is  smaller than the one for the original problem Λ. However, these restrictions allow us to come up with a concrete solution approach. Note that the optimal cache and transmission design policy is already a very hard problem even in the simple case of broadcast transmissions with a fixed common rate, and the method in <cit.>,   <cit.>  are  practical approaches with good performance.  In addition, looking at demand IDs when combining files would be very complex and, because of the big library sizes, is not expected to bring substantial gains (it is improbable that two users will make request for the same file in close time instances).   







§ OFFLINE CODED CACHING


In this section we briefly review decentralized coded caching, first proposed in <cit.>, and used by all  admissible policies Π^CC.
We set m=M/N the normalized memory size. Under the memory constraint of MF bits, each user k independently caches a subset of mF bits of file i, chosen uniformly at random for i=1,…, N. By letting W_i| denote the sub-file of W_i stored exclusively in the cache memories of the user set , the cache memory Z_k of user k after decentralized placement is given by

    Z_k ={ W_i :    ∀⊆[K], ∀∋ k , ∀ i =1,…, N }.

The size of each sub-file measured in bits is given by  

    |W_i |= m^||(1-m)^K-||

as F→∞. The above completely determine the caching functions.

Once the requests of all users are revealed, the offline scheme proceeds to the delivery of the requested files (delivery phase). Assuming that user k requests file k, i.e. d_k =k, the server generates and conveys the following codeword simultaneously useful to the subset of users :  

    V_=⊕_k∈W_k|∖{k},

where ⊕ denotes the bit-wise XOR operation. The main idea here is to create a codeword useful to a subset of users by exploiting the receiver side information established during the placement phase. 
It is worth noticing that the coded delivery with XORs significantly reduces the number of transmissions. 
Compared to uncoded delivery, where the sub-files are sent sequentially and the number of transmissions are equal to ||×|W_k|∖{k}|, the coded delivery requires the transmission of |W_k|∖{k}|, yielding a reduction of a factor ||.
In a practical case of N>K, it has been proved that decentralized coded caching achieves the total number of transmissions, measured in the number of files, given by <cit.>

    T_ tot(K,m) = 1/m(1-m) {1-(1-m) ^K }.

On the other hand, in uncoded delivery, the number of transmissions is given by K(1-m) since it exploits only local caching gain at each user. For a system with K=30 users and normalized memory of m=1/3, the minimum transmissions required by uncoded delivery is 20 and that of decentralized coded caching is 2, yielding a gain of factor 10.  

 In order to further illustrate the placement and delivery of decentralized coded caching,  we provide an three-user example. 

For the case of K=3 users in Fig.<ref>, let us assume that user 1, 2, 3, requests file A, B, C, respectively.  
After the placement phase, a given file A will be partitioned into 8 subfiles.



Codewords to be sent are the following


  * A_∅, B_∅ and C_∅ to user 1, 2 and 3 respectively.  

  * A_ 2⊕ B_ 1 is intended to users {1,2}. Once received, user 1 decodes A_ 2 by combining the received codeword with B_ 1 given in its cache. Similarly user 2 decodes B_ 1. The same approach holds for codeword B_ 3⊕ C_ 2 to users {2,3} and codeword A_ 3⊕ C_ 1 to users {1,3}

  * A_ 23⊕ B_ 13⊕ C_ 12 is intended users 1,2,3. User 1 can decode A_ 23 by combining the received codeword with {B_ 13,C_ 12} given in its cache. The same approach is used for user 2, 3 to decode B_ 13, C_ 12 respectively.  
     






§ BROADCASTING PRIVATE AND COMMON MESSAGES



In this section, we address the question on how the transmitter shall convey private and multiple common messages, each intended to a subset of users, while opportunistically exploiting the underlying wireless channel.  We start by remarking that the channel in (<ref>) for a given channel realization  corresponds to the Gaussian degraded broadcast channel. Without loss of generality, let us assume h_1≥…≥ h_K so that the following Markov chain holds.


 
    X ↔ Y_1  ↔…↔  Y_K.



The capacity region of the degraded broadcast channel for K private messages and a common message is well-known <cit.>.
 In this section, we consider a more general setup where the transmitter wishes to convey 
2^K-1 mutually independent messages, denoted by {M_}, where M_ denotes the message intended to the users in subset ⊆{1,…, K}. Each user k must decode all messages {M_} for ∋ k. By letting R_ denote the multicast rate of the message M_, we say that the rate-tuple ∈_+^2^K-1 is achievable if there exists encoding and decoding functions which ensure the reliability and the rate condition. The capacity region is defined as the supremum of the achievable rate-tuple, where the rate is measured in bit/channel use. 

The capacity region Γ() of a K-user degraded Gaussian broadcast channel with fading gains h_1 ≥…≥ h_K and 2^K-1 independent messages {M_} is given by 

    R_1    ≤log(1+ h_1α_1 P) 
    ∑_⊆{1,…, k}: k∈ R_   ≤log1+ h_k ∑_j=1^kα_j P/1+ h_k∑_j=1^k-1α_j P    k=2, …, K

for non-negative variables {α_k} such that ∑_k=1^K α_k ≤ 1. 


 Please refer to Appendix <ref> for the proof.



The achievability builds on superposition coding at the transmitter and successive interference cancellation at receivers. For K=3, the transmit signal is simply given by 

    x = x_1 + x_2 + x_3 + x_12 + x_13+ x_123

where {x_} are mutually independent Gaussian distributed random variables satisfying the power constraint and x_ denotes the signal corresponding to the message M_ intended to the subset ⊆{1,2,3}.   
User 3 (the weakest user) decodes M̃_3 ={M_3, M_13, M_23, M_123} by treating all the other messages as noise. User 2 decodes first the messages M̃_3 and then jointly decodes M̃_2 ={M_2, M_12}. Finally, user 1 (the strongest user) successively decodes M̃_3, M̃_2 and, finally, M_1. 

Later in our online coded caching scheme we will need the capacity region Γ(), and more specifically, we will need to characterize its boundary. 
To this end,   

it suffices to  consider the weighted sum rate maximization:

    max_∈Γ()∑_: ⊆{1,…, K}θ_ r_.

We first simplify the problem using the following theorem.


The weighted sum rate maximization with 2^K-1 variables in (<ref>) reduces to a simpler problem with K variables, given by 

    f() = ∑_k=1^K θ̃_k log1+h_k ∑_j=1^kα_j P/1+ h_k∑_j=1^k-1α_j P.

where θ̃_k denotes the largest weight for user k 

    θ̃_k=max_: k∈⊆{1,…, k}θ_.



The proof builds on the simple structure of the capacity region. We first remark that for a given power allocation of other users, user k sees 2^k-1 messages {W_} for all  such that k∈⊆{1,…, k} with the equal channel gain. For a given set of {α_j}_j=1^k-1, the capacity region of these messages is a simple hyperplane 
characterized by 2^k-1 vertices C_k _i for i=1, …, 2^k-1, where C_k is the sum rate of user k in the RHS of (<ref>) and _i is a vector with one for the i-th entry and zero for the others. Therefore, the weighted sum rate seen is maximized for user k by selecting the vertex corresponding to the largest weight, denoted by θ̃. This holds for any k. 


We provide an efficient algorithm to solve this power allocation problem as a special case of the parallel Gaussian broadcast channel studied in <cit.>. Following <cit.>, we define the rate utility function for user k given by 

    u_k(z)= θ̃_k/1/h_k+z-λ

where λ is a Lagrangian multiplier. The optimal solution corresponds to selecting 
the user with the maximum rate utility at each z and the resulting power allocation for user k is 

    α^*_k = { z:   [max_j u_j(z) ]_+ = u_k(z)  }/P

with λ satisfying 

    P= [ max_k θ̃_k/λ -1/h_k]_+.





§ PROPOSED ONLINE DELIVERY SCHEME

This section presents first the queued delivery network and its feasible rate region of arrival rates, then describes the proposed
control policy. 



 §.§ Solution plan


At each time slot t, the controller admits a_k(t) files to be delivered to user k, and hence a_k(t) is a control variable.[We note that random file arrivals can be directly captured  with the addition of an extra queue <cit.>, which  we avoid  to simplify exposition.]
As our model dictates, the  succession of requested files for user k is determined uniformly at random.


Queueing model.
The base station organizes the information into the following types of queues: 

	
  * User queues  to store admitted files, one for each user. The buffer size of queue k is denoted by S_k(t) and expressed in number of files. 
	
  * Codeword queues to store codewords to be multicast. There is one codeword queue for each subset of users ⊆{1, …, K}. The size of codeword queue  is denoted by Q_(t) and expressed in bits.
 
A queueing policy π performs the following operations: (i) decides how many files to admit into  the user queues S_k(t) in the form of (a_k(t)) variables, (ii) then  it decides how to combine together files from different user queues to be encoded into the form of multiple codewords which represent the required broadcast transmissions for the reception of this file–these codewords are stored in the appropriate codeword queues Q_(t), (iii) and last it decides the encoding function f_t.
(ii) and (iii) are further clarified in the next section.



	A queue S(t) is said to be (strongly) stable if
	

	
    lim sup_T→∞1/T∑_t=0^T-1𝔼[S(t)] < ∞.

	A queueing system is said to be stable if all its queues are stable. Moreover, the stability region of a system is the set of all arrival rates such that the system is stable.   

The above definition implies that the average delay of each job in the queue is finite. 

In our problem,  if we develop a policy that keeps user queues (t) stable, then all admitted files will, at some point, be combined into codewords. If in addition codeword queues (t) are stable, then all generated codewords will reach their destinations, meaning that all receivers will be able to decode the admitted files that they requested. 

The region of all feasible delivery rates Λ is the same as the stability region of the system (i.e. the set of all demand arrival rates for which there exists a policy that stabilizes the queueing system). 


Let a_k = lim sup_t→∞1/t∑_t=0^t-1𝔼[a_k(t)],
denote the time average number of admitted files for user k.  Lemma <ref> implies the following Corollary. 

Solving  (<ref>) is equivalent to finding a policy π such that 

	

    a^π =   ∑_k=1^Kg_k(a_k)
    s.t.     the system is stable.



See Appendix <ref>

	


 §.§ Feasible Region

Contrary to the offline coded caching in <cit.>, we propose an online delivery scheme consisting of the following three blocks. Each block is operated at each slot. 



  * Admission control:
At the beginning of each slot, the controller decides how many requests for each user, a_k(t) should be pulled into the system from the infinite reservoir.



  * Routing:
The cumulative accepted files for user k are stored in the admitted demand queue whose size is given by S_k(t) for k=1,…, K. The server decides the combinations of files to perform coded caching. The decision at slot t for a subset of users ⊆{1,..,K}, denoted by σ_(t)∈{0,1,…,σ_max}, refers to the number of combined requests for this subset of users. It is worth noticing that offline coded caching lets σ_ = 1 for ={1,…, K} and zero for all the other subsets.  
The size of the queue S_k evolves as: 

    S_k(t+1) = [S_k(t) - ∑_: k∈σ_(t)]^+ + a_k(t)

If σ_(t)> 0, the server creates codewords by applying offline coded caching explained in Section [] for this subset of users 
as a function of the cache contents {Z_j: j∈}. 
  

  * Scheduling:
  The codewords intended to the subset  of users are stored in codeword queue whose size is given by Q_(t) for ⊆{1,…, K}. Given the instantaneous channel realization (t) and the queue state {Q_(t)}, the server performs scheduling and rate allocation. Namely, at slot t, it determines the number μ_(t) of bits per channel use to be transmitted for the users in subset . By letting b_, denote the number of bits generated for codeword queue ⊆ when offline coded caching
  is performed to the users in , codeword queue  evolves as 
   
    Q_(t+1) =  [Q_(t) - T_ slotμ_(t)]^+  + ∑_:⊆b_,σ_(t)

   where b_,=m^||(1-m)^||-||-1.
   

In order determine our proposed policy, namely the set of decisions {(t), (t),(t)} at each slot t,  we first characterize the feasible region Λ as a set of arrival rates . We let π_𝐡 denote the probability that the channel state at slot t is ∈ where  is the set of all possible channel states. We let Γ() denote the capacity region for a fixed channel state 𝐡. Then we have the following 

	A demand rate vector is feasible, i.e. ∈Λ^CC, if and only if there exist ∈∑_𝐡∈ℋπ_𝐡Γ(𝐡), σ̅_∈[0,σ_max], ∀⊆{1,…, K} such that: 
	
    ∑_: k∈σ̅_≥a̅_k, ∀ k =1,…,K 
     
    	T_slotμ_≥∑_: ⊆ b_, σ̅_, 
    	∀∈ 2^
    .


Constraint (<ref>) says that the service rate at which admitted demands are combined to form codewords is greater than the arrival rate, while (<ref>) implies that the long-term average transmission rate μ_ for the subset  of users should be higher than the rate at which bits of generated codewords for this group arrive. In terms of the queueing system defined, these constraints impose that the service rates of each queue should be greater than their arrival rates, thus rendering them stable.   

Theorem <ref> implies that the set of feasible average delivery rates is a convex set. 



 §.§ Admission Control and Routing


In order to perform the utility maximization (<ref>), we need to introduce one more set of queues. These queues are virtual, in the sense that they do not hold actual file demands or bits, but are merely counters to drive the control policy. Each user k is associated with a queue U_k(t) which evolves as follows: 

    U_k(t+1) = [U_k(t) - a_k(t)]^+ + γ_k(t)


where γ_k(t) represents the arrival process to the virtual queue and is given by 

    γ_k(t) = max_0≤ x≤γ_k,max[Vg_k(x) - U_k(t)x]

In the above, V>0 is a parameter that controls the utility-delay tradeoff achieved by the algorithm (see Theorem <ref>). 

The general intuition here is as follows: Observe that the number a_k(t) of admitted demands is the service rate for the virtual queues U_k(t).  The control algorithm actually seeks to optimize the time average of the virtual arrivals γ_k(t). However, since U_k(t) is stable, its service rate, which is the actual admission rate, will be greater than the rate of the virtual arrivals, therefore giving the same optimizer. Stability of all other queues will guarantee that admitted files will be actually delivered to the users. 

We present our on-off policy for admission control and routing.  For every user k, admission control chooses a_k(t) demands given by 

    a_k(t) = γ_k, max{U_k(t) ≥ S_k(t) }


For every subset ⊆{1,…, K}, routing combines σ_(t) demands of users in  given by

    σ_(t) = σ_max{∑_k∈S_k(t) > ∑_: ⊆b_, /F^2 Q_(t)  }
    .




 §.§ Scheduling and Transmission

In order to stabilize all codeword queues, the scheduling and resource allocation explicitly solve the following weighted sum rate 
maximization at each slot t where the weight of the subset  corresponds to the queue length of Q_ 

    (t) = max_∈Γ((t))∑_⊆{1, …, K} Q_(t)r_
    .

We propose to apply the power allocation algorithm in Section <ref> to solve the above problem by sorting users in a decreasing order of channel gains and treating Q_(t) as θ_.  
In adition, we assume that the number of channel uses in one coherence block is large enough such that the decoding error from choosing channel  codes with rate (t) is very small. In this case, no feedback from the receivers is given. 



 §.§ Example
 
We conclude this section by providing an example of our proposed online delivery network for K=3 users as illustrated in Fig. <ref>.

 At slot t the server decides to combine W_1 requested by user 2 with W_8 requested by user 2 and  to process W_4 requested by user 1 uncoded. Therefore σ_{1,2}(t)=σ_{1}(t)=1 and σ_(t)=0 otherwise. Given this codeword construction, codeword queues have inputs as described in Table I.
 
In addition, data from queues Q_{2}(t), Q_{2.3}(t) are transmitted.  




§ PERFORMANCE ANALYSIS

In thi section, we present the main result of the paper, that our proposed online algorithm leads to close to optimal performance for all policies in the class Π^CC:


	Let r̅^π_k the mean time-average delivery rate for user k  achieved by the proposed policy. Then 
	
    ∑_k=1^Kg_k(r̅^π_k) ≥max_∈Λ^CC∑_k=1^Kg_k(r̅_k) - 1/V
    lim sup_T→∞1/T∑_t=0^T-1𝔼{Q̂(t)}  = V,

where Q̂(t) is the sum of all queue lengths at the beginning of time slot t, thus a measure of the mean delay of file delivery. 

The above theorem states that, by tuning the constant V, the utility resulting from our online policy can be arbitrarily close to the optimal one, where there is a tradeoff between the guaranteed optimality gap 1/V and the upper bound on the total buffer length V.

For proving the Theorem, we use the Lyapunov function 

    L(t) = 1/2(∑_k=1^KU_k^2(t) + S_k^2(t) + ∑_∈ 2^1/F^2Q_^2(t))

and specifically the related drift-plus-penalty quantity, defined as: 𝔼{L(t+1) - L(t)| 𝐒(t), 𝐐(t), 𝐔(t)} - V𝔼{∑_k=1^Kg(γ_k(t))|𝐒(t), 𝐐(t), 𝐔(t) }. The proposed algorithm is such that it minimizes (a bound on) this quantity. The main idea is to use this fact in order to compare the evolution of the drift-plus-penalty under our policy and two "static" policies, that is policies that take random actions (admissions, demand combinations and wireless transmissions), drawn from a specific distribution, based only on the channel realizations (and knowledge of the channel statistics). We can prove from Theorem 4 that these policies can attain every feasible delivery rate. The first static policy is one such that it achieves the stability of the system for  an arrival rate vector ' such that '+δ∈∂Λ^CC. Comparing with our policy, we deduce strong stability of all queues and the bounds on the queue lengths by using a Foster-Lyapunov type of criterion. In order to prove near-optimality, we consider a static policy that admits file requests at rates ^* = max_∑_kg_k(a_k) and keeps the queues stable in a weaker sense (since the arrival rate is now in the boundary Λ^CC). By comparing the drift-plus-penalty quantities and using telescopic sums and Jensen's inequality on the time average utilities, we obtain the near-optimality of out proposed policy.  

The full proof is in Appendix <ref>.  






§ NUMERICAL EXAMPLES


In this section, we compare our proposed delivery scheme with the following two other schemes, all building on decentralized cache placement in (<ref>) and (<ref>). 



  * Unicast opportunistic
scheduling: for any request, the server sends the remaining (1-m)F bits to the corresponding user without combining any files. Here we only exploit the local caching gain. In each slot the serve sends with full power to   user



    k^*(t)=max_klog( 1+h_k(t)P) / T_k(t) ^α,

 where T_k(t)=∑_1≤τ≤ t-1μ_k(τ)/(t-1) is the empirical average rate for user k up to slot t. 


  * Standard coded caching: we use decentralized coded caching among all K users. For the delivery, non-opportunistic TDMA transmission is used. The server sends sequentially codewords V_ to the subset of users  at the weakest user rate among : 



    μ_(t)=log( 1+Pmin_k∈(h_k(t))) .
Once the server has sent codewords {V_}_∅≠⊆{1,..,K}, every user is able to decode one file. Then the process is repeated for all the demands. 


We consider the system with  normalized memory of m=0.6, power constraint P=10dB, file size F=10^3 bits and number of channel uses per slot T_ slot=10^2. We divide users into two classes of K/2 users each: strong users with β_k=1 and weak users with β_k=0.2.

We compare the three algorithms for the cases where the objective of the system is sum rate maximization (α=0) and proportional fairness (α=1). The results are depicted in Fig. <ref> and  <ref>, respectively. 
 


   

Regarding the sum rate objective, standard coded caching performs very poorly, indicative of the adverse effect of users with bad channel quality. It is notable that our proposed scheme outperforms the unicast opportunistic scheme, which maximizes the sum rate if only private information packets are to be conveyed. The relative merit of our scheme increases as the number of users grows. This can be attributed to the fact that our scheme can exploit any available multicast opportunities. Our result here implies that, in realistic wireless systems, coded caching can indeed provide a significant throughput increase when an appropriate joint design of routing and opportunistic transmission is used. 

Regarding the proportional fair objective, we can see that the average sum utility increases with a system dimension for three schemes although our proposed scheme provides a  gain compared to the two others. 





§ CONCLUSIONS

We provided an algorithm to solve the problem of ensuring fairness in the long term delivery rates in wireless systems employing decentralized coded caching. Our results imply that appropriately combining the  opportunism arising from the fading channels with the multicasting opportunities that arise from coded caching can mitigate the harmful impact of users with bad channel conditions in standard coded caching schemes and provide significant increase in the performance of the system. 







§ PROOF OF THEOREM <REF>




 §.§ Converse


We provide the converse proof for K=3 and the general case K>3 follows readily.
Notice that the channel output of user k in (<ref>) for n channel use can be equivalently written as 

    _k=+_k,

where _k=_k/√((h_k))∼_(0, N_k_n)  for N_k=1/h_k and _n identity matrix of size n. Since N_1≤ N_2≤ N_3, we set M̃_k=∪_k∈⊆[k] M_ the message that must be decoded by user k (user k decodes all bits that user k'≥ k decodes) at rate R̃_k. More explicitly, M̃_1={M_1}, M̃_2={M_2,M_12}, M̃_3={M_3,M_13,M_23,M_123}.
By Fano's inequality, we have 

    nH(M̃_1)   ≤ I(M̃_1;Y_1M̃_2,M̃_3)
    
    		nH(M̃_2)   ≤ I(M̃_2;Y_2M̃_3)
    
    		nH(M̃_3)   ≤ I(M̃_3;Y_3).

Consider 

    I(M̃_3;Y_3)=H(Y_3)-H(Y_3M̃_3).

Since nlog( 2π eN_3)=H(Y_3M̃_3,X) ≤ H(Y_3M̃_3)≤ H(Y_3)≤ nlog( 2π e(P+N_3)), there exist 0≤α_3≤ 1 such that 

    H(Y_3M̃_3)=nlog( 2π e((1-α_3)P+N_3)).

Using (<ref>) and (<ref>) we obtain

    I(M̃_3;Y_3)
       = H(Y_3)-H(Y_3M̃_3)
       ≤ nlog( 2π e(P+N_3))-nlog( 2π e((1-α_3)P+N_3))
       =nlog(N_3+P/N_3+(1-α_3)P).



Next consider 

    I(M̃_2;Y_2M̃_3)=H(Y_2M̃_3)-H(Y_2M̃_2,M̃_3).

Using the conditional entropy power inequality in <cit.> , we have

    H(Y_3M̃_3)   =H(Y_2+n_3-n_2M̃_3)
       ≥ nlog(2^2H(Y_2M̃_3)/n+2^2H(n_3-n_2M̃_3)/n)
       = nlog(2^2H(Y_2M̃_3)/n+2π e(N_3-N_2))

(<ref>) and (<ref>) imply 

    nlog( 2π e((1-α_3)P+N_3))
       ≥ nlog(2^2H(Y_2M̃_3)/n+2π e(N_3-N_2))

equivalent to

    H(Y_2M̃_3)   ≤ nlog(2π e((1-α_3)P+N_2)).

Since nlog( 2π eN_2)=H(Y_2M̃_2,M̃_3,X)≤ H(Y_2M̃_2,M̃_3)≤ H(Y_2M̃_3), there exists α_2 such that 0≤1-α_2-α_3≤ 1-α_3 and 

    H(Y_2M̃_2,M̃_3)=nlog(2π e((1-α_2-α_3)P+N_2)).

Using (<ref>), (<ref>) and (<ref>) it follows

    I(M̃_2,M̃_3;Y_2)   =H(Y_2M̃_3)-H(Y_2M̃_2,M̃_3)
       ≤ nlog(2π e((1-α_3)P+N_2))
    -nlog(2π e((1-α_2-α_3)P+N_2))
       =nlog(N_2+(1-α_3)P/(1-α_2-α_3)P+N_2).



Last we consider

    I(M̃_1;Y_1M̃_2,M̃_3)
       =H(Y_1M̃_2,M̃_3)-H(Y_1M̃_1, M̃_2,M̃_3)
       =H(Y_1M̃_2,M̃_3)-H(Y_1M̃_1, M̃_2,M̃_3, X)
       =H(Y_1M̃_2,M̃_3)-H(Y_1  X)
       =H(Y_1M̃_2,M̃_3)-nlog( 2π eN_1)

Using the conditional entropy power inequality in <cit.> , we have

    H(Y_2M̃_2, M̃_3)
       =H(Y_1+n_2-n_1M̃_2,M̃_3)
       ≥ nlog(2^2H(Y_1M̃_2,M̃_3)/n+2^2H(n_2-n_1M̃_2,M̃_3)/n)
       = nlog(2^2H(Y_1M̃_2,M̃_3)/n+2π e(N_2-N_1))


(<ref>) and (<ref>) imply 

    nlog(2π e((1-α_2-α_3)P+N_2))
       ≥ nlog(2^2H(Y_1M̃_2,M̃_3)/n+2π e(N_2-N_1))

equivalent to

    H(Y_1M̃_2,M̃_3)   ≤ nlog(2π e((1-α_2-α_3)P+N_1)).

Let α_1=1-α_2-α_3. Combining the last inequality with (<ref>) we obtain 

    I(M̃_1;Y_1M̃_2,M̃_3)≤ nlog( N_1+α_1P/N_1).

From (<ref>), (<ref>), (<ref>) and (<ref>), it readily follows that ∃ 0≤α_1,α_2,α_3≤1 such that α_1+α_2+α_3=1 and 


    H(M̃_1)   ≤log(1+ α_1P/N_1),
    
    		H(M̃_2)   ≤log(1+α_2P/N_2+α_1P),
    
    		H(M̃_3)   ≤log(1+α_3P/N_3+(α_1+α_2)P).

By replacing H(M̃_k) with ∑_k∈⊆[k]R_ and N_k with 1/h_k we obtain the result

    R_1   ≤log( 1+h_1α_1P)
    
    		R_2+R_12   ≤log(1+h_2(α_1+α_2)P/1+h_2α_1P)
    
    		R_3+R_13+R_23+R_123   ≤log(1+h_3P/1+h_3(α_1+α_2)P),





 §.§ Achievability
 

Superposition coding achieves the upper bound. For 1≤ k≤3, generate random sequences u^n_k(m_k), m_k∈[1:2^nR̃_k] each i.i.d. _(0, α_kP). To transmit a triple message (m_1,m_2,m_3) the encoder set X=u^n_1(m_1)+u^n_2(m_2)+u^n_3(m_3).
For decoding:

	
  * Receiver 3 recover m_3 from Y_3=u^n_3(m_3)+( u^n_1(m_1)+u^n_2(m_2)+n_3) by considering u^n_1(m_1)+u^n_2(m_2) as noise. The probability of error tends to zero as n→∞ if R̃_3≤log( 1+α_3P/N_3+(α_1+α_2)P).
	
  * Receiver 2 uses successive cancellation. First, it decodes m_3 from Y_2=u^n_3(m_3)+( u^n_1(m_1)+u^n_2(m_2)+n_2) by considering u^n_1(m_1)+u^n_2(m_2) as noise. The probability of error tends to zero as n→∞ if R̃_3≤log(1+ α_3P/N_2+(α_1+α_2)P). Since N_2≤ N_3 and R̃_3≤log(1+α_3P/N_3+(α_1+α_2)P), the later condition is satisfied. Second, it subtracts off u^n_3(m_3) and recover u^n_2(m_2) from Ỹ2=u^n_2(m_2)+( u^n_1(m_1)+n_2) by treating  u^n_1(m_1) as noise. The probability of error tends to zero as n→∞ if R̃_2≤log(1+α_2P/N_2+α_1P).
	
  * Receiver 1 uses successive cancellation twice. First, it decodes m_3 from Y_1=u^n_3(m_3)+( u^n_1(m_1)+u^n_2(m_2)+n_1) by considering u^n_1(m_1)+u^n_2(m_2) as noise. The probability of error tends to zero as n→∞ if R̃_3≤log(1+α_3P/N_1+(α_1+α_2)P). Since N_1≤ N_3 and R̃_3≤log(1+α_3P/N_3+(α_1+α_2)P), the later condition is satisfied. Second, it subtracts off u^n_3(m_3) and decodes u^n_2(m_2) by treating  u^n_1(m_1) as noise. The probability of error tends to zero as n→∞ if R̃_2≤log(1+α_2P/N_1+α_1P). Since N_1≤ N_2 and R̃_2≤log(1+α_2P/N_2+α_1P), the later condition is satisfied. Last, it subtracts off u^n_2(m_2) and recover  u^n_1(m_1). The probability of error tends to zero as n→∞ if R̃_1≤log(1+α_1P/N_1). 




§ PROOF OF LEMMA <REF>



Denote A_k(t) the number of files that have been admitted to the system for user k up to slot t. Also, note that due to our restriction on the class of policies Π^CC and our assumption about long enough blocklengths, there are no errors in decoding the files, therefore the number of files correctly decoded for user k till slot t is D_k(t). Since D_k(t)≤ A_k(t), ∀ t≥ 0, ∀ k=1,..,K, if suffices to show that for every arrival rate vector ∈Λ^CC, there exists a policy in Π^CC for which the delivery rate vector is =. 

We shall deal only with the interior of Λ^CC (arrival rates at the boundaries of stability region are exceptional cases). Take any arrival rate vector ∈ Int(Λ^CC). From <cit.> it follows that for any there exists a randomized demand combination and transmission policy π^RAND, the probabilities of which depending only on the channel state realization each slot, for which the system is strongly stable. In addition, any arrival rate vector can be constructed via a randomized admission policy. Since the channels are i.i.d. random with a finite state space and queues are measured in files and bits, the system now evolves as a discrete time Markov chain (𝐒(t), 𝐐(t), 𝐇(t)), which can be checked that is aperiodic, irreducible ad with a single communicating class. In that case, strong stability means that the Markov chain is ergodic with finite mean. 

Further, this means that the system reaches to the set of states where all queues are zero infinitely often. Let T[n] be the number of timeslots between the n-th and (n+1)-th visit to this set (we make the convention that T[0] is the time slot that this state is reached for the first time). In addition, let Â_k[n], D̂_k[n] be the number of demands that arrived and were delivered in this frame, respectively. Then, since within this frame the queues start and end empty, we have 
    [Â_k[n] = D̂_k[n], ∀ n, ∀ k.


In addition since the Markov chain is ergodic,  

    a̅_k = lim_t→∞A(t)/t = lim_N→∞∑_n=0^NÂ_k[n]/∑_n=0^NT[n]

and 

    r̅_k = lim_t→∞D(t)/t = lim_N→∞∑_n=0^ND̂_k[n]/∑_n=0^NT[n]


Combining the three expressions, = thus the result follows. 



§ PROOF OF THEOREM <REF>




From Lemma <ref> and Corollary <ref>, it suffices to prove that under the online policy the queues are strongly stable and the resulting time average admission rates maximize the desired utility function subject to minimum rate constraints. 

We first look at policies that take random decisions based only on the channel realizations. Since the  feasibility region Λ^CC is a convex set (see Theorem ), any point in it can be achieved by properly time-sharing over the possible control decisions. We focus on two such policies, one that achieves the optimal utility and another on that achieves (i.e. admits and stabilizes the system for that) a rate vector in th δ- interior of Λ^CC. We then have the following Lemmas:  

 Define a policy π^*∈Π^CC that in each slot where the channel states are 𝐡 works as follows:  (i) it pulls random user demands with mean a̅_k^*, and it gives the virtual queues arrivals with mean γ̅_k = a̅_k^* as well (ii) the number of combinations for subset  is a random variable with mean σ̅^*_ and uniformly bounded by σ_max, (iii) selects one out of K+1 suitably defined rate vectors μ^𝐥∈Γ(), l=1,..,K+1 with probability ψ_l,. The parameters above are selected such that they solve the following problem: 
	
    max_   ∑_k=1^Kg_k(a̅_k^*)
    s.t.     ∑_: k∈σ̅_≥a̅_k^*, ∀ k∈{1,..,K}
       ∑_: ⊆b_, σ̅_≥∑_π_∑_l=1^K+1ψ_l, μ^l_(), ∀∈ 2^

	Then, π^* results in the optimal delivery rate vector (when all possible policies are restricted to set Π). 	
  



 Define a policy π^δ∈Π^CC that in each slot where the channel states are 𝐡 works as follows:  (i) it pulls random user demands with mean a̅_k^δ such that (+δ)∈Π^CC, and gives the virtual queues random arrivals with mean γ̅_k ≤ + 
	ϵ' for some ϵ'>0 (ii) the number of combinations for subset  is a random variable with mean σ̅^δ_ and uniformly bounded by σ_max, (iii) selects one out of K+1 suitably defined rate vectors μ^𝐥∈Γ(), l=1,..,K+1 with probability ψ^δ_l,. The parameters above are selected such that: 
	
    ∑_: k∈σ̅^̅δ̅_≥ϵ + a̅_k^δ, ∀ k∈{1,..,K}
       ∑_: ⊆b_, σ̅^δ_≥ϵ + ∑_π_∑_l=1^K+1ψ'_l, μ^l_(), ∀∈ 2^

	for some appropriate ϵ < δ. Then, the system under π^δ has mean incoming rates of ^δ and is strongly stable. 
  


The proof of the performance of our proposed policy is based on applying Lyapunov optimization theory <cit.> with the following as Lyapunov function

    L()= L(𝐒, 𝐐, 𝐔) = 1/2(∑_k=1^KU_k^2(t) + S_k^2(t) + ∑_∈ 2^Q_^2(t)/F^2)
    .

Defining its drift as 

    Δ L(𝐙) = 𝔼{L(𝐙(t+1))-L(𝐙(t))|𝐙(t)=𝐙}
, using the queue evolution equations and the fact that ([x]^+)^2≤ x^2, we have 

    Δ L(𝐙(t)) ≤ B    + ∑_∈ 2^Q_(t)/F^2𝔼{∑_: ⊇b_,σ_(t) - μ_(t)}
        + ∑_k=1^KS_k(t)𝔼{a_k(t) - ∑_: k∈σ_(t)}
        + ∑_k=1^KU_k(t)𝔼{γ_k(t) - a_k(t)}  
    ,

where B<∞ is a constant that depends only on the parameters of the system. Adding the quantity -V∑_k=1^K𝔼{g_k(γ_k(t))} to both hands of (<ref>) and rearranging the right hand side, we have 

    Δ L(𝐙(t)) - V∑_k=1^K𝔼{g_k(γ_k(t))}≤
     B   +∑_k=1^K𝔼{-Vg_k(γ_k(t)) + γ_k(t)U_k(t))}
       +∑_𝔼{σ_(t)}(∑_:⊆Q_(t)/F^2b_, - ∑_k∈S_k(t)) 
        + ∑_k=1^K(S_k(t) -  U_k(t))𝔼{a_k(t)}
       -∑_Q_(t)/F^2𝔼{μ_(t)}
 

Now observe that the control algorithm minimizes right hand side of (<ref>) given the channel state (t) (for any channel state). Therefore, taking expectations over the channel state distributions, for every vectors ∈ [1,γ_max]^K, γ̅∈ [1,γ_max]^K, σ̅∈ Conv({0,..,σ_max}^M),  μ̅∈∑_∈ℋπ_Γ() it holds that 

    Δ L(𝐙(t)) - V∑_k=1^K𝔼{g_k(γ^π_k(t))}≤
     
    B   - V∑_k=1^Kg_k(γ̅_k)  + ∑_k=1^KU_k(t)(γ̅_k - a̅_k)
       +∑_k=1^KS_k(t)(a̅_k -∑_ :k∈σ̅_)
        + ∑_Q_(t)/F^2(∑_ :⊆b_,σ̅_ - μ̅_)

We will use (<ref>) to compare our policy with the static policies defined in Lemmas <ref>, <ref>.  More specifically, replacing the time averages we get from the static stabilizing policy π^δ of Lemma <ref> for some δ>0, we get that thre exist ϵ >0 such that 

    Δ L(𝐙(t)) ≤ B     + V∑_k=1^K𝔼{g_k(a^π_k(t))}- V∑_k=1^Kg_k(a̅_k^δ) 
       -ϵ(∑_k=1^K S_k(t) + ∑_mQ_(t)/F^2)
       ϵ'∑_k=1^KU_k(t)

Since a_k(t)≤γ_max∀ t, it follows that g_k(a̅_k^δ)<g_k(γ_max), therefore, we have from the Foster-Lyapunov criterion that the system (𝐒(t), 𝐐(t), 𝐔(t)) has a unique stationary probability distribution, under which the mean queue lengths are finite [For the utility-related virtual queues, note that if g_k'(0)<∞, then Y_k(t)<Vg'_k(0)+γ_k,max, i.e. their length is deterministically bounded]. Therefore the queues are strongly stable under  our proposed policy. 

We now proceed to proving the utility-delay tradeoff. 

Proof of near optimal utility: Here we compare π with the static optimal policy π^* from Lemma <ref>. Since π^* takes decisions irrespectively of the queue lengths, we can replace quantities 𝐚̅, σ̅,  μ̅ with the time averages corresponding to π^*, i.e. 𝐚̅^*, σ̅^*,  μ̅^*. We thus have:  

    V∑_k=1^K𝔼{g_k(γ^π_k(t))}≥ V ∑_k=1^Kg_k(a̅^*_k) - B + 𝔼{Δ L (𝐙(t))}

Taking expectations over 𝐙(t) for both sides and summing the inequalities for t=0,1,..,T-1 we get 

    1/T∑_t=1^T-1∑_k=1^K𝔼{g_k(γ^π_k(t))}≥∑_k=1^K   g_k(a̅^*_k) - B/V - 𝔼{L(𝐙(0))}/VT
       + 𝔼{L(𝐙(T))}/VT

Assuming 𝔼{L(𝐙(0))} < ∞ (this assumption is standard in this line of work, for example it holds if the system starts empty), taking the limit as T goes to infinity gives

    lim_T→∞1/T∑_t=1^T-1∑_k=1^K𝔼{g_k(γ^π_k(t))}≥∑_k=1^Kg_k(a̅^*_k) - B/V

In addition, since g_k(x) are concave, Jensen's inequality implies 

    ∑_k=1^Kg_k(γ̅_l^π)   =∑_k=1^Kg_k(lim_T→∞1/T∑_t=0^T𝔼{γ_k^π(t)})
       ≥lim_T→∞1/T∑_t=1^T-1∑_k=1^K𝔼{g_k(γ^π_k(t))}
       ≥∑_k=1^Kg_k(a̅^*_k) - B/V
    .

Proving the near optimality of the online policy follows from the above and the fact that a̅_k^π > γ̅_k^π (since the virtual queues U_k(t) are strongly stable).


10

url@samestyle








cisco15 “White paper: Cisco VNI Forecast and Methodology, 2015-2020”, Tech. Report, 2015.

maddah2013fundamental
M. Maddah-Ali and U. Niesen, “Fundamental Limits of Caching,” IEEE Trans. Inf. Theory, vol. 60, no. 5, pp. 2856–2867, 2014.

misconceptions G. S. Paschos, E. Bastug, I. Land, G. Caire, and M. Debbah, “Wireless caching: technical misconceptions and business barriers”, IEEE Communications Magazine, 2016.
  
ji2013fundamental
M. Ji,  G. Caire, A. Molisch,  “Fundamental Limits of Distributed Caching in D2D Wireless Networks” , arXiv/1304.5856, 2013.

ji2015order
M. Ji,  A. Tulino, J. Llorca, and G. Caire,  “Order-Optimal Rate of Caching and Coded Multicasting with Random Demands”, arXiv:1502.03124, 2015. 

maddah2013decentralized
M. Maddah-Ali and U. Niesen, “Decentralized Coded Caching Attains Order-Optimal Memory-Rate Tradeoff”, 
 IEEE/ACM Trans. Netw., vol. 23, no. 4, pp. 1029–1040, 2015.



niesen2013coded
M. Maddah-Ali and U. Niesen, “Coded Caching with Nonuniform Demands”,in IEEE INFOCOM Workshops, 2014.

pedarsani2016online
R. Pedarsani, M. Maddah-Ali, and  U. Niesen, “Online Coded Caching," in IEEE/ACM Trans. Netw., vol. 24, no. 2, pp. 836-845, 2016.

 


zhang2016wireless
J. Zhang, and P. Elia, "Wireless Coded Caching: a Topological Perspective". arXiv:1606.08253, 2016.

bidokhti2016noisy
 S. S. Bidokhti, M. Wigger, and R. Timo, “Noisy Broadcast Networks with Receiver Caching”, arXiv preprint arXiv:1605.02317, 2016. 
 
NgoAllerton2016
 K-H. Ngo, S. Yang, and M. Kobayashi, “Cache-Aided Content Delivery in MIMO Channels”, 
 in Proc. Allerton, IL, USA, 2016.


niesen2015coded U. Niesen M. Maddah-Ali “Coded Caching for Delay-Sensitive Content”, in IEEE ICC, pp. 5559-5564, 2015.


el2011network
A. El Gamal and Y. H. Kim, “Network Information Theory”, Cambridge university press, 2011.

  neely10 M. Neely, “Stochastic Network Optimization with Application to Communication and Queueing Systems”, Morgan & Claypool,  2010.
  
    mowalrand J. Mo and J. Walrand, “Fair end-to-end window-based congestion control”, IEEE/ACM Trans. Netw. , Vol. 8, No. 5, Oct. 2000. 
    
    pfscheduling    F. Kelly, “Charging and Rate Control for Elastic Traffic”, European Transactions on Telecommunications, 1997.
    
     stolyar A. L. Stolyar,  “On the asymptotic optimality of the gradient scheduling algorithm for multiuser throughput allocation." Operations Research Vol. 53 No. 1, 2005.

      knopp R. Knopp and P. A. Humblet, “Information capacity and power control in single-cell multiuser communications," in IEEE ICC, Seattle, WA, 1995.

       caire_fairnessMIMO H. Shirani-Mehr, G. Caire and M. J. Neely, “MIMO Downlink Scheduling with Non-Perfect Channel State Knowledge," in IEEE Trans. Commun. , vol. 58, no. 7, pp. 2055-2066, July 2010.

       caire_fairnessBC G. Caire, R. R. Muller and R. Knopp, “Hard Fairness Versus Proportional Fairness in Wireless Communications: The Single-Cell Case," in IEEE Trans. Inf. Theory, vol. 53, no. 4, pp. 1366-1385, April 2007.
       
       Seong06 K. Seong, R. Narasimhan, and J. Cioffi, “Queue Proportional Scheduling via Geometric Programming in Fading Broadcast Channels”, in IEEE JSAC, vol. 24, no. 8, Aug 2006.
       
Eryilmaz01  A. Eryilmaz, and R. Srikant, and J. R. Perkins, “Throughput-optimal Scheduling for Broadcast Channels”, in Proc.  ITCom, Denver, CO, August 2001.

TseOptimal 
D. Tse,  “Optimal Power Allocation over Parallel Gaussian Broadcast Channels”, unpublished


Li05 M. Neely, E. Modiano, and C.-P. Li, “Fairness and Optimal Stochastic Control for Heterogeneous Networks”, IEEE/ACM Trans. Netw., 2005.


  
 
 
 
