交換技術(shù)基于DRAM的路由查找算法

　在線輔導(dǎo)　面授招生　考試大綱　指定教材　試題匯總

1.基于DRAM的路由查找算法
1）Dm-24-8-BASIC算法
目前應(yīng)用較多的是一種基于DRAM稱為DIR-24-8-BAS1C的路由查表算法。該算法采用存儲在DRAM中的兩個表，如圖7-42所示。第一個表稱為TBL24,存儲所有長度小于等于24bit的網(wǎng)絡(luò)前綴，該表有個表項，地址范圍從0.0.0~255.255.255,TBL24的每一表項都有圖7-43所示的格式。第二個表稱為TBLlong，存儲所有長度大于24bit的網(wǎng)絡(luò)前綴。IP地址的這種24-8分割方式的合理性在于：第一，目前的內(nèi)存技術(shù)很容易實現(xiàn)上述兩個表；第二，一些骨干路由器轉(zhuǎn)發(fā)表的測試結(jié)果顯示，超過99%的網(wǎng)絡(luò)前綴的長度小于等于24bit。
假設(shè)在一個空路由表里存儲一個網(wǎng)絡(luò)前綴X,如果X長度小于等于24bit,則僅僅存儲在TBU4中，表項的第一位置0，表示表項剩余字段保存的是該表項的下一跳信息。如果，長度大于24bit,則根據(jù)X的前24位查找到TBL24中的表項，該表項的第一位置1,表示表項剩余字段為一個指向TBLlong表的指針。

事實上，在該算法中長度小于24bU的網(wǎng)絡(luò)前綴被擴展了。例如，網(wǎng)絡(luò)前綴128.23/16在TBL24中會有2^6=256個相關(guān)表項，范圍從128.23_0-128.23.255,這256個表項都有相同內(nèi)容（對應(yīng)于網(wǎng)絡(luò)前綴128_23/16的下一跳地址）。通過這種對內(nèi)存的低效使用，經(jīng)過一次內(nèi)存訪問就可獲得下一跳信息。
TBLkrng包含了所有長度大丁24bit的網(wǎng)絡(luò)前綴，對每個TBL24中的表項，其包含的網(wǎng)絡(luò)前綴只要有一個長度大于24bit,則在TBLlong中就會被分配28=256個表項，每個表項對應(yīng)了可能的256個長度大于24bit的網(wǎng)絡(luò)前綴的一個，這256個網(wǎng)絡(luò)前綴在TBL24中有共同的24位前綴。因為TBLlong的表項僅存儲下一跳信息，如果假設(shè)作為下一跳節(jié)點的路由器少于256個（即路由器的端口數(shù)少于256個），則TBLlong每個表項的大小為lbyte。假定長度超過24bit的網(wǎng)絡(luò)前綴的數(shù)童為4096(該值遠遠超過了實際情況），則TBLlong所占空間為1MB。
由此，對于給定的目的地址，根據(jù)該路由查找機制，首先，分離出地址的前24位用來檢索TBL24,如果表項第一位是0,則表項后15位就是下一跳地址；否則（第一位是1),用后15位與256相乘作為基址，與原目的地址的后8位相加，再用得到的值檢索TBLlong。

圖7-45中24位前綴10.78.45包含兩個網(wǎng)絡(luò)前綴：A=10.78.45.128/26和B=10.78.45.132/30,長度最大為30位，則TBLlcmg要分配26=64個表項給前綴10.78.45。通過査詢第一和第二個表，獲得查詢第三個表的索引325。由于30位相對于24位的偏移長度為6,所以要將325與原目的地址的4段中的最后一段（如128與132)的前6位相結(jié)合來檢索第三個表對網(wǎng)絡(luò)前綴B而言，其最后一段132的前6位有效，值為（lOOOOlh=33,所以表項325+33含有B的下一跳信息。對前綴A而言，其最后一段128的前2位（10)有效，對應(yīng)的地址范圍為100000~101111(即32~47),所以表項325+32-325+47(除去前綴B所對應(yīng)的表項325+33)包含A的下一跳信息。

DIR-24-8-INT算法增加了一次內(nèi)存訪問，使流水線操作變?yōu)?個階段，但是節(jié)省了TBLlong的內(nèi)存空間。

返回目錄： 通信專業(yè)交換技術(shù)非連接型快速分組交換匯總

編輯推薦

通信專業(yè)實務(wù)考試終端與業(yè)務(wù)教程匯總

通信專業(yè)實務(wù)考試設(shè)備與環(huán)境教程匯總

通信工程師考試培訓(xùn)交換理論基確匯總