日本免费全黄少妇一区二区三区-高清无码一区二区三区四区-欧美中文字幕日韩在线观看-国产福利诱惑在线网站-国产中文字幕一区在线-亚洲欧美精品日韩一区-久久国产精品国产精品国产-国产精久久久久久一区二区三区-欧美亚洲国产精品久久久久

  1. 首頁 > 云知道 > >

路由器中的硬件IP路由表查找技術(shù)

云知道


Internet的迅速發(fā)展給我們的生活帶來了巨大的變化 。隨之而來的是網(wǎng)絡(luò)流量的迅速增長 。網(wǎng)絡(luò)流量的增長對于Internet上的路由器來說是一個很大的挑戰(zhàn) ， 非凡是核心路由器 。它需要高速有效的包調(diào)度.轉(zhuǎn)發(fā)和路由策略 。本文針對路由器的路由查找 ， 提出了一種高效的.便于用硬件實現(xiàn)的技術(shù) 。
1. 路由器的體系結(jié)構(gòu)
圖1給出了一般路由器的邏輯體系結(jié)構(gòu) 。它主要由下面幾部分組成 ：路由引擎、轉(zhuǎn)發(fā)引擎、 路由表、網(wǎng)絡(luò)適配器和相關(guān)的邏輯電路等 。轉(zhuǎn)發(fā)引擎負(fù)責(zé)把從一個網(wǎng)絡(luò)適配器來的數(shù)據(jù)包轉(zhuǎn)發(fā)到另一個網(wǎng)絡(luò)適配器出去 。IP協(xié)議 ， 包括對路由表的查找 ， 構(gòu)成了轉(zhuǎn)發(fā)引擎中最主要的部分 。由于每個通過路由器并需要其轉(zhuǎn)發(fā)的數(shù)據(jù)包都要對路由表進(jìn)行查找 ， 所以路由表的查找效率如何往往決定了整個路由器的性能 。路由引擎則包括了高層協(xié)議 ， 非凡是路由協(xié)議 ， 它負(fù)責(zé)對路由表的更新 。由于路由引擎不涉及通過路由器的數(shù)據(jù)通路 ， 故它可用通用的CPU代替 。
2．硬件路由表的數(shù)據(jù)結(jié)構(gòu)設(shè)計
一般路由器中路由表的每一項至少有這樣的信息：目標(biāo)地址、網(wǎng)絡(luò)隱碼、下一跳地址 。假如對每一個IP地址都要一個表項 ， 那么需要占用很大的2323*4字節(jié)的存儲器 ， 而且其中必定有很多的表項沒有被使用 ， 這就會造成極大的資源浪費 。
為了用硬件實現(xiàn)路由表的查找 ， 查找算法需要滿足如下的條件：
1） 實時的實現(xiàn)路由表的查找；
2） 有效的實現(xiàn)路由表的插入和刪除；
3） 提供有效的最長前綴匹配；
4） 具有良好的可擴(kuò)展性；
5） 支持廣播和組播；
6） 有效的對Memory進(jìn)行利用；
7） 硬件上輕易實現(xiàn) ， 并具有良好的性能。
我們考慮 ， 假如在對路由表的查找中 ， 把子網(wǎng)隱碼和IP地址結(jié)合起來 ， 對IP地址進(jìn)行相應(yīng)的分段 ， 并把它們相連 。這樣在路由表的表項中 ， 只有IP地址的一部分及其相應(yīng)的隱碼部分 ， 可以實現(xiàn)良好的可擴(kuò)展性 ， 只要對Memory進(jìn)行有效的治理 ， 可以靈活的動態(tài)的實現(xiàn)對路由的插入和刪除 。鑒于此 ， 我們設(shè)計該表的結(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一致時所要查找的下一路由項所在地址的指針 。,Miss-hit[0-4]則是相互不一致時 ， 下一路由項所在地址的指針 。Shift位則用于判定是否需要對IP地址中的下8位進(jìn)行查找和判定 。它只有在當(dāng)前的8位IP地址與目標(biāo)地址中相應(yīng)的8位一致時 ， 才會被置位 。Stop位用于判定是否還需進(jìn)行查找 。它在IP地址查找結(jié)束時被置位 ， 或沒有比當(dāng)前項所對應(yīng)的IP地址更長的路由表項時被置位 。
圖2就是一個表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 ;
entry = entry ->hit_next;
}ELSE{
entry = entry ->miss_next;
IF ( entry ->stop = = TRUE ) search = FALSE;
}
}
RETURN best_match ；
／＊　查找算法結(jié)束 */
為了實現(xiàn)有效的插入和刪除 ， 我們還要在路由表的數(shù)據(jù)結(jié)構(gòu)中再另外添加幾個域 ：parent指針（指向本結(jié)點的父結(jié)點） ， 路由信息（routeinfo）等 。它們的用途是在路由表的查找過程中 ， 非凡是在指針的回溯（pointer reversal）中 ， 可以大大的節(jié)省查找時間 。由于IP路由的插入和刪除比較復(fù)雜 。我們只是粗略得說明一下 。

推薦閱讀