臺灣博碩士論文加值系統

在本篇論文中，我們研究了在無線網絡中，基站（BS）具有有限緩存空間以及未知的內容熱門程度的延遲感知合作線上內容緩存機制。我們提出了一種在不需要知道內容熱門程度的多BS合作系統中進行合作緩存的線上演算法。當來自用戶的新請求到達BS時，如果所請求的內容已經被BS緩存在其存儲空間中，則BS通過直接傳送來滿足此請求;否則，BS向移動性管理實體（MME）發送訊息以啟動線上內容緩存機制，於是所提出的合作線上內容緩存演算法（COCA）決定在哪個BS中應該緩存所請求的內容，考慮三個重要的因素：每個BS中的殘餘緩存存儲空間、每個BS連接其他BS的數量、以及每個BS中服務用戶的數量。另外，由於BS中的儲存空間有限，所提出的COCA演算法必須消除最近最少使用的（LRU）內容來釋放其空間。

我們透過模擬比較了所提出的COCA演算法與離線合作緩存模式的延遲表現。模擬結果顯示，COCA演算法具有比離線模式更好的延遲表現。

In this thesis, we study a delay-aware cooperative online content caching mechanism in wireless networks with limited caching space in each base station (BS) and unknown popularity of the contents. An online algorithm is proposed for cooperative caching in multi-BS coordinated systems that does not require any knowledge of the contents popularities. When a new request from a user arrives at a BS, the BS responds the request by direct delivery if the requested content is currently cached in its storage space; otherwise, the BS sends a message to the Mobility Management Entity (MME) to initiate the online content caching mechanism. The proposed cooperative online content caching algorithm (COCA) then decides in which BS the requested content should be cached with considerations of three important factors: the residual cache storage space in each BS, the number of coordinated connections each BS is involved with other BSs, and the number of served users in each BS. In addition, due to limited storage space in the cache, the proposed COCA algorithm eliminates the least recently used (LRU) contents to free up the space.

1 Introduction 1
1.1 Signicance................................ 1
1.2 Motivation................................. 2
1.3 RelatedWork............................... 3
1.4 ContributionsoftheResearch...................... 3
2 Preliminaries 5
2.1 ContentDeliveryNetworks(CDNs)................... 5
2.1.1 ContentCachingDeliveryTechniques.............. 6
2.1.2 CooperativeCaching....................... 9
2.1.3 OfflinecachingversusOnlinecaching.............. 10
2.2 Contentpopularity............................ 12
2.2.1 Zipf'slaw[1]........................... 12
2.2.2 Zipfdistribution......................... 12
2.3 CacheReplacementPolicies....................... 15
2.3.1 FirstinFirstOut(FIFO).................... 15
2.3.2 LeastRecentlyUsed(LRU)................... 16
2.3.3 LeastFrequentlyUsed(LFU).................. 16
3 CooperatvieBaseStationContentCaching 17
3.1 SystemModel............................... 17
3.2 ProblemFormulation........................... 18
3.3 DelayPerformancewithOnlineCaching................ 21
3.3.1 Implementation.......................... 21
3.3.2 TheCooperativesmallcellBSContentCachingwithOnline
Algorithm ............................. 21
4 Simulations 25
4.1 SimulationSetup............................. 25
4.2 Offlinecontentcachingalgorithm.................... 27
4.3 SimulationResults............................ 28
4.3.1 AverageDelayofeachuser.................... 28
4.3.2 AverageDelayofusersindifferentsmallcellBSs....... 31
4.3.3 ContentHitProbability..................... 31
4.3.4 Averagedelaywithwitherrorsinestimatingthecontentspop-
ularities .............................. 32
5 ConclusionandFutureWork 34
5.1 Conclusion................................. 34
5.2 FutureWork................................ 34
Bibliography 36

