快速路由查找算法的研究

1、    快速路由查找算法的研究隨著因特網(wǎng)中主機(jī)數(shù)不斷增加，目前制約路由器性能的問題主要有3個(gè)：路由查找、分組交換和輸出調(diào)度。一些性能良好的解決交換和輸出調(diào)度的方案已經(jīng)提出，研究路由查找算法，提高路由查找速度成為進(jìn)一步提高路由器性能的關(guān)鍵。1常用路由查找算法線性表算法基本方案：基本思想是對于IPv4，把地址分成兩部分，第一部分24bit，第二部分8bit，兩部分均由線性表組成。兩個(gè)線性表分別用于存儲第0級擴(kuò)展樹和第1級擴(kuò)展樹。其中最高位為0表示查隨著因特網(wǎng)中主機(jī)數(shù)不斷增加，目前制約路由器性能的問題主要有3個(gè)：路由查找、分組交換和輸出調(diào)度。一些性能良好的解決

2、交換和輸出調(diào)度的方案已經(jīng)提出，研究路由查找算法，提高路由查找速度成為進(jìn)一步提高路由器性能的關(guān)鍵。1 常用路由查找算法線性表算法基本方案：基本思想是對于IPv4，把地址分成兩部分，第一部分24bit，第二部分8bit，兩部分均由線性表組成。兩個(gè)線性表分別用于存儲第0級擴(kuò)展樹和第1級擴(kuò)展樹。其中最高位為0表示查找結(jié)束，其他位表示下一跳地址信息；否則必須繼續(xù)查找。算法性能評估：優(yōu)點(diǎn)最差情況只需要讀兩次內(nèi)存。由于這兩次讀取在不同的內(nèi)存中可以使用流水線方法；算法簡單，易于硬件實(shí)現(xiàn)。缺點(diǎn)內(nèi)存利用不充分；轉(zhuǎn)發(fā)表的更新比較麻煩，更新一個(gè)前綴可能需要多次訪問內(nèi)存?；谇熬Y區(qū)間的算法 基本方案：將0232-1視為

3、IP地址的全空間，地址前綴視為IP地址空間中的一段連續(xù)區(qū)域，并用范圍取值來編碼，把最長匹配前綴問題轉(zhuǎn)化為尋找包含地址的最窄區(qū)間的問題。算法性能評估：優(yōu)點(diǎn)性能與地址的長度關(guān)系不是很密切，所以對前綴長度有很好的擴(kuò)展性。缺點(diǎn)轉(zhuǎn)發(fā)表不支持動態(tài)更新?；谇熬Y長度的二分查找算法基本方案：把前綴按長度分類，長度相同的前綴放到同一集合中，每個(gè)集合組成個(gè)Hash表，用個(gè)陣列來存儲這些Hash表。進(jìn)行最長前綴匹配時(shí)，在各個(gè)集合中尋找分組目的地址的匹配前綴，首先在長度最長的非空前綴集合中進(jìn)行，若成功則停止查找；否則轉(zhuǎn)至尚未查找的非空前綴集合中前綴長度最大的集合繼續(xù)進(jìn)行。算法性能評估：優(yōu)點(diǎn)該算法具有很好的擴(kuò)展性，而其

4、他方法對于擴(kuò)展到IPv6是很困難的。缺點(diǎn)某些前綴集合中的前綴數(shù)量大，找到一個(gè)無沖突的Hash函數(shù)很困難?；赥rie的路由查找算法 基本方案：通過Trie結(jié)構(gòu)相關(guān)技術(shù)構(gòu)造Trie樹，以此Trie樹為基礎(chǔ)進(jìn)行基于地址前綴長度的查找。算法性能評估：基于Trie樹的算法不僅具有較好的查找速度、空間復(fù)雜度和時(shí)間復(fù)雜度，而且能適應(yīng)不斷提高的路由器陛能的要求。2 基于二分查找Trie的路由查找算法在分析現(xiàn)有算法的基礎(chǔ)上，本文提出了一種新穎的路由查找算法基于二分查找Trie的路由查找算法。該算法的特點(diǎn)是采用了二分查找算法的思想，查找速度快，對前綴長度的擴(kuò)展性好；繼承了基于Trie算法的特點(diǎn)，支持轉(zhuǎn)發(fā)表的動態(tài)

5、更新，更新速度快；結(jié)合了基于前綴長度二分查找的優(yōu)點(diǎn)，并利用部分IP地址為索引避免了使用Hash函數(shù)。2.1 算法基本原理在論述前，首先對有關(guān)定義加以說明。步長：第k(k1)次查詢的前綴長度Lk與第k-1次查詢的長度Lk-1的差值的絕對值L=Lk-Lk-1稱為第k次查詢的步長L0=0。查詢方向：假設(shè)第K次查詢的網(wǎng)絡(luò)前綴長度為Lk，第K-1次查詢的網(wǎng)絡(luò)前綴為Lk-1，如果Lk-1<Lk測稱為k-1次查詢結(jié)果的方向是正向的(該節(jié)點(diǎn)為其父節(jié)點(diǎn)的右節(jié)點(diǎn))，否則為反向(該節(jié)點(diǎn)為其父節(jié)點(diǎn)的左節(jié)點(diǎn))。節(jié)點(diǎn)表示為NL,i，其中L表示該節(jié)點(diǎn)代表前綴的長度，i為節(jié)點(diǎn)編號。節(jié)點(diǎn)數(shù)組的表項(xiàng)表示為EL,i,

6、j，其中L和i的定義與節(jié)點(diǎn)中的定義相同，j為節(jié)點(diǎn)數(shù)組索引值。節(jié)點(diǎn)編號長度Li：該長度與節(jié)點(diǎn)所代表的前綴長度有關(guān)，根節(jié)點(diǎn)的編號長度為0，節(jié)點(diǎn)如果是其父節(jié)點(diǎn)的左節(jié)點(diǎn)，則該節(jié)點(diǎn)的節(jié)點(diǎn)編號長度與其父節(jié)點(diǎn)相同；如果是右節(jié)點(diǎn)，則該節(jié)點(diǎn)的節(jié)點(diǎn)編號長度等于其父節(jié)點(diǎn)所代表前綴的前綴長度。例如節(jié)點(diǎn)NW2,i的Li=0，其左節(jié)點(diǎn)的節(jié)點(diǎn)編號長度為0，右節(jié)點(diǎn)的節(jié)點(diǎn)編號長度為W2。節(jié)點(diǎn)編號值i：IP地址(用二進(jìn)制表示)前Li位的值。索引長度Lj=節(jié)點(diǎn)代表的前綴長度L-節(jié)點(diǎn)編號長度Li。索引值j：IP地址第Li+1位到第Li+Lj位所代表的值，該值既與前綴有關(guān)又與節(jié)點(diǎn)有關(guān)，對于不同的節(jié)點(diǎn)即使是相同的前綴其索引值也不同。查找級Le：表示節(jié)點(diǎn)所處的查找級。基于Trie的路由查找算法采用順序比較IP地址位數(shù)的方法，所以訪問存儲器次數(shù)較多，查找速度慢，如果采用二分的方法將會提高查找速度，基于二分查找Trie的路由查找算法的前綴長度查詢順序如圖1所示。對于前綴長度為W的IP地址，首先利用IP地址的前W2 bit與所有前綴長度為W2前綴進(jìn)行匹配，如果匹配成功則用I