基于OPNET的二叉樹路由查找算法的設計與實現

戴澤華 張連連 鄧全才 葛 宇

(1.張家口市交通局，河北張家口075000;2.河北建筑工程學院，河北張家口075024)

0 前言

隨著科學技術的發展，不論地面網絡還是空間網絡的規模都呈指數級增長，路由器是構成因特網的中間節點，其轉發性能決定了因特網的整體性能.傳統的路由查找算法已不能滿足需求對大容量路由表處理的適應性以及報文轉發查表的能力提出了更高要求.因此，路由查找技術已經成為了當前路由器轉發性能的瓶頸之一［1］.

1 二叉樹路由查找算法介紹

1.1 路由查找算法

路由查找查找就是在對應的轉發表中進行精確匹配查找.設分組的目的地址為D，包含長度為W的比特數.設路由前綴為P，包含的比特數為0～W，L(P)表示前綴長度.地址D匹配前綴P的含義:地址D的前L(P)位比特值與前綴P完全相同.給定一個路由前綴集合PA，集合含有N個路由前綴，到達分組的目的地址為D，路由的最長前綴匹配查找定義為:在前綴集合PA中搜索到的前綴Pm滿足:目的地址D匹配前綴Pm;在集合PA中不存在其他的前綴P，滿足D匹配P，且L(P)＞L(Pm).

路由查找過程中首先根據IP地址的前幾位得到該地址所屬的地址類別;其次根據地址類別提取目的地址中的網絡地址部分;最后根據相應的查找算法查找相應的路由地址.

1.2 二叉樹路由查找算法［2］

本文采用的樹型結構為鍵樹，每個結點中存儲的信息為二進制數值，0或1，因此每個結點的度為小于等于2的自然數，此種類型的樹又叫做二叉檢索樹(Trie)，樹中的每個結點含有路由前綴的1比特信息，并根據下一個比特生成兩個子結點.在樹的非空結點處，存放該結點對應的下一跳信息.在進行最長前綴匹配時，首先根據路由前綴的比特信息遍歷二叉樹，達到最終匹配的葉子結點處，最后讀出存儲在葉子結點中的下一跳路由信息.

二叉檢索樹進行路由查詢時，時間復雜度與樹的深度(在這種算法中就等于路由前綴的最大長度)有關.如果最大可能的路由前綴長度為W，則最壞情況下的查找時間復雜度為O(W).最壞情況下的空間復雜度為O(N*W).更新復雜度為O(W).更新時需要先進行查找，找到之后進行相應的增刪操作就可以了(包括中間節點和葉子節點兩種情況).在IPv4中最多需要32次查找，在IPv6中最多需要128次查找.

2 二叉樹路由查找算法的設計實現

對二叉樹路由查找算法的設計實現主要從兩個方面來進行.一是存儲方式，即用二叉樹結構表示路由表中內容的方法.二是查找方式，即在二叉樹中查找相應目的地址的方法.

2.1 存儲方式

從根到葉子結點路徑中的字符組成的字符串表示一個關鍵字，葉子結點中的特殊符號空格(“”)以表示字符串的結束.Trie是一個有序樹，即同一層中兄弟結點之間所含符號自左到右有序，并假設空格小于任何字符.

采用多重鏈表的方式表示Trie樹，樹中的每個結點含有3個指針域，如果從樹的每個結點到葉子結點的路徑上都只有一個孩子，就將該路徑上的所有結點壓縮成一個葉子結點，在葉子結點中存儲關鍵字及其路由表相關信息.

在Trie中有兩種結點:分支節點:含有3個指針域，在分支結點中不設數據域，每個分支結點所表示的字符均由其雙親結點中(指向該結點)的指針所在位置決定;葉子結點:含有關鍵字域和指向路由表記錄的指針域.

2.2 查找方式

在查找的過程中，有可能出現多個前綴匹配的情況，這時要選擇最長的前綴.同時在查找時要記錄當前最匹配的路由前綴，一直到葉子節點或者節點沒有合適的分支為止.在進行最長前綴匹配時，首先根據路由前綴的比特信息遍歷二叉樹，達到最終匹配的葉子節點處，最后讀出存儲在葉子節點中的下一跳路由信息.具體操作為從根結點出發，沿給定值相應的指針逐層向下，直至葉子結點，如果葉子節點中的關鍵字和給定值相等，則查找成功;如果分支結點中和給定值的相應指針為空，或葉結點中的關鍵字和給定值不相等，則查找失敗.

