路由器中的硬件IP路由表應(yīng)用解析
1. 路由器的體系結(jié)構(gòu)
圖1給出了一般路由器的邏輯體系結(jié)構(gòu)。它主要由下面幾部分組成 ：路由引擎、轉(zhuǎn)發(fā)引擎、 路由表、網(wǎng)絡(luò)適配器和相關(guān)的邏輯電路等。轉(zhuǎn)發(fā)引擎負(fù)責(zé)把從一個(gè)網(wǎng)絡(luò)適配器來(lái)的數(shù)據(jù)包轉(zhuǎn)發(fā)到另一個(gè)網(wǎng)絡(luò)適配器出去。IP協(xié)議，包括對(duì)路由表的查找，構(gòu)成了轉(zhuǎn)發(fā)引擎中最主要的部分。由于每個(gè)通過(guò)路由器并需要其轉(zhuǎn)發(fā)的數(shù)據(jù)包都要對(duì)路由表進(jìn)行查找，所以路由表的查找效率如何往往決定了整個(gè)路由器的性能。路由引擎則包括了高層協(xié)議，特別是路由協(xié)議，它負(fù)責(zé)對(duì)路由表的更新。由于路由引擎不涉及通過(guò)路由器的數(shù)據(jù)通路，故它可用通用的CPU代替。
2．硬件路由表的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)
一般路由器中路由表的每一項(xiàng)至少有這樣的信息：目標(biāo)地址、網(wǎng)絡(luò)隱碼、下一跳地址。如果對(duì)每一個(gè)IP地址都要一個(gè)表項(xiàng)，那么需要占用很大的2323*4字節(jié)的存儲(chǔ)器，而且其中必定有很多的表項(xiàng)沒有被使用，這就會(huì)造成極大的資源浪費(fèi)。
為了用硬件實(shí)現(xiàn)路由表的查找，查找算法需要滿足如下的條件：
1） 實(shí)時(shí)的實(shí)現(xiàn)路由表的查找；
2） 有效的實(shí)現(xiàn)路由表的插入和刪除；
3） 提供有效的最長(zhǎng)前綴匹配；
4） 具有良好的可擴(kuò)展性；
5） 支持廣播和組播；
6） 有效的對(duì)Memory進(jìn)行利用；
7） 硬件上容易實(shí)現(xiàn)，并具有良好的性能 。
我們考慮，如果在對(duì)路由表的查找中，把子網(wǎng)隱碼和IP地址結(jié)合起來(lái)，對(duì)IP地址進(jìn)行相應(yīng)的分段，并把它們相連。這樣在路由表的表項(xiàng)中，只有IP地址的一部分及其相應(yīng)的隱碼部分，可以實(shí)現(xiàn)良好的可擴(kuò)展性，只要對(duì)Memory進(jìn)行有效的管理，可以靈活的動(dòng)態(tài)的實(shí)現(xiàn)對(duì)路由的插入和刪除。鑒于此，我們?cè)O(shè)計(jì)該表的結(jié)構(gòu)（如下面的表一所示 ）：
它的思想是：把32位IPv4地址主要分成4部分，每部分8位。在該結(jié)構(gòu)中，Address-part[0-4]是IP地址中的一部分，Mask-part[0-4]是相應(yīng)的掩碼部分。Hit-next[0-4]是需要查找的目標(biāo)IP地址與掩碼部分相與后，與Address-part一致時(shí)所要查找的下一路由項(xiàng)所在地址的指針。,Miss-hit[0-4]則是相互不一致時(shí)，下一路由項(xiàng)所在地址的指針。Shift位則用于判斷是否需要對(duì)IP地址中的下8位進(jìn)行查找和判斷。它只有在當(dāng)前的8位IP地址與目標(biāo)地址中相應(yīng)的8位一致時(shí)，才會(huì)被置位。Stop位用于判斷是否還需進(jìn)行查找。它在IP地址查找結(jié)束時(shí)被置位，或沒有比當(dāng)前項(xiàng)所對(duì)應(yīng)的IP地址更長(zhǎng)的路由表項(xiàng)時(shí)被置位。
圖2就是一個(gè)表1的例子 ：
在該例子中，每一方框中上面一行表示相應(yīng)的IP地址部分和隱碼部分。下面一行表示相關(guān)的隱碼部分的二進(jìn)制表示。 相應(yīng)的查找算法如下：
- ／＊查找算法開始 */
- search = TRUE ;
- WHILE ( search ) {
- masked_key = key & ( entry ->mask_part ) ;
- result = ( entry ->address_part ) = = masked_key
- IF ( result = = TRUE ) {
- best_match = entry ;
- entryentry = entry ->hit_next;
- }ELSE{
- entryentry = entry ->miss_next;
- IF ( entry ->stop = = TRUE ) search = FALSE;
- }
- }
- RETURN best_match ；
- ／＊查找算法結(jié)束 */
為了實(shí)現(xiàn)有效的插入和刪除，我們還要在路由表的數(shù)據(jù)結(jié)構(gòu)中再另外添加幾個(gè)域 ：parent指針（指向本結(jié)點(diǎn)的父結(jié)點(diǎn)），路由信息（routeinfo）等。它們的用途是在路由表的查找過(guò)程中，特別是在指針的回溯（pointer reversal）中，可以大大的節(jié)省查找時(shí)間。由于IP路由的插入和刪除比較復(fù)雜。我們只是粗略得說(shuō)明一下。
IP路由的插入：
- /*插入算法開始 */
- /* 先用上面提到的查找算法找出best-match */
- best_match = search ( new_entry );
- /* 確定需要加入的路由中沒有被best-match包括的那幾位 */
- for ( count = first_unmatched_bit ; count <= sizeof ( new_entry) ;
- count+= sizeof ( address_part ) {
- /* 創(chuàng)建新的結(jié)點(diǎn) */
- create new node ;
- /* 將該結(jié)點(diǎn)連入best_match的hit_next */
- link node into hit branch of best_match ;
- }
- /*插入算法結(jié)束 */
IP路由的刪除要分幾種情況討論 。如 best_match 是葉子結(jié)點(diǎn) ，best_match的hit_next指針為空, best_match的miss_next指針為空 和hit_next指針和miss_next指針都不為空等四種情況。這里就不再討論。
#p#
3．路由表查找的硬件實(shí)現(xiàn)：
圖3就是對(duì)應(yīng)與上面提及的路由表結(jié)構(gòu)的IP路由表查找的硬件實(shí)現(xiàn)（簡(jiǎn)稱為路由卡）的系統(tǒng)框圖。
在路由卡中，主要有IP地址，狀態(tài)機(jī)，路由信息，Memory，譯碼器，掩碼器，比較器，地址寄存器組成。IP地址用于保存所要查找的目標(biāo)地址。狀態(tài)器用于控制IP路由表的查找。路由信息就是我們所要查找的信息。它的工作原理是這樣的：
當(dāng)路由器從某一個(gè)網(wǎng)絡(luò)適配器中接受到一個(gè)需要轉(zhuǎn)發(fā)的數(shù)據(jù)包后，在需要進(jìn)行IP路由表的查找時(shí)，把IP包的目的地址送到IP地址寄存器中，同時(shí)給狀態(tài)機(jī)發(fā)一個(gè)指令。狀態(tài)接到這一指令后，從Memory中讀出路由表的相應(yīng)的表項(xiàng)，并和IP地址寄存器中的相應(yīng)幾位經(jīng)譯碼器，掩碼器后，進(jìn)行比較，把比較的結(jié)果反饋給狀態(tài)機(jī)。再由狀態(tài)機(jī)來(lái)控制下一輪的比較。當(dāng)比較結(jié)束后，把比較的結(jié)果放在路由信息寄存器中，供路由器（如轉(zhuǎn)發(fā)引擎）讀取。同時(shí)狀態(tài)機(jī)在特定的某一端口設(shè)置標(biāo)志，來(lái)通知CPU查找是否已經(jīng)結(jié)束或還在進(jìn)行當(dāng)中。下面對(duì)其性能進(jìn)行分析。
4．性能分析
由于路由表項(xiàng)中，地址掩碼的引入，使得路由結(jié)構(gòu)變得非常靈活。但相應(yīng)的，由此產(chǎn)生的內(nèi)存的開銷也相當(dāng)?shù)拇?。這是性能和硬件開銷一對(duì)矛盾的必然體現(xiàn)。
該路由卡原型的實(shí)現(xiàn)是利用微機(jī)上的ISA總線，采用存取時(shí)間為70ns 的SRAM存儲(chǔ)器（所需容量為6*123k*8bit）。除了使用ISA總線上提供的總線外，本身還帶了33M的晶振。對(duì)某一路由表項(xiàng)的查找，最多只需32步查找。
在最壞情況下，共需32次查找，查找時(shí)間為：
32* 1 /(33*106) ≈ 9.7 * 10 -7秒
此時(shí)每秒可查找 1/（9.7 * 10 -7）≈ 1.03 * 106次
雖然該路由卡是基于ISA總線，但平均來(lái)說(shuō)，該路由卡的查找速率為每秒8百萬(wàn)次。這也從另一方面說(shuō)明該路由卡的設(shè)計(jì)是可行的。
針對(duì)網(wǎng)絡(luò)流量的增加，及對(duì)路由器性能要求的提高，本文從硬件的角度對(duì)IP路由查找算法用硬件實(shí)現(xiàn)做了一系列的分析，并提出了相應(yīng)的便于用硬件實(shí)現(xiàn)的IP路由表的數(shù)據(jù)結(jié)構(gòu)。同時(shí)對(duì)該路由卡的性能進(jìn)行了分析。
同時(shí)也該看到：為了更快的提高路由表的查找速率，基于ISA總線是不可能滿足要求的。由此，使用FPGA芯片不可避免。由于VHDL語(yǔ)言固有的靈活性和可編程性，可以更為靈活和高效的實(shí)現(xiàn)路由查找。所以，使用FPGA芯片來(lái)實(shí)現(xiàn)路由查找，是未來(lái)的趨勢(shì)。
路由器中的硬件IP路由表應(yīng)用的全部?jī)?nèi)容就呈現(xiàn)給了大家，文章內(nèi)容較多，但是敘述比較詳細(xì)，方便讀者理解和閱讀，希望你能從中學(xué)習(xí)到你想要的知識(shí)。
【編輯推薦】
