一种基于哈希策略的路由查找算法

《一种基于哈希策略的路由查找算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、学校代号：10536学号：0810803558密级：公开长沙理工大学硕士学位论文一种基于哈希策略的路由查找算法学位申请人姓名韭堡田导师姓名及职称史蓬璩副熬援培养单位拯过理工太堂专业名称让簋扭廑用撞苤论文提交日期2Q!!生三且!目论文答辩日期2Q!!生主旦!墨旦答辩委员会主席蒸佳红熬援Ahash-basedroutinglookupalgorithmbyZhangLiyangB．E．(UniversityofSouthChina)2008thesissubmittedinpartialsatisfactionof

2、theRequirementsforthedegreeofMasterofEngineeringComputerApplicationTechnologyChangshaUniversityofScience&TechnologySupervisorAssociateProfessorShiChangqiongMarch，2011长沙理工大学学位论文原创性声明本人郑重声明：所旱交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写

3、的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名：掀愿归E1期：沙∥年岁月娩学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电f版，允许论文被查阅和借阅。本人授权长沙理工大学町以将本学位论文的伞部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扛j描等复制手段保存和汇编本学位论文。本学位论文属于1、保密口，在年解密后适用本授权书。2、不保密圈。(请

4、在以上相应方框内打“4”)作者签名：苏瑶弦日期：如∥年岁月巧自导师签名：粤：长疬、日期：．20J1年r月)占口摘要随着Internet的迅速发展，用于网络互联的主干链路上的核心路由器的接口速率达到100Gbit／s。这就要求骨1二路由器每秒可以转发f万以上：的分组，然而分组转发的关键是查找路由表，高速的路由查找算法成为提高路由器性能的关键技术。本论文研究经典路由查找算法的具体设计，分析了现有路由查找算法的优缺点，并从查找速度方面入手给出了一种新的路由查找算法。论文主要从以下几个方面进行研究。首先，研究了各种经典

5、的路由查找算法，分析了路由查找算法的存在的问题以及路由查找算法的性能参数，并分析了各种路由查找算法的复杂度；然后，给出了一种基于满二叉树的分层哈希路由查找算法，算法充分考虑到Ⅲ路由查找前缀分布情况，将口路由查找前缀的查找重点放在查找前缀长度在16．24比特位之间m路由前缀，从而大大的加快了路由查找算法的查找速度；其次，给出了一种哈希负载平衡优化策略，将哈希动态负载平衡的优化策略应用f路由查找算法中。哈希算法的缺点就是会产生哈希碰撞，哈希动态负载平衡优化策略能有效的降低哈希碰撞几率，从而能够提高哈希算法的性能，从

6、而进一步提高路由查找算法的性能。最后，通过仿真实验，得出基于满二叉树的路由查找算法在查找速度上要明显优于以往算法。关键字：IP路由查找；分层哈希；满二叉树；哈希冲突AbstractWiththerapiddevelopmentofInternet,theinterfacerateofbackboneroutersisupt0100Gbit／s．Coreroutersmustprocessatenmillionormorepacketspersecond,andthemostimportantstepofforw

7、ardingprocessistolookuproutingtable，sothathi曲一speedroutinglookupalgorithmisthemajortechnologytoimproverouterperformance．Inthispaper,thespecificdesignofclassicalroutelookupalgorithmisresearched．Theadvantagesanddisadvantagesoftheexistingroutelookupalgorithmare

8、analyzed，andanewroutelookupalgorithmwhichcouldimprovetheroutinglookupspeedisgiven．Paperisstudiedonthefollowingaspects．First,avarietyofclassicalroutinglookupalgorithmsarediscussed，theproblemsofth