基于動(dòng)態(tài)規(guī)劃和B+樹的IP路由查找技術(shù)研究.pdf

1、隨著Internet技術(shù)的迅猛發(fā)展，路由表，網(wǎng)絡(luò)速度，網(wǎng)絡(luò)流量都在持續(xù)增長(zhǎng)，IP路由查找困難度也隨之增加。無(wú)類別域間路由選擇(CIDR,Classless InterDomain Routing)的使用，使得路由器必須在路由表中找到與IP地址最長(zhǎng)匹配的前綴進(jìn)行路由轉(zhuǎn)發(fā)。IP地址查找是路由器轉(zhuǎn)發(fā)性能的瓶頸，因此本文對(duì)IP路由查找技術(shù)進(jìn)行了深入研究，并分別對(duì)兩篇文獻(xiàn)中提出的算法進(jìn)行了改進(jìn)。
　　本文首先對(duì)路由系統(tǒng)和IP路由查找技術(shù)進(jìn)行

2、了相關(guān)研究，對(duì)當(dāng)前IP路由查找技術(shù)的難點(diǎn)進(jìn)行了分析；然后對(duì)當(dāng)前已有的典型IP路由查找算法進(jìn)行了分類研究，重點(diǎn)對(duì)基于Trie樹的算法、基于哈希技術(shù)的算法和基于硬件TCAM的算法進(jìn)行了研究和分析，總結(jié)了各種算法的優(yōu)點(diǎn)和缺點(diǎn)，對(duì)本文提出改進(jìn)算法起到了較大的啟發(fā)。
　　本文針提出了一種基于Trie樹的動(dòng)態(tài)規(guī)劃算法。該算法可以確定一個(gè)最優(yōu)的前綴劃分方式，以使在所有不同的劃分方案中，該劃分方案可以達(dá)到空間最優(yōu)，哈希結(jié)構(gòu)使用的空間達(dá)到最小。實(shí)驗(yàn)

3、結(jié)果表明，不同劃分方式使用的空間差距較大，而本文提出的動(dòng)態(tài)規(guī)劃算法可使空間達(dá)到最優(yōu)。
　　本文還提出了一種可升級(jí)的、支持快速動(dòng)態(tài)更新的基于B+樹的IP路由查找算法。該數(shù)據(jù)結(jié)構(gòu)用最特殊前綴作為關(guān)鍵字來(lái)構(gòu)造B+樹，用一個(gè)無(wú)符號(hào)整數(shù)來(lái)壓縮存儲(chǔ)包含一個(gè)最特殊前綴的所有前綴。和其他可升級(jí)的動(dòng)態(tài)算法相比，該算法對(duì)路由表中的每一個(gè)前綴只存儲(chǔ)一次，且查找到葉節(jié)點(diǎn)就能找到匹配的最長(zhǎng)前綴，而不會(huì)往回查找。對(duì)于一個(gè)有n個(gè)前綴的路由表，使用m階的B+樹，