基于二分查找和Trie的IPv6路由查找算法

分析基于前缀长度的二分路由查找算法和基于Trie的路由查找算法的优缺点,在此基础上提出一个改进的路由查找算法,并给出其在IPv6下的实现方案.由于基于前缀长度的二分路由查找算法扩展性好、查找速度快,而基于Trie的路由查找算法实现灵活、转发表动态更新快,这使得所提算法具备路由转发表动态更新快、查找速度快、对前缀长度扩展性好等优点.模拟实验表明该算法能够较好地满足IPv6的要求.

IPv6 routing search algorithm based on binary search and Trie

The merit and defect of both the binary routing search algorithm based on prefix length and that based on Trie were briefly analyzed.On this basis,an improved routing search algorithm was presented and its realization scheme was also given out in the case of IPv6.Due to the good expansibility and fast speed of searching with the first search algorithm mentioned above and the flexibility of algorithm implementing and fast dynamic updating of forwarding table with the second search algorithm above-mentioned,the algorithm presented was made to have the merits such as fast dynamic updating of routing forwarding table,fast searching speed,and good expansibility of prefix length.It was shown by the simulation result that this algorithm could well meet the requirement of IPv6.