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

有效

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

技術(shù)領(lǐng)域

本發(fā)明涉及計(jì)算機(jī)網(wǎng)絡(luò)通信領(lǐng)域，具體涉及三層交換機(jī)的一種高效的路由表管理方法。

背景技術(shù)

在三層以太網(wǎng)交換機(jī)的運(yùn)維過程中，對(duì)交換機(jī)的路由表表項(xiàng)的查找、刪除、插入是非常頻繁的，提高交換機(jī)路由表管理的效率對(duì)保證交換機(jī)的性能起著非常重要的作用。

目前對(duì)路由表的管理一般是采用TCAM(Ternary?Content?AddressMemory)作為存儲(chǔ)介質(zhì)來提高路由表的管理效率。這種方法雖然通過提高存儲(chǔ)介質(zhì)性能而提高了路由表的管理效率，但由于每次操作需要逐條在TCAM表中去查找，所以開銷很大、成本較高。

發(fā)明內(nèi)容

為了解決現(xiàn)有的采用TCAM作為存儲(chǔ)介質(zhì)來提高路由表管理效率的方法開銷大、成本高的問題，本發(fā)明提供了一種交換機(jī)路由表的管理方法。

本發(fā)明的管理方法按以下步驟進(jìn)行：

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

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

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

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

上述A步驟中所述的散列表還包括一個(gè)哈希沖突表，用于記錄由于目的IP和掩碼依據(jù)哈希算法所獲得的數(shù)值發(fā)生相同情況而導(dǎo)致沖突的路由表項(xiàng)；發(fā)生沖突時(shí)，以已經(jīng)存入哈希表中的路由條目在硬件TCAM路由表中所對(duì)應(yīng)的表項(xiàng)索引作為與該路由條目發(fā)生沖突的沖突路由條目在哈希沖突表中的下標(biāo)，該下標(biāo)對(duì)應(yīng)的哈希沖突表中的內(nèi)容為所述沖突路由條目在硬件TCAM路由表中所對(duì)應(yīng)的表項(xiàng)索引。

發(fā)明效果：本發(fā)明通過在軟件上維護(hù)一個(gè)記錄每條路由表項(xiàng)索引(index)的哈希(Hash)表，在查找、插入、刪除路由表項(xiàng)時(shí)先通過查軟件上的哈希表來獲取對(duì)應(yīng)的TCAM表里路由表項(xiàng)的索引(index)，找到對(duì)應(yīng)表項(xiàng)，避免每次都是逐條去讀硬件路由表項(xiàng)。本發(fā)明通過減少硬件路由表項(xiàng)的讀寫次數(shù)來而提高系統(tǒng)性能、降低成本。最好的情況是能一次根據(jù)哈希表找到到對(duì)應(yīng)路由條目的索引，那么就只需要進(jìn)行一次讀硬件路由表項(xiàng)的操作；只有在最壞情況下才需要逐條去讀硬件表項(xiàng)。本發(fā)明通過軟硬件的配合來加快硬件TCAM路由表的插入、刪除及查找的速度，提高了路由表的管理效率。

附圖說明

圖1是本發(fā)明的散列表與TCAM表的對(duì)應(yīng)關(guān)系示意圖；

圖2是具體實(shí)施方式中本發(fā)明管理方法的B步驟中查找過程的流程圖；

圖3是具體實(shí)施方式中本發(fā)明管理方法的C步驟中刪除或插入路由表項(xiàng)的過程流程圖。

具體實(shí)施方式

以下將詳細(xì)描述本發(fā)明的各較佳實(shí)施例。

本發(fā)明的交換機(jī)路由表的管理方法按以下步驟實(shí)施：

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

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

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

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

以下舉例說明如何建立上述哈希表：以目的IP和掩碼為Hash算法的鑰匙(key)定義Hash算法。如圖1所示，如果路由條目a的IP地址和掩碼所對(duì)應(yīng)的TCAM表里的內(nèi)容為“Index2”，而由Hash算法根據(jù)該IP地址和掩碼所Hash出來的數(shù)值為“value1”，那么，該路由條目a在哈希表中的索引下標(biāo)設(shè)為“value1”，對(duì)應(yīng)的在哈希表里第“value1”條表項(xiàng)的內(nèi)容被填入“Index2”。

上述A步驟中所述的散列表還包括一個(gè)哈希沖突表，用于記錄由于目的IP和掩碼依據(jù)哈希算法所獲得的數(shù)值發(fā)生相同情況而導(dǎo)致沖突的路由表項(xiàng)；發(fā)生沖突時(shí)，以已經(jīng)存入哈希表中的路由條目在硬件TCAM路由表中所對(duì)應(yīng)的表項(xiàng)索引作為與該路由條目發(fā)生沖突的沖突路由條目在哈希沖突表中的下標(biāo)，該下標(biāo)對(duì)應(yīng)的哈希沖突表中的內(nèi)容為所述沖突路由條目在硬件TCAM路由表中所對(duì)應(yīng)的表項(xiàng)索引。