（计算机应用技术专业论文）在internet中确定瓶颈链路的算法研究.pdf

重庆邮电大学硕士论文 摘要 目前在l i n u x 操作系统下有一瓶颈链路定位工具p a t hn e c k ，该工具是 基于回归数据包队列算法的主动探测工具。本文通过分析该工具的源码， 并用d e l p h i 将重新编码移植到w i n d o w s 操作系统下，在中国电信a d s l 终端傲了大量的定位试验，试验结果表明，p a t hn e c k 的回归数据包队列算 法不能满足电信a d s l 终端用户的定位要求。 本文详细地阐述了回归数据包队列的算法思想，分析了p a t h n e c k 中回 归数据包队列的计算可用带宽的计算方法，发现了该计算方法在计算上存 在较大的误差。并在此基础上提出了该算法的两种改进算法。第一种改进 算法称为测量数据包优化算法，该算法将测量数据包的大小增加到负荷数 据包的大小，并重新设计了可用带宽计算方法。第二种改进算法称为负荷 数据包优化算法，该算法将负荷数据包的大小增大到原来的2 倍，运用原 来的计算方法计算，虽然在计算方法上同样存在误差，但是误差已经降低 到原来的一半，而且还可以继续增大负荷数据包的大小来降低计算误差。 本文将三种算法在中国电信a d s l 终端用户进行了大量的试验，试验表明 p a t hn e c k 不能满足中国电信a d s l 终端用户定位瓶颈链路位置的要求，测 量数据包优化算法能够满足中国电信a d s l 终端用户定位瓶颈链路位置的 要求，本文中的负荷数据包优化算法也不能满足中国电信a d s l 终端用户 的定位瓶颈链路位置的要求。 本文用d e l p h i 对三种算法进行了编码。成功地将l i n u x 操作系统下运 行的p a t hn e c k 移植到了w i n d o w s 操作系统下。该工具具有友好的用户交 互界面，能够实时地显示测试结果，分析处理交叉试验结果。并以柱形图 的形式显示出来 关键词：可用带宽，瓶颈带宽，瓶颈链路，回归数据包队列 重庆邮电大学硕士论文 a b s t r a c t ab o t t l e n e c k - l o c a t i n gt o o ln a m e dp a t hn e c kw h i c hi sb a s e san o v e l p r o b i n gt e c h n i q u ec a l l e dr e c u r s i v ep a c k e tt r a i n ( r p t ) i sap r o g r a mw h i c h r u ni nl i n u xo s t h i sp a p e ra n a l y s i st h ec o d eo fp a t hn e c k ，a n dr e c o d ew i t h d e l p h i i nw i n d o w so s an u m b e ro ft e s t so nt h ee n d - u s e r o fc h i n a t e l e c o m m u n i c a t i o n sa d s lh a v e b e e nd o n e t h eo u t c o m e so ft h e s et r i a l s j n d i c a t et h a tp a t hn e c kd o e s n tf i tt h ee n d - u s e ro fa d s l i nt h i sp a p e r ，w ed i s c u s s e dt h eb a s i ci d e ao fr e c u r s i v ep a c k e tt r a i ni n d e t a i la n dw ea n a l y z e dt h ec o m p u t i n gm e t h o d t h e nw ed i s c o v e r e dt h a ta l l e r r o ri si nt h ec o m p u t i n gm e t h o d t ot h ee r r o r ，w ep r o p o s e dt w ob e t t e r t e c h n i q u e s b a s e dr e c u r s i v ep a c k e tt r a i n t h ef i r s t t e c h n i q u ei s c a l l e d t e s t i n g - p a c k e t o p t i m i z e d s c h e m e ，i nt h i st e c h n i q u et h el e n g t ho f e a c ht e s t i n g p a c k e ti si n c r e a s e dt ot h el e n g t ho fal o a d i n gp a c k e t ，a n dw er e d e s i g n e dt h e c o m p u t i n gm e t h o d t h eo t h e ri sc a l l e dl o a d i n g - p a c k e t - o p t i m i z e d - s c h e m e ，i n t h i st e c h n i q u et h el e n g t ho fe a c hl o a d i n gp a c k e ti si n c r e a s e dt od o u b l et h e l e n g t ho fe a c hl o a d i n gp a c k e t i nt h i sp a p e r ，w ec o d et h et h r e er e c u r s i v e p a c k e tt r a i n si no n ep r o g r a mw i t hd e l p h ii nw i n d o w so s a n dw em a d ea n u m b e ro ft e s t so na d s le n d u s e r t h eo u t c o m e so ft h et e s t si n d i c a t e dt h a t t e s t i n g - p a c k e t o p t i m i z e d s c h e m ei sb e s tf i tt ot h ea d s le n d u s e r i n t h i sp a p e r ，u s i n gt h ei d e ao fo o ，w i t ht h ed e l p h iw ec o d e dt h et h r e e r p ti no n ep r o g r a mi nw i n d o w so s ，t h i sp r o g r a mh a saf r i e n d l yu s e r i n t e r f a c e 。i tc a nd i s p l a yt h eo u t c o m eo ft e s ti nt i m e ，i tc a na n a l y z et h e o u t c o m e so ft e s t sa n dd i s p l a yw i t hh i s t o g r a m k e yw o r d s ：a v a i l a b l eb a n d w i d t h ，b o t t l e n e c kb a n d w i d t h ，b o t t l e n e c kl i n k ， r e c u r s i v ep a c k e tt r a i n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及 取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论 文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重庆 邮虫太堂或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签名：璎犬毒 签字日期：加7 年多月孑日 学位论文版权使用授权书 本学位论文作者完全了解重庆邮电太堂有关保留、使用学位论 文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权重废整虫太堂可以将学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：玄犬毒 导师签名： 移剜寥 签字日期：砷 年月事日 签字日期：乒垆月p 1 1 研究背景 第一章绪论 在过去的2 0 年里，可用带宽( a v a i l a b l eb a n d w i d t h ) 作为网络路由、流量 工程、q o s 控制的一个关键参数，引起了学术界和工业界的广泛关注。目 前可用带宽的测量工具大部分是基于单数据包技术和包对包队列技术的， 但是这些工具的测量需要发送端和接收端相互配合才能进行测量，也即是 说这些工具需要发送端发送数据包到接收端，接收端通过接收来自发送端 的数据包来计算可用带宽。而一种名为p a t hn e c k 的新工具的出现，让发 送端向目的端发送数据包队列，但是发送端通过接收来自路径中各个存储 转发节点的i c m p 数据包来计算该路径的可用带宽，简化了端到端链路的 可用带宽测量的步骤，减少了参与测量的人员数，增加了测量的灵活性。 p a t hn e c k 可以测量选定的发送端到任何目的节点的可用带宽，该工具也可 以在测量可用带宽的同时，确定该路径的瓶颈带宽( b o t t l e n e c kb a n d w i d t h ) ， 而这种工具是基于回归数据包队列算法( r e c u r s i v ep a c k e t t r a i n ) 的。回归数 据包队列算法为我们提供了个人研究i n t e r n e t 网络路径可用带宽和瓶颈链 路定位算法的机会。 但是p a t hn e c k 并不一定适合所有的个人研究可用带宽和回归数据包 队列。其原因主要是；p a t h n e c k 是l i n u x 操作系统下的命令行工具，对 于目前大多数用户使用w i n d o w s 系列操作系统而言。这是一个比较大的障 碍：目前的p a t hn e c k 中的1 2 0 个u d p 数据包不适合重庆电信a d s l 终 端用户，经过大量的测试表明连续向目的节点发送1 2 0 个u d p 数据包， 会导致该u d p 数据包队列后面的几十个u d p 数据包会被丢弃：按照比 例将p a t hn e c k 中的1 2 0 个u d p 数据包缩减到8 0 个u d p 数据包时，丢包 率将会降低到5 以下，但是计算出的路径中各单链路的可用带宽呈递增 趋势；将p a t hn e c k 中的计算误差进行纠正，发现各单链路的可用带宽 仍然呈递增趋势。 根据，本文将p a t hn e c k 移植到了w i n d o w s 操作系统下；根据， 本文在设计w i n d o w s 下的定位工具的时候将1 2 0 个u d p 数据包缩减到了 8 0 个u d p 数据包；根据，本文通过分析p a t hn e c k 的源码。以及文献 【2 】【3 儿4 】，发现了p a t hn e c k 在理论上存在计算误差，根据修正该计算误差 后，路径中各单链路的可用带宽仍然呈递增趋势。 根据，本文在回归数据包队列算法的基础上提出了回归数据包队列 算法的两种改进算法，来提高路径中各单链路的可用带宽的精确度和瓶颈 链路定位的准确度。 1 2 可用带宽的研究历史 可用带宽( a v a i l a b l eb a n d w i d t h ) - - 词随着网络路由、流量工程、q o s 控 制的产生而出现。先介绍一下与可用带宽有关的一些基本概念。 在本文中路径( p a t h ) 是由从源节点到目的节点之间的一系列存储转 发节点组成。路径中相邻两个存储转发节点组成的被称为单链路( 1 i n k ) ， 路径是由若干相邻的单链路组成。单链路的带宽或容量( 本文通称为带宽) 指的是该链路上数据报文的最大传输速率。路径的带宽指的是该路径上数 据报文的最大传输速率，该值等于路径上所有单链路的最小带宽，被称为 路径的可用带宽或瓶颈带宽( 本文通称为瓶颈带宽b o t t l en e c k b a n d w i d t h ) 。在路径的所有单链路中带宽等于路径的带宽的单链路被称为 该路径的瓶颈链路( b o t t l e n e c kl i n k ) 。网络时延指的是从源节点发送数 据包到目的节点所需要的时间，网络时延由发送时延、传播时延和排队时 延三个部分组成，发送时延指的是源节点发送数据包所需要的时间，传播 时延指的是数据包在链路上传播所需要的时间，而数据包到达该链路中的 所有存储转发节点时，都要排队等待转发的时间，而排队时延就是该数据 包在所有的存储转发节点等待的时间之和。其中对于固定的链路而言传播 时延是固定的。发送时延根据源节点的性能而定，与源节点的c p u 、内存 和i o 等硬件设备有关，在本文中没有进行特殊说明的情况下，发送时延 和排队时延忽略不计。排队时延是一个变化的，无法估计的量，这与网络 的状态有关，当网络比较繁忙的时候，排队时延就长一些，网络空闲的时 候，排队时延就相对的短一些。 1 2 1 单数据包技术的出现 在早期的窄带宽的网络环境下，研究人员根据传输相同长度的数据 包，低速的链路传输的时间比高速的链路传输的时问长的原理，提出了单 数据包技术，该技术又称为可变大小数据包技术。该技术向网络发送大小 2 变化的探测数据包，并统计达到目的端的时延来计算该路径的可用带宽。 这类算法典型的工具有p a t h c h a r 2 5 ，p c h a r ，c l i n k 。 设一单链路的带宽为c ，一个大小为f 的数据包通过该单链路的时间为 f ，则 f 2 一c o a ) 根据i 1 式，单链路的带宽计算公式如下 c = 一i ( 1 2 ) t 设见是某条路径的可用带宽，p 为数据包的大小，是数据包通过该 链路的发送延迟和排队延迟，在此f 是一个固定的值，则该数据包从发送 开始到接收完毕的时间可以表示为 f = - - 。- p + t ( 1 3 ) 见 对该路径发送大小分别为p 和见的两个数据包，要求p 。 ，说明了在焉接收完第二个数据包的时 刻在转发完第一个数据包之前，也即是说尼转发第二个数据包的时刻就是 转发完第一个数据包的时刻。从式( 1 9 ) 得知胄：向目的节点转发第一个数 据包的时刻是岛，则目的节点接收完第一个节点的时刻应该为岛， ，一轰“： c l r ：接收完第二个数据包的时刻为t ；，该时刻表示为 ，：2 毒+ ，2 由州1 = ( 舌+ ，2 卜咯+ f 2 ) 2 署 。表示目的节点接收完第一个 4 数据包时，局没有接收完第二个数据包，即矗：在时刻，；转发第二个数据包。 则目的节点完全接收到第二个数据包的时刻t ：应该为 f ；= 晏+ f ； ( 1 1 3 ) 则目的节点接收到前后两个数据包的时间间隔为 a t = 一f ，= f ；一r 2 = 导 ( 1 1 4 ) 该时问间隔正好是瓶颈链路厶通过一个数据包的时间。 现假设r s r l r 2 r 。r 。是网络中的一条路径，其中b 是源节点，是 目的节点，马，r ：，月是按照先迸先出的排队等待机制的存储转发节 点。设c o 是单链路贾s r 。的带宽，c 。( 1 fs 万一1 ) 表示单链路置置+ 的带 宽，e 是单链路砖的带宽，则该路径的带宽c 可以表示为 c 2 卿q ( 1 1 5 ) 设“( o u 1 ) 是第f 条单链路的带宽利用率，则该单链路的空闲带宽 ( 即可用带宽) 4 = q x ( 1 - u , ) ，则该链路的可用带宽是 彳。m ，o i 2 4 。罂曾c , x ( 1 一玛) ( 1 1 6 ) 有m ( m 0 ) 个探测数据包，每个数据包的大小均为z ，第t ( 1 s ，拼) 个数 据包在第j ( 1 ，玎一1 ) 存储转发节点的等待转发的时间为酬，则每个数据 包通过该路径的时间为 ：咱= j - 薯i 。洲+ + 吉0 n 一il - o 其中。：分别表示数据包在发送端开始发送的时刻和接收端刚把此 数据包接收完毕的时刻。在式1 1 7 中f j 由该数据包在各个转发节点的排队 延迟和发送延迟组成。设发送端连续地将m 个大小均为，的数据包沿着该 链路发送到接收端，j 和t j , 分别表示第j 个存储转发节点接收完毕第f 个数 据包的时刻和发送完毕该数据包的时刻。 当册= 2 时，即数据包对，两个数据包发送的时间间隔应该为第一个数 据包被转发到第一个存储转发节点的时间 r o = f 2 i t i l = f 刍一f ：= i _ ( 1 1 8 ) 两个数据包在第一个存储转发节点被转发的时间间隔为 = f 之一，厶 ( i 1 9 ) 下面分成两种情况讨论。 第一种情况：第一个数据包已经被转发完毕，但第二个数据包还没有 被完全接收，那么此节点需要等待第二个数据包完全被接收才能进行转 发，所以该时间间隔应该为 a t i 础。玄 ( 1 工o ) 第二种情况：第一个数据包还没有或刚发送完毕的时候，第二个数据 包已经接收完毕，此时该时问间隔为 她2 玄 2 1 ) 根据式1 2 0 和式1 2 1 可以得到下式 她= 一喙， = 丽1 ：， 依此类推可以得到在第- ，个节点转发的时间间隔为 牛嬲白2 南 z ， 则接收端接收到两个数据包的时间间隔为 址刮控- - 1 1 22 雠l5 面矗( 1 2 4 ) 由式1 2 4 式可以计算得到该路径中最小的可用带宽 m i n 4 = ( 1 2 5 ) t - 0 月一l ， 根据式1 2 1 和式1 2 5 ，该路径的可用带宽可以表示为 彳：上 ( 1 2 6 ) f 。 当所 2 时，即数据包队列。第一个数据包和第聊个数据包在发送端发 送的时间间隔应该是相邻数据包的发送间隔之和，于是 ，互，石i = 伽- 1 ) x 百i ( 1 2 7 ) 以此类推，可以将所个数据包队列分成肼一1 个数据包对来处理，则在 各个存储转发节点的时间间隔应该为 6 r ，2 面( m - f 1 ) x l ( 1 2 8 ) 以此类推，可以求得在接收端收到第一个数据包与接收第m 个数据包 的时间间隔为 r ：a t 一i ：( m _ - 1 ) x - l ，晋哩，一， 以此类推，可以求得该路径的可用带宽表示为 一：( m - 1 ) x l a t 1 2 3 我国可用带宽的研究历史 ( 1 2 9 ) ( 1 3 0 ) 1 9 8 7 年9 月2 0 日，钱天自教授发出了第一封电子邮件，标志着我国 开始进入i n t e r n e t 世界。经过1 9 8 7 年到1 9 9 5 年这段萌芽阶段，i n t e r n e t 正 式在我国进行商业化运作。由于我国在i n t e m e t 的起步比较晚，在可用带 宽方面的研究也相对的较为落后，下图表示我国在1 9 9 5 年到2 0 0 6 年的可 用带宽的研究情况。 可用带墨嚣呈 学术关注度( 1 9 9 1 年2 。6 年) 眵 卜j ! 。 ： 年蚺二椭- 卿2 ：咖i 卅2 l “2 鸣一一确 l h2 一2 - 图1 2 我国学者在1 9 9 4 年到2 0 0 6 年对可用带宽测量的关注度曲线 而我国研究人员研究可用带宽的基本方法主要是采取模拟仿真的方 式，不能真实反映i n t e r n e t 网络路径中可用带宽的真实情况。 1 2 4 国外在瓶颈链路定位算法的研究现状 2 0 0 3 年1 2 月，n i n g n i n gh n 和p e t e rs t e e n k i s t e 在卡内基梅隆大学发 表了学术论文( r p t ：al o wo v e r h e a ds i n g l e e n dp r o b i n gt o o lf o rd e t e c t i n g 7 n e t w o r kc o n g e s t i o np o s i t i o n s ，提出了回归数据包队列算法( r e c u r s i v e p a c k e tt r a i n 简称r p t ) ，并在r p t 算法基础上用c 语言在l i n u x 操作系统 下编写了p a t hn e c k 瓶颈链路定位工具。在2 0 0 4 年和2 0 0 5 年相继发表了 学术论文【2 儿3 儿4 】。并对p a t hn e c k 工具进行改进升级，目前版本号为1 3 1 3 论文结构 本文一共分为5 章： 第一章：阐述了瓶颈链路定位算法的研究背景；可用带宽的研究历史， 对上述所提及的各种可用带宽测量技术的理论进行了详细的推导；介绍了 国内和国外的研究现状。 第二章：着重论述了回归数据包队列算法的基本思想，对其进行了详 细的理论推导。 第三章：分析定位工具p a t hn e c k 中计算各单链路的可用带宽计算公 式，讨论了该公式的计算误差：为了减少计算误差或消除误差分别提出了 负荷数据包优化改进算法和测量数据包优化改进算法；分别对两种改进算 法进行了误差分析。 第四章：用面向对象的思想对上述三种算法编码，把p a t h n e c k 从l i n u x 操作系统移植到w i n d o w s 系列操作系统下，同时实现了负荷数据包优化改 进算法和测量数据包优化改进算法。并编写了三种算法的交叉比较实验算 法。 第五章：在重庆电信a d s l 用户终端，通过第四章编写的工具进行了 大量实验，并对实验结果进行了分析，得出了结论，并对未来的研究提出 了新的方向。 3 第二章p a t hn e c k 工具中的回归数据包队列算法 2 1p a t hn e c k 工具简介 p a t hn e c k 是由美国电话电报公司( a t & t ) 和剑桥管理机构共同开发的 主动探测工具，该工具允许终端用户高效精确地确定i n t e r n e t 网络中的瓶 颈链路位置，为个人获知网络瓶颈链路位置提供了一种方法。由于该工具 是工作于l i n u x 操作系统之下，由c 语言编码完成的命令行工具，对使用 者的专业知识要求比较高，不仅要求用户会使用l i n u x 的命令，还必须了 解该工具的一些参数设置，这给一般终端用户使用带来了障碍本章将着 重讲述p a t hn e c k 运用的算法思想一一回归数据包队列算法。 2 2 回归数据包队列算法思想 2 2 1 有关的基本概念 设r s r i r ：r r 。( 其中b 表示源结点，如表示目的结点) 是一条 i n t e r n e t 路径。设c o 是单链路r s 马的可用带宽，c j ( 1 i s 万一1 ) 是单链路 与月m 的可用带宽，4 ( 1 i s 阼) 是路径如局蜀的可用带宽，由式1 1 5 有 由式2 1 ， 4 = m 甄c ， ( 2 1 ) 姑，鲥一l 。 。 彳m2 则2 q 2 m 洒( z 密。q ，c ) ( 2 2 ) a i + 1 = m i n ( a ，c ，) 4 ( 2 3 ) 由式2 3 ，得到 4 l 彳22 之4 2 4 + j2 以 ( 2 4 ) 咽喉链路( c h o k el i n k ) ：当4 一州时，则称r ，r j + l 为咽喉链路，同时存 储转发结点置为咽喉结点( c h o k ep o i n t ) 。图2 1 中l 2 和l 5 是咽喉链路。 其中r 2 和r 5 是咽喉结点。 瓶颈链路( b o t t l e n e c kl i n k ) ：在整个链路中最后一个咽喉链路就是瓶 9 颈链路。换句话说可用带宽变成最小的链路就是瓶颈链路。如图2 1 ，假 如该路径最后一条咽喉链路就是l 5 ，则l 5 就是瓶颈链路。 2 2 2 算法思想 图2 1 咽喉链路和瓶颈链路示意图 回归数据包队列算法( 简称r p t ) 是一个数据包队列，该数据包队列中 的数据包分为测量数据包( m e a s u r e m e n tp a c k e t s ) 和负荷数据包( 1 0 a d p a c k e t s ) 。测量数据包用于获取r p t 通过路径中某存储转发结点的时间和 该节点的信息的数据包；负荷数据包的大小在r p t 中占了近9 0 ，用于计 算各单链路的可用帮宽。 图2 2 是p a t hn e c k 工具r p t 的组成示意图，从图2 2 中可以看出， 该r p t 由三部分组成，第一部分是由3 0 个测量数据包组成，它们的生命 周期从1 到3 0 依次递增，每个数据包的大小为6 0 个字节，其作用是获取 该队列到达该链路中某个节点的时刻。第二部分由6 0 个负荷数据包组成， 每个数据包的生命周期为2 5 5 ，其目的是确保该数据包在传输过程中不被 存储转发节点丢弃：每个负荷数据包的大小为5 0 0 字节，用来计算各单链 路的可用带宽。第三部分由3 0 个测量数据包组成，它们的生命周期从3 0 到1 依次递减，其目的是为了获得该数据包队列通过该链路某节点的时刻， 其大小仍然为6 0 字节。 在i n t e r n c t 中每个存储转发节点都满足t c p i p 协议，当一个i p 数据 包到达一个存储转发节点后，该数据包的生命周期自动减l ，在存储转发 节点转发数据包时，首先检查该数据包的生命周期是否为o ，如果生命周 期为o ，存储转发节点将其丢掉，并向源节点返回一个i c m p 数据包。源 节点通过获取测量数据包被丢弃的i c m p 数据包来得知r p t 通过某存储转 发节点的时问。r p t 算法充分地利用了i n t e r n e t 网络的这一特点。如图2 2 所示的r p t 示意图，该数据包队列每通过网络中的一个存储转发，队列中 的每个数据包的生命周期都减l ，此时该队列中第一个测量数据包和最后 一个测量数据包的生命周期都为0 ，被存储转发节点丢弃，向源节点发送 两个i c m p 数据包。源节点通过接收前后两个数据包的时刻之差，就是该 1 0 队列通过该存储转发节点的时间。 t t l 从1 到3 0 的 测量数据包，功 能就是获得数据 包欧列到达某个 结点的时刻，大 小为6 0 字节 6 0 个t t l 为2 5 5 的负荷数 据包，目的测量通过某结点 的可用带宽，大小为5 0 0 字节 t t l 从3 0 到l 的 测量数据包，功能 就是获得数据包 队列完全通过某 个结点的时刻，大 小为6 0 字节 图2 2p a t hn e c k 中r p t 数据包队列的组成示意图 在r p t 中前3 0 个测量数据包的目的就是在数据包队列到达某个节点 的向下一个存储转发节点转发时向源节点发送i c m p 数据包，源节点记录 下接收到i c m p 数据包的时刻，通过解析i c m p 数据包可以记录到达节点 的i p 地址；后3 0 个测量数据包的目的就是在数据包队列完全通过某个节 点时向源节点发送i c m p 数据包，源节点记录接收到i c m p 数据包的时刻， 通过解析记录该数据包获得通过该节点的i p 地址，通过查找该节点的到达 时刻，将两个数据包到达源节点的时刻相减就获得了该数据包队列通过该 节点的时问，由于该队列的大小是可知的，因此就可以通过式1 2 8 计算获 得该节点所在单链路的可用带宽。 图2 3 是一个r p t 通过一个节点的示意图，其中粉黄色的表示负荷数 据包，而蓝色的表示的是测量数据包，绿色表示存储转发节点向源节点发 送的i c m p 数据包。 在图2 3 中，“s e n d e r ”是源节点，从源节点s e n d e r 发送出一个数据包 队列，该队列由黄色的负荷数据包和蓝色的测量数据包组成。第一层图中 表示从源节点“s e n d e r ”向“r o u t e r ”发送该数据包队列，第二层表示的是在t 时刻，第一个蓝色的测量数据包到达“r o u t e r ”时，该数据包被“r o u t e r ”丢弃， 并向源节点“s e n d e r ”返回一个绿色的i c m p 数据包。在该图的第三层， “s e n d e r ”在，：时刻接收到从“r o u t e r ”返回的绿色的i c m p 数据包。在图的第 四层，“r o u t e r ”在，时刻接收到该队列最后一个绿色的测量数据包，该数 据包被丢弃，并向源节点“s e n d e r ”返回一个i c m p 数据包第五层，“s e n d e r ” 在t i 时刻接收到第二个i c m p 数据包。 图2 3r p t 通过存储转发节点示意图 图2 3 中我们看到每当数据包队列通过一个存储转发结点的时候，该 节点都会抛弃第一个数据包和最后一个数据包，而抛弃这两个数据包的原 因是该测量数据包而且生命周期为0 。存储转发结点在抛弃每个数据包时， 同时也会向源结点发送一个i c m p 数据包，向源节点报告这该数据包的生 命周期已经为0 ，不能继续向下一个节点转发，同时i c m p 数据包中包含 有i c m p 数据包产生的原因和产生该数据包的存储转发节点信息。在图2 3 中存储转发结点“r o u t e r ”发送两个i c m p 数据包的时刻分别为，和 ，源节 点“s e n d e r ”收到两个i c m p 数据包的时刻为t ：和t ：，假设同一个存储转发节 点向源节点发送i c m p 数据包，i c m p 数据包从该节点到达源节点所需要 的时间是一个固定值，则有源节点接收同一个节点的i c m p 数据包的时间 间隔就是源节点发送两个i c m p 数据包的时间间隔，即 t 2 一t 1 = t 2 一t i ( 2 5 ) 尽管无法获得该存储转发节点“r o u t e r ”发送i c m p 数据包的时刻，但 是可以通过源节点获得接收到该i c m p 的时刻，所以将该数据包队列通过 该结点的时间由源节点接收到i c m p 来获得，即f = 一t ：。由于这个时间是 r p t 通过该结点的时间，同时该r p t 的大小已知，不妨设r p t 的大小为， 根据式1 2 得可用带宽 4 ：一l ：。_ 。( 2 6 ) t r 2 一t i 以此类推，可以求得r p t 经过任何一条单链路的时间，也即是说可以 通过式2 6 计算出路径中任何一条单链路的可用带宽。 图2 4 是r p t 在一i n t e r n e t 路径上的传输示意图，该图说明r p t 在经 过咽喉节点后，该队列由于咽喉链路的可用带宽小而导致了该队列在该咽 喉链路上传输的时间变长。 图2 4r p t 传输过程示意图 从图2 4 中可以看出，r 2 是咽喉节点，从源节点s 到存储转发节点 r 1 的过程中，r p t 中的每个数据包的生命周期都减了1 当r l 向r 2 转发 时，生命周期为0 的两个数据包被丢掉，并向源节点s 发送了i c m p 数据 包，而被丢掉的两个数据包位于该r p t 的首位和末位当r p t 到达r 2 后， r p t 中的数据包没有间隔，在r 2 向r 3 转发该r p t 时，所有数据包的生命 周期都减去1 ，同时生命周期为o 的被丢弃，向源节点发送i c m p 数据包。 在r 2 向r 3 转发r p t 的过程中，数据包之间产生了空闲，也即是说数据包 之间发生了分离，也就是说由于r 2 与r 3 之间的可用带宽比较小，导致了 传输该r p t 的时间增长了，这样通过源节点获得的i c m p 数据包信息可以 得知r 2 是该链路的一个咽喉节点，以此类推，可以获碍该链路的所有咽 喉节点，而最后一个咽喉节点就是瓶颈节点，该节点对应的链路就是瓶颈 链路。 2 3p a t hn e c k 在l i n u x 操作系统下的实现 p a t hn e c k 是用基于面向过程的c 语言开发的l i n u x 操作系统下的瓶颈 链路定位工具。下文将分析p a t hn e c k 中r p t 的组成，可用带宽的计算， 以及如何运用t c p i p 协议族中的u d p 协议来实现。 2 3 1 回归数据包队列的组成 p a t hn e c k 中的r p t 含有1 2 0 个u d p 数据包，共分成三个部分，如图 2 2 所示。第一部分是由3 0 个测量数据包组成，测量数据包的大小为6 0 字节，测量数据包的生命周期按顺序依次从l 到3 0 递增。第二部分由6 0 个负荷数据包组成，每个数据包的大小是5 0 0 字节，生命周期为2 5 5 。第 三部分由3 0 个测量数据包组成，每个数据包的大小为6 0 字节，生命周期 从3 0 到1 递减。 ， 2 3 2 可用带宽的计算 如图2 2 所示，在p a t hn e c k 中，由于测量数据包的总量占r p t 总量 的l o ，并且这个比例随着r p t 的传输而减小，因此测量数据包在单链 路可用带宽的计算中被忽略不计。设r p t 的大小为厶，测量数据包的大小 为o ，负荷数据包的大小为三，。其中负荷数据包在传输过程中该数据包 不会被丢弃，其大小是固定的，即l ，= 5 0 0 x 6 0 = 3 0 0 0 0 。测量数据包每经过 一个存储转发节点，测量数据包数目就减少了2 个，总量减少了1 2 0 字节。 则测量数据包的大小可以用一个函数来表示，即 1 4 上m ( f ) = 6 0 x ( 6 0 2 x f ) = 3 6 0 0 1 2 0 i( 2 7 ) 其中i = 1 , 2 ，3 ，3 0 。 r p t 的大小厶表示为负荷数据包的大小l 和测量数据包的大小“之 和，但是在p a t hn e c k 中，测量数据包的大小在r p t 中的大小的比例为 2 等2 彘 p e r u ( 牡若格= 厕3 6 0 0 - 1 2 0 i p e r u ( i ) = 器 ( 2 8 ) 其中i = 1 , 2 ，3 ，3 0 。测量数据包在r p t 中所占比例随着经过的存储转 发节点的增多而减少，因此在可用带宽的计算中不把测量数据包包括在 内，即r p t 的大小厶就等于负荷数据包的大小钆。 设该r p t 经过测试路径中某个存储转发节点冠的时间由式2 5 计算得 到，即源节点接收到存储转发节点尺先后发回的两个i c m p 数据包的时间 间隔。设a t i ，纽2 ，a t 。表示r p t 分别经过存储转发节点蜀，如，r 。的时间， 由式2 6 可以计算出各路径r s r , 0 s j s 片$ 3 0 ) 的可用带宽 4 ：上：3 0 0 0 0( 2 9 ) a = 一= 一 z 9j l tl t 根据式2 9 ，在数据包队列总大小不变的情况下，可用带宽与所经过 的时间成反比，由式2 4 得到 a t is a t 2s s 馘 ( 2 1 0 ) 从式2 1 0 中可以看出，当a t ， a t ， a t 。，与公式2 5 相反，因此r p t 不能由t c p 来实现。 u d p 协议是i p 协议族的非面向连接的协议，在传输过程中发送端不 考虑接收端是否能收到正确的数据，同时也不知道数据包通过哪条链路到 达接收端，如图2 6 。 从图2 6 中可以看出u d p 协议在传输过程中不顾及该包是否正确到达 接收端，而发送端则只管向网络中发送数据包。而连续发送两个数据包的 时间间隔就是第一个数据包在发送端的发送时间间隔( 假设该发送端的发 1 6 送速度是i nk b p s ，每个数据包的大小均为p 字节，则相邻数据包的发送时 间间隔是昌黑j ：旦竺，椰) ，即两个数据包在发送的时候没有任何时间 m l u u um 间隔。在这里假设u d p 数据包沿着同一链路到达接收端，那么就能够满 足r p t 算法的要求。但是实际上u d p 数据包的传输路径是根据路由表来 决定的。因此在较短的时间内，如果网络流量分布不发生显著变化的话， 各个存储转发节点的路由表不会发生变化，也就是说u d p 数据包的传输 路径在较短的时间内发生改变的可能性较小。因此一个r p t 队列中的大部 分数据包将通过同一条路径到达目的节点。 发送端 接收端 图2 6u d p 传输数据示意图 通过中国电信的a d s l 用户终端分别向w w w v 1 2 6 c o m 、w w w c s d n n e t 和w w w q q c o m 发送生命周期从1 递增的u d p 数据包，通过接收i c m p 数据包获得该路径上的所有节点信息，从而获得从a d s l 终端到三个地址 的链路，经过4 天断断续续的测试，a d s l 终端到w w w 1 2 6 c o r n 和 w w w q q c o r n 的路径改变的周期比较长，大概为1 2 个小时到2 4 个小时之 间，而到w w w c s d n n e t 的路径的改变周期则较短，大概是1 0 分钟到1 5 分 钟之间。也就是说在a d s l 终端到w w w c s d n n e t 的路径改变的周期大于1 0 分钟。而对于测试次r p t 算法所需要的时阅不会超过2 秒。于是u d p 协议能够实现r p t 算法，而p a t hn e c k 工具也正是运用t c p i p 协议族中 的u d p 协议实现其算法的。 1 7 2 4w i n d o w s 操作系统下p a t hn e c k 对p a t hn e c k 的c 语言源码进行深入的分析后，在w i n d o w s 操作系统 中，用d e l p h i 开发工具，运用面向对象的思想将其重新编码，将p a t hn e c k 移植到了w i n d o w s 操作系统下。该软件拥有友好的与用户交互的界面，实 时地将测试过程显示在界面上，以表格的形式显示测试数据。以柱形图的 形式显示分析结果。 2 5p a t hn e c k 的试验结果 通过对p a t hn e c k 源码的分析，将其移植到w i n d o w s 操作系统，在中 国电信a d s l 终端对其做了大量的试验发现了如下问题： 1 、按照图2 2 所示的r p t 发送a d s l 用户终端不能获得r p t 通过 路径中的各存储节点的时间。其原因是a d s l 用户终端只能接收到来自 r p t 前3 0 个测量数据包的i c m p 数据包，而无法接收到r p t 中后3 0 个测 量数据包的i c m p 数据包。 2 、通过将r p t 按比例减少，将由1 2 0 个数据包组成的r p t 变成了由 8 0 个数据包组成的r p t 后，其中r p t 同样由3 部分组成：第一部分是2 0 个测量数据包，大小为6 0 字节，生命周期从1 到3 0 递增；第二部分由4 0 个负荷数据包组成，大小为5 0 0 字节，生命周期为2 5 5 ：第三部分由2 0 个 测量数据包组成，大小为6 0 字节，生命周期从3 0 到1 递减。a d s l 用户 终端发送这样的r p t 后能够接收到9 5 以上的i c m p 数据包，经过试验 发现r p t 通过存储转发节点的时间呈现递增的趋势，这与式2 1 0 相反。 3 、在试验过程中发现，a d s l 用户终端接收到的第一个i c m p 数据包 通常情况下不是路径中第一个存储转发节点返回的。 重庆邮电大学硕士论文第三章回归数据包队列算法的优化方案 3 1 引言 第三章回归数据包队列算法的优化方案 通过将l i n u x 环境下的p a t hn e c k 移植到w i n d o w s 环境下后，并对其 做了大量的试验，发现了2 5 节中的l 和2 两个问题。在带宽为l m b p s 的 电信a d s l 用户终端对w w w 1 2 6 。c o m ，w w w q q t o m 和w w w c s d n n e t 三个 网站进行了测试。对三个网站分别测试了3 0 0 次。测试的结果发现了可用 带宽沿着链路呈现递增的趋势，超过9 0 的瓶颈节点在第一个或第二个存 储转发节点处，不到1 0 的瓶颈节点在第三个节点以后，如图3 1 。 图3 1w i n d o w s 下的p a t hn e c k 测试结果 图3 1 中红色的柱形图表示的是对目的节点w w w 1 2 6 t o m 做的1 0 0 次 瓶颈链路定位试验的柱形图，其中第一个和第二个存储转发节点作为瓶颈 节点的次数接近9 0 次，而最后一个节点作为瓶颈节点的次数为0 。 经过分析可用带宽的计算后发现，在p a t hn e c k 的计算中存在误差。 1 9 重庆邮电大学硕士论文 第三章回归数据包队列算法的优化方案 于是通过对p a t hn e c k 工具中的r p t 算法的误差率的分析，该算法中计算 可用带宽的误差在第一个节点时超过了1 0 ，虽然这个误差随着链路节点 的增多而减少，但是这样造成了瓶颈链路的前驱性。在窄带宽网络环境下， 网络的处理能力比较差，在链路中单链路之间的可用带宽之差的比例比较 大，尽管可用带宽的误差达到1 0 ，但对瓶颈链路位置的定位造成的影响 较小，但是在高带宽的环境下，每条链路的可用带宽之差占可用带宽的比 例比较小，但是误差