基于包速率模型的网络带宽测量.docx

1、基于包速率模型的网络带宽测量 基于包速率模型的网络带宽测量 目录 1 前言 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1. 1 网络带宽测量的研究背景及意义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1. 2 国内外研究现状 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2、 . . . . . . . . . . . . . . 1 1. 3 网络带宽测量面临的挑战 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 需求分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. 1 功能需求分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3、 . . . . . . . . . . . . . . . . 3 2. 2 运行环境 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. 3 开发工具 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3 分析和设计 . . . . . . . . . . . . . . . . . . . . .

4、 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3. 1NS 平台的介绍 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3. 2 NS 软件包、 模块的组成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3. 3 工作机制 . . . . . . . . . . . . . . . . .

5、 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 4 基于自感应拥塞理论的算法分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 4. 1 基于自感应拥塞控制 ITP 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 4. 2 ITP 算法概述 . . . . . . . . . . . . . . . . . . . . . . . . . .

6、. . . . . . . . . . . . . . . . . . 8 5 算法实现 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 5. 1 算法流程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 5. 2 算法参数 . . . . . . . . . . . . . . . .

7、 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 5. 3 仿真实验 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 6 性能瓶颈分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 7 课程设计总结 . . . . .

8、. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 参考文献 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 致谢 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9、. . . . . . . . . . . . 18 1 前言 1. 1 网络带宽测量的研究背景及意义 近年来以TCP/IP为主要协议的Internet技术飞速发展， 网络的规模不断扩大， 网络上的流量爆炸式增长。 Internet已经渗透到社会的各个领域， 成为现代社会最重要的基础设施之一。 但是， 由于Internet发展的特殊性， 人们对于Internet的流量模型、 网络行为、 性能指标等都缺乏理解和精确的描述， 对网络测量技术的研究明显滞后于网络及其应用的快速发展。 特别是， 实时业务和多媒体应用等新业务不断增加， 对网络的服务质量 （QoS）提出了更高的要求。 如何在Interne

10、t上提供QoS保证是近几年学术界和产业界共同关心的热点问题。 人们提出了一系列的QoS保证框架， 不论是在应用层的负载均衡或传输层的综合服务 （IntServ） 和区分服务 （DiffServ） ， 还是网络层的流量工程 （Traffic Engineering）和QoS Routing， 都是以对网络运行状态进行测量并将信息有效发布为基础的。 此外，Internet规模日益膨胀， 如何对网络带宽进行有效的管理、 规划和利用是网络设计者、 管理者和使用者共同关心的问题。 Internet是一个商业性的基础设施， 所有接入Internet的用户都要付费给为他们提供接入服务的Internet服务提

11、供商（ISP） 而衡量ISP提供接入服务的优劣通常取决于ISP为用户所提供接入带宽的大小， 因为高带宽通常意味着高速度和较高的服务质量保证。 在这种前提下， 网络带宽的监测成为因此， ISP服务商和接入用户迫切需要解决的问题： 接入用户需要检查他们是否获得了 ISP服务商所允诺提供的接入带宽： ISP服务商也需要带宽测量工具来规划他们的带宽分配， 以避免链路拥塞和提高链路利用率。 此外， 网络带宽的测量在提高应用程序性能、 研究新的拥塞控制算法和建立高性能多播路由树等方面， 也具有重要意义。 研究Internet网络性能测量方法是了解网络行为， 采取措施进行网络控制， 实施QoS保证， 提高网

12、络性能的重要环节和前提基础， 具有十分重要的意义。 1. 2 国内外研究现状 对网络行为观测与研究的系统讨论源于一次有关Interact统计与测量分析的研讨会(ISMA)， 是在1996年初美国应用联网研究国家实验室(NLANR) 与Beloote在美国NSF支持下召开的。 在此之后， 依托于美国加州大学圣迭戈分校超级计算中心(SDSC)的C AIDA(Internet数据分析联合会) 对网络测量的相关理论和方法展开了系统性的研究。 IM也成立了专门的工作小组IPPM(IP Performance Metrics)来制定IP网络的运行 参数。 目前国外许多组织和机构， 如美国应用网络研究国家实

13、验室NLANR、 因特网数据分析合作组织CAIDA、 Stanford大学和美国的NIMI等， 对带宽测量已经或正在进行大量的研究， 并取得了一些成果。 与国外相比， 国内对可用带宽测量技术的研究起步晚一些， 但现在已经有很多大学和公司对带宽测量都进行了不同程度的研究。 国内一些高校和研究所， 如中国科学院计算技术研究所、 信息产业部电信传输研究所、 北京邮电大学、 湖南大学等， 也在进行带宽测量的研究。 目前形成的可用带宽测量方法和测量工具比较多， 但由于可用带宽与背景流量相关， 其值随链路上流量的变化而变化， 是一个动态的概念， 要准确测量它非常困难， 因此， 如何准确的测量可用带宽是一个

