[發明專利]命名數據網轉發平面的FIB存儲結構及其使用方法

在審

• 申請號: 201810428740.3
• 申請日: 2018-05-07
• 公開（公告）號: CN110460528A
• 公開（公告）日: 2019-11-15
• 發明（設計）人: 李卓;劉開華;許亞平
• 申請（專利權）人: 天津師范大學
• 主分類號: H04L12/741
• 分類號: H04L12/741;H04L12/743;H04L12/745
• 代理公司: 12214 天津創智天誠知識產權代理事務所(普通合伙)
• 代理人: 周慶路<國際申請>=<國際公布>=<進入

1.一種命名數據網轉發平面的FIB存儲結構，其特征在于：包括一個片內存儲單元和一個片外存儲單元；其中，所述片內存儲單元中具有W個相同的可定位型布隆濾波器，所述可定位型布隆濾波器由一個通用型布隆濾波器和一個定位數組組成，所述片外存儲單元具有字節數組、計數布隆濾波器組以及多個動態存儲器，所述字節數組由W個相同的字節數構成，用于存儲要檢索的數據名稱所對應的地址偏移量，所述計數布隆濾波器組由W個相同的計數布隆濾波器構成，與其他結構配合實現數據的插入和更新，所述動態存儲器用于實現數據路由轉發信息的存儲。

2.根據權利要求1所述的一種命名數據網轉發平面的FIB存儲結構，其特征在于：所述的片內存儲單元為高速存儲器，所述的片外存儲單元為低速存儲器。

3.根據權利要求1所述的一種命名數據網轉發平面的FIB存儲結構，其特征在于：所述的通用型布隆濾波器平均分為j個大小相同的部分，同時定位數組的大小設置為j比特，通用型布隆濾波器的每一個部分依次對應定位數組的一個比特位。

4.根據權利要求1所述的一種命名數據網轉發平面的FIB存儲結構，其特征在于：Bit定位數組p的槽個數與定位數組的大小設置成指數關系，即字節數的槽個數為2^j，并平均分為N部分；然后根據該定位數組的數值可以計算出該數據名稱在Bit定位數組p中的第m(m＝1，2，…，N-1，N)部分，以及該部分的具體槽位置。

5.一種如權利要求1-4任一項所述命名數據網轉發平面的FIB存儲結構的使用方法，其特征在于：包括在所述FIB存儲結構中針對數據名稱的插入數據方法、數據檢索的方法或更新方法；

所述的數據插入方法包括以下步驟，

步驟11：定位數組初始化：數據插入前，將定位數組中的所有比特位初始化為0；

步驟12：輸入數據名稱：將數據名稱輸入到所述的命名數據網轉發平面FIB存儲結構中；

步驟13：對該數據名稱進行K次哈希編碼：

步驟14：將K次哈希操作所映射的通用型布隆濾波器的比特位數值全部置為1：即如果哈希操作映射到通用型布隆濾波器的一個比特位，則該比特位置1，通過K次哈希操作后數據名稱被插入到通用型布隆濾波器中；

步驟15：將K次哈希操作所映射到的計數布隆濾波器的計數器加1：即如果哈希操作映射到計數布隆濾波器的一個計數器，則該計數器加1，通過K次哈希操作后數據名稱被插入到計數布隆濾波器中；

步驟16：計算定位數組的數值及計算該數據名稱在字節數中的位置：根據該數據名稱的K次哈希操作在通用型布隆濾波器中的映射值，計算得出定位數組的數值；然后，根據上述的定位數組的數值計算該數據名稱在字節數中的第幾部分的第幾槽內；

步驟17：為該數據名稱分配地址偏移量：根據上述操作得到的該數據名稱插入到所在部分的順序為該數據名稱標序號，該序號即為該數據名稱在片外存儲單元對應的動態存儲器中的地址偏移量，并將該地址偏移量存儲在該數據名稱所在的字節數組的字節數的槽內；

步驟18：將數據路由轉發信息存儲于動態存儲器：根據上述操作分配的該數據名稱的地址偏移量和其所對應的動態存儲器的基地址為該數據名稱分配存儲空間，并將該數據的路由轉發信息存儲于該存儲空間內；

步驟19：數據名稱插入操作結束。