ip包分类算法研究

《ip包分类算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、i玲磊蘼．雒嘎芸懑硕士学位论文余磊邓亚平专t世：计算机应用技术7S"，：臻分类号密级公开重庆邮电大学硕士学位论文论文题目IP包分类算法研究英文题目ResearchonIPPacketClassificationAlgorithm硕士研究生金磊指导教师巫垩垩丝丝学科专业进关扭应田拉本论文提交日期2QQ2生§且论文答辩日期2Q皿生‘且2且论文评阅人答辩委员会主席李祖枢教授重庆大学2007年5月30日重庆邮电大学硕士论文摘要网络新业务的不断出现，对网络传输速度提出了越来越高的要求。为适应这些新变化，ISP(InteractServiceProvider)一方面必须升级因

2、特网骨干网络的速度，一方面必须筹划新的有差别的网络服务，以满足不同用户的需要。由于光纤技术和DWDM(DenseWavelength-DivisionMultiplexing)技术的发展使得链路的速率不再成为瓶颈，而路由器作为连接链路的节点，其性能会成为主要瓶颈。高速路由器要求包分类装置具有线速度的吞吐能力，使得包分类的设计具有很高的难度，成为路由器处理流程中最大的瓶颈之一，并且随着口网络应用领域的不断扩展，要求包分类算法对规则维数、规则数量和每维的宽度可扩展能力强，这也加剧了包分类算法设计的难度，成为扩宽11'(Int豇'nctProtoc01)网络应用的障碍。

3、口包分类是路由器根据口包的多个域，从分类器数据库中匹配每个输入包，确定包转发规则的技术。分类器为实现因特网新业务提供了统一的方式，包分类是因特网提供一切有差别服务和其他新业务的基础，高速包分类问题是具有重要现实意义和理论价值的研究课题。路由器不仅要完成按照口包头目的地址转发口包的任务，同时也要满足能区分不同的数据流的任务。一维P包分类用于处理前一个任务，多维Ⅲ包分类用于处理后一个任务。口包分类算法根据口包头地源地址、P目的地址、源端口号、目的端口和协议五个域进行分类，把不同的包归为不同的流，以便为不同的流提供有差别的服务。本文首先介绍了口包分类算法的应用背景，然后

4、给出了m包分类问题的详尽数学描述。对现有的各种口包分类算法进行了详细的分析，并对各种算法的查找性能和存储空间需求进行了分析比较。在此基础上，针对AQT(Area-basedQuadTree)算法提出了改进算法。为了使原有AQT算法能够应用于五维的口包分类，使用无冲突哈希函数处理源端口号、目的端口和协议域，提出了一种新的口包分类算法NCHAQT(Non-CollisionHashArea-basedQIIadTree)。详细地给出了该算法的基本思想、预处理过程、包匹配过程，并对规则优先权给出了明确的定义。经理论分析与仿真实验证明，该算法是一个综合性能较高的算法。关键

5、词：m包分类，无冲突哈希，规则库，匹配，复杂度重庆邮电大学硕士论文AbstractWiththedevelopmentofnewnetworktta伍c，itisurgenttoacceleratethespeedofthetransmissionofthenetwork．Inordertoadapttothenewsituation,InternetServicePm“dersOsP)needsnotonlytoimprovethespeedofthebackbonenetwork,butalsoprovidesn绷differentiatednetworkse

6、rvicesthatcallmeetdemandsofthe．differentclients．Thelinkspeedhasn'tbeenperformancebottleneckb∞auseofimprovinginfiberopticsandDenseWavelength-DivisionMultiplexing(DWDM)，butInternetProtocol(口)touterscallbemainperformancebottleneckbecauseofrequiringmanycomplexoperationssuchasfastpacketcla

7、ssification．m曲-speedrouterrequiresthepacketclassificationequipmenttop麒瑚spacketsinwire-speed．Thus，itisveryhardtodesignpacketclassificationalgorithmsandithasbecomeabigbottleneckoftheactionsinmuters．Withtheincreasingdevelopmentofthenetworkapplication，IPpacketclassificationalgorithmsmusth

8、avest