14、具有挑战性的问题， 也是网络技术的研究热点之一。 1. 3 网络带宽测量面临的挑战 评价网络性能有很多指标， 包括网络容量、 丢包率、 可用带宽、 延时、 背景流量等。 随着网络的飞速发展， 网络应用更加关心的是自己可以使用的带宽， 即可用带宽。 在过去的十几年中， 研究者们一直不懈地努力提高端到端的可用带宽测量算法的精度和速度， 然而， 可用带宽本身具有动态变化的特性， 受到很多因素的影响， 可用带宽测量面临诸多挑战： 1） 背景流量的突发特性： 造成了可用带宽的动态性， 给测量带来了很大困难， 需要采用一定的技术缓和背景流量的突发性给测量结果造成的偏差。 2） 可用带宽测量技术的实际应用性

15、： 即要求可用带宽测量准确性和可操作性， 而且测量时间短， 开销低， 从而能在实际网络应用程序中集成， 达到测量可用带宽的真正目的。 3） 多瓶颈链路模型的可用带宽测量： 现有的可用带宽测量技术都是基于单瓶颈链路模型， 用于多瓶颈链路环境时， 测量结果就会出现一定的偏差。 4） 时间精度问题： 现有的可用带宽测量技术都是基于时间信息统计分析， 因此，最小时间粒度(时间精确度) 是限制可用带宽测量精度的一个非常重要的因素。 如果最小时间粒度比测量的间隔还大， 那么可获得的时间间隔就是最小时间粒度； 如果最小时间粒度比两个包的时间间隔大， 就认为这两个包同时到达。 2 需求分析 2. 1 功能需求

16、分析 基于包速率模型的网络测量原理 （自感应拥塞理论）的两种重要算法： ITP和SLoPS算法， 其中围绕了ITP算法讲述了该模型下的算法的原理。 根据自感应拥塞理论， 如果我们向网络中注入探测包的速度大于网络的可用带宽，节点处的拥塞就会导致排队的出现。 这样， 排队时延会使得数据包的传输延迟增大; 相反， 如果探测流量小于路径的可用带宽， 数据包的延迟中则不包括排队延迟。 所以， 我们可以通过改变注入流量的速率， 进而得到使得数据包传输延迟增大的最小值， 将其做为可用带宽的估计值。 2. 2 运行环境 （1） WINDOWS2019/XP 系统 （2） NS 平台 2. 3 开发工具 Pat

17、hload、 TOPP、 ITP 等。 3 分析和设计 3. 1NS 平台的介绍 NS是一个用C+编写， 并且以OTCL为前端的面向对象的模拟器。 模拟器支持C+中的类的层次结构和OTCL解释器中的类似的层次结构。 它是Network Simulator的首写字母缩写， 是由LBNL ( Lawrence Berkeley National Laboratory ) 的网络研究小组开发的仿真工具。 NS是一种可扩展、 易配置、 可编程的事件驱动的网络仿真软件。 LBNL的网络仿真软件的开发始于1990年5月对S.Keshav的REAL网络仿真程序的修改， 并于91年夏天完善成为Tcpsim。

18、1994年12月， Mccane用C+重写了Tcpsim，并用基于Tcl ( Tool Command Language ) 的仿真语言代替了基于yacc ( yet another compilers compiler ) 的仿真语言， 同时支持多点发送。 该仿真软件从此改称为NS。 NS仿真程序所使用的脚本语言是由Tcl语言和OTcl语言， 其中 Tcl（ Tool Command Language） 语言是由美国加州大学伯克利分校的John K. Ousterhout教授开发的解释执行的程序语言。 Tcl语言是一种用来控制和扩展应用程序的简单脚本程序， 它具有与普通的程序设计语言相似的一

19、些特点， 如变量、 循环及子程序等； OTcl语言是Object Tool Command Language的简称， 它是由麻省理工大学开发的面向对象的Tcl语言。 NS软件的Tcl脚本程序中涉及到类与对象的部分都是OTcl语言的语法，仿真支持C+中类的层次结构（称为编译体系） ， 也支持OTcl解释器中相似的层次结构（称为解释体系） 。 3. 2 NS 软件包、 模块的组成 Ns-allinone中含有12个模块： 模块 版本号 必选/可选 Tcl Tcl release 8.3.2 必选 Tk Tk release 8.3.2 必选 Otcl otcl release 1.0a6 必选 T

20、clcL tclcl release 1.0b10 必选 Ns ns release 2.1b7 必选 TclDebug tcl-debug relase 1.9 可选 Nam Nam release 1.0a9 可选 Xgraph xgraph version 12 可选 GT-ITM Georgia Tech Internetwork Topology Modeler 可选 0 SGB Stanford GraphBase package 可选 1 CWEB CWeb version 1.0 (?) 可选 2 Zlib zlib version 1.1.3 可选 上表中各大模块说明如下：

