50 W.Wang et aL /Computer Communications 83 (2016)45-55 Request for Content B Request for Content C -t<T T Relay sessions 0.8 -Top-5 Content delivered Content cached in 0.6 --Top-10 relay storage ContentA Content B segment 0.4 Content B cached Time 0.2 Fig.3.Content replacement process for a single relay storage segment. 0 10 20 30 40 50 60 total number of available storage segments is pL2I and we have L2.Therefore.the total amount of content that the Fig.2.CDF of Ar/As for top frequent contacting friends in MIT reality trace. system can support is N=0(1). Now consider system with relays.As friends contact regularly irrespective of the network size,it is reasonable to assume that the subscribers are familiar with their friends,they will know the ex- contact rate between relays and subscribers,Ar.remains constant act contact patterns of these relays.Such relays may exhibit dif- when the network size increases.As s=(L-2).we have Asz ferent contact patterns compared to relays selected by the net- CL-2 for some constant cx. work operator.For example,the subscriber may contact colleagues To ensure that Fns.i.n.)<Fo for some constant Fo 1,we regularly on workdays 35.Suppose that inter-contact time be- tween relay and subscriber is bounded above by To.with To can choose ns.i=n.i=L-In Fo/(CT).For sufficiently large L,we T.By the reversibility of the contact process 34.the efficiency haver ns iAs due to ns.is is O(L-1)in this case.Using the of a single relay is at least as good as ns.i seeds that duplicated analysis in Section 4.1,we have Er(nsi-s)sT for arbitrarily small s.Therefore, the content at time To after the subscriber requested the con- tent.By Theorem 1.we have the efficiency Er bounded below by F(ns.i.nri)se-(mtnm-ne)T -nsiIn(Y(T-To)).Considering the case that the contact process ≤eLV-n6/G万rGl-27 between the seed and relay is a Poisson process,Er is bounded below by ns.i(T-To)As.In this case,a single relay has the same =6 (14) efficiency as ns i/2 seeds when To =T/2. Thus,we can ensure that there are at least N pieces of content The above analysis shows the potential benefits of using nodes with bounded failure probability,while >(n+)spL21.It is with regular contact patterns as relays.For example,nodes de- easy to see that N=(L)in this case.Consequently.the amount of ployed at subway stations have high contact rates to many users. content increase as N=©（√m)when the network size L increases.. If we use these nodes as seeds to cache popular content,their ef- Note that the relaying scheme needs (vn)relays,which re- ficiency is equivalent to Ar/s regular seeds.However,if we use quires more friends with constant contact rates when the network them as relays.their efficiency is multiplied by n/2 times,which size increases.In cases where subscribers only have constant num- can be higher than Ar/As.Therefore,it is preferable to use these ber of friends,multi-hop relaying can be used.In multi-hop re- nodes as relays instead of as seeds. laying.friends of friends are requested to act as relays.It can be Note that our relay selection process only considers the contact shown that offloading efficiency of (ns.i-s)sT can be achieved rate of a given relay.Relays can improve the offloading efficiency by using relays that are h hop away from the subscriber when each as long as they have higher contact rates than a randomly selected hop satisfiesrnsis and h is o(logn).Therefore,we can still node.In the case that two relays always have the same mobility find (n)relays via multi-hop relaying in the case where each pattern,e.g.,two mobile phones belonging to the same person,the subscriber/relay only has a constant number of friends. offloading efficiency will be worse than relays have independent mobility patterns.How to select relays under correlated mobility 4.4.Reuse of relays patterns is leaved as future works. 4.3.Asymptotic analysis for Poisson process Relays can be reused for offloading different pieces of content. This is especially useful for offloading rare contents.Define a relay session as the period which starts at the time when the request Relays with higher contact rates increase the amount of content reaches the relay,and ends when either the content is delivered to that the system can support when the network size increases.Con- the subscriber or the request expires.As shown in Fig.3.content sider a network deployed on a square region with side length of L. stored in a single relay segment changes over time while the stor- Suppose that the density of helpers in the network is p.The num- age segment always retain some content even after the session is ber of helpers n then increases as pL-when the network size L finished.Moreover,relays who do not contact a seed will do noth- increases.As the network size increases,the contact rate between ing during the relay session,as shown in the relay session for con- a particular pair of nodes decreases at a speed of (L-2)for vari- ous types of mobility models [321. tent C in Fig.3.Among the©（√n)relays reserving resources for We first show that the total amount of content that the of- the session,only a small fraction F(nsi.0)of them actually down- load the content. floading system can support is (1)under static caching systems. In static caching systems with Poisson contact process,we have As described in Section 3.1.the relay storage segment is com- F(ns..0)=e-nsT.wheres=(L-2).Suppose that nsi=o(12). mitted to caching the requested content during the relay session. i.e.0s ns.i<c1L2,forarbitrary small constant c when Loo.We Since the number of relay segments used for a session for content can make F(ns,0)arbitrarily close to 1 when L approaches infin- i is n.i.which can be obtained through methods described in 5.1. ity by taking the constant c small enough.Therefore,to achieve the average number of relay segments committed to relaying con- tent i can be derived by Little's Theorem: an acceptable offloading success probability,nsi at least should be 2(L2).i.e..ns.iz c2L2 for some constant c2 when L-oo.The nni Rinr.iTi, (15)50 W. Wang et al. / Computer Communications 83 (2016) 45–55 0 10 20 30 40 50 60 0 0.2 0.4 0.6 0.8 1 λr /λs CDF Top−5 Top−10 Fig. 2. CDF of λr/λs for top frequent contacting friends in MIT reality trace. subscribers are familiar with their friends, they will know the ex￾act contact patterns of these relays. Such relays may exhibit dif￾ferent contact patterns compared to relays selected by the net￾work operator. For example, the subscriber may contact colleagues regularly on workdays [35]. Suppose that inter-contact time be￾tween relay and subscriber is bounded above by T0, with T0 < T. By the reversibility of the contact process [34], the efficiency of a single relay is at least as good as ns, i seeds that duplicated the content at time T0 after the subscriber requested the con￾tent. By Theorem 1, we have the efficiency Er bounded below by −ns,i ln(Yˆ(T − T0)). Considering the case that the contact process between the seed and relay is a Poisson process, Er is bounded below by ns,i(T − T0)λs. In this case, a single relay has the same efficiency as ns, i/2 seeds when T0 = T/2. The above analysis shows the potential benefits of using nodes with regular contact patterns as relays. For example, nodes de￾ployed at subway stations have high contact rates to many users. If we use these nodes as seeds to cache popular content, their ef- ficiency is equivalent to λr/λs regular seeds. However, if we use them as relays, their efficiency is multiplied by ns, i/2 times, which can be higher than λr/λs. Therefore, it is preferable to use these nodes as relays instead of as seeds. Note that our relay selection process only considers the contact rate of a given relay. Relays can improve the offloading efficiency as long as they have higher contact rates than a randomly selected node. In the case that two relays always have the same mobility pattern, e.g., two mobile phones belonging to the same person, the offloading efficiency will be worse than relays have independent mobility patterns. How to select relays under correlated mobility patterns is leaved as future works. 4.3. Asymptotic analysis for Poisson process Relays with higher contact rates increase the amount of content that the system can support when the network size increases. Con￾sider a network deployed on a square region with side length of L. Suppose that the density of helpers in the network is ρ. The num￾ber of helpers n then increases as ρL2 when the network size L increases. As the network size increases, the contact rate between a particular pair of nodes decreases at a speed of (L−2) for vari￾ous types of mobility models [32]. We first show that the total amount of content that the of- floading system can support is O(1) under static caching systems. In static caching systems with Poisson contact process, we have F (ns,i, 0) = e−ns,iλsT , where λs = (L−2). Suppose that ns,i = o(L2), i.e., 0 ≤ ns, i < c1L2, forarbitrary small constant c1 when L → ∞. We can make F(ns, i, 0) arbitrarily close to 1 when L approaches infin￾ity by taking the constant c1 small enough. Therefore, to achieve an acceptable offloading success probability, ns, i at least should be (L2), i.e., ns, i ≥ c2L2 for some constant c2 when L → ∞. The Fig. 3. Content replacement process for a single relay storage segment. total number of available storage segments is ρL2I and we have N i=1 ns,i ≤ ρL2I. Therefore, the total amount of content that the system can support is N = O(1). Now consider system with relays. As friends contact regularly irrespective of the network size, it is reasonable to assume that the contact rate between relays and subscribers, λr, remains constant when the network size increases. As λs = (L−2), we have λs ≥ cλL−2 for some constant cλ. To ensure that F(ns, i, nr, i) ≤ F0 for some constant F0 ≤ 1, we can choose ns,i = nr,i = L − ln F0/(cλT ). For sufficiently large L, we have λr  ns, iλs due to ns, iλs is O(L−1) in this case. Using the analysis in Section 4.1, we have Er ≥ (ns,i − ε)λsT for arbitrarily small ε. Therefore, F (ns,i, nr,i) ≤ e−(ns,i+nr,ins,i−nr,iε)λsT ≤ e−(L √− ln F0/(cλT ))2cλL−2T = F0. (14) Thus, we can ensure that there are at least N pieces of content with bounded failure probability, while N i=1(ns,i + nr,i) ≤ ρL2I. It is easy to see that N = (L) in this case. Consequently, the amount of content increase as N = (√n) when the network size L increases. Note that the relaying scheme needs (√n) relays, which re￾quires more friends with constant contact rates when the network size increases. In cases where subscribers only have constant num￾ber of friends, multi-hop relaying can be used. In multi-hop re￾laying, friends of friends are requested to act as relays. It can be shown that offloading efficiency of (ns,i − ε)λsT can be achieved by using relays that are h hop away from the subscriber when each hop satisfies λr  ns, iλs and h is O(log n). Therefore, we can still find (√n) relays via multi-hop relaying in the case where each subscriber/relay only has a constant number of friends. 4.4. Reuse of relays Relays can be reused for offloading different pieces of content. This is especially useful for offloading rare contents. Define a relay session as the period which starts at the time when the request reaches the relay, and ends when either the content is delivered to the subscriber or the request expires. As shown in Fig. 3, content stored in a single relay segment changes over time while the stor￾age segment always retain some content even after the session is finished. Moreover, relays who do not contact a seed will do noth￾ing during the relay session, as shown in the relay session for con￾tent C in Fig. 3. Among the (√n) relays reserving resources for the session, only a small fraction F(ns, i, 0) of them actually down￾load the content. As described in Section 3.1, the relay storage segment is com￾mitted to caching the requested content during the relay session. Since the number of relay segments used for a session for content i is nr, i, which can be obtained through methods described in 5.1, the average number of relay segments committed to relaying con￾tent i can be derived by Little’s Theorem: nr,i = Rinr,i Ti, (15)