臺灣博碩士論文加值系統

由於網路通訊技術的高度發展，往返傳遞的資料日趨龐大，快取演算法的重要性就被突顯出來，透過快取技術我們可以更快速的讀取資料，節省時間。
在本篇論文中，我們提出了一個新型態之檔案模型，根據檔案請求的出現次數及時間順序，給予每個檔案相對應的權重值。檔案模型中含有兩套機制：為檔案衰退率以及檔案比例，檔案衰退率是個零到一之間的小數，在檔案模型更新權重前，將過往的權重乘以此數值，減少過往權重之影響。檔案比例則是一個變數，代表的是每個檔案在本次檔案請求之中所佔據之比例，在使每次所更新之權重，可以依照當下檔案請求做調整。以檔案權重模型為基礎，我們還引進了強化學習之概念，預期可以從歷史紀錄中學習到檔案請求彼此間的關聯性，猜測未來會使用到何種檔案，進而調整其檔案模型之權重，提高快取命中率。
在實驗部分，我們採用了兩種資料集以及五種檔案請求頻率，兩種資料集分別是齊夫定律所產生之資料集以及自定義之離散資料集，由於齊夫定律之資料，檔案頻率太過於集中，我們希望所設計之演算法，也適用於檔案頻率快速變化之場景，故設計此資料集加入實驗。五種檔案請求則可分為兩類做討論，第一類為固定請求數量，第二類為隨機產生之請求數量。
最終做出的實驗結果顯示，與傳統快取演算法中最近最少使用策略(LRU)及做使用頻率最低策略(LFU)比較，在齊夫定律資料集中，這種較集中式之資料集裡，我們所設計之模型不敵傳統演算法，而在離散式之資料集中，則大多是我們提出的演算法獲勝，因為我們的演算法較能學習出資料集的特徵，所以可以適應這類快速變化的離散資料。

Cache algorithms play an important role in the world, because they allow retrieval the data without having to request from the original source. In this study, we propose a novel algorithm which integrates temporal and frequency factors, named file model. File model is used to calculate weight value by the information of each file, such as arrival order and frequency of each file. File model consists of two mechanisms, file proportion variable and file decay coefficient. The former deals with the current file weight, and it reduce all the value of each file according to their proportion in the current data request. The latter focuses on previous file weight and it would reduce all the value of each file as time goes on. Based on the file model, we then propose a reinforcement learning approach to predict file frequency by taking into account the relation between each data request. Numerical results based on two different dataset, zipf’s law dataset and discrete dataset, show that the proposed file weight and learning-based caching algorithm outperforms the traditional caching algorithms in certain schemes, such as the discrete dataset we design.

摘要 I
Extend Abstract II
誌謝 V
內文目錄 VI
表目錄 IX
圖目錄 X
第一章 緒論 1
1.1 研究動機 1
1.2 研究方向與貢獻 2
1.3 章節提要 3
第二章 背景介紹與文獻探討 4
2.1研究背景介紹 4
2.1.1快取介紹 4
2.1.2強化學習範例概述 4
2.2快取節點配置策略 5
2.3快取演算法(Caching Algorithm) 8
2.3.1傳統演算法 8
2.3.2傳統演算法延伸 8
2.3.3近年發展概念 12
2.3.4未來發展 16
第三章 研究方法 18
3.1環境假設 18
3.2問題描述 18
3.3檔案模型 18
3.3.1符號定義 19
3.3.2 α (檔案衰退率) 19
3.3.3 β (檔案比例) 20
3.3.4檔案權重 21
3.4強化學習模型 21
3.4.1狀態 (State) 22
3.4.2動作 (Action) 22
3.4.3動作價值函數 22
3.4.4獎勵函數 26
3.4.5策略 28
3.5實驗設計 28
第四章 系統實作與結果分析 30
4.1 實驗資料集說明 30
4.1.1基於齊夫定律之檔案使用頻率 30
4.1.2單位時間內之檔案請求數 31
4.1.3隨機產生之檔案使用頻率 33
4.1.4資料集 36
4.2 (1.1) 實驗 36
4.2.1快取大小與檔案種類比例 36
4.2.2檔案請求方法與齊夫定律資料集之關係 38
4.2.3檔案請求方法與隨機產生資料集之關係 43
4.3 (2.1) 實驗結果 46
4.3.1預測模型實作方法 46
4.3.2實驗說明 47
4.3.3狀態閥值與零散狀態之關係 48
4.3.4強化學習模型輔助預測 50
第五章 結論與未來展望 54
5.1 實驗結論 54
5.2 未來發展方向 54
參考文獻 56
附錄 59
附錄一 演算法試算 59
α值試算 59
β值試算 59
檔案權重模型試算 59
強化學習狀態試算 狀態閥值(Threshold)為1 59
強化學習狀態試算 狀態閥值(Threshold)為2 59
附錄二 30個檔案之各區間權重分布圖 60
附錄三 隨機產生資料之狀態減少比例 61

