一种新型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