散列索引多分支Trie树快速路由查找算法

摘要

路由器的主要任务是转发IP分组,实现高速分组转发的关键是快速的路由查找算法.我们针对IPv4地址,首先建立前缀长度为8、16和24的3张hash表,在此基础上,再分别针对不同长度的前缀建立最多只涉及其余8比特的多分支Trie树.在这种结构中进行IP路由查找,其存储器访问次数最多为7次,而且还具有易于更新、易于扩展等特点.