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

A Dynamic IP Routing Lookup Algorithm Based on Limited Prefix Expansion and Multiple Hash Function Techniques

作　　者：谭明锋[1] 龚正虎[1] 高蕾[1] 

机构地区：[1]国防科学技术大学计算机学院,湖南长沙410073

出　　处：《电子学报》2005年第11期1992-1999,共8页Acta Electronica Sinica

基　　金：国家重点基础研究发展计划(973项目)(No.2003CB314802);国家自然科学基金重点项目(No.90104001)

摘　　要：该算法根据IP路由表的分布特征将前缀有限扩展为三种长度,并用算法所提出的最大熵判定法选取多个Hash函数,将扩展后的前缀映射到三个Hash表的不同级别.在查找过程中算法根据三个Hash表的命中率动态计算查找代价,并据此调整对三个Hash表的搜索顺序.算法支持增量更新,适于软件实现和硬件流水实现.实验表明,对128K前缀的真实转发表算法仅约需3.7M字节,平均每次查找仅需约1.1次访存,而且路由更新时间较小.This algorithm expands all prefixes to three kinds of lengths according to the prefixes distribution of route tables. And several Hash functions are selected by using the maximum entropy criterion method proposed in this paper, then map the expanded prefixes to different levels of three Hash tables. In process of IP routing lookup, the algorithm dynamically calculates the searching cost using the hit rate of the three Hash tables, and then adjusts its searching sequence accordingly. The algorithm supports increasing update, and is easy to be implemented in software or pipelined hardware. The experiment demonstrates that it needs less than 3.7 M bytes for the real route tables of 128K prefixes, and averagely it needs only 1.1 memory accesses for each lookup and few memory accesses for each update.

关 键 词：动态IP路由查找 有限前缀扩展 哈希 最大熵判定法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]