文档介绍：兰州理工大学
硕士学位论文
基于trie的路由查找算法研究
姓名:赵永精
申请学位级别:硕士
专业:通信与信息系统
指导教师:宋健
20070520
摘要由于的飞速发展,网络用户数目的增长,多媒体网络应用日益广泛,网络流量呈爆炸式的增长趋势。若要想继续提供较好的服务,要求核心路由器每秒能转发几百万个以上的分组,快速路由查找技术成为路由器报文转发的瓶颈。因此如何实现高速路由表的查找和更新是研究的难点。同时随着技术的逐步成熟和推广,也进一步要求提升路由查找的性能。文章在通过对近年来提出的各种路由查找方法进行详细阐述基础上,对各种算法的性能以及对的适应性进行了分析,结果发现数据结构是实现高速路由查找和报文转发的关键,且算法具有易于与硬件结合的特点,因此提出基于的最长前缀的查找算法。该算法中某些节点包含多条路由信息,减少了树的节点数目。这样大大减少了存储空间。考虑到当前路由表中前缀分布的特点,改进后的算法降低了树的高度。同时,该算法能够应用于网络。尤其适于当前快速变化的更新要求。总之,该算法不仅保障了路由表的快速查找,同时在执行更新操作时,不需要重新构建路由表。这种算法用到同样收到很好大效果,因此,它可以兼顾/网络。最后,作者总结全文,综合了作者在该课题研究中的主要成果,并且提出了需要进一步研究和讨论的问题。关键词:路由查找;最长前缀匹配;树硕士学位论文
;.瓸......∞..,...;Ⅱ
插图索引基本报头与报头的比较⋯⋯⋯⋯图路由器的体系结构⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图五类地址比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.图线性存储⋯图二进制结构⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图路径压缩的树的结点结构⋯⋯⋯⋯⋯⋯图路径压缩结构⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图步宽为亩喾种鹘峁埂图表的籺峁埂表实例⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图基于前缀长度的二分查找结构图⋯⋯⋯⋯⋯.图白憾杂Φ牡刂非渫肌图删除结点的实例图图结点结构⋯⋯⋯图插入算法举例⋯硕士学位论文⋯⋯⋯⋯⋯⋯。⋯⋯⋯⋯⋯⋯..⋯⋯⋯⋯⋯⋯⋯.⋯⋯⋯⋯..
附表索引基于吨的路卣壹找篝法研究表查询速度的要求⋯⋯⋯⋯.表前缀表表算法复杂度列表⋯⋯.表前缀长度分布统计表.
跫,奇作者签名:畄、拐日期:砷年占月户日【冢菏年律袱,学位论文原创性声明学位论文版权使用授权书兰州理工大学日期:~印年厂月少日本人郑重声明:所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外,本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体,均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。本学位论文作者完全了解学校有关保留、使用学位论文的规定,同意学校保留并向国家有关部门或机构送交论文的复印件和电子版,允许论文被查阅和借阅。本人授权兰州理工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存和汇编本学位沦文。本学位论文属于⒈C芸冢年解密后适用本授权书。作者签名:导师签名:¨』虹方框内打“√”⒉槐B蒵闭。
第滦髀研究背景近年来,随着的迅速增长,要求唯一地址的无线设备的激增,地址呈现枯竭趋势。地址为位长,经常以隽轿皇剖直硎荆渤3R个至涞氖直硎荆旨湟孕∈慵涓簟C扛鯥骰刂钒讲糠郑簕网络地址,主机地址M绲刂罚糜谥赋龈弥骰粲谀囊桓鐾属于同一个网络的主机使用同样的网络地址恢骰刂罚ㄒ坏囟ㄒ辶送缟系闹骰这种安排一方面是协议的长处所在,另一方面也导致了地址危机的产生。采用了一牡刂方峁梗獯永砺凵辖部梢蕴峁┙诘闹骰量,但实际上所能分配的地址远远小于该数目。这种地址配置的低效率,主要是由于地址以、壤啾鸾腥宋;帧T贗姆⒄钩跗冢由于对其发展速度估计不足,都以为地址空间将会一直是非常宽裕的,在分配时,嗟刂分挥个,用于那些最大的实体,如政府机关,因为它们连接着最多的主机:理论上最多可达一千六百万台。嗟刂反笤觯糜大型机构,如大学和大公司,理论上可支持超过个公司、一所大学就能获得一个嗷駼类地址。嗤绯桨偻蚋觯个网络上的主机数量不超过觯糜谑褂肐绲钠渌埂8〉墓荆某些只有几台主机,它们对于嗟刂返氖褂眯屎艿停欢笮突乖谘罢褺类地址时却发现越来越难;那些幸运地获得嗟刂返纳偈竞苌倌芄桓咝地使用它们的一千六百万个主机地纰。同时由于历史的原因,美国一些大学和公司占用了大量的地址,如康柏公司就有鯝类地址,麻省理工大学、斯坦福大学都有嗟刂贰6刂沟甑祝夜舐絀刂纷苁鑫觯簿褪撬得鲋泄酥荒芊窒硪桓龅刂罚此形成鲜明对比的是,美均每个美国人享有龅刂贰S纱瞬慕峁牵环矫姹徽加玫地址大量空置,另一方面是在互联网快速发展的国家地址紧缺。据官方预测,根据目前使