（计算机系统结构专业论文）tcp数据流测度的研究.pdf

摘要 t c p 数据流测度的研究 戴宣丁伟 东南大学计算机科学与工程学院 在现有的网络流量中，t c p 数据流占据了绝对优势，针对t c p 数据流的测量成为网络 测量的研究热点。网络测量以获取测度值为目的，所以，对于数据流测度的研究十分必要。 为此，本论文围绕t c p 数据流测度展开研究。论文的研究工作包括定义一系列新的t c p 数 据流测度，提出每个测度的测量方法，为测量存在的误差建立误差估计模型，从而为数据流 测量提供量化指标。 论文在目前国内外对数据流测量的研究基础上，提出了十个新的t c p 数据流测度，包 括测度的定义、测量方法以及误差估计模型。 首先，论文从集合和时间序列的角度，对t c p 数据流测度进行了形式化描述，并给出 了t c p 数据流测度的分类标准。同时，论文还总结了t c p 流测度的可能来源。之后，论文 着重讨论了数据流测度的测量方法分类、测量方法的评价标准以及误差分析方法。 其次，论文按照协议层次，对新提出的t c p 数据流测度进行了阐述，详细论述了十个 t c p 数据流测度的测量动机、定义、测量方法以及误差模型。同时，还对测量方法的时间 和空间开销进行了分析 然后，以实际鼹络流量为数据源，对论文所提t c p 数据流测度进行了测量，并分析了 测度值在实际流量中的分布状况。总结了相关结论。此外，通过实验对比了测量方法的实际 时间和空间开销，并且对所建立的误差模型进行了检验。 论文最后作了简要总结，回顾了已完成的工作，指出了不足，并对未来工作进行了展望。 【关键词】t c p数据流测度网络测量 网络行为学【l 】 a b s t r a c t r e s e a r c h0 nt c pd a t af l o wm e t r i c s d a i x 啪d 玎q g w e i s c h o o lo f c o m p u t e rs c i e n c e e n # n e e i n gs o u t h e a s tu n i v e r s i t y s i n c et c pd a t af l o wo c c u p i e sas i g n i f i c a n tp e r c e n t a g eo f t h en e t w o r kt r a f f i c ，t h e r eh a sb e e n ak e e ni m e r e s ti nt h e 北s 瞄呦o nt c pd a t af l o wm e a s u r e m e n t a c q u i r e m e n to fm e t r i cr e s u l ti s t h eo b j e c t i v eo fn e t w o r km e a s w e n l e n t ，t h u s i t sn e c e s s a r yt od om o r er e s e a r c ho nd a t af l o w m e u i c s f o rt h e s er e a s o n s , 唧d a t af l o wm e t r i c sa f ed i s c u s s e d t h i st h e s i sd o e sr e s e a r c ho nt h e p r o d u c t i o no fn e wt c pd a t af l o wm e t r i c s , i n c l u d i n gt h e d e f r u i t i o no fn e wm e t r i c s ，t h e m e t h o d o l o g yo f n e wm e t r i c sa n de r r o te s t i m a t i o nm o d e lw h i c ha t h ef u n d a m e n t a lw o r kf o rt h e s e t 叩o f 。m e t r i ca r c h i t e c t u r e b a s e do n 曲w o r ki nt h ef i e l do f n e t w o r kd a t af l o wm e a s u l o m e n t t e nn e wt c pm e t r i c s 舭b r o u g h tf o r w a r d f i r s t , i nt h ep e r s p e c t i v eo f s e tt h e o r ya n dt i m es e r i e s ，ad e s c r i p t i o no f t c p d a t af l o wm e t r i c i sg i v e nw i t ht l l ec l a s s i f i c a t i o ns t a n d a r df b rt c pd a t af l o wm e t r i c m e a n w h i l e ，t h eo r i g i 船o f t c p d a t af l o wm 硎c sm ec o n c l u d e d a f t e rt h a t , t h ec l a s s i f i c a t i o no fm e t h o d o l o g yt h ee s t i m a t i o n s t a n d a r df o rm e t h o d o l o g y 锄dm e t h o d o l o g yo f e r r o ra n a l y s i s 戤a l li l l u s w a t e d s e c o n d , n e wm e u i c sa r ei n t r o d u c e da c c o r d m gt o t h e p r o t o c o lh y e r s ，i n c l u d i n gt h e m o t i v a t i o n , d e f m i t i o n , m e t h o d o l o g ya n de r r o re s t i m a t i o nm o d e l b e s i d e s t h ec o n s u m p t i o no f e a c hm e t h o d o l o g yi sa n a l y z e d t h e n , w i t ht w ot r a c e sf r o ma c t u a ln e t w o r k 廿a 伍ca se x p e r i m e n td a m , t h er e s u l t so fa l lt h e n e wm e t r i c s 矾c a l c u l a t e d a t i e r t h ea n a l y s i so f t h ed i s t r i b u t i o no f e a c hr e s u l t , s e v e r a lc h a r a c t e l s a p p e a r o t h e re x p e r i m e n t sc o m p a r et h ec o n s u m p t i 0 1 1o f e a c hm e t h o d o l o g ya n dv a l i d a t et h e e s t i m a t i o i lm o d e l f i n a l l y , ab r i e f s u m m a r yi sg i v e n , w h i c hc o n c l u d e st h er e s e a r c hw o r ka n dd e f i c i e n c yo f t h e w o r ka n di n d i c a t e st h ew a yf o rf u r t h e rr e s e a r c h k e y w o r d s ：t c p , d a t a f l o w , m e t r i c , n e t w o r k m e a s u r m e n t , n e t w o r k b e h a v i o r 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我 所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同 志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名：黛量日期：坐坚凹 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印件和 电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内 容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的 全部或部分内容。论文的公布( 包括刊登) 授权东南大学研究生院办理。 研究生签名：黛叁： 导师签名：日期：j 叶4 田 第1 章绪论 1 1 网络测量介绍 1 1 1 网络测量的意义 第1 章绪论 自从世界上第一个分组交换网a r p a n e t 的诞生起，短短几十年中，互联网已经成为 目前信息交流的最主要平台之一。上网主机数量的不断增长，网络服务的层出不穷，导致 互联网所表现行为越来越复杂。所以，虽然互联网发展迅速，但是人们对它在局部和整体 范围内所体现出的行为特征依然没有一个正确和完整的认识。t c p i p 网络体系结构与协议 的巨大成功来源于其开放性，但正是这种开放性使得互联网成为一种高度异构、开放的复杂 系统。这使我们对互联网的运行特性与内在本质知之甚少，给互联网的管理和分析带来了一 系列的困难。网络测量是对网络行为进行特征化、对各项指标进行量化并充分理解与正确 认识互联网的最基本手段，是理解网络行为的最有效的途径。 网络测量是一项研究如何应用工程方法和数学工具定量测量和描述网络系统的技术， 也是对网络行为研究的基础。网络测量的过程是通过对网络传输的信息进行观测，按照一 定方法，得到测量结果。其测量结果可以用于用户行为分析、网络流量规划，网络计费以 及网络管理等等。类似于人体的各种生理指标，如温度，体重、肺活量等，网络也需要各 种指标用于刻画自身特征，这些指标被称为测度。网络测量的目的就是获取测度值。以此 为网络行为的研究提供量化的依据。因此，测度对于网络测量至关重要。 m t f 的i p p m 工作组在r f c 2 3 3 0 中提出了口性能测度框架【3 】，规定了提出的测度必 须遵循的原则： 1 ) 测度必须是具体的和有明确定义的； 2 1 测度的测量方法对于同一参数必须具有可重复性，即在相同条件下多次使用该方 法所获得的测量结果应该相同； 3 ) 测度必须具有公平性，即对同种网络的测量结果不应有差异而对不同网络的测量 结果则应出现差异； 4 1 测度必须有助于用户和运营商了解他们所使用或提供的i p 网络性能； 5 ) 测度必须捧除人为因素。 1 1 2 网络测量的基本方法 网络测量可以使用不同的方法获取测度值。根据网络测量实施手段的不同，网络测量 可以分为主动测量和被动测量。 主动测量是在选定的测量点上利用测量工具有目的地主动产生测量流量，注入网络， 并根据测量数据流的传送情况来分析网络的性能。主动测量的优点是对测量过程的可控性 比较高，灵活、机动，易于进行端到端的性能测量，如端到端传输的带宽，路径的不对称 性，传输的延迟和抖动等特性。 主动测量也有一定缺点。一方面，注入的测量流量会改变网络本身的运行情况，使得 测量的结果与实际情况存在一定的偏差。原因在于，主动测量需要被测路径两端节点以及 中间路由器的参与，中问节点的状况会对测量结果产生影响。此外，网络旁路流量( c r o s s 东南大学硕士学位论文 i r a f f i c ) 也会影响测量结果的准确性。另一方面，测量流量还会增加网络负担。如果网络 状况较差，增加额外流量月u 会加重网络负担，可能引起网络拥塞。 被动测量是指在链路或设备( 如路由器，交换机等) 上利用测量设备对网络进行监测的 测量方法。最具代表性的例子就是c i s c o 的硬件流测量系统n e t f i o w 1 。被动测量的优 点在于它不产生多余流量，不会增加网络负担；其缺点在于被动测量基本上是基于对单个 设备的监测，很难对网络端到端的性能进行分析，并且由于实时采集的数据量过大，对采 集设备的性能要求很高。 主动测量与被动测量各有其优、缺点，对于不同的需求来说，主动测量和被动测量也 都各具优势。在网络发展的早起网络带宽有限，网络流量内容和行为特性单一，无法为被 动测量提供足够丰富的信息，因此主动测量更为合适。然而，随着网络规模的不断扩大， 网络带宽不断增加，网络业务流量呈现多样性，导致流量行为不在单一，主动测量无法有 效的感知复杂网络行为特征。因此，被动测量成为大规模高速网络测量的研究焦点。 1 2现有网络测度介绍 网络测量的目的是为了获得测度的值。目前，已经存在许多测度用于刻画网络的不同 特征。按照研究角度，在报文层面，存在有网络性能测度；在数据流层面，则有数据流测 度。本节就对这两类测度分别进行介绍。 1 2 1 网络性能测度介绍 网络性能测度可以定义为反映网络某一性能的指标。通过一系列测度值衡量网络的传 输性能及健壮程度。 目前，基本的网络性能测度包括： 传送时延：数据包从a 到b 的传输时间。有单程和往返( r o u n d - l x i p ) 时延。 包丢失率：数据传送中丢失数据包的比率。 连通性：即可达性。主机a 到b 有连通性指从a 发出的数据包可以传送到b 。 吞吐量：主机a 到b 的路径的吞吐量指这条路径所能传送数据的最大速率。 大批传输容量：在拥塞控制下，单个链路传输数据的最大能力。 在已有的r f c 中，都给出上述测度的测量方法。目前，上述所有测度的测量方法都是 通过主动测量来完成测量 在网络性能测度的框架【3 仲，并没有对测度进行明确的分类。但是，通过对其测度来 源及定义，本文将其对测度的分类总结如图1 - 1 所示。 厂原子测度( a t o m i cm e t r i c ) 网络性一按测度定jr 派生禊i 度 能测度义方式分1 复合测度( c o m p o u n dm e , c ) 一按复合i ( d e r i v e dm e t r i c ) l -方式铺组合测度 【( c o m p o s i t em e t r i c ) 图1 - 1 网络性能测度分类图 复合测度是在已有测度的基础上，通过与其他测度进行组合计算( 组合测度) ，或者对 已有测度进行扩展( 派生测度) 彳导到的。如，双向连通性就是单项连通性的组合，而延迟抖 动就是延迟的扩展。r f c 2 0 3 0 中，原子测度被定义为构成复合测度的基本测度，如大批传 2 第1 章绪论 输容量【3 】。但是，“大批传输容量”的测量并不具备原子性( 包括传输时间和报文数的测量) ， 因此测度的原子性并没有明确标准，只能视实际需求而定 1 2 2 数据流测度介绍 数据流定义 网络测量的基本单元是报文。通过报文的各种传输特征，可以获知网络的传输特性。 然而，网络中传输的报文类型众多，不同类型的报文可以有不同的传输特性，如果将各类 报文混合在一起进行测量，不同类报文的传输特征可能会被掩盖。例如，u d p 协议缺乏拥 塞及流量控制等机制，会导致其抢占网络带宽，造成t c p 报文传输不畅，这就是t c p 友 好性【4 】研究的问题。因此，有必要对报文进行分类测量。 基于将报文分类测量的目的，提出了基于数据流的网络测量。所谓数据流( f l o w ) ，是指 符合特定的流规范( s p e c i f i c a t i o n ) 和超时( t i m e o u t ) 约束的一系列报文的集合【2 】【5 】【6 】， 又称口流，简称流。其中，超时约束是指将超过一定时间不活动的数据流定义为已终结， 从而使测量系统资源更充分的用于活动的数据流。流规范则是指定了数据流中报文必须具 有的相同属性。流规范与超时约束的标准并不唯一，目前使用较多的流规范有n e t f l o w 的 七元组规范 4 h 及五元组【5 【6 】【7 】规范等。 n e t f i o w 的数据流定义遵循如下流规范及超时机制： a ) 数据流中报文的如下属性相同：源m 地址、目标讲地址，源端口号、目标端口号、 协议类型、服务类型( t o s ) 、网络设备的输入逻辑接口号 b ) 满足如下条件之一，则认为数据流已经结束： 一遇到t c p 的f i n 或r s t 数据包( 仅对代p 数据流) 数据流已有1 5 秒没有新报文到达 一数据流已经3 0 分钟没有结束 路由器缓存已满 n e t f l o w 的流规范及超时策略限制较多，且流规范包含网络设备接口号，因此，n e t f l o w 的流定义广泛应用于路由设备。 除了n e t f l o w 的流定义之外，五元组的流规范使用频率较高五元组的数据流定义遵 循如下流规范及超时机制： 曲数据流中报文的如下属性相同：源i p ，宿口，源端口，宿端口，协议号 ”数据流已有6 4 秒没有新报文到达【5 】 曲遇到t c p 的f i n 或r s t 数据包( 仅对t c p 数据流) 五元组规范适用于各种测量系统，与网络设备无关，因此得到广泛应用。若无特殊说 明，本文之后提及的数据流均为遵循1 2 2 中五元组规范的数据流 还有一些流定义将了五元组的部分元作为流规范，如源宿伊，这些流可以看成五元组 数据流的聚合，称为聚流( a g g r e g a t e dn o w ) 。 数据流测度定义 按照协议层次，数据流可以分为t c p 流、u d p 流以及1 c m p 流【9 】。目前，数据流的 研究主要是针对流测度的研究。数据流测度则是刻画数据流某种特征的指标。目前，数据 流测度研究主要集中于以下四个测度： 幻数据流长：指数据流包含的报文总数。 ”数据流持续时间：指数据流从开始到结束的持续时间。 3 东南大学硕士学位论文 c )数据流速度：单位时问内数据流的报文到达速率。 m数据流到达率：单位时间内，到达观测结点的数据流数量。 数据流测度的主要测量过程如下：首先，在各种网络业务流中提取出特定的端到端数 据流；其次，对其进行统计；晟后，获得测度值。这是一种典型的被动测量方法。通过被 动测量方法进行端到端测量是数据流测量的主要特点。对于上述四个数据流测度的研究已 经取得了一些成果，1 3 节对数据流测度的研究现状进行了详细介绍。 1 3数据流测度研究现状 以1 2 2 中四个数据流测度为基础，研究工作围绕数据流长分布、数据流持续时间以及 数据流速分布展开，并取得了一些结论。 在一段时间内，w e b 是最主要和常见的网络应用。因此，早期的数据流流长的研究就 针对w e b 服务提供的文件长度分布展开【1 0 】【l l 】 1 2 】【1 3 】，以此探询t c p 流的流长分布，并 发现w e b 文件长度服从重尾分布。然而，文件与数据流并不存在一一对应的关系，因此这 种研究方法具有一定局限性。也可以通过实际测量得出数据流的流长分布 1 4 1 ，但是结果 依赖于实验环境，结论并不具有普遍性。目前的研究表明，w e b 文件大小服从一定分布， 如l o g n o r m a l 分布、l o g n o r m a l 和p a r e t o 联合分布以及多重p a r e t o 分布；而较为准确的数 据流的流长分布只能通过实际测量获得。，。 对于数据流的时间特征研究较为广泛。数据流持续时间分布的研究表明【1 5 1 ，网络中7 大多数流持续时间较短，只有少数流持续时间较长，却承载了一半以上的链路负载，即流持 续时间也具有重尾特征。研究还表明，流长度较大的数据流速度不够稳定，波动性较大【2 】： 通过对不同t r a c e 的统计并结合协方差相关理论发现，流速度和流长度存在强正相关关： 系1 1 6 】d 7 i s ，流速和流持续时间存在弱负相关关系【1 7 】【l8 】。在此基础上，研究得出结论： 短t c p 流的流速特征主要反映为协议行为【1 7 】【1 8 】。 相比流长分布、流持续时间以及流速分布的研究，数据流到达率的研究主要集中于1 如 流到达率的研究。然而，研究结论并不统一，可以分为两种：1 ) t c p 流具有长相关性： 2 ) t c p 流到达服从p o i s s o n 分布。根据排队论的相关理论，通过测量和仿真，文献d 9 推测 链路带宽足够的情况下，t c p 流的到达模型是p o i s s o n 分布；对流内报文到达的分析结论 表示【2 0 】：如果只观察t c p 流的m 层报文，则数据流的到达过程可以被视为p o i s s o n 过程。 另一方面，对大规模网络研究表明【2 1 】，当网络不存在拥塞时，同一个s e s s i o n 2 1 中的t c p 流到达基本服从w e i b u l l 分布；对于t c p 流到达的相关性研究，文献【2 2 】发现，只有在分 钟到小时级的粒度内，t c p 流的到达是长相关的或者说是自相似的总之，对于数据流的 到达，目前仍无统一的结论。 综上所述，目前的数据流研究主要从宏观角度出发，分析被观测网络的用户群体行为， 可以发现在一定时间范围内用户的群体行为。除了对数据流自身特点的研究之外，还有很 多研究从数据流的角度出发，分析协议行为和用户行为对网络传输的影响，研究结论应用 于基于数据流的服务质量( q o s ) 和带宽控制 2 3 】【2 4 】【2 5 】【2 6 】，网络安全监测【2 7 】【2 8 】，流量测量 和预测【2 9 】等相关领域。由此可见，数据流研究已成为当前网络测量的热点问题。 目前对数据流的研究主要从宏观角度出发，获得了很多具有实际意义的结论。但是， 当前数据流测量的研究还有不足之处： ( 1 ) 没有充分挖掘数据流的特性 依据数据流定义，如果不考虑时间因素，可以将数据流视为对报文的聚类，此时可以 将数据流看成报文的集合；在考虑时间因素的前提下，可以将数据流视为一组报文的有序 序列。在数学定义中，集合与序列本身就有各自的特点和属性。因此，数据流也应该具有 4 第1 章绪论 与之对应的若干特性。但是，目前的数据流特性研究主要集中于流长、流速，流持续时间、 流到达等的研究，缺少对数据流其他特征的挖掘与研究。 ( 2 ) 研究对象范围宽泛 数据流包括t c p 流、u d p 流以及1 c m p 流。t c p 与u d p 是两种不同的传输层协议， i c m p 是一种网络控制消息协议。三种流具有不同的传输机制或用途，这必然会影响到对 应的数据流的传输特性。特别是对于网络中比例占有绝对优势的t c p 流，缺乏专门研究。 因此，可以考虑将数据流分类研究，缩小研究范围，以发掘不同类型数据流的特征。 从数据流研究存在的不足可见，现有流测度数量相对偏少，因此，本文将从定义一系 列新的数据流测度出发，展开对数据流的研究和分析工作。为了使研究工作更具针对型， 将研究范围限定于网络中占据绝对优势的t c p 数据流。 1 4论文研究目标和研究内容 1 4 1 论文研究目标 论文工作的研究目标是，根据研究工作的需要，提出一组新的t c p 流测度，包括每个 t c p 流测度的定义、测量和计算方法，并给出相应的误差模型。此外，基于两个具体的 t r a c e 数据，完成这些测度的准确值和近似值测量，并对其进行误差比较，以证明其合 理性和可操作性 1 4 2 论文研究内容 论文主要围绕t c p 流测度的定义、测量方法及误差分析展开，具体研究内容包括： & t c p 流测度的形式化描述 理论上t c p 流测度无穷无尽，研究工作也无法穷尽每一个t c p 流测度。因此，本文 给出一种t c p 数据流测度的形式化描述，以便新测度的补充。同时，以此描述为基础，提 出t c p 流测度的不同分类。 b 若干流测度的提出 报文头的内容是数据流信息的基础。报文头中的每个字段都是数据流信息的最基本来 源。然而，并不是对所有的报文头字段都可以定义测度。本文对流测度的可能来源进行总 结，在此基础上定义若干测度，包括给出各个测度的明确含义、测度的单位及结果表示方 式。对于某些测度还要给出其测量意义。 c 流测度测量方法的设计与实现 测量方法的设计包括详细描述测量方法的流程，设计所需的数据结构，并分析测量方 法的时间及空闻开销，以此作为衡量测量方法优劣的标准。之后，还将使用实际网络数据， 对比测量方法的时间和空间开销。 d 误差模型的建立 本文所提的测量方法中，某些测量方法得到的是测度近似值。针对这些测量方法的特 点，本文将给出刻画测量误差的数学模型。 c 。测量结果分析 对于本文所提测度，本文将对不同的t r a c e ，按照本文设计的测量方法进行测量， 得到测度值。之后，将统计实际网络中各测度值的分布，并分析原因、总结相关结论。 f 误差模型的验证 东南大学硕士学位论文 对于给出的误差模型，本文将使用实际网络数据，统计测量产生的误差，并与误差模 型进行对比，以验证建立的误差模型。 1 5论文的组织结构 论文第一章：绪论，主要介绍了有关网络测量的研究现状。着重讨论了当前数据流测 量的研究现状，并提出了不足之处，提出数据流测度概念；第二章：t c p 数据流测度的定 义，主要介绍t c p 数据流测度的来源、描述方式、测量方法的分类和评价标准以及相关分 析方法；第三章：t c p 流分组特性测度的研究，介绍了t c p 流分组特性测度的特点，并详 细讨论了四个t c p 流分组特性测度的定义、测量方法及误差分析；第四章：介绍了t c p 流传输特性测度的特点，并详细讨论了六个t c p 流传输特性测度的定义、测量方法及误差 分析：第五章：实验及相关结论，主要通过实验结果的展示，验证第3 、4 章提出的测量方 法，并总结了相关实验的结论。 6 第2 章t c p 流测度研究内容介绍 第2 章t o p 流测度研究的基础问题 2 1t c p 流测度的形式化描述及分类 本论文的研究目标之一在于提出一系列数据流测度，从而为数据流测量提供量化指标。 为此，本章首先对数据流测度进行分类，希望将众多的流测度区分为不同类型。分类的关 键问题在于分类标准的确定。如1 1 - 1 节中所述，网络性能测度的类型划分标准并不明确。 因此，本文在参考已有分类的基础上，提出流测度的分类标准。 在对数据流测度分类之前，首先给出数据流测度的形式化描述。 报文描述：报文表示为若干域的集合，即报文p = a 1 ，a 2 其中，a i 为报文第i 个域的值，为十进制整数；“域”可以包括口报文头字段、传输层包头字段以及应用层协 议字段。l i n ，n 为报文的域总数。 数据流描述： 数据流f 俨i ，t t ) ，劭t 拼= ( a l l 4 1 2 a h , t o ，( a 2 1 a 2 a 抽t 2 ) ( a i l , a o a 缸，t d ( a m l ，a 皿a 珊，t m ) ，( s r c i p , d s t l p , s r c p o r t , d s t p o r t p r o t o c 0 1 ) 。其中，a b 表示第i 个报文的第j 个属性；t i 表示第i 个报文的到达时刻，l i m ， l j n ，m 为数据流f 所含报文总数；( s r d p , d s t l p , s r c p o r t , d s t p o r t , p r o t o c 0 1 ) 为流所属五 元组。 从流的形式化描述可以看出，流不仅可以看作( 报文，时戳) 二元组的集合，也可以视 为以时戳为时间自变量的时间序列。 数据流测度描述； 流测度 m = g ( a n l ，如1 a _ 1 ) ，( a “2 a 2 i 2 a m ) 一( a i m a 2 t k 札) ( t 1 ，1 2 t o ， 。 ； ( s r c l p ，d s t l p ，s r c p o r t ，d s t p o r t ，p r o t o c 0 1 ) 1 其中g 为以各报文若干域值或时戳为自变 量的数学函数又称测度函数，0 i j i 2 5 ) g ( f ) 或者 p ( 防一x i ) g ( ) 式表示x 与x 之差大于e 的可能性不超过g ( c ) ：类似的，式表示x 与x 之差小于的可能性不低于g ( e ) 此时，误差在置信度0 ( # ) 下成立，称为概率 误差。 2 ) 对于测度x ，其近似测量值为x ，jc 0 ，有 x - x i 占 此时，取值与概率无关，称为非概率误差 对于非概率误差，只需获得e 即可；对于非概率误差，则需要同时获得与g fc ) 。 在进行误差分析的过程中，往往需要使用概率与统计的相关理论。概率误差可以使用中心 极限定理或者特定概率分布等方法进行估计，而非概率误差则可以通过三角不等式等方法 进行估计。 1 )中心极限定理 设磊，磊点是独立随机变量序列，假设e 磊及d 磊( 1 咄t 瓤) 存在，若对于任意 的z ，若成立 l i r a p 宝舌一百窆点舌一百点 面 3 0 ，则可以认为 东南大学硕士学位论文 n ( o ，1 ) 在上式成立的基础上，可以根据正态分布的置信区间，可以求得总体均值或者方差的 误差。以正态分布为基础，还可以根据其它已知统计分布，求得统计量的置信区间，如z 2 分布。 2 )特定概率分布 对于某些误差，中心极限定理可以直接获得某些测度可以作为统计量，求得其置信区 间。但是，还有一些测度并无统计量与之对应。此时，可以根据某些已存在的概率分布， 求得误差限为时的概率口 假设测度x ，其近似测量值为x ，a x = l x x l ，若存在概率分布函数g ( e ) 满 足p ( z 占) 2 1 一g ( 力，则占与1 - g ( e ) 分别为误差及置信度。 3 ) 三角不等式 对于测量的准确值x 与近似值x ，可以利用三角不等式推导出两者误差的一个上界： j x - x j j + 防i g 。可以通过求解防卜防i 的上界，近似代替误差e 。 2 5 本章小结 本章首先s i 入了对t c p 流测度的形式化描述，并在此基础上介绍了t c p 流测度的分 类标准；其次，本章遵照r f c 2 3 3 0 ，对流测度的表述内容进行了说明；然后，阐述了t c p 流测度产生的来源背景；最后，对数据流的测量过程及测量方法进行了介绍，给出了测量 方法的评价标准以及误差分析相关方法。在第3 、4 章中，本文将按照域值所属协议层次分 类，例举具体的t c p 流测度进行研究。 1 4 毒 。 占一 缶 。d 第3 章t c p 流分组特性测度研究 第3 章t o p 流分组特性测度研究 3 1t c p 流分组特性测度定义及特点 若测度函数所依赖的自变量均来源于m 报文头字段，则称测度为t c p 流的分组特性测 度。本章主要讨论t c p 流的分组特性测度测量。分组特性测度具有以下特点： 1 分组特性测度来源于m 报文头中的属性值，与报文数据净荷无关。根据2 1 对流 测度三要素的描述。m 报文头属性( 版本号、口头部长度、服务类型、口总长， m 标识、m 分片标识、分片偏移、r r l 、协议号、校验和、源宿口) 都可以作为 分组特性测度的属性要素。 2 数据采集结果往往是以太帧或者m 报文，而每个p 报文都具有完整的i p 报文头。 ， 所以基于妒报文头的流测度可以直接对每个采集报文进行统计和计算，无需筛选。 即，每个报文都是有效的测量对象。 3 虽然基于口报文头的流测度仅依赖于口报文头属性，但是t c p 数据流只对应协 议号为6 的i p 报文。因此，在本章讨论中，所提口报文都默认为6 ，即t c p 协议。 基于分组特性测度的特点，并结合2 2 中t c p 流测度的可能来源，本文提出如下分组 特性测度：流平均空闲时间、最小分片尺寸、流的报文生命周期差异及一个基于口报文头 的聚流测度一流密度 3 2 t c p 流分组特性测度 3 2 1t c p 流的平均空闲时间 3 2 1 1 测量动机 超时值的设定是数据流定义中一项重要的因素。超时值过大，会导致流合并；超时值 过小，会导致流分裂【2 】。超时值的设定与报文的到达间隔明显相关然而，链路状况的不 同，传输信道的不同，采集点的不同都会影响报文的到达间隔。因此，需要一项指标，用 以统计流的报文到达时间间隔，为t c p 流的超时值设置提供依据。 3 2 1 2 测度描述 测度名称 t c p 流的平均空闲( t c p f l o w l e i s u r e l i m e ) 相关参数 一t c p 流f 所含报文总数n f t c p 流f 的第i 个口报文的到达时刻t f i ，l i n v 结果表示 该测度结果为一个正浮点数，单位为秒。 测度定义 t c p 流f - ( s r c l p ，s r c p o r t ，d s t l p ，d s t p o r t ，t h n e o u t ) ，任何两个相邻报文到达 的时间间隔平均值就是数据流f 的平均空闲时间。可以如下表示： 东南大学硕士学位论文 f l t v = i n t e r v a l , ；n f 为数据流报文总数，i n t e r v a l i ( 1 n ) 为第i + i 个报文与 l - i 第i 个报文的到达时间间隔，即i n t e r v a l 。= t f i - t f i 1 0 特别的，如果数据流只有一个报文， 则定义兀b 卸。 其他讨论 测量结果中，i n t e r v a l i ( 1 ( n ) 的精度与测量点的时戳精度以及应用目的有关。 只要测量点的时戳精度允许，可以根据应用目的的不同，使报文间隔周期i n t e r v a l l ( 1 i q i ) 精确到秒、毫秒或者微秒，从而影响f l t f 的精度。 3 2 1 3 测量方法 准确测量方法 输入 一t c p 流f 新到达报文p 的时戳t f 测量流程( 参见图3 - 1 ) 记第一个报文到达时刻为t f 甜。，最后一个报文到达时刻为t f 。 1 t c p 流f 的新报文p 到达，报文p 到达时间为t w 2 如果n e w f l o w 为真，则初始化f it l = o ，n r = 0 ；t f 。【n = t f ； 3 n 产n l ； 4 如果t c p 流f 结束，则转5 ；否则，转1 ； 5 t l k 确- ； 6 f u 仁玉堕二k ，测量过程结束。 。+ l 方法评价 设t c p 流长度为n ，则该方法时空开销见表3 一l 与表3 2 。 1 6 第3 章t c p 流分组特性测度研究 表3 - 1f l t f 准确测量方法运算次数 运算步骤 运算次数 n f = n v + l n 次 减法、加法以及除法各1 次 一苇，+ l 总计n + 3 次运算，时间复杂度为o ( n ) 表3 - 2f l t f 准确测量方法空间消耗 变量名变量类型占用字节数 届，肠“，乃 s t r c u tt i m e v a l 各8 个字节 n v i n t e g e r 4 个字节 f l t f f l o a t 4 个字节 总计共3 2 个字节 3 2 2t c p 流最小分片尺寸 3 22 1 测量动机 链路的m t u ( m a x i m u m t r a m n i s s i e n u n i t ) 限制了口报文最大尺寸。如果口报文的尺寸 大于m t u ，则将被路由器或者发送端分片( f r a g m e n t ) ，最后再由接收端重组m 分片。t c p 连接允许传输双方根据各自所在网段的m t u 协商m s s ( m a x i m u ms e g m e n ts i z e ) ，用于限 制t c p 数据包的最大尺寸，进而控制m 报文的大小，以此避免分片过程带来的开销( 参 考文献t c p i p 详解) 。为此，可以根据t c p 流的m 报文分片信息。推测链路m t u 的情 况，从而为m s s 的设置提供依据。 3 2 2 2 测度描述 测度名称 最小分片尺寸( m i n i m a lf r a g m e n ts i z e ) 测度参数 一t i c p 流f 所含报文总数n v t c p 流f 的第i 个口报文长度l e n f i ，i i n v t c p 流f 的第i 个口报文的m f 标记m f v l ，1 i n v 结果表示 该测度结果为一正整数，单位为字节 测度定义 t c p 流f _ ( s r c i p ，s r c p o r t ，d s t i p ，d s t p o r t ，t i m e o u t ) ，定义f 的最小分片尺寸 p m t u v = m i n 饱。 ；特别的，如果f 不含分片报文，则p m t u v = 朋磐 l e n r j 埘i p 脶= l l 掣7 其他讨论 对于t c p 流f 而言，当f 含有分片报文时，p m t l j f 即为整个链路的路径m t u ( 链 路m t u 的最小值) ；否则，p m t u f 只是路径m t u 的一个下界。 3 2 2 3 测量方法 准确测量方法 输入 一t c p 流f 的i p 报文总长字段( t o t a ll e n g t h ) l e n t 1 7 东南大学硕士学位论文 一t c p 流f 的m 报文m f f ( m o r ef r a g m e n t s ) 标记 测量流程( 参见图3 - 2 ) 1 t c p 流f 的新报文p 到达；将报文p 的总长度字段值赋予l e n f ，m f 标记值赋 予m f f ； 2 如果n e w f l o w 为真，那么初始化p m t u f - 0 ； 3 若m f r = i 且p m t u f - 0 ，则p m t u f = l e n f ，转7 ； 4 若p m t u f s 0 ，则l e n f = - - l e n f ： 5 若l e n f p m t u f ，则p m t u f = l e n f ： 6 如果t c p 流f 结束，则测量过程结束；否则，转l 。 图3 - 2p m t u f 准确测量方法流程 其它讨论 若p m t i i f 为负值，则表示t c p 流f 不含分片报文， k i p m t u v l 为所求测度 值；否则，表示t c p 流f 的最小分片尺寸为p m t u f 。 方法评价 设t c p 流长度为n ，则该方法时空开销见表3 - 3 与表3 - 4 。 1 8 第3 章t c p 流分组特性测度研究 表3 - 3 p m t u f 准确测量方法运算次数 运算步骤运算次数 d f f = i 且m f v = i 且p m t u f - 0 3 n 次 步骤4 ：p m t u v - 0 最多n 次 u n f = 一l e n f 及l e n t p m t u v晟多n 次 总计 最多5 n 次运算，时间复杂度为o f n ) 表3 - 4 p m t u f 准确测量方法空间消耗 变量名变量类型占用字节数 m f f c h a t 1 个字节 l e n f 、p m t u fu n s i g n e ds h o r t 各2 个字节 总计 共5 字节 近似测量方法 原理 文献【3 9 】通过统计发现，网络中的分片报文比例不足l 。本文通过对c e r n e t 江苏省网边界2 0 0 5 年1 1 月1 0 日的2 4 时流量统计发现，在所有t c p 分组中，分片报 文不超过o 8 。因此，一般情况下，分片报文可以忽略。如果忽略报文分片的影响， 则所获得t c p 流的“最小分片尺寸”就是“最大报文尺寸”该测量方法属于第二类 近似测量方法。 输入 一t c p 流f 的m 报文总长字段( t o t a ll e n g t h ) l e n f 测量流程( 参见图3 - 3 ) 图3 - 3p m t u _ - 近似测量方法流程 1 t c p 流f 的新报文p 到达；将报文p 的总长度字段值赋予l e n f ； 2 如果n e w f i o w 为真，那么初始化p m t u f = l e n f ，转4 ； 1 9 东南大学硕士学位论文 3 若p m t u f l e n f ，则p m 脚l e n f ，转7 ； 4 如果t c p 流f 结束，则测量过程结束；否则，转l 。 其它讨论 若p m t u f 为负值，则表示t c p 流f 不含分片报文，并且l p 打u f l 为所求测度 值；否则，表示t c p 流f 的最小分片尺寸为p m t u f 。 方法评价 设t c p 流长度为n ，则该方法时空开销见表3 - 5 与表3 - 6 。 表3 - 5p m t u f 近似测量方法运算次数 l 运算步骤 运算次数 l e n f p m