[發明專利]一種路由表的更新方法及系統有效

申請號：	201110222783.4	申請日：	2011-08-04
公開（公告）號：	CN102291296A	公開（公告）日：	2011-12-21
發明（設計）人：	吳霞;朱曉強	申請（專利權）人：	中興通訊股份有限公司
主分類號：	H04L12/56	分類號：	H04L12/56
代理公司：	北京安信方達知識產權代理有限公司 11262	代理人：	解婷婷;龍洪
地址：	518057 廣東省深圳市南山***	國省代碼：	廣東;44
權利要求書：	查看更多	說明書：	查看更多
摘要：
搜索關鍵詞：	一種路由更新方法系統
鉆瓜網技術展會專利詞庫專利權人專利榜在售專利公布日期熱門專利

【說明書】：

技術領域

本發明涉及路由器、交換機等網絡設備，尤其涉及一種路由表的更新方法及系統。

背景技術

路由器、交換機是組網的核心設備，而這些設備最基本、最核心的功能就是基本轉發。基本轉發功能是通過查找路由表來實現的，因此查找路由表的性能直接影響著路由器、交換機的性能。路由表的查找是按照最長前綴匹配的原則。常用的實現最長前綴匹配的方法有基于hash(哈希)表的方法和基于Trie(鍵樹)表的方法。這些方法的特點是：查一次路由表需要進行若干次比較操作，而且比較操作的次數是不固定的。這就使得查表的性能不高，而且也不夠穩定。

TCAM(Ternary?Content?Addressable?Memory，三態內容尋址存儲器)是一種專用的存儲器，可以進行快速大量并行搜索，并且一次查找的時間是固定的。因此，在高端路由器中通常選用TCAM芯片來存放路由表。目前，TCAM芯片價格相對比較昂貴，且容量有限，因此如果采用TCAM芯片來存放路由表，路由容量便成為一大難題。

針對該問題，相關專利給出了一些解決思路，例如申請號為CN201010233044.0的發明公開了一種路由轉發表容量擴展實現方法、裝置及交換設備，將路由表項分為兩類，將由內部網關協議產生的域內路由轉發表項存放在TCAM中，將由外部網關協議產生的域間路由轉發表項存放在大容量存儲器中。查找的時候先查TCAM，如果沒有命中再查大容量存儲器。該方法確實可以解決容量問題，但是路由查找性能也損失不少。申請號為CN200910236687.8的發明提供了一種三態內容可尋址存儲器TCAM的尋址方法及裝置，采用動態分配TCAM空間的思路，對于提高TCAM芯片的利用率有一定的作用。但是TCAM芯片本身在配置上有一些限制，例如不同寬度的表不能放在一個塊中等。

目前，路由器一般都會同時支持IPV4和IPV6路由，如果要將IPV4和IPV6路由這兩張路由表同時存放在TCAM上，由于上述兩種類型的表對各自表項的位置有限制，例如路由表需要遵循最長前綴匹配方法，這就要求表項要按照路由前綴進行排序。如果整個TCAM都采用上述動態分配TCAM空間的方式，表項的更新性能會受到影響。為了保證更新性能，如采用靜態分配TCAM空間的方式，例如為IPV4分配80萬路由表項空間，為IPV6分配20萬路由表項空間，則當在某種網絡環境下某種類型的路由表項非常少，比如IPV6只有幾十個表項時，由于采用靜態分配方式，IPV4最多只能支持80萬，而IPV6的TCAM空間就浪費了。

發明內容

本發明的目的在于提供一種路由表的更新方法及系統，以在兼顧路由表更新性能的基礎上實現IPV4和IPV6路由表容量的動態調整。

為解決上述問題，本發明提供了一種路由表的更新方法，應用于三態內容尋址存儲器(TCAM)中，包括：

將所述TCAM中用于存放路由表的存儲資源劃分為用于存放IPV4路由表的第一存儲區、用于存放IPV6路由表的第二存儲區、及第三存儲區；

當有路由表項需要插入到所述TCAM時，若所述路由表項對應的路由表所在存儲區的剩余空間不足，則從所述第三存儲區中劃分至少部分資源作為所述路由表項對應的路由表所在存儲區的資源后，將所述路由表項添加到對應的路由表所在存儲區中。

進一步地，上述方法還包括：

若所述路由表項對應的路由表所在存儲區的剩余空間不足，且所述第三存儲區沒有剩余資源可供劃分，則在用于存放另一路由表的存儲區中劃分至少部分空閑的可用資源作為所述路由表項對應的路由表所在存儲區的資源，然后將所述路由表項添加到對應的路由表所在存儲區中。

進一步地，上述方法還包括：

若所述用于存放另一路由表的存儲區中亦沒有空閑的可用資源可供劃分，則添加所述路由表項失敗。

進一步地，

所述第三存儲區的容量為0。

進一步地，