（计算机科学与技术专业论文）大规模网络流量实时分析技术的研究与实现.pdf

国防科技大学研究生院学位论文 摘要 随着互联网规模的扩大和带宽的增加，大规模网络流量实时分析面临着流量 数据规模庞大，到达速度快的挑战。传统的基于数据库或文件系统的流量分析系 统已经无法应对这一挑战。 流数据挖掘作为一个新的研究领域给大规模网络流量实时分析提供了新的思 路。与传统数据挖掘算法不同，流数据挖掘算法通常只扫描数据一次，做出数据 摘要，提供持续的查询结果。这种技术用在网络管理中，可以迅速分析网络流量 数据，提供连续的分析结果，给网络管理、入侵检测和故障分析带来极大方便。 基于互联网流量特征，本文提出了分离最大流流量的基于多级过滤器的最大 流发现算法，将已鉴别的最大流的流量分离，有效的减少了最大流发现算法的错 误率，减少了访存次数，更为精确的估计最大流的流量。理论和实验证明，该算 法在消耗少量内存和极少访存次数的情况下，迅速准确地发现网络中存在的最大 流，并且可以给出流的持续时间等信息。该算法能够很好的适应网络规模的变化， 从而可以应用到大规模网络。同时算法的内存需求可以预先给定，在网络规模扩 大时，算法的精度也可以得到很好的控制。 本文在建立传统的基于数据库的网络管理系统n c t w a t c h c r 之后，成功地将数 据流挖掘技术集成到实时网络监控中，提供及时的流量信息，避免了存储大量流 量数据，降低了网络流量数据存储消耗。另外，系统为以后进一步添加流数据挖 掘算法提供了一个平台，方便系统扩充，以提供更多的流量信息。 最后，n c t w a t c h c r 在管理海量数据存储的互联网络中发挥了重要作用。系统 不仅能提供传统的s n m p 、s f l o w 流量情况，而且还可以实时的给出网络中存在的 最大流，极大地提高了存储系统的稳定性。 主题词：网络管理，流数据挖掘，网络流量分析 第i 页 国防科技大学研究生院学位论文 a b s t p a c t a st h ef a s te x p a n s i o no fi n t e r n e ta n dt h ee x p o n e n t i a li n c r e m e n to fn e t w o r k b 锄d 谢d m ，r e a lt i m et r a f f i ca n a l y s i so f l a r g es c a l en e t w o r kf a c e st h ec h a l l e n g ep r o p o s e d b ym a s s i v et r a f f i cd a ma r r i v i n gf a s ta n dr a n d o m l y s t r e a m i n gd a t am i n i n g , a sa n e wr e s e a r c ha r e ao f v e r y l a r g ed a t ap r o c e s s i n g , g i v e s an e ww a yt oa n a l y z en e t w o r kt r a f f i cd a t a d i f f e r e n tw i t ht r a d i t i o n a ld a t am i n i n g a l g o r i t h m , s t r e a m i n gd a t am i n i n ga l g o r i t h ms c a n st h ed a t ao n l y0 1 1 et i m e ，g i v e sd a t a s y n o p s i sq u i c k l y , a n dp r o v i d e sc o n t i n u o u sq u e r yr e s u l t s p r o b a b l ra p p l i e di nn e t w o r k t r a f f i ca n a l y s i s ，i tc a nq u i c k l ya n a l y z et r a f f i cd a t a , g i v i n gr e s u l to fp r e d e f i n e dq u e r y , w h i c hc a ng r e a t l yb e n e f i tn e t w o r km a n a g e r n e n t , i n t r a s i o nd e t e c t i o na n df a u l ta n a l y s i s b a s e do nt h ec h a r a c t e r i s t i co fi n t e m e tt r a f f i ca n dm u l t i s t a g ef i l t e r , t h i st h e s i sg i v e s an e wa l g o r i t h md e t e c t i n gl a r g ef l o wb ys e p a r a t i n gl a r g ef l o wt r a f f i c t h ea l g o r i t h m e f f e c t i v e l yr e d u c e df a l s ep o s i t i v ee l l o r sa n dm e m o r y a c c e s 8 0 s t h e o r e t i c a la n a l y s i sa n d e x p e r i m e n t ss h o w e dt h a ti tc a nq u i c k l yd e t e c tl a r g ef l o w su s i n go n l yf e wm e m o r i e sa n d m e m o r ya c c e s s e s i na d d i t i o n , t h i sa l g o r i t h mc 越b eu s e di nl a r g en e t w o r k s t h e m e m o r yr e q u i r e m e n tc o u l db ep r e d i c t e d t h ep r e c i s i o no ft h ea l g o r i t h mc o u l da l s ob e w e l lc o n t r o l l e dw h e na p p l i e dt ol a r g en e t w o r k a r e rb u i l d i n gat r a d r i o n a ln e t w o r km a n a g e m e n ts y s t e m - - n e t w a t c h e r w e s u c c e s s f u l l ya p p l i e ds t r e a m i n gd a t am i n i n ga l g o r i t h mt or e a lt i m et r a f f i ca n a l y s i sw h i c h g i v e so nt i m et r a f f i cd a t as u m m a r yw h i l ea v o i d i n gs a v i n gm a s s i v ed a t ai n t od a t a b a s et o r e d u c es t o r a g ec o s t t h es y s t e ma l s op r o v i d e da l lo p e np l a t f o r mf o rf u r t h e ri n t e g r a t i n g n e ws t r e a mm i n i n ga l g o r i t h m s f i n a l l y , n e t w a t c h e rw a su s e dt om a n a g et h ei n t e r c o n n e c t i o nn e t w o r ko fm a s s i v e s t o r a g es y s t e ma n dp l a y e dav e r yi m p o r t a n t t a l c t h es y s t e mc o u l df i n dt h el a r g ef l o wi n t h et r a f f i ca sw e l la sg i v i n gs n m p ，s f l o wt r a f f i ci n f o r m a t i o n k e y w o r d s ：n e t w o r km a n a g e m e n t ，s t r e a m i n gd a t am i n i n g ，n e t w o r kt r a f f i ca n a l y s i s 第i i 页 国防科技大学研究生院学位论文 表目录 表2 1r m o n 、n e t f l o w 和s f l o w 的信息详细程度比较1 0 表4 1 当n - - 9 时测试任务的分配。 表4 2n - - q ) 时测试任务的分配。 第1 i i 页 国防科技大学研究生院学位论文 图目录 图1 1 网络管理系统典型结构及其瓶颈 图2 1s n m p 网络管理模型 图2 2s n m p 的基本结构 图2 3s f l o w 报文格式。 图2 4r m o n ，非采样n e t f l o w 和s f l o w 的内存消耗比较【3 3 1 图2 5 传统的数据处理模型和流数据处理模型刚 图3 is a m p l ea n dh o l d 算法瞄】 图3 2 多级过滤器最大流发现算法 9 1 0 1 2 1 9 图3 3 前1 0 的流占的报文数目比例和占的b y t e 比例【3 0 1 2 0 图3 4 分离最大流流量的多级过滤器最大流发现算法2 1 图3 5 将最大流分离后，小于阀值的流的误报率。2 2 图4 1n e t w a t c h e r 的整体设计 图4 2s n m p 性能监测模块 ：! ! ； 2 6 图4 3 性能数据相关的主要的数据库表格的关系2 7 图4 4s n m p 消息类型和格式 图4 5 m i b 组变量结构 图4 6t r a p 信息结构。 图4 7 视图层主要涉及的类及关系3 0 图4 8 数据层类结构图3 1 图4 9 历史数据管理模块3 2 图4 1 0 探针服务器设计( 图中仅标出重要的属性和方法) 3 4 图4 11 目前探针节点支持的命令3 5 图4 1 2 探针程序流程图3 5 图4 1 3 流数据处理模块结构。 图4 1 4 分离最大流流量的多级过滤器类图( 主要类) 图4 1 5 不同的b i t m a p ( 2 s 。 图4 1 6g g o r m o d e 变化测试算法3 9 图5 1n e t w a t c h c r 测试环境 图5 2 接口流量图 图5 3 探针服务器收集探针数据。 图5 4 基于数据库和流数据挖掘算法的s f l o w 数据丢弃率比较。 4 2 4 2 图5 5 网络中存在的最大流4 3 2 6 7 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目：盘趣搓圜垒速量塞盟佥拉拉查盟翌究生塞盈 学位论文作者签名：l 盔i：! ：国日期：另易晦l i 月i 6 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印，缩印或扫描等复制手段保存，汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文题目：太趁搓圜垒速量塞盟金盘挂盎敛盈塞量塞煎 学位论文作者签名： 作者指导教师签名： f 舌 ，j 、鸟 穗眇 日凝：2 卯6 年f ia 区日 日期：多嬲务月w 国防科技大学研究生院学位论文 第一章绪论 1 1 课题研究背景 全世界有上百万的人每天使用互联网收发e m a i l 、浏览网页、购物、网上银行 交易、网络电话等等。大型企业使用互联网来连接各地分公司，向他们的合作伙 伴以及顾客传送各种重要信息。政府和一些非盈利组织也广泛使用互联网这种低 廉高效的通信工具。随着我们对计算机网络的依赖性的加强，对计算机可靠性的 要求也越来越高，测量和理解网络的流量对于构建可靠网络是十分关键的。 然而随着网络带宽的增加和规模的扩大，大规模网络测量面临着越来越多的 挑战。互连网松散的管理结构使得收集大规模网络流量数据非常困难，互联网提 供商通常不保存详细的流量数据。而新型的应用如p 2 p ，v o i p 更增加了网络流量 的复杂性。 网络管理和流量分析系统除了要克服上述的困难外，还需要消除因为网络流 量数据规模而导致的两个障碍：数据规模庞大和数据到达速度快。随着网络规模 和带宽指数级增长，这些问题将会更加严重因此，网络管理系统和流量测量系 统不仅要能够处理现在的流量数据，而且还要能够很好应对日益扩大的网络。 由于互联网流量测量和分析的重要性，目前存在大量的研究机构研究网络测 量，并且部署了大量系统来收集互联网的流量。但是由于前面提到的问题，这些 系统仍然不能解决很多重要的测量任务。现存的解决方案有的粒度太大，不能提 供足够的细节，有的不能适应高速链路，或者无法提取有用信息。 典型的网路管理系统结构如图1 1 示。网络管理站从设备上采集网络流量数 据，经过处理后提交给网络管理中心。但是这种方法容易给网络管理中心形成很 大的负担。有些系统的结构可能存在一定的结构差异。有些系统采用分布式结构 或者独立的多个测量系统。当时他们都有一个共同特点：在系统的一端一个或者 多个组件观察网络流量；在另一端，系统向管理员提供一些有用信息，或者产生 一些动作来调整网络。在这条路径上的所有组件都执行同样的功能：将输入的数 据转化为更加紧凑的信息，并且尽量的不丢失信息。 为了实用，网络管理员喜欢简洁的流量描述：在每级信息处理上，内存和带 宽都会成为瓶颈。在处理能力很低的时候，要精化流量描述是非常有挑战性的。 d r a m 的速度每年增加9 ，当时链路速度每年增加5 0 。d r a m 的速度现在已 经落后于链路的速度，并且这一差距将进一步扩大。因此，很多对每一个报文都 第1 页 国防科技大学研究生院学位论文 图1 1 网络管理系统典型结构及其瓶颈 进行测量的测量组件越来越来越多地使用硬件实现，但是硬件的内存( s r a m ) 和 处理资源都非常有限。即时能够将流量数据采集到，传送到处理中心的带宽也是 有限的。而在最后一级，网络管理员自身可能就是一个“瓶颈”：大量的信息超 过了他的处理能力。另外，多数流量测量数据通过u d p 传送，在网络发生异常的 时候，这些数据容易发生丢失。但在网络发生拥塞时，u d p 报文的丢弃率高达9 0 。 这将导致收集的数据非常不准确i l 】。 如果能将流量分析系统布置在网络的主干链路上，则可以大大减少流量数据 传输的失真、减少传输的代价、方便的管理大规模网络。但是，主干链路上的数 据量非常大，要将系统布置在主干链路上需要解决下面两个问题：1 、如何高速的 捕获主干链路上的流量数据。2 、如何高速的处理，存储这些数据。问题1 目前主 要由网络交换设备( 路由器、交换机) 完成。使用高速的a s i c 芯片和s r a m 储 存器，s f l o w 可以高速地分析千兆以上的网络，截取报文头部，并且发送到分析中 心。但是问题2 目前并不能很好的解决：硬件因为处理能力和内存的限制不能做 复杂的流量分析。而存储的代价也非常高，在主干的i s p 链路上，一天的流量记 录就高达1 0 g b 以上【3 2 1 。因此如何设计高效的、在线软件分析算法成为解决问题2 的主要手段。 流数据挖掘作为一个新型的研究领域，主要研究高效在线处理诸如电话记录， 金融证券管等海量数据。这类数据有如下特点：1 ) 数据源连续产生的数据以流形式 传递，大多不需保存，完整存储的代价太大。连续查询在定义好的时间间隔内实 时响应。2 ) 数据通常以不稳定速率传递，传来的数据有时是无用的。3 ) 许多聚集查 第2 页 国防科技大学研究生院学位论文 询可能需要近似解答4 ) 查询大多数情况下是预先给定的。 目前有不少的学术性项目，都处于原型阶段。代表有斯坦福大学的 s l w e a m 【2 1 ，伯克利大学的电信电话流t e l e g r a h p c q 及分布式网络监控系统 g i g a s e o p e 但是基于数据流的网络管理系统目前仍然较为少见。本文根据互联网流量特 征，提出了基于多级过滤器的最大流发现算法，设计并实现了基于数据流技术的 网络流量实时分析系统。理论和实践证明，该系统可以迅速的分析出s f l o w 数据， 发现网络中存在的最大流。系统同时提供了一个可以进一步集成其他流数据算法 的开发平台。 1 2 本文研究的内容和意义 本论文的主要研究工作包括： 1 分析了目前网络流量数据分析中存在的因网络流量数据规模庞 大，到达速度快而导致的流量数据分析问题，围绕该问题对相关 的技术和理论进行研究和分析。 2 流数据挖掘在海量数据实时分析中取得了很好的效果，其中很多 思想和算法也非常适合应用到大规模网络流量分析中，本文对流 数据算法进行了分析，从网络流量分析的角度进行了分类，同时 讨论了这些算法在网络管理中的应用。 3 基于网络流量分布不均匀的特征，提出了分离最大流流量的基于 多级过滤器的最大流发现算法。理论和实验证明算法能在极少的 空间复杂度、时间复杂度下和预先定义好的可信度下，准确地发 现网络中存在的最大流，并且能够很好的记录流的始末时间和流 量。 4 设计实现了基于数据流的网络管理系统，实时地对s n m p 、s f l o w 数据进行分析，给出网络中存在的最大流。同时为进一步集成新 的数据流挖掘算法提供了一个平台。 将数据流挖掘技术应用到网络管理和流量分析中，可以更有效的处理海量的 网络流量数据，快速的分析出网络管理和流量分析中关心的问题，为实时流量分 析提供一种新的思路。开发了一套管理管理系统n e t w a t c h e r ，并将流数据挖掘应 用到实时流量分析中，向网络管理员提供更为及时地网络流量信息。 1 3 论文的组织 第3 页 国防科技大学研究生院学位论文 本文的工作着力于研究如何应用数据流挖掘算法对网络流量数据进行在线挖 掘，为网络管理员提供及时的、准确的流量报告。分析了在线流量分析的需求， 讨论已有的相关技术，优化了查找最大流的近似算法。同时设计并且实现了 n c t w a t c h e r 网络管理系统。并且对系统进行了评测和分析。 本文的主要创新点有； 1 应用数据流挖掘算法对网络流量数据进行分析 2 根据s f l o w 的特点和互联网流量特征，提出了基于多级过滤器最大流发现 算法，更准确快速的发现网络中存在的最大流。 本文各章节的组织如下： 第一章网络管理和大规模网络实时流量分析面临的挑战，描述了为了应对这 一挑战，我们开展的课题的研究目标、研究内容、课题意义等。 第二章描述了目前的网络测量方法，包括s n m p 、r m o n 、n e t f l o w 和s f l o w ， 并且比较了它们之间的区别。详细的分析了目前的流数据管理系统，和已有的流 数据算法。并讨论了他们在网络流量分析中的应用。 第三章分析了目前的发现最大流的算法，比较了各自的特点，根据互联网络 流量分布特征，提出了基于多级过滤器的最大流算法。通过理论分析和实验，证 明了算法的正确性和有效性。 第四章介绍了n e t w a t c h c r 中网络流量监控模块的设计和实现。 第五章对n e t w a t c h e r 系统进行了分析和测试。 第六章进行了总结和下一步工作的展望。 第4 页 国防科技大学研究生院学位论文 第二章相关技术研究 随着互联网的发展，网络管理技术和流量测量技术也不断发展。网络管理系 统从简单的，集中式的体系结构发展到分布式结构，甚至出现了使用p 2 p 技术来 进行网络信的交互的网络管理系统测量技术从最开始的s n m p 技术发展到 r m o n 、n c t f l o w 和s f l o w 等细粒度，高速的报文采样、统计方法，主动测量技 术也日益丰富。通过主动发送测试报文，直接有效的测量网络的报文时延、报文 丢失率、网络抖动以及链路瓶颈等有效信息。目前广泛使用的网络流量信息是 s n m p 等的计数信息和n e t f l o w ，s f l o w 等报文统计信息，还有一些如l i b p c a p , s n i f f e r 等抓包工具捕获的报文信息。 同时数据库技术也在不断发展。一方面数据建模方式日益多样化，从层次数 据库、网状数据库、关系数据库、对象数据库，直到关系对象数据库。另一方面， 数据规模也越来越大，数据库系统从简单的本地数据发展到分布式数据库，从同 构数据库发展到可融合各种不同数据库的数据仓库。而数据挖掘也随着数据集规 模的扩大，不断发生改变，从传统的精确的，多遍扫描数据方式，发展到单遍， 快速的近似挖掘算法。流数据挖掘作为一种新型的挖掘算法，致力于研究如何高 效，准确地挖掘大规模，连续数据集。将这种算法应用到网络管理和流量分析中， 将可以迅速的分析网络流量的特征，为网络管理提供更加及时的流量信息。 本节将首先简要介绍s n m p , r m o n 、n e t f l o w 和s f l o w 等流量信息获取手段， 然后分析了流数据挖掘系统的结构和常见的流数据挖掘算法。最后从网络管理和 流量分析的角度，讨论如何将流数据挖掘技术应用到实时流量分析中。 2 1 流量测量技术和比较 不同的用户对网络流量信息需求是不同的，主要有四类用户使用流量信息。 网络的拥有者需要流量信息来决定是否应该增加网络带宽，i s p 使用网络流量来计 费，网络管理员分析网络流量来发现网络中存在的恶意行为，而研究人员和网络 操作员和生产厂商则使用网络流量信息来监视各种不同的协议在网络中的运行情 况。根据不同的需要，可以选择不同的流量测量技术。 目前广泛使用并且成为标准的网络流量测量技术主要有s n m p 、r m o n 、 n e t f l o w 和s f l o w 。下面将简要介绍这些技术，最后对这些技术进行比较和选择。 2 1 1s n m p 技术 s n m p 是为了管理t c p i p 网络提出来的模型，基本的体系机构采用管理站和 第5 页 国防科技大学研究生院学位论文 代理两级管理模式。s n m p 运行在t c p i p 上，数据的传输采用u d p 协议。 2 1 1 1s n m p 管理模型 s n m p 的网络管理模型包括以下元素：网络管理站( n m s ) ，代理，管理信息库 ( m m ) ，网络管理协议s n m p ，如图2 1 示。 用户界面 网络应用li 网络应用n is n m p 协议i l 网络管理( n m s ) l l - 。i 代i 进ib：耋程 网络协议网络协议 互连用 图2 1s n m p 网络管理模型 ( 1 ) s n m p 网络管理站 网络管理站一般是一个专用的设各，也可以利用共享系统实现，它被作为网 络管理员与网络管理系统的接口。它的基本构成为： 1 一组具有分析数据、发现故障等功能的管理程序； 2 一个用于网络管理员监控网络的接口； 3 将网络管理员的要求转变为对远程网络元素的实际监控的能力； 4 一个从所有被管网络实体的m m 中抽取信息的数据库。 ( 2 ) s n m p 代理 网络管理系统中另一个重要元素是装备s n m p 平台的主机、交换机、路由器 等均可作为代理工作。代理对来自管理站的信息请求和动作请求进行应答，并随 机地为管理站报告一些重要的意外事件。 ( 3 ) 管理信息库( m i b ) s n m p 中的对象是表示被管资源某一方面的数据变量，对象的集合被组织为 管理信息库( m i b ) ，由管理信息结构s m i ( s t r u c t u r eo fm a n a g e m e n ti n f o r m a t i o n ) 对 其进行定义管理站通过读取m m 中对象的值来进行网络监控。管理站可以在代 理处产生动作，也可以通过修改变量值改变代理处的配置。 ( 4 ) s n m p 协议 管理站和代理之间通过网络管理协议s n m p 通信，8 n m p 协议支持的操作主 要包括： 1 g e t ：管理站读取代理中对象的值； 第6 页 国防科技大学研究生院学位论文 2 s e t 管理站设置代理中对象的值； 3 t r a p ：代理向管理站通报重要事件。 在标准中，没有特别指出管理站的数量及管理站与代理的比例。一般地应至 少要有两个系统能够完成管理站功能，以提供冗余度，防止故障。另一个实际问 题是一个管理站能带动多少代理。只要s n m p 保持它的简单性，这个数量可以高 达几百。 2 1 1 2s n m p 协议体系结构 s n m p 是应用层协议，属于t c p i p 协议族的一部分。在分立的管理站中，管 理站进程通过s n m p 协议完成网络管理。而s n m p 是在u d p ti p 及有关的其他网 络协议( 如：e t h e m e t , f d d lx 2 5 ) 之上实现的。 s n r m p 协议支持的主要的消息有：g e t r v q u c s t , g c t n e x t r e q u e s 4s e t r e q u e s t , g c t r e s p o a s e 及t r a p 。从管理站发出三类与管理应用有关的s n m p 的消息； g e t r e q u e s t , g e t n e x t r e x i u e s t , s e t r e q u e s t 。这三类消息都由代理用g c t r e s p o n s e 消息 的形式来应答，并将该消息上交给管理应用程序另外，代理还可以发送t r a p 消 息，向管理者报告有关m 璐及底层被管理资源的意外事件。图2 2 给出了s n m p 协议的基本结构。 由于s n m p 依赖u d p ，而u d p 是无连接型协议，所以s n m p 本身也是无连 图2 2s n m p 的基本结构 接协议。在管理站和其代理之间不维持连续连接，相反每一次信息交互都是管理 站和代理之间的独立行为。 2 。1 2r m o n r m o n 是i e t f 定义的m i b ( r f c l 7 5 7 ) ，是对s n m p 标准的扩展，它定义了标 准功能以及在基于s n m p 管理站和远程监控者之间的接口，主要实现对一个网段 第7 页 国防科技大学研究生院学位论文 乃至整个网络的数据流量的监视功能，目前已成为成功的网络管理标准之一。 r m o n 是对s n m p 的重要增强，它所定义的m i b 被补充为m i b 11 ，并且提供 了有关互联网络的关键信息，使s n l v i p 更为有效、更为积极主动地监控远程设备。 单纯利用s n i v i p 的管理者代理( m a ) 工作模式，可以获取单个网络设备的信息，但 不易获取l a n 上整个的信息流量通常我们将用于研究网络整体流量的设备称为 网络探测器，或者网络分析器、探测器。探测器通过监听方式在u 蝌上运行，以 监视l a n 上的每一个包。探测器可以产生统计信息，包括错误统计，如小于规定 大小的包的个数和冲突数量：性能统计，如每秒传递的包数以及包的大小分布。探 测器还可以存储全部或部分的报以供以后分析使用，并使用过滤器根据包的类型 或包的其它特性来限制计数或捕获的数据包个数。利用r m o n ，可以有效地监视 l a n 上的每一个数据包，同时又不会对网络性能造成较大的影响。 r i v i o n 的规范主要是一个m i b 的定义( r f c l 2 7 0 。它定义了标准网络监视功 能以及在控制台和远程探测器之间的通信接口。它提供了一个有效的方法，可以 在降低其它代理和控制台负载的情况下监视子网行为。r i v l o nm i b 由一组统计数 据、分析数据和诊断数据构成，利用许多供应商生产的标准工具都可以显示出这 些数据，因而它具有独立于供应商的远程网络分析功能。r m o n 探测器和r m o n 客户机软件管理站结合在一起在网络环境中实施r m o nor m o n 的监控功能是否 有效，关键在于其探测器要具有存储统计数据历史的能力，这样就不需要不停地 轮询才能生成一个有关网络运行状况趋势的视图。 2 1 3n e t f l o w n e t f l o w 是c i s c oi o s 软件内嵌的一种功能，用来将网络流量记录到设备的高 速缓存中，从而提供非常精准的流量测量。由于网络通信具有流动性，所以高速 缓存中记录的n e t f l o w 统计资料通常包含转发的口信息。输出的n e t f l o w 统计数 据可用于多种目的，如网络流量核算、基于使用的网络付费、网络监控以及用于 商业目的的数据存储。路由器和交换机输出的n e t f l o w 数据记录由过期的数据流 及详细的流量统计数据组成。这些数据流中包含与第三层源和目的相关的信息， 以及端到端会话使用的协议和端口。这些信息能帮助r r 人员监控和调整网络流量， 及面向网络有效地分配带宽。 2 1 4s f i o w s f l o w ( r f c 3 1 7 6 ) 是2 0 0 1 年被i e t f 批准成为一项草案标准的一种网络监测 技术，它利用对整个网络上传送的局域网和广域网数据包流的随机采样，让用户 详细、实时地掌握网络传输流的性能、趋势和问题。 第8 页 国防科技大学研究生院学位论文 与数据包采样技术( 如r m o n ) 不同，s f l o w 是一种导出格式，它增加了关 于被监视数据包的更多信息，并使用嵌入到网络设备中的s f l o w 代理转发被采样 数据包，因此在功能和性能上都超越了当前使用的r m o n 、r m o n 和n e t f l o w 技术。s f l o w 技术独特之处在于它能够在整个网络中，以连续实时的方式监视每一 个端口，但不需要镜像监视端口，对整个网络性能的影响也非常小 s f l o w 使拥有高速千兆和万兆端口的网络能够得到精确的监视，同时经过扩 展，可以在一个采集点上管理数万个端口。因为s f l o w 代理嵌入在网络路由器和 交换机a s i c 中，所以与传统的网络监视解决方案相比，这种方法的实施成本要低 得多，而且也不需要购买额外的探针和旁路器，就能全面监视整个网络。与那些 需要镜像端口或网络旁路器，来监视传输流量的解决方案不同，在s f l o w 的解决 方案中，并不是每一个数据包都发送到采集器( 接收s f l o w 数据包的设备) 。s f l o w 使用两种独立的采样方法来获取数据：针对交换数据流的基于数据包统计采样方 法和针对网络接口统计数据的基于时间采样方法。 s f l o w 还能使用不同的采样率，对交换机或仅对其中一些端口实施监视，这样 保证了在设计管理方案时的灵活性。 s f l o w 需要网络交换设备硬件支持。如果硬件设备不支持，则需要在端系统上 开发s f l o wa g e n t 。 采集到的数据以u d p 报文发送到采集器。一个数据包主要分为三大部分：a 数据的包头部分，b 。样本的具体信息，c 接口统计信息。以一个s f l o w 数据版本号为 2 的基本数据包为例，在数据的包头部分包含s f l o w 数据的版本信息，a g e n t 的m 地址、采样包的序列号、采样的样本数、系统采样时间等信息。其中采样的样本 数，就是指该包中所含s a m p l e 数据的个数。在一单位s a m p l e 的数据中，首先是采样 的标识号( s a m p l ei d ) 、输入和输出端口号等信息；然后是采样来的原始数据包头信 息，这个包头包括口以及相应协议i c m p u d p f r c p 的相关数据，最后是部分可选的 扩展数据。其中i p i c m p u d p t c p 等按照相应首部格式进行解码。s f l o w 报文 结构如图2 3 示。 臣亟三工五区正亟匠 = 三盈 图2 3s f l o w 报文格式 2 1 5 各种技术的比较 s n m p 是t c p i p 协议族的一部分，嵌入在各种t c p i p 协议中，提供基本的 接口计数信息和协议信息。而r m o n 、n e t f l o w 和s f l o w 通常都是采用嵌入式系 统实现的a g e n t 系统，因此与s n m p 差异较大。本节将主要对r m o n 、n e t f l o w 第9 页 国防科技大学研究生院学位论文 和s f l o w 进行比较。 1 a g e n t 的资源消耗 1 对处理能力的消耗。r m o n 对每个数据报文进行处理，提取出信息后，存 入数据库，把流量信息按照a s n 1 的格式进行编码，以s n m p 数据包发给管理站。 n e t f l o w 即可以处理逐个报文进行处理，在繁忙的时候也进行采样，然后把流量用 n e t f l o w 报文发送到管理站s f l o w 直接将采样的数据报文部发送到管理站。因此 r m o n 和非采样n e t f l o w 对a g e n t 处理能力要求最高，采样的n e t f l o w 和s f l o w 对处理能力要求低。 。? 2 。对内存的消耗。在不同的时间r m o n 和n e t f l o w 内存的消耗不一样，s f l o w 在固定了采样率和轮训间隔后，内存消耗保持不变。图2 4 比较了它们对内存的需 求。 内 存 消 耗 时间 图2 4r m o n ，非采样n e t f l o w 和s f l o w 的内存消耗比较p 1 2 信息的精确性和详细程度 1 信息的精确性：r m o n 和n e t f l o w 可以对每个报文进行处理，因此信息的 精确性要比采样的n e t f l o w 和s f l o w 要高，但是数据量也大。 2 内容的详细程度：r m o n 和n e t f l o w 都对报文进行过处理，损失了一些报 文头部信息，而s f l o w 则将整个报文头部发送给管理站，信息的内容最为 丰富。表2 5 给出了它们的内容丰富程度比较。 表2 1r m o n 、n e t f l o w 和s f l o w 的信息详细程度比较 r m d n r m o n n e t f l o ws h o w 报文捕获 蛩j y ；，n ，之。 p 协议信息 pp ，。4 。奠二。：i y 链路层信息 “零n ? j ? p 毒，t 群”鼍 y 网络层信息 kn 擘 孑j _ n - o yy b g p 4 ；醪o i曩i ；啦l j 。n py ( 衷注：n 表示不支持，p 表示部分支持，y 表示完全支持) 第l o 页 国防科技大学研究生院学位论文 2 2 流数据挖掘相关研究 上一节介绍了四种普遍使用的流量数据获取手段，并对它们的特点进行了比 较。s n m p 数据相对而言规模较小，在轮询频率较低的情况下，可以将数据存入 数据库，便于以后进一步分析而r m o n ，n e t f l o w 和s f l o w 数据如果完全存储， 则规模庞大，不便于分析和查询，存储的代价也非常高。在管理集群服务器的互 连网络时，s f l o w 数据一天就可累积达到数gb y t e 。如何在线的处理这些流量数据 是实现大规模网络流量实时分析的关键技术。 ，数据流挖掘技术这一新型的研究领域为大规模，连续数据处理提供了新的思 路。与传统的数据挖掘技术不同，数据流挖掘不再追求精确的挖掘结果，而是将 问题放宽，在非常小的时间复杂度和空间复杂度下，迅速的处理连续到达的数据， 输出预先定义好的查询结果。这使大规模数据实时处理成为可能。 在网络管理中，有一定可信度的近似信息并不影响决策( 如路由调整、故障排 查) 的制定，相反，如果信息的滞后性却会严重影响一些决策的制定。因此针对 网络流量数据的规模和分析结果的可近似性，可以将流数据挖掘技术应用到网络 管理中，获得实时的流量信息，为管理员了解当前网络的运行状况提供依据。 本节将介绍流数据挖据的概念，流数据处理的通用模型和常用的流数据挖掘算 法。 2 2 1 流数据模型 根据s m u t h u k r i s h a n 在【1 4 】中的定义，数据流是指输入数据a i ，4 ，按顺序到 达，这些数据描述了一个信号a 。a 是一个一维函数4 ：【1 j 叼一r 2 。模型取决于 西如何描述a 。三种常用的数据流模型是时间序列模型( t i m es e r i e sm o d e l ) ，收 银机模型( c a s h r e g i s t e r m o d e l ) 和转门模型( t u r n s t i l e m o d e l ) 。时间序列模型是 指每个q = ( 工) 是箕刀的更新，即4 【刀= ，并且- a i 按照f 递增的顺序到达。收 银机模型指q f f i ( j ，) 是趣刀的一个增i r i , o ，即4 d 3 = 4 - l 【刀十。转门模型 与收银机模型类似，但是l 可以小于0 。 数据流模型也可以根据不同的时序范围可以划分成多种子模型，包括界标模型 ( 1 a n d m a r km o d e l ) 、滑动窗口模型( s l i d i n gw i n d o wm o d e l ) 和快照模型( s n a p s h o t m o d e l ) 0 1 】令n 表示当前时间戳，s ，e 分别是两个已知的时间戳。界标模型的查 询范围从某一个已知的初始时间点到当前时间点为止，即 a | ，a n ) 。滑动窗口模 型仅关心数据流中最新的w ( w 也称为滑动窗口大小) 个数据，其查询范围是 a 。睡w + l 加，a n ) ，随着数据的不断到达，窗1 3 中的数据也不断平移。快照模型则 第u 页 国防科技大学研究生院学位论文 将操作限制在两个预定义的时间戳之间，表示为( a s ，a c 。界标模型和滑动窗口模 型由于要不断处理新来的数据，更接近于真实应用，因而得到更加广泛的研究。 区别于传统应用模型，流数据模型具有以下4 点共性：( 1 ) 数据实时到达；( 2 ) 数据到达次序独立，不受应用系统所控制；( 3 ) 数据规模宏大且不能预知其最大值； ( 4 ) 数据一经处理，除非特意保存，否则不能被再次取出处理，或者再次提取数据 代价昂贵利用传统技术处理这种模型，必须将数据全部存储到介质中，然后通过 提交d m l 语句访问存储介质来获取查询结果旭是，由于数据规模宏大且到达速 度很快，传统技术难以满足实时要求。 2 2 2 流数据分析系统结构 设计单遍扫描算法( o n e - p a s sf l g o f i t h m ) ，实时地给出近似查询结果是数据流模 型下数据处理的目标。算法的关键在于设计一个远小于数据集规模的结构，从而 可以在内存中处理数据。相对于数据流的规模而言，这种名为概要数据结构 ( s y n o p f i sd a t as t r u c t u r e ) 的规模至多应该是次线性的。即如果流的长度为n ，则概要 数据结构大小不超过o ( p o l y l o g ( n ) ) ，并且处理流上每一组数据的时间不超过 o ( p o l y l o g ( n ) ) 。图2 5 显示了传统数据处理技术和数据流处理技术的差异。 图2 5 传统的数据处理模型和流数据处理模型m 1 从图2 5 可以看出，传统的数据处理技术将所有数据存放到数据库或者数据仓 库中；系统响应用户提交的d m l 语句，搜索数据存储媒介，返回查询结果当数 据规模很大时，数据往往以磁盘或者磁带为介质，因而执行查询操作需要大量的 f o 交换，效率低下，不能适应实时系统的需求。相反，新的流数据处理技术并不 保存整个数据集，仅维护一个远小于其规模的概要数据结构，从而能够常驻内存。 流数据处理技术往往包含两部分算法，一部分监控流中的数据，更新概要数据结 构；另一部分响应用户查询请求，返回近似查询结果。