一种基于非背靠背包列简易化单源网络整体压力测量.doc

精品论文一种基于非背靠背包列简易化单源网络整体压力测量方法及其设计框架研究 宋佳，董巍 北京邮电大学信息工程学院，北京（100876）email:摘 要：本文首先定义了一种新的描述网络压力的数学模型，并在此基础上提出了一种使用非背靠背包列的单源主动测量整体网络压力的新测量方法，同时对此测量方法中的关键 指标进行了严格误差分析和测试参数定性分析，由于数学模型描述简单，又采取单点测量 可以大大消减以往网络测量的耗费和复杂性, 使得整体网络压力测量变得简单易用，实时操 控性强；同时针对此测量方式测量精度的要求给出了一个自由度很高的系统实现框架，能 够较好对其进行扩展和加强。关键词：网络测量，网络压力，单源测量，主动测量，包列测量 中图分类号：tp393.061.引 言网络测量是一种综合运用软硬件技术对网络性能和相应指标进行测量的技术，随着现 在网络规模的不断扩大，用户数量的增加，各种应用的加深和种类的增多，如 voip 电话业 务，p2p 数据共享技术和实时视频点播等，进一步增加了对网络测量技术的需求。对于运营 商而言，网络测量技术对于维护网络性能，提高网络质量和加强网络对各种业务的承载能 力有着不可替代重要作用。当今主要的网络测量技术，按照其测量方法分为主动测量和被动测量，按照其测量结 构分，可分为单点测量，多点测量（端对端测量以及分布式测量），按照其测量的指标分 又分为时延，带宽，丢包率和抖动测量，按照被测网络的关系分为合作测量与非合作测量 等。当今比较流行的主动测量有 nimi、iepm、amp、skitter 等，被动测量有 nlanr pma 和 coralreef 等，其中绝大多数属于多点测量，单点测量一般多用于非合作形式下的网络测量。对于网络压力指标而言，比较传统的定义一般为 b i （网络各链路有效带宽和）、 lossi （网络各链路丢包率和）和 i （网络各链路传输时延和）等，需要对网 络每个链路进行分布式测量，而且对于每种指标均存在不同的测试方法，测试复杂度和设 备要求较高。本文首先提出了一种新的能够有效描述网络压力的数学模型，并进行了数学推导，然 后对其进行了误差分析，并对需要用到的参数进行定型分析，接着对整个方法进行了详细 描述，突出了其区别与以往测量方式的易用性和有效性，根据此方法的特点针对性的设计 了一套用于实现的框架，为后续工作奠定了良好的基础。2.衡量网络整体压力的新定义为了描述一个网络中的设备所受到的网络压力的大小，能够用部分特性去描述整体特 性，并且能够有效定义网络设备压力的存在性，本文基于包对间隔通过某设备是否真实扩- 12 -大（在此节点对包对间隔插入过多的包而使时间间隔扩大），定义某设备节点在某时所受到的压力为（假设此设备的输入接口的带宽等于输出接口带宽，包本身长度并不发生变 化）：pi =a iafter- ibefore (2.1) 其中 iafter 表示测试输入端口包对通过 i 节点的之后的时间间隔； ibefore 表志测试输入端口包对将要经过 i 节点时的时间间隔；a 表示乘数因子用来调节 p 的数值，为正常数,如图 2.1a。p=0 表示设备节点没有压力； p 0 表示设备存在节点。 假设有效输入端口为多个，有效输出端口为一个，当其他输入端口的负载相对低时 ibefore 经过时设备 i 时，向其中插入的包较少，其不会影响到 ibefore 的变化，即 iafter = ibefore ；当其他端输入口的负载逐渐加大并导致需要插入更多的包，使得 iafter= ibefore 不再成立，而变为 iafter ibefore 时，说明除此端口外的其他端口造 成的负载对此节点产生压力，直观上来讲，可认为是由于设备压力的增加，导致两个已同 速率发出的包，已不同的时延到达，网络压力越大，向两个测试包对间隔中插入的背景流 量包越多，时延差越大，对此网络节点所造成的压力越大，或者说网络节点无压力是指一 包对通过此设备点时，不会因为其他接口的流量而其两者之间迫于某种压力而相对滞留。 以上为一般定义，现实中设备的输入带宽很少等于输出端口带宽的情况，根据输入端口的 带宽和输出端口不同关系存在两种定义的演变。2.1 测量输入端口带宽 biin 小于或等于输出端口带宽 biout定义：bp =a - - 1-biin iiafteribeforeliiout (2.2)如图 2.2 由于输出端口 biout b iin ,在无压力的情况下，字节数为 l 的包在带宽大的情况下biin传输时间会缩短，所以存在 iafter = ibefore li 1- biout ， p 0 表示设备节点没有压力； p 0 表示设备存在节点， p 0 不存在,如图 2.1b。2.2 测量输入端口带宽 biin 大于输出端口带宽 biout定义：bp =a - biin iiafteribeforeliiout-1(2.3)如图 2.3 由于输出端口 biout b iin ，在无压力的情况下，字节数为 l 的包由大带宽传入小 带宽时，包本身的传输时间增大，则b = - b iin iafter ibefore liiout-1(2.4)从而压缩了无压力情况下的包对时间间隔， p 0 表示设备节点没有压力； p 0 表示设 备存在节点， p 0 不存在,如图 2.1c。图 2.1 压力定义图,a 输入输出带宽相等,b 输入小于输出,c 输入大于输出n2.3 一个网络的综合压力表述现在的网络大部分都是分级配置的，即从用户到核心网的设备带宽逐渐增大， 假设一个由用户 a 节点到核心 b 节点存在 n 个节点设备，标号为 1,2. . n ，则上行时其中节点的压力遵循 2.1 所定义，则整个上行网路的压力为：biinpnetwork-up= a iafter- ibefore- li 1 -1iout (2.5)bb iinb由于式中 iafter = i1 before , l i1 = li 则ioutnpnetwork-up= a iafter- ibefore- li l i1 (2.6)1得：up- up- b 1in 1- 0pnetwork -up= a nafter1befor el1 bnout(2.7)当网络反向运行时，根据 2.2 定义有：1b iinpnetwork -down= a iafter - ibefore li nb iinbiout- 1(2.8)由于式中 iafter = i-1 before , l i-1 = li b 则iout1pnetwork -down= a iafter - ibefore l i-1- li (2.9)n为了与上行相区别，在形式上得：down - down - (2.10)pnetwork -down= a 1after即：nbeforel1 l ndown - down b nin - 1 0(2.11)pnetwork -down= a 1afternbeforel n b1outl1由于使用单点测量，则整体网络的双向压力可以定义为：l npnetwork = pnetwork-down pnetwork -up (2.12)由于得：无压力时： b ninb1out- 1= 1- b 1inbnout(2.13)down - down up - up = 0(2.14)因为：pnetwork =a 1afternbeforenafter1beforedown = up (2.15)所以： nbeforenafterdown = up (2.16)有压力时： 1after11beforendown- down a up - up0pnetwork = a iaftern则：ibefore 1iafteribefore(2.17)down - down up- up0(2.18)所以：pnetwork =a 1afternbeforenafter1beforedown up 1a fte r1befor e(2.19)以上结论可以看出，在理想情况下(不存在其它不确定延迟时)通过测量包对发出间隔 和返回时的间隔，完全可以知道网络上各个节点正面临的压力，从而给出一个简单易行的 整体网络压力的衡量标准：精品论文定义压力指数为：k 为放大因子。pindex= k down1afterup 1befor e(2.20)通过此指数可以有效的衡量，一个网络的压力水平，并能明确分辨出网络当前是否存 在压力，以及压力水平的大小,如图 2.2。图 2.2 网络整体压力测试包对转移过程2.4 参数的有效确定方法和误差分析up 本方法的配置参数主要有 l(包长度）、n（包列中包的数量）、e 1befor e（包对测量间隔）、e t 包列之间的间隔。以下对参数进行定性分析，为参数选择提供指导，同 时分析用此方法测量网络压力的误差的性质。由于此方法以网络时延为主要的测量依据，所以对于每个链路都会引入相应的噪声，噪声可分为压缩噪声和扩展噪声，如文献9所述。 首先研究一个包对经过一个节点的误差情况，定义噪声情况，设某节点引入的噪声为：i= icie (2.21)标准噪声定义为：n = / t l(2.22)i :i 节点引入的总误差， ic :i 节点引入的压缩噪声， ie ：i 节点引入的扩展噪声， ：l = n -1 l / c为标准误差， = i :系统的总误差， t n为接受到长度真值。根据文献9的有关内容，对本文而言，设路径经过的设备节点集为 p 1, p2, p3. . p n ， 其对应的出入口带宽为 c1, c 2, c 3. . c n , c n1 ，其中， c i 为 pi 的入口带宽， c i1 为 pi 的出口带宽，每个节点的出口带宽递增，因为本文所使用的包对（包列）间隔是非零的，为了符合文献9描述的模型，对上述内容添加细节如下:在 p1 前添加节点 p0 ，其入口带宽为 c 0 ，出口则为带宽 c 1 ，令 0= l / c 0 ,使得 在 p0 的入口带宽时包对间无测量间隔，令 p0 无压力，则 1 l /c 1 = 0 ,添加的细 节对本文网络模型并无影响。由于网路采取的单点测量机制，所以可以把此模型改变为端到 端的模型，其节点的安排是对称的 p 1, p2, p3,. . p n , . p 3, p2, p1 ，其中对称部分的出入口 带宽对调，取值不变。文献9所述，如果选取间隔为小间隔间 n =2 ，l 很小，所以 1 l /c 1 = 0 也将很小，所以条件等比于 n =2 ， 1 很小，误差概率密度满足9：0f min c / c i-1 , i g= 0 (2.23)if c / c -1 0- f c / c -1 -0down= p = 1after i (2.24)if x = f c / c -10xf t dt , x , x c / c i-1 (2.25)i c /ci-1误差点在 c / c i-1 ， i =i : c k c i , k i , n cmini n ，= x min c / c i- 1 , x c / c i ,i 出现冲击，其它点则形成正态分布，且e 0 ,由于误差主要是网络背景流量产生，说明在网络运行时以扩展噪声为主，也就是插包扩展为主，所以整体网络压力也可以描述为:down = up e t l , e p= e t l 1a fter1befor en networkn(2.26)得： pindex 1 (2.27)即：网络压力指数的测量值的分布与标准噪声分布相同。由于本文所述的模型中，仅有最后的 p1 满足 集要求，所以 e 将出现相应左偏，若由于网络的下行线路网络节点的压力越来越小，则在下行过程中当 i 节点之后的节点压力变小，i 节点属于 的扩展集 ，令 i = i : p p , k i , nkicmini n 包含 （由于本文篇幅限制此论点将在其它文章证明），因此误差密度函数在c / c i-1 i 均会出现冲击，而且群体左偏，所以当 n =2 、l 很小时，误差很大，将过 大低估网络压力。当 n 2 、l 很小（ n 2 ， 1 很小）时或者 n =2 ，l 很大( n =2 ， 1 相对大或者 l 很大)时， = c / ci -1 i 的冲击消失, 逐渐逼进正态分部，其方差为2d = =1 / n -1 (2.28)n其中 = 1i ,i1/ n - 1 ， 1= d i ,i 1 。所以通过 n 的增加或者 l 的增加来提高准确度，由于 l mtu ，所以 l 不能无限增加，因此可以选择适当的 n 来缩小方差，提高 的正态性。9已证明当 n 足够大时 接近完全的正态分布，其 e 稳定。up up = 1由于 1= 1befor e是使用泊松采样方法产生的，所以选值时针对 e 1befor e 的大小即可，所以选择的泊松分布的 参数应尽量小，但是由于网络压力是动态指数p = f t upindex-network p ，取 e 1befor e太大会导致 f p t t = 0 c , c 0 即两个测量包无法同时运行在近似具有相同网络压力的时间短上，导致新的误差产生，所以1beforee up 或 的选择必须折衷。 e t 即为网络发生压力变化的时间间隔，每发生1before一次网络变化就要针对性的进行相应的测量，l，n， e up ， e t 的关系满足：1before1ine t e up l / b n t (2.29)e t ：其是为了适应网络压力变化的快慢，其值确定主要与当时的网络使用群的习惯 f p t 而定，并要作相应调整，即 e t =af p t =b1/, a ,b= const ，其均值与当前 t1before网络压力成正比，与当前网络变化的速度成反比，由于是主动测量，为了减小 heisenberg 效应，并且降低测量包的丢包率，必须 e up 做到相应的扩大，n 相应的减小，l 相 应的增大，可以证明:1before 1inup-limite t e up l/ bn c(2.30)（由于篇幅所限，此方法网络测量的精确度极限问题将在以后的论文中讨论），这个调整 问题主要通过负反馈完成，如下文所述，但是 e t 的基值需要根据网络的高峰低峰的 具体情况而定，单位调整以分钟为宜。以上描述了如何选取合适的参数以使网络压力指数测量值服从正态分布，或者说影响网络压力值的误差是服从均值为零的正态分布，下文将提供一个实施测量的框架。3.测试方法关键性问题描述3.1 使用非背靠背的包列间隔对当前网络状况进行采样此提法是根据前人提出的背靠背包对测量有效带宽的方法描述衍生而来，指的是在 发送的包对或包列之时人为地添加时间间隔,来收集网络信息进行网络相应指标的测量，这里所指的是压力指标 pindex 。每对包之间的时间间隔相当于采样间隔。关于采样方式，在1 4文献中已有相应研究，主要分为：周期采样，随机附加采样，泊松采样，几何采样，自 适应采样2以及伽马采样3等。这里给出如何使用这些采样方式来设计采样时间间隔和测量包列的放送时间间隔：在以上采样中自适应采样和伽马采样相对于前四种采样较为复杂，实现较为困难但是精确性相对较高，而前四种采样方式实现较易，其中泊松分布具有无偏、 非周期性特点并且测试时间不可预测等特点，相对于其它采样方式优点突出，实现复杂度 低1，可以有效的运用到采样设计中。本文所用方法的采样间隔有两种：1、整个包列的发送时间间隔 t ，指整个包列的发送间隔，按照一个较大的时间间隔 来测量，这样可以有效收集在此段时间内的网络压力情况下，同时最大消除主动测量对于 网络本身的影响。2、包列中包之间的时间间隔 ，是用来在有效的包列中采集足够的数 据用于分析，并尽量克服网络本身的突发性和其它引起随机误差的问题。作为算法复杂性和采样方法优劣性的折衷，这两个间隔的产生均采用泊松方法产生 2 ， pnetwork 误差与e ， e t 有很大关系（误差分析中证明）。3.2 单点测试单点测试主要是指，由一台测试机所进行的，其是相对于端到断测量和分布式测量而 言的，由 2 所定义的网络压力方法，可以仅在一个设备中即刻完成相应的测量，此种测量 方法，相对于端到端而言由于时钟仅与本地有关，克服了端到端和分布式测量需要严格的 时钟校对问题，又去除分布式测量设备之间的协同的复杂性4，只要将设备接入网络即可 测量相应部分的网络压力，由于测量是基于每个路径上的设备插包思想的，所以所测量的 网络必须以所选路径为核心路径，并且上行和下性路径相对唯一（图 2.2），例如：星形 网络和总线网络。3.3 使用包列来替代包对包对模型本身是具有很多问题的，作为它的改善提出的多种包列模型，文献5给出 了详细的描述，本方法将借助包列模型，有效提供所收集数据效率，并克服有网络压力情 况下测试包丢失问题和包对所固有的一些测量缺陷。3.4 测量协议的选择基于文献6研究成果，在选择测量使用协议是 tcp,icmp 在测量延时时具有相同的精 确度，而 icmp 简单易用，实现起来负载度相对于 tcp 协议低很多，所以本方法将使用 icmp 协议作为测量协议。3.5 测量数据的滤波和误差处理数据的有效性和处理是进行压力估计的重点，其中包括两类问题：过滤错误数据，即 由于网络其它原因导致的测量数据明显不在正常范围内的数据，此类错误通常使用滤波算 法进行滤除；数据处理，根据采集的数据使用概率统计手段进行有效修正；为了简化易行 ， 本方法主要使用检验特殊数据，来使得数据处理不受异常数据的影响，精度下降。如果采用 相应的噪声滤波算法，如直方图统计技术或核密度估计算法，可以更有效的提高测量的精 确度。3.6 整体测量方法的流程描述测量简单流程如图 3.1，描述了一个基本的测量周期，整个测量是这样的基本周期组合而成，但是每个周期所用参数都会随时发生变化，整体测量是个动态过程。图 3.1 测试流程图4.测量框架设计研究：根据文献78设计测试工具框架的相应思路，为了使上述方法的实现更具有灵 活性，并能够有效对某些部分进行优化和升级，从而提高整个测量的精确度，本方法提出 如下设计框架如图 4.1：图 4.1 总体框架图4.1 用户接口模块提供用户的参数输入和测量结果的输出，此模块应该遵循最大自动化配置和最小化管理原则，根据用户的输入，动态的生成其它参数。此外，此模块还负责测量开始后实时结果的显示，以使用户能够时实观测结果。4.2 数据配置模块提供配置信息的生成和分发，对用户输入的配置进行数据认证，保证输入参数的正确性，并分发给各个系统。4.3 数据显示模块由数据生成模块提取数据，形成报表数据或图标，提交给用户接口，此模块可以嵌入 多种数据表格形式，呈现给用户多种角度的测量数据形象。4.4 系统测试包发生模块根据配置模块的要求，使用相应的采样方式，发送采样包列间隔，本文使用泊松采样 方式，并同步系统采集模块。本模块除了可选择采样方式外，也可选择用于采样的协议，本 文建议使用 icmp 协议，协议确定后要与系统采样模快进行协调，同时向数据过滤模块提交 自身相应信息。4.5 系统采集模块接受来自经过系统的响应包，并将信息提交给数据过滤模块。4.6 数据过滤修正模块数据过滤修正模块获得有 4.4 和 4.5 模块提交的相关信息，对其中的数据进行错误数 据过滤，背景噪声处理等， 或者灵活引入某种噪声滤波算法，提高数据的有效性。4.7 数据处理模块数据处理模块根据过滤的结果，进行数理统计运算，从而提供一个具有一定可行度的 概率意义上的网络压力的测量数据，此数据除了提交给存储模块进行存储，以备情景重现 外，还将提交给反馈模块，进行时实参数的配置，构成反馈系统。4.8 数据存储模块此模块存储测量包列发放和接受的信息，数据修正产生的有效数据和测试数据处理结果，以备场景重现和压力对比实验。4.9 系统反馈模块主要根据测量的压力结果来调整测量采集各种参数，当网络压力大时，可以适当增大 包对测量间隔 ，已减小网络压力过大引起的测量包列丢包过多的现象，同时减小对网 络本身的影响，减小主动测量的 heisenberg 效应，同时适当减小包列之间的间隔 t ，更 有效的跟踪网络压力的变化。当网络压力小时，则相反。此框架可以有效对此测试方法进行某些模块算法的有效变更，提高测量的精确性，并 能够随着研究的深入不断增加新的内容，进一步改进测量效果。5.总结本文提出了一种利用单点就能实现整个网络压力测量的新思路，方法简单易行，并对其进行数学模型的推导和严格误差分析，证明了其可实现性，接着提出一套有效利用此方法进行测量实现的框架，框架灵活性高，可在采样，数据过滤和数据处理等多个环节加强算 法利用，克服单点测量固有的精确性不高的问题，为后续更深入研究降低网络测量复杂度 和易用性提供了基础和新思路。参考文献1田海燕,王換招和李玉鹏泊松采样在基于 rmon 的网络测量中的研究及实现j微电子学与计算 机，2003，7：56-592baek-young choi, jaesung park, zhi-li zhang adaptive packet sampling for accurate and scalable flowmeasurementjieeecommunications society globecom ,5:1448-1452,2004.3francois baccelli,sridhar machiraju,darryl veitch,jean bolot. on optimal probing for delay and lossmeasurement j .proceedings of the 2007 acm sigcomm internet measurement conference,7: 291-3022007.4matthew roughan. a comparison of poisson and uniform sampling foractive measurementsj.ieee journal on selected areas in communications, 24:2299-2312, december 2006.5李星,谈杰网络测量综述j计算机应用研究 ，2005，2：5-136lin wenwei,zhang dafang,yang jinming,xie gaogang.on evaluation the differences in tcp and icmp in network measurementj.computer communications ,30 :428-439,2007 .7v.suryanarayana, k.chandra sekaran. active probing based end to end internet estimation tool j , ieee 8:397-400,2006.8vern paxson, an architecture for large-scale internet measurement j ,ieee communications magazine4:48-54,august 1998.9林 宇,邬海涛,程时端,王重钢等网络瓶颈带宽测量的噪声分析 j 电子学报，2004，4：552-556a simple network pressure measurement method based on the package series w