[發明專利]一種用于命名數據網絡中網絡節點的轉發方法、裝置、系統及存儲介質

在審

• 申請號: 201910879763.0
• 申請日: 2019-09-18
• 公開（公告）號: CN110417661A
• 公開（公告）日: 2019-11-05
• 發明（設計）人: 李揮;胡嘉偉;鄔江興;黃婷;伊鵬;侯韓旭;馬化軍;尹峰
• 申請（專利權）人: 北京大學深圳研究生院;國家數字交換系統工程技術研究中心;佛山賽思禪科技有限公司
• 主分類號: H04L12/741
• 分類號: H04L12/741;H04L12/751
• 代理公司: 深圳市科吉華烽知識產權事務所(普通合伙) 44248
• 代理人: 胡玉

1.一種用于命名數據網絡中網絡節點的轉發方法，包括哈希表、前綴樹，其特征在于，由哈希表和前綴樹構成FIB，對于FIB中存儲的任一個名字，其所有的真前綴在FIB中擁有相應的表項，檢查前綴是否存在并添加對應輔助表項的過程被稱為FIB重構，在重構后的FIB中，表項被分為實表項和非實表項，非實表項分為虛表項和半虛表項；

在哈希表中，以名字作為key, 并以前綴樹中的節點作為value，由此實現了從名字到前綴樹中轉發信息的快速檢索；

前綴樹中的邊均代表一個名字組件，前綴樹的每個節點都代表一個名字，該節點存儲了名字對應的轉發信息和表項的對應類別、以及用于維持前綴樹結構的指針；

實表項：實表項中的名字均指代實際存在的數據，并用于指導興趣包的轉發；在FIB重構之前，所有的表項均為實；

非實表項：用于支持隨機搜索算法的輔助表項被稱作非實表項，非實表項中的名字不指代任何實際存在的數據，且無法用于指導興趣包的轉發；

虛表項：若一個非實表項不擁有任何實前綴，則稱該非實表項為虛表項；當隨機搜索過程以虛表項結束時，直接結束而不會產生任何假陰性錯誤；

半虛表項：若該非實表項存在實前綴，則該非實表項稱為半虛表項并需要進行回溯查找；

FIB：轉發信息表；

該轉發方法包括搜索步驟，所述搜索步驟包括：

步驟1：通過隨機搜索算法查詢興趣包中的名字，從而獲取轉發出報文的端口；

步驟2：判斷最后一次HIT的前綴是否為實，若是，返回該前綴作為查詢結果，否則執行步驟3；

步驟3：判斷最后一次HIT的前綴是否為虛，若是，返回查詢失敗，否則執行步驟4；

步驟4：在前綴樹中向上回溯至第一個實節點，返回其對應的轉發信息。

2.根據權利要求1所述的轉發方法，其特征在于，該轉發方法還包括插入步驟，所述插入步驟用于將名字插入到FIB中，所述插入步驟包括：

首先，判斷在FIB中查詢待插入的名字是否存在，若是，那么執行第一插入步驟，否則執行第二插入步驟；

所述第一插入步驟包括：

步驟一：判斷名字對應的表項是否為實表項，若是，那么更新其轉發信息，否則執行步驟二；

步驟二：判斷名字對應的表項是否為虛表項，若是，那么執行步驟三，否則執行修改步驟；

步驟三：將其子樹中所有的虛表項修改為半虛表項，然后執行修改步驟；

修改步驟：修改其類別為實表項并添加轉發信息；

所述第二插入步驟包括：

首先，在FIB中查詢待插入的名字的LPM，若HIT且為實，那么執行第一處理步驟，若MISS、或HIT且為虛，那么執行第二處理步驟；

第一處理步驟：插入名字對應的實表項，在FIB中查找名字所有的真前綴，若不存在則插入對應的半虛表項；

第二處理步驟：插入名字對應的實表項，在FIB中查找名字所有的真前綴，若不存在則插入對應的虛表項；

LPM：最長前綴匹配。

3.根據權利要求1所述的轉發方法，其特征在于，該轉發方法還包括刪除步驟，所述刪除步驟用于將過時的非實表項進行發現和回收，所述刪除步驟包括：

首先，判斷在FIB中的待刪除的名字的對應表項是否存在子節點，若是，那么執行第一刪除步驟，否則執行第二刪除步驟；

第一刪除步驟：判斷對應表項的父節點是否為虛，若為虛，那么，執行第一刪除子步驟，若對應表項的父節點為實或半虛，那么，名字的表項類別修改為半虛；

第一刪除子步驟：將名字對應的表項類別修改為虛，然后，遍歷以名字為根的子樹，若其中某個節點滿足第1條件和第2條件，那么該節點的類別修改為虛，第1條件：類別為半虛，第2條件：該節點到名字的路徑上沒有任何實節點；

第二刪除步驟：刪除該表項，然后，遞進地向上檢查名字的所有真前綴，若該前綴的對應節點滿足第一點和第二點，那么刪除該節點，第一點：類別為非實，第二點：為葉節點。

4.根據權利要求1至3任一項所述的轉發方法，其特征在于，隨機搜索算法為二分查找算法，在步驟1中，通過二分查找算法查詢興趣包中的名字，從而獲取轉發出報文的端口；

當二分查找過程以虛表項結束時，直接結束而不會產生任何假陰性錯誤。