（信号与信息处理专业论文）基于voip的网络性能数据的挖掘方法研究与应用.pdf

气 l j 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：囱堡型型 日期： 圣型里! 兰：1 2 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即：研究生在校 攻读学位期间论文：1 j 作的知识产权单位属北京邮电人学。学校有权保留并向国家有关部门或 机构送交论文的复印件和磁盘，允许学位论文被夯阅和借阅；学校可以公布学位论文的全部 或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编学位论文。( 保密的学位 论文在解密后遵守此规定) 非保密论文注释：本学位论文不属于保密范围，适用本授权书。 本人签名：血垂坦丛日期：兰! 丝：主：坦 导师签名：垒垒垄奎 日期：圣! ! ! ：! ：2 0 基于v oip 的网络性能数据的挖掘方法的研究与应用 摘要 在网络管理领域，网络故障的定位问题受到越来越多的关注。而 利用数据挖掘方法从网络性能数据中挖掘出网络性能数据与故障之 间的关联模式是一个新的研究热点。 针对网络性能数据挖掘中的几个关键问题，本课题对网络性能数 据的特点进行了详尽的分析，同时研究了目前常见的网络性能数据处 理方法，发现了一些重要的特征，并基于此提出了一种基于序列特征 分析的网络性能数据处理方法。本文试图将这种数据处理方法应用于 以v o l p 业务为基础盯网络性能数据特征统计分析和数据挖掘过程之 中，以找出有价值的关联模式。 随后，我们使用o p n e t 设计了一系列基于v o l p 业务的网络故 障场景模型，对这些场景进行仿真分析和数据挖掘处理，并成功的挖 掘出网络性能数据特征与网络中的故障之间的关联关系模式。实验数 据表明，我们提出的基于序列特征分析的网络性能数据处理方法能有 效地对网络中的性能数据进行特征统计分析及关联模式挖掘，并且能 将挖掘得到的关联模式应用于网络故障的分析与定位。 关键词：网络性能数据，网络故障，数据挖掘，v o l p ， 、 ， ： j r e s e a r c ha n da p p l i c a t i o no fd a t am i n i n go fn e t w o r k p e r f o r m a n c ed a t ab a s e do nv o i p a b s t r a c t t h ei s s u eo ff a u l tl o c a t i o nr e c e i v e de x t e n s i v ec o n c e r ni nt h ef i e l do f n e t w o r km a n a g e m e n t t h ed a t am i n i n ga p p r o a c h e sa r ei n t r o d u c e dt o e x t r a c tc l u e sf r o mt h en e t w o r kp e r f o r m a n c ed a t af o rf a u l tl o c a t i o n a i m i n ga tt h ek e yp r o b l e m si nn e t w o r kd a t am i n i n g ，w eh a v em a d ea c o m p r e h e n s i v ea n a l y s i s o nt h en e t w o r kp e r f o r m a n c ed a t aa n dt h e m e t h o d so fp r o c e s s i n gn e t w o r k p e r f o r m a n c ed a t a ，s o m ei m p o r t a n t c h a r a c t e r i s t i c sa r ed i s c o v e r e d ，a n dad a t ap r o c e s s i n gm e t h o db a s e do n a n a l y s i so fn e t w o r kp e r f o r m a n c ed a t ai sb u i l tt oh e l pu st oe x t r a c tt h e c l u e sb e t w e e nn e t w o r k p e r f o r m a n c e d a t aa n dn e t w o r kf a u l t w eu s eo p n e tt od e s i g nas e r i e so fv o l p b a s e dn e t w o r km o d e l s c e n a r i o sa n ds i m u l a t et h e s en e t w o r km o d e ls c e n a r i o s t h e nw ed o a n a l y s i sa n dd a t am i n i n go nt h es i m u l a t ep e r f o r m a n c ed a t aa n de x t r a c tt h e 。 c l u e sb e t w e e nn e t w o r kp e r f o r m a n c ed a t aa n dn e t w o r kf a u l ts u c c e s s f u l l y , w h i c hh a sag r e a tb e n e f i tt ot h en e t w o r km a n a g e rf o rf a u l tl o c a t i o n k e yw o r d s ：n e t w o r kp e r f o r m a n c ed a t a , n e t w o r kf a u l t ，d a t am i n i n g ， v o i p r。、l 1 2 网络管理概述l 1 3 v o i p 介绍3 1 4 研究目的和内容4 第二章网络性能数据的获取及预处理6 2 1 网络性能数据的获取及其特性6 2 1 1 网络性能数据的获取6 2 1 2 网络性能数据特性7 2 2 数据挖掘方法概述8 2 3 序列距离特征表示9 2 4 序列特征表示9 2 5 序列挖掘算法1 0 2 5 1 序列关联规则挖掘1 0 2 5 2 序列分类算法l o 2 5 3 序列聚类算法1 0 2 5 4 趋势分析和预测1 l 第三章常见网络性能数据处理方法1 2 3 1 网络性能数据预处理和查询1 2 3 2 网络性能数据挖掘方法介绍1 3 3 2 1 基于已知模式的方法1 3 3 2 2 基于决策树的方法1 3 3 2 3 基于矢量分类和聚类的方法，1 4 3 2 4 基于神经网络的方法1 5 第四章基于序列特征分析的数据处理方法及实现1 6 4 1 基于序列特征分析的数据处理方法介绍1 6 4 2 网络性能数据序列样本获取1 6 4 3 网络性能数据预处理，1 8 4 3 1 预处理基本流程1 8 4 3 2 预处理实现方法1 9 4 4 网络性能数据序列聚类2 l 4 4 1 序列聚类算法2 1 4 4 2 序列聚类举例2 3 4 5 网络性能数据挖掘过程2 4 4 5 1 数据挖掘工具w e k a 介绍2 4 4 5 2 网络性能数据值聚类2 6 4 5 3 网络性能数据变化趋势聚类2 7 4 6 网络性能数据挖掘结果处理2 8 4 6 1 性能数据特征呈现2 8 4 6 2 基于决策树的挖掘结果表示2 9 4 6 3 挖掘结果的关联规则表示3 1 第五章实验仿真与分析3 4 5 1 实验设计3 4 5 1 1 v o l p 网络建模3 4 5 1 2 网络故障设置3 7 5 2 实验仿真与数据处理3 9 5 3 实验结论4 6 第六章j i ：作总结和展望4 9 6 1 本文内容总结4 9 6 2 未来研究与展望5 0 参考文献5 l 致谢5 2 攻读学位期间发表的学术论文目录5 3 符号说明 、，o i pv o i c eo v e ri n t e m e tp r o t o c o l w a i k a t oe n v i r o n m e n tf o r k n o w l e d g e w e k a a n a l y s i s ( 怀卡托智能分析环境) s v ds t a n d a r dd e v i a t i o n 标准差 m a xs a m p l e序列样本最大值 m i ns a m p l e序列样本最小值 s a m p l ea v e r a g e 序列样本均值 s a m p l es d v序列样本标准差 r e g r e s sk 序列样本回归系数 r e g r e s sr 2序列样本回归判定系数 l a r g e rs a m p l e sd i s t r i b u t i o n序列样本最大值分布 s m a l l e rs a m p l e sd i s t r i b u t i o n序列样本最小值分布 北京邮电人学硕j ：学位论文罐于v o l p 的网络性能数据的挖掘方法研究j 应用 1 1 研究背景 第一章绪论 网络通信技术在过去的二十多年里深刻地改变了人类的生活，已经成为生活 不可缺少的一部分，网络通信技术的进步一直伴随着人类同常的生活。在科学技 术高速发展的今天，网络深刻地介入了人类的生活，颠覆性的改变了人类的生活 方式。今天的网络正日益承担着越来越多、越来越重要也越来越复杂的事务。 然而随着计算机及通信技术的不断进步，全世界的网络日益发展，主要体现 在网络的规模不断扩大，网络中承载的服务的种类不断增多，网络中各种设备的 复杂程度不断提升，同时网络的异构性和复杂性也显著提升。有了网络，势必 需要对它进行管理，使网络能够正常、安全、高效、合理的运行和使用，这是就 网络管理。在这样的网络环境中，伴随着网络中各种设备的运行，会产生大量的 网络数据信息。这些网络数据信息是网络人员判断网络当前状态及相关故障并提 出修复方案的重要依据。但由于网络数据信息的数据量同趋增大，而网络管理人 员对于故障定位的实时性的要求又不断提高，如何快速有效地利用网络数据信息 进行故障根源定位，进而找出网络性能数据与网络故障之间的关联关系以及网络 性能数据与网络所承载的业务之间的关联模式，成为当前被学界广泛关注的焦 点。 1 2 网络管理概述 随着网络技术与应用的不断发展，计算机网络在我们的日常生活中己经变得 越来越普遍。特别是2 0 世纪9 0 年代以来，随着i n t e r n e t 在世界范围的普及，计算 机网络逐渐成为人们获取信息、发布信息的重要途径。与此同时，基于计算机网 络的应用也越来越多，许多人们生活中的重要环节都可以利用网络方便、快捷地 实现。金融网络、邮电网络等等各种专业大型网络的发展使得大到国家经济命脉 小到个人日常生活严重依赖于计算机网络。因此，网络运行的稳定性、可靠性就 显得至关重要，于是网络管理就应运而生。网络管理是计算机网络发展的必然产 物，它随着计算机网络的发展而发展。 网络管理是指对网络的运行状态进行监测和控制，使其能够有效、可靠、安 全、经济地提供服务髓1 。从这个定义可以看出，网络管理包含两个任务，一是对 网络的运行状态进行监测，通过监测了解当前状态是否正常，是否存在瓶颈问题 北京邮电人学硕i ：学位论文 基于v o l p 的i 自9 络性能数据的挖掘方法研究j 应用 和潜在的危机；二是对网络的运行状态进行控制通过控制对网络状态进行合理调 节，提高性能，保证服务。监测是控制的前提，控制是监测的结果。 通过网络管理，使网络中的各种资源得到更加有效的利用，以维护网络的正 常运行，并为网络性能的改善提供全方位的动态支持。特别是当网络出现故障时， 网络管理系统要能及时地报告和处理，并协调和保证网络的高效运行。网络管理 的发展大致分为四个阶段：专业网络系统的管理、通信网络设备的管理、综合网 络的管理和综合智能网络系统的管理。其发展阶段如图卜l 所示。 专业网络系统 的管理 1 9 6 9 1 9 通信网络设备 的管理 1 9 陷2 0 综合网络 的管理 2 d 叩现在 综合智能网络 系统的管理 未来 图卜1 网络管理技术的发展阶段 国际标准化组织i s o 将网络管理的功能划分为5 个管理功能域 m f a ( m a n a g e m e n t f u n e t i o n a r e a ) ：故障管理( f a u l t m a n a g e m e n t ) 、性能管理 ( p e r f o 瑚a n e e m a n a g e m e n t ) 、配置管理( c o n f i g u r a t i o n m a n a g e m e n t ) 、计费管理 ( a e e o u n t i n g m a n a g e m e n t ) 和安全管理( s e e u r i t y m a n a g e m e n t ) 。具体如下所述： 1 故障管理就是对网络中的故障进行检测、诊断和恢复，其目的是保证网 络能够提供连续、可靠的服务。主要功能包括： 定义和管理配置信息： ， 设置和修改配置参数值和属性值： 开通和终止网络服务： 配置网络中软件的参数； 2 性能管理是以网络性能为准则，负责收集、分析和调整管理对象的状态， 其目的是保证在使用最少网络资源和最小延迟的前提下，网络提供可靠、连续的 通讯能力。分为性能监测和性能控制两部分。性能监测指工作状态信息的收集和 整理，性能控制则指为改善网络设备的性能而采取的动作和措施。 3 配置管理是网络管理的起点和基础，它负责对网络全局的状态进行跟踪， 了解当前网络资源的应用情况，关键部分是对网络资源即网络对象的定义、存储、 定位及操作。因此，网络配置管理功能至少包含： 识别网络拓扑结构，标识网络中的管理对象； 自动修改指定设备的配置： 动态维护网络数据库等等； 4 计费管理记录用户使用网络资源的情况并核收费用。计费管理系统的设 计目标应使系统具有如下功能：以用户或网络主机使用网络资源的情况为依据， 根据管理策略对使用者进行收费。通过收费政策，使网络资源合理使用：通过收 集各种访问信息，调整网络结构，提高网络使用效率。 5 安全管理是对网络资源的访问提供保护，包括授权机制、存取机制、加 2 北京邮电大学硕，i ：学位论文基于v o l p 的网络性能数据的挖掘方法研究j 应用 密及密钥管理以及有关安全访问日志的维护。一般的安全措施主要分为两类：加 密技术和防火墙。 在未来，网络必将深入人们生活的各个方面，而保证网络高效运行的网络管 理系统也必将成为影响网络更快发展的关键技术，受到越来越多的重视。将来， 不仅电信运营商和大企业需要网络管理系统，d , n 网络社区，甚至网络用户都需 要网络管理系统。 - 1 3 v o l p 介绍 v o l p ( v o i c eo v e ri n t e r n e tp r o t o c 0 1 ) 是一系列使用i p ( i n t e r n e tp r o t o c 0 1 ) 网络进行语音通信的技术的集合n 1 。v o p i 系统利用p i 网络来传输信令和流媒体， 并建立和拆除通话连接以使得用户可以进行交流。这些信令和流媒体都是通过 i p 报文的形式来进行传送的，因此v o i p ，又被称之为“p a c k e tt e l e p h o n y 。目 前，v o l p 技术主要有三种形式：桌面应用，电话服务和企业电话系统。v o l p 作为 一种核心技术，使得p c p c ，p c p h o n e ，p h o n e p h o n e 的同网络和跨网络 互通成为可能n 1 。现在普遍认为，v o i p 将是下一代正网络技术的核心应用之一。 事实上，v o l p 中的很多技术已经被开发多年睛1 。例如，在v o i p 中最广泛使 用的语音压缩协议g 7 1 1 在1 9 7 2 年就己经被应用在用长距离电话电缆传输语音 上了。而i n t e r n e t 作为v o i p 基础设施的一部分，是从2 0 世纪6 0 年代开始发展 的，目前已经成为了世界上最大的计算机互联网络。m i c r o s o f t 公司在2 0 0 0 年 将n e t 2 p h o n e 产品和m s nm e s e s n g e r 产品相捆绑，使得许多用户第一次尝到了 v o l p 的甜头，但是由于当时网络基础设施相对落后，缺乏宽带和高速的i n t e r n e t 接入服务，v o l p 用户经常能感受到明显的延时和断续。直到2 0 0 1 年1 月，v o n a g e 公司宣布开始为企业用户提供v o i p 解决方案。这被看作是v o l p 发展史上的一个 里程碑，因为v o i p 进入商业领域意味着对该技术的严格考验，并标志着v o l p 技 术已经可以进入广泛使用阶段。 在数据网络上进行v o l p 电话呼叫首先需要建立呼叫，即用v o i p 来实现获得 拨号音、拨号、得到回铃音或忙音、摘机、通话、挂机，这一系列活动v o l p 协 议需要以下步骤的实现陋1 ： 1 呼叫建立协议 使用一些高层协议来完成呼叫的建立和拆除，常用的协议有：h 3 2 3 、s p i 、 s c c p 、m g c p 和m e g a c o h 2 4 8 等。这些协议都是基于t c p 和u d p 来交换数据和信 令的。 2 媒体流协议 呼叫建立之后，开始传送编码后的语音数据。由于是全双工的对话，语音流 3 北京邮i 乜人学硕1 ：学位论义基于v o i p 的网络性能数据的挖掘方法研究畦用 同时向对话双方即两个方向传输。在此传输过程中使用的协议被称为r t p ( r e a l t i m et r a n s p o r tp r o t o c o l ，实时传输协议) 。r t p 使用u o p 作为底层传输协议。 v o l p 网络中的网络性能指标对各种网络业务或应用的性能都有一定的影响， 但对于具体的业务类型或应用，还需具体分析。常见的网络性能指标包括以下几 种： 1 延迟 网络延迟是指报文在指定两点问的往返时间。网络延迟的确定常需测量往返 时间( r t t ) ，即一个数据包自客户机到服务器间往返所需的时间间隔。 2 丢包率 网络丢包率是指在一特定时间间隔，从客户机到服务器问往返过程中丢失的 数据包占所发送数据包的百分比数。 3 吞吐量 吞吐量一般指链路上所有通信数据总的传输速率，有时也可以表示某特定业 务的数据传输速率。 4 链路使用率 链路使用率就是指特定时间间隔吞吐量占链路接入速率的百分比。 5 带宽 带宽是网络的一种重要资源，根据带宽测量的目标不同，带宽测量可分为链 路带宽测量、端到端瓶颈链路带宽测量和端到端可用带宽测量，它们相互关联而 又有所区别。 1 4 研究目的和内容 现在，网络规模和复杂性的不断增加，网络管理及维护变得越来越困难。现 有的网络管理系统往往是以“事后处理 为出发点。能否使用技术手段来预测到 即将产生的网络故障? 能否根据现有网络运行数据的特征及变化趋势预测到某 些设备节点可能发生故障的概率? 以便及时的作出判断，避免运行事故的发生， 则是本文研究的目的。 在本课题中主要研究网络性能数据特征与网络故障之间的关联关系模式。 v o l p 业务为出发点，运用网络仿真工具构建典型的网络拓扑和故障场景，收集 网络中不同网络故障情境和不同网络情境下的网络仿真数据结构，监控并收集网 络层相关性能指标如端到端时延、时延抖动、应呼比、呼损率、应答率、成功率 等等。研究的思路总共分为4 个阶段，如图1 - 2 所示： 4 北京邮电人学硕- i - 学位论文基十v o l p 的网络性能数据的挖掘方法研究0 应用 图卜2 课题研究思路 阶段1 为数据准备阶段，主要构建基于v o l p 业务的网络拓扑并进行实验仿 真和实验数据收集；阶段2 为数据预处理阶段，主要对性能数据序列进行预处理 操作；阶段3 为数据挖掘阶段，主要对预处理后的序列样本进行数据挖掘分析； 阶段4 为挖掘结果分析阶段，主要对挖掘结果进行分析以及关联规则的呈现 并提出了一种运用数据统计分析、数据挖掘等技术对仿真数据进行处理的方 法，用以发现网络性能数据与网络故障之间的关联模式。其价值在于：当发现了 网络性能数据与网络故障之间的关联模式后，一方面当监控到网络性能数据发生 变化时，可根据这些关联模式推断出网络故障的发生，以实现网络故障的快速定 位和恢复，从而减少业务不能正常运行的第一个症状到确认所需要的故障修复所 需要的时间。另一方面，当网络中的设备发生故障时，通过关联模式实现影响分 析，可以预测受该故障影响的相关网络性能参数及相关业务和客户。最后通过一 系列的实验验证了该方法的可行性及有效性。 5 北京邮i 乜人学硕卜学位论文基于v o l p 的网络性能数据的挖掘方法研究j 应用 第二章网络性能数据的获取及预处理 2 1 网络性能数据的获取及其特性 2 1 1 网络性能数据的获取 网络性能数据的获取可以分为主动测量和被动测量两种方法。其中主动测量 是在选定的测量点上利用测量工具有目的地主动产生测量流量注入网络，并根据 测量数据流的传送情况来分析网络的性能口1 。 主动测量在性能参数的测量中应用十分广泛，因为它可以以任何希望的数据 类型在所选定的网络端点间进行端到端性能参数的测量。最为常见的主动测量工 具就是“p i n g ”，它可以测量双向时延，i p 包丢失率以及提供其它一些信息， 如主机的可达性等。因为一次主动测量只是查验了瞬时的网络质量，因此有必要 重复多次，用统计的方法获得更准确的数据。 主动测量法依赖于向网络注入测量包，利用这些包测量网络的性能，因此这 种方法肯定会产生额外的流量。另一方面，测量中所使用的流量大小以及其他参 数都是可调的。主动测量法能够明确地控制测量中所产生的流量的特征，如流量 的大小、抽样方法、发包频率、测量包大小和类型( 以仿真各种应用) 等，并且实 际上利用很小的流量就可以获得很有意义的测量结果。主动测量意味着测量可以 按测量者的意图进行，容易进行场景的仿真，检验网络是否满足o o s 或s l a 非 常简单明了。 而被动测量是指在链路或设备( 如路由器，交换机等) 上对网络进行监测， 而不需要产生流量的测量方法。被动测量利用测量设备监视经过它的流量。这些 设备可以是专用的，也可以是嵌入在其它设备( 如路由器、防火墙、交换机和主 机) 之中的。控制者周期性地轮询被动监测设备并采集信息( 在s n m p 方式时，从 m i b 中采集) ，以判断网络性能和状态。被动测量主要有三种方式：s n m p 协议、 链路检测、流量检测。 被动测量非常适合用来测量和统计链路或设备上的流量，但它并不是一个真 正的q o s 参数，因为流量只是当前网络( 设备) 上负载情况的一个反映，通过 它并不能得到网络实际的性能情况，如果要通过被动测量的方法得到终端用户所 关心的时延，丢包，时延抖动等性能参数，只能采用在被测路径的两个端点上向 时进行被动测量，并进行数据分析，但这种分析将是十分复杂的，并且由于网络 曩 北京邮电人学硕1 ：学位论文 基十v o l p 的网络性能数据的挖掘方法研究与应用 上数据流量特征的不确定性，这种分析在一定程度上也是不够准确的。只有链路 带宽这个流量参数可以通过被动测量估算出来。 被动测量法在测量时并不增加网络上的流量，测量的是网络上的实际业务流 量，理论上说不会增加网络的负担。但是被动测量设备需要用轮询的方法采集数 据、陷阱( t r a p ) 和告警( 利用s n m p 时) ，所有这些都会产生网络流量，因此实 际测量中产生的流量开销可能并不小。 另外，在做流分析或试图对所有包捕捉信息时，所采集的数据可能会非常大。 被动测量的方法在网络排错时特别有价值，但在仿真网络故障或隔离确切的故障 位置时其作用会受到限制。 总之，主动测量的优点在于可以主动发送测量数据，对测量过程的可控制性 比较高，比较灵活机动，并易于对端到端的性能进行直观的统计；其缺点是注 入测量流量本身就改变了网络的运行情况，即改变了被测对象本身，使得测量的 结果与实际情况存在一定的偏差，而且注入网络的测量流量还可能会增加网络的 负担。适用于主动测量的数据一般多为业务性能相关数据，如端到端时延，时延 抖动，丢包率等等。而被动测量的优点在于理论上它不产生流量，不会增加网络 的负担；其缺点在于被动测量基本上是基于对单个设备的监测，很难对网络端到 端的性能进行分析，并且可能实时采集的数据量过大，且存在用户数据泄漏等安 全性问题。一般使用被动测量方法的网络性能数据主要是流量相关数据，如链路 利用率、设备端口吞吐量等等。 主动测量与被动测量各有其有缺点，而且对于不同的参数来说，主动测量 和被动测量也都有其各自的用途。对端到端的时延，丢包，时延变化等参数比较 适于进行主动测量；而对于路径吞吐量等流量参数来说，被动测量则更适用。因 此，对网络性能进行全面的测量需要主动测量与被动测量相结合，并对两种测量 结果进行对比和分析，以获得更为全面科学的结论。 2 1 2 网络性能数据特性 网络中的性能数据不同于一般的性能数据，由于是从网络中获取到的数据， 因此具有其独特的特征随1 。具体如下： 1 网络性能数据量庞大且随时更新 由于网络中的设备数量众多，种类也各不相同，并且网络经常是以2 4 小时 * 3 6 5 天的方式进行监控，因此造成收集到的网络数据极其庞大。这要求数据处 理的方法必须高效迅速，否则不仅达不到实时的标准，而且可能会造成大量数据 的堆积。 2 网络性能数据具有多维度的特性 7 北京邮电人学硕十学位论文基于v o | p 的网络性能数据的挖掘方法研究j 应用 网络性能数据包括流量、时延、呼损等等内容，处理时常常需要结合起来才 能得到需要的结论。可以将网络性能数据看做多维度的随时间变化而变化的变 量，在图形化显示上也要考虑到这一特性，将主要的维度都表现出来 3 由同一或临近设备上检测到的网络性能数据具有一定关系 由于数据包在传输过程中一定会经过相邻设备的相连链路。因此相邻链路的 性能数据会具有一定关系。如路由器的背板总流量是所有链路的和。在挖掘中可 以首先对全网部分数据挖掘，根据结果选择子网进行挖掘。 4 很多网络性能数据在不同情境下也具有相似的特征 例如在网络负载较轻但因为其他原因存在丢包的情况下，时延并不会发生变 化；当一个子网中因故障造成性能数据变化时，其他距离较远的子网数据流量特 征不变。 由上述可知，网络中的性能数据具有数量庞大、更新速度快、多维度、关联 性、相似性等特征。因此要想通过数据挖掘分析方法从网络性能数据中找出有价 值的关联模式需要采用适合处理网络性能数据的数据挖掘方法。 2 2 数据挖掘方法概述 数据挖掘( d a t am i n i n g ) ，就是从大量数据中获取有效的、新颖的、潜在有 用的、最终可理解的模式的非平凡过程阳3 。从广义观点来说，数据挖掘就是从存 放在数据库，数据仓库或其他信息库中的大量的数据中“挖掘有趣知识的过程。 数据挖掘又称为数据库中知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，k d d ) ， 也有人把数据挖掘视为数据库中知识发现过程的一个基本步骤n 0 1 。 数据挖掘约由3 个主要阶段组成： 1 数据准备阶段 数据挖掘的对象往往不适合于直接挖掘，需要做预处理准备工作。如选择相 关的数据，消除冗余的数据，推算缺失数据，变换或提取数据的特征，减少数据 量等等。 2 数据挖掘阶段 挖掘阶段利用各种分析方法从海量数据中发现有价值的模式和规则。得到的 知识包括： 描述性规则：给出数据的内涵或特征概况性描述，如聚类等； 预测性规则：根据数据的某些特征预测其他一些特征，如回归模型，分类等； 局部模式：给出数据中某些特征的相关性，如关联等。 3 结果评价和解释 挖掘阶段获得的模式可能大部分没有意义，因此需要根据讲演来评估哪些是 3 北京邮i 乜人学顾l ：学位论文蔗于v o l p 的网络性能数据的挖掘方法研究与心用 有效和有用的规则。还包括将规则以易于理解的方式呈现给用户，如将规则表示 为决策方法或通过可视化工具帮助用户理解等n 。 目前时序序列挖掘主要包括三种技术：比较两个序列的相似性；表征序列的 特征；序列挖掘算法。 2 3 序列距离特征表示 序列距离的度量确定序列的相似性，是序列关联和特征发现的基础。时间序 列数据或时序数据是随时间变化而变化且不同时间状态新相互关联的数据。时序 数据挖掘时对时序数据进行分析，以发现未知的关系和时态数据的特征模式。时 序数据挖掘大概涉及四个方面的任务： 1 相似性发现：判断两个或多个序列之间的距离，距离近相似，距离远则 不相似； 2 序列关联：发现多个序列之间的关联关系； 3 序列特征：根据序列相似性进行的序列分类和聚类； 4 趋势分析和预测：分析序列的变动趋势并预测未来的发展。 对于连续性的时序数据，一般使用l p 范数度量距离： l p = ( h y ，r ) p 其中，丈：y 为两个长度相同的序列，l 为序列长度，p 为任意正整数。l 2 即 为最常用的欧式距离。 l p 范数要求两序列长度相同，且对序列长度变化敏感。因此也出现了许多 其他技术，如动态时间弯曲( d y n a m i ct i m ew a r p i n g ，d t w ) 、序列相互变换代价 度量、基于概率分布的距离度量等。 2 4 序列特征表示 最简单的序列特征表示是将一个长度为l 的序列看作是1 个1 维空间的点。 但这样做空间维度非常高，因此常采用其它一些特征表示方法。无论何种方法都 应满足： d f ( x ，y ) d ( x ，】，) 即任意两序列的特征距离不能大于两序列的原距离。这些方法包括： 1 序列变换 如利用d f t ( 离散傅里叶变换) 、小波变换等方法将序列由时域映射到另一 个空间如频域，去变换后前若干个系数表示原序列的特征，将序列维度大大缩减； 2 分段统计特征 将序列分为等长的若干段，以每段的平均值作为该序列的特征。 9 北京邮电大学硕i ：学位论文 基于v o l p 的网络性能数据的挖掘方法研究与应用 3 聚类方法 将序列划分为若干子序列，用合适的相似度量对这些子序列进行聚类，指定 相应标识，各子序列类标识的集合就是该序列的特征。 4 基于模型的方法 假设序列满足某种模型的分布，只需要根据序列猜测出模型的参数。这些参 数即为序列的特征。 2 5 序列挖掘算法 序列挖掘算法主要通过一些数据挖掘方法如关联规则挖掘、分类、聚类等对 序列数据进行处理，从中找出有价值的序列类别或关联关系。具体的挖掘算法如 下： 2 5 1 序列关联规则挖掘 加入事务的先后顺序，即可将传统关联规则挖掘扩展为序列关联规则挖掘。 如将顾客在超市的交易按时间先后排列为序列，每个交易是一个事务集，序列支 持度为支持该序列的顾客与顾客总数之比。关联规则挖掘将找到所有的频繁序 列。 ，主要算法包括： 1 基于a p o r i o r i 的关联算法，如g s p 算法 2 基于投影的模式生长方法，如p r e f i x s p a n 算法 2 5 2 序列分类算法 由于时态数据具有独特的结构，因而很多非时态的分类算法难于应用到时态 数据上。大多数基于时态数据的分类方法都假定存在一些简单的序列基本形状或 模版，使用分段拟合或者推导模型参数的方法判断某序列是否属于某类。 还有一些算法直接抽取序列的关联模式或特征，将关联模式子序列或者特征 的值作为向量输入分类器。 2 5 3 序列聚类算法 序列聚类方法可分为基于距离的算法和基于模型的算法。具体如下所述： 1 基于距离的算法 基于距离的算法可以首先缩减序列长度，然后用k - m e a n s 算法和其扩展算法 ( 比如迭代e m 算法) 进行聚类。 i o 北京邮电人学硕士学位论文 基于v o l p 的网络性能数据的挖掘方法研究j 心用 或概括出要分类样本序列的共同成分( 子序列) ，将样本序列变换为共同子 序列标记序列，然后用c o b w e b 算法分组序列。 此外还有基于统计特征，层次性方法等聚类方法。 2 基于模型的算法 基于模型的算法已知模型形式，根据样本估算模型参数，如m a r k o v 模型、 回归混合模型等等。 2 5 4 趋势分析和预测 趋势分析法( t r e n d a n a l y s i s ) 又叫比较分析法、水平分析法。趋势分析最初 由t r i g g s 提出，采用t r i g g s 轨迹信号( t r i g g s t r a c k i n g s i g n a l ) 对测定方法 的误差进行监控。此种轨迹信号可反映系统误差和随机误差的共同作用，但不能 对此二者分别进行监控。其后，c e m b r o w s k i 等单独处理轨迹信号中的两个估计 值，使之可对系统误差和随机误差分别进行监控，其一即为“准确度趋势 ( 均 数) 指示系统_ t r i g g s 平均数规则，其二即为反映随机误差的“精密度趋势 ( 标 准差) 指示系统_ t r i g g s 方差卡方规则。趋势分析与传统的s h e w h a r t 控制图在 表面上有类似之处，即用平均数来监测系统误差而用极差或标准差来监测随机 误差。然而，在趋势分析中，平均数( 准确度趋势) 和标准差( 精密度趋势) 的估计 值是通过指数修匀( e x p o n e n t i a ls m o o t h i n g ) 方法获得的。指数修匀要引入权数 来完成计算，而测定序列的每一次测定中，后一次测定的权数较前一次为大，因 此增加了对刚刚开始趋势的响应，起到了“预警 和“防微杜渐”的作用。 趋势分析法总体上分四大类：纵向分析法、横向分析法、标准分析法、综合 分析法。此外，趋势分析法还有一种趋势预测分析。 趋势预测分析运用回归分析法、指数平滑法等方法来对财务报表的数据进行 分析预测，分析其发展趋势，并预测出可能的发展结果。趋势分析和预测可以基 于统计方法，如回归方法。或在分类、聚类、关联的基础上进行。神经网络、自 动机等理论也应用于序列趋势预测中。 北京邮电人学硕士学位论文 基于v o l p 的网络性能数据的挖掘方法研究j 心用 第三章常见网络性能数据处理方法 3 1 网络性能数据预处理和查询 网络数据一般按层次性结构进行存储在数据库中，低层次存储原始的性能数 据，高层次存储进行统计或简单计算预处理过的数据，最高层存储对得到性能模 式和关联规则。如下图所示： 图3 - 1 网络数据层次结构 如图3 - 1 所示最底层为收集到的原始数据，第二层为对这些数据进行简单的 加减或平均方法处理过的数据，如子网内相同数据合并后的结果；第三层是对第 二层进行再次处理后得到的数据，如经过某路由器所有呼叫的时延平均等；最高 层是根据这些数据及处理结果得到的关联规则或其它知识。 层次性的存储方法同时也提高了网络数据查询的便利，特别是原始数据进行 过很好的预处理和处理结果存储时。比如当查询8 ：0 0 - 1 0 ：0 0 的时延平均，系 统可以从已计算并存储的每小时时延平均中取出8 ：o o 一9 ：0 0 和9 ：0 0 - 1 0 ：0 0 两个时间段再次进行平均，使反应时间大大缩短。 1 2 北京邮电人学硕 ：学位论文甚于v o i p 的网络件能数据的挖掘方法研究与应用 3 2 网络性能数据挖掘方法介绍 3 2 1 基于已知模式的方法 根据不同网络数据的特性，我们可以总结出每种性能数据可能会出现的模 式：如时延可能为等值稳定于8 0 m s 以下，测不到，大斜率增长到s 级，突变到更高 并稳定，突变到更低并稳定等。如图3 - 2 所示： * 坼t 腑 一。啦# 冉 雹 f “一 、* b _ “- 摊 錾 j 一 ：二赫 7 ：。 i 一撼 器 赫 ” 疃 口a 撸 一o i 尊 缨 尊麓，删j 黪4 謦7 黝，擘。譬4 j 。黼7 ；，：。：赫霭 图3 - 2 网络性能数据特性 其中，左边的图表示时延为稳定状态；中间的图表示时延特性为线性增长； 而右边的图则表示时延存在突变，并且在突变后又回到稳定状态。 将这些模式存储起来，一般故障条件下网络性能不会显示出其它的性能特 征。虽然网络数据数据量很大，但数据特征的类别并不多，因此在处理实际的网 络数据时，可设置一定的时间窗口和采样间隔，运用统计和与门限比较等方法得 到窗口中网络性能数据的特征，与已知模式比较后，得到故障类型和故障位置。 例如网络性能满足一下特征：时延基本稳定，流量振荡稳定，核心设备收发相等， 链路上下行相等，是连接设备流量的1 2 ，不存在丢包，m o s 稳定于3 7 ，则可认 为网络中不存在故障。 3 2 2 基于决策树的方法 基于决策树的方法常见的算法如c 4 5 算法较为简单，而且速度较快，精确 度也可以。较适于网络性能数据。其基本思想如图3 3 所示： 北京邮电人学硕 ：学位论文 基于v o i p 的网络性能数据的挖掘方法研究0 应用 图3 - 3 决策树处理方法 在图3 3 中，判断一个网络质量为l o w ，m e d i u m ，或h i g h ，只需要获取最多 三个性能数据，如n o r m a l i s e dn e t w o r kd e l a y 平均值为5 0 - 1 0 0 之间，n e t w o r k d e l a y 平均值大于1 2 5 ，则网络质量为l o w 。运用这种方法可以将不同位置的网 络设备性能区别开来，按照由核心到接入的方法组织为节点。使定位过程更快速 的收敛。对于单一故障可能会更精确些。 3 2 3 基于矢量分类和聚类的方法 基于矢量的方法就是将网络数据看做多元的矢量序列，置于各维为时延、吞 吐量等的矢量空间中进行分类和聚类。 正常情况下性能应该是稳定的，这时候矢量序列应该是序列间重合或者序列 问间距很小的点状，当出现故障时，某些维的序列值发生变化，在矢量空间中呈 现出不同的形状。因此可以通过计算汉明距离、k 平均的分类和聚类的方法，归 纳出故障特征。 这种方法的缺点在于需要很大的存储空间，否则会影响处理速度。同时理想 情况下的处理速度也不如决策树方法。 1 4 北京邮电人学硕1 ：学位论文 基于v o l p 的网络性能数据的挖掘方法研究j 应用 c o m p u t e rc e t r e ：8n o v e m b e r sd e c e m b e r2 0 0 4 d 岫f r e q u e n c y 瀚 7 4 p 。i “ “，0 。4 。”。7 ” 一：? 。4 0 0 o 5 7 椰o口 4 3 蓼5 0 0 圈 9 鼋 2 譬m 豳 占 i ，哆、 奢瑚 () l 童抛 l t o n- i o 锯b 触峦蠢女知识。i 。矗m z 。：t * 也如0 虢、黝勘| i 珏。砒 轧一_ 。* 。0 批：l 女口。i 唬# 盛钯 | 一燃 o l ，。 一 冀l 鼬瑚枷辩舶