（通信与信息系统专业论文）ip网络链路时延和带宽利用率的有效测量模型研究.pdf

重庆邮l 乜学院硕1 ：论文 摘要 及时、准确获取网络内部各条链路的时延和带宽利用率信息，以便实时、充 分了解网络的状态，是资源管理、拥塞控制、多路径路由等网络管理与控制手段 的关键之。高速i p 网络要求测量方法满足快速、及时、准确和低开销的特点。 目前针对时延和带宽利用率的测量分别采用了不同的测量模型架构，要想同 时获得链路时延或利用率信息，必须启动两套测量系统，这样既增加了测量开销， 也不利于测量系统的维护和测量结果的进一步分析和使用。而且，现有的时延测 量模型存在测量精度差、安全性差等问题，影响了其在实际网络中的实用性。而 带宽利用率测量模型通常基于s n m p r m o n 机制，或基于类似n e t f l o w 的机制，加 重了路由器的处理负担，影响路由器的转发性能。 本文提出一种可以同时获取网络内部链路的时延和带宽利用率的测量模型， 称为线卡采集代理模型。通过设置于网络节点接口上的线卡采集器实时监测并统 计链路上的流量，由预先设置好的线卡采集代理点集合发来的探测包将统计信息 带回代理点，同时，通过计算发往同一条链路两个端点的探测包的往返时间差得 到该链路时延，各代理点将汇总后的结果向网络监测中心( n o c ) 报告，由n o c 进 一步得到全网监测结果。该模型以项点覆盖和边覆盖的相关理论为基础，证明了 以最小代价混合覆盖全网的问题是n p 一难的，并提出新的贪心近似算法，仿真结 果验证了算法的有效性。 作为模型的实现技术基础，本文提出的线卡采集技术便于硬件实现，符合未 来路由器技术的发展趋势，也可作为传统测量方法信息采集技术的有效补充。基 于f p g a 实现了线卡采集模块的硬件功能仿真，进行了模块级功能测试，结果显 示功能与性能达到了设计要求。最后，对整个模型系统进行了仿真测试，结果说 明文中模型是可行的。 关键词：测量模型，时延，带宽利用率，n p 一难，贪心算法，f p g a 重庆邮电学院硕十论文 一一 a b s t r a c t g e t t i n gd e l a ya n db a n d w i d t hu t i l i z a t i o no fl i n k si n 1 pn e t w o r kn o to n l v a c c u r a t e l yb u ta l s ot i m e l ya r eg o o dt ok n o ws t a t e so f n e t w o r k ，h o w e v e ri t so n eo f t h e c r i s i sn e t w o r km a n a g e m e n ta n dc o n t r o l l i n gs t e pf o rr e s o u r c em a n a g i n g ，c o n g e s t i o n c o n t r o l l i n g ，m u l t i p a t hr o u t i n ge t c t om e a s u r et h eh i g hs p e e di pn e t w o r ki nl a r g e s c o p e ，m e a s u r i n gm e t h o d sn e e dt om e e tt h er e q u i r e m e n t sf o r q u i c k l y , t i m e l y , a c c u r a t e l ya n dl o wo v e r h e a d b u tt h e r ea r ed i f f e r e n c e sb e t w e e nd e l a ym o n i t o r i n gm o d e l sa n du t i l i z a t i o n m o d e l s i fo n ew a n t st og e tb o t hd e l a ya n du s e t h e nh eh a st or u nt w om o n i t o r i n g s y s t e m s t h i sh a ss o m ea p p a r e n td r a w b a c k s a b o u tl i n k s d e l a ym o n i t o r i n gm o d e l s ， t h e ym a y b ei n a c c u r a t eo ri n s e c u r i t y a b o u tl i n k s u t i l i z a t i o n ，t h em o d e l sa v cu s u a l l ) b a s e do ns n m p r m o no rn e t f o w , w h i c hc a nb en e g a t i v ei m p a c to nt h er o u t e r s p e r f o r m a n c eo ff o r w a r d i n g i n t h i sp a p e r , w ep r o p o s eam e a s u r e m e n tm o d e lb a s e do nl i n ec a r dc o l l e c t i o n a g e n t ，w h i c hc o u l dg e te a c hl i n k sv a r i a b l ep a r a m e t e r si nn e t w o r k sw i t ho v e r h e a da s l o wa sp o s s i b l e o u rm o d e lh a st h ec o m b i n a t i o nv i r t u eo fv e r t e xc o v e ra n dl i n kc o v e r , a n di tc o u l dg e tl a t e n c ya n du t i l i z a t i o nu s e st h es a m em o d e ls y s t e mw i t hm a x i m u m r a t i oo fi n f o r m a t i o na n dc o s t s m o r e o v e gt h eq u e s t i o no fm i x e dc o v e rw i t hm i n i m u m c o s ti sp r o v e dt ob en p h a r d w ed e s i g nan o v e lg r e e d ya p p r o x i m m i o na l g o r i t h mf o r i t ，a n dg i v et h ee v i d e n c ef o ri t se f f e c t i v e n e s sb ys i m u l a t i o n l i n ec a r dc o l l e c t i o n ，t h ec o r ec o m p o n e n to fo u rm o d e lc a l lb em a d ei nh a r d w a r e i tc o u l db ev a l u a b l ec o m p l e m e n t st oe x i s t i n gi n f o r m m i o nc o l l e c t i o nt e c h n i q u e s a n d r e a l i z ei nh a r d w a r ei st h em o s tp o s s i b l et r e n d so ft e c h n i q u ed e v e l o p m e n t t h ea u t h o r h a sd e s i g nal i n ec a r dc o l l e c t i o nm o d u l ei nf p g a t h et e s tr e s u l t si m p l yt h a tt h e f u n c t i o n sa n dp e r f o r m a n c ea r eq u a l i t y f i n a l l y , t h es i m u l a t i o nr e s u l t ss h o wt h a tt h e m o n i t o r i n gm o d e li sf e a s i b l eu n d e rs i m u l a t i o ne n v i r o n m e n t s k e yw o r d s ：m e a s u r e m e n tm o d e l ，d e l a y l a t e n c y , b a n d w i d t hu t i l i z a t i o n ，n p h a r d ， g r e e d ya l g o r i t h m ，f p g a 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得重迭鲣电堂瞳或其他教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示谢意。 学位论文作者签名：幕爱踯 签字日期：妒争年细哆日 学位论文版权使用授权书 本学位论文作者完全了解重废整皇堂瞳有关保留、使用学 位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件 和磁盘，允许论文被查阅和借阅。本人授权重庞由g 电堂瞳可以 将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：融螂 签字日期：f ；f 年箩月乃e t ， 导师签名：7 妻红 签字日期：似f f 年f 月巧e l 重庆邮电。学院硕士论文 1 1 引言 第一章绪论 1 1 1 对i p 网络测量的必要性 未来，i p 网络是否能够继续取得巨大的成功，关键之一是看其能否提供令用 户满意的服务质量( o o s ) ，通常需要保证o o s 的应用以低时延、低时延抖动的实 时应用为主。但是，i p 网络在本质上只提供“尽力而为服务”，无法满足诸如v o i p 、 实时媒体等应用的o o s 要求。因而迫使网络服务提供商( i s p ) 改善网络设备性 能，增加传输带宽，如使用更先进的交换机实现业务处理，采用高带宽的光纤介 质满足高速数据传输的需要j 。这样增加基础设施的办法，虽然能在一定程度上 缓减用户数据传输带宽和o o s 保证的压力，但同时也使i p 骨干网络链路平均利 用率愈来愈低。产生这种现象的原因主要是i n t e r n e t 流量极端不对称，网络流 量的分布极不平衡及其增长难于预测，而快速的传输技术的出现使大量增加链路 容量在经济上可行，造成链路带宽的过量供应【2 j 。另外，今天的运营商缺乏对网 络内部链路贽源利用率情况的了解，也是造成链路带宽过量供应的原因之一。因 为如果不知道网络内部资源利用的情况，就无法量化提供q o s 与资源过量供应的 对比成本，运营商不得不采用宁多勿少地增加带宽的策略，靠进一步降低链路利 用率来满足低时延的应用需求【3 】。因此，当今天的运营商面对出于故障、拥塞引 起的网络震荡、不稳定进一步加剧拥塞，严重影响网络性能问题时，依靠带宽过 量供应，保持网络的低利用率解决这类问题【4 l 。这样与传统基于时分复用的电信 网络比较，大量的链路资源闲餐，使得基于统计复用的i p 网络高效的资源利用 率的优越性无从体现j 。 然而，仅仅依靠链路带宽过量供应，降低链路平均利用率并不能避免严重拥 塞和网络资源利用率的进一步下降【4 】，也就必然不能令用户满意，因为用户不仅 需要低时延，还需要低的时延抖动，要求网络利用率的低变化率1 2 】。因此迫切需 要大型i s p 和自治系统( a s ) 具有可行的控制网络资源、优化网络性能的管理和 监控机制。及时获取网络内部备条链路的时延和带宽利用率信息，以便实时。充 分了解网络内部的状态，是资源管理、拥塞控制、多路径路由等控制手段的关键 之。 而网络内部的动态信息只能通过测量的手段来获得( w i h i a m s o nc 和 p a x s o nv ) 。同时，高速i p 网络要求测量方法满足快速、及时、准确和低开销 要求。a c ms i g c o m m 从2 0 0 j 年开始连续举办了三届网络测量工作组会议，专门 重庆邮电学院硕十论文 讨论测量模型、体系、工具等问题，以期对动态路由调整和灵活的网络控制能力 提供测量支持。 1 1 2i p 网络测量技术应该满足的基本要求 i p 网络对网络测量技术的基本要求： 有效性 高速钡4 量 准确性 实时性 1 有效性：就是低丌销，是网络测量中研究的重要问题，因为要满足业务级、 应用级管理的现代网管系统( n m s ) 对网络参数的需求，网络测量过程需 要相当大的数据量和相当高的数据采集频率连续不断地监测网络状态及 变迁，例如，每隔1 5 分钟，以免漏掉相关变化、应用行为或业务可靠性的 衰退变化1 5 】。所以，在网络大范围内进行经常性的数据采集、通信、汇总， 必然引起大量的网络资源耗费。这意味着，收集网络带宽利用率信息时减 少对下层网络的影响是网络测量方法的基本要求【6 】。 2 高速测量：随着链路传输速率的快速增长以及i n t e r n e t 用户和流量的大 量增长，测量技术也必须满足高速测量的要求。 3 准确性：对网络控制的粒度越来越来细比如包级别、流级别的控制，而且 网络流量的可预测性低，需要测量的数据尽量准确。 4 实时性：因为要对网络资源进行实时的调度、控制，要求测量也能及时监 测到网络的状态变化。 1 2 选题背景 i p 链路带宽利用率是指在一段时间内i p 层的吞吐量占总吞吐能力的比重， 链路时延就是链路对数据包传输、传播、排队等待的总延迟。链路时延和带宽利 用率是i p 网络进行监测和控制的两个基本参数，通常两者对于不同类型的应用 表现的重要性不相同，实时性业务对时延比较敏感，而大数据量型业务对带宽利 用率敏感。但对于网络的一些精细控制，需要同时获取这两个参数，比如很多 q o s 路由选择算法将网络多条路径的时延和带宽利用率作为输入。而且，同时获 取链路时延和带宽利用率信息，可以更加细致的把握网络内部状态，因为同时获 取两个参数信息可以将两者在同一个时间轴上分析，能够发现网络中隐藏的问 题，比如出现带宽利用率低但是时延较大的异常情况时，网络管理者可以据此进 一步调查。在全网范围以最低开销、及时、准确获取这两个参数，对于合理规划 利用网络资源、平衡网络流量、动态服务器路由、服务等级( s l a ) 确认、错误 2 重庆邮电z 院硕十论文 ，7 故障定位检测等有非常重要的作用1 7 】j ，因此研究高速i p 网络的带宽利用率和 时延测量，对于网络管理和控制及网络发展具有重要的意义。e h u ，时延和带宽 利用率的测量使用的方法明显不同，较细粒度的带宽利用率依靠被动监测技术， 而时延测量需要通过主动探测包。所以要想同时获耿这两个参数，需要研究有效 的网络测量模型，在模型中合理运用主动和被动测量技术。另外，有效的网络测 量模型对于降低网络测量开销，以及确保网络测量的其他要求具有关键性作用。 论文选题是以重庆市科技攻关项目“高速i p 网络测量系统”为基础，主要 研究内容包括： 网络的有效测量模型研究 流量信息采集技术的研究 1 3 论文主要工作 1 主要研究内容和贡献 ( 1 ) 从i p 网络测量的必要性全网测量的基本要求出发，讨论和分析了现有 的测量模型存在的开销大、不能同时获得时延和带宽信息、信息采集影响节点转 发性能等问题。本文提出_ 种新的全网测量模型线卡采集代理模型，综合运 用了被动监测和主动探测两者的优点，能够同时测量时延和带宽利用率。系统用 于带宽利用率测量和时延测量的资源可在更深程度上共享，从而进一步降低了测 量开销。 ( 2 ) 证明了最小混和覆盖问题是n p 一难的，并提出两个有利于最小化开销的 贪心近似算法，仿真验证了算法的有效性。 ( 3 ) 作为模型的实现技术基础，本文提出了线卡采集技术，基于f p g a 实现 了线卡采集模块的硬件功能仿真，进行了模块级功能测试，结果显示功能与性能 达到了设计要求。 ( 4 ) 对整个模型系统进行了仿真测试，结果说明文中模型是可行的。 2 主要创新点 ( 1 ) 在现有测量模型的基础上，综合了顶点覆盖和边覆盖的优点，巧妙应用 了被动监测和主动探测技术，提出的测量模型能够同时测量时延和利用率这两个 不同的参数。 ( 2 ) 针对本文测量模型映射成的两个特定n p - 难问题，深入挖掘了其相互关 联因素，提出两个具有关联因素的贪心算法，使得最终的算法结果优于直接使用 两个无关联的贪心算法结果，为解决这种具有关联关系的n p 一难问题提供了一种 思路。 ( 3 ) 针对现有网络监测技术在高速网络环境下不能线速统计、影响所在节点 转发性能、无法满足大量实时任务对统计结果的实时查询需要等问题，提出的线 3 重庆邮叱学院硕十论文 卡采集技术对于网管任务或应用中所需的最普遍、最基本的那些统计任务用 f p g a ( 现场可编程门阵列) 实现，可快速、准确、及时地统计，不会对数据包转 发性能造成任何负面影响，符合未来路由器技术的发展趋势，也可作为传统测量 方法信息采集技术的有效补充。基于f p g a 实现，代价小，易于现场升级，增加 了采集功能的灵活性。 3 论文安排 论文按下面章节组织： 第1 章：绪论，简单介绍i p 网络测量的必要性，对网络测量方法的一些要求 指出论文工作就是为了满足这些要求所做的努力。 第2 章：研究现状与分析，详细介绍和分析了现有模型和信息采集技术，提 出可能存在的诸多问题，指明论文工作努力的方向。 第3 章：基于线卡采集代理的有效网络测量模型与算法仿真，论述模型结 构，证明模型的难点归结为两个n p - 难问题，提出近似算法并给出仿真结果， 结果验证算法是有效的。并简要介绍了测量模型系统的主要方面。 第4 章：线卡采集器的f p g a 实现，详细描述线卡采集器的功能模块结构， 以及每一个模块的具体实现和仿真测试。 第5 章：测量模型功能的o p n e t 仿真，在o p n e t 中搭建真实网络的模拟环境， 通过修改路由器节点模型，使其具备线卡采集器功能，让一些节点行使监 测代理功能，最终验证了测量模型的可行性。 第6 章是论文的总结与下一步工作的展望。 一4 重庆邮电学院硕1 论文 第二章研究现状与分析 2 1 概述 众所周知，s n m p r m o n l 9 】是i p 网络广泛使用的管理监视机制。网络管理中 心不仅仅关心网络上单个节点的状态和行为，也关心网络本身的流量。远程监视 r m o n 是指为了网络管理，通过网络上的一个节点( 通常是网络运行中心n o c ) 来监视整个网络。在s n m p 环境中，已经定义了r m 卟m i b 。r m o nm i b 规定了远程 监视器要采集和存储的信息，该规范中也定义了监视器的功能以及管理站监视器 的相互作用功能。为了监视全网，需要在网络中每个节点设置监视器，n o c 和各 监视器通过轮询( p o l l i n g ) 或事件报告( e v e n tr e p o r t i n g ) 将监视信息汇集在 n o c 。这种在每个节点设置监视器的方法虽然直观，但有个致命的缺陷是开销太 大，在实际网络环境中无法使用，不仅是s n m p r m o n 机制如此，其他测量机制也 遇到了类似的开销问题，这些开销包括： 设置在节点的监视器软硬件成本、设备维护的昂贵的人力成本 信息汇集的通信成本，主要是占用的链路带宽资源 监视器采集、存储信息时对所在节点处理器资源的耗费，会严重影响节点 的处理速度或吞吐量，从而使节点成为新的网络瓶颈 为了降低i p 网络测量开销，人们积极研究： i 一方面研究有效的测量模型，使得设置在网络中的监视器最少，精心设计 信息汇集的通信路径与通信时刻，使得通信成本最低，当然有效的测量模 型并不局限于只为s n m p r m o n 机制服务，不同的测量机制可以有不同的测 量模型； 2 另一方面测量模型离不开有效的信息采集技术的支撑，研究有效的信息采 集技术，目的是占用所在节点最少的处理器资源，从而不对节点的转发性 能造成负面影响。 同时，从i p 网络测量技术的基本要求得出，有效的测量模型和信息采集工 具需满足以下约束条件： 覆盖全网 结果准确 快速及时 本文从测量模型的开销方面着手，在满足上述约束条件下从l ，2 两方面进 行了较深入研究。下面是目前有关的研究现状和分析。 5 照庆邮l 乜学院硕十论文 2 2 有效测量模型研究现状与分析 2 2 1 问题描述 定义1 给定无向图g = ( v ，e ) ，其中v 是顶点集，e 是边集，s 是v 的子集，若 根据与s 中顶点按特定关系相关的各条边的参数，可以确定e 中任意边的参数， 则称s 是图g 的基于顶点的测量集。 定义2 给定无向图g = ( v ，e ) ，其中v 是顶点集，e 是边集，s 是v 的子集，a 是从s 中顶点发射的探测包集，若通过a 得到与s 按特定关系相关的各条边的参 数，可以确定e 中任意边的参数，则称a 是图g 基于边的测量集。 有效测量模型问题的目标是求给定图g = ( v ，e ) 关于流量和时延的最小顶点测 量集或最小边测量集。 2 2 2 现有测量模型概述 目前，有效的网络测量模型主要思想是将网络利用最小测量集覆盖，并且设 计一种使测量集相互合作的机制，利用资源共享使测量开销进一步最小化，从而 避免对运营网络的共享资源引起不适当的损伤。在网络中智能化设置测量集通常 是一些图论里的难题，类似于设备放置问题( f l a ) 中心设置问题( c p ) 、集合覆 盖问题( s c ) 、顶点覆盖问题( v c ) ，这些都是著名的n p 一难问题。同时在i p 网 中，利用路由器、交换机或者路由路径等条件，还可以挖掘出其他约束条件，比 如，非叶子结点的流守恒方程、路由路径树覆盖链路，使得找到最小测量集( 近 似) 成为可能。根据测量集覆盖网络方式的不同，有效测量可分为基于顶点覆盖 ( v c ) 、基于边覆盖( e c ) 、或混合覆盖( m c ) 。 基于顶点覆盖( v c ) 的测量集 顶点覆盖( v c ) 是指图g = ( v ，e ) 中v 的子集s 互v ，对任意e e ，e 至少有 一个端点属予s 。基于v c 的测量集是网络图的一个顶点覆盖的子集，利用面向 结点的采集工具统计网络参数信息。难点是找到个最小的顶点测量集。虽然采 用求解最小顶点覆盖问题的算法可以求出一个顶点测量集，但已证明，最小顶点 覆盖问题是个n p 一难问题，尚无多项式时间的求解算法，并且求出的测量集也 未必是最小顶点测量集。这是因为，在实际网络环境中测量集往往满足一些特定 的约束条件，如果加以合理利用可以有效减d , n 量集。例如下面所述的弱顶点覆 盖。 ，6 重庆邮也学院硕十论文 v v j ( b ) 图2 i ( a ) 圈g 的一个昂小顶点覆盖v cs = v l ，v 2 ，v 3 ，v 4 。( b ) 有向图6 的一个摄小弱顶点 覆盖集w v cs = v l ，v 2 弱顶点覆盖( w e a kv e r t e xc o v e rw v c ) 1 0 1 是网络流量测量方法的最新成 果。假定无向图g = ( v ，e ) 满足对任意1 ，矿有d e g r e e ( v ) 2 2 ，称s c 矿是图g 的若 顶点覆盖集，当且仅当执行以下操作能使e 中所有边可以被标记：( 1 ) 标记所有 与s 中顶点相关联的边。( 2 ) 若某个顶点v 的d e g r e e ( v ) 一1 条相关联的边已被标 记，则标记剩下的那条相关联的边。( 3 ) 重复第( 2 ) 步直到不能再标记新的边 为止。w v c 基于非叶子节点流守恒原理，且依托广泛使用的面向结点的测量技术 s n m p r m o n 代理，或n e t f o w 。结点的流守恒原理是流入结点的流量等于流出结 点的流量。当然流守恒只是近似，若考虑结点丢包、组播等因素时，流入结点跟 流出结点的流量并不总是相同，在当前的网络环境下相差低于0 0 5 6 】。将来网 络中媒体流的组播应用大量增加时，流守恒偏差可能加大。流守恒原理的具体应 用：假如一个路由器结点有k 条链路相连，当已知其中的k l 条链路的流量时， 则剩下的第k 条链路的流量根据流守恒原理也可以得到。如图2 1 所示，( b ) 中 只需在v i 和v 2 点设置监测工具，就可以得到网络图中所有边上的流量。这个方 案的关键问题是找到最小顶点测量集，也就是寻找最小弱顶点覆盖集，是n p 一难 问题，目前只能用近似算法求解。用类似于解决f l a 问题的贪心算法解w v c 问题， 如下所示。 w e a kv e r t e xc o v e ra g o r it h m ( g r a p hg ) 1 )u = g 2 )i = l 3 )g = g 4 ) w h i l e ( 6 的顶点集非空) 5 ) 选取图g = ( ，e ) 中度最大的顶点v 6 ) l = u + v ) 7 ) v7 = k 一 一 - 7 - 一 醛一 。、一甾 亚庆邮电。院硕十论文 8 ) e = e a d j ( v ) 9 )j = i + l 1 0 ) 对图g = ( 矿7 ，e 7 ) 反复删除度不超过1 的所有顶点及其相关联 的边，直到不能再删除新的顶点和边为止。令6 为最后得到的圈) 返回集合u ) w v c 方法可以使用目前广泛应用的监测工具如s n m p r m o 、代理，或 n e t f l o w 】，特别是n e t f l o w 工具可以基于流粒度的统计，测得的流量数据应用 范围更广，比如：基于使用的用户计费，服务等级约定( s l a ) 确认等。但是， 监测工具对所在结点转发性能的负面影响无法消除，而且，w v c 的算法通常选择 度较大的结点【6 1 0 】，流过结点的流量通常较大，所以监测工具必须以很高的速率 统计流量数据，加重了结点处理资源负担，很可能使此结点成为新的网络瓶颈， 例如图2 卜( b ) 的v 1 ，v 2 。s a m p l e dn e t f l o w 【i 2 j 和a g g r e g a t e dn e t f l o w 叫可以减 少一部分影响，然而在全网测量的实际应用中依然存在较大的问题【i 4 1 。 基于边覆盖( e c ) 测量集 边覆盖( e c ) 是指探测包集经过的边集包含图g 的所有边。基于c 的测量 集是向网络发射的探测包集，探测包沿路径集流过网络，利用面向路径的监测技 术获得网络参数。这种方法的关键步骤是对给定路径集配置最小探测包集，有两 方面的含义，第一是探测包数最少，第二是探测包占用的链路总代价最小，例如， 探测包经过的链路总数最少。寻找最小探测包集也是n p 一难问题，通常考虑探测 包共用来减少探测包数，让探测包沿最短路径转发来减少对链路资源的占用。探 测包共用思想如图2 2 所示，测量路径集p = p i ，p 2 ，p 3 的探测包集可以有多种 不同的选择，例如：( a ) ，( b ) 。其中，( b ) 考虑了探测包共用，明显减少了探测 包集的大小。接下来，关键问题是设计一个算法：寻找一个能够准确测量给定路 径集的最小探测包集，最小探测包集施加给网络的附加流量最小。可以证明这个 问题能够在多项式时间内映射成著名的n p 一难问题：设备位置问题( f l p ) i s l 1 6 i 。 可用启发式算法在多项式时间内求得对数因子的近似解，如下所示。 v o ( a ) 3 图2 2 测量路径p 】，p 2 ，p 3 朐探测包集 8 一 v 0 ( b ) 3 重庆邮电学院硕十论文 a 1 9 0 rj t h mo p t i m a l p r o b e s ( g ，p ，k ) i n p u t ：g ( v ，e ) = 网络图。 p = 待测路径集。 v _ 给定锚点集。 o u t p u t ：a ，= 对于圪和p 的一个最优探测包集。 1 ) a 。2 ： 2 ) f o re a c hp pd o 3 ) 令v ，屹，u f ( p ，) ，1 ( 只) ) ，使得i 舅6 m 最小，f ( 只) ，1 ( 只) 分 别为只的第一个和最后一个端点哆，。为v ，到h 的最短路径，v o 到_ 的最短路径为 ，( v 0 是网络图的一个探测包发射顶点) ： 4 ) 以2 以，u ，巧，。只) ： 其中圪求法如下：令c 为待测路径p 的集合，j 为k 的可选锚点集。对于j j 的固定成本为v 0 到v ，的最短路径长i ，| ，则屹为j 的一个满足 m i n ，；， 。l 乒l + 2 2 。m i n 州，( ，州圳 l 局l + l t ，。l 的子集f j 。令对圪的探 测包集为也，则4u4 ，为最后所求的最小测量集。 v n 测量位于其路由路径以外的链路时需要得到源路由的支持，但在实际网络 环境中，源路由选项常常得不到支持，因为i s p 或a s 由于安全原因，不允许使 用源路由选项。人们也提出了别的方法，将v c 和e c 结合起来使用，就是下匦描 述的基于混合覆盖( m c ) 模型。 基于混合覆盖( i c ) 测量集 基于混合覆盖( m c ) 测量集是指综合了v c 和e c 的特点，先确定个最小顶 点测量集，然后在顶点测量集的基础上确定最小边测量集。例如在网络图顶点广 泛设置监测代理【8 】【1 7 】【1 8 j 【1 9 ，监测代理使用探测包收集网络参数信息。比较而言， m c 的优点是比较灵活，可以组合利用被动测量和主动测量的优点。m c 的缺点是 模型比较复杂。m c 问题通常也是n p 一难的。 减少测量开销的其他方法 除了上述主要测量模型外，还有另外一些方法可以减少测量开销。文献 2 0 9 一 重庆邮i u 学院硕十论文 提出：用基于组播的方法测得的一组m 络路径端到端时延作为已知量，将更小的 路径段时延作为未知量，通过解一个线性方程组来计算更小的路径段的时延。文 献 2 1 研究了检测阀值警戒的方法来减少监测时的通信开销。分布式轮询引擎 ( 例如 2 2 ) 、关于“批处理”s n m p 一轮询消息的提议1 2 3 1 、更有效的s n m p 一轮询策 略i 2 4 j 等工作也是为了减少使用s n m p 代理测量开销。 2 2 3 有效测量模型总结 上面描述了不同类型的测量模型，v c 适合流量监测，e c 更适合于时延测量。 v c 的模型简单，但是需要在网络中广泛设置测量代理，设备费用、维护、人工 费用高，而且可能会影响所在结点设备的性能。e c 模型不需在网络中设置测量 设备，但需要网络中间设备某种形式的参与合作，比如i c m pe c h o ，发送的探测 流量需要精心计算，若不加控制会给网络带来额外的开销。m c 融合两者之长， 更加灵活。 这些模型存在的主要问题是： 网络的有效测量模型依赖于现有的信息采集机制，机制本身的缺陷比如， 测量速度、测量开销等问题，在网络测量时并不会改善和消除，特别是信 息采集对网络节点转发性能有时会产生较大影响。 目前带宽利用率和时延的获取分别使用了不同的模型机制，没有一种模型 能够既得到时延信息，又获得带宽利用率信息。实际中，两者都是相当重 要的，要同时获得这两个参数必须启动两套系统。这样一来，两个系统之 间资源便无法共享，比如，探测包共享或探测路径共享，所以，与使用了 资源共享比较，相当于对下层网络施加了更多的测量开销，也不利于测量 系统的维护以及测量结果的分析和使用。 本文针对这些问题在两方面进行了深入研究，一方面是信息采集技术，另一 方面是测量模型。关于测量模型，我们提出了一种混和覆盖( m c ) 模型，综合了 v c 和e c 的优点，能够充分利用被动监测和主动监测技术的优势，将时延和利用 率两个完全不同的度量同时在一个模型中获得。关于信息采集技术，在下面进行 详细描述。 2 3 信息采集技术现状与分析 2 3 1 现有采集技术概述 被动监测技术 被动监测是在网络中的特定点收集流量信息，如：s n m p r m o n 探测或c j s c o 1 0 重庆邮电学院硕士论文 n e t f l o w 工具，它们面向结点，从网络设备( 路由器、交换机、主机) 上收集 监测信息，也有的是一个独立的设备，面向链路，被动地监测网络链路的流量， 如o c x m o n 。这些工具可以用来收集统计信息和计费信启、测量单独网络设备的 性能( 例如，链路带宽使用) 。无论如何，除非在每个设备或链路上安装监测工具， 否则，这些工具无法监测涉及多个部分的网络参数，像多条链路或路径流量。基 于软件的测量技术，先天决定测量速度很难适应测量高速网络环境下带宽，而且， 要占用所在路由器的处理器资源，有些技术严重影响路由器吞吐量( 例如， s n m p r m o x 代理会影响所在路由器的吞吐量，严重时使所在路由器吞吐量减少 l j 一2 0 l 6 】) 。所以抽样测量、流量聚合也是监测技术的热点之一，如s a m p l e d n e t f l o w 旺 和a g g r e g a t e dn e t f l o w d 3 i ，对节点减少了一部分影响。现有的基于硬 件实现的技术如o c x - m o n l ”】，需要专门的硬件( 例如，d a g 卡、g p s 天线、分光器) 和独立监测工作站【2 ，通常用来离线式( o f f 一1 i n e ) 的i n t e r n e t 流量特征分析和 建模，不利于在全网广泛布置和维护这些高成本的设备，难以达到及时收集全网 参数的目的。 主动监测技术 成熟的主动监测工具有：p i n g ，t f a c e r o u t e r 2 ，s k i t t e r 28 1 ，t c p p i n g f 2 9 】。 这些测量技术属于主动测量的范畴，测量过程中产生新的网络流量，这些注入网 络的新的流量是为了引起网络部件的特殊响应( 如：t r a c e t o u t e r ) ，至少要多个 网络内部部件某种形式的参与。要完成主动式的测量要求网络内部各元素广泛的 合作如，i c m pe c h o 请求应答响应，然而，常常为了安全等因素使这种合作不可 得，例如，常用的i c m p 请求应答机制会导致d o s ( d e n i a lo fs e r v i c e ) 攻击，所 以i s p 或a s 经常会拒绝合作，t c p p i n 9 1 2 9 】就是对付这种问题的一种方法。另外， 主动式的测量给网络增加了额外的载荷，这些附加的流量若不仔细控制，会扰乱 网络，产生h e i s e n b e r g 效应，歪曲网络分析结果1 3 0 。这一点体现了有效的网络 测量模型研究的必要性，因为有效的测量模型的目的正是为了使网络附加的测量 流量最小化。 也正是因为主动时延测量向网络注入了流量，这些流量穿越了网络内部，切 身“感受”了网络内部性能，所以精心设计的注入流量反映出来的时延可以间接 推断网络内部参数，这也是主动带宽测量技术基本思想。 总的说来，带宽测量比较困难【3 ”，特别是在高速网络环境下准确测量带宽更 加困难。主动带宽测量技术简单的说是利用时延推断带宽，已经出现了大量的成 果，诸如n e t t i m e r 3 ”、p a t h c h a r 3 2 1 、c p r o b e 3 3 】、p a t h r a t e 3 剞、p t v s 3 5 】等。这些 工具的基本思想是通过精一山安排注入网络的信息包，包括包的数目、包之间的间 隔、包的大小等，然后依据包返回的信息利用统计推断方法估计网络路径的带宽 信息，这些带宽信息，有的是路径瓶颈带宽，有的是链路容量，有的是有效带宽， 照庆邮电学院硕 论文 或者他们之中的几个f 3 4 j 1 3 6 j 。这些技术同时也是面向路径的，简单、灵活，不需 要在网络中进行特别的设鹭，特别适合于网络用户或网络研究人员用来分析指定 网络路径的流量行为。所以成为目| j 带宽测量研究的热点之一，但毕竟是对网络 带宽的估计，偏差不可避免存在，特别是对高速网络测量时( 例如，超过5 0 0 m b s ) 精确度仍有待提高p 。而且测量时向网络注入的探测包数相对太多( 为了精确测 量带宽，源端需要发送一系列的探测包，比本身时延测量引起的额外流量多很多 倍) ，限制了其应用范围。目前还没有发现被用来全网带宽监测。 2 3 2 采集技术总结 从全网测量的角度来看，与主动测量相比较，被动测量工具本身在统计流最 数据时完全没有附加流量和h e i s e n b e r g 效应，这些优点使人们更愿意使用被动 带宽测量技术进行全网测量。但目前的被动监测技术存在缺陷： 对所在节点线速转发性能影响较大 统计速度跟不上链路传输速率的增长速度 从上面的分析可以看出，在高速网络环境下，不论是被动监测技术还是主动 探测技术都遇到了极大挑战，现有技术各有其优缺点。从全网带宽利用率( 流量) 测量的角度来看，被动监测仍然是目前必须依赖的技术，但必须满足两点要求， 点是不会对所在节点的数据包转发性能产生负面影响，另一点是能够进行线速 统计。我们针对这些问题提出了线卡采集器技术，基于硬件实现，不会对节点转 发造成任何负面影响，而且能对网络数据( 数据包数，字节数，简单的流) 进行 快速准确的统计。 2 3 3 线卡采集器 随着传输技术的迅速发展，链路传输速率快速增长，从o c - 3 ( 1 5 5m b s ) 到 o c 1 9 2 ( 1 0o b s 1 ，甚至o c 7 6 8 ( 4 0o b s ) ，相应地，路由器也需要能够快速处理。 另一方面，路由器为了保证0 0 s 需要完成的功能也在不断增加，如四层路由 ( l e v e l - 4r o u t i n g ) 、防火墙、m p l s 、d i i t s e r v 、基于流调度等功能”“，路由器已 逐渐成为限制网络速率的瓶颈。基于电子技术的路由器将接近其性能极限，全光 路由器中光数据包的缓存、光包头的读写等难题尚未很好解决，人们依赖于电路 由器的体系结构的改进来提高数据包处理速度。目前，高端路由器大多采用线卡 转发引擎加高速交换结构来实现1 3 8 】。为提高转发速率，引擎通常使用a s i c 来设 计，而且发展趋势是在硬件中提供更多的功能口9 1 。关于这一点有其技术方面的深 层次的原因：c m o s ( 互补金属氧化物半导体) 在更新换代上满足1 8 2 4 月翻一 番的m o o r 定律，但这只局限于晶体管密度。考虑到全局布线因素，交换芯片的 1 2 弧庆邮l 也学院硕十论文 时钟速率每一代仅能增加5 - 1 0 所以运行其上的软件处理速率增加有限，而且 由于高速路由器线卡功耗、空间、健壮性等的要求，限制了线卡上网络处理器 ( n p ) 的个数，故依靠多个处理器并行来提高软件速率、增加功能的想法不太 实际“。所以利用芯片卜越来越多的品体管实现更多的功能成为路由器设计的长 远发展趋势。 为了监视下一代极高速链路的流量，i e t f 工作组也有人提出了用专用硬件 结合流量压缩与采样技术完成对o c 7 6 8 的监测，同时，也认为部分功能可能嵌 入路由器线卡硬件中1 4 0 。 本文针对目前i p 网络监测技术的不足，提出了线卡采集器，在包分类的部 分模块基础上增加一些功能来实现，能够快速准确的实现数据包的统计 ( p a c k e t s s 、b y t e s s ) 、简单的流统计( p a c k e t s c l a s s 、b y t e s c l a s s ) ，作为现有测量 方法的补充机制。主要特点是用硬件实现，几乎不会对节点处理资源造成影响， 同时，实现线速统计，不会丢失信息，也符合路由器设计的发展趋势。而且，能 够实时响应探测包的对统计信息的查询，可以为一些需要及时获取网络信息的业 务和应用提供测量支持，比如将测量结果作为q o s 路由算法的输入，为动态服 务器选择提供依据等。本文对线卡采集器的实现是基于f p g a ( 现场可编程门阵 列) ，用f p g a 实现难度低，成本小，能够进行现场升级，增加了硬件实现功能 的灵活性，从而能满足更大范围的应用需求。 1 3 重庆邮电学院硕十论文 第三章基于线卡采集代理的有效测量模型 3 1 概述 本文工作的目标是针对大型i s p 网络或a s 确定有效的测量模型，在准确、 及时测量的基础上最大程度的减d , n 量开销： 给定链路( 子) 集合的带宽利用率( 流量) 测量。通过统计段时间内 链路上承载的载荷或者流量值，与这段时问链路所能承受的最大载荷之比，就是 链路的带宽利用率。通常固定链路的最大载荷是定值，可以通过查询网络配胃的 链路标称速率( 或其他形式的速率) 得到，带宽利用率随链路载荷或流量值变化， 所以等价于链路流量值的统计。很明