基于IP网络的路由查找算法的研究与设计

发布时间：2017-12-11 19:27

  本文关键词：基于IP网络的路由查找算法的研究与设计

  更多相关文章： 路由查找 最长前缀匹配 哈希函数 多比特树

【摘要】：路由器是组成互联网的重要节点设备,位于ISO/OSI七层模型中的网络层,负责网络中数据的转发工作。它将不同的网络连接起来,并为经过它的数据包选择最佳的出口进行转发。路由器转发数据包的快慢,决定了经过路由器的所有数据包的传输速度。目前,链路上传输的数据已经可以通过光纤来承载,其传输速度可以达到400Gbps,因此当前路由器的性能瓶颈在于路由查找算法。路由器的查找效率决定了路由器的性能,决定了互联网的数据吞吐量。互联网上大多数的流量还是由IPv4网络承载,研究基于IPv4的路由查找算法有其现实意义。如何解决最长前缀匹配问题,是设计路由查找算法的核心问题,目前众多学者主要围绕路由查找算法的最长前缀匹配问题展开研究。IPv6作为IPv4的下一代技术,具有128位的地址长度。它对IPv6网络中的核心路由器处理负担更重、要求更高。已有的基于IPv4的路由查找算法,扩展到IPv6后无法适应新的需求或效率低下,需要建立新的基于IPv6的路由查找算法。论文主要围绕基于IPv4、IPv6路由查找算法展开,分别给出了适用于IPv4和IPv6的路由查找算法。主要工作包括:1、分析了 IPv4的地址结构及其发展史,通过对核心路由器中路由表数据的分析,发现了 IPv4地址前缀分布呈现一定特点:地址前缀长度为24的表项最多。论文针对这个特性,提出了一种哈希表和多比特树相结合的分阶段路由查找算法,算法将路由查找阶段分为两个阶段,分别是哈希表查找阶段和多比特树结构查找阶段。为了减少对存储器的访问,还提出了一种固定高度的多比特树结构:4-3Trie,该结构将路由查找时访问存储器的次数限定在了可接受的范围之内。算法分析和实验仿真表明,该算法通过利用IPv4地址前缀分布的特点,提高了查找效率,具有良好的路由查找性能。2、分析了 IPv6地址结构,通过对从Internet核心路由器的路由表中获取了路由前缀分布数据分析,发现地址前缀长度为16倍数的表项最多,其中尤以地址前缀长度为48的表项最多,其次是地址前缀长度为32的表项。同时分析还发现,在路由表中前缀中以20、24、26、28和2a开头的表项占了绝大多数。在此分析基础上,综合运用了哈希表和多比特树两种结构,提出了一种适用于IPv6的分阶段的路由查找算法,给出了 H16、H32、H32c、H48、H48c和H64六个哈希函数和一套哈希冲突解决策略。同时算法还提出了 6-5-4Trie结构,将树的高度控制在了可接受的范围,并且,算法在压缩树高度的同时,尽可能的降低树的稀疏程度来减少存储空间的浪费。算法分析和实验仿真证明,该算法在查找速度和存储空间上都有优势,能够满足核心路由器的性能要求。路由查找算法是复杂的,众多学者对其进行了深入的研究,我们是在前人研究的基础上进行了改进和探索。相关研究成果已被录用,即将在国内外的核心期刊上发表。
【学位授予单位】：扬州大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP393.0

【相似文献】

中国期刊全文数据库 前10条

1 廖恬瑜,涂晓东,黄协;高速路由查找算法的研究[J];电子科技大学学报;2004年06期

2 徐恪,徐明伟,吴建平,吴剑;路由查找算法研究综述[J];软件学报;2002年01期

3 王智强,王振兴,张定心;快速路由查找算法研究[J];计算机应用研究;2004年02期

4 刘英臣;傅光轩;;路由查找技术的分析及研究[J];贵州大学学报(自然科学版);2006年03期

5 郭润伟;;路由查找算法研究与分析[J];科技经济市场;2009年06期

6 朱国胜;余少华;;一种新的二分路由查找方法[J];小型微型计算机系统;2010年09期

7 袁博;汪斌强;王志明;;并行多流水绿色路由查找架构和算法[J];西安电子科技大学学报;2012年02期

8 田园;王萌;缪建军;刘葳;;星上路由查找的设计与分析[J];电子质量;2012年04期

9 徐宇锋,李乐民;快速路由查找算法及其实现[J];通信技术;2001年07期

10 姚兴苗,李乐民,胡光岷;快速路由器的路由查找和流分类算法研究[J];电子科技大学学报;2004年06期

中国重要会议论文全文数据库 前3条

1 张荣高;龚雪春;;基于位图映射路由查找算法的研究[A];2006通信理论与技术新进展——第十一届全国青年通信学术会议论文集[C];2006年

2 王燕;;IPv6的快速路由查找算法研究[A];2005年全国开放式分布与并行计算学术会议论文集[C];2005年

3 苗建松;丁炜;;改进的TCAM路由更新方法与实现[A];2006年全国开放式分布与并行计算学术会议论文集（二）[C];2006年

中国重要报纸全文数据库 前1条

1 吴;神码网络加速多业务融合[N];计算机世界;2006年

中国博士学位论文全文数据库 前6条

1 王振兴;NGI高性能路由器转发处理算法与实现[D];南京理工大学;2004年

2 谭明锋;域间路由协议BGP-4健壮性测试技术的研究[D];国防科学技术大学;2005年

3 郑凯;高性能IP路由查找和分组分类技术的研究[D];清华大学;2006年

4 汪漪;内容中心网络路由查找关键技术研究[D];清华大学;2013年

5 胥小波;新型蜜网体系结构及告警聚类的关键技术研究[D];北京邮电大学;2012年

6 朱国胜;高速分组查找规则匹配算法研究[D];华中科技大学;2010年

中国硕士学位论文全文数据库 前10条

1 张宁;基于Lua的手游服务器的研究与设计[D];南华大学;2015年

2 贺雨虹;命名数据网络的路由查找算法研究[D];哈尔滨工业大学;2015年

3 秦怡;基于IP网络的路由查找算法的研究与设计[D];扬州大学;2017年

4 张理阳;一种基于哈希策略的路由查找算法[D];长沙理工大学;2011年

5 王智强;高速路由查找算法研究[D];中国人民解放军信息工程大学;2003年

6 张荣高;网络处理器原型系统路由查找算法的研究[D];国防科学技术大学;2006年

7 陈静;路由器中路由查找子系统的实现和优化[D];华中科技大学;2006年

8 王波;基于FPGA的快速路由查找算法研究及实现[D];西安电子科技大学;2009年

9 奚晓华;基于FPGA的可编程高速路由查找算法的研究与实现[D];南京邮电大学;2013年

10 张晓波;路由查找算法的研究及其FPGA实现[D];华东师范大学;2006年

，

本文编号：1279674