位置:51电子网 » 技术资料 » IC/元器件

二叉线索这种数据结构的用法

发布时间:2014/8/31 20:31:51 访问次数:365

   假定有一个lP地址是10011011 01111010 00000000 00000000,需要查找该地址是否在此二叉线索中。我们从最左边查起。很容易发现,查到第三个字符(即前缀10后面的0)时,在二叉线索中就找不到匹配的,E5CN-HQ2H03-FLK说明这个地址不在这个二叉线索中。

   以上只是给出了二叉线索这种数据结构的用法,而并没有说明“与唯一前缀匹配”和“与网络前缀匹配”的关系。显然,要将二又线索用于路由表中,还必须使二叉线索中的每一个叶节点包含所对应的网络前缀和子网掩码。当搜索到一个叶节点时,就必须将寻找匹配的目的地址和该叶节点的子网掩码进行逐位“与”运算,看结果是否与对应的网络前缀相匹配。若匹配,就按下一跳的接口转发该分组。否则,就丢弃该分组。

   总之,二又线索只是提供了一种可以快速在路由表中找到匹配的叶节点的机制。但这是否和网络前缀匹配,还要和子网掩码进行一次逻辑与的运算。

   为了提高二叉线索的查找速度,广泛使用了各种压缩技术。例如,在图4-26中的最后两个地址,其最前面的4位都是1011。因此,只要一个地址的前4位是1011,就可以跳过前面4位(即压缩了4个层次)而直接从第5位开始比较。这样就可以减少查找的时间。当然,制作经过压缩的二叉线索需要更多的计算,但由于每一次查找路由表时都可以提高查找速度,因此这样做还是值得的。



   假定有一个lP地址是10011011 01111010 00000000 00000000,需要查找该地址是否在此二叉线索中。我们从最左边查起。很容易发现,查到第三个字符(即前缀10后面的0)时,在二叉线索中就找不到匹配的,E5CN-HQ2H03-FLK说明这个地址不在这个二叉线索中。

   以上只是给出了二叉线索这种数据结构的用法,而并没有说明“与唯一前缀匹配”和“与网络前缀匹配”的关系。显然,要将二又线索用于路由表中,还必须使二叉线索中的每一个叶节点包含所对应的网络前缀和子网掩码。当搜索到一个叶节点时,就必须将寻找匹配的目的地址和该叶节点的子网掩码进行逐位“与”运算,看结果是否与对应的网络前缀相匹配。若匹配,就按下一跳的接口转发该分组。否则,就丢弃该分组。

   总之,二又线索只是提供了一种可以快速在路由表中找到匹配的叶节点的机制。但这是否和网络前缀匹配,还要和子网掩码进行一次逻辑与的运算。

   为了提高二叉线索的查找速度,广泛使用了各种压缩技术。例如,在图4-26中的最后两个地址,其最前面的4位都是1011。因此,只要一个地址的前4位是1011,就可以跳过前面4位(即压缩了4个层次)而直接从第5位开始比较。这样就可以减少查找的时间。当然,制作经过压缩的二叉线索需要更多的计算,但由于每一次查找路由表时都可以提高查找速度,因此这样做还是值得的。



相关IC型号
E5CN-HQ2H03-FLK
暂无最新型号

热门点击

 

推荐技术资料

单片机版光立方的制作
    N视频: http://v.youku.comN_sh... [详细]
版权所有:51dzw.COM
深圳服务热线:13751165337  13692101218
粤ICP备09112631号-6(miitbeian.gov.cn)
公网安备44030402000607
深圳市碧威特网络技术有限公司
付款方式


 复制成功!