基于OPNET的卫星路由查找算法仿真分析

邓全才 张连连 孙志田

（河北建筑工程学院，河北 张家口075000）

0 前 言

传统的查找方法（如顺序查找法、二分查找法）只能完成关键字的精确查找，而路路由查找需要完成最长匹配地址前缀的查找.本文针对在卫星网络中，常见的三种快速路由查找算法进行了比较透彻的分析和比较［1］.

1 算法介绍

1.1 线性表查找

线性表结构是最简单的查找数据结构，因此可以把所有的路由地址前缀用线性链表的方式组织起来.每一次查找需要遍历线性表中的所有表项，在遍历过程中记录最长的路由前缀项，直到遍历完整个线性链表为止［2］［3］.

1.2 二进制键树（Trie tree）查找

二进制键树［4］（Trie tree）的每个结点中存储的信息为二进制数值0或1，因此每个结点的度为小于等于2的自然数，树中的每个结点含有路由前缀的1比特信息，并根据下一个比特生成两个子结点.

1.3 哈希表（Hash）查找

哈希（Hash）算法在路由查询中应用的时候，通过查找建立的哈希索引，来找到对应的路由前缀.同时，整个路由表做为一个哈希表是不切实际的，可以在局部范围内应用哈希算法［5］.

2 网络模型

OPNET仿真［6］［7］［8］场景设置如图1所示：一个卫星节点，100个地面节点（二叉树深度为路由前缀长度为6，修改了接收机组模型，使地面节点发送的数据包发送到卫星节点然后再进行转发.

3 进程模型

3.1 地面节点

地面节点的应用层应完成向卫星发送hello数据包和查询数据包的功能，其状态图设计如图2所示.

图1 仿真场景

图2 地面节点状态图

init状态中初始化进程中的变量转到idle状态；当收到终端号为1时转到send的状态，定时向卫星节点发送查询数据包转到idle状态；当收到自中断号为2时转到hello状态，向卫星节点发送hello数据包转到idle状态；当收到数据包到来时，记录收到的数据包个数并处理，回到idle状态.

3.2 卫星节点

卫星节点完成储存场景路由表和路由查询的功能，其状态图设计如图3所示.

图3 卫星节点状态图

init状态中初始化进程中的变量转到idle状态；当收到数据包到来时转到PK＿ARRIVE状态，判断数据包格式，若为hello数据包则把数据包中的源地址保存到路由表中，若为查询数据包则根据目的地址按照相应的算法查询路由表，找到对应的路由路径.

4 实验及结果分析

实验仿真时间80S，选取以下几个参数进行结果分析：路由查询次数，即卫星收到的数据包个数；单次查询所用时间（单次查询访问存储器次数），即访问次数；查询深度；响应时间（硬件时间（ms））.在实验中，为了更好的观察实验效果，除了路由查询次数以外，其它参数均取平均值（average）或时间平均值（time＿average）为例来说明算法的性能.

计算出的时间与计算机硬件有关，本次仿真的计算机配置如图4所示.

图4 计算机系统配置

4.1 路由查询次数

从图5可以得出，在80S内三种算法得到的数据包总数均为60 000.

图5 路由查询次数

图6 访问次数

4.2 访问次数

路由查找算法都是在软件环境下设计实现的，算法查找时间主要是由查找过程需要进行的存储器访问次数所决定.因此，通过统计算法在查找过程中存储器访问的次数就可以基本估计该算法的查找性能.

从图6访问次数的平均值中可以看出线性表算法所用时间远远大于Trie tree和Hash算法所用时间，Hash算法所用时间略高于Trie tree算法所用时间.因此，如果以访问次数为标准，选择Trie tree算法为宜.

4.3 查询深度

由于本实验仿真场景属于固定网络场景，因此对于线性表最大查询深度为100，Trie tree最大查询深度为6，对于Hash算法来说其查询深度是动态变化的（根据需要需要重建哈希表），本实验队列长度的变化范围为100～200之间的素数序列.

图7为本次实验的结果，从图中可以得出，Trie树算法查询结果深度最低，线性表和哈希算法查询深度平均值最大，并且二者查询深度相近.因此，如果以查询深度为标准，选择Trie tree算法为宜.

图7 查询深度

图8 响应时间

4.4 响应时间

通过clock函数得出硬件滴答数，从而得到查询开始时间和查询结束时间，响应时间＝查询结束时间－查询开始时间.

图7为本次实验的结果，从图中可以得出，其中Hash算法响应时间不稳定，变化幅度较大，线性表和Trie tree算法响应时间较稳定，但最后都趋于相同.如果以响应时间为标准，由于Hash算法不稳定，选择线性表算法和Trie tree算法为宜.

4.5 结论

在卫星网络中，Trie tree算法总体性能最佳，但算法相对复杂，占用的存储器空间小；Hash算法不稳定，但算法对规则的增减比较容易，理论上讲，哈希算法的时间复杂度和空间复杂度都很低，但实际上很难找到一个完美的或者近似完美的哈希函数，路由更新也往往会导致哈希表的重建；线性表算法比较稳定，但是访问次数较高，所占用的存储空间容量较大，但易于实现.

5 结束语

本文针对线性表算法、Trie tree算法以及Hash算法进行了详细的分析和介绍，并通过OPNET平台对上述三种算法进行了设计实现，并设计了相应的卫星网络模型和评估参数对三种查找算法进行了性能分析和比较，对今后进行卫星路由查找算法的应用和研究奠定了基础.

［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］刘永锋，杨宗凯.高速路由器中基于树型结构路由查找算法的研究与实现［J］.计算机工程与科学，2004，26（1）：77～80

［5］刘尉悦，王永纲，张万生，王砚方.基于Hash和二叉树的路由表查找算法［J］.中国科学技术大学学报，2006，36（3）：293～296

［6］陈敏.OPNE网络仿真［M］.北京：清华大学出版社，2004

［7］伍俊洪，杨洋，李惠杰，等.网络仿真方法和OPNET仿真技术［J］.计算机工程，2004，30（5）：106～108

［8］宋文苑，樊水康，张日飞.OPNET网络仿真与建模方法［J］.电脑开发与应用，2007，20（9）：51～52，55