基于有限前缀扩展和多Hash函数的动态IP路由查找算法

摘要

该算法根据IP路由表的分布特征将前缀有限扩展为三种长度,并用算法所提出的最大熵判定法选取多个Hash函数,将扩展后的前缀映射到三个Hash表的不同级别.在查找过程中算法根据三个Hash表的命中率动态计算查找代价,并据此调整对三个Hash表的搜索顺序.算法支持增量更新,适于软件实现和硬件流水实现.实验表明,对128K前缀的真实转发表算法仅约需3.7M字节,平均每次查找仅需约1.1次访存,而且路由更新时间较小.