（计算机科学与技术专业论文）基于流标签的ipv6包分类算法研究.pdf

独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列 的内容以外，论文中不包含其他人已经发表或撰写过的研究成果，也 不包含为获得北京邮电大学或其他教育机构的学位或证书而使用过 的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中 作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：l 拭l l 、踟j日期：矽c 纵乏似 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文 的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属北 京邮电大学。学校有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许学位论文被查阅和借阅；学校可以公布学位论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编 学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权 书。 、-h-tt i l 声 仑 北京邮电人学硕士论文摘要 基于流标签的i p v 6 包分类算法研究 摘要 由于i n t e r n e t 的快速发展，i p v 4 地址稀缺的问题越来越严重。i p v 6 由此被引入以解决此问题。到目前为止，i p v 6 已经在大规则模的测试 之中，在欧洲、亚洲和北美也得到一些初期的部署。 但是，由于协议本身的改变，特别是地址长度的极大加长，而i p v 4 和i p v 6 之间不是平滑的升级，这就给i p 包分类算法带来一些不可避 免的挑战。比如：传统包分类算法对查找关键字的长度都是比较敏感 的。如果直接把现有的i p v 4 包分类算法升级到i p v 6 的版本，性能可 能严重的下降。这就意味着包分类算法应该跟随i p v 6 的发展而更新 换代。同时，i p v 6 包分类算法目前还处于起步阶段，各自算法之间的 比较需要有一个客观的测试用例，也就是i p v 6 的规则集作评价标准， 但是因为i p v 6 商业化进程缓慢而导致规则集缺乏。 本论文的工作主要分两部分。首先，结合i p v 4 与i p v 6 之间的联 系，从i p v 4 中的分类器基准库( c l a s s b e n c h ) 借鉴经验，提出i p v 6 中的c l a s s b e n c h v 6 。其次，考虑到i p v 6 包分类算法可能由于r f c 3 6 9 7 中对流定义的改变而作出调整，而从i p v 4 中的五元组，变成i p v 6 中 的三元组，这样势必对i p v 6 包分类算法造成影响。因此，本论文根 北京邮电大学硕士论文 摘要 据r f c 3 6 9 7 的规定，提出一种基于流标签、源l p 地址、目的i p 地 址的i p v 6 包分类算法。 关键字i p v 6 包分类c l a s s b e n c h 规则集流标签 u 一 ， t 北京邮电大学硕+ 论文 a b s t r a ( 了r r e s e a r c h0 ni p v 6p a c k e tc l a ss i f i c a t l 0 n a l g o r i t h mb a s e d0 nf l o wl a b e l a bs t r a c t a st h er a p i dd e v e l o p m e n to fi n t e m e t ，i p v 4a d d r e s ss c a r c i t yi s g e t t i n gw o r s e t h i sh a sb e e nt h ei n t r o d u c t i o no fi p v 6i no r d e rt os o l v e t h i sp r o b l e m s of a r , i p v 6h a sb e e ni nt h el a r g es c a l et e s t ，a n di nt h ei n i t i a l d e p l o y m e n ti ne u r o p e ，a s i aa n dn o r t h a m e r i c a h o w e v e r , d u et ot h ec h a n g e so ft h ep r o t o c o l si t s e l f , e s p e c i a l l yt h e i n c r e a s e dl e n g t ho ft h ea d d r e s s ，t h eu p g r a d i n gb e t w e e ni p v 4a n di p v 6a r e n o ts m o o t h l y t h e r e f o r e ，i tw i l lb r i n gs o m ei n e v i t a b l ec h a l l e n g e st ot h ei p p a c k e tc l a s s i f i c a t i o na l g o r i t h m s ；f o re x a m p l e ，t h et r a d i t i o n a lp a c k e t c l a s s if i c a t i o n a l g o r i t h m s a r es e n s i t i v et ot h e l e n g t ho ft h e s e a r c h k e y w o r d s i fw ed i r e c t l yu p g r a d et h ee x i s t i n gi p v 4p a c k e tc l a s s i f i c a t i o n a l g o r i t h mt os u p p o r ti p v 6 ，t h ep e r f o r m a n c ec o u l ds e r i o u s l yd e c l i n e t h i s m e a n st h a t p a c k e t c l a s s i f i c a t i o n a l g o r i t h m s s h o u l df o l l o wt h e d e v e l o p m e n to f i p v 6r e p l a c e m e n t m e a n w h i l e ，i p v 6p a c k e tc l a s s i f i c a t i o n a l g o r i t h mi s s t i l li ni t si n f a n c ya n dt h ec o m p a r i s o nb e t w e e na l g o r i t h m s r e q u i r eo b j e c t i v et e s tc r i t e r i a ，t h a ti s ，t h es e to f i p v 6r u l e s ，h o w e v e r , t h e i i ! 北京邮电人学硕十论文 a b s t r a c t s l o wp r o c e s so fc o m m e r c i a l i z a t i o no fi p v 6l e a dt oal a c ko ft h es e to f r u l e s t h ew o r ki nt h i sp a p e rc a nb ed i v i d e di n t ot w op a i r t s f i r s t l y , f r o m t h ec o m p a r i s o nb e t w e e ni p v 4a n di p v 6 ，a n dl e a r n tf r o mt h ec l a s s b e n c h o fi p v 4 ，c l a s s b e n c h v 6f o ri p v 6i sp r o p o s e d a n dt h e n ，c o n s i d e r i n gt h e f a c tt h a ti p v 6 p a c k e tc l a s s i f i c a t i o na l g o r i t h m sm a yc h a n g ed u et o r f c 3 6 9 7d e f i n i t i o n ，i nw h i c ht h ef i v e t u p l ei ni p v 4m a y c h a n g ei n t o t r i p l e si ni p v 6 ，a n di tw i l la f f e c tt h ed e s i g no f i p v 6p a c k e tc l a s s i f i c a t i o n a l g o r i t h m s t h e r e f o r e ，t h i sp a p e rp r o p o s e sai p v 6p a c k e tc l a s s i f i c a t i o n a l g o r i t h m ，w h i c hi sb a s e do nf l o wl a b e l ，t h es o u r c ei pa d d r e s s ，a n d d e s t i n a t i o ni pa d d r e s s k e yw o r d s i p v 6 ，p a c k e tc l a s s i f i c a t i o n ，c l a s s b e n c h ，r u l e s ， f l o wl a b e l i v i 冷 i 北京邮电大学硕士论文目录 目录 第一章前言1 1 1 课题背景1 1 2 研究内容及创新点2 1 3 国内外相关研究现状3 1 4 论文章节安排4 第二章c l a s s b e n c h v 4 简介5 2 1 国内外关于i p v 4 分类器特征的研究5 2 2i p v 4 规则集中与地址相关特征的研究6 2 2 1 地址前缀长度的分布6 2 2 2 地址值分布特性7 2 2 3 总结9 第三章i p v 4 的包分类算法简介。1 1 3 1 多维包分类算法的定义11 3 2i p v 4 下的多维包分类算法l l 3 2 1 穷举遍历算法1 2 3 2 2 决策树算法l4 3 2 3 基于分解思想的算法1 9 3 2 4 基于元组空间的分类算法2 3 第四章c l a s s b e n c h v 6 的研究2 6 4 1 总体思想2 6 4 2i p v 4 与i p v 6 规则集的关系2 7 4 3 地址前缀结构特征2 8 4 3 1i p v 6 地址结构2 8 4 3 2i p v 4 和i p v 6 地址分配策略。2 8 4 3 3i p v 6 规则集地址前缀的特征2 9 4 4 评估与实验3l 第五章基于流标签的i p v 6 包分类算法研究3 3 5 1i p v 6 流标签介绍3 3 5 2 基于流标签的算法提出3 3 5 3 算法的实现3 4 v 北京邮电大学硕士论文目录 5 3 1 独立规则集的定义3 4 5 3 2 独立规则集组( g i ) 的数据结构3 6 5 3 3 标记和重排序3 6 5 4 f l 决策树3 7 5 3 5 查找过程3 8 5 3 6 更新3 9 5 4 算法性能分析4 1 5 4 1 性能评价指标。4 1 5 4 2 时间复杂度分析4 2 5 4 3 空间复杂度分析4 2 5 4 4 结果比较4 3 第六章总结与展望4 4 参考文献4 6 致谢4 8 攻读学位期间发表的学术论文目录4 9 v i i 北京邮电大学硕士论文第一章前言 1 1 课题背景 第一章前言 现有的互联网主要是在i p v 4 协议的基础上运行的。i p v 4 获得了巨大的成功， i p 网络发展惊人，使得i p 网的基础设施平均每1 2 年要全面升级一次，其骨干 网带宽的增加速率为每乱9 个月翻一番【l 】。随着i p 业务的迅速增长，i p 网络上 应用的不断增加，原有的i p 网越来越显得力不从心。个人电脑市场的急剧扩大、 还有个人移动计算设备的上网、网上娱乐服务的增加、多媒体数据流的加入、以 及出于安全性等方面的需求都迫切要求新一代p 协议的出现。 i p v 6 t 2 】最初的提出是因为随着互联网的迅速发展，p v 4 定义的有限地址空间 将被耗尽，地址空间的不足必将影响互联网的迸一步发展。i p v 4 采用3 2 位地址 长度，而i p v 6 采用1 2 8 位地址长度，几乎可以不受限制地提供地址。在i p v 6 的 设计过程中除了一劳永逸地解决地址短缺问题以外，还考虑了在i p v 4 中解决不 好的其它问题。i p v 6 的主要优势体现在以下几方面：扩大地址空间、提高网络 的整体吞吐量、改善服务质量( q d s ) 、安全性有更好的保证、支持即插即用和 移动性、更好实现多播功能p j 。 到目前为止，i p v 6 已经在大规则模的测试之中，在欧洲、亚洲和北美也得 到一些初期的部署。 多维包分类算法一直是路由器相关技术中的瓶颈所在，但是它又是多种网络 增值业务比如防火墙，区分服务，q o s 和a c l 等等的基础。包分类算法的好坏 直接影响着这些增值业务的开展。 但是，由于协议本身的改变，特别是地址长度的极大加长，而i p v 4 和i p v 6 之间不是平滑的升级，这就给i p 包分类算法带来一些不可避免的挑战。比如： 传统包分类算法对查找关键字的长度较为敏感。如果直接把现有的i p v 4 包分类 算法升级到i p v 6 的版本，性能就可能严重的下降。随着i p v 6 网络商业化推广， 研究一种快速的i p v 6 包分类算法已经迫在眉睫。而根据r f c 3 6 9 7 【4 】中对i p v 6 流 标识方式的重新定义，基于流标签的三维包分类算法有可能取代于目前i p v 4 所 用的五维包分类算法。 现实中规则集的特征会对包分类算法的性能产生很大影响。分析现有的i p v 4 规则集特征可以得到很多有助于提高包分类算法性能的特性。但是由于安全和保 北京邮电大学硕七论文第一章前言 密等等的原因，一般研究人员很难接触到现实中的大型规则集，另外，i p v 6 还 是处于初始应用阶段。只有一小部分的地址块被分配使用。因此，按现阶段的情 况，是不足以反映未来i p v 6 规则集发展特征的。 对于i p v 4 的包分类规则集，d e t a y l o r 已经发展了一套叫c l a s s b e n c h 【5 】的 i p v 4 包分类算法性能评估工具。作者深入观察研究了现实中的一些i p v 4 规则集， 并从中抽象出一部分i p v 4 的规则集特征，在此基础之上提炼出有限的几个参数 以反应规则集的结构特征。同时也提供了1 2 个参数文件，这些参数文件包括了 不同类型的规则集的特征。比如：a c l ( 接纳控制列表) f w ( 防火墙) 等。 尽管还没有公开可使用的i p v 6 规则集，但我们相信很多在i p v 4 规则集中出 现特征将会出现在i p v 6 的规则集中。原因主要有四个方面：分配策略的延续， 应用类型保持不变，拓扑结构和i n t e m e t 模式的延续。这同时也是影响规则集形 式的四个关键点。首先i p v 6 地址的分配策略跟i p v 4 的分配策略相类似，尽管在 细节方面会有所差别。其次，应用类型比如a c l 、f w 、流量工程等等在i p v 6 中都会出现，并且形式相同。第三，网络拓扑会影响到规则集的结构，但是网络 拓扑不会随着i p v 4 到i p v 6 的迁移而发生大的改变。最后，i n t e m e t 的演进也会 以相同的方式进行，i p 地址前缀提供者和终端用户的商业关系不会改变。因此， 我们可以使用【5 】中提供的参数文件来预测i p v 6 规则集的特征，从而发展出i p v 6 的c l a s s b e n c h v 6 。 一 1 2 研究内容及创新点 本课题主要研究内容有两个： 一是根据现有的i p v 6 发展情况，结合i p v 4 国内外研究人员对i p v 4 规则集 特征的研究，深入探讨未来i p v 6 规则集的特征，整理出一套与i p v 4 下的 c l a s s b e n c h 相对应的i p v 6 下的c l a s s b e n c h v 6 。 i p v 6 由于商业应用进程一直很慢，所以并没有出现完全可用的规则集。这 就给i p v 6 包分类算法的研究带来了没有标准化的测试用例等问题，各学者和研 究人员都根据自己的算法的特征来设计规则集，导致各个i p v 6 算法相互进行比 较困难。我们尽可能的尝试搜集相关资料，结合i p v 4 中c l a s s b e n c h 的研究成果， 发展一套c l a s s b e n c h v 6 ，目的是提供一套尽量符合实际需求的i p v 6 包分类算法 的测试用例。但是由于规则集的获取涉及安全和保密问题，且由于i p v 6 还没大 规模商业化应用，给这些问题的研究带来很多的困难。 二是根据r f c 3 6 9 7 中关于i p v 6 流定义的新规定，研究一种基于流标签、源 地址和目的地址的三维的i p v 6 包分类算法。包分类算法是多种网络增值业务的 基础。 2 北京邮电大学硕十论文 第一章前言 多维包分类算法一直是路由器相关技术中的瓶颈所在，但是它又是多种网络 增值业务比如防火墙、区分服务、q o s 和a c l 等等的基础。包分类算法的好坏 直接影响着这些增值业务的开展。在i p v 4 环境下，算法需要匹配的五元组是源 i p 地址、目的i p 地址、源端口号、目的端口号和协议类型，五元加起来一共是 1 0 4 比特位，如何能让算法在有限的硬件资源下，尽快匹配上规则集是算法研究 的目的。i p v 4 发展成熟，成果较多；但是i p v 6 环境下，单单一个i p 地址的位数 就是1 2 8 比特位了，这比i p v 4 下的五元总量还要多，因此它不可避免的要更消 耗硬件资源。但是网络的发展必然是更高速和更多的接入设备，因此i p v 6 下的 包分类算法更显得重要。值得庆幸的是，r f c 3 6 9 7 规定i p v 6 下的流标识方式定 义由i p v 4 的五元变成了三元组，这固然是减少了算法的复杂度，但是i p v 6 三元 所占总比特位数的极大增加，也给算法带来了更大的挑战。而且i p v 6 下的流标 签是随机生成，存活时间不固定，因此i p v 6 的规则集可能更趋向于变化频繁， 这也为算法增加了困难。本课题就是在这样的约束条件下发展出一套解决上述难 题的算法。由于算法难度大，可参考资料少，所以研究也碰到了很大的困难。 1 3 国内外相关研究现状 网络带宽不断的快速发展一直推动着相关路由技术的发展，路由技术已经在 体系结构和内部的交换结构方面取得了较大的突破，但是相关的路由查找算法以 及为了适应更多的增值应用的i p 包分类算法一直都是路由器的瓶颈所在。经过 多年许多国内外专家学者的研究，在i p v 4 环境下的包分类算法都有了很成熟的 理论创新和性能的提升，性能和评测都有了权威的标准和一套自成体系的工具。 但是随着i p v 6 的引入，包头格式的改变，地址长度的加长以及流定义的更新， 给包分类领域带来了巨大的挑战，但同时也意味着巨大的机遇，挑战与机遇并存， 促进着包分类算法更新换代。 由于i p v 4 应用的时间较长，研究人员投入了很大的精力进行理论和实践的 创新，先后出现了一大批高水平的论文，包括g r i d o f - t r e e 【6 】、r f c 【7 j 、h i c u t s 心j 、 b v l 9 1 、a b v 1 0 】等等。但是这些在i p v 4 下运行良好的算法，如果不经理论修改 直接改造地址部分在i p v 6 下运用，结果无法令人满意，因为这些算法大多都是 根据i p v 4 的特点进行研究得出的，而i p v 6 地址有着跟i p v 4 不一样的特点，结 果不尽如人意也是可以预料得到的。 而近年来计算机硬件水平也有了相当大的提高，计算速度快速增加，而存储 单位价格也快速下降，人们越来越多的希望利用硬件在处理能力方面的优势来提 高包分类算法的性能。而实践也证明了硬件的处理能力相对于软件有着明显的优 势。由此，硬件厂商相应的推出了用于分类算法的硬件产品，比如t c a m 。在 北京邮电人学硕+ 论文 第一章前言 此硬件基础上，学者和研究人员也提出了一些相关的算法，实际性能也相当良好， 但是虽然t c a m 有着天然的速度优势，但也同时有着致命的缺点，这就是价格 昂贵，能耗巨大，这使得即使在i p v 4 环境下也仅用于高端路由器。发展到i p v 6 ， 地址长度的成倍增加，使得t c a m 的缺点更为明显。可以说t c a m 对i p v 6 包 分类算法作用有限。 至于针对i p v 6 环境下的包分类算法，由于i p v 6 的商业化进程一直以来都比 较缓慢，甚至于之前对于是否进行i p v 6 的推进也存在着相当大的争议，因此投 入到i p v 6 包分类算法的研究人员也就相对较少，而且时间也不充分，成果明显 不如i p v 4 环境。同时，r f c 3 6 9 7 提出了i p v 6 流标识方式的定义及识别方式的改 变，导致了i p v 4 与i p v 6 包分类算法有了更多的区别，目前符合r f c 3 6 9 7 新的 流识别定义规定的算法寥寥可数。 另一方面，p v 4 环境下包分类算法有着自己的一套规则生成和包头生成工 具c l a s s b e n c h ，此工具是研究人员分析了大量的i p v 4 环境下正常使用的规则集 后得出的辅助工具。此工具的研究和发布，对评价各研究人员的i p v 4 包分类算 法的成果提出了标准化的测试用例，这就反过来推动着i p v 4 包分类算法的进一 步发展。 而i p v 6 下现阶段的试验环境都是不作限制的使用为多，由此缺乏规则集的 研究，没有了客观的测试用例，使得i p v 6 的包分类算法好坏标准不一，因此各 研究人员也希望有i p v 6 环境下的c l a s s b e n c h 。 随着i p v 6 发展进程的加快，互联网服务提供商的增值业务的增多，研究高 效的、用软件实现的针对i p v 6 新流标识方式定义的包分类算法显得十分重要而 且时间紧迫。 1 4 论文章节安排 本论文主要论述i p v 6 环境下与包分类算法密切相关的分类器特征及其实 现，以及基于流标签的分类算法及其实现，将主要分为四部分进行论述： 第一部分包括第一章，论述课题的背景、必要性、创新点。 第二部分包括第二章和第三章，分析i p v 4 下与包分类算法相关的分类及和 包分类算法本身及其用到的关键技术。 第三部分包括第四章和第五章，详细介绍了适用于i p v 6 的分类器原理及其 实现和基于流标签的i p v 6 包分类算法的实现和性能分析。 第四部分包括第六章，对本课题进行总结。 4 北京邮电大学硕士论文第二章c l s s s b e n c h v 4 简介 第二章c l a s s b e n c h v 4 简介 2 1 国内外关于i p v 4 分类器特征的研究 i p v 4c l a s s b e n c h 最早由d e t a y l o r 提出，在i p v 4 环境下对包分类算法的性 能评估方面得到了广泛的应用。c l a s s b e n c h 的设计思想是先从现实应用中采集一 些规则集，根据这些规则集抽取相关特征，在此基础上总结出一系列相关的参数 以反应规则集的结构特征，从而可以构造出与现实规则相似的仿真规则集，为研 究包分类算法提供了高层次的输入；同时支持产生包头数据功能，可以由用户自 定选项产生与生成规则集相对应的包头数据，便于检测对应的规则集。 所选择的参数是从现实的规则集中高度抽象出来的，因而极为重要。这些参 数可以分为两大类：地址前缀对和应用程序类型。如表一所示：这些参数全面的 描述了口v 4 规则集的特征。 表2 - 1c l a s s b e n c h 中的参数 地址前缀 长度的分布源和目的地址前缀长度值的分布 单支比例( o b p )在特定长度某一节点只有一个孩子的比例 s k e w对于由地址组成的单比特树，左右孩子权重的平衡性。 应用程序类型 p r o t协议号值的分布情况 p a r对源或者目的端口是任意值的情况描述 p e m对源或者目的端口是特定值的情况描述 目前，国内外研究人员得到了部分现实中使用的i p v 4 规则集后，他们各自 对这些规则集从地址角度、端口号角度、协议角度等等进行独立的分析研究，提 炼出各自的特征。这些特征从不同角度能够反映i p v 4 规则集的部分特点，以下 是对这些特点的总结： 1 不同的包分类算法所使用的规则集特点差异较大； 2 位于协议字段的协议号可能代表的协议种类相当有限，一般不会超过9 种 协议类型【5 j ； 3 从端口的角度来看，未指定的端口号的情况在规则集中普遍存在。例如： 一般a c l 的规则集中，源端口通常未指定，但是目的端口常指定一个固定值： 北京邮电大学硕士论文 第二章c l s s s b e n c h v 4 简介 4 大多数规则集中地址前缀长度都集中出现在有限种类的长度范围：0 、3 2 、 2 4 、2 3 、2 2 、1 6 【5 】： 5 未指定源地址或者目的地址的规则集在整个规则集中占较高比例，随着规 则集数目的增多，未指定源地址或者目的地址的规则集比例将下降。 2 2i p v 4 规则集中与地址相关特征的研究 在规则集中与地址相关的特征有两种：地址前缀长度分布和地址值分布。下 面将对这两种分布方式分别进行介绍。 2 2 1 地址前缀长度的分布 f w il m g t l ad i s t r i b u t i o n 0 p v 4 )a c l ik g l i ld i 曲诒u 删p 、啦 图2 - 1 规则集长度分布图 因为包分类算法在现实中的应用场景很多，所以规则集中地址前缀长度的分 稚就有可能相去甚远。从文件5 】中的f w l 和a c l l 提取源地址前缀长度的数据 可以得到图2 1 。尽管不同的规则集在地址前缀长度分布也存在差异，但从图中 能够清晰的看到源地址前缀长度分布集中在0 、3 2 、2 4 、2 2 、2 3 、1 6 。 图2 - 2i p v 4 下b g p 路由器地址长度分布 图2 2 反映了r o u t e - v i e w 项目里对现实世界中b g p 路由表( 2 8 0 7 2 0 0 7 ) 地 址前缀长度的分析数据的分析。b g p 路由表前缀长度的分布会受到地址分类策 略影响。 6 北京邮电大学硕+ 论文 第二章c l s s s b e n c h v 4 简介 从图2 1 和图2 2 可知，地址前缀长度除了o 和3 2 之外，其它的峰值在规 则集中和b g p 路由表中是一致的。这是因为在规则集中不会存在一个未被分配 的地址前缀长度，地址分配策略就能直接影响不同机构获得的地址。规则集另一 个显著的特点是有大量的前缀长度分布在o 和3 2 。原因是前缀长度为3 2 的规则 集要限定特定的终端主机的访问；而通常管理员会使用大量地址前缀长度为0 的规则集，一方面可以专门对某些应用进行限定而无需对其地址限制，另一方面 也可对本局域网内的机器不作任何的出去限定。但是这种情况在b g p 路由表上 是不会出现的。 2 2 2 地址值分布特性 地址值的分布可以用如图2 3 中所示的单比特树表示，树中的黑节点表示该 节点是一个地址前缀。图中右表是地址前缀，相应的a b c d e 都已经在图中表示 出来。因此，我们可以通过分析前缀的单比特树的特征来描述地址值特性分布。 馓0s i c 钾：1 馓q 5 虫e 霄：0 5 c b p ：o5s k e w ：0 5 0s k e 谚o 图2 3 由地址前缀组成的单比特树显示地址值分布 o b p 和s k e w 是两个重要参到5 1 ，它们能够反映由规则集中所有地址组成的 单比特树的特征和地址值的分布情况。 l 单支比例 o b p ，是指在一棵由规则集地址组成的单比特树中，某一层的节点中只有一 个孩子的节点数占该层中所有有孩子的节点( 包括有一个孩子和两个孩子的情 况) 的比例。例如在图2 3 在第一层，o b p 值为0 5 ，因为第一层有两个节点有 孩子节点f 和g ，且有一个节点f q 有一个孩子节点。第二层的o b p 值也同样为 o 5 ，因为第二层也有两个节点h 、i 有孩子节点，且仅有一个节点i 有一个孩子 节点。 我们分析文献【5 】中提供的所有规则集，发现o b p 的分布主要有两类：第一 种类型，如图2 - 4 所示，前2 4 层的o b p 值几乎都为1 。可以推测a c l l 和i p c 2 是在某一个机构的局域网内使用的地址块是2 4 ，因为在2 4 之前单比特树基本都 是单支，说明前缀只有一种。另一种情况是o b p 值在前面的几层中值相对较小， 7 北京邮电大学硕十论文第二章c ! s s s b e n c h v 4 简介 如图2 5 所示，可以推测a c l 3 、a c l 5 和f w 主要来自包含了地址前缀最初几 位不同的边缘路由器。 o b p ( t y p e1 ) - i p v 4 ( a c l 1 一s r c ) 1 2 1 1 自 吕：詈 0 4 ；0 2 0 1 2 l 0 8 0 6 o 4 o 2 o 滋i p v 4 ( i p c 2 _ s r c ) 13 579l 11 3l5l7l92 12 32 52 7 2 93 13 2 图2 4 i p v 4 0 b p 分布第一种类型 o b p ( t y p e 2 ) 一i p v 4 ( a c l 3 一s r c ) 莉删 i ! 兰三z ? i i1 31 5 i 一71 9 2 12 3 2 52 72 9 3 13 2 图2 5i p v 4o b p 分布第二种类型 由此可知o b p 分布主要受到两个因素的影响：规则集的应用场景和地址分 配策略和分配的进程。 当规则集应用于核心网边缘时( 比如一个大地理区域的边缘路由器，或者大 型的i s p ) ，则对应o b p 在地址前缀最初几层的比特值变化不一。因为越靠近 核心网的设备往往管理较大的地址块，而极少管理到终端用户的地址，从而导致 前缀频繁的变化。越靠近接入网时( 比如具体某个公司、机构或者小型i s p 的规 则集) ，则对应o b p 前面比特非常的整齐而后面比特数值变化不一，因为接入 网设备往往就管理着小的地址，甚至是部分具体的终端用户。 地址分配策略和进程的影响主要体现于地址使用得越是充分，o b p 值就越 小，因为此时更多的地址出现在规则集中，从而使得由地址组成的单比特树更加 接近一棵满二叉树。 2s k e w 在一棵由规则集地址组成的单比特树中，s k e w 用于描述某一层各节点左右 子树的权重比例关系的平均值。子树的权重是指在子树节点中包含的规则数量。 s k e w 值越大，则说明单比特树的地址组成分布的越平衡。 北京邮电大学硕十论文第二章c l s s s b e n c h v 4 简介 s k e w - l - 箍 式( 2 - 1 ) 小权重指的是左右子树中权重较小的一个，大权重则指的是左右子树中权重 较大的一个。仍以图2 3 为例，第一层中的f 节点其左子树有两个前缀值，右子 树则没有，所以s k e w 值为l ；同理可得g 节点的s k e w 值为o ，因此该层的总体 s k e w 值为平均值o 5 。 o b p 和s k e w 值虽然是两个不同的参数，但彼此有着内在的联系。通常平均 s k e w 值小的层可能有高的o b p 值，但也有例外的情况，如果所有节点都是只有 一个孩子，那么o b p 和s k e w 值都将为1 。图2 - 6 和图2 7 分别是f w l 与i p c 2 关于o b p 和s k e w 值的图，可以看到当o b p 值为1 时，s k e w 值为1 。当s k e w 小 于l 的时候，s k e w 值越大，o b p 的值越小。因为应用场景和地址分配策略和进 程不仅是影响o b p 分布的两大因素，s k e w 同样受到这两个因素的影响。 2 2 3 总结 。 f w ls k e wb r a n c h 一一 s k e w f w l l _ s r c 糍b r a n c h f w ls r c ： 7 8 9l o li1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 0 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 3 q 3 1 3 2 3 3 图2 - 6i p v 4 下o b p 与s k e w 之间的关系 i p c 2s k e wb r a n c h 一 一l s k e wi p c 2s r c 鞘b r a r l 虻hi p c 2s r c l | | l | 2 2 2 2 【2 4 2 1 记6 2 7 2 k 2 9 3 0 31 3 2 3 3 图2 7i p v 4 下o b p 与s k e w 之间的关系 本章主要介绍了与地址相关的两个主要问题地址前缀长度问题和地址 值问题，这对规则集的研究相当重要。地址的出现虽然只与地址提供者的分配策 略有关，但不同的应用场景又使得规则集的组成发生了的变化。这两个问题有着 9 ili，_-i 北京邮电大学硕士论文第二章c l s s s b c n c h v 4 简介 密切的关系： 一方面，地址前缀长度分布是由地址分配策略和进程决定的，除了0 和3 2 的地址外，在规则集中的地址前缀长度峰值与b g p 路由表上的地址前缀峰值是 一致的。 另一方面，地址值的分布又与分配策略及应用场景相关，因而在i p v 6 中应 用场景与i p v 4 应该是保持一致的。i p v 4 与i p v 6 的不同之处在于值分布特征和长 度分布特征会处于不同的地址位置上。 综上所述，尽管不同的规则集会呈现各自的特征，但地址分配策略和进程对 规则集的特征是影响最大的。因此研究i p v 4 和i p v 6 的地址分配策略和进程以及 i p v 4 和i p v 6 两者之间的内在联系非常重要，为合理预测未来i p v 6 规则集的特征 提供了重要而宝贵的参考价值。 l o 北京邮电大学硕七论文 第三章i p v 4 的包分类算法简介 第三章i p v 4 的包分类算法简介 3 1 多维包分类算法的定义 i n t e m e t 的发展对人们的生活产生了同趋深远的影响。i n t e r n e t 服务提供商也 趋于向终端用户提供更多的增值业务，比如说防火墙、决策路由、虚拟专网 ( v p n ) 、按流量计费和网络服务质量( q o s ) 等。为了提供这些增值服务，路 由器需要将不同的包按照不同的规则进行分类过滤。尽管分类过滤的功能可以在 l 2 l 3 l 4 中分别进行，但是最主要的还是在i p 层来进行，一个在对i p 包进行分 类过滤的算法就是叫i p 包分类算法。 一条过滤规则r 可用如下形式表示，( f l ，f 2 ，f 3 ，f k ) ，称为k 维规则。 这里f i 可以是一个前缀，也可以是一个范围，以位串表示。在i p 数据包中最常 用的字段是i p 目的地址字段、i p 源地址字段、协议类型字段、目的端口字段和 源端口字段。以过滤规则1 - - ( 1 1 8 2 2 6 宰，宰，t c p ，2 3 ，) 为例，它为流向子网1 1 8 2 2 6 ， 并且t c p 目的端口为2 3 的数据流定义了一条规则。在进行数据包和过滤规则的 匹配时，根据字段类型的不同，允许三种匹配方式：精确匹配、前缀匹配和范围 匹配。 3 2i p v 4 下的多维包分类算法 目前，i p v 4 包分类算法已经在学术界和工业界被充分地进行了研究。其中 主要能够分为成四类【i l 】，包括穷举遍历的算法、决策树的算法、分解并行的算法 和元组空间的算法。分布情况如图3 1 所示： 1 穷举遍历算法 这类算法就是查检所有规则集，选出一个最佳匹配的规则。主要代表有线性 查找和基于硬件的t c a m 。 2 决策树的算法 这类算法是根据规则集，构造出特定结构的决策树，用包中的相关域对决策 树进行遍历，从而找到最佳匹配的规则。树结构由于性能优良，在各个领域都得 到充分的研究，在包分类算法中也不例外，成果较多。主要有g r i d o f - t r i e s 、 e g t - p c 、h i c u t s 等等。 北京邮电大学硕士论文 第三章i p v 4 的包分类算法简介 3 分解并行的算法 随着计算机软硬件的发展，并行思想越来越多的得到应用。这类算法就是基 于并行思想而得出的。主要思想是将多维包分类问题分解为多个一维问题，在各 个维度上面独立而且并行的进行匹配，然后在此基础之上将结果归并，综合得到 最佳匹配的规则。主要算法包括r f c 、b v 和a b v 等。 4 元组的算法 这类算法的主要思想是根据特点规则，将较长的规则划分成较多的几个小组 合，然后对这些小组合进行查找匹配，以一次降低查找的复杂度。这类算法出现 得较晚，但近年越来越多的研究人员朝着这方向努力，主要算法有t u p l es p a c e 和p r u n e dt u p l es p a c e 。下面将对这几类算法中的代表进行详细的描述。 3 2 1 穷举遍历算法 图3 - 1i p 包分类算法分类图【1 1 】 基于完全遍历的算法的基本思想是要将数据包的相应字段跟每条规则进行 匹配，从而找到能够匹配上的规则。基于这种思想的算法主要有两类。 1 线性匹配算法 线性匹配算法( l i n e a rs e a r c h ) 是最简单的i p 包分类算法。线性匹配算法按 规则集中规则的顺序，将数据包的报头相关字段( 在i p v 4 下面就是，目的地址， 源地址，目的端口，源端口和协议字段) 和每条规则的相应字段进行比较。找到 能够匹配上的所有规则中优先级最高的一条作为最终的匹配结果。显而易见，线 性匹配算法的时间复杂度为o ( n ) ，空间复杂度也是o 州) 。空间复杂度在本算法 中非常理想，从理论上讲也是包分类算法所能达到的最小空间复杂度，但其时间 复杂度则是另一个极端。 1 2 北京邮电大学硕士论文 第三章i p v 4 的包分类算法简介 2 t c a m 算法 这里有一类特殊的基于线性匹配思想的算法，那就是基于t c a m 硬件的算 法。t c a m 的全称为t e r n a r yc o n t e n ta d d r e s s a b l em e m o r y ，它并不是一个算法， 而是一种因包分类而诞生的硬件。但根据t c a m 的匹配行为来划分的话，t c a m 属于线性匹配算法。 一个t c a m 用( 值，掩码) 对的方式来储存每一个w 比特的域，其中每一个 值和掩码都是w 比特位。例如，如果w = 5 ，前缀是1 0 ，则t c a m 要储存的就 是( 1 0 0 0 0 ，1 1 0 0 0 ) 。对于每一个需要查找的关