（计算机应用技术专业论文）关于internet时延推测的研究.pdf

北京邮电走学硕士论文 关于i n t e r n e t 时延推测的研究 摘要 随着网络重要性的日益提高和网络结构的日益复杂，越来越有必要 对网络的整体拓扑结构和网络行为进行深入的了解、分析，以利于发现 网络瓶颈，优化网络配置，并进一步发现网络中可能存在的潜在危险。 为此，需要对大规模网络结构进行动态描述，并根据网络流量的变化分 析网络的性能，为加强网络管理、提高网络利用率、防范大规模网络攻 击提供技术平台。网络的分析和推测已经成为学术界、企业界和国家政 府部门普遍关心的重要问题之一。 本文在此基础上着重就i n t e m e t 的时延推测方面进行了阐述和讨论。 首先介绍了论文背景，即i n t e m e t 时延推测的原理，重要性、应用，以 及国内外的发展状况。接下来围绕此课题进行了详述，从网络传输时延 的基本概念说起，引入网络性能特征体系的概念，讨论了影响网络时延 的因素，并给出了实际系统中采用的各种实现方法及其综合比较的结 果，接着，就网络传输时延引出时延推测的概念，阐明其在网络研究中 的重要性，并对其进行分类。然后分析了几种现有的网络推测的方法， 根据网络的拓扑结构将其分为树性网络和一般网络两类，并对其做出比 较。 接下来，本文将通信网络描述为一个动态系统，给出网络推测的一 般数学模型和方法，然后由最大似然思想引出e m 算法( 即期望最大化算 法1 的基本思想以及求法的般步骤。然后，针对采用高斯混合模型来逼 近源信号的密度函数，用e m 算法获得参数的思想，根据网络时延的测 量结果，为因特网的端端时延建立密度函数，并针对一个具体的例子给 出主要仿真程序，得出结果：算法能有效地逼近真实的源信号，此种方 法可以用于推测端到端时延。本文还简要介绍了时延推测是利用端到端 时延与链路时延的关系，使用统计信号处理技术进行计算，可以推测网 北京邮电太学硕士论文 络的各节点间链路的时延。将端到端路径时延的推测扩展每段链路的时 延推测。本文针对在m f m m 模型的基础上提出采用辅助测量信息作为 e m 算法的初始值，能够从端端时延的测量结果推测出单一测量路径上 各链路的时延密度函数这一理论，独立完成m a t l a b 环境下网络仿真步 骤，得出仿真结果，并分析了算法的有效性，从仿真结果可看出，算法 能有效地逼近真实的源信号，并得出结论，证明此种算法也可以应用在 链路的时延推测中。 最后是结束语，对全文进行了总结，并对网络性能测量与推测的作 用意义进行了展望，指出了目前在研究中还存在的一些问题和不足，并 给出了下一步可能的研究课题和相应的一些设想。 关键词：网络时延时延推测e m 算法高斯混合模型m f m m 模型 北烹邮电太学颈士论文 r e a r c ho ni n t e r n e td e l a yi n f e r e n c e a b s t r a c t w i t ht h en e t w o r kb e i n gm o r ea n dm o r ei m p o r t a n t ，i t ss t r u c t u r eh a s b e c o m em o r ec o m p l e x ，s oi ti sn e c e s s a r yt od e e p l yu n d e r s t a n da n da n a l y z e t h e t o p o l o g ya n d b e h a v i o ro ft h en e t w o r kt od i s c o v e ri t sb o t t l e n e c k ，o p t i m i z e t h ec o n f i g u r a t i o na n dt h e nf i n dt h ep o s s i b l em a l f u n c t i o no ft h en e t w o r k t h u st h el a r g en e t w o r kf r a m e w o r ks h a l lb ed y n a m i c a l l yd e s c r i b e dt oa n a l y z e t h e p e r f o r m a n c eo f 也en e t w o r ku n d e r d i f f e r e n tl o a da n dt o p r o v i d e a p l a t f o r mt os t r e n g t h e nn e t w o r km a n a g e m e n t ，i n c r e a s et h e u t i l i z a t i o nr a t ea n d d e f e n dm a s sn e t w o r ka t t a c k t h ea n a l y s i sa n d p r e d i c t i o no f 也en e t w o r k h a v e a l r e a d yb e e no n eo f t h em o s tc o n c e r n e dp r o b l e m so fb o t ht h ea c a d e m e ，t h e b u s i n e s sa n dt h eg o v e r n m e n ta sw e l l t h i 8 p a p e rm a i n l y d e a l s 、i mt h ei n t e m e t d d a yp r e d i c t i o n n l ef i r s tp a r t b r i e f l yi n t r o d u c e st h eb a c k g r o u n d , s u c ha st h ep r i n c i p l e ，t h ei m p o r t a n c e ，t h e a p p l i c a t i o na n dt h ed e v e l o p m e n to f t h ei n t e r a c td e l a yp r e d i c t i o n t h e nt h e t e c h n o l o g y i sf u r 血e r e x p l a i n e d i nt h es e c o n d s e c t i o n , i n c l u d i n g t h e d e f i n i t i o no ft h en e t w o r kt r a n s m i s s i o nd e l a y , t h ei n t r o d u c t i o no ft h en e t w o r k p e r f o r m a n c ee v a l u a t i o ns t a n d a r d ，t h e f a c t o r st h a ti n f l u e n c et r a n s m i s s i o n d e l a ya n dt h eo v e r a l lc o m p a r i s o no f d i f f e r e n ts v s t e m sc u r r e t t t l yu s e d a f t e r t h a tt h ed e l a yp r e d i c t i o ni si n t r o d u c e dw i t ht h ee x p l a n a t i o no fi t si m p o r t a n c e a n dt h ec l a s s i f i c a t i o na n d c o m p a r i s o n o fd i f f e r e n t p r e d i c t i o n m e t h o d s a c c o r d i n gt o t h ed i f f e r e n tn e t w o r kt o p o l o g ys u c ha st r e e l i k ea n do r d i n a r y n e t w o r k i nt h en e x t p a r to f t h e p a p e r , s o m ec o m m o n l y u s e dm a t h e m a t i c a lm o d e l s a n dm e t h o d sa r ei n t r o d u c e dw i t ht h ep r i n c i p l ea n dp r o c e d u r eo fe s t i m a t e m a x i m i z a t i o na l g o r i t h mt op r e d i c tt h ec o m m u n i c a t i o nn e t w o r k ，w h i c hi s d e s c r i b e da sad y n a m i cs y s t e m f u r t h e r m o r e ，t h eg a u s s i a nm i x e dm o d e li s u s e dt o a p p r o x i m a t e t h e d e n s i t y f u n c t i o no ft h et r a f f i cs o u r c e a n dt h e i l l 北京邮电大学硕士论文 d e n s i t yf u n c t i o no ft h ei n t e m e te n dt o e n dd e l a yi ss e tu dw i mt h ee m a l g o r i t h ma n dt h em e a s u r e m e n tr e s u l to f t h er e a ln e t w o r k t h es i m u l a t i o n r e s u l ts h o w st h a tt h ea l g o r i t h mc a r lb ee f f e c t i v e l yu s e dt oa p p r o x i m a t et h e r e a ls o u r c et r a f f i ca n dt h em e t h o di sp r e c i s ee n o u g ht op r e d i c tt h ee n dt oe n d d e l a y b e s i d e st h a t ，t h e s t a t i s t i c a l s i g n a lp r o c e s s i n gm e t h o dc a nb eu s e dt o p r e d i c t t h e1 i n k d e l a yb e t w e e n e a c hn e t w o r kn o d eb e c a u s et h e d e l a y p r e d i c t i o ni sb a s e d o nt h ee n dt oe n dd e l a ya n dl i n kd e l a y t h u st h ee n dt o e n dd e l a yi se x t e n d e dt ot h ed e l a yo f e a c hl i n k i nt h ep a p e r i ti sp u tf o r w a r d m a tb a s e do nm f m mm o d e l ，t h em e a s u r e de n d t oe n dd e l a yc a l lb eu s e dt o p r e d i c tt h ed e l a yd e n s i t yf l m c t i o no f t h el i n k so nt h em e a s u r e dp a t hi fm e m e a s u r e di n f o r m a t i o ni su s e da st h ei n i t i a lv a l u eo fe ma l g o r i t h m t h e s i m u l a t i o nr e s u l to nm a t l a bp r o v e st h ee f f e c t i v i t yo f t h ea l g o r i t h ma n di tc a n b eu s e dt op r e d i c tt h e i n kd e l a y t h ef m a lp a r to ft h ep a p e ri st h ec o n c l u s i o no f t h ep a p e r , i n c l u d i n gt h e s i g n i f i c a n c eo f t h en e t w o r kp e r f o r m a n c em e a s u r e m e n ta n dp r e d i c t i o n ，t h e p r o b l e m a n ds h o r t a g eo ft h ec u r r e n tr e s e a r c ho n t h i sf i e l da n ds o m ei d e a so f t h ef u t u r ew o r k k e yw o r d s ： i n t e m e td e l a yp r e d i c t i o ne ma l g o r i t h m g a u s s i a nm i x e dm o d e l m f m mm o d e l 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处 本人签名：磷 本人承担一切相关责任。 日期：硎j 兰一 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘。允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名：塑i ：日期：k 堕：i ! ! 兰 导师签名： 篷鏖局 日期： 地j ! u 坠 北京邮电太学硕士论文第一幸绪论 1 1 论文背景 第一章绪论 i n t e m e t 自6 0 年代出现以来蓬勃发展，近年来更以惊人的速度增长。周时伴随 着多媒体技术的发展，从要求计算机网络仅传输数据到要求其能够传输多媒体信息， 支持诸如视频点播、视讯会议、远程医疗和远程教学等服务，用户对i n t e r n e t 的需 求不断升级，基于i p 技术的因特网正在成为全球经济的基础设施之一。 i n t e m e t 是一个由各种不同类型和规模的独立运行与管理的计算机网络组成的 全球范围的计算机网络。组成i n t e r n e t 的计算机网络包括局域网( l a n ) 、城域网( m a n ) 以及大规模的广域网( w a n ) 等。这些网络通过普通电话、高速率专用线路、卫星、 微波和光缆等通讯线路把不同国家的大学、公司、科研机构以及军事和政治等组织 的网络连接起来。它并不象电话网那样有规则地组织起来，它的子网管理是相互不 协作的，所以直接从网络设备收集数据，反映网络运行状况，一般限制在个较小 的可管理范围内，如果希望知道大范围、更普遍意义上的网络运行参数，只能测量 端端的性能参数。如果能利用端端的测量结果。为网络性能建立模型，推测网络 内部节点的运行参数，将为因特网的测量和管理提供有力的支持。 目前，i n t e r n e t 测量研究工作大致可划分为三部分：端到端性能测量( 主要包括性 能拓扑推测、时延、丢包率测量、带宽测量等) 、路由路由器相关测量( 包括流量 抽样技术、根据路由器端口流量推测端到端流量特征、路由器参数推测、路由器协 作测量协议、路由测量、网络距离推测等) 、应用层测量( w e b 测量、d n s 系统往 能测量等) 。其中对于端到端的网络性能测量。如果能利用端端的测量结果，为网 络性能建立模型，推测网络内部节点的运行参数，将为因特两的测量和管理提供有 力的支持。 端到端性能测量的研究最初是由m i n c 项目中组播树丢包相关的研究引发，而 后雄广到单播网络以及其他性能的研究中。其又称为网络甑层成像( i n t e r n e t t o m o g r a p h y ) ，是一个新兴的领域，它的目标是将i n t e r n e t 网络拓扑、带宽、性能 北京邮电大学硕士论文 第一章绪论 等映射成随时间空间变化的函数，主要是利用网络的部分测量信息通过推导来获得 未知性能的估计和推测，特别是利用端到端的分组延迟和丢失信息来获得网络内部 链路的q o s 性能，比如测量端一端的时延，使用统计信号处理技术进行计算，推测 网络的备节点间链路的时延等。 端到端性能测量 时钟同步，单向时延i 端到端拓扑 |性能推测l带宽推测 时延拓扑推测ii时延性能推测il 链路带宽 丢包拓扑推测ll丢包性能推测 l 瓶颈带宽 图1 1 网络性能测量的研究工作及其联系 可用带宽 在端到端测量技术中，时间测量是许多测量工作的必需因素，这使得测量主机 间时钟同步是许多端到端测量技术的重要基础；在网络拓扑是不可知的情况下，端 到端拓扑推测是端到端性能推测的基础，此外，它还是基于性能角度对复杂物理拓 扑进行抽象简化的有效手段；性能测量( 时延、丢包) 的研究主要集中予树型拓扑的性 能推测，对于一般网络，可将其划分成多个树型拓扑分别进行测量，丽后将这些树 型拓扑上获得的性能参数恢复成整个网络的性能；网络带宽测量的研究包括链路带 宽、瓶颈带宽和可用带宽三部分，带宽测量中引入的一些探针技术，如p a c k e t p a i r ， 也被运用在时延丢包测量中。 1 2 国内外发展状况 在国乡 ，互联网性能监测这一行业已经非常发达，从事互联网性能监测的知名 企业有许多，如c a 、m e r c u r yi n t e r a c t i v e 、k e y n o t e 、b m c 、f r e s h w a t e r 等。这些公 司的股票在纳斯达克表现出色，颇受投资者青睐，像m e r c u r y i n t e r a c t i v e 这样的中等 规模的企业，其市值也在5 0 亿美元左右。 北京邮屯大学礓士论文第一幸绪论 互联网位能监测这一行业正在细化，从t c p i p 体系结构来看，从接口层到应用 层，针对每层不同协议有不同的产品；从网络应用来看，从公共网到服务器再到后 台数据库，针对每一部分都有监测工具；从功能来看，对网络安全、速度、可用性 等都有监测手段。这一市场的发展得益于发达国家相当完善的网络基础设施和相对 成熟的电子商务环境。在全球i t 市场上，有关互联网性能监测方面的产品和服务的 市场总值已达2 0 0 亿美元。 在我国，由于受网络带宽、互联网普及程度、网上交易环境等影响，互联网性 能监测这行业发展相对较晚。但是，随着目前政府对网络经济的大力支持和软硬 件环境的不断完善，这一市场已经初露端倪。跨国公司在华业务的发展、金融证券 业网上交易的开展、传统企业的触网以及一些电子商务企业对自身竞争能力的要求 已经为这个市场的发展打下了初步的客户基础。园此，第三方互联网性能监测服务 提供商游龙科技应运而生，并且已经获得良好的市场反应。 在测量方面，国防科学技术大学，西南交通大学等单位在基于i c m p 协议的i p 拓扑探测方面的技术比较成熟。目前，哈尔滨工业大学计算机科学与工程系实现了 一个大规模网络拓扑测量的原型系统，能够针对大规模网络进行路由i p 拓扑结构的 自动发现，并进行可视化显示。该课题组对全国范围内的近1 7 万个i p 进行了探测， 获得了1 6 1 2 个路由i p 节点间的2 9 4 0 个连接关系，并结合各i p 的地理信息，生成 了分层次的地理拓扑图，准确度达到9 0 以上。 未来几年，随着我国全民上网的普及和电子商务交易环境的日趋成熟以及网络 竞争的日趋激烈，互联网性能监测这一市场空间将得到极大的拓展 1 3 课题的主要任务 本文主要研究网络时延的推测方面。网络内部性能在空间的分布信息可以极大 地提高动态路由算法和流星传输协议的性能与效率，但是，在网络的每个点进行网 络流量测量是不切实际的。一种有前途的方法是：仅在网络边缘测量，并由这些测 量来推测网络的内部延迟行为，通过发送端到接收端的端到端延迟测量估计内部延 迟或延迟分布。需要解决的核心问题是如何从端到端测量结果获得每个路由器的延 迟。 北京邮电大学硕士论文 第一章绪论 本课题针对在网络的每个节点直接测量分组延迟是不实际的情况，分析对i p 网 进行网络推测的重要性，同时学习网络测试方法和推测原理。在掌握其基本原理的 条件下对各种算法，如高斯混合模型、e m 算法、m f m m 算法等，将其应用到网络 时延推测中进行分析研究，对其进行对比，找出其中的不足。熟练使用m a t l a b 程序 设计语言，针对几种算法进行编程仿真，利用测量的端端的时延，推测网络的各节 点间链路的时延，并完成网络仿真工作，给出仿真结果，对比推测值和真实值，得 出结论。 1 4 论文的结构和安排 本文的剩余部分内容安排如下： 第二章从网络传输时延的基本概念说起，引入网络性能特征体系的概念，讨论 了影响网络时延的因素，并给出了实际系统中采用的各种实现方法及其综合比较的 结果，接着，就网络传输时延引出时延推测的概念，阐明其在网络研究中的重要性， 并对其进行分类。 第三章主要分析了几种现有的网络推测的方法，根据网络的拓扑结构将其分为 树性网络和般网络两类，并对其做出比较。 第四章首先通信网络描述为一个动态系统，给出网络推测的一般数学模型和方 法，然后给出了e m 算法( 即期望最大化算法) 的基本思想以及求法的一般步骤。接 着针对采用高斯混合模型来逼近源信号的密度函数，用e m 算法获得参数的思想， 根据网络时延的测量结果，为因特网的端端时延建立密度函数，并针对个具体的 例子给出主要仿真程序，得出结果：算法能有效地逼近真实的源信号，此种方法可 以用于推测端到端时延。 第五章首先简要介绍了时延推测是利用端到端时延与链路时延的关系，使用统 计信号处理技术进行计算，可以推测网络的各节点间链路的时延a 将端到端路径时 延的推测扩展每段链路的时延推测。本章针对在m f m m 模型的基础上提出采用辅 助测量信息作为e m 算法的初始值，能够从端一端时延的测量结果推测出单一测量路 径上各链路的时延密度函数这一理论，独立完成m a t l a b 环境下网络仿真步骤，得出 仿真结果，并分析了算法的有效性，从仿真结果可看出，算法能有效地逼近真实的 北京邮电大学硕士论文第一章绪论 源信号，并得出结论，证明此种算法也可以应用在链路的时延推测中。 第七章是结束语，对全文进行了总结，并对网络性能测量与推测的作用意义进 行了展望，指出了目前在研究中还存在的一些问题和不足，并给出了下步可能的 研究课题和相应的一些设想。 北京邮电大学硕士论交第二章网络传输时琏的测量厦推测 第二章网络传输时延的测量及推测 网络传输时延是最基本的网络性能评价指标，也是业务流测量系统中最重要、 最常用的衡量参数。准确地测量网络传输时延，对于整个业务流系统架构的配置、 动态选用合理网络实体以及系统资源的分配，都有着举足轻重的意义。本章首先介 绍了网络性能特征体系，接着介绍了网络传输时延测量的概念，讨论了影响网络时 延的因素，并给出了实际系统中采用的各种实现方法及其综合比较的结果，最后， 就网络传输时延引出时延推测的概念，阐明其在网络研究中的重要性，并对其进行 分类。 2 1 网络性能特征体系 网络由一个个的网络实体( n e t w o r ke n t i t y ) 组成，网络实体可以分成网络节点 ( n e t w o r kn o d e ) 和网络路径( n e 脚o r kp a t h ) 。节点的定义是能使用互联网协议来通讯 的计算机，包括主机、路由器、交换机、代理等。路径是一个节点到另一个节点的 单向连接。 性能特征( p e r f o r m a n c ec h a r a c t e r i s t i c ) 是描述网络实体性能与稳定性方面的内 在属性。节点和路径的性能特征使得由于不同类型网络流量形成的网络行为就能够 有区别的表现出来。图2 - 1 给出了性能特征与相关概念之间的关系。 气三 u 也删i 。翩。蚺w 讯弱翮 广 图2 - 1 网络性能测量体系 北京邮电大学硕士论文 第二幸同络传输时延的谭q 量度推测 测量方法( m e a s u r e m e n tm e t h o d o l o g y ) 是记录和估算性能特征的技术。一般，一 种特征有多种测量的方法。测量方法可能是“原始”的，也可能是“推导”。“原始”测 量方法得到测量的原始记录。“推导”测量方法则是聚合或估算一组“原始”测量或低 级的“推导”预4 量得到测量结果的。例如，通过统计分析突发数据包的方法来信计带 宽的容量。 测量方法的输出就是观察值( o b s e r v a t i o n ) 。一个观察值可能是不可分割的原子 ( s i n g l e t o n ) i 己r j - l ：值，也可是原子值组合而成的抽样( s a m p l e ) 值。也可是在对抽样值的 统计( s t a t i s t i c ) 结果值。因为网络性能特征具有高速变化的动态特性每个观察值 必须带有时间信息，用于表明测量的时间。对于“原子”观察值，一个时间戳就够了， “统计”观察值的记录，开始和结束观察的时间均要记录。 网络的带宽a n d w i d t h ) 、时延( d e l a ”和丢包( l o s s ) 是最能体现网络行为的三类 性能特征，如图2 - 2 所示。但它们只是一般化的概念，在得到有意义的测赶数据之 前，它们被细化成两到三种更细的性能特征。带宽包括容量带宽( c a p a c i t yb a n d w i d t h ) ， 可用带宽( a v a i l a b l e b a n d w i d t h ) 和己用带宽( u t i l i t y b a n d w i d t h ) 。时延特征包括单向时 延( o n e w a yd e l a y ) 、双向时延( r o u n d t r i pd e l a y ) 丢包特征包括单向丢包( o n e - w a y l o s s ) 、双向丢包( r o u n d - t r i pl o s s ) 、丢包模式( l o s $ p a t t e r n ) 。这些分类不是固定不变 的，有时根据需要会增加类别。 圈2 - 2 罔络性能镣征分爽 北京邮电走学硕士论文 第二章网络传输时延的测量度推测 容量带宽是指路径能够传输的最大数据容量。己用带宽为当前网络路径上流量 之和a 可用带宽则是在当前已用带宽的前提下，路径能给一个网络应用所能提供的 最大吞吐量，它可由容量带宽和已用带宽直接得出。由于运行于网络两端的应用之 间来回路径可能不是同一条物理链路，而且即使是同条物理链路，但来回路径上 的拥塞情况也有可能不一致，这两点原因使得时延和丢包的路径特征必须单方向区 分，导致单向时延和单向丢包性能特征的出现。 2 2 网络传输时延基础 2 2 1 时延的基本概念 概括的说，时延被分为四个主要部分 处理时延( p r o c e s s i n gd e l a y ，正) ：指分组到达个节点的输入端与该分组到 达该节点的输出端之间的时延。它受每个节点的计算能力和可用的硬件的影响，不 受流量的影响。乙总体上看是一个随机变化的，每一个探测包在路由器中处理的速 度不完全相同，因此，我们分巧为一个确定部分和一个随机部分， 乙= 0 a + 乙。 传输时延( t r a n s m i s s i o nd e l a y ，z ) ：指发送节点在传输链路上开始发送分组的第 一个比特至发完该分组的最后一个比特所需的时间。e 主要由连接速度或容量决 定，对于每一个探测包，传输时延被认为是相同的。 传播时延( p r o p a g a t i o nd e l a y ，。) ：指发送节点在传输链路上发送第一个比特时 刻至该比特到达接收节点的时间。t 。由电磁波通过通信链路的物理信道的传输时 间所决定。 排队时延( q u e u i n gd e l a y ，瓦) ：指分组在路山器的缓冲区中，传输前的等待时 间，乙由路由器中的交换结构决定。若节点的传输队列在节点的输出端，则排队时 延是指分组进入传输队列到该分组实际进入传输的时延。若节点的输入端有一个等 待队列，则排队时延是指分组进入等待队列到分组进入节点进行处理的时延。 令最小要求的数据包的大小为m 。比特( 仅是头字节加上尾字节的大小) ，总的数 北京邮电大学硕士论文第二章目络待输时延的制量及推割 据包的大小为m 比特。在第i 个节点，置为传输速率，则分别用乙互，j t 。乙， 表示处理时延大小，传输时延大小，从节点i 到节南的传播时延大小，m 比特大小的 数据包的排队时延大小。r 为总的传输速率( 各个链路传输速率总和) ，l 为传播对延 和处理时延的总和，瓦为排队时延的总和，则对于一个k 跳的链路： l膏一i 三= + 0 ， 扭if = l r = r ， i = i 。 m 。2i 式( 2 一1 ) 式( 2 2 ) 式( 2 3 ) m 比特大小的数据包的端到端时延： a a t a y ( m ) 邓+ m o + ( + 半) 斓 式( 2 5 ) 中第一项( 上+ 单) 是端到端时延的固定部分，它依赖于最初设计的网络 性能( 如数据包的传输速率) 和最短的数据包长 厶。 第二项( 乃+ ! 堕二芋监) 是端到端时延的随机部分，它依赖于网络的拥塞程度( 如链路 利用率) 和数据包大小m 。 网络传输时延的精度由发送方、接收方的系统而定。通常，考虑到正常使用时 操作系统对进程调度的时间粒度、收到数据报文的提交、中间结果的计算等时间因 素，网络的传输时延精度设置为lm s 。而且，在p c 系统上不能测量网络的传输时 延小于1 0 m s 的情况。 网络传输时延的结果一般用兰元组来表征，即最大传输时延、最小传输时延、 平均传输时延。通常情况下对同一对象测试4 5 次即可得出结果，当然也可以根据实 际的需要设定测壁次数和测量结果的表示形式。 弓 。阿 = l 北京邮电太学硕士论文 第二章网络传输时延的测量及推测 2 2 2 时延的分类 网络的传输时延主要可以分为2 类，即有往返时延( r o u n d - t r i pt i m e ：r t t ) 和单向 时延( 即端到端时延e n d t o e n dd e l a y ) 两种，基本单位为秒。网络的单程传输时延，是 指从发送方( 源端) 的物理设备开始发送数据至接收方( 目的端) 的物理设备全部接收 到该测量报文所需要的时间。单程对延的测量需要有专门的时间同步设备，如g p s 等。因此，通常意义上的网络传输时延测量指的是测量报文往返的时延测量，即；受0 量报文从发送方开始发送时计时，接收方在接收到该报文后立即返回给发送方，发 送方接收到该测量报文届停止计时，此时发送方所得的时闻间隔邵为往返时延， 测量单向时延和双向时延的好处： 1 如果两机器之间的端到端时延超过某个闽值后，它们之上的一些应用程序不 能很好的工作，或者根本不能工作。 2 交互形式的实时应用很难或不可能在时延的恶性波动的环境下工作。 3 时延越大，传输协议越难保持占用高的带宽。 4 从时延的最小值可直接得知构成时延的固定部分连接的传输时延和机器的 发送时延。 5 当时延指标值最小时表明测量包经过的连接负载极小。 6 最小值之上的时延表示连接上出现拥塞。 单向时延较双向时延的优势： 1 来回路径的不对称性，从源到目的路径与从目的到源的路径不一样，经历不 同路径上的序列的不同路由器，双向时延实际上反映了两条不同连接的性能。 2 即使来回路径对称，经历相同的路由器序列，但路由器队列的不对称使得两 个方向的性能差距可能很大。 3 。一些种类的应用依赖于只单方向的时延性能。 4 在一些提供q o s 保障的网络，一条连接的性能往往在两个方法有很大的不同， 要验证时必须单方向测量。 双向时延的优势： 1 易于部署。测双向时延时不需像测量单向时延要在目的端安装专门的测量软 件。己经有许多基于i c m p ec h o 和t c p 回应的测量工具。 2 ，易于解释。在某些时候只要双向时延，如果把一条连接的相反方向单向时延 北京邮电大学硕士论文 第二幸网络侍输时延的测量厦推洲 和两端的处理时延相加得到双向时延，会带来较大的不准确性。 3 时钟带来的测量误差只要考虑源端时钟的频率一致性，不需考虑源和目的端 的同步。 考虑到业务流本身具有交互性的特点，因此论文中的网络传输时延均指的是网 络传输的往返时延。 端到端时延是评估i n t e r n e t 的网络性能的重要参数之一。通过对端到端对延的测 量，能够分析当前t n t e r n e t n 基本特性，可根据i n t e m e t 的q o s 要求进行网络规划设计， 如推测网络的拓扑结构和网络的流量模型等，为网络技术的改进提供可靠的理论依 据。 2 2 3 影响网络传输时延的因素 网络传输时延总是随着网络的运行状况而不断的变化，但是仔细分析可知，网 络的传输时延主要与如下二类因素密切相关： 因素一、网络本身的性能，即完全独立于网络业务流测量方法、仅与网络本身 的硬件特性相关的部分，主要包括三个方面的因素： 1 ) 网络的物理介质。不同的物理介质，例如光网、以太网和无线n 络( w i r e l e s s n e t w o r k ) 上，随着底层物理信号实现、转换的不同，丽导致网络本身带宽各不相同， 因此对于具有一定长度的数据报文而言，其传输速度也各不相同。并且，在某些介 质中，还需要对数字信号进行调制和解调，以实现数字信号与模拟信号甚至是光信 号的相互转变，因此相对而言额外的时间开销较大。 2 ) 当前传输所需的路由、转发、过滤次数。路由器的路由、转发实现需要时间 而在路由上等待转发也同榉需要时间。因此经过的路由器个数越多，转发的次数越 多，带来的时延也就越大。同时，路由器负荷越重，等待队列越长，时延也就越大。 同样，在经过防火墙时，防火墙会对报文进行扫描、过滤，不同效率的防火墙、不 同的过滤次数( 经过防火墙的个数) 等，都会对报文的传输时延产生影响。 3 ) 网络的数据链路层协议的不同实现方式。数据链路层对数据报文的传输存在 北京邮电大学硕士论支 第二章网络传输时延的测量厦推测 多种实现方式。在完全相同的上层协议和底层的物理链路上，不同传输机制的实现 对传输时延会产生不同的影响。例如，发送方采取何种机制以避免拥塞。早期的链 路层协议，只有当发送( 接收) 缓冲区满时，才开始进行“丢尾”操作，即直接将溢 出的数据丢失。这样的处理，使网络在抗报文的碎发( b u r s t ) 情况时性能极差，使传 输时延呈现较大的波动。而相比之下，现在新的数据链路层协议，采用r e d ( r a n d o m e a r l yd e t e c t i o n ) 机制，在缓存区没有达到满时，即有选择地( 例如，可以根据报文的 q o s 请求级别) 进行报文丢弃，这样使得网络抗b u r s t 的性能大为增强，同时，也使 得传输时延比较稳定。再例如，报文丢失后的恢复重传机制。特别是在某些特殊的 网络中( 例如无线网络中) ，上层的数据报文在实际的物理链路层传输时，都将被分 成若千小片( f r a m e ) 。因此，当出现小片丢失时，链路层可以采取不同的a r q ( a u t o m a t i cr e p e a tr e q u e s t ) 机制，如停等( 即一直等待超时) ，全部重传，选择重传等 等，这些不同的机制对上层报文的传输都带来了必然的影响。总之，底层的数据链 路层不同的实现方式，会对传输时延产生极大的影响。 因素二、测量报文的特定性能。相对因素一而言，这和网络具体的测量方式密 切相关，主要可以分成如下两个方面： 1 ) 承载报文的协议类型。网络传输时延的测量，往往要根据实际的情况( 例如， 对方防火墙设定的过滤规则) 来选取合适的承载报文的协议。而不同的协议，有着不 同的发送机制和速率控制模式，其实现方式也各不相同。对接收方而言，从收到承 载报文到给出反馈报文的实现过程，也随着协议的不同而各不相同，响应的时间， 处理的时间都不一样。因此选用不同协议测试的结果可能会存在一定的差异。 2 ) 报文长度、发送频率。在一段具体的链路上，带宽一定的情况下，报文的长 度、发送频率与传输的时延成反比。因此，报文越长，频率越高，其传输时延也就 越大。 此外，当前的网络流量、处理机性能( 包括其接收、处理数据报文的速度) 和其 当前的作业量等等，也对网络传输时延产生影响。当网络或处理机处于重载时，其 传输速度、响应处理速度会大大下降。此时若测量网络传输时延，测量结果将比轻 载时大。 北享邮电大学硕士论文第二章网络待输时琏的测量厦推剥 2 2 4 网络传输时延的实际测量方式 实际测量是对真实网络的测量，它可以对算法和模型进行应用和检验，是 n e t w o r k i n gt o m o g r a p h y 的基础。 网络测量与分析主要分为3 个研究领域：( 1 ) 测量领域。精确地捕捉定量的因 特网及其活动的测量数据。网络测量的主要参数包括r t t 、路径数据、带宽、延迟、 瓶颈、突发业务置的频率、拥塞程度、动态瓶颈、站点的可达性、吞吐量、带宽利 用率、丢包率、服务器和网络设备的响应时间、最大的网络流量、网络服务质量q o s ( 包括图像、数据、语音等服务的质量) 等。( 2 ) 模型化领域。这是性能评价的核 心问题建立正式的网络描述与模拟。这种模型的有效应用可以实现对未来网络 行为的预测。( 3 ) 控制领域。利用从测量和模型化得到的知识，实现因特网资源的 合理配置使用。 根据测量技术获得网络节点支持的多少以及测量点的位置，测景可分为基于路 由器的测量( r o u t e r - b a s e dm e a s u r e m e n t ) 、端到端测量( e n d q o - e n dm e a s u r e m e n t ) 和 路由器协作测量( r o u t e r - a i d e dm e a s u r e m e n t ) 。基于路由器的测薰主要由路由器中的 管理软件来完成测量。i s p ( i n t e r n e ts e r v i c ep r o v i d e r ) 通常采用基于路由器的测量来 监测其内部网络的拓扑、流量、时延、丢包率等。由于各i s p 之间的非协作性，这 些数据对外保密；另外，将大量路由器统计的性能数据传递给中心网管系统，本身 就需消耗大量带宽，增加网络负荷；这些原因使得在许多场合下不适合采用基于路 由器的测量。端到端测量的目标是在只有边缘主机参与下，无需路由器的配合，获 取网络性能统计，并且尽可能减小对网络造成的负荷。路由器协作测量在边缘主机 上执行测量，但需要路由器的配合，这方面近来提出了一些新协议。由于i n t e r a c t 不 同i s p 之间不协作的特点，依赖于路由器目b 合的测量方法的能力将受眼，因此，路 由器协作的测量需要获得标准化组织和工业界的支持。 根据是否发送主动探针( a c t i v ep r o b e ) ，测量技术可分为主动测量和被动测量技 术。被动测量不发送承载报文，而是根据具体情况选取正在通讯的报文作为承载报 文，即在正常的通信过程中同时实现了网络传输时延的测量，其原理是通过捕获承 载报文的信息，被动地实现网络传输时延的测量，不会对网络的负荷造成影响a 主 动测量通过向网络发送探针，并根据探针所携带的信息来推测网络的情况，主动测 量将影响网络的负荷，产生大量探针的主动测量方法无法实用。探针是由同一源发 北京邮电大学碰士论文 第二章网络传输时延的测量厦推测 送的数据包序列，根据发送探针数据包的类型，还可划分为组播探针、单播探针。根 据探针结构的差异，常用的探针可分成：单数据包探针、等长和非等长数据包对探针、 数据包串探针等。 两种测量技术适用于不同的测量需要。被动测量被动地监测网络，捕获数据信 息，它不增加网络流量，不对网络数据进行修改，因此不影响网络行为。而主动测 量向网络中发送测量报文，因此主动测量会引发性能的失真，即所谓h e i s e n b e r g 效 应，这是由于测量报文插入到网络中的数据包会改变网络的行为，从而使实际测量 的结果失真。因此采用主动测量时必须尽量减少由测量所生成的流量。 另外，网络传输时延的测量按照其承载的协议可以分为如下三类 1 ) 利用i c m p 协议实现。这是最常用的测量方式，最典型的应用就是操作系统 里自带的“p i n g ”命令。p i n g 是基于i c m p 请求应答( e c h or e q u e s t ) 报文开发的应用软 件，p i n g 发送i c m p 的e c h o