IP路由查找算法的研究.pdf

1、近些年來，互聯(lián)網(wǎng)得到了極大的發(fā)展，越來越多的人利用互聯(lián)網(wǎng)來通信，于是網(wǎng)絡(luò)業(yè)務(wù)急劇增加。據(jù)調(diào)查，自從1997年后Internet的網(wǎng)絡(luò)業(yè)務(wù)流量和帶寬以及網(wǎng)絡(luò)骨干路由器的接口速率以每半年增長(zhǎng)一倍的速度增長(zhǎng)，由此導(dǎo)致骨干路由器每秒需要轉(zhuǎn)發(fā)的報(bào)文數(shù)量也隨之劇增。
　　 而在路由器處理巨量業(yè)務(wù)的過程中，最重要同時(shí)也是最耗時(shí)的一步就是查找路由表。因此，快速的IP路由查找算法是實(shí)現(xiàn)高速分組轉(zhuǎn)發(fā)的關(guān)鍵。而且IP路由查找算法的空間復(fù)雜度和時(shí)間復(fù)雜

2、度以及高效的實(shí)現(xiàn)方法一直是研究的熱點(diǎn)問題，也可以說這些因素目前還是網(wǎng)絡(luò)發(fā)展的瓶頸。由此可見IP路由查找算法的優(yōu)劣直接影響當(dāng)前和未來的Internet網(wǎng)絡(luò)的整體性能。
　　 在此背景下，本文提出了一種基于硬件的快速IP路由查找算法：并行前綴長(zhǎng)度猜測(cè)算法(PPLS,parallel prefix length speculation)，以及該算法的改進(jìn)算法—基于Trie的PPLS算法。與傳統(tǒng)路由查找算法不同的是，本文提出的算法給出了

3、一種IP前綴長(zhǎng)度猜測(cè)機(jī)制。也就是當(dāng)一個(gè)分組來的時(shí)候，該算法先猜測(cè)分組目的地址所對(duì)應(yīng)前綴的長(zhǎng)度，然后以猜測(cè)到的長(zhǎng)度為基準(zhǔn)通過精確匹配來進(jìn)一步確認(rèn)。這樣大大減少了查找時(shí)間，同時(shí)還減少了查找過程中所用到的存儲(chǔ)空間。
　　 首先，本文介紹IP路由查找算法的發(fā)展現(xiàn)狀，以及一些相關(guān)背景技術(shù)。然后，分析和比較了現(xiàn)有IP路由查找方法，為引出本文最終所要提出的新的路由查找思路和算法做準(zhǔn)備。接下來，我們?cè)敿?xì)描述了本文提出的IP路由查找算法：并行前綴