快速路由查找算法的研究

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

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

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

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

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

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