[1]M.Agiwal, A.Roy, andN.Saxena, “Next generation 5G wireless networks: A comprehensive survey, IEEE Communications Surveys and Tutorials, vol. 18, no. 3. pp. 1617–1655, 2016.
[2]B. K.Wiederhold, G.Riva, andG.Graffigna, “Cisco Visual Networking Index: Forecast and Trends, 2017–2022, Annual Review of CyberTherapy and Telemedicine. 2013.
[3]D.Xu et al., “A Survey of Opportunistic Offloading, IEEE Commun. Surv. Tutorials, vol. 20, no. 3, pp. 2198–2236, 2018.
[4]I. U.Din, S.Hassan, M. K.Khan, M.Guizani, O.Ghazali, andA.Habbal, “Caching in Information-Centric Networking: Strategies, Challenges, and Future Research Directions, IEEE Commun. Surv. Tutorials, vol. 20, no. 2, pp. 1443–1474, 2018.
[5]G.Paschos, E.Bastug, I.Land, G.Caire, andM.Debbah, “Wireless caching: technical misconceptions and business barriers, IEEE Commun. Mag., vol. 54, no. 8, pp. 16–22, Aug.2016.
[6]R. S.Sutton andA. G.Barto, Reinforcement learning: An introduction. MIT press, 2018.
[7]N.Laoutaris, H.Che, andI.Stavrakakis, “The LCD interconnection of LRU caches and its analysis, Perform. Eval., vol. 63, no. 7, pp. 609–634, Jul.2006.
[8]Hao Che, Ye Tung, andZhijun Wang, “Hierarchical Web caching systems: modeling, design and experimental results, IEEE J. Sel. Areas Commun., vol. 20, no. 7, pp. 1305–1314, Sep.2002.
[9]S.Eum, K.Nakauchi, Y.Shoji, N.Nishinaga, andM.Murata, “CATT: Cache aware target identification for ICN, IEEE Commun. Mag., vol. 50, no. 12, pp. 60–67, Dec.2012.
[10]W. K.Chai, D.He, I.Psaras, andG.Pavlou, “Cache ‘less for more’ in information-centric networks (extended version), Comput. Commun., vol. 36, no. 7, pp. 758–770, Apr.2013.
[11]S.Podlipnig andL.Böszörmenyi, “A survey of Web cache replacement strategies, ACM Comput. Surv., vol. 35, no. 4, pp. 374–398, Dec.2003.
[12]M.Abrams, C. R.Standridge, G.Abdulla, S.Williams, andE. A.Fox, “Caching Proxies: Limitations and Potentials. Virginia Polytechnic Institute ＆ State University, 1995.
[13]J. E.Pitkow andM.Recker, “A Simple Yet Robust Caching Algorithm Based on Dynamic Access Patterns, 1994.
[14]M.Abrams et al., “Removal policies in network caches for World-Wide Web documents, in Conference proceedings on Applications, technologies, architectures, and protocols for computer communications - SIGCOMM ’96, 1996, vol. 26, no. 4, pp. 293–305.
[15]M.Arlitt, L.Cherkasova, J.Dilley, R.Friedrich, andT.Jin, “Evaluating content management techniques for Web proxy caches, ACM SIGMETRICS Perform. Eval. Rev., vol. 27, no. 4, pp. 3–11, Mar.2007.
[16]D.Lee et al., “On the existence of a spectrum of policies that subsumes the least recently used (LRU) and least frequently used (LFU) policies, in Proceedings of the 1999 ACM SIGMETRICS international conference on Measurement and modeling of computer systems - SIGMETRICS ’99, 1999, vol. 27, no. 1, pp. 134–143.
[17]D. S.Berger, R. K.Sitaraman, andM.Harchol-Balter, “AdaptSize: Orchestrating the Hot Object Memory Cache in a Content Delivery Network. pp. 483–498, 2017.
[18]T.Saemundsson, H.Bjornsson, G.Chockler, andY.Vigfusson, “Dynamic Performance Profiling of Cloud Caches, in Proceedings of the ACM Symposium on Cloud Computing - SOCC ’14, 2014, pp. 1–14.
[19]S.Mullender andR.Cox, “Semaphores in Plan 9, in 3rd International Workshop on Plan 9, 2008, pp. 53–61.
[20]K.Shanmugam, N.Golrezaei, A. G.Dimakis, A. F.Molisch, andG.Caire, “FemtoCaching: Wireless content delivery through distributed caching helpers, IEEE Trans. Inf. Theory, vol. 59, no. 12, pp. 8402–8413, Dec.2013.
[21]N.Zhang, K.Zheng, andM.Tao, “Using Grouped Linear Prediction and Accelerated Reinforcement Learning for Online Content Caching, Mar.2018.
[22]M.Ahmed, S.Traverso, M.Garetto, P.Giaccone, E.Leonardi, andS.Niccolini, “Temporal Locality in Today’s Content Caching: Why it Matters and How to Model it, May2013.
[23]E. G. (Edward G.Coffman andP. J.Denning, Operating systems theory. Prentice-Hall, 1973.
[24]F. M.Harper andJ. A.Konstan, “The MovieLens Datasets, ACM Trans. Interact. Intell. Syst., vol. 5, no. 4, pp. 1–19, Dec.2015.
[25]S.Muller, O.Atan, M.Van DerSchaar, andA.Klein, “Context-Aware Proactive Content Caching with Service Differentiation in Wireless Networks, in IEEE Transactions on Wireless Communications, 2017, vol. 16, no. 2, pp. 1024–1036.
[26]S.Li, J.Xu, M.Van DerSchaar, andW.Li, “Popularity-driven content caching, in Proceedings - IEEE INFOCOM, 2016, vol. 2016-July, pp. 1–9.
[27]I.Althamary, C.-W.Huang, P.Lin, S.-R.Yang, andC.-W.Cheng, “Popularity-Based Cache Placement for Fog Networks, in 2018 14th International Wireless Communications ＆ Mobile Computing Conference (IWCMC), 2018, pp. 800–804.
[28]F.Bonomi, R.Milito, J.Zhu, andS.Addepalli, “Fog computing and its role in the internet of things, in Proceedings of the first edition of the MCC workshop on Mobile cloud computing - MCC ’12, 2012, p. 13.
[29]M. A.Maddah-Ali andU.Niesen, “Fundamental Limits of Caching, Sep.2012.
[30]“Human behavior and the principle of least effort. - PsycNET. [Online]. Available: https://psycnet.apa.org/record/1950-00412-000. [Accessed: 08-May-2019].
[31]L.Breslau, Pei Cao, Li Fan, G.Phillips, andS.Shenker, “Web caching and Zipf-like distributions: evidence and implications, in IEEE INFOCOM ’99. Conference on Computer Communications. Proceedings. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. The Future is Now (Cat. No.99CH36320), 1999, pp. 126–134 vol.1.