基于降维的ipv6包分类算法的设计与实现

《基于降维的ipv6包分类算法的设计与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、密级：保密期限：工程硕士研究生譬学位论文题目：基王隆维趁兰＆受鱼佥娄篡洼数逡盐皇塞盟学号：Q墨2986姓名：鱼匾差专业：筮鲑王程导师：呈芒学院：筮鲑堂院2010年4月独创性(或创新性)声明本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。申请学位论文与资料若有不实之

2、处，本人承担一切相关责任。／入，k，本人签名：缘!!!!蓉．日期：兰皇!Q!!厶：兰!关于论文使用授权的说明本人完全了解北京邮电大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编学位论文。本学位论文属于保密论文，在一年解密后适用本授权书。本学位论文不属于保密范围，适用本授权书。本人签名：导师签名：日期：丝丝：竺：!j基

3、于降维的IPv6包分类算法的设计与实现摘要包分类是下一代因特网网络设备(如MPLS路由器、防火墙、VoIP网关、VPN网关等)和新型网络服务(如QoS服务、包安全过滤、网络地址转换、流量记帐、流量限制服务等)实现的关键技术。研究有效地包分类算法及其实现技术是目前网络技术领域的热门课题。数据包分类就是根据口数据包从包头中取出相关的域，对其进行分类，在规则集中进行查找，然后返回与该数据包相匹配的优先级最高的规则。之后依据这些规则将包归入不同的数据流中，最后根据不同的服务对不同数据流中的包进行相关联的操作，如转发包，丢弃包等。随着互联网

4、的迅速发展，口v6将成为下一代互联网体系结构的核心协议。现有的m网络朝着口V6的方向发展，各种网络服务也将转移到口v6上运行。IPv6具有的很多新特性，如Pv6基本报头更简洁、扩展性更好，口v6能够更好地支持即插即用、服务质量、移动性等。但是，口v6并没有改变路由器数据平面的基本功能一路由查找和报文分类。mv6也给报文分类问题提出了新的挑战。IPv6定义了流的概念，通过采用流标签提供了一种更加高效地处理数据分组流的机制，该机制对于实时应用尤其有用。根据RFC3697的定义，路由器可以使用源口地址、目的P地址和流标签的三元组来标识一

5、个特定的流。因此，我们可以利用流标签字段简化IPv6报文分类问题。本文提出了一种基于流标签的疋v6包分类算法一降维排序二叉树算法。本算法使用三元组(源IP地址、目的口地址、流标签)代替传统的五元组(源IP地址、目的口地址、源端口、目的端口、协议)来实现IPv6报文分类，以达到简化报文分类的目的。核心思想是对源口、目的P进行降维处理后，再用排序二叉树组织复合口，通过复合口与流标签来进行分类。排序二叉树是一种利用类字典序方法组织数据的二叉树。与一般的二叉查找树不同，其不包含任何内部空节点，可以达到较好的空间性能。当前缀嵌套关系较少，回

6、溯现象较少发生时也能保证较好的时间性能。本文首先介绍了包分类算法产生的背景和应用、经典的包分类算法的基本原理和特点以及IPv6流标签的定义和相关规定；接着讨论了基于流标签的包分类算法与传统包分类算法的区别及其优势。然后重点描述排序二叉树的排序和建树规则及其搜索步骤，并在此基础上介绍降维排序二叉树算法的原理、实现及性能分析，为报文分类的进一步研究和算法设计提供一定根据和思路。关键词包分类IPv6流标签算法降维排序二叉树一’■’【沪THEDESIGNANDREALIZATIoNOFPACKETCLASSIFICATIoNBASEDoN

7、FLOWLABELINIPV6ABSTRACTPacketclassificationisthekeytechnologiesfortheimplementationofnext-generationInternetnetworkequipments(includingMPLSrouter,firewall，VPNgateway,VOIDgateways，etc．)andnewnetworkservices(includingQoSservices，securityfiltering,networkaddresstranslati

8、on,trafficaccounting,trafficrestrictions，etc．)Researchonefficientpacketclassificationalgorithmanditsimplementationisahotrese