鄧全才 張連連 孫志田

（河北建筑工程學院，河北 張家口075000）

0 前 言

傳統(tǒng)的查找方法（如順序查找法、二分查找法）只能完成關(guān)鍵字的精確查找，而路路由查找需要完成最長匹配地址前綴的查找.本文針對在衛(wèi)星網(wǎng)絡中，常見的三種快速路由查找算法進行了比較透徹的分析和比較［1］.

1 算法介紹

1.1 線性表查找

線性表結(jié)構(gòu)是最簡單的查找數(shù)據(jù)結(jié)構(gòu)，因此可以把所有的路由地址前綴用線性鏈表的方式組織起來.每一次查找需要遍歷線性表中的所有表項，在遍歷過程中記錄最長的路由前綴項，直到遍歷完整個線性鏈表為止［2］［3］.

1.2 二進制鍵樹（Trie tree）查找

二進制鍵樹［4］（Trie tree）的每個結(jié)點中存儲的信息為二進制數(shù)值0或1，因此每個結(jié)點的度為小于等于2的自然數(shù)，樹中的每個結(jié)點含有路由前綴的1比特信息，并根據(jù)下一個比特生成兩個子結(jié)點.

1.3 哈希表（Hash）查找

哈希（Hash）算法在路由查詢中應用的時候，通過查找建立的哈希索引，來找到對應的路由前綴.同時，整個路由表做為一個哈希表是不切實際的，可以在局部范圍內(nèi)應用哈希算法［5］.

2 網(wǎng)絡模型

OPNET仿真［6］［7］［8］場景設置如圖1所示：一個衛(wèi)星節(jié)點，100個地面節(jié)點（二叉樹深度為路由前綴長度為6，修改了接收機組模型，使地面節(jié)點發(fā)送的數(shù)據(jù)包發(fā)送到衛(wèi)星節(jié)點然后再進行轉(zhuǎn)發(fā).

3 進程模型

3.1 地面節(jié)點

地面節(jié)點的應用層應完成向衛(wèi)星發(fā)送hello數(shù)據(jù)包和查詢數(shù)據(jù)包的功能，其狀態(tài)圖設計如圖2所示.

圖1 仿真場景

圖2 地面節(jié)點狀態(tài)圖

init狀態(tài)中初始化進程中的變量轉(zhuǎn)到idle狀態(tài)；當收到終端號為1時轉(zhuǎn)到send的狀態(tài)，定時向衛(wèi)星節(jié)點發(fā)送查詢數(shù)據(jù)包轉(zhuǎn)到idle狀態(tài)；當收到自中斷號為2時轉(zhuǎn)到hello狀態(tài)，向衛(wèi)星節(jié)點發(fā)送hello數(shù)據(jù)包轉(zhuǎn)到idle狀態(tài)；當收到數(shù)據(jù)包到來時，記錄收到的數(shù)據(jù)包個數(shù)并處理，回到idle狀態(tài).

3.2 衛(wèi)星節(jié)點

衛(wèi)星節(jié)點完成儲存場景路由表和路由查詢的功能，其狀態(tài)圖設計如圖3所示.

圖3 衛(wèi)星節(jié)點狀態(tài)圖

init狀態(tài)中初始化進程中的變量轉(zhuǎn)到idle狀態(tài)；當收到數(shù)據(jù)包到來時轉(zhuǎn)到PK＿ARRIVE狀態(tài)，判斷數(shù)據(jù)包格式，若為hello數(shù)據(jù)包則把數(shù)據(jù)包中的源地址保存到路由表中，若為查詢數(shù)據(jù)包則根據(jù)目的地址按照相應的算法查詢路由表，找到對應的路由路徑.

4 實驗及結(jié)果分析

實驗仿真時間80S，選取以下幾個參數(shù)進行結(jié)果分析：路由查詢次數(shù)，即衛(wèi)星收到的數(shù)據(jù)包個數(shù)；單次查詢所用時間（單次查詢訪問存儲器次數(shù)），即訪問次數(shù)；查詢深度；響應時間（硬件時間（ms））.在實驗中，為了更好的觀察實驗效果，除了路由查詢次數(shù)以外，其它參數(shù)均取平均值（average）或時間平均值（time＿average）為例來說明算法的性能.

計算出的時間與計算機硬件有關(guān)，本次仿真的計算機配置如圖4所示.

圖4 計算機系統(tǒng)配置

