基于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.