基于軟件的高速路由查找算法研究.pdf

1、該論文回顧了現(xiàn)有的路由查找算法的一些問題,包括對于路由查找性能最敏感的兩大指標(biāo):轉(zhuǎn)發(fā)表的體積和平均內(nèi)存訪問次數(shù)方面的問題.在對現(xiàn)有算法分析的基礎(chǔ)上提出了一套新的路由查找算法,主要內(nèi)容包括以下的幾個(gè)方面:1.首先針對現(xiàn)有的算法進(jìn)行了歸納和總結(jié):對現(xiàn)有路由查找算法進(jìn)行分類、歸納和總結(jié),在此基礎(chǔ)上對它們的轉(zhuǎn)發(fā)表信息冗余度、轉(zhuǎn)發(fā)表體積和平均內(nèi)存訪問次數(shù)等等方面的性能進(jìn)行分析.2.在上述分析的基礎(chǔ)上,作者提出了一種被稱為自適應(yīng)分段多分搜索樹(AS

2、MS樹:Adaptive Segmented Multiway Search)的查找樹結(jié)構(gòu).這種樹型結(jié)構(gòu)可以根據(jù)實(shí)際路由前綴分布自適應(yīng)的壓縮轉(zhuǎn)發(fā)表中的冗余信息,調(diào)整節(jié)點(diǎn)分支因子的大小,從而提高了單次內(nèi)存訪問所獲取的信息量,同時(shí)也達(dá)到顯著壓縮轉(zhuǎn)發(fā)表體積的目的.同時(shí),文中研究并給出了針對該查找樹的路由查找算法.ASMS樹對轉(zhuǎn)發(fā)表中冗余信息進(jìn)行了壓縮,這種壓縮可以被看成是對轉(zhuǎn)發(fā)表的預(yù)處理.理論上來說:每次路由更新都可能導(dǎo)致ASMS樹的重構(gòu),而

3、Internet中路由規(guī)則變化是非常頻繁的,在每次路由規(guī)則變化時(shí)都進(jìn)行ASMS樹的重構(gòu)會帶來大量的開銷,為此,文中還給出了一種簡單有效的準(zhǔn)漸進(jìn)式更新算法.3.內(nèi)存訪問是路由表查找過程中的性能瓶頸,因此降低平均內(nèi)存訪問次數(shù)會有效的提高路由查找的效率.為了達(dá)到最優(yōu)化的平均內(nèi)存訪問次數(shù),需要采用動態(tài)規(guī)劃的方法,這意味著生成算法本身異常復(fù)雜,運(yùn)算量非常大.即使采用前面的準(zhǔn)漸進(jìn)式更新算法,可以預(yù)期ASMS樹的重構(gòu)仍然會相當(dāng)頻繁,因此采用動態(tài)規(guī)劃算

4、法不能滿足實(shí)際應(yīng)用的需求.為此,作者給出了兩種針對平均內(nèi)存訪問次數(shù)優(yōu)化的啟發(fā)式ASMS樹生成算法.這兩種算法簡單有效,均采用自項(xiàng)向下的工作模式.4.轉(zhuǎn)發(fā)表的體積是路由查找算法另外一個(gè)重要性能指標(biāo).較小的轉(zhuǎn)發(fā)表體積一方面可以提高路由查找過程中Cache的命中率,從而降低內(nèi)存訪問方面的開銷:另一方面較小的轉(zhuǎn)發(fā)表也意味著較好的擴(kuò)展?jié)摿?使得該查找算法可以適應(yīng)于更加復(fù)雜的情況.作者給出了兩種針對轉(zhuǎn)發(fā)表體積優(yōu)化的啟發(fā)式ASMS樹生成算法.這兩種算