在線輔導　面授招生　考試大綱　指定教材　試題匯總

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

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

圖7-45中24位前綴10.78.45包含兩個網絡前綴：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位相結合來檢索第三個表對網絡前綴B而言，其最后一段132的前6位有效，值為（lOOOOlh=33,所以表項325+33含有B的下一跳信息。對前綴A而言，其最后一段128的前2位（10)有效，對應的地址范圍為100000~101111(即32~47),所以表項325+32-325+47(除去前綴B所對應的表項325+33)包含A的下一跳信息。

DIR-24-8-INT算法增加了一次內存訪問，使流水線操作變為3個階段，但是節省了TBLlong的內存空間。

返回目錄： 通信專業交換技術非連接型快速分組交換匯總

編輯推薦

通信專業實務考試終端與業務教程匯總

通信專業實務考試設備與環境教程匯總

通信工程師考試培訓交換理論基確匯總