采用Trie和二分查找的IPv6路由查找算法  

IPv6 Routing Search Algorithm by Applying Trie and Binary Search

作　　者：陈超[1] 

机构地区：[1]四川理工学院网络管理中心,四川自贡643000

出　　处：《控制工程期刊（中英文版）》2013年第3期147-154,共8页Scientific Journal of Control Engineering

基　　金：四川省科技厅支撑计划项目（2013GZ0030）;人工智能四川省重点实验室开放基金项目（2011RYY06）;四川理工学院国家基金培育项目（2011PY05）.

摘　　要：在IPv6下由于地址长度增加，导致路由器负担加重，目前很多已有的路由查找算法扩展到IPv6后无法适应新的需求。因此，路由查找算法要达到对IPv6很好的适应性，必须要在缓存策略、压缩策略、前缀扩展、独立前缀转化等各个方面都具有很好的性能。本文首先简要分析了基于Trie的路由查找算法和基于前缀长度的二分路由查找算法的优缺点，在此基础上提供了一个改进的路由查找算法并给出了其在IPv6下的实现方案。该改进算法把基于Trie的路由查找算法和基于前缀长度的二分路由查找算法结合起来，从而使其具备路由转发表动态更新、查找速度快、对前缀长度扩展性好等特点。仿真实验表明该算法能够较好地满足IPv6的要求。Because of increase of the address length under IPv6, the treatment burden of router is heavier; it is unable to meet the new demand to a lot of algorithms that is existing after expanding to IPv6 at present. So, for reaching very good adaptability to IPv6, routing search algorithms must have very good performance to buffering tactics, compressing tactics, prefix expanding, independent prefix to transform etc. This paper briefly analyzed the binary routing search algorithm based on prefix length and the routing search algorithm based on Trie. After then, it proposed an improved routing search algorithm and presented corresponding implementation schemes under IPv6. Combined the binary routing search algorithm based on prefix length and the routing search algorithm based on Trie, the improved algorithm supports MVRF dynamic to update, has higher search speed and better scalability of prefix length. Simulation results show that this algorithm can well satisfy the requirements of IPv6.

关 键 词：二分查找 IPV6 路由查找算法 路由转发表 MVRF 

分 类 号：TP311.12[自动化与计算机技术—计算机软件与理论]