[發(fā)明專利]一種交換機(jī)路由表的管理方法

有效

• 申請?zhí)枺?/td>: 200710075184.8
• 申請日: 2007-06-22
• 公開（公告）號: CN101072178A
• 公開（公告）日: 2007-11-14
• 發(fā)明（設(shè)計(jì)）人: 畢恒
• 申請（專利權(quán)）人: 中興通訊股份有限公司
• 主分類號: H04L12/56
• 分類號: H04L12/56;G06F17/30
• 代理公司: 深圳市君勝知識產(chǎn)權(quán)代理事務(wù)所
• 代理人: 楊宏

1、一種交換機(jī)路由表的管理方法，其特征在于，所述方法采用如下步驟：

A、在軟件層上建立散列表，該散列表記錄有每條路由表項(xiàng)索引；

B、通過查找上述散列表，獲得所需路由表項(xiàng)索引；

C、根據(jù)查找到的路由表項(xiàng)索引在硬件路由表中進(jìn)行查找，根據(jù)查找結(jié)果進(jìn)行相應(yīng)地刪除或插入；

所述A步驟中所述的散列表包括一個哈希表，以目的IP和掩碼為鑰匙依據(jù)哈希算法所獲得的數(shù)值作為該條路由條目在哈希表的下標(biāo)，該下標(biāo)對應(yīng)的哈希表中的內(nèi)容為該目的IP和掩碼所對應(yīng)的路由條目在硬件TCAM路由表中所對應(yīng)的表項(xiàng)索引。

2、根據(jù)權(quán)利要求1所述的一種交換機(jī)路由表的管理方法，其特征在于，A步驟中所述的散列表還包括一個哈希沖突表，用于記錄由于目的IP和掩碼依據(jù)哈希算法所獲得的數(shù)值發(fā)生相同情況而導(dǎo)致沖突的路由表項(xiàng)；發(fā)生沖突時，以已經(jīng)存入哈希表中的路由條目在硬件TCAM路由表中所對應(yīng)的表項(xiàng)索引作為與該路由條目發(fā)生沖突的沖突路由條目在哈希沖突表中的下標(biāo)，該下標(biāo)對應(yīng)的哈希沖突表中的內(nèi)容為所述沖突路由條目在硬件TCAM路由表中所對應(yīng)的表項(xiàng)索引；

所述哈希表的構(gòu)成以目的IP和掩碼為Hash算法的鑰匙定義Hash算法。

3、根據(jù)權(quán)利要求1所述的一種交換機(jī)路由表的管理方法，其特征在于，所述哈希表由類型為整形的數(shù)組構(gòu)成，且哈希表的表項(xiàng)大小為TCAM路由表表項(xiàng)數(shù)目的大小。

4、根據(jù)權(quán)利要求2所述的一種交換機(jī)路由表的管理方法，其特征在于，沒有發(fā)生所述沖突時，以該路由條目在硬件TCAM路由表中所對應(yīng)的表項(xiàng)索引作為哈希沖突表的下標(biāo)，該下標(biāo)對應(yīng)的哈希沖突表中的內(nèi)容被填入無效值。

5、根據(jù)權(quán)利要求2所述的一種交換機(jī)路由表的管理方法，其特征在于，所述哈希沖突表由類型為整形的數(shù)組構(gòu)成，且哈希沖突表的表項(xiàng)大小為TCAM路由表表項(xiàng)數(shù)目的大小。

6、根據(jù)權(quán)利要求4所述的一種交換機(jī)路由表的管理方法，其特征在于，所述管理方法的B步驟中查找過程按照以下步驟進(jìn)行：

B1、以目的IP和掩碼為鑰匙依據(jù)哈希算法獲得哈希數(shù)值，以該哈希數(shù)值為下標(biāo)查找哈希表里的對應(yīng)表項(xiàng)，讀出其中存放的該目的IP和掩碼所對應(yīng)的路由條目在硬件TCAM路由表中所對應(yīng)的表項(xiàng)索引；

B2、判斷該表項(xiàng)索引是否無效；

若該表項(xiàng)索引無效，則表明所要尋找的路由條目不存在；

若該表項(xiàng)索引有效，則執(zhí)行步驟B3；

B3、根據(jù)步驟B1讀出的表項(xiàng)索引去讀硬件TCAM路由表；

B4、將步驟B3讀到的硬件表項(xiàng)里的內(nèi)容與所需查找的路由表項(xiàng)相比較，看是否一致；

如果步驟B4的判斷結(jié)果為是，則表明找到對應(yīng)表項(xiàng)；

如果步驟B4的判斷結(jié)果為否，則執(zhí)行步驟B5；

B5、以依據(jù)步驟B1在哈希表里讀出的表項(xiàng)索引作為下標(biāo)去索引哈希沖突表；

B6、判斷哈希沖突表里的內(nèi)容是否為無效值；

若步驟B6的判斷結(jié)果為是，則表明所要尋找的路由條目不存在；

若步驟B6的判斷結(jié)果為否，則執(zhí)行步驟B7；

B7、以步驟B5所讀出的哈希沖突表的內(nèi)容作為索引去讀硬件TCAM路由表；

B8、將步驟B7所讀得的內(nèi)容與所需查找的路由表項(xiàng)相比較，看是否一致；

如果步驟B8的判斷結(jié)果為是，則表明找到對應(yīng)表項(xiàng)；

如果步驟B8的判斷結(jié)果為否，則繼續(xù)以依據(jù)步驟B1在哈希表里讀出的表項(xiàng)索引作為下標(biāo)逐條往后去索引哈希沖突表，并重復(fù)至步驟B6，直到找到哈希沖突表里的對應(yīng)表項(xiàng)的內(nèi)容為無效值時，即證明不存在所要尋找的路由條目時停止。

7、根據(jù)權(quán)利要求1或6所述的一種交換機(jī)路由表的管理方法，其特征在于，所述管理方法的C步驟中刪除或插入路由表項(xiàng)的過程按以下步驟進(jìn)行：

若根據(jù)B步驟查找后表明該路由條目不存在，則在維護(hù)哈希表時，以該目的IP和掩碼為鑰匙依據(jù)哈希算法所獲得到的哈希數(shù)值作為該路由條目在哈希表中的索引下標(biāo)，并將該路由條目在硬件TCAM表中的索引填入哈希表，同時也更新哈希沖突表中的相關(guān)內(nèi)容；

若根據(jù)B步驟查找后表明該路由條目存在，則在維護(hù)哈希表時，直接覆蓋相應(yīng)路由表項(xiàng)目即可；

所述哈希表的構(gòu)成以目的IP和掩碼為Hash算法的鑰匙定義Hash算法。

8、根據(jù)權(quán)利要求7所述的一種交換機(jī)路由表的管理方法，其特征在于，所述更新哈希沖突表中的相關(guān)內(nèi)容的過程如下進(jìn)行：

以該目的IP和掩碼所對應(yīng)的硬件TCAM路由表中表項(xiàng)索引作為與該路由條目發(fā)生沖突的沖突路由條目在哈希沖突表中的下標(biāo)，該下標(biāo)對應(yīng)的哈希沖突表中的內(nèi)容為與該目的IP和掩碼所對應(yīng)的路由條目相沖突的路由條目在硬件TCAM路由表中所對應(yīng)的表項(xiàng)索引。