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ò)骨干路由器的接口速率以每半年增長一倍的速度增長，由此導致骨干路由器每秒需要轉(zhuǎn)發(fā)的報文數(shù)量也隨之劇增。
　　 而在路由器處理巨量業(yè)務(wù)的過程中，最重要同時也是最耗時的一步就是查找路由表。因此，快速的IP路由查找算法是實現(xiàn)高速分組轉(zhuǎn)發(fā)的關(guān)鍵。而且IP路由查找算法的空間復雜度和時間復雜

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

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