簡易檢索 / 詳目顯示

回結果列表
研究生： 林浩陽
Lin, Hao-Yang
論文名稱： 結合階層式線性模型與字典序排序之基於學習的命名資料網路最長前綴匹配方法
A Learning Approach for the Longest Prefix Match Problem in Named Data Networks Using Hierarchical Linear Models and Lexicographic Sort
指導教授： 張燕光
Chang, Yeim-Kuan
學位類別： 碩士
Master
系所名稱： 電機資訊學院 - 資訊工程學系
Department of Computer Science and Information Engineering
論文出版年： 2025
畢業學年度： 113
語文別： 英文
論文頁數： 78
中文關鍵詞： 命名資料網路(NDN) 、轉送資訊庫(FIB) 、最長前綴匹配(LPM) 、學習式索引結構
外文關鍵詞： Named Data Networking (NDN), Forwarding Information Base (FIB), Longest Prefix Match (LPM), Learned Index Structure
相關次數： 點閱：8  下載：0 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 命名資料網路（Named Data Networking, NDN）是一種前瞻性的未來網際網路架構，它將通訊模式從傳統以主機為中心的位址導向，轉變為以內容為核心的通訊方式，允許使用者透過內容名稱直接擷取資料，而非依據物理位置尋找。在 NDN 中，其中一項核心挑戰是如何在轉送資訊庫（Forwarding Information Base, FIB）中有效地執行最長前綴匹配（Longest Prefix Match, LPM）。由於NDN名稱具有階層性以及可變長度的特性，傳統的 IP 查找方法無法直接應用於 NDN 環境。
    在本論文中，我們提出一種新穎的學習型方法來解決 NDN 中的 LPM 問題。我們的方法利用階層式線性模型計算目標名稱的大致位置，並縮小搜尋範圍。此外，現有的學習型索引模型無法直接支援 LPM，因此我們引入了一種新的設計，透過建立父索引表（parent index table）以定位最長匹配前綴。為了減輕頻繁重新建構（reconstruction）所帶來的高成本，我們亦設計了兩種適用於動態更新場景的替代性插入策略。
    我們使用從 DMOZ 轉換而來的資料集對所提方法進行評估，並與現有最先進的 NDN FIB 資料結構進行比較。實驗結果顯示，所提出的方法在大規模資料集上能顯著降低記憶體消耗，同時維持競爭力的查找效能；相較於傳統方法，記憶體使用量最高可減少 27%，查找時間約可加快 4.9%。

    Named Data Networking (NDN) is a promising future Internet architecture that shifts from host-based addressing to content-centric communication, allowing users to retrieve data directly by content names rather than physical locations. One of the core challenges in NDN is efficiently performing Longest Prefix Match (LPM) in the Forwarding Information Base (FIB). Due to the hierarchical and variable-length characteristics of name structures, traditional IP lookup methods cannot be directly applied to NDN environments.
    In this thesis, we propose a novel learning-based approach to address the LPM problem in NDN. Our method leverages a hierarchical linear model to calculate the approximate position and narrow the search range of the target name. Furthermore, existing learned index models cannot directly support LPM, we introduce a new design that builds a parent index table to locate the longest matching prefix. To mitigate the high cost of frequent full reconstructions, we also design two alternative insertion strategies suitable for dynamic update scenarios.
    We evaluate our approach using datasets converted from DMOZ, comparing it with state-of-the-art NDN FIB data structures. Experimental results show that our proposed method significantly reduces memory consumption while maintaining competitive lookup performance, achieving up to 27% lower memory usage and approximately 4.9% faster lookup time than traditional methods in large-scale datasets.

    摘要 i Abstract ii 誌謝 iii TABLE OF CONTENTS iv LIST OF TABLES vi LIST OF FIGURES vii Chapter 1 Introduction 1 1.1 Introduction 1 1.2 Organization of the Thesis 3 Chapter 2 Background 4 2.1 Named Data Networking (NDN) 4 2.1.1 Packet Routing in NDN Router 5 2.1.2 Name Type in NDN 7 2.1.3 Longest Prefix Match 7 2.2 Learned Index Structure 8 2.2.1 Build Procedure 11 2.2.2 Search Procedure 12 2.3 Learned Index Structure for String 12 Chapter 3 Related Work 15 3.1 Forwarding Information Base in Named Data Networking 15 3.1.1 Bloom Filter Based Method 15 3.1.2 Hash Table Based Method 17 3.1.3 Hash Table with Bloom Filter 18 3.1.4 Trie Based Method 20 3.2 Learned Index Structures in Network Data Structures 23 3.2.1 NuevoMatch 23 3.2.2 Learning Name Index (LNI) 25 Chapter 4 Proposed Scheme 27 4.1 Motivation 27 4.2 Proposed Name Prefix Search Scheme 27 4.2.1 Parent Index Traversal 28 4.2.2 Lower-Bound Search 29 4.2.3 Name Lookup in Scheme 30 4.3 Validation of the Name Lookup Scheme 32 4.4 Parent Index Table Construction 35 4.5 Learned Index Model in our Scheme 38 4.5.1 Overview 38 4.5.2 Build Procedure 39 4.5.3 Search Procedure for the Ideal Scenario 41 4.5.4 Search Procedure for the Non-Ideal Scenario 42 4.6 Updated in Proposed Method 44 4.6.1 Method 1: Insert via Linked List 45 4.6.2 Method 2: Insert into Auxiliary Structure 51 Chapter 5 Experimental Results 55 5.1 Experimental Environment 55 5.2 Average Search Time 59 5.3 Memory Consumption 61 5.4 Building Time 62 5.5 Comparison of Update Methods 64 Chapter 6 Conclusion 65 References 66

    [1] L. Zhang, A. Afanasyev, J. Burke, V. Jacobson, k. claffy, P. Crowley, C. Papadopoulos, L. Wang, and B. Zhang, “Named data networking,” SIGCOMM Comput. Commun. Rev., vol. 44, no. 3, pp. 66–73, Jul. 2014
    [2] T. Kraska, A. Beutel, E. H. Chi, J. Dean, and N. Polyzotis, “The case for learned index structures,” in Proc. Int. Conf. Management of Data (SIGMOD), 2018, pp. 489–504.
    [3] A. Rashelbach, O. Rottenstreich, and M. Silberstein, “A computational approach to packet classification,” in Proc. ACM SIGCOMM, 2020, pp. 542–556
    [4] Y. Wang, T. Pan, Z. Mi, H. Dai, X. Guo, T. Zhang, B. Liu, and Q. Dong, “Namefilter: Achieving fast name lookup with low memory cost via applying two-stage bloom filters,” in INFOCOM. IEEE, 2013, pp. 95–99.
    [5] A. Afanasyev, J. Shi, B. Zhang, L. Zhang, I. Moiseenko, Y. Yu, W. Shang, Y. Huang, J. P. Abraham, and S. DiBenedetto, “NFD developer’s guide,” Technical report, NDN-0021, NDN, 2014.
    [6] W. So, A. Narayanan and D. Oran, "Named data networking on a router: Fast and DoS-resistant forwarding with hash tables," Architectures for Networking and Communications Systems, San Jose, CA, USA, 2013, pp. 215-225.
    [7] Y. Wang, T. Huang, G. Wei, H. Li, and H. Zhang, “Scalable name identifier lookup for Industrial Internet,” Computer Communications, vol. 186, pp. 102–109, 2022.
    [8] J. Kim, M.-C. Ko, M. S. Shin, and J. Kim, “Scalable name lookup for NDN using hierarchical hashing and Patricia Trie,” Appl. Sci., vol. 10, no. 3, p. 1023, 2020.
    [9] J. Seo and H. Lim, “Bitmap-based priority-NPT for packet forwarding at named data network,” Computer Communications, vol. 130, pp. 101–112, 2018.
    [10] Z. Li, J. Liu, L. Yan, B. Zhang, P. Luo and K. Liu, "Smart Name Lookup for NDN Forwarding Plane via Neural Networks," in IEEE/ACM Transactions on Networking, vol. 30, no. 2, pp. 529-541, April 2022.
    [11] M. A. Ruiz-Sanchez, E. W. Biersack, and W. Dabbous, “Survey and taxonomy of IP address lookup algorithms,” IEEE Network, vol. 15, no. 2, pp. 8–23, Mar.–Apr. 2001.
    [12] V. Jacobson, D. K. Smetters, J. D. Thornton, M. Plass, N. Briggs, and R. Braynard, “Networking named content,” in Proc. CoNEXT, 2009, pp. 1–12.
    [13] M. F. Bari, S. R. Chowdhury, R. Ahmed, R. Boutaba, and B. Mathieu, “A survey of naming and routing in information-centric networks,” IEEE Commun. Mag., vol. 50, no. 12, pp. 44–53, Dec. 2012.
    [14] J. Ding, U. F. Minhas, J. Yu, C. Wang, J. Do, Y. Li, H. Zhang, B. Chandramouli, J. Gehrke, D. Kossmann, D. Lomet, and T. Kraska, “ALEX: An updatable adaptive learned index,” Proc. 2020 ACM SIGMOD Int. Conf. Manag. Data (SIGMOD ’20), New York, NY, USA, pp. 969–984, 2020.
    [15] P. Ferragina and G. Vinciguerra, “The PGM-index: A fully-dynamic compressed learned index with provable worst-case bounds,” Proc. VLDB Endow., vol. 13, no. 8, pp. 1162–1175, Apr. 2020.
    [16] Y. Yang and S. Chen, “LITS: An optimized learned index for strings,” Proc. VLDB Endow., vol. 17, no. 11, pp. 3415–3427, Jul. 2024.
    [17] Y. Wang, C. Tang, Z. Wang, and H. Chen, “SIndex: A scalable learned index for string keys,” in Proc. APSys, 2020, pp. 17–24.
    [18] W. Zhou and S. Yang, “SLIPP: A space-efficient learned index for string keys,” in Proc. BDSIC, 2024, pp. 69–77.
    [19] S. Jang, H. Byun, and H. Lim, “Dynamically allocated Bloom filter-based PIT architectures,” IEEE Access, vol. 10, pp. 28165–28179, 2022.
    [20] G. Pike and J. Alakuijala, “Introducing CityHash,” 2011. [Online]. Available: https://opensource.googleblog.com/2011/04/introducing-cityhash.html.
    [21] DMOZ – The Open Directory Project. https://dmoztools.net (accessed: Dec. 2023).

    無法下載圖示 校內：2029-09-01公開
    校外：2029-09-01公開
    電子論文尚未授權公開，紙本請查館藏目錄
    QR CODE