（计算数学专业论文）计算机通讯网络中的qos算法研究.pdf

摘要 在当代的计算机通讯网络中，随着网络数据业务的不断扩大，由于在传统意 义上的尽力而为服务已经不能满足越来越多的业务需求的要求，这样，为客户提 供保质保量的服务已经是网络服务的一个客观要求。近年来，有关计算机网络的 q o s 算法逐渐成为各个路由器厂商以及科研机构研究的热点，本文则分析了目前 的计算机网的q o s 算法的有关成果，剖析其优缺点，在此基础上对这些算法有机 的结合和进一步改进和推广，得到了比较满意数值结果，而且实验证明算法是有 效的。本文的详细内容如下： 1 建立了基于t c p i p 的适应q o s 要求数据传输的计算机网络数学模型，从 而完成对当代网络的数据传输比较详细的q o s 参数化过程，给出了基于全光纤网 络的数学模型，还从理论上分析了适应q o s 的光纤网络的物理连接度的问题； 2 为了克服常用s p t 问题算法的对单一度量的依赖，建立了向量比较的有关 的概念，给出了基于遗传算法和计算s p t 问题的动态b a s i c 算法的q o s 路由问题， 并分别给出了相关的计算复杂度； 3 给出了保证q o s 路由算法的网络资源管理算法，并重点给出了在加权公平 意义下的队列的数据传输的全局抖动最小算法。 4 最后给出了有关算法的数值实验结果，并对算法模拟与设计提出了一些有 用的建议及实现方法。 关键词：计算机网络q o s 路由遗传算法( g a )b a s i c 算法 加权公平队列抖动 些塑坠竖 m a s t e r d e g r e e d i s s e n a t i o n t h e a l g o r i m m s o f q o s f o rt h ec o m p u t e rc o n u n u n i c a t i o nn e t w o r k s d o n g j i a n r n i n d i r e c t e db y x i n gz h i d o n g d 印a n m e m o f m a t i l e m a t i c s ，n o n h w e s tu n i v e r s i 劬x i a i l7 1 0 0 6 9 a b s t r a c t i nt l l ec o n t e m p o r a r yc o m p u t e rc o m m u n i c a t i o nn e t w o r k s ， 、i t l lc o n t i n u o u s e x p a n d a b i l i t yo fm en e t w o r k sd a t ab u s i n e s s ，i ti s1 1 e c c e s a r ya n do b j e c t i v ef o rt h e c l i e n t st o p r o v i d e t o g u a r a n t e e b o t l l q u a l i t y a n d q u a n t i t y s e r v i c eb e c a u s et l l e n a d i t i o n a ls e r v i c ew h i c hi sc h a r a c t e r db v “b e s to fe f i - o r t s ”h a i m o tb e e na b l et o s a t i s f i e dt l l em o r ea i l dm o r eb u s i n e s ss e n r i c ed e m a i l d s i nr e c e n t ”a r s ，a l g o r i m m so f q u a l i t yo fs e i c e ( q o s ) i n 也ec o m p u t e rn e t w o r k sh 搜b e e nf o c l l s e db ym a i l yr o u t e r f a c t o r i e sa s 、e 1 1 髂s o m ei n s t i t i l d e ss t e pb ys t e p t l l i sp a p e ra n a l 朔他ds o m er e l e v a n t r e s u l t so f 也eq o sa l g o r i 也m sa r ds t u d i e d 也e i ra d v a n t a g e sa r dd i s a d v a n t a g e s ，n e w a 1 2 0 r i m m sa r ep r e s e n t e d ，w h i c ha r cb a s e do nt 1 1 ec o m b i n a t i o no ft h ep a s ta 1 卫。一m m s w i t l lm ef 曲m l e ri m p r o v e m 啪a n de x p a n s i o i 啦l s o ，t 1 1 e yh a v eb e e np r o v e dv a l i da n d e 历c i e n tb ym en m e r i c a lr e s u l t s d e 协i l so f t h ep a p e ra sf o l l o w s ： 1 e s t a b l i s han e t 、v o d 岱m o d e lb 船eo nt l l et c m p p r o t o c o l s ，枷c hi sa d a p t c dt o d a t at 瑚吼s m i s s i o no f q o sa 1 1 dc o m p l e t eq o sq u a n t i z a t i o np r o c e s so f t l l er l e t 、v o r l ( sa t t l l es 栅et i m e a l s o ，t h em o d e lo f a l l 丘b c r o p t i cn e t 、v o r k si sg i v c na i l dm ed r o b l e mo f p h y s i c sl i r l l ( d e 霉婶ea b o u ti ti sm e o r e t i c a l l ya 1 1 a l y z e d 2 e s t a _ b l i s hc o m p a r a t i v er c l a t i o ns h i pb e “怕e n v e c t o r st oo v e r c o m et i l e c o i m o ns p t a l g o r i m mw l l i c hd 印e n e do nas i n g l em e 硒u r e m e n t ，t w oq o sr o u t i n g a l g o r i m m 、v i t l lt h e i rr e s p e 宅t i v ec o m p l e xa r cg i v e i l w h j c hi sb a s e do nm eg e n i c a l g o r i t l l ma i l dt l l eo t l l e ro nm ed y l l 蛐i cb 鹊i ca l g o r i m m 3 r e s o u r c em a i l a g e m e n t a l g o r i m mo fg i l 跏t e eq o sm u t i n gi sg i v e n ，w 1 i c hh a s p m p o s e dan e wa l g o r i m m 、v i m 斟o a lm i i l i m mj i 壮e r 岫d e rt l l ew e i 曲t e d 黼rq u e u e 4 t h ee x p e r i r i l e mr e s u l t sf o rs o m ea l g o r i t l l ma r eg i v e na sw e l la ss o m eu s e 如l a d v i s eo nt h ei e a l i 段i t i o no f t h e ma r ep r o p o s e d k e y w o r d s ：c o m p u t e r n e t w o r k s q o sr o u t i n g g e n i c a l g o m h m ( g a ) b 嬲i c a l g o r i t l l mw e i g h t e d f a i rq u e u ej m e r 独创性声明 本人声明所呈交的学位论文是本人在导师的指导下进行的研究工作及取得 的研究成果。据我所知，除了文中特别加以标注和致谢的内容外，本论文不包含 其他人已发表或撰写的研究成果，也不包含为获得妥琵嵫或其它教育机 构的学位和证书而使用过的材料。与我一起工作的同志对本研究所做的贡献已在 论文中作了明确的说明并表示谢意。 学位论文作者签名：应翟臣 签名日期：塞丛年上月胆目 堕韭查堂堡主兰竺堡兰一 第一章引言 本章主要介绍i pq o s 技术产生的背景、i pq o s 的研究现状、i pq o s 的解决 方案及研究方法，最后指出了本文研究内容和安排 1 1 i p0 0 s 技术产生的背景 随着国际互联网i n t e r n e t 的快速发展，网络功能逐渐的从单一走向多样化， 其作用也从简单的信息发送发展到远程教学、视频会议、数据分发和网络游戏等 等。正是这些网络应用的不断增加使得当代计算机网络已经发展成为一个多样性 的数据传输媒体，伴随着不同业务的增加，使得对其数据传输提出了更高的要求。 由于传统的i p 网络只是提供“尽力而为”的数据传输能力，远远不能满足提供 给企业所需要的且已经在其专用网络中的可靠性和稳定性。而商业客户在其安全 性、可测性、可量性等方面得到保证之前，还不可把关键业务的数据、语言和多 媒体应用放在公用的i p 网络上，i pq o s 就是在这些情况下产生的。 i pq o s 是指i p 网络的服务质量，是数据通过网络时的性能，它的目的就是 向用户提供端到端的服务质量保证有自己的质量指标，包括业务的可用性、可 变延迟、吞吐量和丢包率。i pq o s 在可预测、可测量性方面比传统i p 有了很大 的提高，而且它的使用带来了更高效的带宽使用效率和商业机会。 随着网络上主机数量的不断增加，网络服务的需求将超过网络提供的能力， 从而会造成传输时延的变化( 抖动) 、传输时延迟过大会引起分组丢失，出现网 络拥塞，网络拥塞对一些i n t e r n e t 应用( 如电子邮件，文件传输和w e b 应用) 一般不会造成很大的影响，但是对于传输要求比较苛刻的实时应用( 比如多媒体 业务) 及大多数双向通信业务( 如电话业务) 却不能容忍。 当然，我们可以通过增加网络带宽来缓解拥塞，但是这样做不能消除拥塞。 当两条容量极高的光缆汇集到第三条光缆时仍会造成拥塞。此外，由于交换机和 路由器的接口速率与网络带宽相比仍然很低，于是当数据到达接口的速率超过转 发的速率时，拥塞也会发生，并且需要大带宽的新业务不断地涌现，当这些业务 量猛增的时候，拥塞将是难以避免。甚至在负载相对较轻的时候的i p 网络上传 输延迟也能积累到影响实时应用的程度。为了在i n t e r n e t 上提供有质量保证的 服务，必须制定有关服务数量和服务质量水平的规定。规定中需要在网络方面增 西北大学硕士学位论文 加一些协议，对具有严格时延要求的业务和能够容忍延迟、抖动和分组丢失的业 务进行处理，这就是q o s 机制的职责。也就是说，i pq o s 机制不是用来增加网 络带宽，而是通过优化的使用和管理网络资源使其尽可能地满足数据业务的需 要。总之，i pq o s 要求我们从现有的网络资源入手，通过调整带宽和路由来最 大程度的满足一定服务质量的数据业务。 正是由于诸如上面所描述的，使得i pq o s 的研究成为当前业内研究和关注 的热点，特别是网络多媒体的研究，见文献( 6 ) ( 7 ) 。 1 2 i p0 0 s 的研究现状 由于i pq o s 的应用前景十分广泛，也必然成为下一代网络的发展趋势，但 总体上来说，i pq o s 的研究还未成熟，只是一个人们关注的焦点，因此还未成 为一个统一的标准。就世界范围而言，不同的单位或组织提出了自己对i pq o s 的认知及研究成果。下面列出的便是i pq o s 研究的几个代表机构： ( 1 ) i b m 公司的h e i d e l k e gq o s 模型； ( 2 ) 美国哥伦比亚大学c o m e t 研究组提出的x r m 模型： ( 3 ) 美国宾夕法尼亚大学的o m e g a 体系结构模型： ( 4 ) 加利福尼亚大学伯克利分校的t e n e t 模型； ( 5 ) i e t f 工作组提出的集成业务体系结构( i n t s e r v ) 和区分业务体系结构 ( d i f f s e r v ) 。 在上面所列举的研究机构中，i e t f 则是最早关注i pq o s 的，而且其研究成 果也是比较著名的。下面是i e t f 工作组的主要研究成果。 i n t s e r v r s v p 是i e t f 工作组于1 9 9 4 年提出的，主要有两部分组成： 流量控制：它包括接纳控制、分类器和包调度等； 建立信路协议：即资源调度协议。 但是，i n t s e r v 存在主要三方面的问题( 2 7 ) ： 1 展性不够好： 2 对路由器要求比较高，实现复杂； 3 不适用于业务量较小的流。 而区分服务模型( d i f f s e r v ) 在一定程度上克服了集成服务( i n t s e r v ) 的缺 西北大学硕士学位论文 点，并且仍然保持了把流分类、类问按准则共享、类内平等共享的原则，在文献 ( 2 7 ) 指出i n t s e r v 存在以下问题： 如何向用户提供有数量等级区别的不同性能的服务； 它存在组播实现较复杂的问题： 存在同一流之间聚集中各微流之间的公平性问题； 对预流操作i n t s e r v 缺乏相应的身份验证和授权机制，使网络可能受到攻击， 因而存在安全性问题。 通过以上的分析可知，要考虑基于数据流的q o s 算法，就必须处理好以下 的几个问题： 1 如何在算法或实现途径上解决数据流数目巨大的存储开销； 2 数据流状态信息的量化描述： 3 相同性质数据流之间的优先级问题： 4 在上述情形下，各种路由算法的实现。 1 3 i p0 0 s 的研究方法和解决方案 通过前面的分析，笔者认为要研究i pq o s 问题，即必须要解决好以下的几 个问题： q o s 的量化问题，即q o s 量化指标( 将服务质量与网络传输过程中的参数结 合起来) ： q o s 问题的分类及量化后对服务按照某种标准加以分类，这是更好的提高网 络资源的利用问题。 网络中流的数学模型化问题： 路由算法的解决方案； q o s 在实现过程中，网络资源的管理和抖动的控制问题； 通常，q o s 的量化主要从呼叫与连接建立的速度( 延迟尺度) 和网络数据的传 送速度( 吞吐量尺度) 的两个方面考虑；q o s 的分类从数据流属性上划分为确定型 ( d e t e 硼i n i s t i c ) 、统计型( s t a t i s t i c a l ) 、实时服务型( r e a 卜t i m e ) 、尽全力 型( b e 乩一e f f o r t ) 这四个方面考虑。这样，终端主机、链路、交换机路由器 等网络元素的特性，通过延迟和吞吐量的尺度，共同决定了提供给应用程序的服 西北大学硬士学位论义 务质量。而从服务质量的实现层次来分类时主要表现为物理网络层、i p 层、应 用层三个方面来考虑的。 而本文则是在考虑到了网络的物理层的q o s 实现以后，从网络i p 层出发， 在网络资源的管理和抖动控制方面，则采用数学方法，包括带宽资源、缓冲区资 源等等；同时流的量化细节及q o s 路由算法将在本文的后面各章具体加以讨论， 特别是对q o s 路由算法加以讨论。 1 ，4 本文的研究内容和安排 本文则是以面向应用网络的数据流为基础，对网络以及网络中的数据流进 行了量化与其数学模型的描述、针对目前的网络提出了基于数据流的q o s 的路 由算法，包括q o s 资源管理算法和保证网络数据流q o s 服务的抖动控制算法， 而笔者在讨论了以上的几个算法中，充分考虑了实际应用网络中必须注意的单 播和多搔问题，并给出了实际的数据模拟试验，结果证明这些算法是正确的和 有效的。基予以上的内容，本文的结构如下： 第一章介绍了i pq o s 问题提出的背景、应用、研究方法以及本文的结构 安排； 第二章首先将网络中的流加以抽象和量化，荠提出面向应用的现代网络的 数学模型，且给出该模型的评价： 第三章给出q o s 的路由算法，包括单播路由算法和多播路由算法； 第四章分别给出基于q o s 资源管理算法和保证q o s 的抖动控制； 第五章给出上述各个算法的数值模拟： 西北大学硕士学位论文 第二章保证业务q o s 的当代数据流网络模型 本章首先介绍并给出了当代网络中流的抽象定义，接着给出它的数学模型的 描述，最后给出了对于该模型的分析和应注意的问题。 2 1 当代网络中流的定义、分类和量化 一、基本概念 在通常我们所接触的流的定义中，流一般被抽象地描述成按照一定的序列， 连续移动的物质。而在当代的流网络中，网络中不断地传输着的数据包或数据报 文也可以看成是数据流。而这些数据包是从它的源地址流向目的地址的现象，被 称为是数据流，简称流。具体地说来，可以从以下方面加以考虑： 定义l 网络中的流：指在当代网络中，以数据包或数据报文为基本单位，它们 在发送端和接收端相互定向动态转移，便称之为数据包流，简称数据流或流。 实际上，我们以二进制表示当代网络中的数据时，把这些数据流相应的称为比 特( b i t ) 流。而现实中当代网络中的数据进行网络操作时，比如说传输( 物理传 输) ，它们都是以比特为基础的。这里，为了研究的方便性和现实性，我们以数 据包或数据报文为基础进行研究是基于以下考虑的： ( 1 ) 数据在网络中的交换在实质上是可以用数据包交换来衡量的； ( 2 ) 数据包表示的数据流可以转化为比特流来考虑。 ( 3 ) 数据包表示的数据流在实验的模拟环境中便于测量，即为实验的测量提供 了一个数据接口。 二、流的分类 从应用的角度考虑，在流的分类中，既不能分的太细而导致问题的复杂化， 但又不能太粗，致使很多不同性质的流之间不具有广泛的共性，从而使问题的研 究与实际问题相差甚远。基于以上的考虑，在本文的研究中将流大致可以分为以 下几类： a ) w e b 流 w e b 流在实际中又可称为突发流。因为该流是在某些偶然或不确定因素下， 由某个事件驱动，一般是主机到客户机之间的数据通信，而且往往在性质上是单 向的，而在数量上是少量的，而且它几乎对传输延迟不做要求，可在瞬时终止传 输。它在数学的表现形式上，呈现离散的贝努力分布。在现实网络中，包括我们 经常使用的电子邮件的数据传输属于w e b 流。 b ) 文件流 文件流在数据的传输过程中，对延迟要求不高，但对数据传输的正确性要求最 高即不容许有任何的传输差错，比如在现实网络中，以f t p 协议为主的文 件传输数据流，这类文件数据传输的任何错误，都将会导致文件传输的失败或使 文件的传输毫无意义。 c ) 实时数据流 这类数据流对数据传输的延迟特别敏感，但对数据的流量要求较低，但同样不 容许有任何差错。比如现实网络中的远程医疗数据流、股票数据流以及在战争中 雷达发现异常情况到作出反应的数据交换，都属于实时数据流。 d ) 多媒体流 在这里大多表现为两种情形：一种为音频数据流；一种为多媒体的音频和视频 数据共同构成的多媒体视频流，这两种现实中的数据流都具有多媒体流的共性， 西北大学硕士学位论文 那就是：对在数据传输过程中，延迟的要求很高，而且数据流量也很大。总之， 这类数据流对延迟较为敏感，但对差错没有实时流要求那么严格。这类流上前主 要表现为远程视频会议、网上电视转播及v o d ( 视频点播) 产生的流。 三、分类的现实性 实际上，由于目前计算机网络的连接是基于t c p i p 的，而在该协议中，不 妨用数据包中的报头的两个二进制位来表示该四类流，称之为1 o s 字段( t y p e o fs e r v i c e ) p 2 p ip ot 3 t 2t l lt 0 c u 详细参见r f c i e t f 规定的r 0 s 字节。比如说我们用 0 0 0 11 01 1 w e b 流文件流实时流多媒体流 因此我们只需借用数据包头的未用的t o s 字段的两个二进制位就可以很容易 的实现。 2 2 网络模型的建立 一、引言 在目前笔者所见到的很多文献中如( 5 5 ) 几乎所有的研究人员都把网络应用 的稳定性归结为其建立网络模型的相关算法上，从而忽略了网络的应用属性，事 实上，不管研究者对网络模型的如何研究和考虑，它无非都是以满足当前不断增 加的网络应用，也就是说网络模型的建立，无论从哪个层面上来说，都离不开网 络应用这个基本属性。在实际应用中，同样多的用户要求同一多媒体数据流，然 而对同样的拓扑结构来说，由于采取不同的资源调度和管理算法，会出现不同的 结果：一方面可能是某个用户得到了满足，而其余用户未得到满足；另一方面可 能大家都得到了满足，而且网络资源的利用最少；有时还会出现网络拥塞，从而 导致网络瘫痪。产生以上的现象根本原因是忽略了网络的应用属性。 二、网络的建模分析 2 1 由于我们的模型是面向应用而设计的，这就要求我们必须从现代的应用 网络出发，但为了研究方便，又不得不舍去有关具体的物理性质，从而进行抽象 和量化。由于网络在功能上是分层描述的，我们相应的模型也应该是具有层次性 的。在链路层以下，特别是物理共享传输媒体，链路常常被认为是一个无向的。 但是在描述波分多路复用( w d m ) 的网络方面，便可以用一组有向的可利用的 波长来描述每条链路的传输能力。而在网络层，对于每个数据流所建立的路径， 这条路径是与数据的传输方向是相关的，这样可视为带宽是有方向性的。从传输 层往上，在对等的实体之间所建立的链接，代表了一条从源结点到目的结点之问 的逻辑链路，具有明确的方向性。这样也是众多的研究网络模型的文献( 9 ) 均采 用有向图来描述网络，使它们研究的对象适合于面向连接的网络控制。但是这样， 它们也忽略了许多重要的网络细节，特别是网络传输媒体的物理性质，比如说， 信元率的延迟。例如拿传输延迟来说，一个数据位从发送方到接收方的传输的所 需时间，即使在最好的条件下，也比光速小的多，但是这种延迟取决于距离和介 质，而与带宽无关。对于广域网络链路，通常以毫秒来记录传播延迟。例如贯穿 美国大陆的传播延迟在3 0 毫秒左右( 1 3 ) ，而这些情况往往被人们认为是与带宽 有关的，或者有关文献都作了一些假设( 4 2 ) ，这些都是与我们实际网络相差甚远。 但若拘泥于过细的物理细节会使我们的网络模型失去其通用意义，使得我们在网 络模型的建立时，对于现实中的网络和所研究的对象的抽象来一个可以接受的折 6 衷。这就是说，在网络的拓扑结构中，我们可以视其为一个有向图，而在其传输 媒体应用的层面上，可以视其为抽象的虚拟通道。这样在研究数据流或信元的传 输时，我们总是假想其在某个信道中以恒定的速率传输。 2 2 在理论意义上，什么样的网络拓扑结构最稳定，这也是很多文献没有提 到的，实际上，q o s 网络算法的研究前提都是要具有十分可靠的网络拓扑结构， 对此问题，本文给出了明确的回答。网络的拓扑结构是在网络建设初期完成的， 也就是说它在网络规划阶段完成的，但无论怎样细致地规划，网络节点和链路也 会不断地增加，客观上要求我们的模型要适合动态的情形，即模型要不断地适应 网络的不断发展变化，在这个层面上我们尝试采用动态的方法。而且，由于对网 络的拓扑结构具有不可预测性，从而在客观上也要求模型具有适应这种变化的能 力。 2 3 网络特征尺度之间的关系( 即网络特征的量化) 。通常分组级的q o s 集中 在分组的丢失率、分组的延迟和延迟的抖动上，而这些参数又与所保留的带宽和 网络的突发信息量有关。在实际运用中，延迟比其他指标更重要。但若考虑到带 宽和网络的突发信息量等两个或两个以上的网络尺度的相乘或相加给某些技术， 比如说路由选择会带来的n p 完全问题，这样就有必要将采用一些可接受的技术， 在不影响网络模型和实际网络之间的差距的情况下，对带宽、速率等进行离散化， 这样做是由于通常实际网络应用中接入速率和带宽是一些有限的常数。这样处理 以后，给我们的路由技术带来了巨大的变化，即把n p 完全问题转化为多项式时 间算法( 1 3 ) 。又由于网络在使用的过程中有很大的不确定性，这就使得我们在处 理问题的过程中，要有很大的不确定性，也使得我们不得不采用概率的方法。 由于本文考虑的是基于i p 的q o s 网络模型问题，即源结点到目的结点的q o s 保证。实际上，在i p 网络里，端到端的链接起始于第三层，因此，只有运用网 络协议即l p 协议才能提供软的端到端的q o s 保证。通常人们考虑端到端的q o s 保证时，是从以下几个方面考虑的： 带宽( b a n d 、v i d t l l ) 用来描述给定的传输介质协议或链接的额定吞吐量。实际 上，是指应用程序在网络上所需要的管道大小。通常说来，0 0 s 服务的连接，会 有一定的带宽要求，并希望网络为它分配最小的带宽。 分组延迟：在我们讨论i p 网络中，分组延迟包括以下情形： a 串行化延迟：在输出速率一定的情况下，指各同步一个分组所需的时间。 串行化延迟取决于链路的带宽以及分组的大小。 b 传播延迟：一个数据位从发送到接收方所需要的时间。 c 交换延迟：设备从收到分组到开始传输的时间，通常少于1 0 us 。 实际上，并非同一流中所有的分组延迟都相同，它的每个分组的延迟随中转网络 的状况而异。如果网络没有拥塞，则路由器上没有队列，这样，总的分组延迟由 每个中继段的串行化延迟和传播延迟所组成，这是网络的最小的分组延迟，串行 化延迟用s d 表示，传输延迟用t d 来表示。但是如果网络发生拥塞，排队延迟将 影响到端到端的延迟，并导致通过同一连接的传输分组延迟各不相同。称分组延 迟的变化程度为分组的抖动。由于分组的抖动可以估算出接收方分组的最大延 迟，而不是单个分组的延迟，所以，分组抖动很重要，接收方可以根据应用程度 添加一个能够存储抖动范围内分组的接收缓冲区来补偿抖动。发送连续信息流的 回放应用程序( 如交互式语音电话、视频会议及v o d 视频点播) 都属于这一类。 下图( 1 3 ) 便是描述了随着链路速度的增加，三种延迟对总延迟的影响，串行化延 迟s 。比传播延迟l 随着链路速度的增大越来越不重要。如果队列为空，则交换 西北大学硕士学位论文 延迟可以忽略，但随着队列中等待分组的增加，交换延迟将锐增。 图2 2 在上图中l ，2 ，3 ，4 ，5 ，6 分别代表我们经常所见到的t l ( 1 5 m b i t s ) ，d s 3 ( 4 5 m b i “s ) ， o c 3 ( 1 5 5 m b i 魄) ，o c l 2 ( 6 2 2 m b i s ) ，o c 4 8 ( 2 4 g b i 魄) ，o c l 9 2 ( 9 6 g b i 魄) 速率，而三种 延迟则分别是最左边所示的为串行化延迟，中间所示的为交换延迟以及最右边的 便是传播延迟。 实际上，影响延迟的因素还有分组的丢失率，这是因为当输入某个端口的分 组数量远远超过输出队列的限制时，就会发生丢弃现象，丢失率用来记，这样 使得实际上发送端的数据量在到达接收端之前需要发送( 1 + “) 个分组。 在以往的网络模型中，链路延迟仅考虑的是传播产生的延迟，结点处理相对 快而被忽略( 4 5 ) 。而有些文献( 4 2 ) 则用瓶颈带宽和传播延迟来反映网络的基本特 征，将其看成是路径的宽度和长度( 4 6 ) ，而有些文献虽然注意到了结点处的处理 速度，但是却忽略了排队延迟对整个端对端延迟的影响( 1 0 ) 。此外，还有众多的 文献都忽略了网络中数据流的生存期( 3 ) ( 4 ) ( 5 ) ，即在流的生存期内考虑对网络资 源的管理，而且也未提到如何安排队列问题，及它对数据分组的延迟抖动影响。 这样，给定个拧跳的路径p ，每条路径的剩余带宽为尼，结点的通信量受限于 漏桶( 盯，6 ) ( 即我们经常所说的c b r 承诺接入速率) ，其中，玎是平均的令牌 产生速率，6 是桶的大小。可以证明，分组所绑定的端到端的延迟、延迟抖动和 所需的缓冲空间可由以下公式计算( 4 0 ) ： 。2 軎+ 争+ 喜等+ 喜t z m j ( p ) ：鱼+ 堕竖( 2 2 2 ) 盯盯 b ( p ) 2 6 + 月一 ( 2 2 3 ： 其中，n 是源结点到目的结点的跳数，r ，( ，2 盯) 是链路所留的带宽，l 。是 8 堕j ! 盔兰堡主兰些堡兰 最大的分组尺寸，d 。是第f 跳的传播延迟。实际上，这些公式将延迟、延迟抖动 和缓冲空间与带宽和过滤流量漏桶特性联系在一起，若把n 看成变量- ，上述公 式可以变成第，跳的延迟、延迟抖动和缓冲空间。 另一方面，也可以利用下面两个公式来计算端到端的分组延迟( 4 3 ) ： 垡二! 堂掣+ 兰些- 鱼+ d 。p ，盯( 2 2 4 ) r o p 一仃) 7 姓+ r p 盯( 2 2 _ 5 ) r 其中，p 是通信量的峰值速率，c 表示与速率相关的误差，单位为比特( 如连续 的分组由于尺寸的差异造成发送时间的误差) ；d 表示与速率无关的误差，单位 为芦s( 如等待所分配的时隙的时间造成的延迟误差) 。c 。和d 。分别表示端 到端c 和d 的组合，r p 盯的情况表示当链路服务速率大于通信量的峰值速 率时，不存在排队分组，因而它表示两个端点之间单纯用于传播和交换的时间。 但从上面的( 2 2 1 ) 式可以看出其没有考虑到通信量的峰值速率，是整形以后， 即( c b r ) 流的传输和交换时间。再来比较( 2 2 1 ) ( 2 2 2 ) ，延迟抖动来自于各 结点的整形时间。综上，两个公式可以说明以下问题： ( 1 ) 链路上传播延迟d ，是固有的，通常与距离有关，这部分不是导致严 重延迟的主要因素： ( 2 )链路上可利用带宽r 越大，排队时间越小： ( 3 )端口的处理能力既影响整个传输速率，也关系到分组的丢失率； ( 4 ) 上面的考虑方法都是以过程为基础的，但是对于用户和服务器端没有 考虑有效的数据大小。 三、网络模型的建立 笔者在( 4 3 ) 的基础上，本节给出基于流的q o s 网络模型，将在2 3 给出了 基于光纤波长分配的映射。 定义2 2 1 网络的拓扑结构，用有向图g ( v ，e ) 来表示。其中v 是结点集， 可以表示交换机、路由器和主机，也可以表示子网；e 是边集，代表通信链路。 ”= i v i ，小= 吲，边e 表示为g 。= ( u ，v ，) ，表示从结点v ，到v ，之间的一条直 通的链路，f ，= l ，2 ，3 n ，_ ，_ v 。 定义2 2 2 边p f 有三个属性：长度，f ( 拥) ，媒体的传播速率，( 枷s ) ，误码 率e 。 ，、l 定义2 2 3 结点v ，的属性，d 一蚵表示每个结点的入度，即以v ，为尾的边数目 d o 驴表示每个结点_ 的出度，即以_ 为头的边数目：v ，的服务速率为s ， ( 6 f ，j ) ，v ，= ( 弓，吃气，k = d 产l ，2 一n ) 气表示v ，连接第k 个边的端口，端口有两个属性：端口的吞吐率，( b i 仃s ) ，端口 的缓冲空问v ( b ”e ) 。 定义2 2 4 每一条边有以下4 个函数： 单位分组的传播延迟函数，m 。：e r + ； 边误码率：e 。：e 斗( 0 ，1 ) ； 代价函数，c 。：e r + ； 可利用的剩余带宽函数，r 。：e r + ； 状态函数，s 。：e 寸 o ，1 ) e 定义2 2 5 每个节点有以下几个函数： 单位分组的传输延迟，l ：v 专r + ； 单位分组的串行化延迟，d 。：v 哼r + 代价函数，c 。：v j r + ； 端口的自由缓存，f 。：v 专r + ； 节点的分组丢失率，l 。：v 寸r + ； 端口的传输速率，t 。：v r + ； 与调度机制相关的节点延迟抖动，d j ：v _ r + 单位分组的排对延迟，d 。：v 斗r + 这样g 上的一条路径p ( v ，v ：v 。) ，七n ，v l 是源结点，v 。是目的结点， 从源结点到目的结点的跳数为路径p 所经过的链路数：h ( p ) = k l 。通过上面的 定义，则该路径p 上的延迟、代价、瓶颈带宽等函数为： l o ( 2 2 6 )如 吃 “h + ”p 乃 + )p d h + ) p 怫 h m = d 西北大学硕士学位论文 代价函数为 ( 2 2 7 ) 瓶颈带宽为： r ( p ) = m i n r e ( v ，v + 1 ) if = l ，2 助 ( 2 2 8 ) 由于在实际中，考虑到传输链路的误码率的节点的分组丢失率，其采用的方法都 将传输错误的数据重传。这样，设需要从源结点到目的结点需要传输m 个分组， 则实际需要传输的数据分组为： 一i g ( p ) 2 二 ( m ( 1 + ，) ( 1 + 巳( ( v ，v m ) ) ) ，此时，我们总是假定源节点传输过来的埘个 女一1 分组是有效的应用分组，而且，此时延迟抖动为： j ( p ) 2 d ，( v 小p 上需要的 i i l 自由缓冲空间为： f ( b ) = m i n f b ( v ，) if = l ，2 埘，这样，由于单位分组从元节点到目的节点需要 d ) 时间，于是，在单位时间内，可到达目的节点的分组数为： 1 p2 d ( p ) ( 2 2 9 ) 实际上，对于应用程序来说，不管你采用什么样的传输方法及调度策略，应用 程序端只是关心的是单位时间内到达的有效分组的数目，即指这里的有效数据流 密度p 这样，对于要求不同的网络传输服务质量的应用，可以根据该数学模型，定义 相应的度量函数，并将其作为q o s 路由尺度和资源管理尺度。 四、下面考虑路径p 的带宽碎片函数( 4 5 ) 。假设该链路的容量为r ，剩余带 宽为，在连路未阻塞时，总共有窄带连接 个( 带宽为6 1 ) ，宽带连接为，个 ( 带宽为6 ：) ，则链路的资源利用率声为 声2 ( ，6 l + ：6 2 ) 瓜= 1 一瓜 ( 2 2 1 0 ) 令珊= 孚 ，表示两链接的资源占用比，则( 1 0 ) 可变为： ，2 d 2 芦2 ( 6 l + 26 2 ) r = ( ( 1 + ) ，2 ) 6 ：r ( 2 2 1 1 ) 这样，式( 1 1 ) 便等效于链路上全市宽带链接的资源利用率，根据文献( 4 1 ) ，提出的 关键路径( 如网络中流量远大于平均链路流量的容易阻塞的平静链路) 阻塞公式 西北大学硕士学位论文 可以求出关键连路的最佳资源利用率： 皇型! ! 型 o 5( 2 2 1 2 ) b ( - ，a ) ， 二二曰( m 一1 ，a ) 其中b 是标准的e r l a l l gb 公式： b ( 川，旯) = 兰下一 ( 2 2 1 3 ) 珊+ 二b ( 肌一1 ，五) 在上式中，链路的分组到达为泊松过程，处理时间为指数分布，a 为呼叫的到达 率( 连接申请的到达率) ，为处理速度，并假设链路的时延为单位时间。于是， 可利用( 1 1 ) ( 1 2 ) 可以计算出关键链路中等效宽带连接的最佳资源利用率芦+ 。 定义2 2 6 设p 是连接i 的路径，对于v ，接入f 之前的剩余带宽为冉， 接入之后剩余带宽与蜀之比为链路带宽碎片函数，记为f r a g ： f r a g ( ? ) ：墨。1 0 0 ，其中f 的带宽为6 。 “t 实际上，带宽碎片函数反应的是连接对链路的带宽影响。为保证金在网络负荷较 重时( 对应的相关链路的资源利用率大于最佳利用率) ，宽带和窄带接入的公平 性，要对两种连接应分别作出相应的处理，f r a g ( d 值越小，表示该链路接入该 连接后剩余带宽越小，亦即选用的是剩余带宽小的链路。 定义2 2 7 设连接路径p 包含了网络的若干关键路径，则称f m g q ) ： f r a g ( p ) = 肌g ( ，) 为路径带宽的碎片函数。 f t p 这样，在网络负荷较轻时，无论是宽带链接还是窄带连接均可选择与f m g ( p ) 有 关的路径。但当网络负荷较重时，为了保证接入的公平性，两种连接需分别做出 处理，种方法是宽带链接选择f 嘞) 值小的路径，而窄带链接选择f m g ( p ) 值 大的路径。这样，可以避免当资源严重不足时链接接入宽带链接后无法再接入新 的宽带链接。 综上所述，网络优化的总体目标是： a 对于四种流的任意一种流的应用程序，从应用程序之端，即用户端来说，所 关心的是他自己的应用程序所需要传输的数据，及关心的是数据包( 数据分组) 到达的速率及抖动参数。在这里，传输率体现为带宽，即给定某条路径p ，对 用户端来说，要求： f m a ) ( ( m i nr ( p ) ) 1m i nd 0 )( 2 2 1 4 ) l m i nj ( p ) b 而对网络资源管理者来说，对于用户所要求的一条路径p ，则必须考虑以下 的因素： 堕! ! 茎兰堡主兰篁笙苎一 网络某条关键路径的带宽碎片函数，即m i nf r a g ( p ) ( 2 2 1 5 ) 网结整体的负载平衡参数口：口是指在网络中关键链路最大的剩余带宽r 与 最小的剩余带宽r m 的比值，即：a = j ( 2 2 1 6 ) 儿m m 若a ( 1 一占，1 + 之间时，我们就称该网络在基本上是平衡的，其中s 是我们可 以接受的范围。 三、下面我们给出前面所提到的有关其他函数的定义： t l， m 个分组的传播延迟函数：2 肌c ，其中k 为跳数，j 钆。 ，。l f “o q f + 。 为边e m 的长度，f 。为边e “+ 的传输介质传输一个数据位从发送方到接收 方所需的时间，s 。为边p 。+ 。的状态函数，即当s 。= l 时表示边e 。+ ，为通 路，即当5 q 。2 0 时表示边e 。+ ，为断路a 节点的串行化延迟函数：由于串行化延迟与带宽和分组大小有关，而且 在实验测得，串行化延迟与带宽成反比，和分组大小成正比。于是串行化 延迟函数可以表示如下： d ( b ，c ) = 女，； d ( 2 2 1 7 ) 其中c 为分组大小，单位为字节，6 为该链接所需要的带宽的大小，为该 节点的处理属性，它与节点的处理速度成反比，即若节点的处理速度为p 。 时，则，= 上。 p ， 单位分组的传输延迟函数：乃= 女，- c ，其中c 为单位分组的大小，k 为 该节点的处理常数，它与该节点的处理速度有关，由于在实际中，k 的值 非常小，c 也不超过6 4 个字节，于是总是假定死是一个常数， 即l 1 0 朋。 单位分组的排队延迟：由于排队延迟具有非常的不确定性，我们试图从网 络的实际出发去探索，实验测得，排队延迟与网络的关键路径的负载状态 有关，也与节点服务器或交换机、路由器的工作速度有关，于是我们可以 通过下面的公式加以粗略的描述： 。c p ，p v ，c ，2 七一，。j ；三与 c 2 2 j s ， d q ( p ，p ”。) 2 七p s 。徜 q 2 1 8 ) 西北大学硕士学位论义 其中p 为该网络某些关键路径的负载参数，p ( 0 ，l n ( r ) ) ，p 9 为指数函 数，。为分组在队列中距处理器的“距离”，n 为该节点的处理速度，t ，为 与队列调度有关的一个常数，比如说，如果采用先进先出机制，则七。= 1 ， 为对列长度毛与自由缓存0 的一个函数 当，g 三q ，6 ， ，g 时，s q2 1 ；否则，j 。2 0 关于抖动函数p ) ，它与源节点发送数据分组的性态是相关的，我们总是 假定源节点是均匀的发送数据分组的。设口= f ，) ：，是一个时间序列，我们 定义他的平均、最小、最大的时间间隔分别为( 1 4 ) ： 平均的时间间隔：x 二= 量二生 疗 最小的时间间隔：j i ：i 。= 胁( jf 。一ii o f h 一1 ) 最大的时间间隔：z 0 = 嬲& r ( if j + l f ， i o j 一1 ) 在不影响上下文产生歧义的的情况下，我们在这了略去上标盯，从而盯的 平均速率便记为1 x ? 。 实际上对于抖动，一般有两类，一类是速率抖动，一类便是延迟抖动。其中 延迟抖动是指在x 。时间单元内，理论上的延迟时间与实际上的提交分组的时间 差别。此时给定一个时间序列仃= 钒) 二，我们定义仃的延迟抖动为： ，4 2 皇鬯( i 一气一( f 一七) 托i ( 2 2 1 9 ) o s s 。 “、 、 另一方面，我们定义盯的速率延迟，可以用最大的时间问隔去描述，这是因为在 不同的时间内最大的时间间隔与速