一種新型IP數據鏈網絡路由算法模型

馮 彬

(中國西南電子技術研究所,成都 610036)

一種新型IP數據鏈網絡路由算法模型

馮 彬

(中國西南電子技術研究所,成都 610036)

針對無線數據鏈網絡,提出了一種新型的基于分層結構的IP路由算法模型,滿足至少3種異構數據鏈網絡的集成要求。仿真結果表明,該模型可有效支撐基于鏈路帶寬、傳輸時延、鏈路質量等多種QoS的路由算法設計,為無線數據鏈網絡層IP路由協議和算法設計提供了理論框架和實現指導。

IP數據鏈網絡;路由算法模型;網絡層;IP路由協議

1 引 言

進入21世紀,通信領域中的數據鏈技術呈現出高速發展態勢,鏈路傳輸速率越來越快,業務類型越來越多。寬帶數據鏈的出現,不僅滿足了大容量圖像、視頻的實時傳輸需求,同時也促進了各種商用技術在數據鏈通信領域中的應用,如Web、VoIP、DDS服務等。為了進一步發展基于數據鏈的網絡化協同作戰能力,在數據鏈網絡中實現IP協議,為用戶提供通用的IP服務,已經成為未來數據鏈技術的發展趨勢[1]。

最早提出IP數據鏈概念的是美國陸軍和空軍。戰術互聯網[2]有效地將美國陸軍的武器平臺、指控系統、傳感器以及后勤支援系統連接起來,網絡層面采用IP技術,功能與商用Internet相似,利用IP協議來交換可變信息格式(VMF)文電;MP-CDL數據鏈[3]是美國空軍于2002年開始研制的一種新型寬帶情報偵察數據鏈,兼容IP協議,2006年10月,L-3通信公司宣布成功地完成了基于IP的MP-CDL系統測試,驗證了其通過網絡中心終端向地面作戰人員提供實時運動圖像的能力;TTNT數據鏈[4]是一種高速、寬帶、基于IP協議的網絡通信系統,可將空中平臺與陸基全球信息柵格(GIG)節點連接在一起,利用IP技術,可將網絡建立時間縮短到 5 s;ACN是美軍重點發展的一個項目,其本質是在中繼通信的基礎上,提供IP數據報的路由功能。通過對美軍各種新型數據鏈的研究可以看到,運用IP技術可使其各種數據鏈平滑接入到全球信息柵格(GIG)中,實現不同軍兵種之間的互聯互通。但根據目前掌握的文獻資料來看,美軍并未對外公布IP數據鏈網絡底層采用的具體技術細節,尤其是網絡層的路由協議和路由算法。

由于各種數據鏈具有不同的物理層、鏈路層和網絡層協議,其中網絡層協議通常采用專用設計,重點解決同種數據鏈網絡成員之間的組網問題,要實現異類數據鏈的互聯,就必須在它們各自的網絡層協議上再進行一次標準協議封裝,采用IP協議是一條較好的解決途徑,其技術成熟,兼容擴展能力強。在數據鏈網絡上封裝IP協議,就是要實現數據鏈特有的網絡層協議到標準IP協議的映射轉換,向用戶屏蔽數據鏈的底層技術細節,對上提供標準的IP接口,同時實現基于IP的網絡路由。為在異構數據鏈網絡中實現IP協議,需要在底層建立一套通用的路由算法模型。本文針對無線數據鏈網絡的特點,提出了一種全新的算法模型并進行了仿真對比,為后續的IP數據鏈路由算法和路由協議設計提供了良好的理論參考。

2 路由設計

2.1 IP數據鏈網絡

基于IP的數據鏈技術就是在數據鏈網絡層封裝標準的IP協議,網絡用戶間的數據通信就如同在有線互聯網中一樣,利用基于IP的上層通信協議(如UDP、TCP等)進行端到端的數據通信,用戶看不到具體的數據鏈設備,也不知道IP數據報是如何傳遞到目的端的,僅通過IP地址進行相互訪問。基于該技術的用戶通信示意圖如圖1所示,其中(a)描述的是用戶所感知到的數據報傳輸路徑,(b)描述的則是實際的數據傳輸路徑。

