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

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

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

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

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

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

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

編輯推薦

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

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

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