[1] \Zipf'slaw," https: //en.wikipedia.org/wiki/Zipf%27s_law .
[2] \Contentdeliverynetwork," https: //en.wikipedia.org/wiki/Content_
delivery_ network .
[3] C. YangD.Liu,B.ChenandA.F.Molisch,\Cachingatthewirelessedge:
design aspects,challenges,andfuturedirections,"in IEEE Communications
Magazine, Sep2016,vol.54,pp.22{28.
[4] X. Wang,M.Chen,T.Taleb,A.Ksentini,andV.Leung,\Cacheintheair:
Exploiting contentcachinganddeliverytechniquesfor5Gsystems," IEEE
CommunicationsMagazine, vol.52,no.2,pp.131{139,Feb2014.
[5] X. Li,S.XiaoX.Wang,andV.C.M.Leung,\Delayperformanceanalysis
of cooperativecellcachinginfuturemobilenetworks," Proc.IEEEICC, pp.
5652{5657, June2015.
[6] Cisco, \CiscoVisualNetworkingIndex:GlobalMobileDataTrafficForecast
Update,2014-2019,"2015.
[7] M. Cha,H.Kwak,P.Rodriguez,Y.Y.Ahn,andS.Moon,\ITube,YouTube,
EverybodyTubes:AnalyzingtheWorld'sLargestUserGeneratedContent
Video System,"in Usenix/ACMSIGCOMMIMC, Oct2007.
36
[8] A. KhreishahandJ.Chakareski,\Collaborativecachingformulticellcoordi-
nated systems,"in Proc.CNTCV2015,inConjunctionwithIEEEINFOCOM,
2015.
[9] C. Bernardini,T.Silverston,andO.Festor,\MPC:PopularityBasedCaching
Strategy forContentCentricNetworks,"in Proc.IEEEInt.Conf., June2013,
pp. 3619{3623.
[10] Z. Chen,J.Lee,T.Q.S.Quek,andM.Kountouris,\Cluster-centriccache
utilization designincooperativesmallcellnetworks," 2016 IEEEInternational
ConferenceonCommunications(ICC), pp.1{6,2016.
[11] A. Gharaibeh,A.Khreishah,B.Ji,andM.Ayyash,\AProvablyEfficient
Online CollaborativeCachingAlgorithmforMulticell-CoordinatedSystems,"
IEEE Trans.MobileComputing, vol.15,no.8,pp.1863{1876,Sep2016.
[12] P.BlascoandD.Gunduz,\Learning-basedoptimizationofcachecontentina
small cellbasestation,"in Proc.IEEEInt.Conf.Commun., June2014,pp.
1897{1903.
[13] S. H.Chae,J.Y.Ryu,T.Q.S.Quek,andW.Choi,\CooperativeTrans-
mission viaCachingHelpers," 2015 IEEEGlobalCommunicationsConference
(GLOBECOM), pp.1{6,2015.
[14] A. VakaliandG.Pallis,\Contentdeliverynetworks:statusandtrends,"in
IEEE InternetComputing, Nov-Dec2003,vol.7,pp.66{74.
[15] A.F. Molisch,\Wirelesscommunications.," Wiley, 2011.
[16] J. Ermanetal,\ToCacheorNottoCacheThe3GCase," IEEE Internet
[17] B. A.Ramananetal,\CacheabilityAnalysisofHTTPtrafficinanOperational
LTENetwork," WirelessTelecommun.Symp, Apr2013.
[18] B. D.Higginsetal., InformedMobilePrefetching, ACMMobiSys.
[19] A. Tataretal,\ASurveyonPredictingthePopularityofWebContent,"
Springer J.InternetServicesandApplications, vol.5,no.1,pp.1{20,2014.
[20] K. Suksomboonetal.,\PopCache:Cachemoreorlessbasedoncontentpop-
ularityforinformation-centricnetworking," 38th AnnualIEEEConferenceon
LocalComputerNetworks,Sydney,NSW, pp.236{243,2013.
[21] DavidM.W.Powers.,\ApplicationsandExplanationsofZipf'sLaw," Pro-
ceedingsofNewMethodsinLanguageProcessingandComputationalNatural
LanguageLearning, 1998.
[22] \Zipfs distributionexamples," http: //www.math.wm.edu/ ~ leemis/
chart/ UDR/PDFs/Zipf.pdf .
[23] S. MartelloandP.Toth., Knapsack Problems:AlgorithmsandComputerImplementations, JohnandSonsInc.