摘要
根据IPV6地址结构和骨干路由表特点,分析了原有路由查找算法,基于IPV6的掩码长度和分段地址,采用Hash表和多分支Trie树结构,提出了一种快速的IPV6路由查找算法。根据分段地址和掩码将最常用到的路由前缀按前缀长度设置Hash表,并将前缀值有序存放在表结点中。不仅可以进行前缀长度的二分查找,同时又是其它前缀匹配的索引。对于其他的前缀匹配问题,根据Hash表中的索引到相应的多分支Trie树完成最长前缀匹配。实践证明该算法具有较好的时空效率,可以较好地提高路由查找速度。
IP lookup algorithms and the characters of IPV6 bone route table has been analysed.Based on mask and segment address,a new IPV6 lookup algorithm has been provided.It uses Hash table and multi-tries,play the frequency prefix in Hash table by order of their value,not only can make bin-search,but also take a index of other prefix.So other prefix can complete it s best prefix matching on multi-trie.This algorithm has better time efficiency and space efficiency.
出处
《计算机与数字工程》
2009年第10期8-11,共4页
Computer & Digital Engineering
基金
苏州科技学院基金项目(编号:z995)资助
