（计算机系统结构专业论文）internet可用带宽测量研究及测量系统实现.pdf

摘要 摘要 带宽是i n t e r n e t 中的种重要资源，也是多种网络技术中的关键因素。可用带 宽的测量对于深入了解网络行为，优化端到端的传输性能具有十分重要的意义。 互联网规模的不断扩大和复杂性的不断增加，对可用带宽的测量提出了越来越高 的要求。 本文在对现有的基于自感应拥塞理论的可用带宽测量算法进行深入研究的基 础上，提出了一种新的基于该理论的测量算法1 t p 。i t p 利用主动测量的方式对端 到端网络路径的可用带宽进行测量。和已有的使用数据包对和普通数据包序列的 可用带宽测量技术不同，i t p 算法使用的探测序列中，数据包之间的间隔呈指数变 化。通过在探测序列中快速增加探测速率，i t p 可获得用于可用带宽估计的丰富的 数据信息。并且，n t 算法通过测量数据包到达接收方时间的差值得到网络的可 用带宽，因此，不需要发送方和接收方之间时钟的同步。通过测试，发现r r p 算 法可以使用比现有的测量技术更少的探测流量获得可用带宽的较好估计。 同时，为了对i n t e m e t 上较大范围内的网络带宽使用情况进行准确、全面的了 解，本文参考p a x s o n 等人构建的n p d ，设计了可伸缩性网络带宽测量系统s a b m s 。 s a b m s 设计的一个核心目标是系统的可伸缩性，使得同一个测量平台能够适应不 同数量的探测节点。当测量节点的数量增加时，可用的测量通路呈n 的指数增长， 从而便了解网络的整体可用带宽情况成为可能。系统由三种网络节点构成，分别 是p p ，p p c 和m c 。p p 是实际进行带宽测量的节点，使用p 算法进行可用带宽 的测量：p p c 是s a b m s 的管理者，负责管理p p ，并向m c 返回有关p p 的信息； m c 是用于访问系统的客户端。这个系统与s u r v e y o r 、f e l i x 等网络测量系统最核 心的区别在于两点：( 1 ) 有多个分散在i n t e r n e t 上的控制主机而不是只有一个控制 节点；( 2 ) 对不同的用户可以赋予不同的使用权限。 关键字：网络测量，可用带宽，自感应拥塞，可扩展性，s a b m s a b s t r a c t a b s t r a c t b a n d w i d t hi sa l li m p o r t a n tr e s o u r c ei ni n t e r n e t a n di ti sa l s oak e yf a c t o ri nm a n y n e t w o r kt e c h n o l o g i e s a v a i l a b l eb a n d w i d t he s t i m a t i o ni so fi n t e r e s tt ou s e r sw h ow i s ht o u n d e r s t a n dt h eb e h a v i o ro ft h en e t w o r kd e e p l ya n do p f i m i z et h ee n d - t o - e n dt r a n s p o r t p e r f o r m a n c e t h ee v e r - i n c r e a s i n gs i z ea n dc o m p l e x i t yo fi n t e r a c ti m p o s e sah i g h e r d e m a n do na v a i l a b l eb a n d w i d t he s t i m a t i o n t h i sp a p e rp r e s e n t si t p , an e wa c t i v ep r o b i n ga l g o r i t h mf o rt h ee s t i m a t i o no f a v a i l a b l eb a n d w i d t ho nac o m m u n i c a t i o nn e t w o r kp a t h ，a f t e rs u m m a r i z i n gc u r r e n t a v a i l a b l eb a n d w i d t he s t i m a t i o nt e c h n o l o g i e s i t pf e a t u r e sa ne x p o n e n t i a lf l i g h tp a t t e m o fp r o b e s ，w h i c hi sd i f f e r e n tf r o mc u r r e n tp r o b i n gs c h e m e sb a s e do np a c k e tp a i r so r p a c k e tt r a i n s ，b yr a p i d l yi n c r e a s i n gt h ep r o b i n gr a t ew i t l t i ne a c hp r o b i n gt r a i n i t p o b t a i n sar i c hs e to fi n f o r m a t i o nt od y n a m i c a l l ye s t i m a t et h ea v a i l a b l eb a n d w i d t h s i n c e i tu s e so n l yp a c k e ti n t e r - a r r i v a lt i m e sf o re s t i m a t i o n r r pd o e sn o tr e q u i r es y n c h r o n o u s c l o c k sb e t w e e nt h es e n d e ra n dr e c e i v e r w et e s ti t pa n df i n dt h a ti tp r o v i d e sg o o d e s t i m a t eo ft h ea v a i l a b l eb a n d w i d t hw h i l eu s i n go n l yaf r a c t i o no fp r o b eb y t a st h a t c u r r e n ts t a t e o f - t h e - a r tt e c h n o l o g i e su s e f u r t h e r m o r e ，t h i sp a p e rd e s c r i b e ss a b m s ，a l la v a i l a b l eb a n d w i t hm e a s u r e m e n t a r c h i t e c t u r eb a s e do nt h ee x p e r i e n c eg o ti np a x s o n sn p dp r o j e c t ，w h i c hi su s e dt o f i g u r eo u tt h ea v a i l a b l eb a n d w i t hr e l a t e di n f o r m a t i o nw e l la n dm d yo ni n t e m e t ak e y d e s i g ng o a ls a b m si ss c a l a b i l i t yt op o t e n t i a l l yt h o u s a n d so fp r o b e sw i t h i nas i n g l e i n f r a s t r u c t u r e a st h en u m b e ro fp r o b e si n c r e a s e s ，t h en u m b e ro fa v a i l a b l em e a s u r a b l e p a t h si n c r e a s e sv i an - s q u a r e de f f e c t ，p o t e n t i a l l ya l l o w i n gf o rag l o b a lv i e wo fi n t e m e t s a v a i l a b l eb a n d w i d t h t h es y s t e mi sc o m p o s e do f t h r e ek i n d so f n e t w o r kn o d e s ，p p , p p c ， a n dm c p pi su s e dt oe x e c u t et h ea c t u a lm e a s u r e m e n tu s i n gi t p ；p p ca c t sa st h e a d m i n i s t r a t i v ec e n t e ro ft h es y s t e m ；m ci st h ec l i e n t ，s a b m sd i f i e r sw i t hs u r v e y o r ， f e l i xm a i n l yi nt w op o i n t s ：( 1 ) m u l t i p l ec o n t r o lh o s t sr a t h e rt h a no n e ；( 2 ) d i f f e r e n tu s e r s a r eg i v e nd i f f e r e n ta c c e s sr i g h t st ot h ep r o b ep o i n t s k e yw o r d s ：n e t w o r km e a s u r e m e n t ，a v a i l a b l eb a n d w i d t h ，s e l f - i n d u c e dc o n g e s t i o n ， s c a l a b i l i t y , s a b m s 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得电子科技大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 己在论文中作了明确的说明并表示谢意。 签名：差盔墅日期：俨g 年fj 可j - n 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文的规定，有 权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借 阅。本人授权电子科技大学可以将学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 血 日期：2 胪g 年- 月参一日 第一章引言 1 1 课题的背景和意义 第一章引言 近年来，随着以t c p i p 为主要协议的n t e m e t 技术的飞速发展，网络的规模 不断扩大，网络的流量也爆炸式的增长。i n t e r n e t 已经渗透到社会生活的各个领域， 成为现代社会发展最重要的基础设施之一。但是，由于i n t e m e t 发展的特殊性，人 们对于i n t e r n e t 流量模型、网络行为、性能指标都缺乏精确的理解和描述，对网络 测量技术的研究明显滞后于网络及其应用的飞速发展。特别是，实时业务和多媒 体等新业务的不断增加，对网络质量提出了更高的要求。人们提出了一系列的o o s 保证框架，不论是应用层的负载均衡、网络层的流量工程( t r a f f i ce n g i n e e r i n g ) 还 是q o sr o u t i n g ，都是以对网络运行状态进行测量并将信息有效发布为基础的。因 此，研究i n t e m e t 网络性能的测量方法是了解网络行为、对大规模网络结构进行动 态描述，分析网络的性能、加强网络管理、提高网络利用率的前提和基础，具有 十分重要的意义。 带宽是i n t e r n e t 中的一种重要资源。网络带宽的概念主要是针对数字交换而 言，特别是包交换网络。它主要是指在单位时间内一条链路或者_ 条网络路径能 够传递的数据总量。对于像文件传输或者多媒体流这样的数据密集型应用而言， 网络可用带宽直接影响到服务的性能。虽说那些对于延迟更加敏感的交互型应用 更能够从端到端的低延迟中获益，可是端到端的低延迟也是与高的链路带宽紧密 相关的。 带宽同时也是多种网络技术中的关键因素。例如，p 2 p 应用基于各点之间的 可用带宽构建用户级的动态网络；o v e r l a y 网络基于各链路的带宽配置其路由表； 网络供应商对顾客通常也是基于租用带宽进行收费。并且，网络带宽是智能路由 系统、端到端的准入控制以及流媒体传输中的重要概念。因此，用一种快速有效 的手段精确的获取网络带宽的信息一直是网络测量中的一个热门的研究课题，受 到了学术晃和企业界的共同关注。 1 2 作者的主要工作 论文作者在对网络带宽测量这一领域的基本理论和最新研究成果进行系统、 全面地学习和总结地基础上，对网络可用带宽测量算法和构建i n t e r n e t 范围内的可 电子科技大学硕士论文 用带宽测量系统两个方面进行了深入细致的研究，取得了一些创新和成果。本文 的主要贡献包括： 对已有的带宽测量技术v p s 、p p t d 、s l o p s 和t o p p 的原理和优缺点进行了 详尽的分析，在此基础上，提出了一种基于自感应拥塞理论的高性能的可用带宽 测量算法p ，并对n t 算法的实现细节进行了深入探讨。 基于n t 算法，作者设计并实现了一个i n t e m e t 范围内可用带宽测量系统，这 个测量系统具有高性能、易扩展、和高安全可靠性等几个特征。 1 3 论文的结构 论文共分六章。 第一章为引言，简要介绍课题的研究背景和意义，以及论文的主要内容和贡 献。 第二章为网络测量以及带宽测量相关理论，是对网络测量基本理论以及带宽 测量的技术的概要介绍。 第三章为可用带宽测量算法分析和n t 算法的实现，是对现有的可用带宽测 量算法的详细分析，并提出建立于自感应拥塞理论上的改进的分组串测量算法 i t p ，并且详细讨论了其实现细节。 第四章为s a b m s 系统设计，讨论测量系统的设计中的关键技术。 第五章为s a b m s 系统实现，详细分析测量系统各模块的实现细节。 第六章为系统测试，并对未来工作的方向进行了展望。 2 第二章网络测量以及带宽测量相关理论 第二章网络测量以及带宽测量相关理论 2 1 网络测量相关理论 2 1 1 网络测量的研究领域与主要应用 网络测量的应用土要包括咀下几个方面： 1 1 测量。精确地捕捉定量的因特网及其活动的测量数据。通常，网络测量的主 要参数包括r t t 、路径数据、带宽、延迟、瓶颈、突发业务量的频率、拥塞程度、 动态瓶颈、站点的可迭性、吞吐量、带宽利用率、丢包率、服务器和网络设备的 响应时间、最大的网络流量、网络服务质量q o s ( 包括图像、数据、语音等服务的 质量1 等。需要指出的是，在网络层次的测量中，需要测量的一类属性是蚓络固有的， 如它的拓扑、连接容量、延迟；另一类属性反映了网络的当前状态，如排队延迟、 连接可用性、路由的动态性。 2 1 模型化。这是性能评价的核心问题一建立正式的网络描述与模拟。这种 模型的有效应用可实现对未来网络行为的预测。 3 ) 控制。利用从测量和模型化得到的知识，实现因特网资源的合理配置与使用。 测量网络的拓扑结构，对大规模网络结构进行动态揣述，并根据网络的变化分 析阱络的性能。对网络效率和行为作出评价至少具有以下几方面的麻用： 1 ) 网络监测。包括对网络运行情况的监视、网络资源的监视和网络性能( 如业 务吞吐量、时延、丢包率、r t t 、带宽利用率、网络伸缩性( s c a l a b i l i t y ) 的监视等， 并可提交故障及异常事件报告作出相应的评价。 2 1 网络质量控制和辅助性网络管理。如发现并改正病态路由、根据长期观察 的路由数据对网络选路制定策略、网绍被破坏后的嗍络资源自组织等。 3 1 防范大规模网络攻击，同时为信息攻击对抗提供必要的网络测绘和流量分 析。通过在大范围内进行网络行为监控，有可能发现网络异常，为防范大规模网络攻 击提供预警手段，使国家对网络管理更具宏观控制力。 4 1 网络测量还可以应用于对不同i n t e r n e t 服务提供商( i n t e r n e ts e r v i c ep r o v i d e r 简称i s p ) 的服务质量( q u a l i t y o fs e r v i c e ，简称q o s ) 的比较、移动i p 的位置发现、代 理服务器的自动选择等许多 面。 5 】为仿真模拟i n t e r n e t 环境、协议设计与评价以及动态网络存活性分析提供 5 】为仿真模拟i n t e r n e t 环境、协议设计与评价以及动态网络存活性分析提供 研究基础。 3 第二章网络测量以及带宽测量相关理论 第二章网络测量以及带宽测量相关理论 2 1 网络测量相关理论 2 1 1 网络测量的研究领域与主要应用 网络测量的应用主要包括以下几个方面： 1 ) 测量。精确地捕捉定量的因特网及其活动的测量数据。通常，网络测量的主 要参数包括r i t 、路径数据、带宽、延迟、瓶颈、突发业务量的频率、拥塞程度、 动态瓶颈、站点的可迭性、吞吐量、带宽利用率、丢包率、服务器和网络设备的 响应时间、摄大的网络流量、网络服务质量q o s ( 包括图像、数据、语音等服务的 质量) 等。需要指出的是，在网络层次的测量中，需要测量的一类属性是网络固有的， 如它的拓扑、连接容量、延迟；另一类属性反映了网络的当前状态，如排队延迟、 连接可用性、路由的动态性。 2 ) 模型化。这是性能评价的核心问题一建立正式的网络描述与模拟。这种 模型的有效应用可实现对未来网络行为的预测。 3 ) 控制。利用从测量和模型化得到的知识，实现因特网资源的合理配置与使用。 测量网络的拓扑结构，对大规模网络结构进行动态描述，并根据网络的变化分 析网络的性能，对网络效率和行为作出评价至少具有以下几方面的应用： 1 ) 网络监测。包括对网络运行情况的监视、网络资源的监视和网络性能( 如业 务吞吐量、时延、丢包率、r t t 、带宽利用率、网络伸缩性( s c a l a b i l i t y ) 的监视等， 并可提交故障及异常事件报告，作出相应的评价。 2 ) 网络质量控制和辅助性网络管理。如发现并改正病态路由、根据长期观察 的路由数据对网络选路制定策略、网络被破坏后的网络资源自组织等。 3 ) 防范大规模网络攻击，同时为信息攻击对抗提供必要的网络测绘和流量分 析。通过在大范围内进行网络行为监控，有可能发现网络异常，为防范大规模网络攻 击提供预警手段，使国家对网络管理更具宏观控制力。 4 ) 网络测量还可以应用于对不同i n t e m e t 服务提供商( i n t e m e ts e r v i c ep r o v i d e a 简称i s p ) 的服务质量( q u a l i t yo fs e r v i c e ，简称q o s ) 的比较、移动i p 的位置发现、代 理服务器的自动选择等许多方面。 5 ) 为仿真模拟i n t e r n e t 环境、协议设计与评价以及动态网络存活性分析提供 研究基础。 3 电子科技大学硕士论文 6 ) 为i n t e m e t 流量工程( t r a f f i ce n 百e e 血曲和网络行为学( n e 呐o r kb e h a v i o r ) l 箕j 研究提供基础辅助依据及验证平台。 2 1 2 网络测量的分类 网络测量的分类标准有多种，根据测量方式，分为主动测量和被动测量：根 据测量点的多少，分为单点测量和多点测量；根据被测量者知情与否，分为协作 式测量和非协作式测量；根据测量所采用的协议，分为基于b g p 协议的测量、基 于t c p ，口协议的测量以及基于s n m p 协议的测量；根据测量的内容，分为拓扑测 量和性能测量。 2 1 2 1 主动测量与被动测量 在主动测量方式中，通过向网络中发送数据，观察结果和发送数据所需时间来 研究网络的行为。主动测量向网络中发送实际的业务量，利用这些业务量测量反映 网络提供给其他用户的服务的参数，包括r o u n d t r i pt i m e f r t r ) 和丢包率。到目前为 止。人们所做的大多数项目都涉及到主动测量。比如，美国的n i m i ( n a f i o n a li n t e r a c t m e a s u r e m e n ti n f r a s t r u c t u r e ) 项目【1 】，利用p i n g , t r a c e r o u t e ，m t r a c e 等工具进行主动测 量；a m p ( a c t i v a m e a s u r e m e n tp r o g r a m ) 项目，采用p i n g 进行双向测量，测量r t t 、丢 包率和拓扑。到了2 0 0 0 年6 月，运行主动测量监视器的源站点有1 1 6 个( 美国1 1 4 个，新西兰、挪威各1 个) ，被测量的目的站点约有1 33 4 0 个。其目的是为了增强参 与站点和用户对高性能网络运行情况的理解，帮助网络用户和提供商分析问题： s u r v e y o r 是一个建立在全球参与站点上的测量平台，部分由n s f 支持。s u r v e y o r 2 】 测量i n t e r n e t 的路径性能，包括单向延时、损耗、路由测量等，并研究相应的分析方 法与工具。设有5 5 个监测点，在18 8 3 条路经上进行单向时延测量；依托于 u c s d s d s c ( u n i v e r s i t yo fc a l i f o r n i a ，s a nd i e g o ，s u p e r c o m p u t e rc e n t e r ) 的研究部i c a i d a 3 ( c o o p e r a t i v e a s s o c i a t i o nf o ri n t e m e td a t a a n a l y s i s ) ，开展网络测量、分析、 可视化工具的研发，维护全球因特网平台的健壮性和可扩放性，受到n s f ( n a t i o n a l s c i e n c ef o u n d a t i o n ) 、d a r p a ( d e f e n s ea d v a n c e dr e s e a r c hp r o j e c t sa g e n c y ) 、 i s p ( i n t e m e ts e r v i c ep r o v i d e r s ) f d 硬件供应商的资助，研究对象包括i n t e r n e t 拓扑结 构、网络负载、网络性能、网络路由，监测正，异常活动，关注带宽估计，负载刻画， 长期趋势识别，以进行流量工程设计、能力计划、安全迹象检测，等等。加拿大国家 研究机构使用p e r ls c r i p t 跟踪对t r i u m f 感兴趣的节点，每1 0 分钟检测一次丢 包率，每天收集4 次t r a c e r t 数据并生成网络可视化图；欧洲的p p n c g ( p a r t i c l e p h y s i c sn e t w o r kc o o r d i n a t i n gg r o u p ) 项目，监视全欧洲某些粒子物理研究所的网 络端到端性能，并加以优化。在主动测量项目中，测量的范围比被动测量大得多，可 4 第二章网络测量以及带宽测量相关理论 大到全球。如此庞大的测量体系，有可能造成较大的网络负荷，且难以统一配置和管 理。 在被动测量方式中，记录网络活动的探针被接入到网络中，在大多数情况下探 接到网络节点之间的连接上，汇总和记录那条连接上业务流量的信息。目前开展的 被动测量项目有：受美国国家科学基金会n s f 资助的美国应用网络研究国家实验 室( n l a n r ) 的测量项目p m a ( p a s s i v em e a s u r e m e ma n da n a l y s i s ) ，旨在为高级网络 ( 如v b n s ，a b l i e n e ) 提供协作性的服务支持。它采用o c3 m o n 数据搜集系统，包括专 门的群机系统、装有f o r ea t mc a r d s 和o p t i c a ls p l i t t e r s ( 分光器) ，采集a t m 的数 据流，使用c o r a l r e e f 根据一定的规则集进行数据采集，并可使用p e r l 等语言对数据 进行分析：b e r k e r l e yu n i v e r s i t y 和i b m 共同开发的s p a n d ( s h a r e dp a s s i v en e t w o r k p e r f o r m a n c ed i s c o v e r y ) 项目，它通过对捕捉到的u d p 厂r c p 分组进行分析得到连接 带宽、丢包率等性能，等等。被动测量主要在一个特殊点观察网络的行为，不增加和 修改通过网络的数据负载，因此对网络的行为没有影响。这种方法能够达到对观察 点网络行为的详尽理解，但难以获得对网络的整体理解，或者对网络的端到端行为 的理解。被动测量经常用于测量业务量的特征。同时不难看出，被动测量的前提是 协作，否则无法在测量点安装必要的软、硬件设备，其测量范围由此而受限。 2 1 2 2 单点测量与多点测量 在研究初期，许多工作都属于单点测量，但因为测量能力有限，搜集的信息不全 面，分布式多点测量应运而生，尤其是多点主动测量，利用多个探测点得到的数据，能 够综合出大规模的网络数据和单点所得不到的交叉路由信息。单点测试的典型例 子是贝尔实验室的i n t e r n e tm a p p m g 项目，这是一个非合作测量。该项目成功地描 述了科索沃战争期间南斯拉夫和科索沃两个网络的拓扑变化情况，这表明在i p 网 络测量中，单点非合作测量具有相当强的网络探测能力，同时这也是网络测量在军 事领域中应用的典范。 2 1 2 3 拓扑测量与性能测量 在拓扑测量方面，多数项目显示的是逻辑拓扑关系图。随着测量范围的扩大，整 张图规模结构也随之扩大，这时，人们往往希望与实际地域位置相对应，也就是具有 地理信息的拓扑图。s k i t t e r ( c a i d a ) 针对从几个源点到成千上万个目标点收集到 的路径信息进行拓扑结构和性能属性的可视化，并且开展了a s 的地理信息图方面 的研究。 在性能测量方面，相关项目开展得较多觏9 量内容包括吞吐量、延迟、丢包率， 并作网络可靠性、稳定性、可达性等方面的分析。这一方面是为了对一个特定网 5 电子科技大学硕士论文 络进行维护管理，保障服务质量，如p p n g g 和t r f u m f 项目：另一方面是为了预报 网络性能，如n p a c i s n e t w o r k w e a t h e r s e r v i c e 每隔定的时间间隔，周期性地监视、 动态地预报( 各种网络及计算资源) 网络性能。收集某一时刻的数据，通过数值模型预 测下一时段的t c p i p 端到端的吞吐量、延迟，主要用于广域网上的大规模计算的 调度，在元计算软件平台上开发服务质量保证。更深入的分析，如异常检测，尚在研究 之中。 2 1 3 网络测量中存在的一些难点问题 1 ) 拓扑准确度。单点测量因为测量能力有限，搜集的信息不全面；分布式多点 测量，尤其是多点主动测量，利用多个探测点得到的数据，能够综合出大规模的网 络数据和单点得不到的交叉路由信息，可以提高测量的准确度。 2 ) 网络额外负荷。由于i n t e r n e t 是一个不断变化的庞大网络，网络测量要具有 一定的实时性，并且要尽量降低这种大规模测量所带来的额外网络负载，与探测点 的数目和探测的周期有关。 3 ) 地理信息的全面、自动提取。传统的网管软件，在网址地理信息方面通常 采用手工方式加以标注，这对于大规模的广域网来说是难以实现的；另一方面，目前 大多数网络测量项目中所显示的也只有逻辑连接关系图，无法提供更切合实际的 重要信息。在逻辑连接图的基础上，通过获取和分析i p 的登记信息和域名信息等 构建地理分布图。地理信息的全面、自动提取具有一定的难度，地理信息的采集可 通过w h o i s 信息库查询、域名反解析、特征字匹配等技术提高其精确度。 4 ) 易于维护的测量体系结构。随着时间的推移，网络测量将不断扩展、升级， 所以，在设计实旌之初就要充分考虑测量体系的可扩展性、可裁减性及兼容性、可 扩展的测量策略允许用户在测量范围扩大或减小的情况下，只做简单配置就能保 证整个系统正常运行。 5 ) 系统容错性。保证系统具有良好的容错性，系统运行中断后能够从断点处 继续执行，而不必对己测量过的探测目标重复进行测量。 6 ) 隐藏探测踪迹。由于对网络性能测量的实时性要求较高，所以探羽4 频率往 往很大，为了不被误认为是网络入侵，注意隐藏探测踪迹，采用随机算法选择探测顺 序可以很好地解决这个问题。 7 ) 测量结果可视化。在测量结果的可视化阶段，由于数据规模的原因，如何在 全面丽客观地显示库中的数据的前提下保证具有良好的视觉效果，是一个主要问 题。在逻辑连接图中，由于在拓扑图中，点、线数量多且分布位置不确定，在绘制过 6 第二章网络测量以及带宽测量相关理论 程中会出现点线重叠、主次不分的“麻团”现象，因此需要提高数据分析和图的生成 速度。 8 1 网络建模与趋势预测。 2 2 带宽测量指标 “带宽”这个名词常常被模糊地用于一系列与吞吐量相关的概念中。在这一 节中，我们具体定义与带宽相关的测量指标，着重强调它们各自的范围以及彼此 之间的联系。具体的说，我们首先要区分一条链路的带宽以及一系列连续链路的 带宽或者说端到端路径的带宽。其次，我们区分一条链路或者一条传输路径最大 可能的带宽( c a p a c i t y ) ，一条链路或路径最大没有被使用的带宽( a v a i l a b l e b a n d w i d t h ) ，以及一条t c p 连接能达到的吞吐量( b u l k t r a n s f e r - c a p a c i t y ) 。这些 带宽的指标都是十分重要的，因为不同的带宽指标与不同的应用相联系。 在下面的讨论中，我们将区分第二层链路( 数据层链路) ? 和第三层链路( i p 层链路) 。我们将前者称为“分节”( s e g m e n t ) 而将后者称为“跳”( h o p ) 。一个分 节通常对应于一条物理的点对点的连接。而跳则可能由通过交换机、网桥、或 其他第二层设备连接的一系列分节组成。 2 2 1 带宽 一条第二层链路，或者叫一个分节通常以恒定的速度传输数据。比方说，这 个速度在一条1 0 b a s e te t h e r n e t 上是1 0 m b p s ，在一条t 1 分节上是1 5 4 4 m b p s 。一 条分节的传输速度不仅由底层传输介质的物理带宽决定，同时也受到光电发射设 备和接受设备的影响。 在i p 层，由于第二层的封装和填充，每一跳事实上以低于其下层所标称的速 率进行传输。假设一分节的标称速率为c 1 2 ，一个大小为l i 3 字节的i p 包的传输时 间 屹； 式( 2 - 1 ) 其中h ，是第二层需要在i p 数据包中填充的字节总数。由此我们可以计算出 i p 层的传输速率 = 乏2 毒。毒 式晓乞， 7 电子科技大学硕士论文 从这个等式中，我们注意到i p 层的传输速率依赖于口数据包字节数与第二层 填充字节数的比值。我们将某一跳上i p 层可能的晟大的传输速率定义成那一跳的 带宽c ；。依据式( 2 - 2 ) ，我们不难得出，这个带宽的最大值出现在传输大小为 m t u 的i p 数据包的时候。 将上面的定义延伸至一条网络路径。一条端到端的路径( p a t h ) 的带宽c 是指 从源主机到目的主机的一条路径上最大可能的i p 层传输速率。换句话说，一条路 径的带宽为用户期望得到的i p 层的吞吐量设定了一个上限值。这条路径上带宽最 小的那条链路决定了这条路径的带宽c ，也就是说， c ：r a i nc ：，式( 2 3 ) i = 1 王，h 。 其中c 。是第i 跳的带宽，h 为这条路径的总跳数。 2 2 2 可用带宽 带宽测量中另一个十分重要的铡量指标是“可用带宽”，它包括一条链路的可 用带宽和一条端到端路径的可用带宽。一条链路的可用带宽指的是在一段时间内， 一条链路中未被使用的，或者说是空闲的带宽i 所以，和一条链路的带宽不同， 后者依赖于底层的传播介质和传输技术，而一条链路的可用带宽还跟那条链路上 的通信量有关，是一个随时问变化的量。 在一个特定的时间点上，一条链路要么以全部的带宽传输数据包，要么空闲。 也即是说，一条链路的即时利用率为1 或者0 。因此，任何有意义的可用带宽定义 都是一段时间间隔内带宽即时利用率的平均值。在时间间隔( t i ，t ) 内的平均 利用率 1 石( t l t ) = 三l 。 ( x ) d ( x ) ， 式( 2 4 ) 其中，”( x ) 是链路在时间x 点上的带宽即时利用率。图( 2 1 ) 解释了这种平 均的作用。 在图( 2 1 ) 这个例子中，在总共1 7 个时间间隔中，有6 个间隔带宽被占用， 因此平均的利用率为3 5 3 。 8 第二章网络测量以及带宽测量相关理论 图2 - 1 时间( 0 ，d 内一条链路的即时利用率 接下来我们定义在一段特定的时间间隔内某一跳的可用带宽。如果用c ；来表 示某一跳i 的带宽，用弘来表示那一跳在给定时间间隔内的利用率，则这一跳在这 段时间内的可用带宽 a j = ( 1 一 i ) c l 式( 2 - 5 ) 将上述的定义延伸至一条包含h 跳的路径，这条端到端路径的可用带宽是所 有h 跳中可用带宽的最小值，即 a = r a i n a 式( 2 6 ) 图( 2 2 ) 所示的是一条网络路径的管道模型，其中每一条链路用一段管道表 示。管道的宽度用于表示相应链路的带宽。阴影的部分表示这条链路中已经被使 用的部分，没有阴影的部分则表示尚未被使用的部分。 个岛龟 l1 、c 。 ； 个a 。l ： ： 羹 心忒忒心 ：口 黼黼 图2 2 包含三跳的网络路径的管道模型 在图2 - 2 所示的例子中，最小的链路带宽c ，决定了端到端路径的带宽，而最 小的可用带宽a ，则决定了端到端的可用带宽。正如图2 - 2 中所示，一条路径带宽 9 圈垦k 电子科技大学硕士论文 最小的链路和可用带宽最小的链路可能是不同的。 许多测量可用带宽的方法都假设随时间的变化链路利用率保持恒定，也即是 说他们假设在网络路径上拥有静态的流量负载。虽然在一段较短的时间内这个假 设是合理的，但是，在一段较长的时间内，负载的变化将对测量的准确性造成影 响。 由于可用带宽随着时间而变化，因此快速的进行测量就显得尤为重要。特别 是对于那些需要根据可用带宽调整其发送速率的应用而言。相反，除非是有路由 的变化或者链路的升级发生，一条路径的带宽通常会在较长的时间范围内保持恒 定。因此，对路径带宽的测量的及时性并不像测量可用带宽要求的那样高。 2 2 3t c p 连接吞吐量 在t c p 口网络中，另外一个与带宽相关的重要测量指标是t c p 连接的吞吐量。 i n t e r n e t 中，t c p 协议是主要的传输层协议，有大约9 0 的流量通过它进行传输f 4 】。 然而，定义一条t c p 连接的吞吐量却不是一件容易的事情。很多因素都会对 t c p 吞吐量造成影响，包括传输文件的大小、流量的类型( u d p 还是t c p ) 、t c p 连接的数量、发送方和接收方s o c k e t 缓存的大小、还有传输路径上路由器缓冲区 的大小等等。另外，t c p 协议实现的变种，象n e w r e n o 5 ，r e n o 等使用s a c k 和 累积发送a c k 、对窗口大小初始值的选择等技术都会对t c p 的吞吐量造成影响。 r f c 2 5 8 1 中定义了b u l k - t r a n s f e r c a p c i t y ( b t c ) 1 6 】这个测量指标。r f c 2 5 8 1 中规定b t c 表示的是一条t c p 连接所能达到的最大吞吐量，这条连接必须实现所 有的t c p 拥塞控制算法。但是，r f c 2 5 8 1 中仍然有一些实现细节是未明确定义的。 所以，b t c 测量时须明确指出在端主机的t c p 实现的其他一些相关的重要参数。 必须指出的是b t c 和可用带宽是两个完全不同的测量指标。b t c 是t c p 特 有的，而可用带宽却不依赖于传输层协议的实现；b t c 依赖于一条t c p 连接如何 与其他t c p 连接分享带宽，而可用带宽则假设平均通信流量保持恒定。 2 3 带宽测量技术 在这一节中，我们希望对现存的测量跳和端到端路径带宽和可用带宽的技 术做一个总结。我们针对四种主要的技术：基于可变分组大小的探测技术( v a r i a b l e p a c k e ts i z e ) ，基于分组对的测量技术，基于s l o p s ( s e l f - l o a d i n g p e r i o d i cs t r e a m ) ，和 基于分组对串的测量技术( t r a i n so fp a c k e tp a i r ) 。其中基于可变分组大小的探测技 术是用于测量单跳的带宽的，基于分组对的测量技术是用于测量端到端带宽的， 1 0 第二章网络测量以及带宽测量相关理论 而s l o p s 和基于分组对串的技术则是用于测量端到端的可用带宽的。目前还没有 用于测量单跳的可用带宽的测量技术。 2 _ 3 1v p s ( v a r i a b l ep a c k e ts i z e ) 测量方法 基于可变分组的测量技术最早是由b e l l o v i n 在【7 】和j a c o b s o n 在【8 】中提出的。 这种算法通过i p 头中的1 几域使得探测数据包在传输路径上的某一条过期。那一 跳的路由器将这个数据包丢弃，并且返回给源主机一个“超时”的i c m p 报文。 这样源主机通过收到的i c m p 数据包来计算到达那一跳的r t i 。 到每一跳的k i t 的包含往返路径上的三种延迟：传输时延( s e r i a l i z a t i o nd e l a y ) 、 传播时延( p r o p a g a t i o nd e l a y ) 和排队时延( q u e u e i n gd e l a y ) 。在一条传输速率为c 的链 路上传输大小为l 的数据包，其传输时延为i _ c 。而传播时延是指每一个比特的数 据通过这段链路所需要的时间，是独立于数据包的长度的。排队时延是指数据元 经过各个包交换机所遭遇的缓冲时延的总和。 v p s 算法发送大小一定的多个数据包给传输路径上的每一个第三层设备。这 种算法假设发送的数据包中，至少有一个在传输过程及其产生的i c m p 报文的回 送过程中都没有排队时延。这样，测得的r t t 中的最小值包含两个部分：传输时 延和传播时延。具体的讲，一个大小为l 的数据包总共传输i 跳，其最小的r t f t ，f u 可用式( 2 7 ) 表示： t a l ) k 壹= l 击舢 、。k 式( 2 7 ) 其中，c 。为第i 跳的带宽，a 为不依赖于包大小的时延部分，卢；为最小的r t t 值关于数据包大小的表达式的斜率，并且 屈= if 1 k = l l k 式( 2 - 8 ) 注意到所有回送的i c m p 数据包的大小一样，是一个独立于l 的值。所以数 据项a 包含了i c m p 包的传输时延和所有数据包在来回路径上的传播时延。 通过发送不同大小的数据包估计得到卢；的估计值。对于每一跳i ，重复测量最 小的r t t 值，据此估计出每跳的带宽为 c ； 1 1 屈一卢。 式( 2 - 9 ) 电子科技大学硕士论文 然而，v p s 算法存在的问题在于如果测量的路径上存在有存储转发功能的第 二层交换设备，带宽的测量值将极大的偏小。这些设备引入了传输对延，但是并 不产生i c m pt t l - e x p i r e 报文，因为它们在口层是不可见的。修改v p s 算法来避 免这样的问题一直是一个活跃的研究课题【9 】。 2 3 2 p p t d ( p a c k e tp a i r t r a i nd i s p e r s i o n ) 测量方法 分组包对技术用于测量一条路径的端到端带宽。源主机发送若干个数据包对 给接收方。数据包对由两个相同大小的背靠背的数据包组成。在特定的一条链路 中，两个数据包之间的距离为两个数据包最后一个比特位的时间间隔。数据包对 技术最早是由j a c o b s o n 1 0 ，k e s h a v 1 1 ，和b o l o t 1 2 提出的a 图2 - - 3p a k c e tp a i r 探测方法原理图 图2 3 描述了一个数据包对中的两个数据包在通过一段链路前后的时间间隔， 假设这条链路上不存在其他的流量。如果数据包的长度为l ，且它们所经过的第一 条链路的带宽为c 。，则数据包对在经过这条链路后的间隔变成。= l c 。更一般