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

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

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

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

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

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