圖1 基于IP數據鏈技術的通信示意圖Fig.1 An illustration of IP data link communication

在基于IP的數據鏈通信過程中,網關擔任了重要的角色,它同時與用戶和數據鏈設備接口,維護了IP數據鏈網絡的路由信息,以及IP數據報到數據鏈設備的接口適配。網關一方面從本地局域網接收來自源端用戶的IP數據報,提取其目的IP地址并查找路由表,選擇相應的數據鏈路,再完成IP數據報到數據鏈設備的接口適配,最后通過無線鏈路進行發射;另一方面,網關通過數據鏈設備接收來自無線鏈路的數據,恢復出完整的IP數據報,查詢路由表,判斷是否將數據報交付到局域網上的目的用戶終端,或是通過另外的數據鏈路進行轉發。

2.2 路由協議

路由協議是通信網絡中各個成員節點(終端節點或交換節點)需要遵循的一套規則和流程,在有線互聯網中,典型的路由協議有RIP、OSPF、BGP等。路由協議簡單來講可以分為3個部分:一是路由信息更新過程,各個節點間按照一定的規則交互網絡拓撲信息,相互感知網絡的變化情況;二是路由算法,結合感知的網絡拓撲信息,根據一定的規則和方法進行數據報傳輸路徑計算,形成路由信息;三是路由表,用于存儲經處理后得到的路由信息,該表在網絡運行過程中會不斷地被刷新。

在IP數據鏈網絡中,網關是路由協議運行的主要載體,負責路由表的生成和維護,網關之間通過交互路由信息,并結合路由算法,就可實現路由的計算。由于本文的研究重點是路由算法模型,考慮到數據鏈網絡的規模通常較小,因此路由信息更新過程和路由表設計可直接參考互聯網的RIP協議。假設經過數輪的路由信息交互,各個網關均掌握了網絡的拓撲結構和鏈路信息,但考慮到數據鏈網絡的特殊性,網關在相互進行路由信息交互時,還需要額外傳遞以下內容:鏈路配置(本地的數據鏈配置信息,包括鏈路類型和數量);鏈路負載(本地各條數據鏈路的可用帶寬);鏈路時延(本地各條數據鏈的數據傳輸延遲);鏈路質量(本地各條數據鏈的傳輸誤包率);接口適配開銷(本地網關與各條數據鏈之間的接口適配處理開銷)。

2.3 算法模型

在IP數據鏈網絡中,路由算法是用于計算“最佳的”數據報傳輸路徑,算法設計應緊密結合數據鏈的特點。對比有線互聯網,數據鏈網絡具備以下特點:第一,網絡規模小,數據報傳輸通常不會超過幾跳;第二,鏈路帶寬資源非常寶貴,傳輸時延和誤包率存在一定的不穩定性;第三,節點間可能存在多條直接通信鏈路;第四,數據報在不同數據鏈路間進行接口適配時,存在不同的處理開銷。為此,需要設計一種通用的路由算法模型,滿足上述數據鏈網絡的特殊需求。

2.3.1 網絡模型設計

為了便于描述,首先對數據鏈網絡進行一定的抽象,假設整個網絡中存在A、B、C 3種數據鏈,每個網絡節點可能配置數量不等的數據鏈路,網絡拓撲采用分層結構設計,如圖2所示。

圖2 分層的網絡模型Fig.2 Layered network model

在圖2的分層模型中,最上層是網關接入層,該層各個節點即為網關節點,利用IP地址進行標識;下面幾層代表了各種數據鏈的網絡拓撲結構,層中各個節點之間的實線代表了具體的無線通信鏈路。為簡化描述,圖2中對于每一類數據鏈,單個節點僅配置最多一條該鏈路,若節點配置的鏈路種類或數量更多時,通過增加分層即可進行描述。網關接入層與各個數據鏈網絡拓撲層之間的垂直虛線代表了數據處理通道,實質就是網關完成IP數據報與具體數據鏈的接口適配處理通道。在分層網絡模型中引入以下工作參數。

