[發明專利]一種名字路由快速匹配查找方法與裝置

有效

• 申請號: 201410059219.9
• 申請日: 2014-02-21
• 公開（公告）號: CN103873371B
• 公開（公告）日: 2017-11-28
• 發明（設計）人: 關建峰;許長橋;張宏科;權偉;韓冰潔;張萌;李杰;石春秋
• 申請（專利權）人: 北京郵電大學
• 主分類號: H04L12/743
• 分類號: H04L12/743;H04L12/753;H04L29/08;G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種名字路由快速匹配查找方法，其特征在于，首先將路由前綴分解成二元組，即T段（T-segment）和B段（B-segment），依次存儲于樹位圖（Tree Bitmap）單元和布隆濾波（Bloom filter）單元，隨后對T段進行匹配，匹配成功后再對B段進行匹配，其中，所述將路由前綴分解成二元組，依次存儲于樹位圖單元和布隆濾波單元的步驟包括：

步驟1、將名字前綴分解為T段和B段，其中，SL（Split Level）稱為名字前綴的分解水平，T段為名字前綴的前SL層，B段為名字前綴的剩余部分；

步驟2、將T段插入樹位圖中，將B段插入到T段構成的樹中相應節點指向的計數布隆濾波器（Counting Bloom filter）中；其中，對T段進行匹配，匹配成功后再對B段進行匹配的步驟還包括：

步驟A、將請求內容的名字，比如N，分解成T段和B段，在T段樹中查找T段的最長匹配前綴，如果T段的最長匹配前綴不存在，執行步驟D；如果T段的最長匹配前綴的層數小于SL，取得T段的最長匹配前綴對應的轉發端口號,執行步驟E；否則，執行步驟B；

步驟B、對B段的前1層，前2層，前3層…前n層并行地在第1號計數布隆濾波器、第2號計數布隆濾波器、第3號計數布隆濾波器…第n號計數布隆濾波器中進行成員關系查找，把查找結果輸出到棧S，執行步驟C；

步驟C、取棧S頂元素SF（棧S頂元素用SF表示），將T段的最長匹配前綴和B段的前SF層的內容連接起來，得到N的最長匹配前綴，通過對N的最長匹配前綴進行哈希計算取得轉發端口號，執行步驟E；

步驟D、將請求包從路由器的默認端口轉發；

步驟E、將請求包從路由器的口轉發。

2.如權利要求1所述方法，其特征在于，將T段插入到樹位圖的步驟是指將所有名字前綴的T段放在一個樹位圖中，形成一個T段樹（T-segment Tree）。

3.如權利要求1所述方法，其特征在于，將B段插入到布隆濾波器的步驟是指將所有名字前綴的B段分別插入到所屬T段所在節點指向的具有相同層數的計數布隆濾波器中，例如，存在三個前綴

a./cn/com/sina/movie/Hollywood

b./cn/com/sina/movie/Hollywood/hottest/M1

c./cn/edu/course/spring

取SL=3，則cn/com/sina和cn/edu/course存儲在樹位圖中，course、sina這兩個節點分別指向自己的布隆濾波器組；前綴c的B段為/spring要插入到course指向的第1號計數濾波器中，因為/spring只有一層；而前綴a、b的B段分別為/movie/Hollywood和/movie/Hollywood/hottest/M1，要插入到sina指向的第2號計數布隆濾波器和第4號計數布隆濾波器中。

4.根據權利要求1所述的方法，其特征在于，所述步驟B中輸出查找結果棧S，是指將查詢結果為真的計數布隆濾波器號碼按從小到大的順序存入空棧S中；例如，B段為com/goole/music/，如果“com/”存在于1號計數布隆濾波器中，“com/goole/”存在于2號計數布隆濾波器中，“com/goole/music/”存在于3號計數布隆濾波器中，則棧S中從底到頂存儲的是：1，2，3，其中3為棧頂元素SF。

5.如權利要求1所述的方法，其特征在于，所述步驟A中返回的路由器的默認端口，是指沒有任何名字前綴與請求內容的名字匹配，則該請求會被從某個固定端口轉發。

6.如權利要求1所述的方法，其特征在于，其根據要插入或刪除名字的層數以及是否存在匹配前綴對樹位圖和布隆濾波器進行更新操作。