21、1、 Tcl： Tcl提供了一个强有力的平台， 可生成面向多种平台的应用程序， 协议，驱动程序等等。 它与Tk(toolkit)协作， 可生成GUI应用程序， 可在PC、 Unix和Macintosh上运行。 Tcl 还可用来为应用程序提供强有力的命令语言。 2、 Tk： 与Tcl协调工作的图形工具包。 3、 OTcl： MIT Object Tcl的简称， 是Tcl/Tk 面向对象编程的扩展。 4、 TclcL： 此目录下含tcl/C+的接口， vic、 vat、 ns、 rtp_play、 和nam都会用到。 5、 ns： NS的主体代码， 内含一个节点移动产生器、 两个传输事件产生器。

22、6、 TclDebug： Tcl调试工具包。 7、 Nam： 即UCB/LBNL Network AniMator， 它与NS协同工作， 将NS仿真过程动态表现出来。 8、 Xgraph： Xgraph是一X-Windows应用程序， 主要包含交互式测量、 绘制和 动画效果 9、 Gt-itm： GT Internetwork Topology Models的简称， 产生模拟internt网络结构的拓扑图， 还提供了一些例子。 10、 SGB： Standford GraphBase的简称， 图形产生器。 11、 Cweb： 与网页相关的工具。 12、 zlib： 通用数据数据压缩库（data

23、 compression library） 。 3. 3 工作机制 NS 的仿真工作机制如图 3.3 所示。 图 3.3NS 的仿真工作机制 进行仿真前， 首先要分析涉及仿真的哪一个层次。 NS 仿真分两个层次： 一个是基于 OTcI 编程的配置、 构造层次， 利用 NS 己有的网络仿真元素实现仿真， 无需对 NS本身进行任何修改， 只要编写 OTcl 仿真脚本， 如图 2.4.2 中流程 1-2-3; 另一个层次是基于 c+和 OTcl 编程的编译、 配置层次， 如果 NS 中没有所需的仿真元素。 NS 提供了用户自我升级或修改协议的技术， 即利用 OTcl 和 NS 的接口类实现 NS 更

24、新， 新NS 生成流程如图 6.1 中 4-5-6， 然后再进行 1-2-3 流程完成仿真。 NS 的目的是提供一个完整的网络仿真平台， 它有庞大的网络元素体系， 从物理层到应用层、 从局域网到广域网、 从有线网到无线网， NS 都提供了丰富的支持。 然而对于网络研究人员而言， 只需要熟悉 NS 相关自己研究方向的基本元素， 对于其它的网络 元素可以做透明 处理。 实践表明， 网络仿真常常涉及第二个层次。 进行第二层次的仿真开发， 首先要充分理解和熟 OTcl 的六个接口 类， 即 Tcl, TclObject, TclClass, TclCommand, Embed-ded,TclInstV

25、ar。 在掌握关于具体课题的 NS 元素的基础上， 分析要建立的新元素特征， 利用 NS 的面向对象特性来构造新的 NS。 如果新方案和现有 NS 元素差别较大， 就需要编写新的 c+程序； 如果无需进行较大改动， 也可以在 NS 现有相关元素的 c+代码中进行修改来达到目的。 例如在某个存在的元素中修改某个算法或增加实现某个功能的函数等。 4 基于自感应拥塞理论的算法分析 基于自感应拥塞理论的三种常见工具的算法分析： Pathload、 TOPP 以及 ITP 测量方法的算法分析。 本课程设计详细介绍 ITP 算法的拥塞控制。 4. 1 基于自感应拥塞控制 I TP 算法 通过仔细分析不难发

26、现， 如果我们仅仅认为探测流量大于可用带宽时， 传输时延会因为排队时延的引入而增加； 而探测流量小于可用带宽时， 数据包的传输时延不会受到排队时延的影响， 则网络中真实的流量情况被大大的简化了。 事实上， 由于突发性背景流量的影响， 即使在探测流量逐渐增大的情况下， 探测数据包的排队时延也不仅仅是简单呈现单调递增的趋势。 在 TOPP 算法的实测过程中发现， 如果传输路径由多条链路组成， 则0 R相对于0/mRR的曲线图中可能出现多次斜率的变化， 而这种变化是由数据包在可用带宽大于端到端可用带宽 A 的链路上的排队造成的因此， 随着探测流量速率的不断增加， 数据包传输路径上的排队时延和探测流量