(1)BWX(m-n):在數據鏈X的網絡拓撲層中,節點m至節點n的單向鏈路可用帶寬。同理,BWX(n-m)則代表了該網絡中節點n至節點m的單向鏈路可用帶寬。

(2)DX(m-n):在數據鏈X的網絡拓撲層中,節點m至節點n的單向鏈路傳輸時延。同理,DX(n-m)則代表了該網絡中節點n至節點m的單向鏈路傳輸時延。

(3)EX(m-n):在數據鏈X的網絡拓撲層中,節點m至節點n的單向鏈路傳輸誤包率。同理,EX(n-m)則代表了該網絡中節點n至節點m的單向鏈路傳輸誤包率。

(4)TX(m):網關節點m接收到用戶IP數據報后,完成IP數據報到數據鏈X的接口適配所耗費的軟件開銷。

(5)RX(m):網關節點m從數據鏈X接收到數據后,完成到標準IP數據報的接口轉換所耗費的軟件開銷。

2.3.2 算法模型設計

路由算法就是在網絡拓撲模型中,計算最佳數據傳輸路徑的方法。在IP數據鏈網絡中,路由算法應充分結合數據鏈的特點,路由優選規則可以根據具體情況進行定義,如“最短傳輸時延”、“最佳帶寬利用率”等。本文提出了一種抽象的通用路由算法模型,在分層的網絡拓撲圖中計算一條“最小代價”的路徑,鏈路代價定義綜合了鏈路帶寬、傳輸時延、誤包率、處理開銷等因素,通過改變代價函數就可以實現不同的路由優選規則。

在分層的網絡模型中,數據鏈網絡拓撲層中各條水平鏈路的代價COSTX(m-n)定義為

式中,COSTX(m-n)代表了數據鏈X的網絡拓撲層中節點m至節點n的水平單向鏈路代價,若這兩個節點間沒有數據鏈X的通信鏈路,則COSTX(m-n)設為+∞。本文并不對公式(1)中的 f函數進行具體定義,這可以根據路由優選規則進行設計。例如,路由優選原則是“最短傳輸時延”,則 f函數應加大對參數DX(m-n)的敏感程度,降低其他兩個參數的比重,當鏈路時延提升時,鏈路代價也會明顯增大,這樣在進行路由計算時,會優先選擇傳輸時延較短的數據鏈路。

同理,分層網絡模型中網關接入層與下層之間的垂直鏈路代價COSTTX(m)和COSTRX(m)定義為其中,COSTTX(m)表示節點m的網關接入層至數據鏈X網絡拓撲層的單向垂直鏈路代價,COSTRX(m)則表示其返向鏈路代價,若節點m沒有配備數據鏈X,則這兩個值均設為+∞。同樣本文不對公式(2)和(3)中的g1、g2函數進行具體定義,這也可結合實際情況進行設計,如考慮網關節點的硬件處理能力、數據鏈消息與IP數據報的接口適配處理復雜程度等。

在IP數據鏈網絡中,每個網關節點均需要計算它到其他網關節點的路徑。以某個網關節點計算一條路徑為例進行路由算法描述,如下所述。

步驟1:計算鏈路代價

網關節點根據最新的路由更新數據,形成分層的網絡拓撲結構圖,更新圖中各條鏈路的可用帶寬、延遲等參數,完成鏈路代價函數設計,并按照公式(1)～(3)完成各條鏈路代價的計算。需要注意的是,在雙向鏈路中鏈路代價是需要區分方向性的。

步驟2:路徑計算

在分層的網絡拓撲中,從源網關節點開始計算到目的網關節點的最小代價路徑,該條路徑可能經過多個數據鏈網絡拓撲層,并在多個層之間來回穿越,最終到達目的節點。最小代價路徑計算可采用經典的Dijkstra算法[5],若計算出路徑的總代價不為+∞,則路徑計算成功。

