基于多分支Trie的虛擬路由查找算法研究.pdf

1、近年來，網(wǎng)絡(luò)服務(wù)日趨多樣化，虛擬路由技術(shù)是解決此難題的一種有效方案。然而，路由器的有限的存儲空間限制了其并發(fā)運行虛擬路由的數(shù)量，此外，多個虛擬路由的并發(fā)運行易導(dǎo)致其IP查找性能下降，給虛擬路由技術(shù)的各種應(yīng)用帶來了巨大困難。因此，如何合理設(shè)計虛擬路由轉(zhuǎn)發(fā)表的結(jié)構(gòu)，保證高性能的IP查找，成為虛擬路由技術(shù)中亟待解決的問題。本文圍繞Trie結(jié)構(gòu)的虛擬路由查找算法轉(zhuǎn)開研究，主要工作如下：
　　首先，研究虛擬路由技術(shù)中基于Trie結(jié)構(gòu)的各虛擬

2、路由轉(zhuǎn)發(fā)表合并的問題。針對單比特位的共享轉(zhuǎn)發(fā)表易導(dǎo)致Trie結(jié)構(gòu)臃腫，查找效率不高的問題，提出了一種基于多分支Trie的動態(tài)共享轉(zhuǎn)發(fā)表結(jié)構(gòu)，并在此結(jié)構(gòu)上實現(xiàn)了相應(yīng)的虛擬路由IP查找算法。該結(jié)構(gòu)采用多比特位的IP查找，減少了轉(zhuǎn)發(fā)表中結(jié)構(gòu)性消耗及訪存次數(shù)，并可動態(tài)調(diào)整Trie每層節(jié)點的步長值。實驗表明，與已有的結(jié)構(gòu)相比，動態(tài)共享轉(zhuǎn)發(fā)表能夠節(jié)省大量的存儲空間。
　　其次，本文研究轉(zhuǎn)發(fā)表的空間消耗與Trie步長值選取之間的關(guān)系。針對不同的

3、規(guī)則集分布，如何構(gòu)造最少空間消耗的動態(tài)共享轉(zhuǎn)發(fā)表的問題，提出了一種基于動態(tài)規(guī)劃思想的Trie自適應(yīng)步長劃分算法，算法通過統(tǒng)計轉(zhuǎn)發(fā)規(guī)則集中轉(zhuǎn)發(fā)規(guī)則長度的分布情況，自動地為每一層Trie節(jié)點選擇合適的步長值，進(jìn)一步節(jié)省動態(tài)共享轉(zhuǎn)發(fā)表的空間開銷。實驗表明，算法能準(zhǔn)確的計算出每層Trie節(jié)點合適的步長值，與固定步長方式構(gòu)造轉(zhuǎn)發(fā)表相比，能節(jié)省更多的存儲空間。
　　最后，結(jié)合以上研究工作，設(shè)計并開發(fā)了基于動態(tài)共享轉(zhuǎn)發(fā)表的仿真工具軟件，評價所提