（计算机应用技术专业论文）流量测量系统中基于特定流的流匹配算法研究.pdf

重庆邮电学院硕士研究生论文 摘要 下一代网络( n g n ) 将是以i p 为核心的高速网络。由于i p 网络固有的缺 陷，其q o s 得不到很好保证。通过对网络中的流量进行准确测量，并以此为依 据进行网络控制和管理，可以显著提高网络的q o s 。然而，在高速网络中，要 想测量全部的流几乎是不可能的。目前，基于特定流的流量测量己成为高速网 络流量测量的一个新的研究方向。因此流匹配算法是对高速网络中特定流进行 准确测量的关键。 目前可用于流匹配的算法有很多。论文对多种i p 数据包分类算法进行了较 为全面的分析比较。通过研究，我们发现递归流分类( r f c ) 算法的分类速度较快， 且适合于硬件实现，它的最大缺点是内存消耗大。研究还发现h a s h 算法用于流 匹配具有预处理时间短、内存消耗低、支持匹配规则数多等优点，但常规的h a s h 算法用于流匹配时冲突率较高。 论文针对r f c 算法的不足，提出了一种多阶段无冲突归并( m p n c m ) 流 匹配算法。m p n c m 流匹配算法采用标记桶实现最长前缀匹配，用最小区间划 分进行范围匹配，同时增加了提前丢包的处理。该算法在平均匹配速度和内存 消耗上优于r f c 算法。由于m p n c m 内存消耗仍然较大且不能支持较大的匹配 规则集，论文又进一步研究了h a s h 算法，提出了一种随枫矩阵映射( s m m ) h a s h 算法。s m mh a s h 算法采用了随机矩阵映射，使计算出的h a s h 关键值服 从均匀分布且能减少自相关冲突，因此该算法在冲突率、匹配时间等方面都优 于常规h a s h 算法，并且支持的匹配规则数可达5 万条以上。 m p n c m 算法和s m mh a s h 算法具有不同的应用场合，m p n c m 算法适用 于硬件实现，用于匹配规则数少，匹配速度要求高的环境。而h a s h 算法适合于 软件实现，用于匹配规则数较多的场合。 关键词：流量测量、数据包分类、流匹配、多阶段无冲突归并、随机矩阵映射、 递归流分类、哈希 重庆邮电学院硕士研究生论文 a b s t r a c t n e x tg e n e r a t i o nn e t ( n o n ) w i l lb eah i 曲一s p e e dn e t w o r kw h i c hi sb a s e di p b u t ， t h eq o so fi pn e t w o r kc a n tb eg u a r a n t e e db e c a u s eo fi p s i n h e r e n t p r o p e r t y m e a s u r i n gn e t w o r k st r a f f i ci saw a yt oc o n t r o la n dm a n a g et h en e t w o r ka n dt h r o u g h w h i c hn e t w o r k sq o sc a l lb eg u a r a n t e e d h o w e v e lm e a s u r i n ga l l t r a f f i ci n h i g h - s p e e dn e t w o r ki s a l m o s ti m p o s s i b l e t h u s ，t h es p e c i a lf l o w s 。b a s e dt r a f f i c m e a s u r e m e n ti sb e c o m i n gan e wd i r e c t i o n ，a n dt h ep e r f o r m a n c eo ff l o w sm a t c h i n gi s ak e yi s s u et h a tw em e a s u r et h en e t w o r k st r a f f i ce x a c t l y n o w , t h e r ea r em a n yf l o w sm a t c h i n ga l g o r i t h m s i nt h i sp a p e r , w ea n a l y z ea g o o df e wf l o w sm a t c h i n ga l g o r i t h m sc o m p r e h e n s i v e l y a sar e s u l t ，w ef i n dt h a t r e c u r s i v ef l o wc l a s s i f i c a t i o n ( r f c ) i so n eo ft h ef a s ta l g o r i t h m sa n dc a nb ec a r r i e d o u tw i t hh a r d w a r ee a s i l y t h ed i s a d v a n t a g eo fr f ci st h a tm e m o r yi tn e e d si sh u g e w ea l s of i n dt h a th a s ha l g o r i t h mh a v em u c ha d v a n t a g ew h e ni ti su s e dt of l o w s m a t c h i n g ，s u c ha ss h o r tp r e p r o c e s st i m e ，l o wm e m o r yc o n s u m p t i o na n ds u p p o r t i n g b i gr u l es e t b u t ，ac o m m o n h a s ha l g o r i t h mh a sah i 班c o l l i s i o nr a t e f o rt h ep u r p o s eo fo v e r c o m i n gt h ed i s a d v a n t a g eo fr f c ，t h i sp a p e rp r e s e n t sa m u l t i - p h a s en o n - c o l l i s i o nm e r g e ( m p n c m ) f l o w sm a t c h i n ga l g o r i t h mw h i c hc a r r y o u tt h el o n g e s t - p r e f i xm a t c h i n ga n dr a n g em a t c h i n gt h r o u g hm a r kb u c k e ta n d m i n i m u mi n t e r v a l s p l i t t i n gr e s p e c t i v e l y , a n dd e p l o y st h ee a r l yd i s c a r d i n gp a c k e t p o l i c y t h ea v e m g em a t c h i n gt i m ea n dm e m o r yc o n s u m p t i o no fm p n c ma l g o r i t h m i ss u p e r i o rt ot h er f ca l g o r i t h m b u tm p n c m a l g o r i t h m sm e m o r yc o n s u m p t i o ni s b i ga n dc a n ts u p p o r tb i gr u l es e ty e t ，w ep r e s e n tas t o c h a s t i cm a t r i xm a p p i n g ( s m m ) h a s ha l g o r i t h m s m mh a s ha l g o r i t h mm a k e st h eh a s hk e yb eau n i f o r m d i s t r i b u t i o nt h r o u g hs t o c h a s t i cm a t r i xm a p p i n ga n dc a nd e c r e a s et h es e l f - c o r r e l a t i n g c o l l i s i o nr a t e s ot h es m mh a s ha l g o r i t h mi s s u p e r i o r t ot h ec o m m o nh a s h a l g o r i t h m si nc o l l i s i o nr a t ea n dm a t c h i n gt i m e i tc a ns u p p o r tam a t c h i n gr u l es e t w i m5 0t h o u s a n dr u l e s m p n c ma n ds m mh a s ha l g o r i t h m sh a v ed i f f e r e n ta p p l i c a t i 9 no c c a s i o n s m p l q c ma l g o r i t h mi ss u i t a b l ef o rm a t c h i n gr u l e sb e i n gs m a l la n dm a t c h i n gs p e e d b e i n gv e r yf a s t t h i sa l g o r i t h mi ss u i t a b l ef o rc a r r y i n go u ti tw i t h h a r d w a r e w h i l e s m mh a s ha l g o r i t h mi ss u i t a b l ef o r m a t c h i n gr u l es e tb e i n gl a r g ea n dc a r r y i n go u ti t w i t hs o f t w a r e k e y w o r d s ：t r a f f i cm e a s u r e m e n t ，p a c k e tc l a s s i f i c a t i o n ，f l o w sm a t c h i n g ，m p n c m ， s m mh a s h ，r f c 。h a s h i i 耍炭邮电学院蕊士硬究生论文 独创性声明 本人声明所呈交的学位论文跫本人在导师指导下进行麴研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的 地方外，沦文中不包含其他人已经发表缄撰写过的研究成果，也不 包含为获得重丛监皂生筮或其他教育机构的学位或证书商使用 过的材料。与我同工作的同志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示谢意。 学位论文作者签名：凌岛锑 签字日期：撕 正年f 月，夕日 学位论文版权使用授权书 本学位论文作者完全了解 萋鏖螯电生殖一有关保留、使用 学位论文的规定，有权保留并向图家钉关部门或机构送交论文的复 e ；| j 件和磁盘，允许论文被查阅和借阅。本人授权重匮自电堂瞳 可以将学位论文的全部或部分内容编入有关数据库避行检索，可以 采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文j 乍者签名：筝、勇芬 签字日期： 抑驴年f 月7 日 导师攀名力五 签字f j 期：加4 年j 。月7 曰 重庆邮电学院硕士研究生论文 1 1 选题的背景 第一章绪论 随着网络技术的快速发展，网络的传输速度越来越快，目前骨干网的速度已 达到1 0 g b p s 以上。从当前数据通信联网协议的应用情况来看。i p 协议己成为一 个占绝对主导地位的网络层协议。可以预见，下一代网络( n g n ) 将是以i p 为 核心的高速网络1 1 l 。但是，由于i p 协议的固有缺陷1 2 1 ，它采用的是尽力而为 ( b e s t - e f f o r t ) 的服务方式，其q o s 无法得到保证。已有的实际应用表明，如果 能准确测量网络中的流量，并以此为依据进行网络控制，可以显著提高i p 网络 的q o s 。3 l | 4 1 。 在当今以i p 协议为基础的i n t e r n e t 网中进行一分钟测量，结果显示有2 5 0 0 0 0 多个流【5 i f 6 i ，要管理如此复杂的骨干网需要监视网络中的流量7 1 1 8 t 。而随着网络运 营商之间的互联和资源共享的不断增加1 9 1 ，运营商需要一种机制来测量相互之间 流量交换的规模和公平性，需要知道彼此之间带宽的使用情况。同时，随着实时 多媒体业务在因特网上的应用，高端用户和低端用户之间的不公平性更加突出。 因为低端用户只需要突发的、低优先级的流量，而他们却支付与高端用户一样的 费率。因此，传统包月式的固定计费方式已不适应新业务的发展，基于服务水平 的计费方式l lo i 成为一种迫切的需要。 一 对于网络管理者来说，网络分析的重要内容是网络负载和用户对网络流量的 需求。通过对流量模式的统计分析，特别是对本地峰值模式的分析能找出流量的 变化规律i l ”，从而为改善网络服务质量提供依据。对于网络规划者来说，要设计 适度规模的网络，需要有网络流量的准确资料。否则，网络容量太大会付出昂贵 的代价，而容量太小又会引起客户的不满。 所有这些都说明准确测量网络流量是保证网络可管理、可运营、可控制的重 要手段，是保证网络健壮的必要措施。 对网络的流量进行测量的方法主要可分为两大类，一是主动测量，二是被动 测量1 1 1 j 。主动测量是在网络的边缘以一定的策略发送探测包，在预先设定的测量 点获取探测包，从而建立整个网络的流量矩阵，再运用一定的数学模型推算出整 个网络的流量。这种测量方法的准确性依赖于发送探测包的策略、建立的流量矩 阵以及数学模型的科学性，同时它产生的附加流量可能会产生h e i s e n b e r g 效应 i l z lo 被动测量是对网络中的全部或部分流量直接进行监测和统计，从而获取网络 流量的实际状况。它可分为基于流的测量、基于接口的测量、基于结点对的测量 和基于路径的测量。这种测量方法不干扰网络自身的流量，不产生额外的流量， 可以完全取消附加流量和h e i s e n b e r g 效应。但是，这种测量方法会产生大量 重庆邮电学院硕士研究生论文 的数据，如何快速处理这些数据成为一个严重的问题。为减少处理的数据量，i e t f r f c2 3 3 0 1 1 3 i 建议采用抽样技术，如采用固定周期抽样、随机时间抽样、泊松分 布抽样和几何分布抽样等。 基于流的被动测量方法是对网络中的数据包按预先指定的特征值( 如i p 地 址、端口号等) 进行聚合，将具有相同特征值的数据包归属为同一个流。然后以 流为粒度进行计量。这种测量方法不会丢失太多的网络信息，同时需要收集的数 据量较少，使得流量测量的速度得到大幅度提高，从而大大提高了高速网络流量 测量的准确度。因此，基于流的被动测量是目前采用较多的一种流量测量方法。 r f c 2 7 2 2 1 1 4 1 描述了基于流的被动测量方法的通用架构。这种测量系统的主要 构成部分是计量器( m e t e r ) 、计量读取器( m e t e rr e a d e r ) 和管理器( m a n a g e r ) 。 该文档还给出了如何编制流匹配规则集、如何对流进行匹配、如何卸出测量数据、 如何对内存的流记录进行管理等。这种测量方法主要存在以下不足：( 1 ) 为每个 流设定最长活动时间和最长不活动时间，对于长流来说会被人为的分成多个流， 造成计量上的不准确1 1 5 1 。( 2 ) 动态进行流的匹配和流的创建，处理时间较长。( 3 ) 对匹配规则没有进行预处理，或只进行了有限的预处理。( 4 ) 系统开销很大。它 为每个流设置2 个定时器，还需经常对内存进行清理。( 5 ) 形成的数据量极大。 在高速骨干网中按r f c 2 7 2 2 规定的测量方法进行连续、实时的流量测量面 临更多的困难，主要表现在：( 1 ) 高速链路中存在大量的流。据统计1 5 i ，在高速 链路中两个终端主机之间进行一个小时的测量有8 0 万个流，要对每一个流维持 一个计数器是不可行的。( 2 ) 在高速链路中，每天收集的数据达几t b i t s 。管理、 存储和分析这些数据也是一种挑战【l 副。( 3 ) 对高速网络进行测量时，测最设备的 总线、内存和磁盘阵列的速度都远远跟不上链路的带宽。( 4 ) 由于i p 网络中流 量的自相似和多分形行为特征i “i i ”i ，使得抽样测量结果存在较大的误差。 有研究表明1 5 1 l l 剐，网络中1 0 的流占有9 0 的流量，同时i p 流具有重尾 ( h e a v yt a i l ) 分布的特点l l 。因此在实际工作中，只要管理好这少部份对网络影 响很大的流即可达到满意的效果。这部分流主要包括业务大客户和签订了s l a 合同用户的业务流，或者是流量很大，容易对网络带宽和服务质量造成较大影响 的流。只要能对这些特定的流进行测量和监视，就能较好地保证整个网络的q o s 。 因此基于特定流的流量测量已成为高速网络流量测量的一个新的研究方向f 2 m 。 对网络中的特定流进行测量的关键是要快速对到达的数据包进行匹配以确 定它属于哪一个流。因此，流匹配算法对高速网络中的特定流进行准确测量具有 重要意义。 目前，适合于流匹配的算法主要有4 类，分别是b p f ( b s dp a c k e t sr i 2 t e r ) 算 法、利用s r l ( s i m p l e r u l e l a n g u a g e ) 编写匹配规则集、多域数据包分类算法 一2 一 重庆邮电学院硕士研究生论文 和h a s h 算法。b p f 算法和s r l 方法的匹配速度相对较慢，不适合高速网络。r f c 算法是多域数据包分类算法中匹配速度较快的，而h a s h 算法的主要优点是运算 简单，支持较大的匹配规则集。这两种算法具有较大的实用价值。但是r f c 算 法用于流匹配存在内存消耗和处理量都很大的缺点，而常规h a s h 算法用于流匹 配具有较高冲突率的缺点。 论文结合重庆市科委项目“高速网络业务量测量系统”和重庆市教委项目“高 速网络数据包分类算法”，针对r f c 算法的不足提出了一种改进算法称为多阶段 无冲突归并( m u l t i p h a s en o n c o l l i s i o nm e r g e ，m p n c m ) 流匹配算法。由于 m p n c m 算法内存消耗仍然较大且不能支持较大的匹配规则集，论文又进一步研 究了h a s h 算法，提出了一种随机矩阵映射( s t o c h a s t i c m a t r i x m a p p i n g ，s m m ) h a s h 算法。该算法能克服常规h a s h 算法的用于流匹配冲突率高的缺点。两种算 法具有不同的应用场合，m p n c m 流匹配算法适用于硬件实现，用于匹配规则数 少，匹配速度要求高的环境。而s m mh a s h 算法适合于软件实现，用于匹配规 则较多的场合。 1 2 论文的内容和结构 论文的主要内容包括：( 1 ) 概括了目前国内外开展的高速网络流量测量的主 要研究工作，总结了用于流匹配的主要方法；( 2 ) 介绍了i p 数据包分类的数学 模型，对多种i p 数据包分类算法进行了较为全面的分析比较；( 3 ) 针对r f c 算 法用于流匹配存在的不足，提出了一种改进算法称为多阶段无冲突归并 ( m p n c m ) 流匹配算法；( 4 ) 针对m p n c m 算法的不足和常规h a s h 算法冲突 率离的缺点，提出了一种随机矩阵映射( s m m ) h a s h 算法。( 5 ) 讨论了m p n c m 算法和s m mh a s h 算法的实现、性能分析和应用环境。 论文的主要结构如下： 第一章：绪论。介绍论文的选题背景和论文从事的主要工作。 第二章：基于特定流的流量测量。介绍了高速网络中基于特定流的流量测量 的意义和应用，并对目前国内外研究现状进行了分析。同时分析了流匹配算法在 基于特定流的流量测量系统中的重要地位。 第三章：i p 数据包分类算法。详细介绍了i p 数据包分类的数学模型，包括 i p 数据包分类算法的数学理论基础、n 维数据包分类的几何问题和范围匹配转换 成前缀匹配等基本问题，并对多种i p 数据包分类算法进行了分类，总结了各自 的特点、适用场合以及时间和空间复杂度。 一3 一 重庆邮电学院硕士研究生论文 第四章：多阶段无冲突归并( m p n c m ) 流匹配算法。本章详细搓述了我们 提出的多阶段无冲突归并流匹配算法的原理、匹配算法的预处理过程、匹配算法 的疆配过摆数及算法的性能分析和仿真结果，并绘出了算法实现的部分源程序代 码。 第五章：随机矩阵映射( s m m ) h a s h 算法。本章详细描述了我l f 提出的随 机矩阵映射h a s h 算法的实现原理、算法的预处理和用于流匹配的过程以及算控 用于流匹配的测试结果，并比较了s m mh a s h 算法和m p n c m 算法。本章还 对s m mh a s h 算法具有较低j 孛突率绘出了3 个定理，并进行了 正明。 第六章：结论与后续工作展望。 一4 一 里壅坚生堂堕堡主竺茎竺堡苎 2 1 概述 第二章基于特定流的流量测量 近年来，数据业务正呈现指数增长态势，特别是i p 业务正呈现爆炸式增长。 光纤骨干网带宽己达到了约6 9 个月就翻一翻，比著名的摩尔定律还要快2 3 倍，成为所谓的光纤定律或超摩尔定律1 2 1 1 。预计在未来5 一l o 年内，世界主要网 络的数据业务量将超过电话业务量。最终，电信网的业务将主要由数据构成1 2 “。 而网络业务的数据化趋势实质上是i p 化口”。从数据通信联网协议的使用率 来看，发达国家i p 协议已超过8 0 ，而我国已超过9 0 ，i p 已经成为占绝对主 导地位的数据通信联网协泌。i po v e re v e r y t h i n g 和e v e r y t h i n go v e ri p 将逐渐成为 现实i2 1 i 。 由此可见，i p 将是n g n ( n e x t g e n e r a t i o n n e t ) 的核心技术之一。然而由于i p 协议是一种面向无连接的、尽力而为的服务，同时针对它的大多数协议和算法都 不能确保q o s 。尤其是在需要提供恒定传输速率( 如话音服务、视频传输) 等方 面，i p 网络存在明显不足。 根据国际标准化组织i e t f ( i n t e m e te n g i n e e r i n gt a s kf o r e 曲内流量工程工作 组( t e w g ) 的定义，流量工程( t r a f f i ce n g i n e e r ，t e ) 就是以优化网络性能为 主要目标的网络工程技术。它包括流量测量、流量建模、流量描述和流量控制， 以及为使网络达到特定的性能要求而采用的技术口2 1 。流量工程的目的是控制网络 资源、提高网络性能，提高业务服务质量，从而解决传统的i p 尽力而为的服务 与q o s 的统一。已有研究和应用表明，凡是采取了流量工程的网络，即使只是 采用了简单的技术手段，都能明显地提高网络的性能f 2 3 1 1 2 。 流量测量作为流量工程的重要组成部分，是流量工程最为核心的基础内容， 因为流量测量所得到的原始信息是流量控制、流量建模的基础。在网络中进行流 量测量可以确定网络中流量的分布状况、网络资源的利用情况，从而为流量工程 中的流量控制提供反馈信息。它还能对控制策略的有效性进行评价，获知网络中 实际的q o s 。了解网络的阻塞情况，探测网络中某些部件故障的发生等。 随着网络速度越来越快要测量网络中所有流量变得十分困难，而只测量网 络中的特定流已成为一个新的研究方向。所谓特定流是指业务大客户或签汀了 s l a 合同的用户的流或者是那些流量很大，容易对网络带宽和服务质量造成较 大影响的流，文献1 7 1 把它们称为h e a v yh i t t e r s ，这部分流是网络运营商特别关心 的。如果能对这部分流进行测量和监视，就能很好地保证整个网络的q o s 。 与对网络中所有流进行测量相比，基于特定流的流量测量有如下优点： 5 一 重庆邮电学院硕士研究生论文 测量速度快，内存需求低，测量准确度高，可以对高速网络中的流量进 行实时测量。 可以长时间对流进行监测，收集的数据较少，利于存储和分析。 对于长流( 如f t p 流、视频流等) 的测量非常有效。因为在整个测量期间 这些流都准确地保持在一个流中。 基于特定流的流量测量的意义： 实现基于流的计费：v o l u m e b a s e d 的计费模式仅依赖于通过的总流量， 而不管流量的起源，它不能反映网络的运行成本。而f l o w b a s e d 的计费方式更 能反映网络运营商提供的服务水平和用户享受的服务质量1 2 6 i 。 可咀实现对指定用户按流量大小计费，还可以根据流量和网络利用情况 给予不同的费率和不同的服务，对超过s l a 合同的流量可以不保证服务质量或 给予高的收费标准| 2 “。 通过对每个流的长期测量数据的分析，可以刻画该流的时间分布，并预 测该流的走势，发现该流与网络性能的关系，从而为网络规划和发现网络瓶颈提 供依据。 通过分析每个流的实时数据，有助于q o s 路由和m p l s 标记路径的准 确建立。 实现实时网络控制：通过测量网络中流量，可以获取网络资源的需求信 息，从而可以通过对流进行分割实对地进行负载平衡，避免网络拥塞。 网络应用状况监测与分析：通过对网络流量的监测，可以了解网络上各 种协议的使用情况，研究者可以据此研究新的协议与应用。 网络用户行为监测与分析：通过监测网络的流量，可以了解到：某一段 时间有多少用户在访问网络；访问网络最多的用户是哪些；用户在网络停留的时 间：用户来自什么地方，到过网络的哪些部分。通过这些信息，网络提供者可以 更好地为用户提供服务，从而自己也获得更大的收益。 网络安全领域的运用。如防火墙、入侵检测等方面需要对指定流进行识 别，并给予不同的策略1 2 7 j l 鞠i 。 2 2 研究现状 目莳，国内外已经丌展了大量的基于特定流的流量测量的研究i i s l l 2 0 i 川，研究的主要内容可分为4 类：一是研究在测量时如钶标识出网络中的“大 流”。二是通过修改操作系统内核的网络协议栈，减少从内核态到用户念之间的 上下文切换。三是研究抽样测量的方法。四是研究用高性能的硬件设备满足对高 一6 一 重庆邮电学院硕士研究生论文 速网络测量的要求。 2 2 1 如何标识网络中的“大流” 文献 z o l 介绍了2 种识别网络中“大流”方法。一是抽样统计，二是多阶段 过滤统计。两种方法具有可以证明的测量准确度边界和错误概率。这种方法对内 存不敏感，它只消耗固定的内存。 抽样统计的方法如下：当一个长为三代表流，的包到达时，按1 - ( 1 - p ) l ( p 为 每一个字节被抽样的概率) 的概率决定是否对它抽样，如抽样则在流内存中加上 流f ，并对流f 的计数器增加。在s 秒后，所有超过一定阀值的流就是需要测 量的“大流”。这种抽样方法的优点，一是采用随机抽样而不是阶段抽样；二是 抽样概率是基于特定的阀值，内存溢出概率很低；三是基于包的大小来抽样，可 以保证大的数据包有较大的概率被抽样。经证明，流三在发送它流量韵5 后， 被抽样的概率为1 - e ，其值大于9 9 。意思是说，一个流如果是大流，那么在 它发送总流量的5 后，该流有9 9 的概率被系统标识为大流。 多阶段抽样是根据到达数据包的i d 计算一个h a s h 值，并基于这个值决定把 它加入到哪一个桶中。在每一个阶段，通过定义一个阀值，超过这个值的流被传 递到下一个阶段的桶中。如果过滤桶的数量足够多，那么大量的小流都会被过滤 掉。假设大流的比例为1 0 ，那么小流通过第一阶段的概率为0 1 ，通过4 个阶 段的概率为0 0 0 0 l 。如果要进一步减少小流通过的概率，只需增加过滤的阶段。 文献1 2 0 l 没有对测量过程中如何快速匹配这些“大流”进行进一步研究，而 这正是进行基于特定流流量测量的关键。 2 2 2 修改操作系统内核网络协议栈的方法 文献1 3 0 1 设计和实现了一种用于高速网络流量测量的系统l i n u x f l o w 。它修改 了l i n u x 内核的网络协议栈，专门设计了一个包括3 个模块的数据包捕获协议栈。 一是l o wc a p t u r e 模块。它的作用是，当数据包到达网络接口时，触发硬中断， 内核调用内核符号n e t i fr x 把数据包发送到网络协议栈。二是a fc a p p k t 模块。 它的作用是把a fc a p p k t 协议家簇注册至f l l i n u x 内核，并建立一个s o c k e t 接口， 用户态通过系统调用可以得到缓存的内容。三是c a p 过设置c a p类型，可以定义要捕获数据包的字段属性。_type 这种方法可以减少内核态和用户态之间上下文切换的次数，同时通过加入过 滤器，使内核只复制需要测量数据包的信息。这个测量工具可对i g b p s 链路进行 测量，但当链路带宽达到1 2 g b p s 时，丢包率达n 2 0 。 文献1 3 1 1 也采用了类似的方法。它设计了一个微内核完全代替操作系统的网 络协议栈，并且采用并行机制，利用多台主机来处理从网络捕获的流量。它能测 7 一 一重塞塑鱼芏堕堡圭婴窒兰堡奎 量的最快链路为1 g b p s 。 通过修改内核协议栈的方法比较复杂、可扩展性不好，而且在内核实现包过 滤一般会采用b p f 的c f g ( c o n t r o lf l o wg r a p h ) 模式，这种方法编制过滤规则 复杂，需要专门的训练，同时，规则数不能太多( 一般几十个到几百个) 。 2 2 3 抽样测量的研究 r f c 2 3 3 0 推荐采用p o i s s o n 抽样f 1 3 j ，它要求u ( 0 = 1 - e 。是一个服从参数五 的指数分布。但研究表明3 2 l ，因特网中数据包的到达不服从指数分布，因此测量 存在较大的误差。 c i s c on e t f l o w 是一个基于流的网络流量测量工具。它通过路由表的目的i p 来标识一个流。这种方法的流分类比较粗糙，同时对路由器性能影响较大。在高 速网络中，它多采取阶段性抽样方法，这种方法精确度不高。 由于网络数据的自相似和多分形行为特征，抽样测量的误差一般较大。因此 抽样测量方法不适合于基于用途的讣费。 2 2 4 用高性能硬件进行测量 o c x n m o n 和d a g 卡主要采用高性能的硬件设备来对高速网络中的全部流 量进行测量。文献1 1 5 1 也采用硬件的方法，在o c 一1 9 2 链路上所需的内存达到 1 0 b y t e s 以上。这些方法的最大缺点是代价昂贵。 我们在文献1 3 3 1 0 ? 对目前国内外开展的工作进行了较全面的总结。 2 3 基于特定流的流量测量系统 基于特定流的流量测量系统的基本思路是由测量管理者首先给出需要测量 的流的特征，称之为规则。在测量前对规则进行预处理，在内存中固定位置形成 流匹配关键字。在测量时，提取到来的数据包相应的特征值与内存中固定位置的 值相比较，满足要求的给出流标识并进行统计。在测量过程中，规则库保持不变， 每个流的状态也保持不变。测量系统还通过设置定时器定时从主存往辅存卸出数 据，并保持测量数据一定的粒度。 我们设计的基于特定流的流量测量系统的整体架构框图如图1 所示【3 引。它包 括规则库、预处理中心、流匹配引擎、测量数据在内存的存储和卸出控制中心、 定时器和辅存几部分。规则库用于指定要测量流的特征；预处理中心是在测量前 对规则库进行处理，在内存固定位置形成匹配特征值；流匹配引擎用于进行流匹 配，给出流标识或丢弃不匹配的包；测量数据在内存的存储和卸出控制中心用于 一8 一 一 垩鏖堕坐兰堕堡主婴壅尘堡苎一 控制测量数据在内存中存储的位置和卸出方式。辅存主要负责对测量数据进行加 密和压缩后进行存储。 图1 ：基于特定流的流量测量系统 由于对高速网络中的特定流进行测量的关键是要快速对到达的数据包进行 匹配以确定它属于哪一个流，流匹配算法的性能是对高速网络中特定流进行准确 测量的关键。因此，在论文中我们主要研究该系统中的流匹配算法，即图1 中的 预处理中心和流匹配引擎所涉及的关键技术。 基于特定流的流匹配的实质是多域数据包分类问题，它具有以下主要特征： 由于特定流的特征通常涉及到数据包的链路层、i p 层、传输层，甚至应 用层的多个特征值，因此匹配算法应能支持多个域的匹配。 匹配算法应尽可能支持掩码匹配和范围匹配，以使规则更具有灵活性和 实用性。 由于要测量的特定流是事先根据一定的需要指定的，因此匹配算法在测 量过程中不需要频繁进行规则库的动态更新。从而可以允许算法有较长的预处理 时间，遥过预处理提高匹配性能。即以预处理时间换取匹配时间。 由于特定流的特征值较多，其比特数较长，因此运用t r i e s 和h a s h 等算 法时，要充分考虑到算法的空间复杂度。 总之，流匹配算法的本质是数据包分类问题。在接下来的第三章我们将重点 讨论数据包分类算法的数学模型和基本理论，并对目前的多种数据包分类算法进 行分析。 一9 一 重庆邮电学院硕十研究生论文 第三章i p 数据包分类算法 目前，适合于流匹配的算法主要有4 类。一是b p f 算法：它采用c f g ( c o m r o l f l o wg r a p h ) 模式进行包过滤【3 4 l 。这种方法编制过滤规则复杂，需要专门的训练， 同时规则数不能太多。二是利用s r l ( s i m p l er u l el a n g u a g e ) 编写匹配规则集。 s r ll ”l 类似一种高级语言，它将匹配规则用条件语句、转移语句的形式编制成匹 配流程，这种方法采用的是线性匹配，速度较慢。三是多域包分类算法。包括 r f c ( r e c u r s i v ef l o wc l a s s i f i c a t i o n ) 、g r i do f t r i e s 、t u p l es p a c es e a r c h 、m o d u l a r 、 t t i c u t s 等。四是h a s h 算法，常见的有取模法、平方取中法、比特异或法等。h a s b 算法的主要优点是运算简单、匹配速度较快、预处理时间短、支持较大的匹配规 则集。但用于流匹配时h a s h 算法的冲突率很高，并且不能支持掩码匹配和范围 匹配。 多域数据包分类是流匹配算法的核心，其采用的理论基础、技术手段对于深 入研究流匹配算法有许多借鉴之处。因此本章对i p 数据包分类的数学理论和研 究现状进行较为全面的总结和分析，并以此为基础在第四章提出了一种改进的 r f c 算法。 3 1i p 数据包分类算法的数学理论 3 1 1 i p 数据包分类的数学模型 这部分内容给出了i p 数据包分类的数学定义，及以此为基础建立的相关数 学模型。 ( 一) i p 数据包分类的术语 定义1 ：地址d 是一个长度为w b i t s 的比特串( 一般为二值比特串，各比特取 0 和l 两个值，也可以为三值比特串，每个比特还可取值“ 1 。 定义2 ：前缀p 是长度介于0 到w 间的一个比特串，l e n g t h ( p ) 表示前缀p 的 以比特数为单位的长度。 定义3 ：如果d 开始的l e n g t h ( p ) 个比特与p 相同，就称前缀尸与地址d 匹 配。 定义4 ：包头日是有k 个域实体，包头的各个域分别表示成 州l 】，州2 ，h k 】，其中每个域都是比特串。 1 0 重庆邮电学院硕士研究生论文 定义5 ：一条过滤规则，具有k 个域。与过滤规则的一个域相关联的有一个 匹配方式，它可以是下面三种匹配方式中的任何一个：精确匹配( e x a c tm a t c h ) ， 前缀匹配( p r e f i xm a t c h ) 或范围匹配( r a l l g em a t c h ) 。 定义6 ：域f f 通过一个数值柬指定，如果包头h 的域h 【f 】与过滤规则f 的 域f 【以满足h 嘲= f 嘲，那么就称h q 与，【f 1 精确匹配。 定义7 ：域f i 】通过一个前缀来指定，如果包头h 的域h i 与过滤规则f 用 前缀表示的域f i 】匹配，那么就称h i 】与f i 前缀匹配。 定义8 ：域f 【f 】通过一个范围指定，也即， ： w ，1 ，m ，2 ，如果包头h 的 域h i 与过滤规则f 的域f i 满足v a i l h i 兰v a l 2 ，那么就称h i 与f i 】范围 匹配。 定义9 ：称过滤规则f 与包头匹配，当且仅当对h 的每个域h i 】都与f 相 应的域f i 1 匹配。h i 】与f i 的匹配方式由f i 的形式指定，可为上述三种匹配 方式中的任何一种。 ( 二) 最佳匹配过滤规则 定义1 0 ：具有n 条过滤规则的过滤规则库，k ，给定一个包头日，在，中 可能有不止一条过滤规则与h 匹配。约定，与每条过滤规则f 有一一个相关联的 4 2 q t 函数c o s t ，过滤规则f 的代价记为c o s t ( f ) 。定义最佳过滤规则匹配为在f 中查找满足下列条件的过滤规则 。： 一一以。是h 的一个匹配过滤规则： 一在吃中不存在其它的过滤规则f ，使f 与h 匹配且满足 c o s t ( f ) 3 ) 。在数据包分类中，超长方体可以重叠，这使得数据包分 类比点定位更困难，它要么对内存需求太大，要么时间太长，因此维数据包 分类要在时间和空间上取得最优的效果是非常困难的，这就是所谓的维数据 包分类的几何问题i s 9 1 1 4 0 i 。 r u l e r il ： 封j - 丹， 打j r j 图2 ：一般的规则集p 9 】 i | i i i i j l f l l h j i ) i i i t ) i ) ij i l i f l i 【f t i i ( 1 0 ，l i 图3 ：规则集用几何图形表示p 9 3 1 3 范围匹配转换成前缀匹配 任何一个范围匹配都可以转换成为前缀匹配。对于在范围【l ，明之间有个 点的范围匹配问题，可以转换成最多2 n 个前缀匹配，每个前缀的长度最多为 l o g u 3 6 1 。 r ；l i 、斗 、1 1 、“n l o i 、fl k 1 1 、“ i j j i i j i 。 h s i t l i “i i j “ l i1 4j1 1 0 0 i 州i i u i 1 i l l 一i j i i l t ， 图4 ：范围表示转换为掩码1 一1 3 一 重庆邮电学院硕士研究生论文 图4 为将范围转换成前缀的结果( 假设最长前缀w = 4 ) 。在数据包分类和 流匹配过程中，经常遇到范围匹配的问题，通常的做法是将范围匹配转换成前缀 匹配，然后利用成熟的前缀匹配方法解决范围匹配问题。 前缀匹配问题也就是一维数据包匹配，它主要用于路由表查找，也是多维数 据包分类的基础。许多多维分类算法就是通过降维，把高维分类逐步化为一维分 类，从而把问题简单化，最终取得问题的解决。常用的前缀匹配方法有：( 1 ) 采用t r i e s 和多b i t 的t r i e s( 2 ) 按前缀长度进行二分查找：( 3 ) 按前缀空间进 行二分查找。 ( 1 ) t r i e s 和多b i tt r i e s 文献 4 1 1 提出的t r i e s 方法如图5 ，前缀以二进制t r i e s 的方式存储。 浅灰节点表示前缀中止结点( 即存在从根到浅灰节点的前缀) 。 查找地址是根据地址的b i t 在图中进行周游。 如果查找中止于一个叶节点，则是一次精确匹配。 如果查找中止是因为没有找到匹配的分支，则退回到上一个最近访问过 的浅灰节点。 这种方法访问内存的次数与地址的b i t 宽度成正比。如i p v 4 为3 2 次，i p v 6 为1 2 8 次。 多b i tt r i e s 是对t r i e s 的改进1 4 l j l 4 2 l ： 多b i tt r i e s 一次匹配多个b “数。 每一次查找所需检查的比特数称为步宽( s t r i d e ) ，步宽可以是固定的， 也可以是可变的。 图5 ：t r i e s 的构造【4 1 多b i t t r i e s 极大地加快了查找速度，代价是增加了存储的空间。对于i p v 4 一1 4 重庆邮电学院硕士研究生论文 如果每步为8 b i t ，则只需4 次访存，但需要更多的存储空间。对多b i t t r i e s 的进 一步优化是采用可变的步宽，或者采用动态编程。s r i n i v a s a n t 等人提出了一神多 分支t r i e 树的优化算法。 ( 2 ) 采用前缀长度进行二分查找 为了减少查找时间，w a l d v o g e l 等人提出了在地址前缀长度空间内进行二分 查找的算法1 4 3 i ，如图6 。如果能够在前缀长度空间内实现二分查找，那么整个查 找性能就可以从o