11 ACKNOWLEDGMENT tradeoffs inherent in the class of scheduling policies in Sec This work was supported by NSF China (No.61532012, II-C.From Lemma 2,for content ik,we can obtain the 61325012,61231010,61271219,61521062.61428205. following relationship among the number of clients ni,the 61401272),National High Technology Research and Devel- average time to serve the clients E [Wi],the average number opment Program of China (No.2015AA015901),and CPSF of servers E[Mi.and the average retrieval area (reflected by funding (No.BX201600056). term E2 Rix.d). REFERENCES E2[R,d4 [1]V.Jacobson,D.K.Smetters,J.D.Thornton,M.F.Plass,N.H.Briggs, d4k=1 and R.L.Braynard,"Networking named content,"in Proc.CoNEXT 1 Rome.Dec.2009 [2]T.Koponen.M.Chawla,B.-G.Chun.A.Ermolinskiy.K.Kim.S.Shenker. di=1 ca(ni-du+1)E M.d EWidig logn and I.Stoica,"A data-oriented (and beyond)network architecture,"in nik Proc.ACM SIGCOMM,Kyoto,Aug.2007. 1 [3]A.Sharma,A.Venkataramani,R.K.Sitaraman,"Distributing content caE Mig]logn din=1 (nix-dix+1)E Wi.dix simplifies ISP traffic engineering."in Proc.ACM SIGMETRICS,Pitts- burgh,Jun.2013. [4]M.Meisel,V.Pappas,and L.Zhang."Ad hoc networking via named 1 之caEM.x]logn （∑- data,"in Proc.ACM MobiArch,Chicago.Illinois,Sep.2010. [5]F.Bai and B.Krishnamachari,"Exploiting the wisdom of the crowd: ∑-：E[w4 canik localized,distributed,information-centric VANETs,"IEEE Communica- 1d.the capy of 之M4回WIog” (33) ad hoc wireless networks,"IEEE/ACM Transactions on Networking.vol. where the second inequality is due to E[MEM 10,no.4,Pp.477-486,Aug.2002. the third inequality is due to Cauchy-Schwartz inequality, [7]S.Toumpis and A.J.Goldsmith,"Large wireless networks under fading. 1 mobility,and delay constraints,"in Proc.IEEE INFOCOM,Hong Kong. and we se之-y5=8Vneo出 Mar.2004. [8]X.Lin and N.B.Shroff."The fundamental capacity-delay tradeoff in inequality.By Holder's inequality,we further have large mobile wireless networks,"in Proc.MedHocNet,Bodrum,Jun (34) 2004. E[R吃，d]≥E[Rk,d [9]L.Ying,S.Yang,and R.Srikant,"Optimal delay-throughput trade-offs in mobile ad hoc networks,"IEEE Transactions on Information Theory, Hence,combining (33),(34)and Lemma 1,we have vol.54,no.9,Pp.4119-4143,Sep.2008 [10]Y.Wang.X.Chu,X.Wang and Y.Cheng."Optimal multicast capacity and delay tradeoffs in MANETs:A global perspective,"in Proc.IEEE INFOCOM,Shanghai,Apr.2011. 1k1 4n 台1k与1d4k=1 [11]M.Garetto and E.Leonardi,"Restricted mobility improves delay- throughput tradeoffs in mobile ad hoc networks,"IEEE Transactions on Information Theory,vol.56,no.10,pp.5016-5029,Oct.2010. EM+奇名名w =1k=1 [12]P.Li.Y.Fang,J.Li,and X.Huang,"Smooth trade-offs between throughput and delay in mobile ad hoc networks,"IEEE Transactions on Mobile Computing,vol.11,no.3,pp.427-438,Mar.2012. [13]S.Gitzenis,G.S.Paschos,and L.Tassiulas,"Asymptotic laws for joint content replication and delivery in wireless networks,"IEEE Transactions √Von logn on Informarion Theory.vol.59.no.5.pp.2760-2776.May.2013. (35) [14]L.Breslau,P.Cao,L.Fan,G.Phillips,and S.Shenker,"Web caching and zipf-like distributions:evidence and implications,"in Proc.IEEE where c4,c5,ce are positive constants.Note that Wo INFOCOM.New York,Mar.1999. EW To make the second and third inequal- [15]P.Gupta and P.R.Kumar,"The capacity of wireless networks,"IEEE Transactions on Information Theory,vol.46,no.2,pp.388-404,Mar. ities hold with equality,we should have i)EWi]=Wo 2000. for all i and,i曲E[Mw】=√Wo log C51 ,·nik,respectively.. [16]B.Azimdoost.C.Westphal,and H.R.Sadjadpour."On the throughput capacity of information-centric networks,"in Proc.IEEE ITC,Shanghai. Substituting (35)into the tradeoff(6)in Lemma 1,we have Sep.2013. I K [17]G.Alfano,M.Garetto and E.Leonardi,"Content-centric wireless networks with limited buffers:when mobility hurts,in Proc./EEE ≤Vo log n.(36) INFOCOM.Turin,Apr.2013. [18]B.Tan and L.Massoulie,"Optimal content placement for peer-to-peer video-on-demand systems."IEEE/ACM Transactions on Networking,vol. 21,no.2,Pp.566-579Apr.2013. SinceK,it is not a dominant factor.Thus,for n [19]M.J.Neely and E.Modiano,"Capacity and delay tradeoffs for ad hoc i=1k=1 mobile networks,"IEEE Transactions on Information Theory,vol.51,no a given request state O,we have 6,Pp.1917-1937.Jun.2005. 2 [20]A.E.Gamal,J.Mammen,B.Prabhakar,and D.Shah,"Throughput- delay trade-off in wireless networks,"in Proc.IEEE INFOCOM.Hong (37) Kong.Mar.2004. log n =1k1 APPENDIX Based on the result of Wo in (37),we now calculate its A.Proof of Theorem I I K The proof of Theorem 1 is mainly based on two key expectation over all request states.Let Sand i=1k=1 inequalities in Lemma 1 and Lemma 2,which capture two u=E[S].Using Chernoff bound,for all 6>0,we have the11 ACKNOWLEDGMENT This work was supported by NSF China (No. 61532012, 61325012, 61231010, 61271219, 61521062, 61428205, 61401272), National High Technology Research and Devel￾opment Program of China (No. 2015AA015901), and CPSF funding (No. BX201600056). REFERENCES [1] V. Jacobson, D. K. Smetters, J. D. Thornton, M. F. Plass, N. H. Briggs, and R. L. Braynard, “Networking named content,” in Proc. CoNEXT, Rome, Dec. 2009 [2] T. Koponen, M. Chawla, B.-G. Chun, A. Ermolinskiy, K. Kim, S. Shenker, and I. Stoica, “A data-oriented (and beyond) network architecture,” in Proc. ACM SIGCOMM, Kyoto, Aug. 2007. [3] A. Sharma, A. Venkataramani, R. K. Sitaraman, “Distributing content simplifies ISP traffic engineering,” in Proc. ACM SIGMETRICS, Pitts￾burgh, Jun. 2013. [4] M. Meisel, V. Pappas, and L. Zhang, “Ad hoc networking via named data,” in Proc. ACM MobiArch, Chicago, Illinois, Sep. 2010. [5] F. Bai and B. Krishnamachari, “Exploiting the wisdom of the crowd: localized, distributed, information-centric VANETs,” IEEE Communica￾tions Magazine, vol. 48, no. 5, pp. 138-146, May 2013. [6] M. Grossglauser and D. N. C. Tse, “Mobility increases the capacity of ad hoc wireless networks,” IEEE/ACM Transactions on Networking, vol. 10, no. 4, pp. 477-486, Aug. 2002. [7] S. Toumpis and A. J. Goldsmith, “Large wireless networks under fading, mobility, and delay constraints,” in Proc. IEEE INFOCOM, Hong Kong, Mar. 2004. [8] X. Lin and N. B. Shroff, “The fundamental capacity-delay tradeoff in large mobile wireless networks,” in Proc. MedHocNet, Bodrum, Jun. 2004. [9] L. Ying, S. Yang, and R. Srikant, “Optimal delay-throughput trade-offs in mobile ad hoc networks,” IEEE Transactions on Information Theory, vol. 54, no. 9, pp. 4119-4143, Sep. 2008. [10] Y. Wang, X. Chu, X. Wang and Y. Cheng, “Optimal multicast capacity and delay tradeoffs in MANETs: A global perspective,” in Proc. IEEE INFOCOM, Shanghai, Apr. 2011. [11] M. Garetto and E. Leonardi, “Restricted mobility improves delay￾throughput tradeoffs in mobile ad hoc networks,” IEEE Transactions on Information Theory, vol. 56, no. 10, pp. 5016-5029, Oct. 2010. [12] P. Li, Y. Fang, J. Li, and X. Huang, “Smooth trade-offs between throughput and delay in mobile ad hoc networks,” IEEE Transactions on Mobile Computing, vol. 11, no. 3, pp. 427-438, Mar. 2012. [13] S. Gitzenis, G. S. Paschos, and L. Tassiulas, “Asymptotic laws for joint content replication and delivery in wireless networks,” IEEE Transactions on Information Theory, vol. 59, no. 5, pp. 2760-2776, May. 2013. [14] L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker, “Web caching and zipf-like distributions: evidence and implications,” in Proc. IEEE INFOCOM, New York, Mar. 1999. [15] P. Gupta and P. R. Kumar, “The capacity of wireless networks,” IEEE Transactions on Information Theory, vol. 46, no. 2, pp. 388-404, Mar. 2000. [16] B. Azimdoost, C. Westphal, and H. R. Sadjadpour, “On the throughput capacity of information-centric networks,” in Proc. IEEE ITC, Shanghai, Sep. 2013. [17] G. Alfano, M. Garetto and E. Leonardi, “Content-centric wireless networks with limited buffers: when mobility hurts,” in Proc. IEEE INFOCOM, Turin, Apr. 2013. [18] B. Tan and L. Massoulie, “Optimal content placement for peer-to-peer video-on-demand systems,” IEEE/ACM Transactions on Networking, vol. 21, no. 2, pp. 566-579, Apr. 2013. [19] M. J. Neely and E. Modiano, “Capacity and delay tradeoffs for ad hoc mobile networks,” IEEE Transactions on Information Theory, vol. 51, no. 6, pp. 1917-1937, Jun. 2005. [20] A. E. Gamal, J. Mammen, B. Prabhakar, and D. Shah, “Throughput￾delay trade-off in wireless networks,” in Proc. IEEE INFOCOM, Hong Kong, Mar. 2004. APPENDIX A. Proof of Theorem 1 The proof of Theorem 1 is mainly based on two key inequalities in Lemma 1 and Lemma 2, which capture two tradeoffs inherent in the class of scheduling policies in Sec II-C. From Lemma 2, for content ik, we can obtain the following relationship among the number of clients nik , the average time to serve the clients E [Wik ], the average number of servers E [Mik ], and the average retrieval area (reflected by term E 2 Rik,dik ). nPik dik =1 E 2 Rik,dik ≥ nPik dik =1 1 c2(nik −dik +1)E Mik,dik E Wik,dik log n ≥ 1 c2E[Mik ] log n nPik dik =1 1 (nik −dik +1)E Wik,dik ≥ 1 c2E[Mik ] log n · Pnik dik =1 √ 1 nik −dik +1 ‹2 Pnik dik =1 E Wik,dik ≥ c3nik E[Mik ]E[Wik ] log n (33) where the second inequality is due to E [Mik ] ≥ E Mik,dik , the third inequality is due to Cauchy-Schwartz inequality, and we use Pnik dik =1 √ 1 nik −dik +1 = Θ €√nik Š in the fourth inequality. By Holder’s inequality, we further have ˝ E[R 2 ik,dik ] ≥ E 2 [Rik,dik ]. (34) Hence, combining (33), (34) and Lemma 1, we have P I i=1 P K k=1 ∆2E[Mik ] 4n + P I i=1 P K k=1 nPik dik =1 π∆2E R 2 ik,dik 4 ≥ c4 n P I i=1 P K k=1 E [Mik ] + c5 log n P I i=1 P K k=1 nik E[Mik ]E[Wik ] ≥ P I i=1 P K k=1  c4 n E [Mik ] + c5 W¯ Q log n nik E[Mik ] ‹ ≥ √ c6 W¯ Qn log n P I i=1 P K k=1 √nik . (35) where c4, c5, c6 are positive constants. Note that W¯ Q = max 1≤i≤I max 1≤k≤K E [Wik ]. To make the second and third inequal￾ities hold with equality, we should have i) E [Wik ] = W¯ Q for all i and k, ii) E [Mik ] = È c5n c4W¯ Q log n · nik , respectively. Substituting (35) into the tradeoff (6) in Lemma 1, we have 1 È W¯ Qn log n X I i=1 X K k=1 √ nik − X I i=1 X K k=1 nik n ≤ W¯ Q log n. (36) Since P I i=1 P K k=1 nik n = K, it is not a dominant factor. Thus, for a given request state Q, we have W¯ Q ≥ Θ „ 1 log n X I i=1 X K k=1 Énik n !2/3Ž . (37) Based on the result of W¯ Q in (37), we now calculate its expectation over all request states. Let S = P I i=1 P K k=1 √nik and µ = E[S]. Using Chernoff bound, for all δ > 0, we have the