计算机科学与技术（参考文献）Joint storage assignment for D2D offloading systems

Computer Communications 83 (2016)45-55 Contents lists available at ScienceDirect computer cmmuncatons Computer Communications ELSEVIER journal homepage:www.elsevier.com/locate/comcom Joint storage assignment for D2D offloading systems CrossMark Wei Wang",Xiaobing Wu,Lei Xie,Sanglu Lu State Key Laboratory for Novel Software Technology.Nanjing University.Nanjing 210093.China ARTICLE INFO ABSTRACT Article history: D2D offloading reduces the load of cellular network by asking mobile nodes to download content directly Received 3 September 2014 from storage of neighboring helpers via short range links.In this paper.we introduce a novel storage Revised 18 December 2015 Accepted 22 February 2016 assignment scheme that can enhance storage utilization for D2D networks that have different types of Available online 3 March 2016 storage nodes.Unlike traditional D2D systems that only use storage as static content cache,our scheme uses on-demand relaying to enhance storage utilization.Our on-demand relaying scheme replicates rare Keywords: content when it is requested.Therefore,the proposed scheme can greatly increase the amount of con- Device-to-Device communication tent supported by the offloading system.We develop a convex optimization based algorithm to find the DTN optimal storage assignment tradeoff between static caching and on-demand relaying.Numerical results Opportunistic networks and real-world trace-driven simulations show that our algorithm can achieve 30%reduction in offloading failure rate compared to static schemes. 2016 Elsevier B.V.All rights reserved. 1.Introduction starts downloading the movie directly through the cellular network 5.To make offloading successful,the movie must be cached in at Mobile traffic has increased at a compound annual growth rate least one of the helpers in a small virtual region that Alice can of more than 70%in recent years [1].Meeting such a large surge contact before she becomes impatient.The size of the "region"is in traffic demand is a great challenge for both cellular network de- determined by the user mobility pattern and the time that Alice signers and operators.One way to relieve the pressure on current can wait.Because the total storage contributed by helpers in this cellular networks is to offload part of the mobile traffic through virtual region is limited,the offloading system can only provide a Device-to-Device (D2D)communication [2.Because most mobile limited amount of content to Alice.Even if the offloading system traffic comes from content downloading [1].one of the impor- covers a large area and has a huge number of helpers,it can only tant offloading targets is mobile content,which includes applica- offload a constant amount of content due to the locality of the con- tion updates and video clips.In D2D offloading systems for con- tent in the static caching scheme. tent downloading,mobile helpers serve as content caches for other In this paper,we improve the scalability of D2D systems by in- nodes.These helpers directly deliver content to neighboring de- troducing different roles to mobile helpers.We assign some of the vices through short-range and low-cost wireless links (e.g.,Blue- mobile helpers as on-demand relays instead of static caches,which tooth,WiFi Direct or LTE D2D links [3]).In this way,the download- are referred to as seeds in this paper.Due to the inherent non- ing traffic does not pass through base stations and core networks uniformity in the contact pattern,relays may have a higher con- so that the limited resource of cellular networks can be saved [4. tact probability to the subscriber than seeds.For example,Alice Existing D2D offloading systems "statically"assign content to may request her friends to act as mobile relays to download the mobile helpers based on content popularity [5.6].Subscribers need movie.Although it might be difficult for Alice to directly contact to directly contact mobile helpers that have the content of interest a seed,there will be a higher chance that one of her friends can in their cache.Such static caching schemes have limited scalabil- successfully download the movie.Afterwards,Alice can download ity with respect to network size.Consider the case where a sub- the movie from her friends when she intentionally or accidentally scriber called Alice wishes to download a movie through the D2D meets them.In this way.the number of helpers that Alice can con- offloading system.Due to limited mobility.Alice can only contact a tact is effectively enlarged with the help of her friends. small number of mobile helpers before she becomes impatient and In addition to using friends as relays,mobile nodes mounted on buses or static nodes deployed at public places (e.g..entrance of subways)can also act as relay nodes.These types of nodes have Corresponding author.Tel:+86 13851658076. regular contact patterns to a given subset of subscribers.For exam- E-mail addresses:ww@nju.edu.cn,wangwei.ww@gmail.com (W.Wang). ple,a subscriber may pass by a given subway station every day.If wuxb@nju.edu.cn (X.Wu).Ixie@nju.edu.cn (L Xie).sanglu@nju.edu.cn (S.Lu). http://dx.doiorg/10.1016/j.comcom.2016.02.012 0140-3664/6 2016 Elsevier B.V.All rights reserved

