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

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

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

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