通信網(wǎng)banner.jpg)
Internet的迅速發(fā)展給我們的生活帶來(lái)了巨大的變化。隨之而來(lái)的是網(wǎng)絡(luò)流量的迅速增長(zhǎng)。網(wǎng)絡(luò)流量的增長(zhǎng)對(duì)于Internet上的路由器來(lái)說(shuō)是一個(gè)很大的挑戰(zhàn)，特別是核心路由器。它需要高速有效的包調(diào)度.轉(zhuǎn)發(fā)和路由策略。本文針對(duì)路由器的路由查找，提出了一種高效的.便于用硬件實(shí)現(xiàn)的技術(shù)。
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)沒(méi)有被使用，這就會(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í)被置位，或沒(méi)有比當(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)的查找算法如下：
/* 查找算法開(kāi)始 */
search = TRUE ;
WHILE ( search ) {
masked_key = key & ( entry ->mask_part ) ;
result = ( entry ->address_part ) = = masked_key
IF ( result = = TRUE ) {
best_match = entry ;
entry = entry ->hit_next;
}ELSE{
entry = entry ->miss_next;
IF ( entry ->stop = = TRUE ) search = FALSE;
}
}
RETURN best_match ;
/* 查找算法結(jié)束 */