步驟3:更新路由表

根據路徑計算結果,更新本地路由表,對“目的IP地址”和“下一跳IP地址”欄目的數據進行更新,后續網關將根據路由表信息進行具體的IP數據報分發處理。

步驟4:運行路由更新協議

網關實時監控本地數據鏈的運行狀態,更新鏈路的各項參數指標,參與與其他網關節點之間的路由信息更新過程,并定期進行路由的實時更新計算。

3 算法仿真

本文提出的路由算法模型可以滿足多種路由優選規則的要求,通過巧妙地設計鏈路代價的定義函數(即f函數和g函數),就能夠在路由計算時權衡各種鏈路性能指標,從而優選出滿足用戶要求的最佳路徑。雖然本文重點并不是進行鏈路代價設計,但為了驗證算法模型的正確性和擴展性,這里給出了3種最簡單的鏈路代價定義函數,對應3種路由算法。為了簡化仿真,忽略層與層之間的垂直鏈路代價(即g1()=g2()=0),僅考慮水平鏈路代價。

在Matlab環境下對上述3種算法進行仿真,使用的網絡拓撲如圖2所示,假設同種數據鏈網絡中的各條鏈路的可用帶寬、傳輸時延和誤包率指標均相同,所有鏈路為雙向對稱鏈路。初始化時,數據鏈網絡A中各條鏈路的BW=10、D=10、E=10-6;數據鏈網絡B中各條鏈路的BW=50、D=20、E=10-5;數據鏈網絡C中各條鏈路的BW=100、D=30、E=10-4。IP數據傳輸請求在5個網關節點間隨機產生,共進行1 000個周期的模擬仿真,每個周期產生一個單播數據傳輸請求(耗費的鏈路帶寬為0.1～1之間的一個隨機數),每個數據連接占用n個周期(n為可變參數)的鏈路資源。網絡每經過20個處理周期就進行一次路由信息更新過程(假設該過程不占用鏈路可用帶寬資源)。仿真結果如圖3所示。

圖3 路由阻塞性能Fig.3 Routing block performance

在圖3中,橫坐標n是數據連接的鏈路資源占用周期,縱坐標代表了路由計算失效(即路徑總代價為+∞)的次數,反映了路由算法的阻塞性能。可以看到,隨著鏈路資源占用周期的增大,3種路由算法的路由阻塞次數均提高,但算法1體現了最佳的抗阻塞性能,主要原因是算法1優選可用帶寬較大的傳輸路徑,數據業務帶寬能夠平均地分布在網絡中,網絡連通性最好,阻塞次數最少;算法2和算法3由于分別優選時延和誤包率較低的鏈路,導致了大量的數據業務分布在某些關鍵鏈路上,極快地耗費完了這些鏈路的可用帶寬,降低了網絡的連通性,導致路由阻塞次數增多。

圖4反映了3種算法計算出路由的平均時延對比,路由時延定義為該路由經過的所有數據鏈路的時延總和。從圖中可以看到,算法2計算出的平均路由時延最短,主要原因是算法2以鏈路時延作為計算代價,在路由選擇時優先尋找時延較短的鏈路,因此計算出的路由總時延相對最小。

圖4 路由時延性能Fig.4 Routing delay performance

圖5反映了3種算法計算出路由的平均誤包率對比,路由誤包率定義為該路由經過的所有數據鏈路的誤包率的疊加。從圖中可以看到,算法3計算出的平均路由誤包率最低,這與算法3采用的鏈路代價定義緊密相關,算法會優先選擇誤包率較小的鏈路,因此計算出的路由總誤包率也相對較小。

圖5 路由誤包率性能Fig.5 Routing error rate performance

