W.Wang et aL/Computer Communications 83(2016)45-55 where Ri is the request rate of content i,n.i is the number of contact patterns and content request rates.Therefore,we should relays for each request and Ti is the average duration of a relay carefully set the number of relays used for each piece of content session.The fraction of offloading session with length longer than based on these parameters.Seeds need to statically cache a piece t can be written as F(nsi.nr.i.t)by substituting the time limit of content to ensure that there are minimal copies of the given T with a variable t in the offloading failure probability.Therefore, content in the network.This leaves limited storage for relays.Thus, we have Ti=F(nsi.n.i.t)dt as subscribers waiting at most for we need to dynamically adjust the number of relays allocated for time T. each piece of content,depending on its popularity and the number From Eq.(15).we see that nr.i can be smaller than nr.i when of seeds currently caching the content. R1.This shows rare content do not actually use nr.i storage In this section,we jointly optimize the storage assigned to segments on average.Thus,it would be more efficient to allocate seeds and relays so that the overall offloading failure probability more relays for rare content,since a relay storage segment can dy- is minimized for content with different request rates. namically switch between different content to get better storage The storage assignment problem for a system with both relays utilization.For "hot"contents that are always simultaneously re- and seeds can be formulated as follows: quested by multiple subscribers,i.e.,RiT>1.a better strategy is Minimize∑，MRF(nfi,nfrs)) (17) to statically cache the content in seeds,since spreading the "hot" content among different relays is less efficient when Ar is compa rable to ns.is as shown in Section 4.1. Relays stay idle between relay sessions.The average length of s.t∑1(fsi+ku.ifri)≤I (18) idle period can be derived using the G/G/m/m queueing model.The utilization factor for relay segments depends on both the request arrival process and the node contact patterns,which do not have fsi+fr s1Vi (19) a general closed form formula.To simplify our model,we use the relay reuse factor ki=RiT to approximate the utility of relays for content i in Section 5. fs.i≥0，ri≥0i (20) 4.5.Dynamical loads wheref=andfr=are the fractions of nodes that serve as seeds and relays for content i.Eg.(18)limits the sum of stor- There are two cases where the requesting rate of R;can change age segments allocated for seeds and relays to be smaller than nl. The first case is a long-term evolution of content popularity.where which is the total number of storage segments in the system.The R;changes slowly.The second case is short-term load surges fraction of relay segments is multiplied by kwhich reflects the where R;can temporally exceed its average rate. impact of relay reuse as described in Section 4.4.Eq.(19)requires To handle long-term load changes,the cellular network keeps that the number of seeds plus the number of the relays should not track of the requests of each content.As all offloading requests are be larger than n for any content. sent through the cellular network,we can estimate the long-term In the above formulation,we relax the storage optimization request rates for a given content i as follows.Suppose that there problem from an integer programming problem,which is NP- are ri(t)requests for content i in a given time slot t,we use Expo- hard [5].to a convex optimization problem that can be efficiently nential Moving Average (EMA)to estimate the long-term request solved.This is because we use real variables fsi and fr.i instead rate as: of integer variables ns.i and nr.i.We can show that the approxi- mation ratio of the above relaxation approaches 1 when n goes to R(t)=aR(t-1)+(1-a)ri(t) (16) infinity,using similar arguments as in 5. where R(t)is the long-term request rate at time t and o is a con- stant smoothing factor with value between 0.8 and 0.95.The size Theorem 2.The objective function Eg.(17)in the storage assignment of the time slot can be chosen as one hour and the smoothing problem is convex,when Er(fs.i)is concave and twice differentiable. factor a determines the smoothness of the estimation.After esti- Proof.The convexity of the objective function in Eq.(17)can be mated the requesting rate,we execute the optimization algorithm derived as follows: described in Section 5 to calculate the optimal values for ns.i and As the nonnegative weighted sum of convex functions is con- nr.i To handle short-term surges in content request,we apply a vex,it is enough to show that F(nfs.i.nfr.i)is convex respect to fs.i rate limiting algorithm for relay requests.Note that the number of and fr.i.We have: seeds,ns.i.is independent of short-term requesting rate changes. F(nfs.i.nfrt)=e-n-n听a (21) We only need to modify the number of relays nr.i for the given re- quest.In case that the instantaneous request rate ri(t)is larger than Define g(fs.i.fr.)as -nfs.Es-nfr.Er.Since F(nfs.i.nfr.i)= long-term average Ri(t).we set the number of relays allocated for e().if g(fsfr)is convex then Fnfs.nf.)is also convex a given request toso that the total number of relays allo- [371. cated for content i will not exceed BR(t)n i.where B is an over- As we have shown in Section 4.1,Er is normally a function of load factor which allows a single content to use more caches than fs i and Es is a constant with respect to fs.i and fr.i.Therefore, the long-term optimal value.In case of load surge,the number of when g(fs.i.fr.)is twice differentiable,we have: relays allocated for the content will be limited and the offloading a2E(5.i) efficiency for the given content will decrease temporally. V2g(fa.fr)=nf (22) 5.Storage assignment optimization Since nfr.i is always positive,gufs.fr.)is convex when E(fs)is concave. 5.1.Problem formulation Corollary 2.The storage assignment problem in Egs.(17)-(20)is con- The analysis in Section 4 shows that the efficiency of relays is vex for relays with nonlattice renewal contact process and twice dif- determined by various factors,including the number of seeds,relay ferentiable offloading efficiency function.W. Wang et al. / Computer Communications 83 (2016) 45–55 51 where Ri is the request rate of content i, nr, i is the number of relays for each request and Ti is the average duration of a relay session. The fraction of offloading session with length longer than t can be written as F(ns, i, nr, i, t) by substituting the time limit T with a variable t in the offloading failure probability. Therefore, we have Ti =  T 0 F (ns,i, nr,i,t)dt as subscribers waiting at most for time T. From Eq. (15), we see that nr,i can be smaller than nr, i when Ri Ti < 1. This shows rare content do not actually use nr, i storage segments on average. Thus, it would be more efficient to allocate more relays for rare content, since a relay storage segment can dy￾namically switch between different content to get better storage utilization. For “hot” contents that are always simultaneously re￾quested by multiple subscribers, i.e., Ri Ti > 1, a better strategy is to statically cache the content in seeds, since spreading the “hot” content among different relays is less efficient when λr is compa￾rable to ns, iλs as shown in Section 4.1. Relays stay idle between relay sessions. The average length of idle period can be derived using the G/G/m/m queueing model. The utilization factor for relay segments depends on both the request arrival process and the node contact patterns, which do not have a general closed form formula. To simplify our model, we use the relay reuse factor ku,i = RiT to approximate the utility of relays for content i in Section 5. 4.5. Dynamical loads There are two cases where the requesting rate of Ri can change. The first case is a long-term evolution of content popularity, where Ri changes slowly. The second case is short-term load surges, where Ri can temporally exceed its average rate. To handle long-term load changes, the cellular network keeps track of the requests of each content. As all offloading requests are sent through the cellular network, we can estimate the long-term request rates for a given content i as follows. Suppose that there are ri(t) requests for content i in a given time slot t, we use Expo￾nential Moving Average (EMA) to estimate the long-term request rate as: Ri(t) = αRi(t − 1) + (1 − α)ri(t) (16) where Ri(t) is the long-term request rate at time t and α is a con￾stant smoothing factor with value between 0.8 and 0.95. The size of the time slot can be chosen as one hour and the smoothing factor α determines the smoothness of the estimation. After esti￾mated the requesting rate, we execute the optimization algorithm described in Section 5 to calculate the optimal values for ns, i and nr, i. To handle short-term surges in content request, we apply a rate limiting algorithm for relay requests. Note that the number of seeds, ns, i, is independent of short-term requesting rate changes. We only need to modify the number of relays nr, i for the given re￾quest. In case that the instantaneous request rate ri(t) is larger than long-term average Ri(t), we set the number of relays allocated for a given request to βRi(t) ri(t) nr,i so that the total number of relays allo￾cated for content i will not exceed βRi(t)nr, i, where β is an over￾load factor which allows a single content to use more caches than the long-term optimal value. In case of load surge, the number of relays allocated for the content will be limited and the offloading efficiency for the given content will decrease temporally. 5. Storage assignment optimization 5.1. Problem formulation The analysis in Section 4 shows that the efficiency of relays is determined by various factors, including the number of seeds, relay contact patterns and content request rates. Therefore, we should carefully set the number of relays used for each piece of content based on these parameters. Seeds need to statically cache a piece of content to ensure that there are minimal copies of the given content in the network. This leaves limited storage for relays. Thus, we need to dynamically adjust the number of relays allocated for each piece of content, depending on its popularity and the number of seeds currently caching the content. In this section, we jointly optimize the storage assigned to seeds and relays so that the overall offloading failure probability is minimized for content with different request rates. The storage assignment problem for a system with both relays and seeds can be formulated as follows: Minimize N i=1 MRiF (n fs,i, n fr,i) (17) s.t. N i=1 (fs,i + ku,i fr,i) ≤ I (18) fs,i + fr,i ≤ 1 ∀ i (19) fs,i ≥ 0, fr,i ≥ 0 ∀ i (20) where fs,i = ns,i n and fr,i = nr,i n are the fractions of nodes that serve as seeds and relays for content i. Eq. (18) limits the sum of stor￾age segments allocated for seeds and relays to be smaller than nI, which is the total number of storage segments in the system. The fraction of relay segments is multiplied by ku, i, which reflects the impact of relay reuse as described in Section 4.4. Eq. (19) requires that the number of seeds plus the number of the relays should not be larger than n for any content. In the above formulation, we relax the storage optimization problem from an integer programming problem, which is NP￾hard [5], to a convex optimization problem that can be efficiently solved. This is because we use real variables fs, i and fr, i instead of integer variables ns, i and nr, i. We can show that the approxi￾mation ratio of the above relaxation approaches 1 when n goes to infinity, using similar arguments as in [5]. Theorem 2. The objective function Eq. (17) in the storage assignment problem is convex, when Er(fs, i) is concave and twice differentiable. Proof. The convexity of the objective function in Eq. (17) can be derived as follows: As the nonnegative weighted sum of convex functions is con￾vex, it is enough to show that F(nfs, i, nfr, i) is convex respect to fs, i and fr, i. We have: F (n fs,i, n fr,i) = e−n fs,iEs−n fr,iEr . (21) Define g(fs, i, fr, i) as −n fs,iEs − n fr,iEr. Since F (n fs,i, n fr,i) = eg(fs,i,fr,i) , if g(fs, i, fr, i) is convex then F(nfs, i, nfr, i) is also convex [37]. As we have shown in Section 4.1, Er is normally a function of fs, i and Es is a constant with respect to fs, i and fr, i. Therefore, when g(fs, i, fr, i) is twice differentiable, we have: ∇2g(fs,i, fr,i) = −n fr,i ∂2Er(fs,i) ∂ f 2 s,i . (22) Since nfr, i is always positive, g(fs, i, fr, i) is convex when Er(fs, i) is concave. Corollary 2. The storage assignment problem in Eqs. (17)–(20) is con￾vex for relays with nonlattice renewal contact process and twice dif￾ferentiable offloading efficiency function.