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

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

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

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