یک روش جایگزینی محتوا مبتنی بر آنتروپی شانون و روش تصمیمگیری وزنی ساده در شبکههای مبتنی بر نام
محمد سلطانی
1
(
دانشکده مهندسی کامپیوتر- واحد نجفآباد، دانشگاه آزاد اسلامی، نجفآباد، ایران
)
بهرنگ برکتین
2
(
دانشکده مهندسی کامپیوتر- واحد نجفآباد، دانشگاه آزاد اسلامی، نجفآباد، ایران
)
فرامرز هندسی
3
(
دانشکده مهندسی برق و کامپیوتر- دانشگاه صنعتی اصفهان، اصفهان، ایران
)
زهرا بهشتی
4
(
مرکز تحقیقات کلان داده- واحد نجف آباد، دانشگاه آزاد اسلامی، نجف آباد، ایران
)
کلید واژه: آنتروپی شانون, جایگزینی محتوا حافظه موقت, روش امتیازدهی وزنی ساده, شبکه داده نامگذاریشده, شبکه محتوا محور,
چکیده مقاله :
شبکه داده نام گذاری شده به عنوان یکی از معماری های پیشرو و نسل بعدی شبکه محتوا محور در آینده اینترنت معرفی شده است. اخیراً، چالش جایگزینی محتوا به دلیل اهمیت ویژه آن مورد توجه محققین قرار گرفته است. اگرچه روش های معرفی شده تا کنون تلاش در بهبود این چالش داشته اند، اما وزن دهی غیرپویا و استفاده از تنها یک معیار برای انتخاب محتوای خروجی، نیاز به ایجاد بهبود بیشتر در تاخیر دسترسی را به امری اجتناب ناپذیر تبدیل نموده است. در این راستا، در این مقاله یک روش جدید مبتنی بر فرآیند تصمیمگیری ساده همراه با وزن دهی پویای آنتروپی شانون برای انتخاب مناسب ترین محتوا جهت جایگزینی محتوا ارائه شده است. در روش پیشنهادی معیار های مهم محبوبیت محتوا و زمان آخرین بازدید به صورت پویا وزن دهی و با توجه به شرایط، امکان تغییر وزن معیارها به صورت پویا وجود دارد. سپس محتوا ها امتیازدهی و محتوای مناسب جهت جایگزینی محتوا تعیین می گردد. از نو آوری های روش پیشنهادی در نظر گرفتن معیارهای تاثیر گذار در شبکه های مبتنی بر نام مانند محبوبیت محتوا و زمان آخرین بازدید برای خروج محتوا و همچنین پویا بودن وزن معیارها می توان نام برد که باعث بهبود همزمان زمان تاخیر و نرخ ضربه می شود. نتایج حاصل از شبیه سازی در ndnSIM حاکی از کاهش تاخیر و افزایش نرخ ضربه در مقایسه با روش های مشابه است.
چکیده انگلیسی :
The named data network has been introduced as one of the next generation content-oriented network architectures in the future of the Internet. Recently, the challenge of content replacement has attracted the attention of researchers due to its special importance. Although the methods introduced so far have tried to improve this challenge, non-dynamic weighting and the use of only one criterion to select the output content have made the need for further improvement in the access delay inevitable. Regarding this matter, a novel strategy is presented based on the simple additive weighting (SAW) with the dynamic weighting of Shannon’s entropy for content replacement. In the proposed method, the important parameters such as the popularity of the content and the time of the last visit are included. According to the conditions of the content, it is possible to change the weights of the criteria dynamically using Shannon's entropy method. Content scoring is done using the SAW method and appropriate content is determined to replace the content. Among the innovations of the proposed method can be mentioned the consideration of influential criteria in named data networks, such as content popularity and the time of the last visit to replace the content, as well as the dynamic weight of the criteria, which reduces the delay and increases the hit rate. The results of the simulation in ndnSIM indicate the improvement access delay and hit rate compared to similar methods.
[1] D. Dhakal, A. Gautam, S. Dey, K. Sharma, ''A review on forwarding strategies in NDN based vehicular networks'', EMITTER International Journal of Engineering Technology, vol. 9, no. 2, pp. 339–356, Dec. 2021 (doi: 10.24003/emitter.v9i2.632).
[2] A. Tariq, R.A. Rehman, B.S. Kim, ''Forwarding strategies in NDN based wireless networks: a survey'', EEE Communications Surveys and Tutorials, vol. 22, no. 1, pp. 68-95, Dec. 2021 (doi: 10.1109/COMST.2019.2935795).
[3] K.N. Lal, A. Kumar, ''A popularity based content eviction scheme via betweenness-centrality caching approach for content-centric networking (CCN)'', Wireless Networks, vol. 25, no. 2, pp. 585–596, Feb. 2019 (doi: 10.1007/s11276-017-1577-z).
[4] A. Kalghoum, L.A. Saidane, ''FCR-NS: A novel caching and forwarding strategy for named data networking based on software defined networking'', Cluster Computing, vol. 22, no. 3, pp. 981–994, Sept. 2019 (doi: 10.1007/s10586-018-02887-w).
[5] D. He, C. Westphal, J. Jiang, G. Yang, ''RankRoute: Efficient interest forwarding using nodes ranking'', Proceeding of the IEEE/ICNC, pp. 741–746, Honolulu, HI, USA, Feb. 2019 (doi: 10.1109/ICCNC.2019.8685608).
[6] M.S.M. Shah, Y.B. Leau, Z. Yan, M. Anbar, ''Hierarchical naming scheme in named data networking for internet of things: a review and future security challenges'', IEEE Access, vol. 10, pp. 19958–19970, Feb. 2022 (doi: 10.1109/ACCESS.2022.3151864).
[7] I.V.S. Brito, L. Sampaio, L. Zhang, ''On supporting forwarding strategies and sync protocols through NDN distance vector routing'', Proceeding of the ACMCICN, pp. 183–185, Osaka Japan, Sept. 2022 (doi: 10.1145/3517212.3559490).
[8] A. Hidouri, N. Hajlaoui, H. Touati, M. Hadded, P. Muhlethaler, ''A survey on security attacks and intrusion detection mechanisms in named data networking'', Computers, vol. 11, no. 12, Article Number: 186, Dec. 2022 (doi: 10.3390/computers11120186).
[9] A. Abrar, A.S. Che Mohamed Arif, K. M. Zaini, ''A mobility mechanism to manage producer mobility in named data networking'', Proceeding of the IEEE/TENSYMP, pp. 1–6, Mumbai, India, July 2022 (doi: 10.1109/TENSYMP54529.2022.9864454).
[10] M. Amadeo, C. Campolo, G. Ruggeri, A. Molinaro, ''Popularity-aware closeness based caching in NDN edge networks'', Sensors, vol. 22, no. 9, Article Number: 3460, May 2022 (doi: 10.3390/s22093460).
[11] S. Lee, I. Yeom, D. Kim, ''T-caching: Enhancing feasibility of In-network caching in ICN'', IEEE Trans. on Parallel and Distributed Systems, vol. 31, no. 7, pp. 1486–1498, July 2020 (doi: 10.1109/TPDS.2020.2970702).
[12] M. Amadeo, C. Campolo, G. Ruggeri, A. Molinaro, ''Beyond edge caching: freshness and popularity aware IoT data caching via NDN at internet-scale'', IEEE Trans. on Green Communications and Networking, vol. 6, no. 1, pp. 352–364, Mar. 2022 (doi: 10.1109/TGCN.2021.3124452).
[13] R.K. Dudeja, R.S. Bali, G.S. Aujla, ''Secure and pervasive communication framework using named data networking for connected healthcare'', Computers and Electrical Engineering, vol. 100, no. 1, Article Number: 107806, May 2022 (doi: 10.1016/j.compeleceng.2022.107806).
[14] X. Wang, Y. Lu, ''Sustainable and efficient fog-assisted IoT cloud based data collection and delivery for smart cities'', IEEE Trans. on Sustainable Computing, vol. 7, no. 4, pp. 950–957, Oct. 2022 (doi: 10.1109/TSUSC.2022.3188330).
[15] P. Mekbungwan, G. Pau, K. Kanchanasut, ''In-network computation for IoT data processing with active NDN in wireless sensor networks'', Proceeding of the CIoT, pp. 197–204, Marrakech, Morocco, Mar. 2022 (doi: 10.1109/CIoT53061.2022.9766613).
[16] E.T. da Silva, A.L.D. Costa, J. M. H. de Macedo, ''On the realization of VANET using named data networking: On improvement of VANET using NDN‐based routing, caching, and security'', International Journal of Communication Systems, vol. 35, no. 18, Article Number: e5348 Dec. 2022 (doi: 10.1002/dac.5348).
[17] B. Hao, G. Wang, M. Zhang, J. Zhu, L. Xing, Q. Wu, ''Stochastic adaptive forwarding strategy based on deep reinforcement learning for secure mobile video communications in NDN'', Security and Communication Networks, vol. 2021, pp. 1–13, April 2021 (doi: 10.1155/2021/6630717).
[18] Z. Sharifian, B. Barekatain, A.A. Quintana, Z. Beheshti, F. Safi, "An enhanced routing algorithm in smart iot networks with mobile nodes", Journal of Intelligent Procedures in Electrical Technology, vol. 16, no. 63, pp. 1-24, December 2025 (in Persian).
[19] M. Meddeb, A. Dhraief, A. Belghith, T. Monteil, K. Drira, H. Mathkour, ''Least fresh first cache replacement policy for NDN-based IoT networks'', Pervasive and Mobile Computing, vol. 52, pp. 60–70, Jan. 2019 (doi: 10.1016/j.pmcj.2018.12.002).
[20] Y. Taj, B. Bakhshi-Sareskanrood, H. ZandHessami, "Reliable relay node selection to real-time messaging in vehicular networks", Journal of Intelligent Procedures in Electrical Technology, vol. 15, no. 59, pp. 53-80, December 2024 (in Persian).
[21] C.E. Shannon, ''A mathematical theory of communication'', Bell System Technical Journal, vol. 27, pp. 379–423, Oct. 1948.
[22] M. Zhang, H. Luo, H. Zhang, ''A survey of caching mechanisms in information-centric networking'', IEEE Communications Surveys and Tutorials, vol. 17, no. 3, pp. 1473–1499, April 2015 (doi: 10.1109/COM-ST.2015.2420097).
[23] D. Grund, J. Reineke, ''Precise and efficient FIFO-replacement analysis based on static phase detection'', Proceeding of the IEEE/ECRTS, pp. 155–164, Brussels, Belgium, July. 2010 (doi: 10.1109/ECRTS.2010.8).
[24] Z. Li, D. Liu, H. Bi, ''CRFP: A novel adaptive replacement policy combined the LRU and LFU policies'', Proceeding of the IEEE/CIT, pp. 72–79, Sydney, QLD, July 2008 (doi: 10.1109/CIT.2008.Workshops.22).
[25] S. Chootong, J. Thaenthong, ''Cache replacement mechanism with content popularity for vehicular content-centric networks (VCCN)'', Proceeding of the IEEE/JCSSE, NakhonSiThammarat, Thailand, pp. 1–6, July 2017 (doi: 10.1109/JCSSE.2017.8025901).
[26] Y. Li, M. Yu, R. Li, ''A cache replacement strategy based on hierarchical popularity in NDN'', Proceeding of the IEEE/ICUFN, pp. 159–161, Prague, Czech, July 2018 (doi: 10.1109/ICUFN.2018.8436597).
[27] Y. Liu, T. Zhi, H. Xi, W. Quan, H. Zhang, ''A novel cache replacement scheme against cache pollution attack in content-centric networks'', Proceeding of the IEEE/CIC, pp. 207–212, Changchun, China, Aug. 2019 (doi: 10.1109/ICCChina.2019.8855925).
[28] M.A.P. Putra, H. Situmorang, N.R. Syambas, ''Least recently frequently used replacement policy named data networking approach'', Proceeding of the IEEE/ICEEI, pp. 423–427, Bandung, Indonesia, July 2019 (doi: 10.1109/ICEEI47359.2019.8988828).
[29] N. Alzakari, A.B. Dris, S. Alahmadi, ''Randomized least frequently used cache replacement strategy for named data networking'', Proceeding of IEEE/ICCAIS, pp. 1–6, Riyadh, Saudi Arabia, Mar. 2020 (doi: 10.1109/ICCAIS48893.2020.9096733).
[30] S. Al-Ahmadi, ''A new efficient cache replacement strategy for named data networking'', International Journal of Computer Networks and Communications, vol. 13, no. 5, pp. 19–35, Sept. 2021 (doi: 10.5121/ijcnc.2021.13502).
[31] S. Rashid, S.A. Razak, F.A. Ghaleb, ''IMU: A content replacement policy for CCN, based on immature content selection'', Applied Sciences, vol. 12, no. 1, Article Number: 344, Dec. 2021 (doi: 10.3390/app12010344).
[32] E.T. Silva, J.M.H. Macedo, A.L.D. Costa, ''NDN content store and caching policies: Performance Evaluation'', Computers, vol. 11, no. 3, Article Number: 37, Mar. 2022 (doi: 10.3390/computers11030037).
[33] J. Hou, H. Lu, A. Nayak, ''A GNN-based proactive caching strategy in NDN networks'', Peer-to-Peer Networking and Applications, vol. 16, no. 2, pp. 997-1009, Mar. 2023 (doi: 10.1007/s12083-023-01464-2).
[34] Y. Zha, P. Cui, Y. Hu, L. Xue, J. Lan, Y. Wang, ''An NDN cache-optimization strategy based on dynamic popularity and replacement value'', Electronics, vol. 11, no. 19, Article Number: 3014, Sept. 2022 (doi: 10.3390/electronics11193014).
[35] J. Hou, H. Xia, H. Lu, A. Nayak, ''A graph neural network approach for caching performance optimization in NDN networks'', IEEE Access, vol., pp. 112657–112668, Oct. 2022 (doi: 10.1109/ACCESS.2022.3217236).
[36] A. Narayanan, S. Verma, E. Ramadan, P. Babaie, Z.L. Zhang, ''Making content caching policies “smart” using the deepcache framework'', ACM SIGCOMM Computer Communication Review, vol. 48, no. 5, pp. 64–69, Jan. 2019 (doi: 10.1145/3310165.3310174).
[37] B. Panigrahi, S. Shailendra, H.K. Rath, A. Simha, ''Universal caching model and markov-based cache analysis for information centric networks'', Photonic Network Communications, vol. 30, no. 3, pp. 428–438, Dec. 2015 (doi: 10.1007/s11107-015-0570-7).
[38] J. Yao, B. Yin, X. Tan, ''A SMDP-based forwarding scheme in named data networking'', Neurocomputing, vol. 306, pp. 213–225, Sept. 2018 (doi: 10.1016/j.neucom.2018.03.057).
_||_JIPET | Journal of Intelligent Procedures in Electrical Technology/ Vol. 11/ No. 41/ Spring 2020 P-ISSN: 2322-3871, E-ISSN: 2345-5594, http://jipet.iaun.ac.ir/ |
A replacement method based on Shannon entropy and Simple Additive Weighting (SAW) method in named data networks
Mohammad soltani1, Ph.D. Student, Behrang Barekatain1,2, Assistant Professor, Faramarz Hendesi3, Assistant Professor, Zahra Beheshti1,2, Assistant Professor
1 Faculty of Computer Engineering, Najafabad Branch, Islamic Azad University, Najafabad, Iran
2 Big Data Research Center, Najafabad Branch, Islamic Azad University, Najafabad, Iran
3 Department of Electrical and Computer Engineering, Isfahan University of Technology, Isfahan, Iran
m.soltani1980@gmail.com, behrang_barekatain@iaun.ac.ir, faramarz@hendessi.com, z-beheshti@iaun.ac.ir
Abstract
Named data network has been introduced as one of the next generation content-oriented network architectures in the future of the Internet. Recently, the challenge of content replacement has attracted the attention of researchers due to its special importance. Although the methods introduced so far have tried to improve this challenge, non-dynamic weighting and the use of only one criterion to select the output content have made the need for further improvement in the delay inevitable. Regarding this matter, a novel strategy is presented based on the Simple Additive Weighting (SAW) with the dynamic weighting of Shannon’s entropy for content replacement. In the proposed method, important parameters such as the popularity of the content and the time of the last visit are included. According to the conditions of the content, it is possible to change the weights of the criteria dynamically using Shannon's entropy method. Content scoring is done using the SAW method and appropriate content is determined to replace the content. The advantages of the proposed method are considering the effective criteria for the content and the dynamic weight of the criteria. Among the innovations of the proposed method is the consideration of influential criteria in named data networks, such as content popularity and the time of the last visit to exit the content, as well as the dynamic weight of the criteria, which improves the delay time and hit rate. The results of the simulation in ndnSIM indicate the improvement of delay time and hit rate compared to similar methods.
Keywords: Information-oriented network, Named data network, Replacement, Shannon entropy, Simple Additive Weighting
Received:
Revised:
Accepted:
Corresponding Author: Dr. Behrang Barekatain
یک روش جایگزینی محتوا مبتنی بر آنتروپی شانون و روش تصمیمگیری وزنی ساده در شبکههای مبتنی بر نام
محمد سلطانی1، دانشجوی دکتری، بهرنگ برکتین2،1، استادیار، فرامز هندسی1و3، دانشیار، زهرا بهشتی2،1، استادیار
1- دانشکده مهندسی کامپیوتر- واحد نجف آباد، دانشگاه آزاد اسلامی، نجف آباد، ایران
2- مرکز تحقیقات کلان داده- واحد نجف آباد، دانشگاه آزاد اسلامی، نجف آباد، ایران
3- دانشکده مهندسی برق و کامپیوتر- دانشگاه صنعتی اصفهان، اصفهان، ایران
m.soltani1980@gmail.com, behrang_barekatain@iaun.ac.ir, faramarz@hendessi.com, z-beheshti@iaun.ac.ir
چكيده: شبکه داده نامگذاریشده بعنوان یکی از معماریهای پیشرو و نسل بعدي شبکه محتوا محور در آينده اينترنت معرفی شده است. اخیراً، در میان چالشهاي كليدي مؤثر در عملکرد این شبکه، چالش جایگزینی محتوا به دلیل اهمیت ویژه آن مورد توجه محققين قرار گرفته است. اگرچه روشهای معرفی شده تاکنون تلاش در بهبود این چالش داشتهاند، اما وزندهی غیرپویا و استفاده از تنها یک معیار برای انتخاب محتوای خروجی، نیاز به ایجاد بهبود بیشتر در میزان تاخیر را به امری اجتناب ناپذیر تبدیل نموده است. در اين راستا، در این مقاله یک روش جدید مبتني بر فرآیند تصمیمگیری ساده تطبیق داده شده همراه با وزندهی پویای آنتروپی شانون تطبیق داده شده برای انتخاب مناسبترین محتوا جهت جایگزینی محتوا ارائه شده است. در روش پیشنهادی معیارهای مهم محبوبیت محتوا و زمان آخرین بازدید به صورت پویا وزندهی و با توجه به شرایط، امکان تغییر وزن معیارها بصورت پویا وجود دارد. سپس محتواها امتیازدهی و محتوای مناسب جهت جایگزینی محتوا تعیین میگردد. از نوآوریهای روش پیشنهادی در نظر گرفتن معیارهای تاثیرگذار در شبکههای مبتنی بر نام مانند محبوبیت محتوا و زمان آخرین بازدید برای خروج محتوا و همچنین پویا بودن وزن معیارها است که باعث بهبود همزمان زمان تاخیر و نرخ ضربه میشود. نتایج حاصل از شبیهسازي در ndnSIM حاکی از کاهش تاخیر و افزایش نرخ ضربه در مقایسه با روشهای مشابه است.
کلمات کلیدی: آنتروپی شانون، جایگزینی محتوا حافظه موقت، روش امتیازدهی وزنی ساده، شبکه داده نامگذاریشده، شبکه محتوا محور
تاریخ ارسال مقاله: 10/7/1402
تاریخ بازنگری مقاله:
تاریخ پذیرش مقاله:
نام نویسندهی مسئول: دکتر بهرنگ برکتین
نشانی نویسندهی مسئول: نجفآباد- بلوار دانشگاه- دانشگاه آزاد اسلامی واحد نجفآباد- دانشکده مهندسی کامپیوتر
1- مقدمه
شبکه داده نامگذاری شده11 بستري است که توسط بسیاری از محققان برای تغییر ساختار شبکه مبتنی بر پروتکل اینترنت22 ارائه شده است. این شبکه به جای رویکرد مبتنی بر میزبان، از رویکرد محتوا محوری استفاده می کند [1]. به عبارتي، برنامهها و کاربران فقط به محتوا اهمیت میدهند، در حالی که پروتکلTCP/IP3 با تعیین و کشف مکان دستگاه بر روی ارتباط تمرکز و به همين دليل مديريت را دشوارتر و محدودتر مینمايد .همچنين شبکه داده نامگذاری شده از توزیع کارآمد محتوا پشتیبانی كرده و به جای ایمنسازی کانال های داده، محتوا را ایمن میکند [2]. از مزایای شبکه داده نامگذاریشده میتوان به احراز هویت و شناسایی هر محتوا بدون دخالت سرویس دهنده اشاره کرد. همچنین با ذخیرهسازی محتوا در نزدیکی درخواست کننده، از هدر رفتن پهنای باند جلوگیری میشود [3]. نامگذاری مستقل از موقعیت مکانی، مسیریابی مبتنی بر نام و امنیت بیشتر نسبت به ساختار کنونی اینترنت، از دیگر مزایای شبکه داده نامگذاری شده است [4]. شبکههای محتوا محور44میتوانند با استفاده از جدولهای ذخیرهسازي محتوا55 ،بستههاي علاقهي منتظر66 ، اطلاعات جلورانی77 و ذخیرهسازی درون شبکهای88، کارایی شبکه را بهبود بخشند. شبکه داده نامگذاری شده در حالت ایدهآل ترجیح میدهد تا محتواها در نزدیکترین مسیریاب به درخواستکننده ذخیره شوند تا تاخیر دسترسی به حداقل برسد [5]. در این نوع شبکهها، علیرغم مزایای فوق، چالشهایی مانند نامگذاری [6]، مسیریابی [7]، امنیت [8]، تحرکپذیری [9] و ذخیرهسازی [10] نیز وجود دارند که باید مورد توجه قرار بگیرند. مسیریابها موظف هستند کارهای بیشتر از مسیریابی مانند ذخیره اطلاعات و جستجوی حافظه موقت انجام دهند و نیاز به سرعت بالاتری نسبت به مسیریابهای موجود دارند. مسیریابها باید جدولهای بیشتری را در خود ذخیره کنند که به طور قابل افزایش سربار پردازش میشود [11]. نحوه ذخیرهسازی حافظه موقت به این صورت است که رونوشت از محتواهای درخواست شده را در تمام مسیریابها در طول مسیر گره به درخواستکننده ذخیره میکند. این امر باعث افزونگی شدید شده و مصرف منابع شبکه مانند پهنای باند و حافظه داخلی را افزایش میدهد [4]. موضوع ذخیرهسازی در شبکههای مبتنی بر نام در زمینههای مختلفی مانند اینترنت اشیا99[12]، حوزه سلامت هوشمند1010 [13]، شهر هوشمند1111 [14]، شبکههای حسگر بیسیم1212 [15]، شبکه وسایل نقلیه1313[16] و جریانهای ویدئویی1414 [17] و غیره مورد بررسی واقع شده است. به عنوان مثال در مورد اینترنت اشیاء با توجه به تولید زیاد دادهها و محدودیت ظرفیت حافظه موقت در مسیریابها، پس از مدتی ظرفیت حافظه موقت تکمیل و تعدادی از دادهها باید از حافظه موقت خارج شوند که میتوان از روشهای جایگزینی محتوا حافظه موقت استفاده کرد [18]. در اکثر تحقیقات پیشین، صرفا یکی از پارامترها برای تصمیمگیری استفاده شده، در حالیکه در روش پیشنهادی علاوه بر میزان محبوبیت محتوا، از آخرین زمان بازدید هم به عنوان یکی از پارامترهای مهم استفاده شده است. با توجه به موارد فوق، میتوان مشکلات عمده جایگزینی محتوا روشهای مطرح شده را موارد زیر دانست:
- در نظر نگرفتن ویژگیهای محتوا مانند میزان محبوبیت در کنار آخرین زمان بازدید که منجر به عدم جایگزینی محتوا مناسب و خروج محتویات با میزان محبوبیت بالا میشود.
- در نظر نگرفتن آخرین زمان بازدید در کنار میزان محبوبیت محتوا که منجر به نگهداری محتویاتی که در گذشته محبوب بودهاند، ولی در حال حاضر محبوب نیستند، میشود.
- جایگزینی محتواهای متعدد در اثر اعمال الگوریتمهای نامناسب برای جایگزینی محتوا که منجر به تاخیر تحویل محتوا میگردد.
در این مقاله یک روش جایگزینی محتوا برای شبکه داده نامگذاری شده طراحی شده که پارامترهای مهم مانند میزان محبوبیت محتوا و آخرین زمان بازدید شده محتوا را در نظر گرفته و با استفاده از آنتروپی شانون به صورت پویا وزندهی میکند. از مزایای روش پیشنهادی این است که در هر مرحله با توجه به شرایط، امکان تغییر اوزان آنها وجود خواهد داشت. سپس با کمک روش وزنی ساده15 هر کدام از محتواهای ذخیره شده با توجه به وزنهای پارامترها امتیازبندی و در نهایت محتوای مناسب جهت خروج با توجه به رابطه محاسبه شده استخراج و انتخاب میشود.
بنابراین، نوآوری روش پیشنهادی شامل موارد زیر است:
- در نظر گرفته شدن معیارهای محبوبیت و آخرین زمان بازدید بطور همزمان و استفاده از مزایای روش خطی ساده تطبیق داده شده مانند پیچیدگی پایین محاسبات، رتبهبندی کامل گزینهها و درنظر گرفتن معیارهای مثبت و منفی اشاره کرد.
- استفاده از روش آنتروپی شانون تطبیق داده شده برای وزندهی پویای مناسب به معیارهای میزان محبوبیت محتوا و آخرین زمان بازدید شده محتوا که مطابق شرایط محتوا میتوانند تغییر کنند. در روش آنتروپی شانون وزن عناصر بر اساس میزان پراکندگی شاخصها تعیین و با تغییر شرایط محتوا میتوانند تغییر کنند.
- عدم خروج محتواهای محبوبی که اخیرا مورد تقاضای درخواست کنندگان هستند.
در روش پیشنهادی با اهداف به حداکثر رساندن استفاده از منابع شبکه، کاهش تاخیر و افزایش نرخ برخورد تمرکز شده است. روش پیشنهادی در شبیه ساز ndnSIM تحت سناریوهای متعددی مورد ارزیابی قرار گرفته و نتایج بدست آمده حاکی از بهبود پارامترهای تاخیر و نرخ برخورد به میزان 25.94% و 51.65% است. ساختار این مقاله به شرح زیر سازماندهی شده است.
در بخش دوم پیشینه تحقیق ارائه شده است. در بخش سوم به بررسی دقیق بیان مساله پرداخته میشود. روش پیشنهادی و مراحل بدست آوردن خروجی رابطه مورد نظر در بخش چهارم توضیح داده شده است. در بخش پنجم به بررسی و تجزیه و تحلیل نتایج خواهیم پرداخت و در نهایت در بخش ششم نتیجهگیری و کارهای آتی بررسی میشود.
2- پیشینه تحقیق
در این بخش ابتدا مفاهیم اولیه و سپس تحقیقات انجام شده محققان در زمینه جایگزینی محتوا مورد بررسی واقع شده است.
2-1- مفاهيم اوليه
در این قسمت ابتدا کلیات شبکه داده نامگذاری شده و سپس مراحل پایه روشهای استفاده شده به منظور انتخاب محتوا جهت خروج که شامل روش خطی ساده و وزندهی آنتروپی شانون[19] است، بررسی میگردد.
2-1-1- کلیات شبکه داده نامگذاری شده
شبکه دادههای نامگذاری شده محتواها را با استفاده از نامهایی بازیابی میکند که به صورت سلسله مراتبی هستند. هر مسیریاب شبکههای داده نامگذاری شده، دارای جدول ذخیرهسازي محتوا، جدول بستههاي علاقهي منتظر و جدول اطلاعات جلورانی است. فرآیند ارسال بسته علاقه1616 و بسته داده1717 متناظر با آن، در یک مسیریاب شبکههای داده نامگذاری شده در شکل (1) نشان داده شده است. زمانی که بسته علاقه به یکی از مسیریابها برسد، ابتدا محتوای جدول ذخیرهسازي محتوا بررسی و اگر اطلاعات درخواست شده در آن وجود داشت، آن را در اختیار درخواستکننده قرار میدهد. اگر اطلاعات در جدول ذخیرهسازي محتوا وجود نداشت، جدول بستههاي علاقهي منتظر را بررسی میکند. اگر اطلاعات درخواستی در لیست جدول بستههاي علاقهي منتظر وجود داشت منتظر پاسخ میماند. اگر در جدول بستههاي علاقهي منتظر نیز وجود نداشت به جدول اطلاعات جلورانی مراجعه میکند و مسیریابی برای یافتن محتوا انجام شده و سپس بسته داده را تحویل درخواستکننده میدهد [20].
2-1-2- روش وزنی ساده
روش وزنی ساده که روش خطی ساده نیز نامیده میشود، یکی از روشهای تصمیمگیری چند معیاره برای انتخاب بهترین گزینه است. از مزایای این روش میتوان به سادگی محاسبه، رتبهبندی کامل گزینهها و درنظر گرفتن معیارهای مثبت و منفی اشاره کرد. در این تحقیق از معیارهای میزان محبوبیت محتوا و آخرین زمان بازدید شده محتوا برای تصمیمگیری در مورد انتخاب محتوای خروجی استفاده شده است. در مدلهای تصمیمگیری چند معیاره، هدف یا وزندهی به معیارها است و یا رتبهبندی گزینهها. این روش نیز رتبهبندی گزینهها را دنبال میکند. در این تحقیق رتبهبندی گزینهها با روش خطی ساده و وزندهی معیارها با روش آنتروپی شانون انجام میشود تا معیارها به صورت پویا وزندهی شوند. دلایل استفاده از روش وزنی ساده به صورت زیر هستند.
- سادگی و قابل فهم: یکی از بزرگترین مزایای روش وزنی ساده سادگی آن است. این روش بسیار قابل فهم و آموزش است و نیاز به تخصص آماری یا ریاضی کمتری دارد. به راحتی میتوان از آن برای حل مسائل مختلف استفاده کرد.
- انعطافپذیری: در روش وزنی ساده ، میتوان وزنها را به صورت دلخواه تعیین کرد. این انعطافپذیری به کاربر اجازه میدهد تا اهمیت معیارهای مختلف را بر اساس شرایط و موارد مختلف تنظیم کند.
- کاربرد گسترده: روش وزنی ساده در مسائل متنوعی مانند انتخاب پروژههای سرمایهگذاری، انتخاب تأمینکنندگان، انتخاب دانشگاه برای تحصیل و مسائل تصمیمگیری مشابه کاربرد دارد.
- تطبیق با مسائل واقعی :روش وزنی ساده به خوبی میتواند با مسائل واقعی و پیچیده تطبیق پیدا کند. با تعیین مناسب وزنها و تعداد معیارها، میتوان به نتایج دقیقتری در مسائل واقعی دست یافت.
- محاسبات سریع: این روش محاسبات نسبتاً سریعی دارد و میتوان به سرعت نتایج را به دست آورد. این ویژگی مهم است زمانی که نیاز به تصمیمگیری در مدت زمان محدودی داریم.
- قابلیت تجزیه و تحلیل: با توجه به سادگی روش وزنی ساده ، میتوان نتایج را به راحتی تجزیه و تحلیل کرد و فهمید که چگونه وزنها و معیارها تصمیمگیری را تحتتأثیر قرار میدهند.
با توجه به این مزایا، روش وزنی ساده به عنوان یک ابزار کاربردی در تصمیمگیریهای متعدد در مسائل مختلف مورد استفاده قرار میگیرد. این روش به تصمیمگیران اجازه میدهد تا با توجه به اهمیت ویژگیها و ویژگیهای مختلف، تصمیمهای بهینهتری اتخاذ کنند.
شکل (1): مراحل درخواست و دریافت محتوا در شبکههای مبتنی بر نام
در روش خطی ساده، مراحل زیر برای بدست آوردن بهترین گزینه انجام میشود.
نخستین گام در این روش تشکیل ماتریس تصمیم است. ماتریس تصمیمگیری یک ماتریس برای ارزیابی تعدادی گزینه براساس تعدادی معیار است. یعنی ماتریسی که در آن هر گزینه براساس تعدادی معیار امتیازدهی شده است. ماتریس تصمیم با X و هر درایه آن با xmn در جدول (1) نشان داده شده است.
جدول (1): ماتریس تصمیم
Cn |
| C2 | C1 |
|
x1n | … | x12 | x11 | A1 |
X2n | … | X22 | X21 | A2 |
| … |
|
| . . . |
xmn | … | Xm2 | Xm1 | Am |
بیمقیاسسازی18، دومین گام در حل تمامی روشهای تصمیمگیری چند معیاره مبتنی بر ماتریس تصمیم است که در جدول (2) نمایش داده شده است.
جدول (2): بی مقیاس شده ماتریس تصمیم
Cn |
| C2 | C1 |
|
r1n | … | r12 | r11 | A1 |
r2n | … | r22 | r21 | A2 |
|
|
|
|
|
| … |
|
| . . . |
rmn | … | rm2 | rm1 | Am |
در گاﻡ سوم ﺗﻌﻴﻴﻦ ﺑﺮﺩﺍﺭ ﻭﺯﻥ ﺷﺎﺧﺺﻫﺎ انجام میگردد که در این مقاله از روش وزندهی آنتروپی شانون استفاده میشود.
در ﮔﺎﻡ چهارم ﺑﺎ ﺿﺮﺏ ﻣﺎﺗﺮﻳﺲ بیمقیاس ﺷﺪﻩ ﺗﺼﻤﻴﻢ ﺩﺭ ﺑﺮﺩﺍﺭ ﻭﺯﻥ ﺷﺎﺧﺺﻫﺎ، ﺭﺗﺒﻪ ﮔﺰﻳﻨﻪﻫﺎ ﻭ ﺩﺭ ﻧﻬﺎﻳﺖ ﺑﻬﺘﺮﻳﻦ ﮔﺰﻳﻨﻪ مناسب ﺑﺪﺳﺖ ﻣﻲﺁﻳﺪ.
2-1-3- ﺭﻭﺵ ﻭﺯﻥﺩﻫﻲ آنتروپی شانون
در اکثر مسایل تصمیمگیری چندمعیاره دانستن وزن عناصر بسیار مهم است. روش آنتروپی شانون یکی از روشهایی است که برای تعیین وزن عناصر مورد استفاده قرار میگیرد. ﺍﻳﻦ ﺭﻭﺵ ﻓﻘﻂ ﺍﺯ ﺍﻃﻼﻋﺎﺕ ﻣﺎﺗﺮﻳﺲ ﺗﺼﻤﻴﻢ ﺍﺳﺘﻔﺎﺩﻩ میکند. ﺍﺳﺎﺱ ﺍﻫﻤﻴﺖ ﻫﺮ ﺷﺎﺧﺺ، ﻣﻴﺰﺍﻥ ﭘﺮﺍﻛﻨﺪﮔﻲ ﺩﺍﺩﻩﻫﺎﻱ ﻣﺮﺑﻮﻁ ﺑﻪ ﺳﺘﻮﻥ ﺁﻥ ﺷﺎﺧﺺ ﺩﺭ ﻣﺎﺗﺮﻳﺲ ﺗﺼﻤﻴﻢ است. در این روش، وزن عناصر بر اساس میزان پراکندگی مقادیر تعیین میشود. ماتریس بیمقیاسشده با N و هر درایه آن را با nij نشان داده شده و بیمقیاسسازی به روش خطی صورت میگیرد. در روش آنتروپی شانون با توجه به وزنهای به دست آمده از شاخصها در این مرحله، آن شاخصهایی که دارای پراکندگی بیشتر هستند، نسبت به دیگر شاخصها، از اهمیت بیشتری برخوردارند و تأثیر آنها در انتخاب گزینه بهینه بیشتر است. موارد کاربرد و دلایل استفاده از روش وزندهی آنتروپی شانون به صورت زیر هستند.
- معیار اطلاعاتی: آنتروپی شانون به عنوان یک معیار اطلاعاتی عمل میکند که به ما اجازه میدهد میزان عدم قطعیت و ترتیب در دادهها را اندازهگیری کنیم. این معیار به ما اطلاعات مفهومی و مهمی از دادهها ارائه میدهد.
- کاربرد در فشردهسازی داده: آنتروپی شانون در فشردهسازی دادهها و کاهش حجم آنها بسیار مؤثر است. با استفاده از تئوری اطلاعات و آنتروپی شانون، میتوان دادهها را با بهینهترین شکل فشرده کرد.
- کاربرد در تشخیص الگو و مدلسازی: در حوزههایی مانند یادگیری ماشین، آنتروپی شانون به عنوان یک ابزار مهم برای تشخیص الگو و مدلسازی دادهها به کار میرود. این روش به تحلیل توزیع احتمالاتی دادهها و استخراج ویژگیهای مهم از آنها کمک میکند.
- کاربرد در شبکهها و امنیت اطلاعات: در حوزه امنیت اطلاعات و تشخیص تهدیدات، آنتروپی شانون میتواند برای تشخیص تغییرات ناشی از حملات سایبری و نفوذها به شبکهها مورد استفاده قرار گیرد.
- استفاده در تئوری اطلاعات کوانتومی: آنتروپی شانون نیز در تئوری اطلاعات کوانتومی مورد استفاده قرار میگیرد.
به طور کلی، آنتروپی شانون به عنوان یک ابزار قدرتمند در تحلیل و مدیریت دادهها، تئوری اطلاعات، یادگیری ماشین، و بسیاری از زمینههای مختلف علوم کاربردی بسیار ارزشمند است.
ﮔﺎﻡﻫﺎﻱ ﺭﻭﺵﺁﻧﺘﺮﻭﭘﻲﺷﺎﻧﻮﻥ به صورت زیر است:
- ﮔﺎﻡ (۱): ﻣﺎﺗﺮﻳﺲ ﺗﺼﻤﻴﻢ ﺑﺎ m ﮔﺰﻳﻨﻪ ﻭ n ﺷﺎﺧﺺ ﺭﺍ ﺑﺎ ﺭﻭﺵ ﻧﺮﻡ ﻣﺠﻤﻮﻉ بیمقیاس ﻣﻲشود.
- ﮔﺎﻡ (۲): ﻣﻴﺰﺍﻥ ﺁﻧﺘﺮﻭﭘﻲ ﻫﺮﻳﻚ ﺍﺯ ﺷﺎﺧﺺﻫﺎﻱ ﺭﺍ ﻣﺤﺎﺳﺒﻪ خواهد شد.
- ﮔﺎﻡ (۳): ﺍﻧﺪﺍﺯﻩ ﻋﺪﻡ ﺍﻃﻤﻴﻨﺎﻥ ﻳﺎ ﺩﺭﺟﻪ ﺍﻧﺤﺮﺍﻑ ﺑﺮﺍﻱ ﺷﺎﺧﺺها ﺗﻌﻴﻴﻦ میگردد.
- ﮔﺎﻡ (۴): ﻭﺯﻥ ﻫﺮﻳﻚ ﺍﺯ ﺷﺎﺧصها محاسبه میشود.
2-2- تحقیقات انجام شده
محققان روشهای مختلفی را به منظور حل مشکلات مربوط به جایگزینی محتوا در شبکههای داده نامگذاری شده پیشنهاد کردهاند. در تحقیقات گذشته از معیارهای محبوبیت محتوا و آخرین زمان بازدید که به صورت پویا وزندهی شده باشند استفاده نشده است. در روش اولین ورودی اولین خروجی، زمانی که نیاز به جایگزینی وجود دارد محتوایی که ابتدا در حافظه نهان قرار گرفته شده است حذف میشود[21]. در روش کمترین استفاده اخیر، محتوایی که اخیراً کمتر استفاده شده است را برای قرار دادن محتوای درخواستی خارج میکند [22].
در مرجع [23]، یک سیاست جایگزینی محتوا حافظه پنهان مبتنی بر محبوبیت محتوا را پیشنهاد شده که محبوبیت را بر اساس نسبت بازدید، فاصله درخواست اخیر و تعداد درخواستهای محتوای ذخیره شده محاسبه و هر بار محتوای دارای کمترین محبوبیت را جایگزین میکند. درتحقیق انجام شده در مرجع [24] یک روش تعویض حافظه بر اساس میزان محبوبیت سلسله مراتبی مورد ارزیابی قرار گرفته است. در این روش هر داده یک ساختار اضافهتر برای نگه داشتن اطلاعات در مورد میزان محبوبیت خواهد داشت. درصد برخورد حافظه نهان نسبت به روشهای کمترین استفاده اخیر1919، اولین ورودی اولین خروجی2020، کمترین استفاده2121 بهبود پیدا کرده است. درتحقیق انجام شده در مرجع [3]، یک روش دیگر برای جایگزینی محتوا مطرح شده است که تاریخچه کاملی از میزان محبوبیت را در نظر میگیرد. با در نظر گرفتن میزان محبوبیت محتوا، میزان محبوبیت محلی محتوا و نسبت برخورد حافظه موقت جایگزینی محتوا را انجام میدهد. پارامترهایی نظیر پهنای باند در نظر گرفته نشده است.
در مرجع [25] یک روش جدید جایگزینی محتوا حافظه نهان درون شبکهای را پیشنهاد کرد که ارزیابی محبوبیت محتویات حافظه نهان و بین گرهها در توپولوژی شبکه را ادغام میکند. این روش با سنجیدن اهمیت هر گره و محبوبیت محتوای حافظه نهان در دامنه، بهترین عملکرد جایگزینی محتوا حافظه نهان را در شبکه به دست می آورد. در روش کمترین استفاده شده، شمارشگر تعداد دفعات درخواست محتوا را نگه میدارد. هر زمان که درخواستی برای محتوا دریافت می شود، مقدار شمارنده یک افزایش می یابد. زمانی که فضای حافظه موقت تکمیل شد و نیاز به وجود جایگزینی محتوا داشت، محتوایی که کمترین مقدار شمارنده را داشته باشد، برای خروج انتخاب میشود[26].
مرجع [27]، روش جایگزینی محتوا حافظه پنهان (تصادفی شده کمترین استفاده شده) را پیشنهاد کرده که از محاسبه فرکانس در یک دوره معین برای تعیین محل جایگزینی محتوای تکه قدیمی با تکه محتوا جدید استفاده میکند. در مرجع [28] یک روش جایگزینی محتوا حافظه پنهان زمان و فرکانس پیشرفته را پیشنهاد میکند که از فرکانس ضربه حافظه نهان و زمان بازیابی حافظه پنهان برای انتخاب تکه های محتوا خارج شده استفاده میکرد. با این حال، این خط مشی از یک عامل واحد برای تعیین محتوای جایگزین حافظه پنهان استفاده میکند که دیگر الزامات مختلف شبکه را برآورده نمیکند. در مرجع [29] روشی را به نام IMU برای جایگذاری حافظه نهان معرفی کردهاند. با توجه به اینکه محتوای محبوب شده در یک دوره خاص محبوبیت خود را از دست میدهد، ولی در فضای حافظه نهان باقی میماند و همچنین محتوا قبل از محبوب شدن از فضای حافظه نهان حذف میشود. در این روش مفهوم بلوغ/ناپختگی22 محتوا معرفی شده است. محتوایی که در یک بازه زمانی خاص محبوبیت خود را از دست بدهد و برای مدت طولانی در حافظه پنهان بماند، محتوای نابالغ نامیده میشود. در مقابل، محتوایی که از محبوبیت بالایی برخوردار باشد و همچنین در یک بازه زمانی خاص اخیراً در شبکه درخواست شده باشد، بالغ تلقی میگردد. هر محتوای جدید نه محبوب است و نه بالغ. محتوا باید برای مدتی در حافظه پنهان بماند تا از میزان بلوغ آن مطلع شویم. از این رو، چنین محتوایی از حافظه پنهان که هنوز محبوبیت پیدا نکرده است، خارج نمیشود. علاوه بر این، این مفهوم محتوایی را از حافظه پنهان حذف میکند که پس از مدتی محبوبیت بالای محبوبیت خود را از دست میدهد.
در مرجع [30] عملکرد سیاستهای جایگزینی محتوا حافظه پنهان در یک توپولوژی شبکه با تعداد متغیری از فروشگاههای محتوا (جدول ذخیرهسازي محتوا) را بررسی و از چندین سناریو شبکه برای شبیهسازی استفاده میکند. عملکرد کمترین استفاده اخیر، کمترین استفاده و خط مشی تصادفی ارزیابی میشود. پنج معیار نسبت ضربه حافظه پنهان، ترافیک شبکه، تاخیر بازیابی، ارسال مجدد علاقه و تعداد پرشها برای ارزیابی عملکرد در نظر گرفته شده است.
مرجع [31] از یک مدل شبکه عصبی گراف برای پیشبینی رتبهبندی کاربران از محتواها استفاده و ﺑﺎ بهره حافظه نهان ﺑﺎﻻ ﺟﺎﯾﮕﺰﯾﻦ محتوا ﺑﺎ ﺑﻬﺮه حافظه نهان ﮐﻢ ﻣﯽﺷﻮﻧﺪ. رتبهبندی پیشبینیشده یک محتوا را به عنوان سود محتوای ذخیرهشده در نظر میگیرد و یک الگوریتم جایگذاری حافظه پنهان را برای به حداکثر رساندن سود ذخیرهسازی پیشنهاد کرده و محتواهای ﻣﺤﺒﻮب را در ﺣﺎﻓﻈﻪ ﭘﻨﻬﺎن و در ﻧﺰدﯾﮑﯽ ﮐﺎرﺑﺮان ذﺧﯿﺮه میکند. جایگزینی محتوا حافظه نهان بر اساس رتبهبندی بهره حافظه پنهان محتواها اجرا و محتواهای با سود بیشتر جایگزین محتواهای با سود پایینتر میشوند.
در مرجع [32] یک روش بهینهسازی حافظه پنهان مبتنی بر محبوبیت و ارزش جایگزینی محتوا را پیشنهاد کرده است. هنگامی که محتوای درخواستی به مسیریاب میرسد، آخرین محبوبیت بر اساس تعداد درخواستها در چرخه فعلی و محبوبیت چرخه قبلی محاسبه میشود. آستانه حافظه نهان، گره را با توجه به اشغال فضای حافظه نهان گره تنظیم و محتوا را با محبوبیت بالاتر از آستانه ذخیره میکند. هنگامی که حافظه نهان کامل شد، روش بهینهسازی حافظه نهان آخرین زمان درخواست، محبوبیت و هزینه انتقال محتوای حافظه نهان را در نظر میگیرد. در نهایت، محتوایی را با کمترین مقدار جایگزینی محتوا از حافظه پنهان خارج میکند و محتوایی را با مقدار جایگزینی محتوا بالا نگه میدارد.
در مرجع [33] یک روش ذخیرهسازی مبتنی بر شبکه عصبی گراف را برای بهینه سازی عملکرد ذخیرهسازی در شبکه داده نامگذاری شده پیشنهاد کرده است. در ابتدا، از یک شبکه عصبی کانولوشن برای استخراج ویژگیهای سری زمانی برای هر گره شبکه داده نامگذاری شده استفاده میکند. سپس پیشبینی احتمال ذخیرهسازی محتوا برای هر گره شبکه داده نامگذاری شده انجام میشود. پس از آن، در هر گره شبکه داده نامگذاری شده، تصمیم جایگزینی محتوا حافظه پنهان بر اساس رتبهبندی احتمال ذخیرهسازی محتوای آن گرفته شده و محتوای با احتمال ذخیرهسازی بالا، جایگزین محتوا با احتمال کم میشود. در ادامه در جدول (3) مهمترین مطالعههای پیشین جمعآوری و مقایسه شده است.
جدول (3): خلاصهای بر روشهای جایگزینی محتوا موجود در زمینه شبکههای مبتنی بر نام
مرجع | نام روش | روش جایگزینی محتوا | معیارهای ارزیابی | عملکرد |
[21] | اولین ورودی اولین خروجی | محتواهای قدیمی را با محتواهای جدید جایگزین می کند. | نرخ برخورد | حتی اگر محتوا قدیمی محبوب باشد، با محتوا جدیدکمتر محبوب جایگزین میشود. |
[22] | کمترین استفاده اخیر | محتوایی که اخیراً کمتر به آن اشاره شده است را با محتوای جدید جایگزین میکند | نرخ برخورد | محتوا دادهای که اخیراً کمتر به آن ارجاع شده است، میتواند یک محتوا مکرر باشد (تعداد زیاد درخواست). |
[26] | کمترین استفاده شده | محتوا با کمترین تعداد دفعات را با قطعه داده جدید جایگزین میکند. | نرخ برخورد | پیچیدگی زیاد |
[29] | IMU | مفهوم بلوغ/ ناپختگی محتوا را معرفی کرده است | نرخ برخورد. تاخیر | آخرین زمان بازدید در نظر گرفته نشده است |
3- بیان مساله
در شبکههای مبتنی بر نام به دلیل محدودیت اندازه حافظه موقت، جدول ذخیرهسازي محتوا ممکن است نیاز به سیاست اخراج محتوا داشته باشد تا محتوای جدیدتری را جایگزین نماید. طرح جایگزینی محتوا مناسب باید تصمیم بگیرد کدام محتوا باید در حافظه باقی بماند و کدام یک خارج شود. یک طرح جایگزینی محتوا قبل از تعویض، باید میزان محبوبیت محتوا و نرخ برخورد را محاسبه کند. طرحهای جایگزینی محتوا حافظه موقت پارامترهای مهمی مانند میزان محبوبیت محتوا و آخرین زمان بازدید شده را برای جایگزینی محتوا را به طور همزمان در نظر نمیگیرند [3]. در صورت در نظر نگرفتن پارامترهای تاثیر گذار مانند میزان محبوبیت محتوا، شاهد کاهش نرخ برخورد، افزایش تاخیر و مصرف منابع شبکه مانند پهنای باند خواهیم بود [24].
با توجه به تغییرات ناگهانی در میزان محبوبیت محتوا، نمیتوان به درستی میزان محبوبیت محتوا را پیشبینی کرد. ارائه روشی که به صورت خودکار تغییرات در الگوهای درخواست میزان محبوبیت و همچنین آخرین زمان درخواست محتوا را محاسبه و تصمیم بگیرد کدام محتوا باید خارج شود، از اهمیت زیادی برخوردار است. تغییر در الگوهای درخواست محتوا با گذشت زمان از چالشهای موجود است [34]. به علت اینکه پارامترهایی مانند اولویت محتوا در سیاستهای تصادفی کمترین استفاده اخیر، اولین ورودی اولین خروجی و مانند آن لحاظ نمیشوند، مناسب شبکههای مبتنی بر نام نیستند [35]. الگوریتم کمترین استفاده اخیر، محتوای کمتر استفاده شده را خارج میکند. در روش کمترین استفاده شده محتوای محبوب را حفظ میکند تا تعداد زیادی از درخواستها را حفظ نماید. در روش تصادفی به صورت تصادفی محتوا را خارج میکند. به هر حال، در الگوریتمهای فوق معیارهای لازم در نظر گرفته نشدهاند [18].
ویژگیهای محتوا مانند میزان محبوبیت محتوا و آخرین زمان بازدید در حال تغییر هستند. اگر بتوان این پارامترها و ویژگیها را برای تصمیمگیری در مورد جایگزینی محتوا در نظر گرفت، به نحوی که تغییرات آنها به صورت پویا اعمال گردد، میتوان مناسبترین تصمیم را برای جایگزینی محتوا اتخاد نمود. بالا بردن نرخ برخورد نیز یکی از چالشهای مهم است که حل آن میتواند باعث کاهش بار ارتباطی شود.
با توجه به ظرفیت محدود مسیریابها، در صورت اتمام ظرفیت مسیریاب برای ذخیره اطلاعات باید برخی از اطلاعات محتواها حذف گردد تا بتواند اطلاعات جدیدتری در آن مسیریاب قرار گیرد. در روش پیشنهادی، دو پارامتر میزان محبوبیت محتوا و زمان آخرین بازدید برای این منظور در نظر گرفته شده است که وزندهی آنها به صورت پویا هستند و انتظار میرود با این دو پارامتر مناسبترین محتوا برای خروج تعیین شود.
4-روش پیشنهادی
با توجه به اهمیت انتخاب محتوا جهت خروج از جدول ذخیرهسازي محتوا، در این بخش مراحل بدست آوردن رابطهای که بتواند محتوای خروجی را انتخاب کند بررسی میشود. همانگونه که ذکر شد، در انتخاب محتوای خروجی پارامترهای میزان محبوبیت محتوا و زمان آخرین بازدید در نظر گرفته شده و به صورت پویا وزندهی میشوند و امکان تغییر وزن پارامترها با توجه به شرایط محتواها وجود دارد.
4-1- کلیات روش پیشنهادی
شکل (2) فلوچارت روش پیشنهادی برای جایگزینی محتوا را نشان میدهد. اگر بسته درخواست به یکی از مسیریابها برسد، ابتدا جدول ذخیرهسازي محتوا بررسی و اگر اطلاعات درخواست شده در آن وجود داشت، آن را در اختیار درخواست کننده قرار میدهد. اگر اطلاعات در جدول ذخیرهسازي محتوا وجود نداشت، جدول بستههاي علاقهي منتظر را بررسی کرده و اگر اطلاعات درخواستی در لیست جدول بستههاي علاقهي منتظر وجود داشت، منتظر پاسخ میماند. اگر در جدول بستههاي علاقهي منتظر هم وجود نداشت، مطابق جدول اطلاعات جلورانی مسیریابی را جهت بدست آوردن محتوا انجام میدهد. پس از رسیدن محتوای درخواستی به مسیریاب، بررسی میشود که آیا مسیریاب حافظه مورد نیاز جهت ذخیره محتوا را دارد یا خیر.
با توجه به ظرفیت محدود مسیریابها، در صورت اتمام ظرفیت مسیریاب برای ذخیره اطلاعات، باید برخی از اطلاعات محتواها حذف گردد تا بتوان اطلاعات جدیدتری در آن مسیریاب قرار داد. دو پارامتر محبوبیت محتوا و زمان آخرین بازدید برای این منظور در نظر گرفته شده است که انتظار میرود با این دو پارامتر مناسبترین محتوا برای خروج تعیین شود. طبق رابطه بدست آورده شده در بخش (5-2-5) که وزندهی معیارها با کمک آنتروپی شانون و امتیازدهی با کمک روش خطی ساده در آن لحاظ شده است، محتواهای ذخیره شده را امتیازدهی و محتوایی که کمترین امتیاز را دارد حذف تا محتوای جدید جایگزین آن شود.
مراحل تعیین محتوا جهت خروج از جدول ذخیرهسازي محتوا در روش پیشنهادی به صورت زیر است:
الف- ایجاد ماتریس تصمیم: دو پارامتر محبوبیت محتوا و زمان آخرین بازدید به عنوان پارامترهای تاثیرگذار انتخاب شدهاند.
ب- بی مقیاسسازی و وزندهی به شاخصها: پس از بی مقیاسسازی با کمک آنتروپی شانون، شاخصها را وزندهی میکنیم. آنتروپی شانون باعث میشود که وزندهی به صورت پویا انجام و طبق شرایط محتواها این وزنها میتوانند تغییر کنند.
ج- امتیازدهی با کمک روش خطی ساده: پس از مراحل فوق وزنها محاسبه و امتیازدهی اعمال میشود و در نهایت محتوایی حذف میشود که دارای کمترین امتیاز است.
با انجام مراحل ذکر شده به رابطه ای میرسیم که میتواند امتیاز محتواها را بدست آورد. تمام مراحل بی مقیاسسازی، وزندهی با کمک آنتروپی شانون و امتیازدهی با روش خطی ساده در این رابطه لحاظ شده است .
4-2- جزئیات روش پیشنهادی
با توجه به اهداف این مقاله، معیارهای میزان محبوبیت محتوا و زمان آخرین در نظر گرفته شده است تا تغییرات وضعیت محتواها را بطور مداوم بررسی و محتوای مناسب را انتخاب کند. در ادامه جزییات روش پیشنهادی بررسی شده است.
4-2-1- دریافت بسته علاقه توسط مسیریاب
در بسته علاقه، فیلد نام وجود دارد که میتواند شامل پیشوند بسته داده یا نام دقیق بسته داده باشد. با رسیدن بسته علاقه به هر مسیریاب پس از بررسی جدول ذخیرهسازي محتوا و جدول بستههاي علاقهي منتظر و عدم مطابقت نام مورد نظر در آنها، جدول اطلاعات جلورانی بررسی میشود.
4-2-2- بررسی جدول ذخیرهسازي محتوا
برای افزایش اشتراک گذاشتن محتوا و کاهش زمان بازیابی محتوا، مسیریاب شبکه داده نامگذاری شده یک رونوشت از بسته داده که از میان آنها میگذرد را در جدول ذخیرهسازي محتوا ذخیره میکند و با پر شدن آن جدول از روش پیشنهادی ﺑﻪ ﻋﻨﻮان ﺧﻂ ﻣش ﺟﺎﯾﮕﺰﯾﻨﯽ حافظه نهان اﺳﺘﻔﺎده میشود. اگر بسته علاقه به یکی از مسیریابها برسد، ابتدا جدول ذخیرهسازي محتوا بررسی و اگر اطلاعات درخواست شده در آن وجود داشت، آن را در اختیار درخواستکننده قرار میدهد. جستجوی جدول ذخیرهسازي محتوا توسط تناظریابی دقیق نامها (تطابق کاراکتر به کاراکتر) صورت میگیرد.
4-2-3- بررسی جدول بستههاي علاقهي منتظر
جدول بستههاي علاقهي منتظر یک مدخل، برای هر بسته علاقه جدید ایجاد و تا زمانی که بسته داده متناظر آن برسد یا زمان آن منقضی شود، این ورودیهای جدول بستههاي علاقهي منتظر جهت ارسال بسته داده به مصرفکننده مورد استفاده قرار میگیرند. اگر محتوا مورد نظر در جدول ذخیرهسازي محتوا نبود، جدول بستههاي علاقهي منتظر را بررسی و اگر اطلاعات درخواستی در لیست موارد تعلیقی وجود داشت، منتظر پاسخ میماند. جستجوی جدول بستههاي علاقهي منتظر توسط تناظریابی دقیق نامها صورت میگیرد.
4-2-4- بررسی جدول اطلاعات جلورانی
جدول اطلاعات جلورانی گامهای بعدی و اطلاعات دیگر را برای هر پیشوند نام مقصد مورد نظر را ذخیره میکند تا برای ارسال بسته علاقه به تولیدکننده مورد استفاده قرار گیرد. پس از بررسی جدول ذخیرهسازي محتوا و جدول بستههاي علاقهي منتظر، اگر اطلاعات درخواست شده در آنها وجود نداشت، به جدول اطلاعات جلورانی مراجعه میکند.
4-2-5- محاسبه امتیاز برای هر یک از محتواها
برای بدست آوردن رابطهای که بتواند امتیاز هر محتوا را محاسبه کند، ابتدا باید با توجه به معیارهای میزان محبوبیت و آخرین زمان بازدید، ماتریس تصمیم را ایجاد و پس از بیمقیاسسازی، وزندهی پویای هر یک از شاخصها انجام و امتیازدهی صورت پذیرد. جدول (4) نمادهای استفاده شده در این مقاله را نشان میدهد.
جدول (4): نمادهای استفاده شده
نماد | توضیحات | نماد | توضیحات |
X | ماتریس تصمیم | wl | وزن آنتروپی میزان محبوبیت |
N | ماتریس تصمیم بیمقیاس شده | wt | وزن آنتروپی آخرین زمان بازدید |
k | ثابت آنتروپی شانون | Tnorm | بیمقیاس شده آخرین زمان بازدید |
Ej | آنتروپی صفت j | lnorm | بیمقیاس شده میزان محبوبیت |
dj | درجه پراکندگی | n | معیار |
Wj | وزن آنتروپی. تعیین وزن صفات | m | داوطلب |
dl | درجه پراکندگی برای میزان محبوبیت | Di | امتیاز هر یک از محتواها |
dt | درجه پراکندگی برای آخرین زمان بازدید |
|
|
|
شکل (2): فلوچارت روش پیشنهادی |
4-2-5-1- ایجاد ماتریس تصمیم و بی مقیاسسازی معیارها
میزان محبوبیت و آخرین زمان بازدید دو شاخصی هستند که برای تصمیمگیری در مورد انتخاب واسط خروجی استفاده شدهاند. اهداف این تحقیق کاهش زمان تاخیر و بهبود نرخ برخورد است که در هر دو معیار میزان محبوبیت و آخرین زمان بازدید میتوانند تاثیر گذار باشند. جدول ماتریس تصمیم برای روش پیشنهادی به صورت جدول (5) است.
جدول (5): تشکیل ماتریس تصمیم
| میزان محبوبیت | آخرین زمان بازدید |
محتوای 1 | L1 | T1 |
محتوای 2 | L2 | T2 |
محتوای n | Ln | Tn |
در روش پیشنهادی، به دلیل اینکه مقیاسهای سنجش متفاوتی وجود دارند، ابتدا باید بی مقیاسسازی انجام شود.
(1)
در رابطه (1) xij هر درایه از ماتریس X رابطه (1) و nij بیمقیاسشده آن معیار هستند.
با توجه به رابطه (1) بیمقیاسشده هر کدام از معیارهای آخرین زمان بازدید و میزان محبوبیت محتوا به ترتیب به صورت روابط (2) و (3) خواهد شد.
(2)
(3)
که tnormi, lnormi به ترتیب بیمقیاس شده میزان محبوبیت و آخرین زمان بازدید مربوط به محتوای i هستند. ورودیهای روابط (2) و (3) از ماتریس تصمیم و خروجی آن به عنوان ورودیهای رابطه (5) که میزان پراکندگی معیارها است، هستند.
4-2-5-2- وزن دهی پویا به معیارها
در روش پیشنهادی با توجه به اینکه وزندهی پارامترها به صورت ثابت نیستند، باید درجه انحراف هر کدام از آنها را با توجه به ضریب اهمیتشان بدست آورد که با توجه به رابطه (4) به صورت روابط (6) و (7) قابل بیان هستند. درجه انحراف که برای وزن دهی پویا استفاده میشود، با توجه به انحراف معیار شاخصها بدست میآید.
(4)
Ej میزان پراکندگی هر یک از معیارها است که از رابطه (5) بدست میآید و dj درجه انحراف معیار است که برای وزندهی پویا در روابط (9) و (10) به کار برده میشوند.
(5)
k ثابت آنتروپی شانون و nij بی مقیاس شده معیار است.
(6)
(7)
در روابط (6) و (7)، Li و Ti به ترتیب میزان محبوبیت و آخرین زمان بازدید مربوط به محتوای i هستند و m تعداد محتواهای ذخیره شده در هر مسیریاب است. برای بدست آوردن میزان محبوبیت محتوا، تعداد درخواستهای هر محتوا در نظر گرفته شده است. همچنین، dL وdT به ترتیب درجه انحراف میزان محبوبیت و آخرین زمان بازدید مربوط به محتوای i هستند که برای وزندهی پویای معیارها در رابطه (8) به کار برده میشوند.
سرانجام برای وزندهی هرکدام از پارامترها از رابطه (8) استفاده میشود. با توجه به اینکه از درجه انحراف برای بدست آوردن وزن معیارها استفاده شده، در صورت تکمیل ظرفیت مسیریاب، معیارهای میزان محبوبیت و آخرین زمان بازدید مربوط به محتوای i در هر مسیریاب به روزرسانی و مجددا محاسبه وزندهی پویا خواهیم داشت.
(8)
پس از ساده سازی روابط (4) و (8)، رابطه (9) برای وزن دهی هر کدام از پارامترها بدست آمده است که در رابطه (13) برای محاسبه امتیاز هر محتوا ، استفاده شده است.
(9)
Wj وزن هر کدام از پارامترها است که در آن j={L,T} و xij عنصر ماتریس تصمیم است. با توجه به اینکه در این تحقیق از دو معیار میزان محبوبیت و آخرین زمان بازدید مربوط به محتوای i استفاده شده است، برای تعیین وزن هرکدام از آنها به صورت پویا با توجه به رابطه (9) از روابط (10) و (11) استفاده میکنیم.
(10)
(11)
در این روابط، WL و WT به ترتیب وزن میزان محبوبیت و آخرین زمان بازدید مربوط به محتوای i است که به صورت پویا هستند و Li و Ti میزان محبوبیت و آخرین زمان بازدید مربوط به محتوای i هستند. در این روابط که درجه انحراف در آنها لحاظ شده و با تغییر اختلاف هر کدام از معیارها، وزنشان نیز تغییر میکند که منجربه وزندهی پویا میشود.
4-2-5-3- امتیازدهی به هر یک از محتواها
طبق رابطه (12)، ماتریس بیمقیاس شده در وزنهای بدست آورده شده روابط (10) و (11) ضرب شده و پس از سادهسازی رابطه (13) بدست میآید.
i=1,2,…,m
j=1,2,…,n (12)
(13)
رابطه (13) حاصل ضرب وزن معیارها در ماتریس بیمقیاس شده معیارها است و پویا بودن معیارها در آن لحاظ شده است.
و چون هدف ما پیدا کردن کمترین امتیاز است، بنابراین، صورت رابطه برای محاسبات کفایت کرده و رابطه (14) را خواهیم داشت.
(14)
و در نهایت محتوایی که Min{D1……DM} است از حالت ذخیره خارج میشود (حذف میگردد).
با توجه به اینکه در رابطه بدست آمده وزندهی به کمک آنتروپی شانون و امتیازدهی با کمک روش SAW و پارامترهای محبوبیت محتوا و زمان آخرین بازدید لحاظ شده است، انتظار میرود مناسبترین محتوا برای خروج انتخاب شود.
4-2-6- حل یک نمونه مساله
به عنوان مثال فرض کنید که ظرفیت یکی از مسیریابها تکمیل شده باشد و نیاز به جایگزینی محتوا داشته باشیم. در این مثال چهار محتوا در مسیریاب ذخیره شده است و برای جایگزینی باید یکی از محتواها از حالت ذخیره خارج گردد. با توجه به رابطه بدست آورده شده (14) محتوایی که کمترین امتیاز را بدست آورد از حالت ذخیره خارج میشود. برای نشان دادن پویا بودن وزن معیارها که از نوآوریهای روش پیشنهادی است، مقادیر مختلف آخرین زمان بازدید و محتوا را طبق جدولهای (6) تا (9) با سه مثال مورد بررسی قرار دادیم.
در مثال (1) جدول (6)، با توجه به مقادیر آخرین زمان بازدید و محبوبت محتوا و روابط بدست آورده شده (10) و (11) وزن هر کدام از معیارهای آخرین زمان بازدید و محبوبت محتوا برابر 0.5 میشود. همان گونه که مشاهده میشود وزن معیارها به صورت پویا محاسبه شده و با تغییر مقادیر معیارهای در نظر گرفته شده تغییر میکنند.
جدول (6): مثال (1) با مقادیر مختلف معیارها جهت محاسبه وزن معیارها و امتیاز محتواها
| آخرین زمان بازدید | محبوبیت محتوا | امتیاز محتوا |
محتوای 1 | 4 | 10 | 0.066 |
محتوای 2 | 8 | 20 | 0.133 |
محتوای 3 | 16 | 40 | 0.266 |
محتوای 4 | 32 | 80 | 0.533 |
با توجه به امتیاز محاسبه شده هر یک از محتواها طبق رابطه بدست آورده شده (14)، محتوای (1) کمترین امتیاز را کسب کرده و از حالت ذخیره خارج میشود. در مثال (2) مربوط به جدول (7)، آخرین زمان بازدید محتوای (1) را افزایش میدهیم تا تغییرات وزنها و امتیاز را شاهد باشیم.
در مثال (2) با توجه به مقادیر آخرین زمان بازدید و محبوبت محتوا و روابط بدست آورده شده (10) و (11) وزن معیارهای آخرین زمان بازدید برابر 0.363 و محبوبت محتوا برابر 0.636 میشود. با توجه به امتیاز محاسبه شده هر یک از محتواها طبق رابطه بدست آورده شده (14)، محتوای (2) کمترین امتیاز را کسب کرده و از حالت ذخیره خارج میشود.
جدول (7): مثال (2) با مقادیر مختلف معیارها جهت محاسبه وزن معیارها و امتیاز محتواها
| آخرین زمان بازدید | محبوبیت محتوا | امتیاز محتوا |
محتوای 1 | 38 | 10 | 0.189 |
محتوای 2 | 8 | 20 | 0.115 |
محتوای 3 | 16 | 40 | 0.231 |
محتوای 4 | 32 | 80 | 0.463 |
در مثال (3) مربوط به جدول (8)، با توجه به مقادیر آخرین زمان بازدید و محبوبت محتوا و روابط بدست آورده شده (10) و (11) وزن معیارهای آخرین زمان بازدید برابر 0.664 و محبوبت محتوا برابر 0.335 میشود. با توجه به امتیاز محاسبه شده هر یک از محتواها طبق رابطه بدست آورده شده (14)، محتوای (3) کمترین امتیاز را کسب کرده و از حالت ذخیره خارج میشود.
جدول (8): مثال (3) با مقادیر مختلف معیارها جهت محاسبه وزن معیارها و امتیاز محتواها
| آخرین زمان بازدید | محبوبیت محتوا | امتیاز محتوا |
محتوای 1 | 38 | 20 | 0.307 |
محتوای 2 | 25 | 20 | 0.197 |
محتوای 3 | 40 | 8 | 0.153 |
محتوای 4 | 50 | 32 | 0.341 |
همانگونه که در مثالهای (1) تا (3) مشاهده میشود وزنهای معیارهای آخرین زمان بازدید و محبوبت محتوا به صورت پویا و طبق شرایط محتواها تغییر میکنند. همچنین از معیارهای آخرین زمان بازدید و محبوبت محتوا به صورت همزمان برای امتیازدهی به محتواها استفاده شده است.در رابطه (14) که برای امتیازدهی به محتواها است، وزندهی پویا لحاظ شده است و نیاز به محاسبه جداگانه برای وزندهی پویا وجود ندارد.
5- شبیهسازی و نتایج
در این بخش ابتدا ابزارها و شرایط شبیهسازی معرفی شده، سپس معیارها و پارامترهای ارزیابی معرفی میگردد و در نهایت نتایج روش ارائه شده نمایش داده میشود و مورد تحلیل و بحث قرار میگیرد.
5-1- ابزار و پارامترهای شبیهسازی
در این پژوهش از شبیهساز ndnSIM استفاده شده که یک ماژول نوشته شده برای پیاده سازی شبکههای مبتنی بر نام است. شبیهساز ndnSIM با هدف شبیهسازی شبکه NDN طراحی شده است. در این شبیهساز از تمام اجزا و عملکردهای NDN مانند جدولهای موارد تعلیقی و پایگاه اطلاعات ارسالی، پیوندهای شبکه، سیاستهای ارسال و منبع محتوا به صورت ماژول و در قالب کلاسهای C++ پشتیبانی شده که می توان سیاستهای مختلف را در آن پیادهسازی کرد.
با در نظر گرفتن متغیرهای مستقل مانند تعداد گرهها، درصد حافظه موقت و نرخ ارسال درخواست با مقادیر مختلف، وضعیت نرخ برخورد و تاخیر دسترسی بررسی میگردد. تعداد گرهها در سناریوهای مختلف 200، 300 و 400 گره درنظر گرفته شده است. نرخ ارسال بسته درخواست2000، 3000 و 4000 درثانیه لحاظ شده است. ﺣﺎﻓﻈﻪ ﭘﻨﻬﺎن ﯾﮏ روﺗﺮ از ﻧﻈﺮ اﻧﺪازه 10 تا 60 درصد از ﮐﺎﺗﺎﻟﻮگ ﻣﺤﺘﻮا و ﮐﺎﺗﺎﻟﻮگ ﺷﺎﻣﻞ 104 آﯾﺘﻢ ﻣﺤﺘﻮای ﻣﺠﺰا ﺑﺎ اﻧﺪازه برابر ﮐﻪ ﻫﺮ ﮐﺪام از 100 ﺑﺴﺘﻪ داده ﻣﺴﺘﻘﻞ ﺗﺸﮑﯿﻞ ﺷﺪهاند، هستند. ﻫﺮسناریو ﺑﻪ ﻣﺪت 300 ﺛﺎﻧﯿﻪ و به تعداد 10 بار اﺟﺮا ﺷﺪه است. جدول (9) پارامترهای شبیهسازی را نشان میدهد. در انجام شبیهسازی، با توجه به سناریوهای جدول (10) ﺑﻪ ﻃﻮرﺗﺼﺎدﻓﯽ ﺟﻔﺖﻫﺎی ﻣﺼﺮفﮐﻨﻨﺪه/ﺗﻮﻟﯿﺪﮐﻨﻨﺪه اﻧﺘﺨﺎب و ﻫﺮ ﻣﺼﺮفﮐﻨﻨﺪه ﯾﮏ ﻓﺎﯾﻞ 4 ﻣﮕﺎﺑﺎﯾﺘﯽ از ﺗﻮﻟﯿﺪﮐﻨﻨﺪه ﻣﺮﺑﻮﻃ به ﺧﻮد درﺧﻮاﺳﺖ میکند.
جدول (9): پارامترهای شبیهسازی | |
تعداد گرهها | 200،300،400 |
ظرفیت حافظه موقت | 10،30،60 درصد اندازه کاتالوگ |
نرخ ارسال درخواست | Packet/second 2000 -4000 |
توپولوژی شبکه | ABILINE |
اندازه کاتالوگ | items 104 |
اندازه آیتم | 100data packet |
ضریب محبوبیت محتوا | Zipf-distributed with α = 1 |
جدول (10): سناریوهای شبیه سازی
| فرکانس ارسال درخواست [Packet/second | درصد حافظه کش | شماره سناریو | تعداد گرهها | فرکانس ارسال درخواست [Packet/second] | درصد حافظه کش | شماره سناریو |
200 | 3000 | 30 | 15 | 400 | 4000 | 10 | 1 |
400 | 2000 | 30 | 16 | 300 | 4000 | 10 | 2 |
300 | 2000 | 30 | 17 | 200 | 4000 | 10 | 3 |
200 | 2000 | 30 | 18 | 400 | 3000 | 10 | 4 |
400 | 4000 | 60 | 19 | 300 | 3000 | 10 | 5 |
300 | 4000 | 60 | 20 | 200 | 3000 | 10 | 6 |
200 | 4000 | 60 | 21 | 400 | 2000 | 10 | 7 |
400 | 3000 | 60 | 22 | 300 | 2000 | 10 | 8 |
300 | 3000 | 60 | 23 | 200 | 2000 | 10 | 9 |
200 | 3000 | 60 | 24 | 400 | 4000 | 30 | 10 |
400 | 2000 | 60 | 25 | 300 | 4000 | 30 | 11 |
300 | 2000 | 60 | 26 | 200 | 4000 | 30 | 12 |
200 | 2000 | 60 | 27 | 400 | 3000 | 30 | 13 |
|
|
|
| 300 | 3000 | 30 | 14 |
5-2- ارزیابی نتایج روشهای پیشنهادی
در این قسمت نتایج شبیهسازی پارامترهای نرخ برخورد حافظه موقت و تاخیر مورد بررسی قرار میگیرند. عملکرد روش پیشنهادی با روشهای FIFO,LRU,LFU ,IMUو به کمکndnSIM مقایسه میگردد. برای محاسبه زمان تاخیر از رابطه (15) و محاسبه نرخ برخورد از رابطه (16) استفاده شده است [36].
(15) مدت زمان دریافت محتوا + مدت زمان ارسال بسته = تاخیر
(16) (نرخ برخورد حافظه موقت + نرخ برخورد تولیدکننده)/ نرخ برخورد حافظه موقت = نرخ برخورد
از آزمون فریدمن که یک آزمون ناپارامتریک از معیارهای چند گروهی است برای مشاهده تفاوت عمکرد روش پیشنهادی با روشهای FIFO,LRU,LFU ,IMU استفاده شده است. آزمایش فریدمن برای 27 سناریو مطابق با جدول 10 اجرا شد. مطابق نتایج آزمون فریدمن و با توجه به اینکه 0.05 P< بدست آمده است، تفاوت معنی داری بین روش پیشنهادی و روشهای مورد مقایسه وجود دارد. امتیازهای روشهای مورد مقایسه مطابق جدول (11) است.
جدول(11): رتبههای روشهای مقایسه شده با آزمون فریدمن
FIFO | LRU | LFU | IMU | روش پیشنهادی | الگوریتم سناریو |
5 | 3 | 4 | 2 | 1 | 1 |
5 | 4 | 3 | 2 | 1 | 2 |
5 | 3 | 4 | 2 | 1 | 3 |
5 | 3 | 4 | 2 | 1 | 4 |
5 | 4 | 3 | 2 | 1 | 5 |
5 | 4 | 3 | 2 | 1 | 6 |
5 | 4 | 3 | 2 | 1 | 7 |
5 | 4 | 3 | 2 | 1 | 8 |
3 | 5 | 4 | 2 | 1 | 9 |
5 | 3 | 4 | 2 | 1 | 10 |
5 | 4 | 3 | 2 | 1 | 11 |
5 | 3 | 4 | 2 | 1 | 12 |
5 | 3 | 4 | 2 | 1 | 13 |
5 | 4 | 3 | 2 | 1 | 14 |
5 | 4 | 3 | 2 | 1 | 15 |
5 | 4 | 3 | 2 | 1 | 16 |
5 | 4 | 3 | 2 | 1 | 17 |
3 | 5 | 4 | 2 | 1 | 18 |
5 | 4 | 3 | 2 | 1 | 19 |
5 | 4 | 3 | 2 | 1 | 20 |
5 | 4 | 3 | 2 | 1 | 21 |
5 | 4 | 3 | 2 | 1 | 22 |
5 | 4 | 3 | 2 | 1 | 23 |
5 | 4 | 3 | 2 | 1 | 24 |
5 | 4 | 3 | 2 | 1 | 25 |
4 | 5 | 3 | 2 | 1 | 26 |
3 | 5 | 4 | 2 | 1 | 27 |
4.741 | 3.926 | 3.33 | 2 | 1 | میانگین |
5 | 4 | 3 | 2 | 1 | رتبه |
5-2-1- بررسی نرخ برخورد حافظه موقت تحت شرایط مختلف
با توجه به نتایج شکلهای (3) تا (5) جایگزینی محتوا مناسب محتوا، باعث افزایش نرخ برخورد میشود.
|
|
|
|
|
|
|
|
|
شکل (3): بررسی نرخ برخورد حافظه موقت تحت شرایط مختلف با 10% اندازه حافظه موقت (الف)سناریو 1، (ب) سناریو 2، (پ) سناریو 3، (ت) سناریو 4، (ث) سناریو 5، (ج) سناریو 6، (چ) سناریو 7، (ح) سناریو 8، (خ) سناریو 9
|
|
|
|
|
|
|
|
|
شکل (4): بررسی نرخ برخورد حافظه موقت تحت شرایط مختلف با 30% اندازه حافظه موقت (الف)سناریو 10، (ب) سناریو 11، (پ) سناریو 12، (ت) سناریو 13، (ث) سناریو 14، (ج) سناریو 15، (چ) سناریو 16، (ح) سناریو 17، (خ) سناریو 18.
|
|
|
|
|
|
|
|
|
شکل (5): بررسی نرخ برخورد حافظه موقت تحت شرایط مختلف با 60% اندازه حافظه موقت (الف)سناریو 19، (ب) سناریو 20، (پ) سناریو 21، (ت) سناریو 22، (ث) سناریو 23، (ج) سناریو 24، (چ) سناریو 25، (ح) سناریو 26 (خ) سناریو 27.
با افزایش تعدا گرهها نرخ برخورد کاهش مییابد که دلیل آن افزایش تعداد درخواستکنندهها و افزایش تقاضای محتوا است که منجر به اشباع سریعتر مسیریابها و سرانجام افزایش تعداد جایگزینی محتواها میشود. در روش پیشنهادی با در نظر گرفتن معیارهای محبوبیت محتوا و آخرین زمان بازدید، محتواهایی که در حال حاضر بیشتر مورد استفاده قرار میگیرند از حالت ذخیره خارج نمیشوند بنابر این با خارج نشدن محتواهای محبوب نرخ برخورد بهبود پیدا میکند. با افزایش نرخ درخواست، با توجه به اشباع شدن سریعتر مسیریابها وارد فاز جایگزینی محتوا میشویم و نرخ برخورد کاهش مییابد. بنابراین با حذف نکردن محتواهای محبوب احتمال برخورد حافظه موقت افزایش مییابد و روش پیشنهادی عملکرد بهتری از خود نشان میدهد. با افزایش میزان حافظه با توجه به اینکه محتواهای بیشتری میتوانند ذخیره شوند، نرخ برخورد افزایش مییابد. در روش پیشنهادی با توجه به دو معیار محبوبیت محتوا و آخرین زمان بازدید وهمچنین پویا بودن این دو معیار، تعداد بیشتری از محتواها در حالت ذخیره باقی میمانند و همین امر باعث افزایش نرخ برخورد میشود. درصد بهبود روش پیشنهادی نسبت به روشهای مقایسه شده مطابق جدول (12) است.
5-2-2- بررسی میانگین تاخیر تحت شرایط مختلف
مطابق آزمایشات انجام شده شکلهای (6) تا (8) جایگذاری مناسب میتواند باعث کاهش تاخیر دسترسی گردد.
|
|
|
|
|
|
|
|
|
شکل (6): بررسی میانگین تاخیر(میلی ثانیه) تحت شرایط مختلف با 10% اندازه حافظه موقت (الف)سناریو 1، (ب) سناریو 2، (پ) سناریو 3، (ت) سناریو 4، (ث) سناریو 5، (ج) سناریو 6، (چ) سناریو 7، (ح) سناریو 8، (خ) سناریو 9
|
|
|
|
|
|
|
|
|
شکل (7): بررسی میانگین تاخیر(میلی ثانیه) تحت شرایط مختلف با 30% اندازه حافظه موقت (الف)سناریو 10، (ب) سناریو 11، (پ) سناریو 12، (ت) سناریو 13، (ث) سناریو 14، (ج) سناریو 15، (چ) سناریو 16، (ح) سناریو 17، (خ) سناریو 18.
جدول (12): درصد بهبود میانگین نرخ برخورد حافظه موقت روش پیشنهادی نسبت به روشهای مقایسه شده
FIFO | LRU | LFU | IMU |
|
0.07 | 0.08 | 0.1 | 0.21 | میانگین نرخ برخورد |
69.95 | 65.07 | 58 | 13.60 | درصد بهبود |
|
|
|
|
|
|
|
|
|
شکل (8): بررسی میانگین تاخیر(میلی ثانیه) تحت شرایط مختلف با 60% اندازه حافظه موقت (الف)سناریو 19، (ب) سناریو 20، (پ) سناریو 21، (ت) سناریو 22، (ث) سناریو 23، (ج) سناریو 24، (چ) سناریو 25، (ح) سناریو 26 (خ) سناریو 27.
با افزایش تعداد گرهها، تاخیر دسترسی به محتوا افزایش مییابد که دلیل آن طی کردن تعداد بیشتر گامها برای دسترسی به محتوای مورد نظر است. در روش جایگزینی پیشنهادی سعی شده است که در صورت نیاز به جایگزینی، محتواهایی که در حال حاضر بیشتر مورد استفاده قرار میگیرد از حالت ذخیره خارج نشوند که این امر باعث کاهش تاخیر دسترسی میگردد. در روش پیشنهادی از دو پارامتر میزان محبوبیت محتوا و آخرینه زمان بازدید محتوا استفاده شده است که این دو پارامتر باعث میشوند که محتواهایی که اخیرا بیشتر مورد استفاده قرار گرفتهاند از حالت ذخیره خارج نشوند. با افزایش تعداد درخواستهای بسته علاقه امکان اشباع مسیریابها وجود دارد بنابر این افزایش تاخیر را خواهیم داشت. در روش پیشنهادی با توجه به پویا بودن پارامترهای میزان محبوبیت محتوا و آخرینه زمان بازدید، میزان محبوبیت محتواها به صورت مستمر سنجیده میشوند و محتواهایی که کمترین امتیاز را دارند از حالت ذخیره خارج میشوند. با افزایش میزان حافظه کش شاهد کاهش تاخیر خواهیم بود که دلیل آن افزایش میزان دسترسی به محتواها است. جدول (13) درصد بهبود روش پیشنهادی نسبت به روشهای مقایسه شده را نشان میدهد.
جدول (13): درصد بهبود میانگین تاخیر روش پیشنهادی نسبت به روشهای مقایسه شده
FIFO | LRU | LFU | IMU |
|
62.15 | 61.66 | 61.07 | 50.74 | میانگین تاخیر دسترسی |
32.88 | 31.84 | 30.58 | 8.49 | درصد بهبود |
میانگین نتایج روش جایگزینی پیشنهادی مطابق شکلهای (9) و (10) است.
شکل (9): بررسی میانگین نتایج نرخ برخورد در شرایط مختلف.
شکل (10): :بررسی میانگین نتایج تاخیر در شرایط مختلف
در شکلهای (9) و (10) متوسط نتایج روش جایگزینی پیشنهادی با توجه به متغیرهای مستقل که شامل درصد حافظه موقت، تعداد گرهها و نرخ ارسال هستند بررسی شده است. با توجه به رابطه بدست آورده شده روش جایگزینی پیشنهادی و معیارهای در نظر گرفته شده، شاهد بهبود نرخ برخورد و کاهش تاخیر در شرایط مختلف هستیم.
6- نتیجهگیری
در اين مقاله، به معرفی یک روش جایگزینی محتوا برای افزایش نرخ برخورد و کاهش تاخیر در شبکههای مبتنی بر نام پرداخته شد. در روش پیشنهادی در صورت تکمیل شدن ظرفیت مسیریاب، یک محتوا باید از حالت ذخیره خارج گردد تا فضا برای ذخیره محتوای جدید ایجاد شود. برای تعیین محتوایی که باید از حالت ذخیره خارج شود، به محتواهای هر مسیریاب امتیاز تخصیص داده شد. برای تخصیص امتیاز به هر یک از محتواها طبق رابطه بدست آورده شده، محتوایی که کمترین امتیاز را کسب کرده است از حالت ذخیره خارج میشود. در رابطه بدست آورده شده، معیارهای مهم آخرین زمان بازدید محتوا و همچنین محبوبیت محتوا در نظر گرفته شده است. وزندهی معیارهای آخرین زمان بازدید محتوا و محبوبیت محتوا به صورت پویا انجام میشود. با توجه به آزمایشات انجام شده، با حذف نشدن محتواهای محبوب شاهد افزایش نرخ برخود و کاهش تاخیر دسترسی به محتوا به صورت همزمان هستیم.
به عنوان پیشنهاد برای ادامه تحقیق با گسترش دادن شبکه در فضای بزرگتر، و همچنین پیشنهاد یک روش جایگذاری با معیارهای تاثیر گذار در کنار روش جایگزینی محتوا و بررسی نرخ برخورد و تاخیر، بهدنبال حفظ و بهبود کارایی کلی شبکه در شرایط مختلف خواهیم بود.
References
مراجع
[1] D. Dhakal, A. Gautam, S. Dey, K. Sharma, ''A review on forwarding strategies in NDN based vehicular networks'', EMITTER Int’l J. of Engin. Technol., vol. 9, no. 2, pp. 339–356, Dec. 2021 (doi: 10.24003/emitter.v9i2.632).
[2] A. Tariq, R. A. Rehman, B.-S. Kim, ''Forwarding strategies in NDN based wireless networks: a survey'', EEE Communications Surveys & Tutorials, pp. 1–1, 2019 (doi: 10.1109/COMST.2019.2935795).
[3] K. N. Lal, A. Kumar, ''A popularity based content eviction scheme via betweenness-centrality caching approach for content-centric networking (CCN)'', Wireless Netw, vol. 25, no. 2, pp. 585–596, Feb. 2019 (doi: 10.1007/s11276-017-1577-z).
[4] A. Kalghoum, L. A. Saidane, ''FCR-NS: a novel caching and forwarding strategy for named data networking based on software defined networking'', Cluster Comput, vol. 22, no. 3, pp. 981–994, Sep. 2019 (doi: 10.1007/s10586-018-02887-w).
[5] D. He, C. Westphal, J. Jiang, G. Yang, ''RankRoute: efficient interest forwarding using nodes ranking'', Proceeding of the IEEE 2019 International Conference on Computing, Networking and Communications (ICNC), pp. 741–746, Honolulu, HI, USA, Feb. 2019 (doi: 10.1109/ICCNC.2019.8685608).
[6] M. S. M. Shah, Y.-B. Leau, Z. Yan, M. Anbar, ''Hierarchical naming scheme in named data networking for internet of things: a review and future security challenges'', IEEE Access, vol. 10, pp. 19958–19970, 2022 (doi: 10.1109/ACCESS.2022.3151864).
[7] I. V. S. Brito, L. Sampaio, L. Zhang, ''On supporting forwarding strategies and sync protocols through NDN distance vector routing'', Proceeding of the ACM 9th ACM Conference on Information-Centric Networking, pp. 183–185, Osaka Japan, Sep. 2022 (doi: 10.1145/3517212.3559490).
[8] A. Hidouri, N. Hajlaoui, H. Touati, M. Hadded, P. Muhlethaler, ''A survey on security attacks and intrusion detection mechanisms in named data networking'', Computers, vol. 11, no. 12, p. 186, Dec. 2022 (doi: 10.3390/computers11120186).
[9] A. Abrar, A. S. Che Mohamed Arif, K. M. Zaini, ''A mobility mechanism to manage producer mobility in named data networking'', Proceeding of the IEEE 2022 IEEE Region 10 Symposium (TENSYMP), pp. 1–6, Mumbai, India, Jul. 2022 (doi: 10.1109/TENSYMP54529.2022.9864454).
[10] M. Amadeo, C. Campolo, G. Ruggeri, A. Molinaro, ''Popularity-aware closeness based caching in NDN edge networks'', Sensors, vol. 22, no. 9, p. 3460, May 2022 (doi: 10.3390/s22093460).
[11] S. Lee, I. Yeom, D. Kim, ''T-caching: enhancing feasibility of In-network caching in ICN'', IEEE Trans. Parallel Distrib. Syst., vol. 31, no. 7, pp. 1486–1498, Jul. 2020 (doi: 10.1109/TPDS.2020.2970702).
[12] M. Amadeo, C. Campolo, G. Ruggeri, A. Molinaro, ''Beyond edge caching: freshness and popularity aware IoT data caching via NDN at internet-scale'', IEEE Trans. on Green Commun. Netw., vol. 6, no. 1, pp. 352–364, Mar. 2022 (doi: 10.1109/TGCN.2021.3124452).
[13] R. K. Dudeja, R. S. Bali, G. S. Aujla, ''Secure and pervasive communication framework using named data networking for connected healthcare'', Computers and Electrical Engineering, vol. 100, p. 107806, May 2022 (doi: 10.1016/j.compeleceng.2022.107806).
[14] X. Wang, Y. Lu, ''Sustainable and efficient fog-assisted IoT cloud based data collection and delivery for smart cities'', IEEE Trans. Sustain. Comput., vol. 7, no. 4, pp. 950–957, Oct. 2022 (doi: 10.1109/TSUSC.2022.3188330).
[15] P. Mekbungwan, G. Pau, K. Kanchanasut, ''In-network computation for IoT data processing with active NDN in wireless sensor networks'', Proceeding of the IEEE 2022 5th Conference on Cloud and Internet of Things (CIoT), pp. 197–204, Marrakech, Morocco, Mar. 2022 (doi: 10.1109/CIoT53061.2022.9766613).
[16] E. T. da Silva, A. L. D. Costa, J. M. H. de Macedo, ''On the realization of VANET using named data networking: On improvement of VANET using NDN‐based routing, caching, and security'', Int J Communication, vol. 35, no. 18, Dec. 2022 (doi: 10.1002/dac.5348).
[17] B. Hao, G. Wang, M. Zhang, J. Zhu, L. Xing, Q. Wu, ''Stochastic adaptive Forwarding strategy based on deep reinforcement learning for secure mobile video communications in NDN'', Security and Communication Networks, vol. 2021, pp. 1–13, Apr. 2021 (doi: 10.1155/2021/6630717).
[18] M. Meddeb, A. Dhraief, A. Belghith, T. Monteil, K. Drira, H. Mathkour, ''Least fresh first cache replacement policy for NDN-based IoT networks'', Pervasive and Mobile Computing, vol. 52, pp. 60–70, Jan. 2019 (doi: 10.1016/j.pmcj.2018.12.002).
[19] C. E. Shannon, ''A mathematical theory of communication'', Bell System Technical Jour, vol. 27, pp. 379–423, Oct. 1948.
[20] M. Zhang, H. Luo, H. Zhang, ''A survey of caching mechanisms in information-centric networking'', IEEE Commun. Surv. Tutorials, vol. 17, no. 3, pp. 1473–1499, 2015 (doi: 10.1109/COMST.2015.2420097).
[21] D. Grund, J. Reineke, ''Precise and efficient FIFO-replacement analysis based on static phase detection'', Proceeding of the IEEE 2010 22nd Euromicro Conference on Real-Time Systems, pp. 155–164, Brussels, Belgium, Jul. 2010 (doi: 10.1109/ECRTS.2010.8).
[22] Z. Li, D. Liu, H. Bi, ''CRFP: a novel adaptive replacement policy combined the LRU and LFU policies'', Proceeding of the 2008 IEEE 8th International Conference on Computer and Information Technology Workshops, pp. 72–79, Sydney, QLD, Jul. 2008 (doi: 10.1109/CIT.2008.Workshops.22).
[23] S. Chootong, J. Thaenthong, ''Cache replacement mechanism with content popularity for vehicular content-centric networks (VCCN)'', Proceeding of the IEEE 2017 14th International Joint Conference on Computer Science and Software Engineering (JCSSE), NakhonSiThammarat, Thailand, pp. 1–6, Jul. 2017 (doi: 10.1109/JCSSE.2017.8025901).
[24] Y. Li, M. Yu, R. Li, ''A cache replacement strategy based on hierarchical popularity in NDN'', Proceeding of the IEEE 2018 Tenth International Conference on Ubiquitous and Future Networks (ICUFN), pp. 159–161, Prague, Czech, Jul. 2018 (doi: 10.1109/ICUFN.2018.8436597).
[25] Y. Liu, T. Zhi, H. Xi, W. Quan, H. Zhang, ''A novel cache replacement scheme against cache pollution attack in content-centric networks'', Proceeding of the 2019 IEEE/CIC International Conference on Communications in China (ICCC), pp. 207–212, Changchun, China, Aug. 2019 (doi: 10.1109/ICCChina.2019.8855925).
[26] M. A. P. Putra, H. Situmorang, N. R. Syambas, ''Least recently frequently used replacement policy named data networking approach'', Proceeding of the IEEE 2019 International Conference on Electrical Engineering and Informatics (ICEEI), pp. 423–427, Bandung, Indonesia, Jul. 2019 (doi: 10.1109/ICEEI47359.2019.8988828).
[27] N. Alzakari, A. B. Dris, S. Alahmadi, ''Randomized least frequently used cache replacement strategy for named data networking'', Proceeding of the IEEE 2020 3rd International Conference on Computer Applications & Information Security (ICCAIS), pp. 1–6, Riyadh, Saudi Arabia, Mar. 2020 (doi: 10.1109/ICCAIS48893.2020.9096733).
[28] S. Al-Ahmadi, ''A new efficient cache replacement strategy for named data networking'', IJCNC, vol. 13, no. 5, pp. 19–35, Sep. 2021 (doi: 10.5121/ijcnc.2021.13502).
[29] S. Rashid, S. A. Razak, F. A. Ghaleb, ''IMU: a content replacement policy for CCN, based on immature content selection'', Applied Sciences, vol. 12, no. 1, p. 344, Dec. 2021 (doi: 10.3390/app12010344).
[30] E. T. da Silva, J. M. H. de Macedo, A. L. D. Costa, ''NDN content store and caching policies: Performance Evaluation'', Computers, vol. 11, no. 3, p. 37, Mar. 2022 (doi: 10.3390/computers11030037).
[31] J. Hou, H. Lu, A. Nayak, ''A GNN-based proactive caching strategy in NDN networks'', In Review, preprint, Jun. 2022 (doi: 10.21203/rs.3.rs-1713271/v1).
[32] Y. Zha, P. Cui, Y. Hu, L. Xue, J. Lan, Y. Wang, ''An NDN cache-optimization strategy based on dynamic popularity and replacement value'', Electronics, vol. 11, no. 19, p. 3014, Sep. 2022 (doi: 10.3390/electronics11193014).
[33] J. Hou, H. Xia, H. Lu, A. Nayak, ''A graph neural network approach for caching performance optimization in NDN networks'', IEEE Access, vol. 10, pp. 112657–112668, 2022 (doi: 10.1109/ACCESS.2022.3217236).
[34] A. Narayanan, S. Verma, E. Ramadan, P. Babaie, Z.-L. Zhang, ''Making content caching policies “smart” using the deepcache framework'', SIGCOMM Comput. Commun. Rev., vol. 48, no. 5, pp. 64–69, Jan. 2019 (doi: 10.1145/3310165.3310174).
[35] B. Panigrahi, S. Shailendra, H. K. Rath, A. Simha, ''Universal caching model and markov-based cache analysis for information centric networks'', Photon Netw Commun, vol. 30, no. 3, pp. 428–438, Dec. 2015 (doi: 10.1007/s11107-015-0570-7).
[36] J. Yao, B. Yin, X. Tan, ''A SMDP-based forwarding scheme in named data networking'', Neurocomputing, vol. 306, pp. 213–225, Sep. 2018 (doi: 10.1016/j.neucom.2018.03.057).
زیرنویسها:
[1] Named data network(NDN)
[2] Internet protocol(IP)
[3] Transmission Control Protocol/Internet Protocol
[4] Information-oriented network
[5] Content store (CS)
[6] Pending interest(PIT)
[7] Forward information base (FIB)
[8] Caching
[9] Internet of things (IoT)
[10] Smart healthcare
[11] Smart cities
[12] Wireless networking
[13] Vehicle-to-Vehicle
[14] Video streaming
[15] Simple Additive Weighting (SAW)
[16] Interest Packet )I_pkt)
[17] Data Packet (D_pkt)
[18] Normalize
[19] Last Recently Used (LRU)
[20] First-in-First-out (FIFO)
[21] Least Frequently Used (LFU(
[22] maturity/immaturity