[發(fā)明專利]一種實現高速路由查找的方法和系統(tǒng)

有效

• 申請?zhí)枺?/td>: 201110314798.3
• 申請日: 2011-10-17
• 公開（公告）號: CN102333036A
• 公開（公告）日: 2012-01-25
• 發(fā)明（設計）人: 孫遠航;李彧;程晨;劉博巖;趙有健;全成斌
• 申請（專利權）人: 中興通訊股份有限公司
• 主分類號: H04L12/56
• 分類號: H04L12/56
• 代理公司: 北京派特恩知識產權代理事務所(普通合伙) 11270
• 代理人: 程立民;蔣雅潔

技術領域

本發(fā)明涉及路由查找技術領域，特別是指一種基于哈希(Hash)函數和Bloom?Filter(BF)實現高速路由查找的方法和系統(tǒng)。

背景技術

隨著互聯(lián)網(Internet)的迅猛發(fā)展，用于主干網絡互聯(lián)的核心路由器的接口速率已經達到100Gbps，該速率要求核心路由器在支持大容量路由表的情況下路由查找，即IP查找的速率達到每秒幾百萬次。

IP查找需要得到最長匹配前綴，由于高速查找的需要，軟件查找的方式已經不適用，近年來研究人員提出了多種硬件查找方法以提高查找速率，其中以查找樹(Trie)結構和三態(tài)內容尋址存儲器(Ternary?Content?Addressable?Memory，TCAM)最為流行。

Trie以樹形結構為基礎，通過流水處理能夠得到較高的吞吐率。由于樹結構的特殊性，使得每級流水難以達到存儲平衡，且每個樹結點都要維護子結點信息，造成存儲需求很大。利用一些優(yōu)化方法可以達到存儲平衡，但容易造成流水級數過多，難以維護。

TCAM是目前查找模塊中利用較為廣泛的技術，查找過程簡單，但要滿足100Gbps的查找速率要求需要多片TCAM調度查找，功耗與發(fā)熱量將成為嚴重問題。

發(fā)明內容

有鑒于此，本發(fā)明的主要目的在于提供一種實現高速路由查找的方法和系統(tǒng)，能夠快速、穩(wěn)定的實現大容量路由表的查詢。

為達到上述目的，本發(fā)明的技術方案是這樣實現的：

本發(fā)明提供了一種實現高速路由查找的方法，所述方法包括：

利用哈希(Hash)函數和Bloom?Filter(BF)將路由表項編碼并儲存；

利用Hash和Bloom?Filter對輸入IP地址進行查詢匹配，找到最長前綴匹配的路由表項。

其中，所述利用Hash和Bloom?Filter將路由表項編碼，包括：

隨機生成各級哈希函數并儲存；按照路由前綴長度，對表項進行分組；在同一長度內，針對表項的起始地址根據哈希結果編碼得到哈希BF(HBF)；針對HBF中各個表項的偏移地址編碼得到分類BF(CBF)；對每個表項計算摘要，并根據CBF編碼結果組織摘要和完整路由表項的儲存。

其中，在CBF編碼之后，所述方法還包括：進行CBF驗證，確保組內各CBF不沖突，否則隨機更換哈希函數，重新編碼HBF和CBF。

其中，所述利用Hash和Bloom?Filter對輸入IP地址進行查詢匹配，包括：

根據輸入IP地址經過哈希查詢HBF，得到一組表項的起始地址；同時，根據輸入IP地址經過哈希查詢CBF，得到偏移地址；將起始地址加上偏移地址得到唯一的命中表項；根據命中表項讀取摘要，與輸入IP地址計算出的摘要進行對比，如果相同，則找到最長前綴匹配的路由表項；如果不同，則將所述輸入IP地址存儲在緩存(Cache)中。

其中，在利用Hash和Bloom?Filter對輸入IP地址進行查詢匹配之前，所述方法還包括：根據輸入IP地址查詢Cache，如果命中則表示路由表項中沒有所述輸入IP地址，否則利用Hash和Bloom?Filter對輸入IP地址進行查詢匹配。

其中，在所述HBF編碼之前，所述方法還包括：針對各個路由前綴長度編碼生成查詢BF(QBF)；

在根據輸入IP地址經過哈希查詢HBF之前，所述方法還包括：根據輸入IP地址經過哈希查詢QBF。

本發(fā)明還提供了一種實現高速路由查找的系統(tǒng)，所述系統(tǒng)包括：路由表項編碼儲存模塊和路由表項查詢模塊；其中，

所述路由表項編碼儲存模塊，用于利用Hash函數和Bloom?Filter將路由表項編碼并儲存；

所述路由表項查詢模塊，用于利用Hash和Bloom?Filter對輸入IP地址進行查詢匹配，找到最長前綴匹配的路由表項。

其中，所述路由表項編碼儲存模塊利用Hash和Bloom?Filter將路由表項編碼，包括：

隨機生成各級哈希函數并儲存；按照路由前綴長度，對表項進行分組；在同一長度內，針對表項的起始地址根據哈希結果編碼得到HBF；針對HBF中各個表項的偏移地址編碼得到CBF；對每個表項計算摘要，并根據CBF編碼結果組織摘要和完整路由表項的儲存。

其中，所述路由表項編碼儲存模塊，在CBF編碼之后，還用于進行CBF驗證，確保組內各CBF不沖突，否則隨機更換哈希函數，重新編碼HBF和CBF。