资源描述：
《基于有限前缀扩展和多Hash 函数的动态IP 路由查找算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第11期电子学报Vol.33No.112005年11月ACTAELECTRONICASINICANov.2005基于有限前缀扩展和多Hash函数的动态IP路由查找算法谭明锋,龚正虎,高蕾(国防科学技术大学计算机学院,湖南长沙410073)摘要:该算法根据IP路由表的分布特征将前缀有限扩展为三种长度,并用算法所提出的最大熵判定法选取多个Hash函数,将扩展后的前缀映射到三个Hash表的不同级别.在查找过程中算法根据三个Hash表的命中率动态计算查找代价,并据此调整对三个Hash表的搜索顺序.
2、算法支持增量更新,适于软件实现和硬件流水实现.实验表明,对128K前缀的真实转发表算法仅约需3.7M字节,平均每次查找仅需约1.1次访存,而且路由更新时间较小.关键词:动态IP路由查找;有限前缀扩展;哈希;最大熵判定法中图分类号:TP393文献标识码:A文章编号:03722112(2005)11199208ADynamicIPRoutingLookupAlgorithmBasedonLimitedPrefixExpansionandMultipleHashFunctionTechniquesT
3、ANMingfeng,GONGZhenghu,GAOLei(SchoolofComputerScience,NationalUniversityofDefenseTechnology,Changsha,Hunan410073,China)Abstract:Thisalgorithmexpandsallprefixestothreekindsoflengthsaccordingtotheprefixesdistributionofroutetables.AndseveralHashfunctionsareselec
4、tedbyusingthemaximumentropycriterionmethodproposedinthispaper,thenmaptheexpandedprefixestodifferentlevelsofthreeHashtables.InprocessofIProutinglookup,thealgorithmdynamicallycalculatesthesearchingcostusingthehitrateofthethreeHashtables,andthenadjustsitssearchings
5、equenceaccordingly.Thealgorithmsupportsincreasingupdate,andiseasytobeimplementedinsoftwareorpipelinedhardware.Theexperimentdemonstratesthatitneedslessthan3.7Mbytesfortherealroutetablesof128Kprefixes,andaveragelyitneedsonly1.1memoryaccessesforeachlookupandfewmem
6、oryaccessesforeachupdate.Keywords:dynamicIProutinglookup;limitedprefixexpansion;hash;maximumentropycriterionmethod法等,它们的树高决定了访存次数,从而决定了时间性能.因1引言[3][5]此,路径压缩、leafpushing等技术被用于降低树高,但它们[6]Internet的高速发展使路由器每秒所需转发的报文数量在路由表较大时基本失效,所需平均访存数达20次以上.[7][5]剧增,而作为路由器转发能力
7、的关键因素之一,IP路由查找而LCTrie树算法、受控前缀扩展算法等则使用前缀扩[1][5]算法的优劣直接影响到Internet的整体性能.我们在中提出展以及多分支等优化技术来降低树高,但这些算法更新时了一种高性能IP路由查找硬件算法,该算法利了多个存储体间复杂度高,耗费空间大,且树的特点决定了这些算法仍需多的并行性以提高查找速度,所以不利于用软件实现.次访存.因此本文提出了LPE-MH(LimitedPrefixExpansionand一些利用Cache的算法努力让更多的访存落到Cache中[8][9]Multi
8、pleHash)算法,利用路由表分布特征,提出并运用最大熵以提高速度,如Lulea算法以及Chiueh所提出的算法等.判定法选择算法所用的Hash函数,运用有别于传统树形结构但由于使用了压缩技术和leafpushing技术,更新时需重建数的新思路:将前缀有限扩展成为三种长度的前缀,并保存到三据结构,且在搜索时需要解压缩,所以虽然它