Computer Communications 83 (2016) 45–55 Contents lists available at ScienceDirect Computer Communications journal homepage: www.elsevier.com/locate/comcom Joint storage assignment for D2D offloading systems Wei Wang∗ , Xiaobing Wu, Lei Xie, Sanglu Lu State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210093, China a r t i c l e i n f o Article history: Received 3 September 2014 Revised 18 December 2015 Accepted 22 February 2016 Available online 3 March 2016 Keywords: Device-to-Device communication DTN Opportunistic networks a b s t r a c t D2D offloading reduces the load of cellular network by asking mobile nodes to download content directly from storage of neighboring helpers via short range links. In this paper, we introduce a novel storage assignment scheme that can enhance storage utilization for D2D networks that have different types of storage nodes. Unlike traditional D2D systems that only use storage as static content cache, our scheme uses on-demand relaying to enhance storage utilization. Our on-demand relaying scheme replicates rare content when it is requested. Therefore, the proposed scheme can greatly increase the amount of con￾tent supported by the offloading system. We develop a convex optimization based algorithm to find the optimal storage assignment tradeoff between static caching and on-demand relaying. Numerical results and real-world trace-driven simulations show that our algorithm can achieve 30% reduction in offloading failure rate compared to static schemes. © 2016 Elsevier B.V. All rights reserved. 1. Introduction Mobile traffic has increased at a compound annual growth rate of more than 70% in recent years [1]. Meeting such a large surge in traffic demand is a great challenge for both cellular network de￾signers and operators. One way to relieve the pressure on current cellular networks is to offload part of the mobile traffic through Device-to-Device (D2D) communication [2]. Because most mobile traffic comes from content downloading [1], one of the impor￾tant offloading targets is mobile content, which includes applica￾tion updates and video clips. In D2D offloading systems for con￾tent downloading, mobile helpers serve as content caches for other nodes. These helpers directly deliver content to neighboring de￾vices through short-range and low-cost wireless links (e.g., Blue￾tooth, WiFi Direct or LTE D2D links [3]). In this way, the download￾ing traffic does not pass through base stations and core networks so that the limited resource of cellular networks can be saved [4]. Existing D2D offloading systems “statically” assign content to mobile helpers based on content popularity [5,6]. Subscribers need to directly contact mobile helpers that have the content of interest in their cache. Such static caching schemes have limited scalabil￾ity with respect to network size. Consider the case where a sub￾scriber called Alice wishes to download a movie through the D2D offloading system. Due to limited mobility, Alice can only contact a small number of mobile helpers before she becomes impatient and ∗ Corresponding author. Tel.: +86 13851658076. E-mail addresses: ww@nju.edu.cn, wangwei.ww@gmail.com (W. Wang), wuxb@nju.edu.cn (X. Wu), lxie@nju.edu.cn (L. Xie), sanglu@nju.edu.cn (S. Lu). starts downloading the movie directly through the cellular network [5]. To make offloading successful, the movie must be cached in at least one of the helpers in a small virtual region that Alice can contact before she becomes impatient. The size of the “region” is determined by the user mobility pattern and the time that Alice can wait. Because the total storage contributed by helpers in this virtual region is limited, the offloading system can only provide a limited amount of content to Alice. Even if the offloading system covers a large area and has a huge number of helpers, it can only offload a constant amount of content due to the locality of the con￾tent in the static caching scheme. In this paper, we improve the scalability of D2D systems by in￾troducing different roles to mobile helpers. We assign some of the mobile helpers as on-demand relays instead of static caches, which are referred to as seeds in this paper. Due to the inherent non￾uniformity in the contact pattern, relays may have a higher con￾tact probability to the subscriber than seeds. For example, Alice may request her friends to act as mobile relays to download the movie. Although it might be difficult for Alice to directly contact a seed, there will be a higher chance that one of her friends can successfully download the movie. Afterwards, Alice can download the movie from her friends when she intentionally or accidentally meets them. In this way, the number of helpers that Alice can con￾tact is effectively enlarged with the help of her friends. In addition to using friends as relays, mobile nodes mounted on buses or static nodes deployed at public places (e.g., entrance of subways) can also act as relay nodes. These types of nodes have regular contact patterns to a given subset of subscribers. For exam￾ple, a subscriber may pass by a given subway station every day. If http://dx.doi.org/10.1016/j.comcom.2016.02.012 0140-3664/© 2016 Elsevier B.V. All rights reserved