通過上述仿真分析可以看到,本文提出的路由算法模型能夠很好地支持各種路由算法設計,在分層的網絡拓撲結構圖中,通過改變鏈路代價定義函數,就能方便地調整路由優選規則,使路由算法具備較強的靈活性,滿足帶寬、時延、誤包率等方面的需求;對鏈路代價函數進行優化設計,就可以在各項鏈路指標間進行權衡,使路由選擇滿足不同場合下的用戶需求。另外,整個算法模型用標準的數據結構構建,網絡拓撲、路由算法和協議均采用模塊化設計,通用性和兼容性較強,可以方便地從Matlab環境移植到C/C++環境,適應不同硬件平臺的處理要求。

4 結 論

本文針對IP數據鏈網絡,提出了一種全新的路由算法模型,該模型緊密結合數據鏈網絡的特點,能夠在鏈路帶寬、傳輸時延、誤包率等通用指標上進行權衡,仿真結果表明該算法模型能夠較好地支撐各種路由算法設計,為今后IP數據鏈網絡的網絡層協議設計提供了基礎理論框架。下一階段的研究重點是結合具體的數據鏈網絡,構建實例模型并設計優化的路由協議和算法,爭取在實用性和工程化方面有所突破。

[1]白劍林,高洪星,梁雨,等.數據鏈對未來信息化作戰的影響及建議[J].航空科學技術,2010,6(1):6-9.

BAI Jian-lin,GAO Hong-xing,LIANG Yu,et al.The Influence of Data Link on Future Informationized Warfare[J].Aeronautical Science and Technology,2010,6(1):6-9.(in Chinese)

[2]劉傳輝,周新力,劉宴濤.戰術互聯網絡體系結構[J].海軍航空工程學院學報,2008,23(1):43-48.

LIU Chuan-hui,ZHOU Xin-li,LIU Yan-tao.Research onNetwork Architecture of Tactical Internet[J].Journal of Naval Aeronautical and Astronautical University,2008,23(1):43-48.(in Chinese)

[3]張強,郭克平.美軍數據鏈的發展及應用[J].艦船電子工程,2010,30(2):18-21.

ZHANG Qiang,GUO Ke-ping.Development and Application of American Date Link[J].Ship Electronic Engineering,2010,30(2):18-21.(in Chinese)

[4]陳志輝,李大雙.對美軍下一代數據鏈TTNT技術的分析與探討[J].信息安全與通信保密,2011,5(1):76-79.

CHEN Zhi-hui,LI Da-shuang.Analysis and Exploration on Tactical Targeting Network Technology for the Next Generation Tactical Data Link[J].Information Security and Communications Privacy,2011,5(1):76-79.(in Chinese)

[5]裴志強,馮海濤.Dijkstra最短路徑算法[J].微處理機,2009,5(1):98-100.

PEI Zhi-qiang,FENG Hai-tao.The Shorte s t PathAlgorithm Based on Dijkstra Algorithm[J].Microprocessors,2009,5(1):98-100.(in Chinese)

Email:fengbin@swiet.com.cn

A New Routing Algorithm Model for IP Data Link Network

FENG Bin
(Southwest China Institute of Electronic Technology,Chengdu 610036,China)

A novel multi-layered IP routing algorithm model is proposed for wireless data link network and the model satisfies the integration requirement of at least three different data link networks.The simulation result shows that the model can effectively support the design of varied QoS(based on bandwidth,latency,error rate,etc.)routing algorithm and provides theoretical framework and implemental guide for IP routing protocol and algorithm design of wireless data link network.

IP data link network;routing algorithm model;network layer;IP routing protocol

the B.S.degree from University of Electronic Science and Technology of China in 1998.He is now an engineer.His research concerns avionics system design.

TN915

A

10.3969/j.issn.1001-893x.2012.06.033

1001-893X(2012)06-0992-05

2012-03-12;

2012-05-15

馮 彬(1973—),男,重慶人,1998年于電子科技大學獲學士學位,現為工程師,主要研究方向為航空電子系統總體設計。

FENG Binwas born in Chongqing,in 1973.He