W.Wang et aL/Computer Communications 83(2016)45-55 53 ◆Content A with relay Content B with relav 0 nt A no relay 00 Conte Content B no relay 0.2 50 0.2 488089-9 0.4 0.6 0.8 02 0.4 0.6 0.8 0.2 0.4 0.6 0.8 (a)Storage allocation for relaying scheme (b)Storage allocation for static scheme (c)Failure probability for relay and static scenario Fig.4.Convex optimization result (n 5000,k =10,T=1). of relays for each session to be smaller than five,i.e.,less than five This shows that relaying can support more content with low re- relays are used in each session.Our numerical results in Section 6 questing rates.The numerical results under various different pa- show that such limitations do not significantly change the system rameter settings also has similar trends that demonstrate relaying performance. can improve the offloading of rare content. Communication overhead:Relaying requires content requests to (2)Offloading performance be sent to relays through the cellular network,which incurs addi- Fig.5(a)illustrates systems with 100 content categories,where tional control traffic above that of traditional static solutions [6]. the content request rate follows a Zipf distribution with a=0.8 However,content delivery systems normally have large segment [39].We observe that the overall failure probability in the optimal sizes,such as 2M bytes in P2P-VoD systems [29].It only takes sev- relaying case reduces much faster than in the static case.We fur- eral hundred bytes to send relay requests to 10 relays,which incurs ther consider the impact of different factors on the offloading ef- less than 1%overhead.Compared to the 30%gain in offloading ef- ficiency.For the curve labeled no reuse,we set ki=1 so that re- ficiency.the 1%communication overhead is small. lays are never reused between contents.We observe that the per- Unreliable contacts:In real networks,detection of the existence formance of relaying is still better in this case than in the static of D2D links might be unreliable,and data transfer over D2D links case,because relays with higher contact rates to subscribers per- could be dropped.Moreover,some contacts may be too short to form better than seeds.On the other hand,if relays do not have transmit even a single segment.Considering these cases,we use higher contact rates but can be reused,the offloading failure prob- the effective contact rate in our system.Suppose that among all ability reduces faster when A is higher,as shown in the no friend contacts,there are a portion y of contacts that are unreliable or case.This is because relays with high reuse rates can be especially short contacts.The effective contact processes for seeds and re- helpful for rare content,which has more chances to be offloaded lays can then be modeled as Poisson processes with intensity of when A is high.We also observe that limiting the number of re- (1-y)As and (1-y)Ar.respectively,by the properties of Poisson lays for each session has little impact on performance,because the process [34].Our results and optimization schemes are still valid curve for limited friends,where nfr.i is smaller than five,is almost in this case. identical to the optimal solution. (3)Performance under different scenarios 6.Simulation results Fig.5(b)shows the relationship between offloading perfor- mance and the number of content categories in the system.In the 6.1.Numerical results experiments,we increase the number of content categories from 5 to 100.In the uniform case,we divide available storage slots in We use the numerical results obtained from gradient projection helpers evenly to these content categories without considering the algorithms to show the properties of the storage assignment prob request rates.Therefore,the offloading failure probability does not lem. change when the number of content categories increases.The static (1)Example for two categories of content scheme allocates storage based on content request rates,where We use an offloading system with only two content categories A popular content gets more replicas.The relay scheme uses part of and B to demonstrate the tradeoffs between relays and seeds.The the storage as seeds and allocates relays for content request based requesting rates for the two categories of content are 0.5 and 0.1 on our optimization algorithm.Both the static and relay scheme respectively.and the amount of content in each category is 1000. consider the request rates of contents,so that their offloading fail- We assume that there are n=5000 helpers,each of which con- ure probabilities decrease as the number of content categories in- tributes one storage segment.We assume the contact processes are creases,ie.,the request rates for content become different.The re- Poisson processes with kr =10 (i.e.,relays have 10 times higher lay scheme has lower offloading failure probability than the static contact rates than seeds.).Fig.4(a)and (b)shows the fractions of scheme storage allocated for each type of contents in the relaying scheme Fig.5(c)shows the performance of offloading schemes with dif- and static cache scheme,respectively.From Fig.4(b).we see that ferent content request rates.Both the uniform and static scheme static cache assignment tends to allocate all storage to the popular have constant offloading failure probability when the request rate content category A when A is small.This implies that a static cache increases,as they only use seeds for offloading.The relay scheme scheme only tries to offload a small number of contents.In the re- has better performance than the other two schemes.However,the laying scheme,the system allocates a high fraction of relays to the gap reduces when the request rate increases.This is because re- less popular content category B to help deliver content B even in lays reserve storage for each individual request.Thus,relays be- the case that A is quite low.The offloading failure probabilities are come congested when the request rates increase.However,the per- shown in Fig 4(c).Offloading failure probabilities of the relaying formance of relay scheme is always better than the static scheme, schemes for both content categories are always smaller than those since the static solutions are in a subset of the relaying solutions. of the static cases.The failure probability for the less popular con- Fig.5(d)shows the offloading performance under different tent category B has been greatly improved in the relaying systems numbers of helpers.We observe that all schemes have betterW. Wang et al. / Computer Communications 83 (2016) 45–55 53 Fig. 4. Convex optimization result (n = 5000, kr = 10, T = 1). of relays for each session to be smaller than five, i.e., less than five relays are used in each session. Our numerical results in Section 6 show that such limitations do not significantly change the system performance. Communication overhead: Relaying requires content requests to be sent to relays through the cellular network, which incurs addi￾tional control traffic above that of traditional static solutions [6]. However, content delivery systems normally have large segment sizes, such as 2M bytes in P2P-VoD systems [29]. It only takes sev￾eral hundred bytes to send relay requests to 10 relays, which incurs less than 1% overhead. Compared to the 30% gain in offloading ef- ficiency, the 1% communication overhead is small. Unreliable contacts: In real networks, detection of the existence of D2D links might be unreliable, and data transfer over D2D links could be dropped. Moreover, some contacts may be too short to transmit even a single segment. Considering these cases, we use the effective contact rate in our system. Suppose that among all contacts, there are a portion γ of contacts that are unreliable or short contacts. The effective contact processes for seeds and re￾lays can then be modeled as Poisson processes with intensity of (1 − γ )λs and (1 − γ )λr, respectively, by the properties of Poisson process [34]. Our results and optimization schemes are still valid in this case. 6. Simulation results 6.1. Numerical results We use the numerical results obtained from gradient projection algorithms to show the properties of the storage assignment prob￾lem. (1) Example for two categories of content We use an offloading system with only two content categories A and B to demonstrate the tradeoffs between relays and seeds. The requesting rates for the two categories of content are 0.5 and 0.1 respectively, and the amount of content in each category is 1000. We assume that there are n = 5000 helpers, each of which con￾tributes one storage segment. We assume the contact processes are Poisson processes with kr = 10 (i.e., relays have 10 times higher contact rates than seeds.). Fig. 4(a) and (b) shows the fractions of storage allocated for each type of contents in the relaying scheme and static cache scheme, respectively. From Fig. 4(b), we see that static cache assignment tends to allocate all storage to the popular content category A when λ is small. This implies that a static cache scheme only tries to offload a small number of contents. In the re￾laying scheme, the system allocates a high fraction of relays to the less popular content category B to help deliver content B even in the case that λ is quite low. The offloading failure probabilities are shown in Fig 4(c). Offloading failure probabilities of the relaying schemes for both content categories are always smaller than those of the static cases. The failure probability for the less popular con￾tent category B has been greatly improved in the relaying systems. This shows that relaying can support more content with low re￾questing rates. The numerical results under various different pa￾rameter settings also has similar trends that demonstrate relaying can improve the offloading of rare content. (2) Offloading performance Fig. 5(a) illustrates systems with 100 content categories, where the content request rate follows a Zipf distribution with α = 0.8 [39]. We observe that the overall failure probability in the optimal relaying case reduces much faster than in the static case. We fur￾ther consider the impact of different factors on the offloading ef- ficiency. For the curve labeled no reuse, we set ku,i = 1 so that re￾lays are never reused between contents. We observe that the per￾formance of relaying is still better in this case than in the static case, because relays with higher contact rates to subscribers per￾form better than seeds. On the other hand, if relays do not have higher contact rates but can be reused, the offloading failure prob￾ability reduces faster when λ is higher, as shown in the no friend case. This is because relays with high reuse rates can be especially helpful for rare content, which has more chances to be offloaded when λ is high. We also observe that limiting the number of re￾lays for each session has little impact on performance, because the curve for limited friends, where nfr, i is smaller than five, is almost identical to the optimal solution. (3) Performance under different scenarios Fig. 5(b) shows the relationship between offloading perfor￾mance and the number of content categories in the system. In the experiments, we increase the number of content categories from 5 to 100. In the uniform case, we divide available storage slots in helpers evenly to these content categories without considering the request rates. Therefore, the offloading failure probability does not change when the number of content categories increases. The static scheme allocates storage based on content request rates, where popular content gets more replicas. The relay scheme uses part of the storage as seeds and allocates relays for content request based on our optimization algorithm. Both the static and relay scheme consider the request rates of contents, so that their offloading fail￾ure probabilities decrease as the number of content categories in￾creases, i.e., the request rates for content become different. The re￾lay scheme has lower offloading failure probability than the static scheme. Fig. 5(c) shows the performance of offloading schemes with dif￾ferent content request rates. Both the uniform and static scheme have constant offloading failure probability when the request rate increases, as they only use seeds for offloading. The relay scheme has better performance than the other two schemes. However, the gap reduces when the request rate increases. This is because re￾lays reserve storage for each individual request. Thus, relays be￾come congested when the request rates increase. However, the per￾formance of relay scheme is always better than the static scheme, since the static solutions are in a subset of the relaying solutions. Fig. 5(d) shows the offloading performance under different numbers of helpers. We observe that all schemes have better