2.3 二叉樹查找算法在OPNET平臺上的實現

OPNET網絡仿真［3］軟件提供了三層建模機制，分別為進程模型，節點模型和網絡模型，這種建模方式和實際協議、設備、網絡完全對應，全面反映了網絡的相關特性.進行二叉樹查找算法實現時，考慮主要研究查找算法的性能，所以對實際協議進行了簡化.

2.3.1 節點模型設計

主要分為地面節點和衛星節點.其中地面節點模型采取了應用層和鏈路層兩層協議機制，向衛星發送route_hello包并發起路由查詢.而衛星節點模型采取了路由層和鏈路層兩層協議機制，保存整個場景的路由表，并執行路由表的查詢功能，找到相應的路由路徑.

2.3.2 進程模型設計

(1)地面節點的應用層應完成向衛星發送hello數據包和查詢數據包的功能，其狀態圖設計如圖1所示.

init狀態中初始化進程中的變量轉到idle狀態;當收到終端號為1時轉到send的狀態，定時向衛星節點發送查詢數據包轉到idle狀態;當收到自中斷號為2時轉到hello狀態，向衛星節點發送hello數據包轉到idle狀態;當收到數據包到來時，記錄收到的數據包個數并處理，回到idle狀態.

(2)衛星節點完成儲存場景路由表和路由查詢的功能，其狀態圖設計如圖2所示.

init狀態中初始化進程中的變量轉到idle狀態;當收到數據包到來時轉到PK_ARRIVE狀態，判斷數據包格式，若為hello數據包則把數據包中的源地址保存到路由表中，若為查詢數據包則根據目的地址按照二叉樹算法查詢路由表，找到對應的路由路徑.

2.3.3 網絡模型

仿真場景設置如圖3所示:一個衛星節點，100個地面節點(二叉樹深度為路由前綴長度為6)，修改了接收機組模型，使地面節點發送的數據包發送到衛星節點然后再進行轉發.

3 二叉樹路由查找算法性能分析

再2.3.3 的仿真場景中，設置仿真時間80S，選取路由查詢次數，單次查詢所需時間，路由表隊列長度進行結果分析［4］.

3.1 網絡模型路由查詢次數:即衛星收到的查詢數據包個數.

3.2 單次查詢所用時間(單次查詢訪問存儲器次數).

路由查找算法都是在軟件環境下設計實現的，算法查找時間主要是由查找過程需要進行的存儲器訪問次數所決定［5］.因此，通過統計算法在查找過程中存儲器訪問的次數就可以基本估計該算法的查找性能.本實驗采用的樹型結構為鍵樹，查詢的時間復雜度與樹的深度(在這種算法中就等于路由前綴的最大長度)有關.本實驗中路由前綴長度為6，與實驗結果相符.

3.3 路由表隊列長度

由于本實驗仿真場景并沒有變化屬于固定網絡場景，二叉樹深度為路由前綴長度即6.

4 總結

本文在OPNET平臺中對二叉樹路由查找算法進行了設計實現，并設計了相應的節點模型和網絡模型對二叉樹路由查找算法進行了性能分析，對今后進行多分支樹、路徑壓縮樹等樹結構的路由查找算法奠定了基礎.

［1］M A Ruiz San chez，E W Biersack，W Dabb ou s.Survey and Taxonomy of IP Address Lookup Algorithms［J］.IEEE Network，2001，15(2):8 ～23.

［2］劉永鋒，楊宗凱.高速路由器中基于樹型結構路由查找算法的研究與實現［J］.計算機工程與科學，2004，26(1):77～80.

［3］陳敏.OPNET網絡仿真［M］.北京:清華大學出版社，2004:1～281.

［4］譚明鋒，高蕾，龔正虎.IP路由查找算法研究概述［J］.計算機工程與科學.2006，28(6):87～91.

［5］徐恪，徐明偉，吳建平，吳劍.路由查找算法研究綜述［J］.軟件學報.2002.