[發明專利]路由表的管理方法和裝置

有效

• 申請號: 200910178756.4
• 申請日: 2009-09-25
• 公開（公告）號: CN101692653A
• 公開（公告）日: 2010-04-07
• 發明（設計）人: 吳霞;尹旺中;徐云川
• 申請（專利權）人: 中興通訊股份有限公司
• 主分類號: H04L12/56
• 分類號: H04L12/56;H04L29/06
• 代理公司: 北京康信知識產權代理有限責任公司 11240
• 代理人: 余剛;吳孟秋

技術領域

本發明涉及通信領域，具體而言，涉及一種路由表的管理方法和裝置。?

背景技術

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

TCAM是一種專用三態內容可尋址存儲器，可以進行快速大量并行搜索，并且一次查找的時間是固定的。因此，在高端路由器中通常選用TCAM芯片來存放路由表。TCAM芯片在進行并行搜索時，如果有多個匹配項，一般都采用低地址優先的策略命中地址最低的那一項。因此，如果選用TCAM芯片來存儲路由表，在更新路由表時需要使IP前綴按照其長度降序排列。?

目前，常用的基于TCAM的IP前綴的排序方法的基本原理可以歸為兩類：PLO_OPT算法和CAO_OPT算法。PLO_OPT算法在排序時基于兩個約束(1)前綴長的條目必須在前綴短的條目前面；?(2)前綴長度相同的兩個條目沒有順序限制。CAO_OPT算法在排序時也是基于兩個約束：(1)在一個前綴路徑上的條目必須按遞減序排列；(2)不在一個前綴路徑上的條目沒有順序限制。這兩種思想各有憂缺點，PLO_OPT算法便于實現，但是總體性能沒有CAO_OPT高，CAO_OPT算法性能較高，然而實現起來比較復雜。?

但是，在相關技術中，基于PLO_OPT算法和CAO_OPT算法的路由表的管理方法在更新路由表中的表項時搬移次數較多，占用了較多的資源和花費了相對長的時間。?

發明內容

針對相關技術中基于PLO_OPT算法和CAO_OPT算法的路由表的管理方法在更新路由表中的表項時搬移次數較多并占用了較多的資源和花費了相對長的時間的問題而提出本發明，為此，本發明的主要目的在于提供一種路由表的管理方法和裝置，以解決上述問題至少之一。?

為了實現上述目的，根據本發明的一個方面，提供了一種路由表的管理方法。?

根據本發明的路由表的管理方法包括：獲取待插入路由表的表項的前綴長度，其中，在上述路由表中，根據高斯分布模型為各個前綴長度的表項空間分配資源；在上述路由表中找到與上述前綴長度對應的第一表項空間；將上述待插入的表項插入到上述第一表項空間內的空閑資源中。?

為了實現上述目的，根據本發明的另一方面，提供了一種路由表的管理裝置。?

根據本發明的路由表的管理裝置包括：獲取模塊，用于獲取待插入路由表的表項的前綴長度，其中，在上述路由表中，根據高斯分布模型為各個前綴長度的表項空間分配資源；查找模塊，用于在上述路由表中找到與上述前綴長度對應的第一表項空間；插入模塊，用于將上述待插入的表項插入到上述第一表項空間內的空閑資源中。?

根據本發明，預先根據高斯分布模型為路由表中各個前綴長度的表項空間分配資源，在插入表項的過程中采用最鄰近法則來尋找空閑的資源，并且在刪除表項的過程中直接回收資源不做搬移操作。在這些策略基礎上建立的路由表管理系統在實際網絡應用中具有較高的性能和自適應能力，并減少了所占用的資源和花費的時間。?

附圖說明

此處所說明的附圖用來提供對本發明的進一步理解，構成本申請的一部分，本發明的示意性實施例及其說明用于解釋本發明，并不構成對本發明的不當限定。在附圖中：?

圖1是根據本發明實施例的路由表的管理方法的流程；?

圖2是根據本發明實施例的前綴長度二分線的示意圖；?

圖3是根據本發明實施例的直接插入表項的示意圖；?

圖4是根據本發明實施例的按最鄰近法則申請空閑的資源插入表項的示意圖；?

圖5是根據本發明實施例的路由表的管理裝置的結構框圖。?

具體實施方式

下文中將參考附圖并結合實施例來詳細說明本發明。需要說明的是，在不沖突的情況下，本申請中的實施例及實施例中的特征可以相互組合。?

功能概述?