基于bloom滤波器路由表查找算法的性能研究论文

《基于bloom滤波器路由表查找算法的性能研究论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Y7GS318学#n类—二曼_三岜一井娄号—卫堕堕里L一单＆R日—卫坐望自g～萄童翕乏学虎硕士研究生学位论文研究生指导教师学科专业研究方向申请学位级别张瑞王文鼐副教授通信与信息系统网络技术与应用二00五年四月堕室些生兰堕堡主堡兰．—————————————————————————i塑里摘要随着hnemet在世界范围内的普及和应用，对高速率和高带宽的网络需求越来越迫切。网络的速度已经从M比特每秒提高到G比特每秒，甚至在未来的几年T比特每秒将可能成为主流。由于hltemet的速度不断提高、网络流量不断增加和网络规模不断扩大，对构成Intemet的

2、设备提出了更高的要求。现有的网络主要是由路由器和物理连线(光纤或光网络)组成。光传输技术上的突破已经可以保证对线路速度的要求，使得高速路由器成为制约htcmet性能的主要瓶颈之一。影响路由器性能的主要因素包括：路由查找，交换织构和输入，输出调度。随着研究的不断深入。人们研究并提出了一些性能良好的方案来解决交换和调度问题。但是，路由查找速度依然是进一步提高路由器性能的关键要素。本文针对一种新的路由查找算法，研究其优化设计问题。该算法基于一种随机化的数据结构B100m滤波器，它可以简洁地表示元素集合并能实现快速查找。新查找算法中，将路由表中的前缀

3、按照长度分为3类，其中两个使用B100m滤波器分别存储和查找，实现对前缀长度匹配的并行计算，提高前缀长度匹配计算速率。配合对固定位长hash表的后续查找，可以快速得到相关路由信息。针对实际流量分布的临时集中性特点，在后续查找中引入了缓存机制以减小B100m滤波器的误检概率，改进算法的性能。在研究过程中使用ac++语言对Bloom滤波器、后续hash表查找以及加入缓存以后的算法性能改进进行仿真研究。仿真计算的数据源使用了实际BGP数据模拟产生具有临时集中性的业务流。通过与理论结果相对比，验证了仿真计算程序的可信度。对新算法的仿真实验结果显示，引

4、入缓存机制后，能够在相同的参数条件下降低误检概率，将系统的性能提高50％。针对实际网络拓扑动态变化特点，本文进一步研究了路由算法的更新问题以及制约算法性能的主要因素，提出了路由更新的算法方案并给出了性能分析结果。堕塞唑生兰堕塑：!堡壅————————————————————些!塑生AbstractA10ngwiththeworld—widepm乒essingaIldrapidapplicationOfIntemet，ahi曲一speedandhi庐山andwidmn咖orkwillbeingreatdemaIld·Thene帆orkspeed

5、hasalreadybecnupgradedfbmmegabitstogigabitspersecond．Itmi曲tbeup乒adedtoterabitsDersecondint11enear鼬ure．Owingtotherapidgrowthofthespeedofne咐orkinterfaces，mevolumeoftramcaIldlhesizeofmutingtable，thet11rou曲puta11dcapacityofnetworkcomponentsneedtobeupFadewithit．Thetypicalcompone

6、ntsincludeIProutersandphysicaltraIlsmissionlinks．Thebreakthrou曲inopticaltransmissiontechniqueshasguaranteedthelinkspeed，t}mshigh_speedrouterbecomethemainbottleneckthatresmcttheperformallcesofIntemet．Thecriticalissuesthatinnuencemerouterperfb玎naIlceinclude：routingtablelookup

7、，switchfabrica11dI／0scheduling．SomegoodsolutionsforswitchingandschedulinghavebeendevelOped．HoweveLrouting100kupalgoritlllllthatimproVestherouting100kupspeedisstillabottleneckofmeperfbnTlaIlceofmutetThisthesisintrOducesanewroutingtableloOkupalgoritmbasedonarandomizeddatastmc

8、ture，Bloomfilter’w11ichcancompactlyrepresentaseta11dsupportfastsearching．Theroutin