4.1 路由查詢次數(shù)

從圖5可以得出，在80S內(nèi)三種算法得到的數(shù)據(jù)包總數(shù)均為60 000.

圖5 路由查詢次數(shù)

圖6 訪問次數(shù)

4.2 訪問次數(shù)

路由查找算法都是在軟件環(huán)境下設計實現(xiàn)的，算法查找時間主要是由查找過程需要進行的存儲器訪問次數(shù)所決定.因此，通過統(tǒng)計算法在查找過程中存儲器訪問的次數(shù)就可以基本估計該算法的查找性能.

從圖6訪問次數(shù)的平均值中可以看出線性表算法所用時間遠遠大于Trie tree和Hash算法所用時間，Hash算法所用時間略高于Trie tree算法所用時間.因此，如果以訪問次數(shù)為標準，選擇Trie tree算法為宜.

4.3 查詢深度

由于本實驗仿真場景屬于固定網(wǎng)絡場景，因此對于線性表最大查詢深度為100，Trie tree最大查詢深度為6，對于Hash算法來說其查詢深度是動態(tài)變化的（根據(jù)需要需要重建哈希表），本實驗隊列長度的變化范圍為100～200之間的素數(shù)序列.

圖7為本次實驗的結(jié)果，從圖中可以得出，Trie樹算法查詢結(jié)果深度最低，線性表和哈希算法查詢深度平均值最大，并且二者查詢深度相近.因此，如果以查詢深度為標準，選擇Trie tree算法為宜.

圖7 查詢深度

圖8 響應時間

4.4 響應時間

通過clock函數(shù)得出硬件滴答數(shù)，從而得到查詢開始時間和查詢結(jié)束時間，響應時間＝查詢結(jié)束時間－查詢開始時間.

圖7為本次實驗的結(jié)果，從圖中可以得出，其中Hash算法響應時間不穩(wěn)定，變化幅度較大，線性表和Trie tree算法響應時間較穩(wěn)定，但最后都趨于相同.如果以響應時間為標準，由于Hash算法不穩(wěn)定，選擇線性表算法和Trie tree算法為宜.

4.5 結(jié)論

在衛(wèi)星網(wǎng)絡中，Trie tree算法總體性能最佳，但算法相對復雜，占用的存儲器空間?。籋ash算法不穩(wěn)定，但算法對規(guī)則的增減比較容易，理論上講，哈希算法的時間復雜度和空間復雜度都很低，但實際上很難找到一個完美的或者近似完美的哈希函數(shù)，路由更新也往往會導致哈希表的重建；線性表算法比較穩(wěn)定，但是訪問次數(shù)較高，所占用的存儲空間容量較大，但易于實現(xiàn).

5 結(jié)束語

本文針對線性表算法、Trie tree算法以及Hash算法進行了詳細的分析和介紹，并通過OPNET平臺對上述三種算法進行了設計實現(xiàn)，并設計了相應的衛(wèi)星網(wǎng)絡模型和評估參數(shù)對三種查找算法進行了性能分析和比較，對今后進行衛(wèi)星路由查找算法的應用和研究奠定了基礎(chǔ).

［1］Miguel A.Ruiz－Sanchez，Ernst W.Biersack，Walid Dabbous.Survey and Taxonomy of IP Address Lookup Algorithms［J］.IEEE Network，2001，15（2）：8～23

［2］徐恪，徐明偉，吳建平，吳劍.路由查找算法研究綜述［J］.軟件學報，2002.13（1）：42～50

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

［4］劉永鋒，楊宗凱.高速路由器中基于樹型結(jié)構(gòu)路由查找算法的研究與實現(xiàn)［J］.計算機工程與科學，2004，26（1）：77～80

［5］劉尉悅，王永綱，張萬生，王硯方.基于Hash和二叉樹的路由表查找算法［J］.中國科學技術(shù)大學學報，2006，36（3）：293～296

［6］陳敏.OPNE網(wǎng)絡仿真［M］.北京：清華大學出版社，2004

［7］伍俊洪，楊洋，李惠杰，等.網(wǎng)絡仿真方法和OPNET仿真技術(shù)［J］.計算機工程，2004，30（5）：106～108

［8］宋文苑，樊水康，張日飛.OPNET網(wǎng)絡仿真與建模方法［J］.電腦開發(fā)與應用，2007，20（9）：51～52，55