6 W.Wang et aL /Computer Communications 83 (2016)45-55 there is a relay deployed at the subway station,this relay can ac- tively search for the content requested by the subscriber and make sure the content can be delivered when the user passes by.Our analysis shows that using one relay with regular contact patterns can be as effective as increasing the number of seeds by a constant D2D ratio. communication An important issue in a relaying system is to allocate storage for content.Because users can choose to statically cache the content or RelaySeed dynamically download new content for their friends,mobile relays Cellular and seeds are actually different roles played by the same group coverace of helpers.In this way,relays and seeds need to share the lim- ited storage resources in mobile helpers and storage allocation be- comes critical to the performance of the offloading system.When Subscriber too many helpers are acting as seeds,there will be an insufficient amount of relays to"ferry"content between seeds and subscribers. Conversely,if there were too few seeds storing the requested con- Fig.1.Illustration of the communication model. tent,it would be difficult for relays to find a seed,making relaying useless.To find the optimal tradeoff point,we introduce the con- Information searching in opportunistic networks:Content of- cept of offloading efficiency to incorporate mobile relays and seeds floading systems focus on reducing the data delivery cost for a in the same optimization framework.We prove that the storage given set of content [5,6,13-16].As contents are cached in a dis- optimization problem is convex for various types of contact pat- tributed way,one important issue in content offloading systems terns and can be efficiently solved in a distributed manner.Our is to search information in a network with dynamic topology and numerical and trace-driven results show that relaying can reduce intermittent connections.User interests and network structures the offloading failure rate by more than 30%in D2D systems. can be used to help the content searching process.SPOON uti- The main contributions of this paper are as follows: lizes interest based searching to improve the performance of P2P file sharing [17].Social contact information is utilized in [18]to 1.We propose a new content download pattern that uses relays in find the optimal caching point based on user interests.Seeker- addition to traditional seeds to improve the scalability of D2D Assisted Searching (SAS)use seekers to help node to search infor- offloading systems. mation,while assuming users with the same interest meets more 2.We introduce a storage optimization framework that can be ap- plied to different types of helpers in D2D offloading systems. frequently [19].Optimal searching strategy in linear opportunistic networks is studied in [201. 3.Assuming constant helper density and Poisson contact pro- Replication optimization in opportunistic networks:The goal cesses,we show that offloading systems with n helpers can of optimal content replication is to maximize the social welfare, support (Vn)pieces of content when using both relays and which is defined as the expected utility gain from offloading seeds,while the amount of content supported by a static Delay-utility models are introduced in [5]to describe the impa- caching system is only 0(1). tience of subscribers.The utility optimization problem is shown 4.We show that the joint storage assignment problem for relays to be NP-hard [5.6].There are several ways to obtain approximate and seeds is convex and can be efficiently solved.Furthermore, solutions,including greedy heuristic algorithms [6.convex relax- our model can be extended to other types of helpers with con- ation [5]and a distributed algorithm based on voting [13.Dis- cave offloading efficiency functions.This leads to a better un- tributed caching in Femtocells is considered in 21.The storage derstanding of storage allocation when the network has multi- allocation problem under this scenario is similar to D2D networks ple types of helpers. with fixed contact patterns.This problem can be formulated as a The rest of this paper is organized as follows:Section 2 reviews set cover problem that is NP-hard [21].Utility based replication al- related works in D2D content dissemination and Section 3 intro- gorithm is used in 22]to distribute mobile videos via human mo- duces the system model used in this paper.Section 4 analyzes the bility between fixed venues.In [23].Chen et al.propose a new file D2D offloading efficiency for relays and shows that on-demand re- replica optimization algorithm that considers both the node stor- lays can asymptotically increase the amount of content supported age and contact frequency. by the system.The storage assignment problem is described in In comparison,we study tradeoffs between using storage for re- Section 5 and the benefits of our scheme are shown by numerical laying and static caching under the D2D scenario.Our model com- results and trace-driven simulations in Section 6.Finally,Section 7 bines static caching systems [5,6]and message relaying methods in presents conclusions of this work. DTN[24].Unlike the traditional DTN routing problems,which only consider cache size in the asymptotical sense [8].we study cache utility with finite storage in the offloading system.In contrast to 2.Related work traditional DTN systems,where the source tries to find a best way to replicate the message,our system adopts a destination centric Message delivery in opportunistic networks:Opportunistic model,where the destination actively searches for the content. networks utilize the intermittent connection between mobile de- vices to transfer data from the source to the destination [7.For 3.Network model message delivery applications,the source first replicates the mes- sage to several relays using short-range links.Relays then deliver 3.1.System overview the message to the destination when they contact the destina- tion [8,9].Most research works in message delivery applications The D2D offloading system studied in this paper combines two consider how to reduce the end-to-end delay under storage con- communication networks:a cellular network and an opportunistic straints in relays [10-12].The content offloading systems studied in network of D2D communication,as shown in Fig 1.The cellular this paper are different to message delivery applications,since the network provides pervasive network coverage and a global com- initial request comes from the destination rather than the source. munication channel for all mobiles.Due to the high cost of cellular

46 W. Wang et al. / Computer Communications 83 (2016) 45–55 there is a relay deployed at the subway station, this relay can ac￾tively search for the content requested by the subscriber and make sure the content can be delivered when the user passes by. Our analysis shows that using one relay with regular contact patterns can be as effective as increasing the number of seeds by a constant ratio. An important issue in a relaying system is to allocate storage for content. Because users can choose to statically cache the content or dynamically download new content for their friends, mobile relays and seeds are actually different roles played by the same group of helpers. In this way, relays and seeds need to share the lim￾ited storage resources in mobile helpers and storage allocation be￾comes critical to the performance of the offloading system. When too many helpers are acting as seeds, there will be an insufficient amount of relays to “ferry” content between seeds and subscribers. Conversely, if there were too few seeds storing the requested con￾tent, it would be difficult for relays to find a seed, making relaying useless. To find the optimal tradeoff point, we introduce the con￾cept of offloading efficiency to incorporate mobile relays and seeds in the same optimization framework. We prove that the storage optimization problem is convex for various types of contact pat￾terns and can be efficiently solved in a distributed manner. Our numerical and trace-driven results show that relaying can reduce the offloading failure rate by more than 30% in D2D systems. The main contributions of this paper are as follows: 1. We propose a new content download pattern that uses relays in addition to traditional seeds to improve the scalability of D2D offloading systems. 2. We introduce a storage optimization framework that can be ap￾plied to different types of helpers in D2D offloading systems. 3. Assuming constant helper density and Poisson contact pro￾cesses, we show that offloading systems with n helpers can support (√n) pieces of content when using both relays and seeds, while the amount of content supported by a static caching system is only O(1). 4. We show that the joint storage assignment problem for relays and seeds is convex and can be efficiently solved. Furthermore, our model can be extended to other types of helpers with con￾cave offloading efficiency functions. This leads to a better un￾derstanding of storage allocation when the network has multi￾ple types of helpers. The rest of this paper is organized as follows: Section 2 reviews related works in D2D content dissemination and Section 3 intro￾duces the system model used in this paper. Section 4 analyzes the D2D offloading efficiency for relays and shows that on-demand re￾lays can asymptotically increase the amount of content supported by the system. The storage assignment problem is described in Section 5 and the benefits of our scheme are shown by numerical results and trace-driven simulations in Section 6. Finally, Section 7 presents conclusions of this work. 2. Related work Message delivery in opportunistic networks: Opportunistic networks utilize the intermittent connection between mobile de￾vices to transfer data from the source to the destination [7]. For message delivery applications, the source first replicates the mes￾sage to several relays using short-range links. Relays then deliver the message to the destination when they contact the destina￾tion [8,9]. Most research works in message delivery applications consider how to reduce the end-to-end delay under storage con￾straints in relays [10–12]. The content offloading systems studied in this paper are different to message delivery applications, since the initial request comes from the destination rather than the source. Fig. 1. Illustration of the communication model. Information searching in opportunistic networks: Content of- floading systems focus on reducing the data delivery cost for a given set of content [5,6,13–16]. As contents are cached in a dis￾tributed way, one important issue in content offloading systems is to search information in a network with dynamic topology and intermittent connections. User interests and network structures can be used to help the content searching process. SPOON uti￾lizes interest based searching to improve the performance of P2P file sharing [17]. Social contact information is utilized in [18] to find the optimal caching point based on user interests. Seeker￾Assisted Searching (SAS) use seekers to help node to search infor￾mation, while assuming users with the same interest meets more frequently [19]. Optimal searching strategy in linear opportunistic networks is studied in [20]. Replication optimization in opportunistic networks: The goal of optimal content replication is to maximize the social welfare, which is defined as the expected utility gain from offloading. Delay-utility models are introduced in [5] to describe the impa￾tience of subscribers. The utility optimization problem is shown to be NP-hard [5,6]. There are several ways to obtain approximate solutions, including greedy heuristic algorithms [6], convex relax￾ation [5] and a distributed algorithm based on voting [13]. Dis￾tributed caching in Femtocells is considered in [21]. The storage allocation problem under this scenario is similar to D2D networks with fixed contact patterns. This problem can be formulated as a set cover problem that is NP-hard [21]. Utility based replication al￾gorithm is used in [22] to distribute mobile videos via human mo￾bility between fixed venues. In [23], Chen et al. propose a new file replica optimization algorithm that considers both the node stor￾age and contact frequency. In comparison, we study tradeoffs between using storage for re￾laying and static caching under the D2D scenario. Our model com￾bines static caching systems [5,6] and message relaying methods in DTN [24]. Unlike the traditional DTN routing problems, which only consider cache size in the asymptotical sense [8], we study cache utility with finite storage in the offloading system. In contrast to traditional DTN systems, where the source tries to find a best way to replicate the message, our system adopts a destination centric model, where the destination actively searches for the content. 3. Network model 3.1. System overview The D2D offloading system studied in this paper combines two communication networks: a cellular network and an opportunistic network of D2D communication, as shown in Fig 1. The cellular network provides pervasive network coverage and a global com￾munication channel for all mobiles. Due to the high cost of cellular

W.Wang et aL/Computer Communications 83(2016)45-55 communication,it is mainly used for control message exchange Section 4.2.Relays are notified through the cellular network and content delivery traffic is offloaded through D2D communi- when they are selected.Each relay then reserves relay storage cation.D2D communication leverages opportunistic short-range segments for this downloading session and starts searching for links formed between nearby mobiles to reduce content delivery the given content.As the notification is sent through the cellu- cost.The links used for D2D communication can be WiFi Direct. lar network,the delay of the notification process can be ignored Bluetooth,LTE/LTE-A,etc.Compared to directly communicating compared to the delay of D2D offloading. with the base station,these short-range links are usually faster, 2.Relays try to replicate the requested content in the reserved re- consumes less energy and free of mobile data charges.For exam- lay storage when contact a seed.The content is replicated to ple,LTE only provides 300 Mbps shared transmission rate,while the relay via short range D2D links. the 802.11ac protocol used by WiFi provides transmission rate 3.When the subscriber contacts a seed or a relay that has already higher than 500 Mbps [25.Real-world measurements also show replicated the content,the subscriber can download the content that WiFi is 14.5 times and 23 times more energy efficient than through D2D links.We call this as an offloading success. 3G and LTE,respectively [26].However,these D2D links have short 4.If the subscriber becomes impatient before reaching any seed communication ranges.For example,WiFi only has communication or relay with the requested content,he/she will directly down- range up to 100 m.Therefore,short-range links only exist when load the content through the cellular network.We call this as mobiles move close to each other,and subscribers may become an offloading failure. impatient before they can find a D2D transmission opportunity[5] 5.Relays receive notifications when the offloading process suc- One important issue for D2D systems is to encourage nodes to ceeds or fails.The storage reserved for the downloading session act as helpers.Helpers contribute their storage as content caches is then released. and allow other nodes to download content from them through D2D links.Therefore,users should have motivations to contribute The advantage of the above on-demand relaying scheme is that storage and battery power of their devices.Helpers may come from it only uses the cellular network to deliver a small amount of con- two sources:mobile devices provided by users and special devices trol information,while the content replications are delivered by deployed by the network operator.The incentive for mobile helpers D2D links between seeds and relays,so the overall relaying cost may come from discounts or other benefits provided by the net- is negligible.Mobile helpers acting as relays also do not consume work operator.Such mechanisms have been well studied in exist- significantly more energy or bandwidth than those acting as seeds, ing work,e.g.[27].In D2D system.it is also possible to utilize because the only extra cost for relays is to receive the control social connections to provide incentives for helpers.For example, message.Note that our relaying scheme is different from relaying users may ask their friends to help them in content downloading. schemes in traditional DTN networks [8.10-12].which mainly fo- Note that incentive schemes developed for traditional D2D offload- cus on point-to-point message delivery rather than content distri- ing systems can be directly applied to our system,as our system bution. do not incur higher storage and energy cost to helpers than tradi tional offloading schemes. 3.2.System model Network operators are also willing to deploy helpers to offload the traffic of cellular systems so that they do not need to contin- We assume that content in the system is divided into segments uously deploy more base stations to handle the increasing traf- with lengths of M.Such a segmentation mechanism is commonly fic.These helpers can be mobile nodes mounted on buses [28 used in streaming and content delivery systems [29].Typical val- or fixed caching points on Femtocells [21].As D2D helpers do ues for segment lengths are 1 to 2 M Bytes.Segments of the same not need high-throughput backhaul,deployment of D2D helpers is file are treated as if they are independent pieces of content,so we much easier than deploying small base stations,e.g,microcells or use the term "content"instead of segments in the rest of this pa- picocells.The advantage of these specialized helpers is that they per.Therefore,it is possible that the user downloads some of the can provide heterogeneous mobility patterns,and it is easier for segments of a given file using the offloading system,while other network operators to optimize the content distribution process on segments of the same file are directly downloaded from the cellu- specialized devices lar network. Different types of helpers can coexist in D2D offloading sys- We assume that there are N pieces of content in the system and tems.Helpers with different mobility patterns,storage sizes or de- that each content i has a mean request rate of Ri.We further as- livery strategies may lead to different performance tradeoffs.In sume that the contact duration between nodes is long enough so this paper,we mainly focus on two types of helpers:Firstly,seeds that at least one segment can be downloaded during the contact are stable content caches that serve for all requests to a given period.As short-range links normally have high transmission rate content.The system allocates a certain number of seeds for each e.g.WiFi has transmission rates from 54-500 Mbps and Bluetooth piece of content to ensure the availability of content.Secondly,re- has rate of 24 Mbps,it takes less than one second to transmit a lays are temporary storage allocated for a specific request.They single segment.Thus,the duration for content transmission is neg- are selected according to the information of the given request to ligible compared to the durations of the contacts,which have av- enhance storage utility.The content cached in relays may dynami- erage length of 370 s [30].Systems with limited contact durations cally change due to arrival or completion of relaying requests.Note can be further optimized using schemes described in [31. that a single node may act as different roles at the same time:it Contacts between nodes are assumed to be independent non- may have part of its storage used as seeds and part of its storage lattice renewal processes.Our model covers most of the existing used as relays. mobility models,which assume that the contact patterns are Pois- Relaying procedure: son processes or have power-law inter-contact times [5,321.In the The content downloading process for a system with both seeds later part of this paper,we may further limit the contact processes and relays is described as follows: to be only Poisson processes,which have been verified by real- world traces [33]as well as theoretical analysis [32].To verify our 1.A subscriber sends a content request to the cellular operator. model in real systems,we also use real-world traces in our exper- Either the operator or the subscriber can select some relays iments,see Section 6.2.In real-world,contact processes between among all available relays to help the subscriber downloading different types of nodes can have different inter-contact time dis- the content.Detailed relay selection procedure is described in tributions.For example,the contact process between relays and

W. Wang et al. / Computer Communications 83 (2016) 45–55 47 communication, it is mainly used for control message exchange and content delivery traffic is offloaded through D2D communi￾cation. D2D communication leverages opportunistic short-range links formed between nearby mobiles to reduce content delivery cost. The links used for D2D communication can be WiFi Direct, Bluetooth, LTE/LTE-A, etc. Compared to directly communicating with the base station, these short-range links are usually faster, consumes less energy and free of mobile data charges. For exam￾ple, LTE only provides 300 Mbps shared transmission rate, while the 802.11ac protocol used by WiFi provides transmission rate higher than 500 Mbps [25]. Real-world measurements also show that WiFi is 14.5 times and 23 times more energy efficient than 3G and LTE, respectively [26]. However, these D2D links have short communication ranges. For example, WiFi only has communication range up to 100 m. Therefore, short-range links only exist when mobiles move close to each other, and subscribers may become impatient before they can find a D2D transmission opportunity [5]. One important issue for D2D systems is to encourage nodes to act as helpers. Helpers contribute their storage as content caches and allow other nodes to download content from them through D2D links. Therefore, users should have motivations to contribute storage and battery power of their devices. Helpers may come from two sources: mobile devices provided by users and special devices deployed by the network operator. The incentive for mobile helpers may come from discounts or other benefits provided by the net￾work operator. Such mechanisms have been well studied in exist￾ing work, e.g., [27]. In D2D system, it is also possible to utilize social connections to provide incentives for helpers. For example, users may ask their friends to help them in content downloading. Note that incentive schemes developed for traditional D2D offload￾ing systems can be directly applied to our system, as our system do not incur higher storage and energy cost to helpers than tradi￾tional offloading schemes. Network operators are also willing to deploy helpers to offload the traffic of cellular systems so that they do not need to contin￾uously deploy more base stations to handle the increasing traf- fic. These helpers can be mobile nodes mounted on buses [28] or fixed caching points on Femtocells [21]. As D2D helpers do not need high-throughput backhaul, deployment of D2D helpers is much easier than deploying small base stations, e.g., microcells or picocells. The advantage of these specialized helpers is that they can provide heterogeneous mobility patterns, and it is easier for network operators to optimize the content distribution process on specialized devices. Different types of helpers can coexist in D2D offloading sys￾tems. Helpers with different mobility patterns, storage sizes or de￾livery strategies may lead to different performance tradeoffs. In this paper, we mainly focus on two types of helpers: Firstly, seeds are stable content caches that serve for all requests to a given content. The system allocates a certain number of seeds for each piece of content to ensure the availability of content. Secondly, re￾lays are temporary storage allocated for a specific request. They are selected according to the information of the given request to enhance storage utility. The content cached in relays may dynami￾cally change due to arrival or completion of relaying requests. Note that a single node may act as different roles at the same time: it may have part of its storage used as seeds and part of its storage used as relays. Relaying procedure: The content downloading process for a system with both seeds and relays is described as follows: 1. A subscriber sends a content request to the cellular operator. Either the operator or the subscriber can select some relays among all available relays to help the subscriber downloading the content. Detailed relay selection procedure is described in Section 4.2. Relays are notified through the cellular network when they are selected. Each relay then reserves relay storage segments for this downloading session and starts searching for the given content. As the notification is sent through the cellu￾lar network, the delay of the notification process can be ignored compared to the delay of D2D offloading. 2. Relays try to replicate the requested content in the reserved re￾lay storage when contact a seed. The content is replicated to the relay via short range D2D links. 3. When the subscriber contacts a seed or a relay that has already replicated the content, the subscriber can download the content through D2D links. We call this as an offloading success. 4. If the subscriber becomes impatient before reaching any seed or relay with the requested content, he/she will directly down￾load the content through the cellular network. We call this as an offloading failure. 5. Relays receive notifications when the offloading process suc￾ceeds or fails. The storage reserved for the downloading session is then released. The advantage of the above on-demand relaying scheme is that it only uses the cellular network to deliver a small amount of con￾trol information, while the content replications are delivered by D2D links between seeds and relays, so the overall relaying cost is negligible. Mobile helpers acting as relays also do not consume significantly more energy or bandwidth than those acting as seeds, because the only extra cost for relays is to receive the control message. Note that our relaying scheme is different from relaying schemes in traditional DTN networks [8,10–12], which mainly fo￾cus on point-to-point message delivery rather than content distri￾bution. 3.2. System model We assume that content in the system is divided into segments with lengths of M. Such a segmentation mechanism is commonly used in streaming and content delivery systems [29]. Typical val￾ues for segment lengths are 1 to 2 M Bytes. Segments of the same file are treated as if they are independent pieces of content, so we use the term “content” instead of segments in the rest of this pa￾per. Therefore, it is possible that the user downloads some of the segments of a given file using the offloading system, while other segments of the same file are directly downloaded from the cellu￾lar network. We assume that there are N pieces of content in the system and that each content i has a mean request rate of Ri. We further as￾sume that the contact duration between nodes is long enough so that at least one segment can be downloaded during the contact period. As short-range links normally have high transmission rate, e.g., WiFi has transmission rates from 54–500 Mbps and Bluetooth has rate of 24 Mbps, it takes less than one second to transmit a single segment. Thus, the duration for content transmission is neg￾ligible compared to the durations of the contacts, which have av￾erage length of 370 s [30]. Systems with limited contact durations can be further optimized using schemes described in [31]. Contacts between nodes are assumed to be independent non￾lattice renewal processes. Our model covers most of the existing mobility models, which assume that the contact patterns are Pois￾son processes or have power-law inter-contact times [5,32]. In the later part of this paper, we may further limit the contact processes to be only Poisson processes, which have been verified by real￾world traces [33] as well as theoretical analysis [32]. To verify our model in real systems, we also use real-world traces in our exper￾iments, see Section 6.2. In real-world, contact processes between different types of nodes can have different inter-contact time dis￾tributions. For example, the contact process between relays and

W.Wang et aL /Computer Communications 83 (2016)45-55 subscribers may be different from that between seeds and sub- and relays can deliver contents to the subscriber via short range scribers. links.The efficiency of the seed only depends on the contact pro- We assume that there are n helpers willing to contribute their cess between subscribers and seeds.However,the efficiency of the storage.We assume that the storage contributed by each helper is relay is dependent on the number of seeds,in addition to the con- able to hold I pieces of content.This assumption can be relaxed tact process between subscribers and relays.This is because re- and will be discussed in Section 5.The storage in helpers can be lays need to first download the content from seeds before they can used as either seeds or relays.We use nsi and n.i to represent the transmit it to the subscribers. number of seeds and relays used by offloading sessions for content We first consider the offloading efficiency of a single relay node. When the contact pattern and number of seeds are known,the We define the offloading failure probability as the probability efficiency of the relays can be calculated as follows: that the subscriber cannot discover the content through D2D com- munication within a given time period of T.To evaluate the effi- Theorem 1.Suppose there are ns.i seeds for content i,and the inter- ciency of a single helper,we define the offloading efficiency Es of contact time between seeds and relays follows a Cumulative Distribu- a single seed as follows: tion Function (CDF)of Y(t)with a mean of uy.If the inter-contact time between relay and subscriber follows CDF of X(t)with a mean Es =-In Ps. (1) of ux,then the offloading efficiency of the relay node for content i is where Ps is the probability that the subscriber cannot receive the given by: content from that particular seed.A higher offloading efficiency means that the seed is more efficient in transmitting the content E,=-ln()- (T-t)"dx( (4) through the D2D link.Similarly.we define the efficiency of a relay Er as-In P.where P,is the probability that the subscriber cannot where: receive the content from the given relay.Table 1 summarizes the symbols used in this paper. (t)=1 As the offloading failure probability depends on the size of the (-X()dr/u (5) cache allocated for the given content,it is a function of the number of relays and seeds for content i.We denote the offloading failure probability for content i as Fnn).Therefore,the total amount Y)=1-(1-Y(t)dr1y (6) of traffic offloaded by D2D communication can be written as: Proof.There are two cases that the given relay will fail to deliver N D=>MRi(1-F(ns.i.nr.i)). (2) the content. (i).The relay never meets the subscriber within time T.For non-lattice renewal processes,the CDF of the time between a For example,suppose that the contact process between a seed randomly picked time point t and the next contact is given by and a subscriber is a Poisson process with a rate of As.Then,the (1-X())dr/ux [34].Therefore,the probability that the relay probability that the seed cannot meet the subscriber during the never meets the subscriber within time T is given by time period of T is given by e-T.Consequently.the offloading ef- ficiency of a single seed is Es =AsT. (T)=1- (1-X(t)dt/μx: (7) Offloading fails when all the ns.i seeds and n.i relays are un- 0 able to deliver the content to the subscriber.When contacts be- (ii).The relay meets the subscriber within time T,but it never tween different pairs of nodes are independent,the event that the meets any seed before the last contact with the subscriber.Sup- given seed or relay can successfully deliver the content is also in- pose that last contact between the relay and the subscriber hap- dependent of other relays/seeds.Therefore,we can multiply the pens in(T-t.T-t+dt),with 0<t<T.The CDF of the time du- failure probability of a single seed/relay to get: ration from last contact to the point of request expiration (at time F(ns.i.nr.)=e-nse-nE =p prd (3) T)is the age distribution of the renewal process.Therefore,the probability that the last contact happens in(T-t.T-t+dt)(with Eq.(3)allows us to directly compare the efficiency of relays and seeds.When there are more than two types of helpers,the offload- age of t at the point of request expire)can be given by-dX(t).Be- cause the probability that the relay does not meet any of the ns.i ing failure probability can be written in a similar way.For details, please refer to Section 5.3. seeds before T-t is given by ((T-t))"s.the probability for the Existing studies that use the static caching model are special second failure case is given by: cases of our system model in Eg.(3).When there are only seeds, we have F(ns..)=P.For a Poisson process with a rate of s. (Y(T-t))""dx(t). (8) we have F(ns..0)=e-mT,which is the same as the results of static caching systems 5.6]. Taking the sum of the failure probability of case (i)and (ii) and translating it into offloading efficiency,we get the result of 4.On-demand relaying in D2D systems Theorem1.▣ Similarly.the offloading efficiency of seeds can be written as: 4.1.Offloading efficiency for helpers Es=-InP=-InY(T) (9) We study the offloading efficiency of our relaying scheme in From Theorem 1,we can see that the ratio of Er/Es is bounded this section.In the relaying scheme,the identity of the content above by the number of seeds: that the subscriber is searching for is delivered to relays through the cellular network.Therefore,only two contacts are needed in Corollary 1.The efficiency ratio of Er/Es is bounded above by ns.i our relaying scheme.In contrast,traditional relaying scheme re- quires three contacts with an extra contact between the subscriber Proof.Because both X(t)and Y(t)are Complementary Cumula- and the relay to deliver the identity of the content.Both the seed tive Distribution Function (CCDF)for age distribution of a renewal

48 W. Wang et al. / Computer Communications 83 (2016) 45–55 subscribers may be different from that between seeds and sub￾scribers. We assume that there are n helpers willing to contribute their storage. We assume that the storage contributed by each helper is able to hold I pieces of content. This assumption can be relaxed and will be discussed in Section 5. The storage in helpers can be used as either seeds or relays. We use ns, i and nr, i to represent the number of seeds and relays used by offloading sessions for content i. We define the offloading failure probability as the probability that the subscriber cannot discover the content through D2D com￾munication within a given time period of T. To evaluate the effi- ciency of a single helper, we define the offloading efficiency Es of a single seed as follows: Es = − ln Ps, (1) where Ps is the probability that the subscriber cannot receive the content from that particular seed. A higher offloading efficiency means that the seed is more efficient in transmitting the content through the D2D link. Similarly, we define the efficiency of a relay Er as − ln Pr, where Pr is the probability that the subscriber cannot receive the content from the given relay. Table 1 summarizes the symbols used in this paper. As the offloading failure probability depends on the size of the cache allocated for the given content, it is a function of the number of relays and seeds for content i. We denote the offloading failure probability for content i as F(ns, i, nr, i). Therefore, the total amount of traffic offloaded by D2D communication can be written as: D = N i=1 MRi(1 − F (ns,i, nr,i)). (2) For example, suppose that the contact process between a seed and a subscriber is a Poisson process with a rate of λs. Then, the probability that the seed cannot meet the subscriber during the time period of T is given by e−λsT . Consequently, the offloading ef- ficiency of a single seed is Es = λsT. Offloading fails when all the ns, i seeds and nr, i relays are un￾able to deliver the content to the subscriber. When contacts be￾tween different pairs of nodes are independent, the event that the given seed or relay can successfully deliver the content is also in￾dependent of other relays/seeds. Therefore, we can multiply the failure probability of a single seed/relay to get: F (ns,i, nr,i) = e−ns,iEse−nr,iEr = Pns,i s Pnr,i r . (3) Eq. (3) allows us to directly compare the efficiency of relays and seeds. When there are more than two types of helpers, the offload￾ing failure probability can be written in a similar way. For details, please refer to Section 5.3. Existing studies that use the static caching model are special cases of our system model in Eq. (3). When there are only seeds, we have F (ns,i, 0) = P ns,i s . For a Poisson process with a rate of λs, we have F (ns,i, 0) = e−ns,iλsT , which is the same as the results of static caching systems [5,6]. 4. On-demand relaying in D2D systems 4.1. Offloading efficiency for helpers We study the offloading efficiency of our relaying scheme in this section. In the relaying scheme, the identity of the content that the subscriber is searching for is delivered to relays through the cellular network. Therefore, only two contacts are needed in our relaying scheme. In contrast, traditional relaying scheme re￾quires three contacts with an extra contact between the subscriber and the relay to deliver the identity of the content. Both the seed and relays can deliver contents to the subscriber via short range links. The efficiency of the seed only depends on the contact pro￾cess between subscribers and seeds. However, the efficiency of the relay is dependent on the number of seeds, in addition to the con￾tact process between subscribers and relays. This is because re￾lays need to first download the content from seeds before they can transmit it to the subscribers. We first consider the offloading efficiency of a single relay node. When the contact pattern and number of seeds are known, the efficiency of the relays can be calculated as follows: Theorem 1. Suppose there are ns, i seeds for content i, and the inter￾contact time between seeds and relays follows a Cumulative Distribu￾tion Function (CDF) of Y(t) with a mean of μy. If the inter-contact time between relay and subscriber follows CDF of X(t) with a mean of μx, then the offloading efficiency of the relay node for content i is given by: Er = − ln Xˆ(T ) −  T 0  Yˆ(T − t) ns,i dXˆ(t)  , (4) where: Xˆ(t) = 1 −  t 0 (1 − X(τ ))dτ /μx (5) Yˆ(t) = 1 −  t 0 (1 − Y (τ ))dτ /μy. (6) Proof. There are two cases that the given relay will fail to deliver the content. (i). The relay never meets the subscriber within time T. For non-lattice renewal processes, the CDF of the time between a randomly picked time point t and the next contact is given by  t 0 (1 − X(τ ))dτ /μx [34]. Therefore, the probability that the relay never meets the subscriber within time T is given by Xˆ(T ) = 1 −  T 0 (1 − X(τ ))dτ /μx. (7) (ii). The relay meets the subscriber within time T, but it never meets any seed before the last contact with the subscriber. Sup￾pose that last contact between the relay and the subscriber hap￾pens in (T − t, T − t + dt), with 0 ≤ t ≤ T. The CDF of the time du￾ration from last contact to the point of request expiration (at time T) is the age distribution of the renewal process. Therefore, the probability that the last contact happens in (T − t, T − t + dt) (with age of t at the point of request expire) can be given by −dXˆ(t). Be￾cause the probability that the relay does not meet any of the ns, i seeds before T − t is given by  Yˆ(T − t) ns,i , the probability for the second failure case is given by: −  T 0  Yˆ(T − t) ns,i dXˆ(t). (8) Taking the sum of the failure probability of case (i) and (ii) and translating it into offloading efficiency, we get the result of Theorem 1. Similarly, the offloading efficiency of seeds can be written as: Es = − ln Ps = − lnYˆ(T ). (9) From Theorem 1, we can see that the ratio of Er/Es is bounded above by the number of seeds: Corollary 1. The efficiency ratio of Er/Es is bounded above by ns, i. Proof. Because both Xˆ(t) and Yˆ(t) are Complementary Cumula￾tive Distribution Function (CCDF) for age distribution of a renewal

W.Wang et aL/Computer Communications 83(2016)45-55 Table 1 Notations used in this paper. Symbol Description The number of contents The segment length for contents The total number of helpers L The side length for the network region The time before the subscriber becomes impatient The storage size for helpers R Request rate for content i fls.i The number of seeds caching content i The number of relays for content i Es.E Offloading efficiency for one seed or one relay Ps,Pr The probability that subscriber cannot receive content from a seed or relay The subscriber contact rate for seeds and relays X(t) CDF of the inter-contact time between relays and subscribers Y(t) CDF of the inter-contact time between seeds and relays process,which are decreasing functions within range of [0,1].we larger than AT,which means a relay is always less effective than a have: seed when As =Ar.This is reasonable because a relay must down- load the content from the seed before it can deliver it to the sub- R(T)- ((T-t))"d(t) scriber. In summary.the offloading efficiency of relays can reach the ((T-t))"dx(t) upper bound of ns.i times the number of seeds when relays have high contact rates to subscribers.However,relays are less efficient =E(T-t)10≤t≤T than seeds when they have same contact rates as seeds. ≥min(T-t)"1o≤t≤T 4.2.Relay selection =((T) (10) According to the above analysis,relaying through a node with Therefore the same contact pattern as seeds is not helpful.However,D2D contact patterns are inherently non-uniform.The contact processes Er =-In T)- (T-t))Td(t) between different groups of mobile nodes have different contact patterns.As seeds serve for all the subscribers in the network,the ≤-nsiln?(T). (11) contact process between a seed and a subscriber should follow the typical contact pattern between random pairs of nodes.However. AsEs=-lnY(T).we have Er≤ns.iEs.□ relays may have different contact patterns to a given subscriber. We can intentionally select relays for a given offloading request Example:poisson contact process Consider the case where both contact processes are Poisson based on previous knowledge of their contact patterns.For exam- process.We have X(t)=1-e-Art and ux=1/r.where Ar is the ple,a device belonging to a friend of the user or a device mounted rate for the contact process between a relay and the subscriber. at a subway station that the user always passes by,can be selected Similarly,we have Y(t)=1-e-Ast and uy =1/As.Using Eqs.(5) as the relay in order to improve the efficiency of content distribu- and (6),we have(t)=e-t and ?(t)=e-st.We can obtain: tion.As discussed in Section 4.1,the offloading efficiency mainly depends on the contact rates of relays.Therefore,we propose to -In nsi入se-dT-入re-nT select relays based on their contact rates to reduce the relay selec- Er ns.is-入 入r≠ns.i入s (12) tion complexity. λrT-ln(1+rT) 入r=几s.i入s The relay selection process can be carried out either by the net- work operator or by the subscriber.When the relay is selected by Note that the sum of two exponentially distributed inter-contact the network operator,the network operator needs to record the times actually follows a hypoexponential distribution as expected. top-k nodes with the highest contact rates for each subscriber. Eq.(12)shows some characteristics of the offloading efficiency Such records can also be generated by the user devices and sub- for relay nodes. mitted to the operator along with the offloading request.These (i)When r ns.is,Er approaches ns.isT.Compared to the nodes will have higher contact rate to the subscriber compared to offloading efficiency of the seed Es =AsT.we see that a single relay randomly selected nodes. has the same efficiency as ns i seeds.where the upper bound in To verify the existence of nodes with higher contact rates,we Corollary 1 is achieved.Therefore,for rare content with low ns.i. studied the MIT reality trace [35],which contains Bluetooth traces using nr.i frequently contacting relays to download the content can from 100 mobiles for more than 9 months.Fig.2 shows the CDF of have effects similar to multiplying nsi by nr.i. the contact rates for the top-k frequently contacted neighbors for (ii)When a relay has the same contact pattern to the subscriber each mobile,normalized by the average contact rate.We see that as seeds,i.e,入r=λs=入，we have a relay offloading efficiency more than 90%of the subscribers have at least 5 neighbors with of a contact rate 10 times higher than average.More than 80%sub- scribers have 10 neighbors with contact rates 10 times higher than Er=入T+ln ns.i-1 几.i-e-(a4-1)x7 (13) average.Similar distributions of frequently contacted neighbors are also observed in recently collected traces as in [36]. Note that we have ns.-1s ns.i-e-(ns-)AT when ns.i 1.Thus Relays can also be selected by the subscribers.A subscriber the second term in Eq.(13)is always negative and Er can never be can request friends or colleagues to help with downloading.As

W. Wang et al. / Computer Communications 83 (2016) 45–55 49 Table 1 Notations used in this paper. Symbol Description N The number of contents M The segment length for contents n The total number of helpers L The side length for the network region T The time before the subscriber becomes impatient I The storage size for helpers Ri Request rate for content i ns, i The number of seeds caching content i nr, i The number of relays for content i Es , Er Offloading efficiency for one seed or one relay Ps , Pr The probability that subscriber cannot receive content from a seed or relay λs , λr The subscriber contact rate for seeds and relays X(t) CDF of the inter-contact time between relays and subscribers Y(t) CDF of the inter-contact time between seeds and relays process, which are decreasing functions within range of [0, 1], we have: Xˆ(T ) −  T 0  Yˆ(T − t) ns,i dXˆ(t) ≥ −  T 0  Yˆ(T − t) ns,i dXˆ(t) = E  Yˆ(T − t) ns,i |0 ≤ t ≤ T ≥ min  Yˆ(T − t) ns,i |0 ≤ t ≤ T =  Yˆ(T ) ns,i . (10) Therefore, Er = − ln Xˆ(T ) −  T 0  Yˆ(T − t) ns,i dXˆ(t)  ≤ −ns,i lnYˆ(T ). (11) As Es = − lnYˆ(T ), we have Er ≤ ns, iEs. Example: poisson contact process Consider the case where both contact processes are Poisson process. We have X(t) = 1 − e−λrt and μx = 1/λr, where λr is the rate for the contact process between a relay and the subscriber. Similarly, we have Y (t) = 1 − e−λst and μy = 1/λs. Using Eqs. (5) and (6), we have Xˆ(t) = e−λrt and Yˆ(t) = e−λst. We can obtain: Er = ⎧ ⎨ ⎩ − lnns,iλse−λrT − λre−ns,iλsT ns,iλs − λr  λr = ns,iλs λrT − ln(1 + λrT ) λr = ns,iλs . (12) Note that the sum of two exponentially distributed inter-contact times actually follows a hypoexponential distribution as expected. Eq. (12) shows some characteristics of the offloading efficiency for relay nodes. (i) When λr  ns, iλs, Er approaches ns, iλsT. Compared to the offloading efficiency of the seed Es = λsT, we see that a single relay has the same efficiency as ns, i seeds, where the upper bound in Corollary 1 is achieved. Therefore, for rare content with low ns, i, using nr, i frequently contacting relays to download the content can have effects similar to multiplying ns, i by nr, i. (ii) When a relay has the same contact pattern to the subscriber as seeds, i.e., λr = λs = λ, we have a relay offloading efficiency of: Er = λT + ln ns,i − 1 ns,i − e−(ns,i−1)λT  . (13) Note that we have ns,i − 1 ≤ ns,i − e−(ns,i−1)λT when ns, i ≥ 1. Thus the second term in Eq. (13) is always negative and Er can never be larger than λT, which means a relay is always less effective than a seed when λs = λr. This is reasonable because a relay must down￾load the content from the seed before it can deliver it to the sub￾scriber. In summary, the offloading efficiency of relays can reach the upper bound of ns, i times the number of seeds when relays have high contact rates to subscribers. However, relays are less efficient than seeds when they have same contact rates as seeds. 4.2. Relay selection According to the above analysis, relaying through a node with the same contact pattern as seeds is not helpful. However, D2D contact patterns are inherently non-uniform. The contact processes between different groups of mobile nodes have different contact patterns. As seeds serve for all the subscribers in the network, the contact process between a seed and a subscriber should follow the typical contact pattern between random pairs of nodes. However, relays may have different contact patterns to a given subscriber. We can intentionally select relays for a given offloading request based on previous knowledge of their contact patterns. For exam￾ple, a device belonging to a friend of the user or a device mounted at a subway station that the user always passes by, can be selected as the relay in order to improve the efficiency of content distribu￾tion. As discussed in Section 4.1, the offloading efficiency mainly depends on the contact rates of relays. Therefore, we propose to select relays based on their contact rates to reduce the relay selec￾tion complexity. The relay selection process can be carried out either by the net￾work operator or by the subscriber. When the relay is selected by the network operator, the network operator needs to record the top-k nodes with the highest contact rates for each subscriber. Such records can also be generated by the user devices and sub￾mitted to the operator along with the offloading request. These nodes will have higher contact rate to the subscriber compared to randomly selected nodes. To verify the existence of nodes with higher contact rates, we studied the MIT reality trace [35], which contains Bluetooth traces from 100 mobiles for more than 9 months. Fig. 2 shows the CDF of the contact rates for the top-k frequently contacted neighbors for each mobile, normalized by the average contact rate. We see that more than 90% of the subscribers have at least 5 neighbors with a contact rate 10 times higher than average. More than 80% sub￾scribers have 10 neighbors with contact rates 10 times higher than average. Similar distributions of frequently contacted neighbors are also observed in recently collected traces as in [36]. Relays can also be selected by the subscribers. A subscriber can request friends or colleagues to help with downloading. As