[發明專利]查找方法和查找裝置無效

申請號：	201310049635.6	申請日：	2013-02-07
公開（公告）號：	CN103986656A	公開（公告）日：	2014-08-13
發明（設計）人：	郭玲波;錢俊;李晚龍	申請（專利權）人：	華為技術有限公司
主分類號：	H04L12/741	分類號：	H04L12/741
代理公司：	北京中博世達專利商標代理有限公司 11274	代理人：	申健
地址：	518129 廣東***	國省代碼：	廣東;44
權利要求書：	查看更多	說明書：	查看更多
摘要：
搜索關鍵詞：	查找方法裝置
鉆瓜網技術展會專利詞庫專利權人專利榜在售專利公布日期熱門專利

【說明書】：

技術領域

本發明涉及通信領域，特別涉及查找方法和查找裝置。

背景技術

通信領域中，進行地址查找時有可能使用最長前綴匹配。例如，路由表中可以存儲網際協議版本4（Internet?Protocol?version4，IPV4）地址和網際協議版本6（Internet?Protocol?version6，IPV6）地址。實際應用中，地址的寬度可能比較寬，一個表中無法承載整個地址。因此，最長前綴匹配可能會使用二次查找。上述技術方案中，可查找的地址的范圍受到一定的限制。

下面以IPv6地址為例進行說明。所述IPv6地址的high?part（以下簡稱第一high?part）存儲在第一表中。例如，所述第一high?part的寬度為64比特。所述IPv6地址的low?part（以下簡稱第一low?part）存儲在第二表中。例如，所述第一low?part的寬度為64比特。網絡設備（例如路由器）查找所述IPv6地址時，先在第一表中查找與所述第一high?part匹配的第一表項。如果查找到所述第一表項，則根據所述第一表項獲取第一索引。在所述第二表中查找包含所述第一索引以及所述第一low?part的第二表項。上述技術方案中，所述第二表項中的匹配域（match?field）中需要存儲所述第一索引以及所述第一low?part。

實際應用中，所述第二表的match?field的寬度比較有限。因此，所述第二表項中能夠用于存儲所述第一索引的空間是有限的。例如，有的應用場景規定，所述第二表的match?field的寬度為80比特。考慮到所述第一low?part的寬度為64比特，所述第一索引的寬度不能超過16比特。另外，在實際應用中，所述第一表中可能需要存儲多個high?part，分別對應多個索引。在所述第一表中存儲多個互不相等的high?part的場景下，所述多個索引互不相等。因此，所述第二表中需要存儲多個互不相等的索引。

當所述第一表中存儲的high?part較多時，可能會出現所述第二表無法為所述第一表中的部分high?part配置對應的索引的情況。例如，如果所述第二表中的match?field的寬度為80比特并且low?part的寬度為64比特，則所述第二表中的索引的最大寬度為16比特。因此，在多個索引互不相等的情況下，所述第二表中能夠存儲的索引的個數為2的16次方。如果存儲在所述第一表中的high?part的數量大于2的16次方，則所述第二表中無法為所述第一表中存儲的部分high?part配置對應的索引。例如，IPv6地址的high?part的寬度可能為64比特，理論上所述第一表需要存儲的high?part的個數可以達到2的64次方。但是，所述第二表中能夠存儲的索引的個數最多只能是2的16次方。

上述技術方案中，所述第二表中無法為所述第一表中存儲的部分high?part配置對應的索引。因此，無法在所述第二表中查找所述第一表中存儲的部分highpart所對應的low?part。以上意味著，可查找的地址的范圍受到了一定限制。

發明內容

本發明提供了查找方法以及查找裝置，可以用于擴大可查找的地址的范圍。

第一方面，提供了一種查找方法，包括：

以地址的high?part為關鍵字，在第一表中查找與所述high?part匹配的第一表項；

根據所述第一表項獲得信息；

以所述地址的low?part的高M比特為關鍵字，在所述信息中查找與所述高M比特匹配的第二表項，所述第二表項包含第一索引，所述low?part的寬度為X比特，所述low?part包括所述高M比特以及低N比特，X等于M加N，X、M和N為正整數；

如果查找到所述第二表項，則獲取所述第一索引；

以所述第一索引以及所述低N比特為關鍵字，在第二表中查找與所述第一索引和所述低N比特匹配的表項。

在第一方面的第一種可能的實現方式中，

如果沒有查找到所述第二表項，則確定與所述地址匹配的最長前綴為所述high?part。

結合第一方面或者第一方面的第一種可能的實現方式，在第一方面的第二種可能的實現方式中，