27、速率的关系如图 3.3 所示。 图 4.1 排队时延特征图 从图 4.1 中， 我们发现随着单位时间内发送的数据包的不断增加， 排队时延并不呈简单的递增趋势。 排队时延随时间变化的曲线图包含若干个偏移。 开始的几个偏移都以排队时延回到 0 而结束。 这是因为这时探测流量小于链路的瓶颈带宽 (minC=min i C ) ，在没有背景流量情况下， 拥塞队列得到释放， 从而排队时延减小到 0。 而最后一个偏移却是以排队时延逐渐增加而结束， 因为这时探测流量大于链路的瓶颈带宽， 探测数据包逐渐填满传输路径上的拥塞队列。 根据以上对算法的分析， 我们提出一种改进的算法， 这种算法的基本原理类似于pat

28、hload 和 TOPP， 基于自 感应拥塞理论。 它运用分组串技术， 因此我们把它称为Improved Trains of Packet (ITP) 。 ITP 算法具有以下特点: 1） 建立在自感应拥塞理论的基础上， 与其它基于这种理论的测试算法的主要差别在于使用一个数据包之间间距呈指数级减小的探测序列， 具有很高的效率。 一个数据包数量为 N 的探测序列， 有 N-1 个间隔， 而同样要获得这么多的间隔， 一个数据包对的探测序列需要发送 2(N-1)个探测数据包。 并且， 通过呈指数变化的间隔， 获得范围为G1, G2探测速率， 只需要发送 log(G2)-log(G1)个数据包。 2）

29、 使用探测数据包的时延的相对差值进行测量， 不需要在发送主机和接收主机之间实现时钟同步。 3） 相比其他利用数据包对或者数据包序列的测量算法， 更好的利用了 延迟之间的关联关系， 具有更好的准确性。 4. 2 ITP 算法概述 首先， 我们给出端到端可用带宽的定义。 对于一条路径012,.nPa a aa= ( 源点为0a ， 依次经过节点121,.naaa,宿点为na ) 其中连接1ia到ia 的为链路i， 在时间点 a 和 b 之间， 进入链路 i 的流量( 包括探测流量和背景流量)为,iA a b 。 则我们将时间点 t -到 t 之 间 ，路 径 P 的 端 到 端 可 用 带 宽 定

30、 义 为 Bt- , t ，并 且,min(i)iiiiA tp tpB ttC+=， 其中，iC表示链路 i 的带宽，ip表示数据包从源主机达到链路 i 所需要的最短时间。 这里最短时间包括传播时延和传输时延。 而事实上， 数据包在传输过程中， 除了有传输时延和传播时延之外， 还有排队时延。 所以， 在时间,tt内发送的探测数据包到达路由器 i 时已在时间范围,iitp tp +之外， 并不能准确的测量,B tt。 但是， 如果 取一个较大的值( RTT )， 排队时延的影响就变得非常小了。 然后， 我们给出探测数据包序列的一些相关属性。 从源主机往目的主机发送若干分组序列 ( packet

31、 train )， 每个分组序列由若干数据包组成， 每个数据包的长度为 P，将每两个相邻的数据包时间间距的比值定义为分散因子( spread factor) 。 典型的探测数据包序列如图 3.4 所示。 将第 m 个序列中的第 k 个数据包的排队延迟表示为mkq ，第 k 个数据包和第 k + l 个数据包发送的时间间隔定义为mk ， 则发送第 k 个数据包时的瞬时流量/mmkkPP= 。 对于每一个数据包序列来说，mk 和mkP 都是相同的， 所以在以后的讨论中， 我们去掉它们的上标。 图 4.2 ITP 算法探测数据包序列图 ITP 算法利用排队延迟与时间关系的特征图(图 3.4)， 获得

32、对应于每一个数据包的可Probe packetsT /T =spread factorTime 用带宽(k)(k)1,mmB tt+ 的估计值(k)mE。 我们通过计算它们的平均值得到对应于每一个分组序列的带宽()(n)1,mmB tt 的估计值()mD 1()()111NkmmkkNkkE=D= 最后我们通过计算()mD的均值， 得到在时间段,tt之间端到端的可用带宽,B tt的估计 ,tt。 5 算法实现 5. 1 算法流程 ITP 算法使用 UDP 数据包来进行探测。 算法的参数包括: 数据包的大小 P， 衰减D的时间间隔。 测量过程中平均探测速率以及因子 F , 繁忙周期的阀值 L,

33、以及测量m探测速率的上、 下限值由用户制定。 ITP 算法通过调整探测序列之间的间隔来到达用户制定的探测速率均值。 下面， 我们通过伪码来表示 I T P 算法的实现细节。 Procedure estimate D(q) / *q 用来表示数据包的排队时延* / for( k = 1 t o N - 1 ) E k = 0 ; / * 初始化* / i =1 ; / * 目 前的数据包编号*/ 1 = N-1 ; / * N 为数据包的数量* / while (I = N - 1 ) qq+ if (1ii) j = excursion ( q , i , F , L ) choose case( j ) : case ( a ) : ( j i ) and ( J =