（计算机应用技术专业论文）流分类技术研究及其原型系统的实现.pdf

摘要 传统路由器在转发报文时主要执行了两大功能：在路由表中查找与报文的目的地址匹配 的表项，并将报文从输入端口交换到输出端口。然而随着i n t e m e t 的不断发展和商业化进程 的加速，传统i p 网络所提供的尽力而为服务已不能完全满足用户的需求。因特网供者( i s p ) 希望网络提供更好的服务，如提供q o s 保障、s l a 、防火墙、虚拟专用网( v p n ) 服务等。虽 然增强服务的种类千交万化，但是它们共同的要求就是路由器能够提供基于报头的分类功 能，相应的技术称为流分类技术。流分类研究的另一个原因就是高速网络发展的需要，目前 流分类己成为路由器查找效率的一个瓶颈。 可以看出流分类技术是作为一些网络服务的必不可少的一部分提出的，因此在流分类技 术实现过程中对网络服务有一定的依赖性。但流分类技术本身是一项独立的技术，因此在研 究过程中有必要摆脱网络服务的束缚进行单独的研究。另外，流分类技术作为一项热点技术， 流分类算法层出不穷，但是很多算法都局限于理论上的分析，实际实现过程中就存在很多问 题。综述上述各个方面，我们在本论文中综合已有的研究成果并加以必要的扩展，提出了一 个独立的流分类框架，来对这一问题进行研究解决的一个初步尝试。本文的主要内容有： 在本文的第一章中，我们对论文的研究背景、国内外研究现状以及全文的研究内容和安 排进行了综述。 在第二章中，我们首先介绍了流分类问题的提出，阐述了进行流分类的必要性；然后介 绍了流分类的一些基本概念，给出了对于流分类问题的认识性看法；最后根据目前流分类发 展的现状和存在的问题，提出了进行流分类研究的原则以及流分类算法的设计思路。 在第三章中，我们从分析目前存在的各种流分类算法着手，在综述相关的流分类研究工 作现状后，分析和比较了各种算法的性能指标，指出我们进一步深入研究的必要性，以及研 究的方向。 在第四章中，遵循我们提出的原则和设计思路，在f i s 树算法的基础上，提出了一个能 处理多个域的、具有较好的最坏情况查找速度的、占有内存小的、支持渐增式更新的动态算 法d s 树算法，并且从理论上对算法的性能进行了分析。 在第五章中，我们首先介绍了构成我们整个流分类原型系统的实践基础一一 n e t f i l t e r l p t a b l e s 框架，这个框架贯穿整个流分类原型系统。然后从用户空间、内核空间以 及用户空间与内核空间的交互技术三个方面，介绍了基于d s 树算法的流分类原型系统的设 计和实现方法。最后，对该原型系统和线形查询的i p l a b l e s 系统的性能进行了测试、比较和 分析。 在第六章中，我们从分析不同的网络服务模型着手，针对他们不同的实现结构进行分析 和总结，指出我们所研究的流分类技术在这样一种网络中所处的地位和作用。通过本章的工 作，验证了流分类技术的实用价值。 最后，在第七章中，通过总结作者在硕士论文阶段的工作，对于流分类技术及其在未来 网络中的应用前景进行了展望，分析了现有工作的缺点和不足，提出了未来可能的进一步研 究方向和方法。 关键词 分类号 流，流分类，n e r f i l t e r i p t 。, b l e s 框架，n e t l i n ks o c k e t ，用户空间，内核空间 t e 3 9 3 a b s t r a c t at r a d i t i o n a lr o u t e rp e r f o r m sr w om a i nt a s k si nf o r w a r d i n gap a c k e t ：l o o k i n gu pt h ed e s t i n a t i o na d d r e s so f t h e p a c k e t s i nt h e r o u t i n gt a b l e ，t h e ns w i t c h i n gt h ep a c k e tf r o mt h ei n p u tp o r tt o t h eo u t p o tp o r tw h i l ew i t ht h e c o n t i n u o u sd e v e l o p m e n to ft h ei n t e r a c ta n dt h es p e e du po fc o m m e r c i a l i z a t i o n ，t h eb e s te f f o r ts e r v i c ep r o v i d e db y t h et r a d i t i o n a li pn e t w o r k sn ol o n g e rs a t i s f i e st h eu s e r s s ot h ei n t e m e ts e r v i c ep r o v i d e r sh o p et h a tn e t w o r k sc a n p r o v i d eb e t t e rs e r v i c e s 。s u c ha sq o s ，s l 凡f i r e w a l l v p n ，e t c a l t h o u g ht h ee n h a n c e ds e r v i c e sv a r yg r e a t l y , t h e ya l l r e q u i r et h er o u t e rt oc l a s s i f yt h ep a c k e t sa c c o r d i n gt o t h ep a c k e th e a d e r s t h i st e c h n i q u ei sc a l l e d t h ep a c k e t c l a s s i f i c a t i o na n o t h e rr e a s o nf o rt h er e s e a r c h i n go f p a c k e tc l a s s i f i c a t i o ni st h ed e v e l o p m e n to f h i g h s p e e dn e t w o r k s s of a rp a c k e tc l a s s i f i c a t i o nh a sb e a nab o t c l c n e c kt oa c h i e v eh i 曲p e r f o r m a n c er o u t el o o k u p s p a c k e tc l a s s i f i c a t i o nw a sb r o u g h tf o r w a r da sa na b s o l u t e l yn e c e s s a r yp a r to fs o m en e t w o r ks e r v i c e s t h e r e f o r e t h ei m p l e m e n t a t i o no ft h et e c h n i q u er e t i e so nc e r t a i nn e t w o r ks e r v i c et os o m ee x t e n t b u tt h et e c h n i q u ei t s e l fi s i n d e p e n d e n t ，s oi t c a nb es t u d i e dn e g l e c t i n gt h ei n f l u e n c eo ft h en e t w o r ks e r v i c e s b e s i d e s , a sa ”h o t ”t e c h n i q u e n e w a l g o r i t h m so np a c k e tc l a s s i f i c a t i o ne m e r g ec o n t i n u o u s l y b u tm o s to f t h e m f o c u so nt h et h e o r e t i ca n a l y s i st h i s l i m i t st h ei m p l e m e n t a t i o no f t h e s ea l g o r i t h m s a c c o r d i n gt ot h ca b o v e ，t h i st h e s i ss t u d i e st h e p r e s e n tr e s e a r c hr e s u l t s a n dm a k e ss o m ee x t e n s i o na n i n d e p e n d e n ta l g o r i t h mf r a m ei sp u tf o r w a r da sa l la t t e m p tt os t u d ya n ds o l v et h e p r o b l e mt h em a i nc o n t e n t si nt h et h e s i sa r e ： f i r s t l y i n c h a p t e ri t h et h e s i ss u m m a r i z e st h er e s e a r c hb a c k g r o u n d , r e s e a r c hs t a t u sq u od o m e s t i c a l l ya n d a b r o a d ，a n dt h ec o n t e n ta r r a n g e m e n to f t h et h e s i s i nc h a p t e rt w o ，t h et h e s i sb e g i n sw i t ht h ee m e r g e n c eo ft h ep a c k e tc l a s s i f i c a t i o np r o b l e ma n di l l u s t r a t e st h e n e c e s s i t yo ft h ec l a s s i f i c a t i o n t h e nt h et h e s i si n t r o d u c e ss o m ec o n c e p t si n p a c k e tc l a s s i f i c a t i o na n dg i v e so u r u n d e r s t a n d i n g a f t e rt h a t , b a s e do nt h ep r e s e n tr e s e a r c ha n di t sd i f f i c u l t y , t h et h e s i sg i v e st h ep r i n c i p l e si n s o l v i n g t h ep r o b l e ma n dt h ec o n s i d e r a t i o n si na l g o r i t h m d e s i g n i nc h a p t e rt h r e e ，t h et h e s i sa n a l y s e st h ep r e s e n ta l g o r i t h m so l lp a c k e tc l a s s i f i c a t i o n f o l l o w i n gas u m m a r y i n t r o d u c t i o n ，t h et h e s i sa n a l y s e sa n dc o m p a r e st h ep e r f o r m a n c ea m o n gt h ea l g o r i t h m s ，t h ea n a l y s i sp o i n t so u tt h e n e c e s s i t ya n dt h ed i r e c t i o no f f o a h e rr e s e a r c h k e e pt o t h ep r i n c i p l e sa n dt h ec o n s i d e r a t i o n sm e n t i o n e da b o v e ，i n c h a p t e rf o u r , t h et h e s i sp u t sf o r w a r da d y n a m i c d s t r e ea l g o r i t h mo i lt h eb a s i so f t h ef i s a l g o r i t h m ，w h i c hc a l ld e a lw i t hm u l t i d i m e n s i o np r o b l e m h a v ea p r e f e r a b l ew o r s t c a s es e a r c hs p e e d ，o c c u p yr e l a t i v e l ys m a l lm e m o r y , a n ds u p p o r td y n a m i cu p d a t eat h e o r e t i c a n a l y s i so na l g o r i t h mp e r f o r m a n c ei sa l s oc a r r i e do n i n c h a p t e rf i v e ，t h e t h e s i s f i r s t l y i n t r o d u c e st h e p r a c t i c a l b a s i so ft h e p a c k e tc l a s s i f i c a t i o np r o t o t y p e s y s t e m - - n e t f i l t e r l p t a b l e sf r a m e w o r k , w h i c ha x i s s i nt h ew h o l es y s t e m s e c o n d l y , i ti n t r o d u c e st h ed e s i g na n d i m p l e m e n t a t i o no ft h ed s t r e ea l g o r i t h mb a s e dc l a s s i f i c a t i o np r o t o t y p es y s t e m t h ea s p e c t si nt h ed e s i g ni n c l u d e u s e rs p a c e ，k e r n e ls p a c ea n dt h ei n t e r a c t i o nt e c h n i q u eb e t w e e nt h e ml a s t , s o m e t e s t ，c o m p a r i s o na n da n a l y s i sa r e m a d eb e t w e e nt h ep r o t o t y p e s y s t e ma n d t h el i n e a r - i n d e xi p t a b l e ss y s t e m i n c h a p t e rs i x ，t h et h e s i sa n a l y s e st h ed i f f e r e n tn e t w o r ks e r v i c em o d e l s b a s e do nd i f f e r e n t i m p l e m a n t i n e s t r u c t u r e s ，w ed r e ws o m ec o n c l u s i o n sa n dp o i n to u it h es t a t u sa n de f f e c to fp a c k e tc l a s s i f i c a t i o n t e c h n i q u e si n c e r t a i nn e t w o r km o d e l s t h i sc h a p t e ri l l u s t r a t e st h ep r a c t i c a li m p o r t a n c eo f t h e p a c k e tc l a s s i f i c a t i o nt e c h n i q u e s i nt h el a s t c h a p t e r , c h a p t e rs e v e n ，t h e r ei s as u m m a r yo ft h et h e s i s b e s i d e s ，ap r o s p e c ti sm a d eo nt h e d e v e l o p m e n to fp a c k e tc l a s s i f i c a t i o nt e c h n i q u e sa n dt h e i ri m p l e m e n t a t i o ni nf o t u r e n e t w o r k ，憾c o r d i n gt oi h e s h o r t a g e si nt h et h e s i s ，w es u g g e s ts o m ep o s s i b l em e t h o d sa n dd i r e c t i o n si nf u t u r er c s e a r c hw o r k k e y “o r d ：f l o w , p a c k e tc l a s s i f i c a t i o n ，n e t f i h e r f i p t a b l e sf r a m e w o r k ，u s e r s p a c e ，k e m e ls p a c e 儿 东南大学学位论文 独创性声明及使用授权说明 一、学位论文独创性声明 x 4 4 6 8 2 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示谢意。 二、关于学位论文使用授权说明 签名：圭熟查日圳! ! 堕生! 兰! 1 8 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电 子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文 被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 签名：圭丞蚕 导师签名期：立型三向 东南大学硕士学位论文 流分类技术研究及其原型系统的实现 1 1 研究背景 第一章引言 i n t e m e t 的高速发展要求底层能够提供足够的带宽，这不但需要高速的通讯链路，还需 要高速的网络路由设备，即路由器。随着光纤通讯技术的发展，通讯链路以吉比特乃至更高 的速度进行数据传输已可以实现。相比较而言，路由器正在成为网络数据传输的瓶颈。 在路由器的转发过程中，主要有三个瓶颈：查找、交换和输出调度。近年来，在解决路 由器瓶颈方面取得了一些进展。首先是体系结构的突破，交换系统方面出现了快速总线和交 换点阵歹o ( c r o s s b a r ) 等交换设备。多数路由器的生产厂商认为，在网络视频得到广泛应用之 前，对输出队列调度的要求还不是很高。在过渡阶段，一些较简单的方案，如改进的轮询策 略( r o u n dr o b i n ) 就能够有效地满足输出调度的要求。因此，当前路由器的瓶颈主要表现在路 由器的查找效率上。 近年来兴起的一些网络应用希望路由器能够提供相应的功能支持，这些功能包括防火 墙、基于策略的路由( p o l i c y b a s e dr o u t i n g ) 、区分服务( d i f f e r e n t i a t e ds e r v i c e s ) 、q o s 、流量 计费等。在上述各种情况下，都需要将到达的数据包归类为不同的数据流，根据不同的数据 流来决定诸如是否转发该数据包、向哪里转发数据包、数据包应该得到什么样的服务或者相 应流量数据包该收取多少费用等一系列问题。这些功能都是以流分类( p a c k e tc l a s s i f i c a t i o n l 技术为基础的。由于路由器处理的数据包绝大部分都是i p 包，因此相应的技术也称为i p 分 类( 1 pc l a s s i f i c a t i o n ) 技术。 1 2 研究现状 目前流分类研究工作的范围包括分组的路由查找、基于特定规则的分组过滤、按流的定 量属性进行的流区分工作等。 1 、 以分组的路由查找为依据的流分类相关研究 分组的路由查找，根据网络层分组的分组头中目的i p 地址属性，对不同的分组进行区 分。所区分出的每一分组集合中的各分组，拥有相同的路由表表项属性。所区分出的各个流 可能的最细粒度为端系统主机一级。由于分类所依据的分类特性是确定的，所以主要的研究 集中在路由表的模式匹配查询上，即如何安排相关的数据结构和改进一般的通用查找算法， 从而使查找具有较高的时间和空间效率。 在文献 1 ，2 l e e ，给出了b s d 操作系统中相关路由查找的实现方法，它采用了基于d a t r j c i a 树 3 1 的路由表数据结构和相应的匹配查找算法。查找过程通过对分组头中目的i p 地址进行 逐比特匹配来实现。为了提高性能，研究提出了各种改进方法，包括扩展p a t r i c i a 树数据结 构1 4 1 采用高基检索树的方法”1 、压缩检索树结点”j 以满足诸如高速缓存( c a c h e ) 等方式的实 现要求等。 对精确匹配算法进行改进，使其能够满足路由查找这一特殊情况的需要，是另一种研究 的总体思路。一些研究”“提出了采用基于哈希表、改进的折半查找等方法来有效地提高路 由查找工作的效率。在进一步的研究中。1 又提出了受控前缀扩展技术，它采用前缀变换和动 态规划方法，并结合上述基于检索树和改进的折半查找等算法，给出了更加有效的路由查找 算法。 除了上述的算法外，还有一些以路由查找的硬件实现为方向的相关研究，包括采用内容 可编址内存实现路由表“，采用缓存技术进行路由缓存i 等。 上述研究仅以区分目的i p 地址为主要内容，对于实现未来网络所需的技术和研究而言， 这部分研究仅仅提供了一个良好的基础，其研究内容尚不足以满足发展的要求。 东南大学硕士学位论文 流分类技术研究及其原型系统的实现 2 、以基于规则的分组过滤为核心的流分类相关研究 基于规则的分组过滤是按照一定的形式语言规则，描述分组头的相应子域应满足的条 件，然后按照这些规则进行相应的分组区分。这时所区分出的每一分组集合中的各分组拥有 相同的规则属性。由丁：分类所依据的分类特征是依据形式规则而定的，所以主要的分类算法 仍采用模式匹配查询的方法。现有的研究主要集中在如何构造灵活和可扩展的过滤结构以 及如何通过较低层的过滤表示优化来提高分组过滤的效率。 早在1 9 8 7 年，m o g u l 等人首先提出分组过滤研究”“，并提出了相应的面向堆栈的虚拟 机实现。在随后的研究中，m c c a n n e 和j a c o b s o n 采用规则集寄存器模型“”，对上述研究进 行了改进。而y u h a r a 等将上述改进进一步完善，使其可以支持任意多的独立过滤规则“。 在此后的研究中，b a i l e y 等从改善虚拟机规则表示方法入手，提出了新的基于信元的模式匹 配方法，通过避免规则间的重复匹配，提高了过滤器的效率，并使其易于硬件实现“”。而 e n g l e r 等基于这一思路，通过引入新的底层描述语言和采用动态代码生成，使他们的研究“ 比传统的、基于解释实现的过滤方法进一步提高了性能。 在文献 1 7 1 0 ，s r i n i v a s a n 等提出了以“g i r do f t r i e s ”数据结构为核心，把多维匹配问题 转化为多个二维匹配问题的解决方法，并随后在文献【1 8 】中提出了针对二维匹配扩展性问题 的元组空问查找算法( t u p l es p a c es e a r c h ) 。上述工作进一步推进了分组过滤的研究，使其更 加灵话和便于扩展，从而满足了在路由器上根据分组头不同域的内容，向分组流提供不同服 务的需要。 b e g e l 等从完善文献 1 2 中提出的b p f 过滤结构的角度出发，提出了包括高级语言、编 译优化、冗余判别消除等一整套新技术的b p f q - 研究“，而g u p a 等根据来自实际i s p 的规 则集合，提出了新的多阶段匹配算法j 。除了上述“命令式”分组过滤以外，j a y a m m 等“ 和l a k s h m a n 等“还分别从上下文无关文法分析器和计算几何的多维空间点定位问题的角度 研究了分组过滤问题。 通过分组过滤器所区分出的不同分组集合虽然可能有较多的流属性特征，但这些依靠规 则描述的特征都是一些与特定协议相关联的确定性特征，即特征不随网络的动态特征，如流 量负载情况而变化。 3 、 以一定粒度下流的定量特征为依据的流分类相关研究 基于流的定量特性进行的流分类相关研究，是在区分一定的流收发粒度的前提下，进一 步依靠定量规则米区分不同的分组集合。定量规则中的分类特征包括依据不同方式计算的流 速率特征等。在文献 2 3 1 中，提出计算传输层t c p 连接流粒度下的流字节速率，以区分该流 是否满足“t c p 友好”( t c pf r i e n d l y ) 的属性。而在将i p 与a t m 网络结合，希望提高两者 结合的运行效率的相关研究中，特别是近年来进行的多协议标记交换( m u l t i p r o t o c o ll a b e i s w i t c h i n g ，m p l s ) 的相关研究中，也进行了以一定粒度下流速率特征为依据的流分类研究， 以挑选适当的流进行交换转发，进而提高m p l s 系统的运行效率。 在文献 2 4 】中，n e w m a n 等最早提出了用于i ps w i t c h i n g 技术中的流分类方法。主要的 分类依据是根据分组头中的相关信息，包括：t o s 、协议号、源目的i p 地址、源目的端口 号，同时也包括流的分组到达时间间隔。所采用的流认定方法包括协议分类方法、端口分类 方法和x t 方法a 前两者判断网络流量分组是否属于特定协议和协议端口号，是则认为其 是一个流；x t 方法则是指如果在t 时段内，一确定粒度的流量所拥有的分组数大于x 时， 则确定此流量符合系统的要求，被认为是一个流，从而将被进一步分配交换资源并进行交换 方式的转发。 在文献 2 5 y h ，l i n 等研究了不同网络流量特性对标志交换系统的性能影响，分析了不 同的v c 管理代价，不同流分类器( x y 分类器，协议区分，端口区分) 对t ps w i t c h i n 2 系统毅 率的影响，以被交换的分组数占流量中总分组数的百分比为尺度进行系统的性能评价。 查堕查兰堡主兰垡笙苎 亟坌鲞垫查堡壅墨基堕型墨堑塑壅塑 在文献 2 6 中，f e l d m a n n 等针对w e b 服务器的响应流，首先进行了其流量特性的分析， 指出了其流的字节大小和持续时间分布情况与各种不同h r r p 相应内容之间的对应关系，分 析了不同类型主机和不同流时，各汇聚粒度下的流字节大小分布情况。随后针对x f y 流分 类器，研究了不同x 值引起的系统效率变化和v c 建立速率变化等。文中最后分析了针对 不同的路径汇聚情况下的x y 流分类器的效率。 在文献1 2 7 中，c h eh a o 等首先研究了在动态的x z 自适应流分类器算法下，标志交 换系统的最优运行控制问题。系统同时跟踪三个动态变化的控制参数：系统软件转发能力利 用率、系统硬件转发能力利用率和系统c a c h e 能力利用率，以在一定时间段内使三者中最大 者最小为目标对系统进行m a x - m i n 最优控制。通过最终控制x 参数和t 参数的变化，使 系统始终处于最优运行区域。 在文献【2 8 1 中，l l v e s m a k i 等主要提出了一种基于神经网络的学习矢量量化流分类方法， 并将其性能与传统的静态协议分类器和协议端口分类器进行了比较。 为了更好地总结上述研究现状，我们从研究方向、分类的应用场合、分类依据特性、分 类的依据和判别方法、对未来网络支持等几个方面，对上述分析进行对比，如表1 - 1 所示。 表1 1 流分类工作研究现状总结 研究方向分类技术的应用研究分类依据分类的依据与判别对未来网络的支 的特性方法持 分组的路分组流的路由寻径定性根据目的i p 地址进无 由查找行模式匹配查找 基于规则分组过滤的不同应用定性由分组头中各域组区分不同定性分 的分组过场合，如网络安全检成的规则或规则组流的不同服务 滤查、防火墙应用、区分集，进行模式匹配 其他定性特征等查找 流的定量网络的流量控制定量依据定量特征和分提高网络的运行 特性类的判别函数进行性能，需要进行相 判别分析应的服务映射 通过上面的分析可以看出，以分组的路由属性为依据的流分类，可以看作是以规则的过 滤研究为核心的流分类的一个特例和基础。前者只是针对分组的目的i p 地址，而后者研究 分组头的多个域，后者的很多算法都是依据前者的算法进行扩展得到的。以规则的过滤研究 为核心的流分类与以一定粒度下流的定量特征为依据的流分类，是从两个不同的角度研究流 分类问题。在本文中，我们主要研究了以规则的过滤研究为核心的流分类算法。 1 3 研究内容和安排 在本文的第一章中，我们对论文的研究背景、国内外研究现状以及全文的研究内容和安 排进行了综述。 在第二章中，我们首先介绍了流分类问题的提出，阐述了进行流分类的必要性：然后介 绍了流分类的一些基本概念，给出了对于流分类问题的认识性看法：最后根据目前流分类发 展的现状和存在的问题，提出了进行流分类研究的原则以及流分类算法的设计思路。 在第三章中我们从分析目前存在的各种流分类算法着手，在综述相关的流分类研究工 作现状后，分析和比较了各种算法的性能指标，指出我们进一步深入研究的必要性，以及研 究的方向。 在第四章中，遵循我们提出的原则和设计思路，在f 1 s 树算法的基础上，提出了一个能 东南大学硕士学位论文 流分类技术研究及其原型系统的实现 处理多个域的、具有较好的最坏情况查找速度的、占有内存小的、支持渐增式更新的动态算 法d s 树算法。并且从理论上对算法的性能进行了分析。 在第五章中，我们首先介绍了构成我们整个流分类原型系统的实践基础一一 n e t f i l t e r i p t a b l e s 框架，这个框架贯穿整个流分类原型系统。然后从用户空间、内核空间以 及用户空间与内核空间的交互技术三个方面，介绍了基于d s 树算法的流分类原型系统的设 计和实现方法。最后，对该原型系统和线形查询的i p t a b l e s 系统的性能进行了测试、比较和 分析。 在第六章中，我们从分析不同的网络服务模型着手，针对他们不同的实现结构进行分析 和总结，指出我们所研究的流分类技术在这样一种网络中所处的地位和作用。通过本章的工 作，验证了流分类技术的实用价值。 晟屙，在第七章中，通过总结作者在硕士论文阶段的工作，对于流分类技术及其在未来 网络中的应用前景进行了展望分析了现有工作的缺点和不足，提出了未来可能的进一步研 究方向和方法。 4 东南大学硕士学位论文流分类技术研究及其原型系统的实现 第二章流分类问题描述 传统路由器在转发报文时主要执行了两大功能：在路由表中查找与报文的目的地址匹配 的表项，并将报文从输入端口交换到输出端口。然而随着i n t e m e t 的不断发展和商业化进程 的加速，传统i p 网络所提供的尽力而为服务( b e s t e f f o r t ) 已不能完全满足用户的需求。i s p 希望网络提供更好的服务，如提供q o s 保障、s l a 、防火墙、v p n 服务等。虽然增强服务 的种类干变万化，但是它们共同的要求就是路由器能够提供基于报头的流分类功能。 本章首先介绍了流分类问题的提出，阐述了进行流分类的必要性；然后介绍了流分类的 一些基本概念，给出了对于流分类问题的认识性看法；最后根据目前流分类发展的现状和存 在的问题，提出了进行流分类研究的原则以及流分类算法的设计思路。 2 1 流分类问题的提出 当前的i n t e m e t 所提供的尽力而为的转发机制，无法为用户提供高质量的声音、图像等 多媒体传输服务。将来的i p 网络服务与商业挂钩，需要考虑用户的要求及其付费行为从 而对用户提供因人而异的全方位i p 网络服务，这就需要对报文的头部进行综合处理，流分 类、流标识是其中的关键技术。同时流分类在网络技术领域中具有广泛的应用，许多网络关 键技术，例如虚拟专用网( v p n ) 、基于访问控制列表( a c l ) 的防火墙、q o s 、网络入侵检测、 网络地址转换、拥塞控制、传输测量与记账、资源预留、负载平衡、收集统计数据等都是以 流分类为基础的，流分类速度的快慢、功能的强弱等都真接影响到这些网络技术的性能，但 目前的研究表明，实现高速多维的流分类算法是非常困难的，它已成为路由器的一个瓶颈， 因此受到了广泛的关注。 图2 - 1 ”。“l 实例网络中i s p i 连接三个不同的站点：两个企业网e l 、e 2 和一个网络接入点， 网络接入点连接i s p 2 和 s p 3 。i s p l 为它的顾客提供如下的服务： 图2 - 1 实例网络 包过滤：路由器x 禁止从i s p 3 到e ：的所有流量。 基于策略路由：路由器y 通过一个独立的a t m 网络转发从e l 到e 2 的所有音频流。 记账和计费功能：把通过路由器y 到e i 的所有视频流作为最高优先级实施记账和计费。 流量速度限制：确保在路由器x ，注入i s p 2 的邮件流量不超过1 0 m b s ，总流量不超过 5 0 m b s 。 流量整形：确保在路由器x ，注入i s p 2 的突发流量不超出5 0 m b s 。 i s p 1 为了提供上述的各项服务，就必须根据服务的要求，对到达各个路由器的报文的报 头进行分析分类。也就是说，实现这些功能都需要将到达的数据包归类为不同的数据流，根 据不同的数据流来决定诸如是否转发该数据包、向哪里转发数据包、数据包应该得到什么样 的服务或者相应流量数据包该收取多少费用等一系列问题。这些功能都是以流分类技术作为 基础的。 研究流分类的另一个原因是高速网络发展的需要。为了使网络性能得到全面的提高，需 要网络各部件：f 作得更快，特别是路由器。而传统的路由器已经无法满足日益增氏的业务需 东南大学硕士学位论文流分类技术研究及其原型系统的实现 要，发展高速路由器作为未来骨干网的良好解决方案越来越受到人们的重视。为此要引入高 速的路由查找、流分类、流标识、缓冲管理和分组调度管理等网络控制机制，以对不同要求 的i p 流进行不同的高速处理。其中高速的路由查找和流分类技术是缓冲管理和分组调度管 理的重要基础，它们的速度快慢和性能好坏直接影响整个路由器的性能。到目前为止，已经 研究出了一些快速的路由查找算法，所以大家的注意力就转移到研究更通用的流分类算法 上。同时流分类机制也已经被认定为由i e t f 建议的q o s 模型的一部分，在区分服务体系结 构中，也专门对流分类机制进行了阐述。 由此看出流分类问题是目前一些热点问题的基础，是路由器的关键技术之，它的研究 一旦获得重大进展，必将进一步扩展宽带i p 网络的应用领域，使i n t e m e t 为用户提供更多、 更好、更完善的服务。 2 2 流分类问题的描述 2 , 2 1“流”简述 关于什么是流，早在1 9 8 8 年因特网研究界的先驱者之一一d a v i dc l a r k 教授在文献3 1 1 中，在展望未来的分组网络体系结构时，给出了最初的定义：流( f l o w ) 是“从一个源发送到 一个目的的分组序列”。之所以要将分组这个网络中的最小单位，从流即分组集合的角度加 以考虑是分组网络发展的必然要求。未来的网络必须面对多种不同媒体应用的需要，向不同 种类的网络应用提供与他们要求相适应的服务。因此，在网络中，特别是在网络的各中继结 点中，处理的信息对象虽然仍以分组为最基本单元，但在进行诸如网络资源分配与管理、网 络运行控制等工作时，就必须至少以两个不同服务对象的信息单位来进行，而这就需要定义 “流”这样的概念。 要对流的概念给出普遍接受的、一般性精确定义是困难的，多年来流的特性相关研究从 不同的方面证明了这一点。流的特性研究是基于网络实时流量测量的流量特性描述和分析研 究的重要组成部分。早在7 0 年代排队论的创始人k l e i n r o c k 教授就开始了这方面的j 二作， 而9 0 年代以来，特别是从开展网络集成服务以来，在这方面最重要的工作是c l a f r y 博士的 博士论文p ”。在论文中，c l a f f y 博士系统地从中继系统的观点出发，研究了流的定义和不同 时空参数下的相应流特性分析问题。通过他的论文我们可以看到，流具有多方面的特性，如 传输的方向性、不同的收发系数粒度、不同的网络协议层次性质等，因此要对流的概念给出 普遍通用的精确定义是困难的。但在网络层，可以采用j a i n 教授。”和c l a f f y 博士所用的基 于超时的流定义方法。 在本文中，我们认为，流是具有某种相同属性的网络协议分组的集合。区分两个流的不 同在于比较它们两者属性的差异。组成流的最小单位为分组。 2 2 2 流分类定义的描述 这一部分中给出流分类的数学定义，从数学上定义流分类，有不同的方法，但它们基本 上都是等价的，我们选取其中的一种来进行描述。“。首先，定义一些必要的术语如下： 2 2 2 1 相关术语 定义1 二值比特只能取0 和1 两个值，三值比特可以取0 、1 和+ 这三个值，其中，为通 配符，可以与0 、1 中的任一个进行匹配； 定义2 一个地址d 是一个民度为w 比特的比特串； 定义3 一个前缀p 是长度介于0 到w 间的一个比特串，l e n g h 俨) 表示前缀p 的以比特 数为单位的长度： 定义4 如果d 开始的l e n g t h ( p ) 个比特与p 相同，就称前缀p 与地址d 匹配： 查堕奎堂堡主兰生笙苎 堕坌鲞垫查堕塞墨基垦型墨竺塑壅翌 定义5 包头h 是有k 个域实体，包头的各个域分别表示成h b i ，h 2 1 ，h 【k 】，其 中每个域都是比特串： 定义6 一条过滤规则f 也具有k 个域。与过滤规则的一个域f i 】相关联的有一个匹 配方式，它可以是下面三种匹配方式中的任何一个口q ：精确匹配( e x a c tm a t c h ) ，前缀匹配 f p r e f i xm a t c h ) 或范围匹配( r a n g em a t c h ) ： 定义7 当域f e i 通过一个数值来指定时，如果包头h 的域h i 与过滤规则f 的域 f i 】满足日【f = f i 】，那么就称h i 】与f i 】精确匹配： 定义8 当域f i 】通过一个前缀来指定时，如果包头h 的域h i 】与过滤规则f 的表示 前缀的域f i 】匹配，那么就称h i 】与f i 前缀匹配： 定义9 当域f i 】通过一个范围指定时，也即f i 】- - v a l 卜v a l 2 ，如果包头h 的域h i 与 过滤规则f 的域f i 】满足v a l l h i 】v a l 2 ，那么就称h i 与f i 范围匹配； 定义l o 我们称过滤规则f 与包头h 匹配，当且仅当对h 的每个域h i 1 都与f 相应 的城f i 】匹配。h i 1 与f i 】的匹配方式由f 【f 】的形式指定，可能为上述匹配方式中的任 何一种。 2 2 2 2 流分类定义 流分类问题可以简单的描述为，根据事先定义的一定的策略和规则，对报文报头的一个 或多个域进行分析，以识别该报文所属的流。一个比较正式的d 维流分类问题可以描述为”： 与流分类有关的策略和规则的集合称为分类器，假定一个分流器含有个规则， r ，) 芒l ，其中规则r ，有三部分组成： 1 、一个规则表达式r ，【f i ，l ，d ，其中d 是指报头有d 个域。 2 、一个数字p r i ( r ，) ，指出了该条规则在分类器中的优先级，用来当一个报文同时匹 配多个规则时决定哪个规则优先匹配。 3 、一个操作a c t i o n ( r ，) ，表示当这个规则被匹配后应对报文所做的操作。 对于一个到达的报文p ，其报头是d 维元组( 只，只，只) ，其最佳匹配规则r 满足： 只匹配r j 【f ，其中l 蔓i 墨d ；并且对于v ，j ，若只匹配r 女【f 都有p r i ( r ，) p r i ( r 女) 。 2 2 3流分类在路由器中所处的地位和作用 流分类是路由器关键技术之一，是提高路由器性能，尤其是提高转发路径性能的一种路 由器机制。因此对于流分类的更深入研究需要对路由器的体系结构有一定的了解。图2 - 2 是 一个典型的路由器体系结构图，路由器的主要由三个部分组成： l 、控制卡：它的主要