（计算机应用技术专业论文）基于排队分析的端到端可用带宽的测量方法研究.pdf

摘要 摘要 随着因特网规模的不断扩大，如何能更好地管理、利用因特网已引起人们 的广泛关注。为达到这一目的，对因特网的网络性能进行测量是必不可少的。 影响因特网整体网络性能的因素有很多，端到端路径可用带宽是其中最重要的 因素之一。到目前为止，研究者们已经提出了多种测量端到端路径可用带宽的 方法。这些方法大体上可分为两类：自拥塞测量方法和基于数学模型的测量方 法。经过研究发现，自拥塞测量方法通常要使路径上的链路发生拥塞，因此这 种方法有可能会严重影响链路上的其它流量；而目前已有的基于数学模型的测 量方法，虽然它们对链路上其它流量的影响较小，但由于它们所采用的模型往 往过于简单以至于不能很好地描述因特网的实际情况，因此准确性不高。 针对已有方法的缺点，本文提出了一种基于数学模型的测量方法：基于排 队分析的端到端可用带宽测量方法( m e 鹤u r e m e n to fe n d 勘e n da v a i l a b l e b a n d 证d t l lb 髂c d q i l e u i n g 锄a i y s i s ，b q a ) 。b q a 继承了基于数学模型的测量 方法占用网络资源少的特点，同时又考虑了因特网流量自相似，远距相关等基 本特点。该方法发送探测流收集紧迫链路的状态信息，并采用渐进变异系数作 为工具从信息中提取出与紧迫链路可用带宽有关的量，在此基础上通过对紧迫 链路进行排队分析，可由渐进变异系数计算出紧迫链路的服务强度，进而推导 出整条路径的可用带宽值。 本文使用网络模拟器n s 2 对b q a 测量方法进行了仿真，并与其它测量方 法进行了比较。仿真实验的结果表明b q a 测量方法不仅具有基于数学模型的 测量方法对路径其它流量影响较小的优点，同时也具有与自拥塞测量方法相当 的准确性。 关键词：可用带宽，紧迫链路，排队服务系统，渐进变异系数 a b s 饷c t a b s t 阳c t a si n t 锄e te x p a n d s ，h o wt ob 嫩盯m 锄g e 锄du t i l i z eh n c r n e th 船c 默d e x 伦哪i v ec m l c 啪t b 解h i e v et 1 1 i sp l i f p o s e ，i ti sn e c e s s a r yt om e 嬲u 坞m c p e d b m 锄c eo fi i l t e m c t 1 1 1 e r c a r eal o to ff 缸t o r s i i i f i u e n c i i l g t l l ew h o i e p e r f o m 锄c eo fi m e m e t ，a i l dt h e d 砌- da v a i l a b i cb 肌d 、v i d t l li so m o ft l l em o s t i m p o r t a l l tf 砬t o r s u pt i l ln o w ，a r c h e 塔l l a v ep u tf o r w a r dm 锄ym 幽d st o m e a 翻j l m ee n d 船e n da v a i l a b l eb 剐“晰d t l l t h e s er n e t l l o d sc a nb ed i v i i i c di n t ot 、o c a t e g 甜e s ：o b a do ns e l c c o n g e s t i 锄dt l l eo t l l e rb 蹴d m 劬锄a t i c a lm o d e l t h e 删= t i l o d sb 勰c d s e l f - c o n g e s t i o nm m l l yi l l c i l rc o n g e s t i o n t l l ei i m 岱o ft l l e e n d t o 枷p a t l l ，t i l c ym a y 撒c to t l l 盯t r 桶co fm ec o n g c s t i v el i n l 【s r i o 懈l y 刖t h o u 曲i l 圮m c t l l o d sb 雒e do nm a t l l 锄a t i c a lm o d c l1 l a v ci i 砌ee 彘c c 伽衄衔co f t h ec o n g e s t i v el i m 墨，b e c a u t l l em o d e i st l l a tt l l e ya d o p ta r ct o o 如p l et om o d e l i n t e m e ta c c u r a t e l y ，t l l e c u 瑚i c yo f t l l e 辩m e t t l o d si sn o th i g h t bo v m et h cs h o n c o m i l l g sm e n t i o n e da b 0 v e ，w ep r o p o an e wm e t h o d w l l i c hb a so nt l l eq l l e l l i n ga n a l y s i st om e 鹤u r et l l ee n d 勘一e n da v a i la _ b l eb a n 捌d t l l ， 缸dt l l em e t l l o di sn a m e d 越b q af o rs h o f t a st l l em e t h o d sb 鹊e do nm a t h e i 】n a t i c a l i n o d e l ，b q ae n g r o s sl i 砌en e t 、 竹f k r e s o u r c e a tt l l e 跚et i n l e ，i tt a k e si n t o c o n s i d e r a t i o nt l l ec h a r 矧s t i co ft h ei m e m e t 仃a f n c ，s u c ha s l f s i m i l a r i l y 锄d l gm g ed e p e n d e l l c e t or n e a 汕et i 圮e n d 勘e 】帕a v a i l a b kb a n d 、i d t l l ，b q a 鲫溅 t l ：幛p r o b i n g 们伍ct oc o l l e c t 也ei l l 】衙m a t i o no fn 坞t i g h tl i n k 锄da d o p t sm e a s y i n p t o t i cc o e 伍c i e n to f v a r i a n c et op i c ku pt t 嵋i n f o l l i l a t i o nw h i c hh 鹤l a 虹诵t l i m ea v a i l a b l eb 柚d w i d mo f t h c 右g b tl i l l l 【1 协u g l lq u e i i i n g 猢l y s i so n 龇t i g h ll i n l 【 i t f i g u r e so u tt h es e r v i t 培i m e 船i 锣o f t h et i g h tl i n kb yt h e 鹤y r i l p t o t i cc o c 伍c i e mo f v a r i a n c e ，趾dt l l g e t st l l ec l l d t o 锄da v a i l a b l eb 锄d 、】l ，i d t l l w bh a v eu s e d 坨n e t w o r ks i m u la _ c o rn s 2t os i i n u l a t eb q a 觚dc o m p a di tt o o n l c rm e 鹬u r e m e mm e m o d s t h es i m u l a t i v e 娜l t ss h o wt l i a tb q an o to i l l yl l 船 l i t t l ee 位c to no t h e r 仃a 伍co f t l l el i i l k s ，b u ta l s oh 雒m ea c c u m c yc 伽叩耐b l et om e m e t h o d sb 船e do ns e l f c o n g e s t i o n 垒! 墅型 - _ _ _ _ _ _ - _ 。- _ - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 。- _ _ _ 。- _ _ _ _ _ _ _ - 。_ _ _ - _ _ _ _ _ - 。- 。_ _ _ 。 k e yw o r d s ：a v a i l a b l eb a n d 讪d m ，t i g h tl i i l k ，q u e u i n gs y s t e m ，勰y m m o t i cc o e 币c i e n t o f v a r i a n c c u i 第一章绪论 第一章绪论 第一节课题背景 i n i e m e t 作为人们改造世界的一大成果，其设计的复杂性和给人们带来的便 捷，可以让人类有史以来的任何一项发明创造都大为逊色。近几年来，随着网 络传输技术的日新月异，h l ：t e r n e t 的网络处理能力得到很大提高，网络应用得到 了极大丰富，i n t e m e t 用户也呈爆炸性增长趋势。但是i i l t c m d 日益多样的功能 和快捷的速度，是以其复杂的组成和不断扩充的规模为代价的。i n t e m 吼的这种 扩张使网络在可扩展、安全、服务质量和创新性等应用方面也面临新的挑战。 为了使i n t e m c t 稳定地、安全地为人类服务，人们迫切地需要了解网络的 运行环境，提供改善网络性能和功能的可量化的依据，为网络应用和技术的改 进提供参考，从而为掌握网络运行的客观规律提供系统的概念和方法。因此， 作为了解网络行为特征的一项努力，网络测量技术应运而生。 网络测量主要分为三个研究领域：性能测量、建模与网络控制。这三个领 域相辅相成，缺一不可：性能测量通过精确地捕捉定量的m e t 及其活动的 数据( 例如网络带宽、拥塞程度、丢包率等等) 为人们对网络行为的建模提供 了基础；人们通过模型，就能对网络的未来行为进行预测，从而能对网络进行 优化及控制；网络控制必然会对网络的性能产生影响，而这一影响又可以通过 性能测量进行观测。 网络测量几乎涉及到了h n e m e t 的每一个方面，比如网络监视、网络质量 控制和辅助性网络管理、防范大规模网络攻击、协议排错等等，因此在i i i 时n c t 这样一个复杂的系统中，通过使用网络测量技术所得到的信息对人们了解这个 复杂系统表现出来的一些未知行为至关重要。 国外对网络测量的研究始于7 0 年代初，逐渐成熟于8 0 年代，9 0 年代己渐 成体系，在网络测量的方法、工具以及网络基础设施框架和流量的测量模型等 方面都做了探索和改进。而我国网络的发展起步较晚，9 0 年代初才引入h n 啪c t ， 虽然近年来随着经济的发展，我国i i i i c m e t 用户呈几何级数增长，使我国己成 为世界上i n t e m e t 用户数第二的国家，但我国对网络测量技术的研究还相对落 后。因此，i l i t e r n e t 的测量分析已成为学术界，工业界和国家政府部门普遍关 第一章绪论 心的重要问题之一。 第二节课题研究意义及研究生期间完成的研究工作 随着h n c m e t 得到越来越广泛的应用，网络性能也越来越受到关注，影响 网络性能的因素很多，路径可用带宽就是其中最重要的因素之一。对于网络运 营商来说，可以根据带宽的状况来指导网络维护和运行、扩容规划工作；对于 网络协议和应用的开发者来说，可以根据网络带宽的状况优化其协议和应用的 性能；网络用户也可以根据带宽选择合适的服务器，如流媒体服务器或代理服 务器的选择。 作为网络测量的重要组成之一，可用带宽的测量非常困难，其主要难点在 于：没有统一的可用带宽的准确定义；可用带宽随时间不断变化；长时间内， 它的变化范围比较大。 针对路径可用带宽的测量，研究者们提出了许多种方法。这些方法大体分 为两类，即自拥塞可用带宽测量方法和基于数学模型的可用带宽测量方法。这 两类方法各有自己的优点及缺点。自拥塞方法具有简易性、鲁棒性的特点，但 是它通常要发送过快流量以使链路发生拥塞，从而这种方法有可能会影响链路 上的其它流量；对于目前提出的基于数学模型的方法，虽然它不会引起链路的 拥塞，但它的准确性很大程度上依赖于所采用模型对i n t e m c t 描述的准确性， 目前的方法采用的模型往往过于简单，与i n t c m e t 的实际情况不符合，因此准 确性不高。 针对目前方法的缺点，本文提出了一种基于数学模型的测量方法：基于排 队分析的端到端可用带宽测量方法( b q a ) 。这一方法继承了基于数学模型的 方法占用路径带宽少的特点，同时，它又考虑了i n t e m c t 流量自相似，远距相 关等特点，并采用渐进变异系数这一工具将流量的这些特性包含了进来。在此 基础上，通过对链路进行排队分析，在渐进变异系数与紧迫链路服务强度之间 建立了联系，进而能确定路径的可用带宽。 对于本文提出的基于排队分析的端到端可用带宽测量方法，本文通过使用 n e t w o r ks i m u l a t o r 2 ( n s 2 ) 网络模拟器进行了仿真，收集了大量测量数据，并 在此基础上对仿真结果进行了分析与总结。 2 第一章绪论 第三节论文结构 接下来的第二章主要对i i l t c ：r r i e t 网络测量作总体上的介绍，包括i n t c r i l e t 网 络测量分类，网络测量的方法等。 第三章对h l _ t e m e t 端到端路径可用带宽测量的各种方法进行了介绍，指出 了各方法中存在的问题。 第四章详细介绍了基于排队分析的端到端路径可用带宽测量方法的基本思 想，并提出了测量算法。 第五章通过仿真实验，在基于排队分析的端到端路径可用带宽测量方法与 其它路径可用带宽测量方法之间进行了比较分析，最后对本文提出的测量方法 做出了评价。 第六章对论文进行了简要总结，并且提出了今后的研究方向。 一3 第二章i n t c m e t 网络测量概述 第二章i n t e r n e t 网络测量概述 第一节网络性能及i n t e m e t 网络测量的定义 网络性能可以采用以下的方式定义【l 】：网络性能是指一系列对于运营商有 意义的，并可用于系统设计、配置、操作和维护的参数进行测量后所得到的结 果。可见，网络性能是与终端性能以及用户操作无关的，它是网络本身特性的 体现，可以用一系列的性能参数来测量和描述。 从空间的角度来看，网络性能可分为两种结构：立体结构模型和水平结构 模型。i p 网络就其协议栈来说是一个层次化的网络，因此，对m 网络性能的 研究也可以按照一种自上而下的方法进行。立体结构模型就是以m 层的性能为 基础，来研究m 层不同性能与上层不同应用性能之间的映射关系；对于网络的 性能，用户主要关心的是端到端的性能，因此从用户的角度来看，可以利用水 平结构模型来对m 网络的端到端性能进行分析。 i n t e m c t 网络测量是指利用有效的仪器、网络探针和工具软件，对i 珊锄e t 的各项网络性能进行测量，以提取各种关于网络健康状况的参数指标。它是对 网络行为的观察和评估，并力图发现影响网络外部特征的主导因素。 第二节网络性能参数 对网络性能进行度量和描述的工具就是网络性能参数，它的制定必须遵循 如下几个原则： ( 1 ) 性能参数必须是具体的和有明确定义的 ( 2 ) 性能参数的测量方法对于同一参数必须具有可重复性，即在相同条件 下多次使用该方法所获得的测量结果应该相同。 ( 3 ) 性能参数必须具有公平性，即对同种网络的测量结果不应有差异而对 不同网络的测量结果则应出现差异。 ( 4 ) 性能参数必须有助于用户和运营商了解他们所使用或提供的i p 网络性 能。 d 第二章i m e t 网络测量概述 ( 5 ) 性能参数必须排除人为因素。 国际上对i p 网络性能参数存在两种定义方法：i t u ti 3 5 0 标型”和i e t f i p p m ( h l t e m c tp r o t o c o lp 刊白删肋c em e 嬲u r e m e n t ) 工作组定义的一系列 r f c 【3 】【4 】【5 】【6 】【7 1 【8 】【9 】。我国采用的“口网络技术要求一网络性能参数与指标 ( y d 厂r l l 7 1 2 0 0 1 ) ”标准根据i t u t 相关标准定义。 2 2 1 i t u t 对i p 网络性能参数的定义 i t u t 定义的网络性能参数1 2 】包括； ( 1 ) i p 包传输时延( i p t d ) ：指两个相关i p 包传送参考事件的时间差( t l - 乜) ， 其中离开事件发生在t 1 ，进入事件发生在t 2 ，这里t t 1 。 ( 2 ) i p 包时延变化( i p d v ) ：在一段较短的测试时间间隔内，最大口t d 与 最小m 1 d 的差值。 ( 3 ) 1 p 包误差率( 口e r ) ：错误i p 包传送结果与所有传送口包的比值。 ( 4 ) i p 包丢失率( i p u t ) ：丢失i p 包传送结果与所有传送m 包的比值。 ( 5 ) 虚假i p 包率( s p i l r i o 惦口p a c k e t f a g e ) ：一个出口测试点的虚假i p 包率 等于在一个特定时间间隔内在该测试点上观测到的虚假i p 包数量除以该时间 间隔。 ( 6 ) i p 网络的流量参数( n o wr e l a t e dp a r 锄e t e r s ) 。流量参数包括：i p 包吞 吐量( m p t ) 与基于字节的m 包吞吐量( p o t ) 。p t 指一个出口测试点的 i p 包吞吐量等于一个特定时间间隔内在该测试点上观测到的所有成功i p 包数 量除以该时间间隔。口o t 指一个出口测试点的基于字节i p 包吞吐量等于一个 特定时间间隔内在该点上观测到的成功i p 包中的所有字节数量除以该时间间 隔。 2 2 2 ，r f 对i p 网络性能参数的定义 i e t fi p p mi 江c 文档提出了一整套口网络性能指标、取样、统计的方法， i 江c 2 3 3 0 【3 1 描述了其总体结构并讨论了取样方法。口p m 工作组已经和正在定义 的性能指标包括： ( 1 ) 连通性川( c o 曲e c t i “t y ) ：连通性也称可用性、连接性或者可达性，严 格说这应该是网络的基本能力或属性，不能称为性能。 一5 第二章i n t e m e t 网络测阜概述 ( 2 ) 单向延迟【5 l 和丢包嘲( o n e w a yd e l a ya n dl o s s ) ：设数据包第一比特离开 源端的时刻为t ，包的最后一比特到达耳的端的时刻为t + l l ，则h 为源端到目 的端的单向延迟；单向丢包可用数值o 或l 表示，单向丢包为o 指目的端接收 到了源端发送的包，为1 指目的端没有接收到源端发送的包。 ( 3 ) 双向延迟p j ( u n d t r i pd e l a y ) ：设数据包第一比特离开源端时刻为t ， 目的端接收到数据包后立即将包发回给源端，设源端接收到数据包最后一比特 的时刻为1 + l l ，则h 就为源、目的端问的双向延迟。 ( 4 ) i p 包抖动( i p p a c k e td e l a y v a r i a t i o n ) ：连续两个i p 包的延迟差。 ( 5 ) 丢包模式【8 l ( 1 0 s sp a _ t t e m ) ：丢包模式包括丢包距离( 1 0 s sd i s t 锄c e ) 与 丢包周期( 1 0 s sp e r i o d ) 。丢包距离用于描述丢包的突发性，丢包周期用于描述 连续丢包事件的持续时间。 ( 6 ) 包重排序( p a c k e tr e o r d c r i n g ) ：用于描述一系列m 包的乱序程度。 整批传输能力【9 】( b u u c 仃a n s p o r tc 印a c 时) ：指一条t c p 连接在待测路径 上能够达到的平均数据传输速率。 ( 8 ) 链路可用带宽( 1 i 1 1 kb 锄d 而d t l lc a p a c 时) ：链路上未被流量占用的剩余 带宽。 删t 和m t f 在i p 网络性能方面的定义大体一致，只在一些具体细节上 有所差异。这两种标准都强调口网络性能参数是从用户感知的角度提出的，与 具体网络及网络的内部结构无关。 第三节网络测量的分类 网络测量依据测量的对象，分为如下几种： 1 ) 基于流的测量 与传统电信网络的呼叫细节记录( c a l ld e t a i lr c r d ，c d r ) 类似，基于 流的测量以流为基准对网络流量进行测量。对于网络测量的流，可以理解为在 同一组特定的源地址和目的地址、源端口和目的端口之间传递的有着固定的协 议类型，具有开始和结束时间的数据包的集合。测量信息通常包括源和目标的 i p 地址、端口号、协议类型、服务类型、流的开始和结束时间戳、分组计数、 字节计数等。 另外，由于流是一个粒度很小的测量对象，不可能长时间的对经过边界路 一6 第二章i n t e m e t 网络测量概述 由器的所有流进行测量，因此基于流的测量往往不是连续进行的，而是采取采 样的方法。使用采样的方法测量还可以减少需要测量的数据的数量和测量的时 间。采样的方法本文会在后面介绍。 2 1 基于网络接口、连接和节点的测量 可以对每个网络元素进行被动式的测量。例如s n m p ( s i i l l p l en 娟v o r k m 锄g e m e mp r o t o c 0 1 ) 采用被动监听的方法，可以在边界路由器上收集原始数 据的有关信息，然后存储到m i b ( m a l l a g 锄e n tm f o m m t i o nb 嬲e ) 里面。这些 信息包括发送接收的分组数、字节数、丢弃的分组数以及出错的分组个数等等。 3 ) 基于节点对的测量 在传统的电信网络中，每个建立的连接都包含了一个节点对。可以在每个 交换机上面为每个节点对维护一系列的数据寄存器，用以记录节点对之间的网 络情况。相对而言，i p 网络的测量就不是那么简单了。因为i p 是一个数据报 协议，这样的数据不可能直接得到，只有通过对被动式测量得到的数据进行分 析而获得关于流的信息。这样做的一个问题就是需要处理的数据量会很大。另 外一个问题是，由于路由配置可能会发生变化，因此对节点对之间流量的跟踪 就会出现丢失的情况。 4 1 基于路径的测量 路径可以定义为i p 分组从源端节点传送到目标端节点的过程中所要经过 的一系列链接的集合。和流一样，路径也是和一个节点对联系在一起的。与流 相比，路径的粒度更大一些，因为路径通常传送的是汇聚流量。而且，如果路 由发生变化，一个路径传送的流量要么不受影响，要么汇合到另外一个路径中 去。正因为如此，基于路径的测量可以对网络需求提供一个更加精确、可行的 视图。例如，对某个节点对之间的流量可以用结束( 或者开始) 于某个节点的 路径的流量来表示。 第四节网络测量的方法 2 4 1 主动测量与被动测量 最常见的m 网络性能测量方法有两类【1 0 】；主动测量和被动测量。这两种方 法的作用和特点不同，可以相互作为补充。 7 一 第二章i n t e m e t 网络测量概述 1 ) 主动测量 主动测量是在选定的测量点上利用测量工具有目的地主动产生测量流量， 注入网络，并根据测量数据流的传送情况来分析网络的性能。主动测量的优点 是对测量过程的可控性比较高，灵活、机动，易于进行端到端的性能测量；缺 点是注入的测量流量会改变网络本身的运行情况，使得测量的结果与实际情况 存在一定的偏差，而且测量流量还会增加网络负担。主动测量在性能参数的测 量中应用十分广泛，目前大多数测量系统都涉及到主动测量。 要对一个网络进行主动测量，需要一个测量系统，这种主动测量系统一般 包括以下四个部分：测量节点( 探针) 、中心服务器、中心数据库和分析服务器。 有中心服务器对测量节点进行控制，由测量节点执行测量任务，测量数据由中 心数据库保存，数据分析则由分析服务器完成。 2 ) 被动测量 被动测量是指在链路或设备( 如路由器，交换机等) 上利用测量工具对网 络进行监测，而不需要产生多余流量的测量方法。被动测量的优点在于理论上 它不产生多余流量，不会增加网络负担；其缺点在于被动测量基本上是基于对 单个设备的监测，可能实时采集的数据量过大，另外还存在用户数据泄漏等安 全性和隐私问题。 被动测量可以通过三种方式获得： ( 1 ) 服务器端测量。通常是在服务器端安装测试代理，实时监测服务器的 性能，资源使用等状况。 ( 2 ) 用户端测量。将监测功能封装到客户应用中，从特定用户的角度实时 监测相关的业务性能。 ( 3 ) 利用网络探针。网络探针可用于监测网络传输状态，分析捕获的数据 包，以实现对网络及相关业务的测量。 3 ) 主动测量与被动测量的结合 主动测量与被动测量各有其优、缺点，而且对于不同的性能参数来说，主 动测量和被动测量也都有其各自的用途。因此，将主动测量与被动测量相结合 将会给网络性能测量带来新的发展。 8 第二章l m e m e t 网络测量概述 2 4 2 网络层测量与应用层测量 应用层测量可以使测量者对整个应用的性能有一个清楚的认识，而这是很 难从低层测量数据综合得到的。同时应用层测量也能提供客户机和服务器之间， 网络链路之间的性能参考。比如想比较某一特定业务连续几天或几星期的性能， 假定由服务器负载引起的变化比由网络拥塞引起的变化小，则测量该业务的总 体性能就足够了。这种方法常用于对不同提供商提供的业务进行性能比较。 采用应用层测量的另一个原因是一些i s p 在其网络内使用通信过滤( 1 - m m c f i l 矧l l g ) 技术，比如阻止i c m p 响应包或限制其传送速率。虽然用p i n g 作网 络测量的工具有时还是有用的，但通信过滤技术的使用日益广泛，在一定程度 上减少了此类测量的使用。 因此，对于i s p 提供的骨干网一般采用网络层测量，以评估其提供的网络 链路或路由器，服务器等网络节点的性能；而对于基于网络平台的各种业务， 其应用层性能的测量变得越来越重要。 2 5 1 抽样概念 第五节网络测量中的抽样 抽样3 1 ，也叫采样，抽样的特性是由抽样过程所服从的分布函数所决定的。 研究抽样，主要就是研究其分布函数。对于主动测量，其抽样是指发送测量数 据包的过程；对于被动测量来说，抽样则是指从业务流量中采集测量数据的过 程。 2 5 2 抽样方法 依据抽样时间间隔所服从的分布，抽样方法可分为很多种，目前比较常用 的方法是周期抽样、随机附加抽样和泊松抽样。 周期抽样是一种最简单的抽样方式，它遵循采样定理，即“采样频率必须 大于所采样信号最高频率的两倍”。因为周期抽样相对简单，所以被广泛应用。 但它存在以下一些缺点：测量容易受到同步效应的影响而具有周期性、很强的 9 第二章i n t e m e t 网络测量概述 可预测性，会使被测网络陷入一种同步状态。 随机附加抽样的抽样间隔的产生是相互独立的，并服从某种分布函数，这 种抽样方法的优劣取决于分布函数：当时间间隔以概率l 取某个常数，那么该 抽样就退化为周期抽样。随机附加抽样的主要优点在于其抽样间隔是随机产生 的，因此可以避免对网络产生同步效应，它的主要缺点是由于抽样不是以固定 间隔进行，从而导致频域分析复杂化。 在i 江c 2 3 3 0 中，推荐泊松抽样，它的时间间隔符合泊松分布，其优点是： 能够实现对测量结果的无偏估计，测量结果不可预测，不会产生同步现象。但 是，由于指数函数是无界的，泊松抽样有可能产生很长的抽样间隔，因此，实 际应用中可以限定一个最大间隔值，以加速抽样过程的收敛。 第六节网络仿真 网络仿真是一种利用数学建模和统计分析的方法模拟网络行为，从而获取 特定的网络特性参数的技术。无论是建设新的网络，还是改造或升级现有网络， 都需要对网络进行可靠的规划和设计。传统上，主要依靠经验来完成，这种方 式不容易抓住问题的要害，尤其是对复杂的大型网络。网络仿真作为一种新的 网络规划和设计技术，以其独有的方法为网络规划设计提供客观、可靠的定量 依据，缩短网络建设周期，提高网络建设中决策的科学性，降低网络建设的投 资风险。网络仿真技术已经逐渐成为网络规划、设计和开发中的主流技术。 网络仿真主要特点为： ( 1 ) 网络仿真能够为网络的规划设计提供可靠的定量依据。 ( 2 ) 网络仿真技术能够迅速地建立起网络模型，并能够方便地修改模型并 进行仿真，获取特定网络的性能参数，这使得网络仿真非常适用于预测网络性 能。 ( 3 ) 网络仿真能够验证实际方案或比较多个不同的设计方案。在网络规划 设计过程中经常出现多个不同的设计方案，它们往往是各有优缺点，仅凭主观 判断，很难做出正确的决定，因此如何进行科学的比较和取舍往往是网络设计 者们感到头疼的事。网络仿真能够通过为不同的设计方案建立模型、进行模拟， 获取定量的网络性能预测数据，为方案的验证和比较提供可靠的依据。这里所 指的设计方案可以是网络拓扑结构、路由设计、业务配置等等。 1 0 一 第二章i n t e m e t 网络测晕概述 目i 前常用的网络仿真软件主要有：o p n e t 和n s 2 ，下面简要介绍一下这两 种网络仿真软件。 2 6 1o p n e t 简介 0 孙厄1 噜1 1 j 公司起源于麻省理工学院，成立于1 9 8 6 年。1 9 8 7 年o p n e t 公 司发布了它的第一个商业化的网络性能仿真软件，提供了具有重要意义的网络 性能优化工具，使得具有预测性的网络性能管理和仿真成为可能。至今o p n e t 已经发行到了1 0 0 以上版本。 o p n e t m o d e l e r 提供了三层建模机制，分别在进程层，节点层和网络层进 行由下到上的建模。同时在仿真的过程中它采用了离散事件驱动的模拟机理。 ( 1 ) 进程模型( p r o c e 站m o d e l ) 的基础是用有限状态机f s m ( f i 咄es t a t e m a c l l i n e ) 来描述各种协议。各个状态再分别进行编程实现。 ( 2 ) 节点模型( n o d cm o d e l ) 由进程模型构成，可以组成完整的协议栈，真 实的反映所建模设备的特性。各模块间通过数据包和状态信息的传递来进行各 种操作，进而实现设备的功能。 ( 3 ) 网络模型( n c tm o d e l ) 由节点模型组成，可以通过不同的拓扑设计来 构造出各种不同的网络结构。 0 p n e t 的建模过程如下： ( 1 ) 了解建模对象。深入理解实际的仿真对象，在建模时还需要对实际的 模型进行一定的简化，一些对仿真结果没有影响的内容可以进行简化或删除。 比如对于m 地址可以简化为用一个8 位的整型数字来代替。 ( 2 ) 确定建模目的确定要得到的结果和要解决的问题。设定好参数和观 察变量，比如若要得到网络的时延特性，需要在进程模型中设定观察变量。 ( 3 ) 模型设计基于f s m 对各个状态进行初始的定义：进行p a c k e t 建模； 设定s 诅t i s t i c s ；定义数据结构；编程实现模型功能。 ( 4 ) 仿真调试。对模型进行测试、修改和完善。 ( 5 ) 验证结果。查看仿真结果，验证模型的正确性。 以上各步骤循环进行，直到得到预定的结果。 第二章i n t 1 e t 网络测骨概述 2 6 2 n s2 简介 n s 2 旧是一个用c + + 语言编写的、面向对象的、离散事件驱动的网络模拟 工具，是美国d a r p a 支持的项目v i n t 中的核心部分。n s 2 主要面向网络协 议研究者，为其提供网络模拟工具，来实现新的互联网协议的设计和实施。 n s 2 使用o t c l ( o b j e c t lc o 咖n 觚dl 锄g 唿g e ) 作为命令和配置接口。它 提供一个分离编程模型，即采用系统编程语言( c + + ) 和脚本编程语言( o t c l ) 共同开发。n s 2 由事件调度器、网络组件对象和网络组装模块库组成。其中事 件调度器和网络组件，即协议的详细实现由c h 完成，从而可以高效地管理字 节和包头，并实现在大量数据集合上的算法；仿真配置由t c l 实现，以便迅速 改变配置参数和设置场景，使性能和灵活性得到均衡【l “。n s 2 支持c + + 中的编 译型类层次和o t c l 中的解释型类层次，以t c l o b j e c t 类为基础，两者之问有一 一对应地关系。 n s 2 有很多特点：它可以支持大规模多协议网络仿真，对同一个仿真模型 提供不同粒度的仿真实现；它提供了个模拟接口，可以把真实网络节点流量 注入到仿真模型中的节点，通过与真实网络同步，模拟网络在真实运营中的行 为；它提供了可视化工具，可动态地显示网络仿真过程，图形化数据结果等等。 o p n e t 虽然功能强大，但价格昂贵，本文不采用。n s 2 是免费的，开源的， 获取容易，特别适合于科研使用。因此本文最终选用n s 2 作为仿真平台。 - 1 2 一 第三章端到端路径可用带宽测量方法概述 第三章端到端路径可用带宽测量方法概述 目前，端到端路径可用带宽测量的研究还处于初级阶段，其主要目标是在 不干扰或者不影响路径原有业务的情况下准确快速地测量可用带宽。由于 h l t e m c t 上流量具有动态性，路径上可用带宽会随时间不断变化，如果测量时间 过长，路径的可用带宽可能会变化较大，因此，一个好的端到端路径可用带宽 测量方法应该耗时较短，且对路径上可用带宽的变化较为敏感。 近年来，研究人员针对i n t 锄e t 端到端路径可用带宽的测量已经提出了多 种测量方法，本文根据它们的基本思想将这些方法划分为如下两类： ( 1 ) 自拥塞方法。这种方法通过使路径上的链路发生拥塞，试图寻找链路 发生拥塞时具有的特征，并将这些特征与路径的可用带宽建立联系。 ( 2 ) 基于数学模型的方法。这种方法通过使用数学模型描述i n t e m e t 上的流 量，进而通过数学分析找出路径可用带宽与这些模型之间的关系。 在介绍这两种类型的端到端路径可用带宽测量方法之前，本文先给出一些 与带宽测量有关的概念术语。 第一节相关概念 因为对于带宽的各种指标国际上还没有统一的定义，各种文献中提到的也 不尽相同，因此有必要先对各种指标给予说明【1 3 】。 链路带宽( 1 i i l i 【b 锄d 谢d t l l ) ：即链路容量，指的是链路在物理设计上能够 达到的最大数据传输速率，一般是一个固定值。 瓶颈带宽( b o t t l e c k b 柚椭d t h ) ：两个节点之间路径上的最小的链路带宽， 它表示一条路径的最大传输速率。对于大多数网络来说，两个主机之间的瓶颈 带宽不会改变，也不受网络流量的影响。如果上。= ( f o ，f 2 ，厶) 表示一条从源 端s 到目的端d 的路径，n 表示路径的跳数，表示第i 条链路( o f 一) ，6 l 表 示t 的链路带宽，那么路径厶。的瓶颈带宽岛，可用如下公式表示： z k = m i n ( ，a ，6 2 ，屯) ( 3 1 ) 链路的可用带宽( 1 i i l i 【a v a i l a b l eb 柚d 诵d t l l ) ：链路上未被流量占用的剩余带 1 3 第三章端到端路径可用带宽测晕方法概述 宽。按上面的定义，如果( o “。1 ) 表示t 的利用率，链路的可利用带宽 q = 包( 1 一虬) 。 路径的可用带宽( p a ma v a i l a b l eb 锄d 、v i d t l l ) ：一条路径中最小的链路可利 用带宽。路径的上可利用带宽如可用如下公式表示： 4 岛d = m i n ( 口0 ，q ，口2 ，q ) ( 3 2 ) 瓶颈链路( n 跏wi i n k ) ；瓶颈带宽所在的链路。 紧迫链路( t i g h tl i l l l 【) ：路径的可利用带宽所在的链路。 背景流量( c r o 蟠t r a m c ) ：一条链路中除去用于探测的流量之外的其它所有 流量。 需要指出的是瓶颈带宽表示的是一个连接传输数据的速度的上限，可利用 带宽表示的是一个连接实际可以再利用的传输速度，可利用带宽不可能超过瓶 颈带宽，而且受瓶颈带宽和路径流量的限制。同时，由于可利用带宽要受网络 中已有流量的影响，瓶颈链路和紧迫链路并不一定在同一位置，因而瓶颈带宽 和路径的可利用带宽并没有必然的联系。它们之间的关系可以用图3 1 表示， 图中相连的方框代表三条相连的链路，厶，厶，它们组成了一条路径。图中阴影 部分表示网络中的已有流量，鱼表示第i 条链路的链路带宽，q 表示第i 条链路 的可利用带宽。根据上面的定义可以得出，6 1 是路径的瓶颈带宽，因此是路 径的瓶颈链路；码是路径的可用带宽，因此是路径的紧迫链路。 jljl r 广 鸪 。 t 。 缸； 月 姒_ ；主，。 b 2 ! i 鹕 i ? j 1r u i ! i f。 1 i。； 图3 1 可用带宽与瓶颈带宽 可用带宽受网络流量影响随时间变化，因而对它的测量有实时性要求。而 对于链路带宽和瓶颈带宽来说它们一般不会发生变化，测量也没有实时性要求。 具体来说，要测量哪个指标要根据不同的情况来定，对于那些对延迟有要求并 第三章端到端路径可用带宽测晕方法概述 且长时间占有网络的应用，可能更关心瓶颈带宽，而那些对平均吞吐量有要求 的应用可能更关心可用带宽。通过测量瓶颈带宽可以为可用带宽测量提供基础。 同时，本文还要介绍一些与排队论印j 相关的概念。 排队服务系统：排队服务系统由队列与服务单元组成。服务单元服务到达 系统的顾客，队列用于缓存服务单元来不及处理的顾客，顾客接受完服务单元 的服务之后自动离开系统。 m 删咖排队服务系统：这一符号代表一个排队服务系统，第一个m 代表 顾客到达过程为泊松过程，第二个m 代表顾客服务时间服从独立同分布的指数 分布，n 代表排队服务系统有n 个服务单元。 服务强度：描述排队服务系统的忙碌程度，数值上等于单位时间内到达系 统的顾客数与单位时间内系统服务完的顾客数的比值。在链路可用带宽这一应 用背景中，它代表链路的利用率。 第二节自拥塞可用带宽测量方法 如前所述，自拥塞( 辩l f c o n g c s t i o n ) 方法需要通过发送探测流引起路径链 路发生拥塞。如果发送端的探测流发送速率超过紧迫链路的处理能力，紧迫链 路就会发生拥塞，从而形成排队。当发生排队时，探测流就会受i 廊m e t 背景 流量的影响而产生变化，自拥塞方法就是通过捕捉这些变化，并在这些变化与 路径可用带宽之间建立联系来达到计算路径的可用带宽的目的。 按测量所需信息的不同，本文将自拥塞方法分为两类：包间隔模型与包速 率模型。 3 2 1 包间隔模型 包间隔模型【1 4 1 ( 1 1 l ep r o b eg a pm o d e i ，p g m ) 通过分析两个相邻数据包到 达接收端的时间间隔来计算可利用带宽。它假设瓶颈链路和紧迫链路在同一位 置，当发生拥塞排队时，探测数据包发送时的初始时间间隔受网络中背景流量 插包的影响，这个间隔会变大，从而数据包到达接收端时的时间间隔可以用一 个关于网络中背景流的函数表示，可以据此测量可利用带宽。 下面介绍一种典型的采用包间隔模型的端到端路径可用带宽测量方法： 1 5 第三章端到端路径可用带宽测量方法概述 图3 29 0 ，q 及问关