（通信与信息系统专业论文）高速网络中端到端qos拥塞控制技术的研究.pdf

华 中 科 技 大 学 博 士 学 位 论 文 ab s t r a c t w i t h 出 . r a p i d p r o l i f e r a t i o n o f t h e w w w , t h e i n t e r n e t h a s s e e n a n e n o r m o u s g r o w t h i n 山 e d e m a n d f o r n e w s e rv i c e f ro m i t s a p p l i c a t i o n s . t h e i n t e r n e t o ff e r s o n l y v e ry s i m p l e q u a l i t y o f s e rv i c e ( q o s ) : p o i n t - t o- p o i n t b e s t- e ff o rt d a ta d e l iv e ry . i t f a l ls f a r s h o rt o f d e l iv e r in g t h e k i n d o f r e l ia b il it y a n d p e r f o r m a n c e g u a r a n t e e s i n t h e f o r m o f b a n d w i d t h a n d e n d t o e n d d e l a y t h a t a p p l i c a t i o n s a r e d e m a n d i n g . i e t f i s w o r k i n g h a r d t o s t a n d a r d i ze n e w s e rv i c e . b u s i n e s s e s w i l l n o t p l a c e t h e i r m i s s i o n - c r i t i c a l d a t a , v o i c e , a n d m u l t i m e d i a a p p l i c a t i o n s o n t o p u b l i c i p n e t w o r k s u n t i l t h e y r e c e i v e s e c u r e , p r e d i c t a b l e , m e a s u r a b l e , a n d g u a r a n t e e d s e rvi c e . t h i s d i s s e r t a t i o n f o c u s e s o n t h e i n t e r n e t q o s r e l a t e d s u b j e c t . m a n y d e e p r e s e a r c h e s h a v e b e e n d o n e i n t h e s e f i e l d s . a n d i t h a s m a d e s o m e c o n t r i b u t i o n s a n d d e v e l o p m e n t s b a s e d o n t h e p r e v i o u s a c h i e v e m e n t s . c h a p t e r 1 r e v i e w s t h e r e c e n t w o r k s a n d s o m e p ro b l e m s i n t h i s a r e a . i n o r d e r t o i m p ro v e t h e e n d t o e n d q o s p e r f o r m a n c e i n t h e i n t e rn e t , c h a p t e r 2 a n a ly s e s t h e s i m i l a r i t i e s a n d d i ff e r e n c e s i n p ro v id i n g q o s o v e r i p a n d a t m . i t f o c u s e s o n t h e c o m p a r is o n o f t w o s e rv ic e m o d e ls p ro p o s e d 妙 i e t f . a n d i t p r e s e n t s t h e a u t h o r s o p i n i o n o n t h e f u t u r e t r e n d s o f q o s s e rv i c e m o d e l s . a t l a s t i t d i s c u s s e s t h e p a c k e t s c h e d u l i n g a l g o r i t h m s , t c p a n d b u ff e r m a n a g e m e n t s c h e m e s . t c p s a b i l i t y t o s h a r e a b o tt l e n e c k f a i r l y a n d e ff i c i e n t l y d e c r e a s e s a s t h e n u m b e r o f c o m p e t i n g fl a w s c h a p t e r 3 s u rv e y s t h e t c p t r a f f i c c h a r a c t e r , d i s c u s s e s t h e c a u s e a n d p r e s e n t s o n e w a y t o w o r k a rou n d t h e p rob l e m. w h e n t h e n e t w o r k m e e t c o n g e s t i o n , c o n g e s t i o n c o n t ro l s c h e m e s s h o u l d b e i m p l e m e n t e d t o a v o i d i t . c h a p t e r 4 p r e s e n t s a n e w i r e d s c h e m e b a s e d o n t h e r e d , i t i n t ro d u c e s fl o w b a s e d t h r e s h e s a n d s c i e n t i f i c d i s c a r d i n g f u n c t i o n s . i t c a n m a i n t a i n s y s t e m s t a b i l i t y a n d d i s t r i b u t e s 伽 o ff l o a d f a i r l y . 1 1 中科技大学博士学位世 c h a p t e r 5 a d d r e s s e s t h e p ro b l e m s o f a g gr e g a t e d fl o w s s c h e d u l i n g . i t h a s p r e s e n t e d a n e w c l a s s - b a s e d s c h e m e 一 b wq t h a t c a n b e u s e d i n d i ff e r e n t s e rv i c e s fr a m e w o r k . i t h a s f o l l o w i n g b e n e f i t : ( 1 ) r , l o s s l e s s , a n d ( 2 ) i t c a n p r e d i c t t h e d e l a y o f t h e b a c k l o g t r a ff i c , a n d ( 3 ) i t c a n a d j u s t t h e a c c o r d i n g t h e b a c k l o g t r a f f i c d y n a m i c a l l y . at e ? t h e in t e r c o n n e c t i o n o f d i s s i m il a r l a n s o v e r a h i g h - s p e e d b a c k b o n e n e t w o r k m a y c r e a t e c o n g e s tio n a n d l o s s o f d a t a a t a d e s t i n a t i o n l a n b e c a u s e o f t h e u n m a t c h e d t r a n s m i s s i o n r a t e . c h a p t e r 6 p r e s e n t s a n e w a l g o r i t h m t h a t a d o p t s o p e n l o o p a n d c l o s e l o o p c o n g e s t i o n c o n t r o l . i t c o o p e r a t e s t h e p e r m i t s a n d t i m e - s t a m p s s c h e m e s , t o g e t h e r w i t h t h e f c f s s c h e d u l i n g p o l i c y . a n d i t w o r k s b e tt e r t h a n t h e o l d a l g o r it h m s t h ro u g h t h e s i m u l a t i o n e x p e r i m e n t s . :t h e d i s s e r t a t i o n s t u d i e s t h e s c h e m e s o f i m p r o v i n g t h e i n t e r n e t p e r f o r m a n c e i n t h e a s p e c t o f t c p , p a c k e t s c h e d u l i n g , b u ff e r e n t a n d n e t wo r k i n t e r c o n n e c t i o n . a c a d e mi c 。t h a t t h e s c h e m e s p r e s e n t i n t h e d i s s e r t a t i o n c a n e n h a n c e t h e i n t e rn e t q o s a n d e x p e r i m e n t e d s t u d i e s s h o w d r a m a t i c a l l y . k e y w o r d s : i n t e r n e t , q o s , t c p , s c h e d u l i n g s e rv i c e , a g g r e g a t e d fl o w , c o n g e s t i o n b u ff e r m a n a g e m e n t , d i ff e r e n t s e rv i c e , 华 中 科 技 大 学 博 士 学 位 论 文 第一章 绪论 本章介绍了 本文研究 课且的背最 及定 义. 分析了 在当 今因 特网 上的q o s 研究 现状及有待解决的问 皿. ，论途了 接纳控侧和信派整形、 q o s 选路和资浑预留、 基于q o s 的传物调度和级冲区管理算法、 惊合服务网的 q o s控制等何月。最后介绍了本文研究内容和结构安排。 互 1 . 1引言 2 0世纪以计算机为代表的信息产业，标志着人类社会进入了信息时代。计算机网络 的研究和发展，对全世界科学、经济和社会产生了重大影响.信息相关领域正在迅速地 融合，信息的获取、传送、存储和处理之间的孤岛现象随着计算机网络和多媒体技术的 发展逐渐地消失了，曾经独立发展的电信网、电视网和计算机网络将合而为一，新的信 息产业正以强劲的势头迅速崛起。 8 0年代末.随着因特网容a与规模以指数级增长并席卷全球，人们的生活与工作方 式随之发生了变化，人类开始看见了网络经济与信息时代的咯光。因特网的指数级增长 不仅出乎当时设计专家的想象，也让全球的传统电信运营商感到艘惊.因特网这种超常 规的发展反过来也刺滋新技术层出不穷，使传统电信设备制造商与电信运营商面临一场 全新的挑战。同时，全球电信管理体制的转轨 ( 开放市场、引入竞争)也引发了全球电 信业 ( 包括设备制造商与运营商)和计算机业 ( 包括 i s p与软件行业)的疯狂收购潮。 因特网己成为世纪之交信息革命 ( 包括电信网的巨大变革)的催化剂之一。 信息网络的建设与发展会对一个国家乃至全球的社会政治、经济、生活产生重要影 响。加快信息网络建设在社会信息化进程中具有非常重要的意义。信息化社会的一个重 要特点是人们对网络通信的能力提出了更多更高的要求，不仅要实现语音的传输，还希 望实现文字、图像乃至实时视频信号的传送.光纤传输网络技术、高性能网络交换技术、 t c p / i p协议技术、计算机技术、软件技术、多媒体技术的发展以及其它相关技术的最新 发展使人们 看到了下一代高性能、多样化网络服务的前景。 1 . 2因特网上的q o s 在当今的因特网中，多种应用播要提供服务质s( q o s ) 控制， 例如， 视频会议、 i p 电 话和远程教育等。因特网的q o s 控制技术也是下一代网络的核心技术之一，是当前网络 研究与开发的热点问压。 目前 q o s的研究开发在很多方面仍然是开放的，其主要问题有:( ) 网络系统状态 和链路带宽容a变化的不确定性，传输通路端一 到一 端带宽预留缺乏有效的保证:( 2 ) q o s 选路、资源预留和信息传愉调度算法的复杂性，还不能适应高速信息传输处理时间的要 求: ( 3 ) q o s 要求所导致的资源利用的无效性， 不能充分利用网络资源提高网络的吞吐量; ( 4 ) q o s 控制方案荃本上还是静态方案，缺乏有效的动态控制方案;( 5 )一些基本研究成 果主要存在于理论中，还没有形成专利或技术产品。现存的网络交换机或路由器还不能 完全保证用户服务质t .缺乏简单而有效的控制方案和算法的实现，传输管理与控制鱼 待改进.在i n t e r n e t 中，为了使i p ( i n t e r n e t p r o t o c o l ) 网络不仅能传输非实时的数据信息， 而且还能传输实时的多媒体信息，国际上的标准化组织，如i t u . i e t f 等已开始起草并 完成了一些用于i p 实时通信的标准，如实时传输协议/ 实时控制协议r t p / r t c p ( r e a l - t i m e p r o t o c o l / r e a l - t i m e c o n t r o l p r o t o c o l ) .资源预留协议r s v p ( r e s o u r c e r e s e r v a t i o n p r o t o c o l ) 以 及 h 3 2 3标准等。这些协议和标准对用户服务质量控制的研究提供了一定的基础，但还 有很远的路要走。 q o s控制主要包括信息传输的实时性和信息丢失的管理与控制等问题 1 - 6 1 .在因特 网中，不同用户可能有不同的传输要求。例如，视频和音频的传输有实时的要求，超时 的信息不能使用，但同时可以容忍某种程度的信息丢失;而数据的传输则不容许信息的 丢失，但传输的时延则不成问题。因此，要保证信息传输的实时性和丢失的综合要求是 因特网传输控制的一个直要问题 7 - 9 1 这里我们从q o s 控制与管理4 个方面的问题进行探讨和综述，它们包括接纳控制和 信汤整形、 q o s 路由、 基于q o s的传愉调度和缓冲区管理算法、 综合服务网的q o s 控制。 本文重点介绍上述问压研究的技术和思路.这些思路和技术对因特网q o s 控制的理解、 一 -一一一一一一- 一 2 设计和实现具有普迫意义。 1 . 3接纳控制和信浑整形 为了保证传输的q o s ，任何实际的q o s 传输控制方案必须考虑对用户传输实施接纳 控制( a d m i s s io n c o n t r o l ) ， 对其信派实施整形( t r a f f i c s h a p i n g ) 1 0 . q o s 的传输连接要求在新用户传输前进行接纳控制( 1 1 , 1 2 1 . 在用户入网时要求用户 把自己的传愉特性和参数以及他所要求的服务质量告知网络，网络再根据用户的传输性 能要求和网络现存的资源情况， 同用户协商决定是否接纳建立一个新的q o s 传输的连接。 在 q o s接纳控制中，有 3 个主要问题需要研究:哪些传输参数可以确切地描述一个 连接的传输? 网络使用哪些判据来决定是否接受一个新的连接? 网络性能与传输参数之间 的关系如何: ( 1 )传输描述参数 在目前的网络q o s 研究中.要求用户提供的有关q o s 属性的参数主要包括: 峰值分组速率 ( p e a k p a c k e t r a t e ) : 是指传输中的 最大瞬间 速率， 可 用产生两 个相邻 分组的最短时间间隔的倒数来表示: 平均分组速率( s u s t a in e d p a c k e t r a t e ) : 是指一段时间内分组传输的平均速率: 分组丢失率( p a c k e t l o s s r a t e ) : 是指由于出错或阻塞， 网络上丢失的分组数与用户发 山的分组总数之比。 分组传辅时延( p a c k e t t r a n s f e r d e l a y ) :是指分组从信源发出的源节点至到达目 的节点 之间的时间，由传播时延、排队时延、交换时延等组成: 分组时延变化( p a c k e t d e l a y v a r i a t i o n ) : 是分组传输时延的变化度盘，当该变量取 值高时，惫味着要给延迟敏感数据( 如声音和图像) 传输提供较大的缓冲. ( 2 )接纳判据 接纳判据是指网络在判断是否接受一个新的连接时决定的依据.分组传输时延和分 组丢失率 1 3 是两个最常用的接纳判据. 一一. 一一一一一一- 3 华 中 科 技 大 学 博 士 学 位 论 文 在 q o s控制网络中，分组传输可采用统计多路复用的方法共享带宽资源，各个连接 没有固定速率的专用信道，当某一连接传愉t增加时，会占用其他连接的资源，从而会 e 影响其他连接的服务质a，特别是由于因特网传输具有离突发性、高速率的特点，其传 输速率变化很快，因此增加了接纳控制过程的复杂性。仅使用长时间项的平均分组传输 时延和分组丢失率作为接纳判据，不能充分表示因特网快速、动态变化的程度，因此必 须虑能反映网络瞬间行为的判据。一些短时间项的瞬间行为的判据，例如，传轴时延的 变化、分组丢失变化率等应在因特网中采用。 ( 3 )网络性能与传输参数之间的关系 在因特网的接纳控制中.一个重要的研究问题是各种传物参数与网络性能之间的关 系。一些定性的关系和影响已经给出，但是如何给出定量的数学描述来表明它们之间的 关系仍然面临挑战，尤其是在多个异种传输流被多路复用的情况下更是一个难题.， 在因特网中，传输流是高度突发的，其传输速率变化很大，q o s网络系统一般要对 分组到达的流速进行整形并对用户所使用的信道带宽实行监控。信源整形和带宽监控技 术就是要避免分组在网络中的突发性传输，达到改善网络q o s 性能的目的.传输整形技 术成功的关键在于减少传输时延和分组的丢失。 可以使用传输限制函数来描述信源整形，如图 1 , 1 所示.b ( t ) 表示在时间长度 t 内 信 源 能 够 发 送 进 入网 络 的 分 组 个 数， 再i s i , s 2 表 示 在 时 间 间 隔 s l , s 2 连 接 ( 或 会 话 )j 到 达 的 分组数量。传愉限制函数可以表达为 a , ( s , s + t ) 5 b j ( t ) , d s , t 0 凡 ( s , s + t ) 5 b q ) 网络 图 l l信潭整形 目 前最常用的信源整形和带宽监控技术是“ 漏桶”( l e a k y b u c k e t ) 算法，这个算法可 华 中 科 技 大 学 博 士 学 位 论 文 将突发信潭流转化为平级传愉流，并确保用户的传输流遵守用户在建立连接时的规定. 润桶算法的荃本思想是， 任何一个分组要进入网络， 一定要从令牌池( 漏桶) 中取得一 个令牌，如果此时令牌池为空，则该分组被丢失。令牌由网络平均接纳速率 r产生，令 牌池最多可存放p 个令牌( p即漏桶的大小) ，令牌池满时，新产生的令牌被丢弃，图1 .2 是这种方法的示惫图.在漏桶算法限定信源模型中， 传输限制函数b ( t ) = p 十 r t 。一个信源 允许在任愈短的时间间隔内发送 p个分组的突发信息，但在长时间间隔范围内，信源被 限定以平均速率r来发送【 1 4 . 一个改进方法是，在分组到达泪桶前增加一个缓冲区，这样，当令牌池为空时，只 要级冲器没有满，分组就可以缓存在缓冲器中而不被丢失，如图 1 . 3 所示. 分组到达 分组离开 分组到达 分组离开 令牌发生价 令牌发生器 图 1 . 2 .捅算法 图 1 . 3 带级冲器的汤桶算法 这些漏桶算法还有一些缺点， 仍然采用丢弃或放入缓冲区的方法 例如，即使在网络负载很低时，漏桶算法对违约分组 ，由于算法的限制， 的浪费。采用标志法可以对此加以改善:当分组到达， 减缓了传输流速，造成网络资源 但令牌池为空或缓冲器已满时， 就将该分组打上一个标志，说明是违约分组，然后接纳它进入网络，如果在网络某处遇 到拥塞.则丢弃，若一直没有遇到拥塞，则可到达目节点。这也是目前i p网络所采用的 区分服务的荃本思路。 信源整形仅限定在信源入m处，非q o s 传输不需要整形 1 5 ) . 1 1 . 4 q o s路由 1 .4 . 1 q o s 路由的羞本概念和原理 q o s路由 1 6 就是根据给定的q o s参数，选择有足够网络资源的链路来传送数据. 路由有两方面的塞本内容.一是收集网络状态信息并不断更新信息，另一是根据已有信 息来为新的连接请求选择一条合适的路由。一个路由算法的性能极大地取决于信息收集 的好坏。 1 . 4 . 1 . 1 加权图模型 网络的拓扑结构和资源容1a 可以抽象为一个加权图( v , e ) . 其中节点 ( v ) 代表网络 中的交换设各，边 ( e )代表传翰线路。如果传输线路是对称的，则对应的边是无向的。 因为对称线路对两个方向上的数据都有同样的特性.对于大多数实际的网络而言，其链 路一般都是非对称的，因而其每一条链路对应于模型中，就是两条有向的加权边.每一 条链路都有一个对应于相关 q o s度量 1 7 . 1 8 的状态. 而每一个节点也有相应的状态. 它可以单独表示出来，或者也可以把它折算到与节点相连的链路状态中去。 1 . 4 . 1 . 2 状态信息 ( 1 )本地信息 每一个节点都必须保持其最新的本地信息，包括链路传输时延、排队时延、输出链 路的剩余带宽以及其他网络资源的可用性信息。 ( 2 )全局信息 所有节点本地信息的总和就构成了全局信息。每一个节点可以用链路状态协议或者 距离一向1t协议来发布、取得全局信息。链路状态协议通过让各节点广播其本地信息来 确定网络的拓扑结构和各链路的状态。距离一向量协议通过相邻节点定期交换其距离向 盘来取得并扩散全局信息.每一个节点保持的全局信息，总是对现有网络状态的一种近 似。这是由于信息传翰时延造成的。而时延的不可避免性表明这种不确定性会随着网络 规模的增加而不断扩大。 ( 3 )状态信息的聚合 因为任何物理设各的存储资源和处理能力都是有限的， 所以对全局信息的精确保存， 学 位 论 会带来扩容性问题，于是降低全局信息的规模就变得十分重要。这可以通过把一个具有 层次性结构的大型网络的局部信息进行聚合来完成，即把包含几个物理节点的组抽象为 一个逻辑节点，而逻辑节点又可以进一步聚合成更高一级的逻辑节点，如此反复下去。 在聚合过程中，必须把下层节点的网络度量特性聚集为本层逻辑节点的度量特性。这种 过程是复杂的，而不同的聚集方法对状态信息的影响也是一个开放性的问题. .4 . 2 q o s 路由 路由可以分为两大类:单播和多播.这两类路由问题是密切相关的。在很多情况下， 多播路由可以视为单播路由的推广。 1 . 4 . 2 . 1 单播路由 通过对 q o s度it 可以定义两种荃本路由问题:最优化问题和性能约束问题.最优化 问且就是寻找对应q o s 度a的最优路径. 而性能约束问题就是寻找大于对应q o s 度it ( 如 带宽)或小于对应q o s 度it ( 如时延)的一条路径，即在满足性能要求的集合中选择一 个解。优化问题要求最优解，而约束问题次优解就有可能满足需求。 这样就可以组合出四种基本的q o s 路由问题:链路约束问题、链路优化问题、路径 约束问题以及路径优化问题。例如带宽优化路由问题，就是寻找一个路由使其瓶颈链路 带宽最大.属链路优化问题。最小费用路由，就是寻找一条路由使其所通过的所有链路 的费用的和为最小， 属路径优化问题. 约束时延路由 1 9 . 就是寻找一条路由使其传输时 延小于给定的值， 属路径约束问 题. 链路优化问 题可由d ij k s t r a 算法或b e l l m a n - f o r d 算 法来实现，而约束链路问题可以比较容易地转化为链路优化路由问题.路径约束和优化 问肠则都可以由d ij k s t r a 算法或b e l l m a n - f o r d 算法来求解。 很多组合路由问题都可以从上面的四种荃本问题演化而来。如约束带宽一最小时延 路由就属于链路约束一路径优化问题，要寻找满足带宽需求的最小时延路由，此问题可 以通过把不符合带宽需求的链路删除后.用最短路径算法来解决。 用最短路径算法在多项式时间内求解的路由问题有以下四类:链路约束一链路优化 一 一 一一.一一 一 一 一 一 一 一 i 一 一 一一一- 问月、链路多约束问月，链路约束一路径约束问题，以及路径约束一优化链路问题。 而涉及到两个或两个以上q o s 度a的优化或约束问题则属于n p完全问题.如路径 约束一路径优化问题、路径多约束问题等。对于这样的问题，一般可以使用一些标准近 似方法求解，但是不能用于大规模的、复杂的网络。目前，算法的研究集中在利用网络 层次的、可压缩的拓扑结构特性方面【 2 0 1 . 1 . 4 . 2 . 2 多播路由 多播路由【 2 1 1 问题的处理与单播路由相似. 其区别仅在于， 在单播路由中对路径的优 化或约束，变为在多播路由中对路由树的操作。例如，带宽优化路由就是寻找瓶颈带宽 最大的路由树。时延约束路由就是寻找路由树，使其从源节点到任何一个目的节点的时 延小于给定值。 多播传送有以下几个重要的问题. s t e i n e r 2 2 路由树问题就是寻找覆盖给定目 标节点 集的路由树，使之在所有链路上的费用之和为最小，即最小费用多播路由问题，属于路 由树优化问题。而约束s t e i n e r 路由树问题，就是寻找时延小于给定值的s t e i n e r 路由树， 即时延受限最小费用路由问题，属约束路由树一路由树优化问题。寻找一个 s t e i n e r 路由 树或者约束 s t e i n e r 路由树属于 n p完全问题。约束时延一约束时延抖动多播传送问题属 于多约束路由树问题。 它也是n p完全问题， 其假设和性质与单播路由中的路径多约束问 肠相 同。 1 . 4 . 3 路由策略 根据网络状态信息的保存方式和路由搜寻方式的不同，路由策略可分为三种:源路 由、分布式路由和层次路由. . 4 . 3 . 1 派路由 每 个 节 点 保 存 全 局 的 网 络 状 态 信 息， 包 括 网 络 拓 扑 结 构 信 息 和 每 条 链 路 的 状 态 信 息 根据此全局信息，派节点在本地计算出一条合适的路由。然后.在选择的路由上传送一 华 中 科 技 大 学 博 士 学 位 论 文 个控制包，通知路由上的每个节点，说明其前继者和后继者为谁。每个节点的信息更新 由链路信息协议完成。 1 . 4 . 3 . 2 分布式路由 路由选择的计算是分布计算完成的。其路径上的各节点通过交互控制消息，并结合 各节点所存储的状态信息.来完成路由选择的计算.大多数分布式路由算法需要用距离 一向t协议成链路状态协议来保持其全局信息，在每个节点上此信息是以距离向量的形 式保存.根据距离向t，路由以接力的形式完成。 1 . 4 . 3 . 3 层次路由 2 3 物理节点聚合为组.而组又反复不断地进一步聚合为更高一层的组，从而形成一种 多层次结构。每个物理节点保存有经过聚合的全局信息，此信息包括此物理节点所在组 的详细状态信息和其他组的聚合信息。使用源路由算法来进行路由选择。然后，用一个 沿计算出的路径传愉的控制消息来建立连接.当代表逻辑组的物理节点收到此消息时， 它将把对应于其组的链路部分进行扩展，即用物理链路代替其对应的逻辑链路。 1 . 4 . 3 . 4 三种路由策略的比较和有待解决的问题 三种路由策略的优缺点如表 1 . 1 所示。 由于以下原因，使源路由不具有良好的可扩容性:通信开销与网络规模和本地信息 的广播频率成正比:存储开销与网络规模成正比:计算开销为网络规模的多项式时间， 且与连接请求的频率成正比:全局信息的准确度与网络规模 ( 或网络半径)和广播频率 成 反 比。 当网络规模扩大时，其对应的通信开销、存储开销和计算开销都相应地增长。降低 网络信息更新频率并不能解决此问题，因为全局信息的准确度也会随之下降。 分布式算法可以部分解决扩容性问题。例如基于选择性探测的分布式路由算法仅需 要局部信息，而差于令牌探侧的分布式路由算法可以克服信息的不精确性问题，从而可 学 位 论 以降低网络的通信开销。 路由策略 优点 缺点 待解决的问题 订路由 集 中处理 ，简 单， 不产生环路 保存全局信息，在大型网 络中有很大的传愉开销， 计算开销较大 可扩容性，信息不 确定性，对选择路 径的影响的研究 分布式路 由 可扩容性好 须引入环路控制机制和解 决分布计算的终止问题 多度坦约束路由算 法的研究降低通信 开销 层次路由可扩容性好， 抑 制环路的产生 聚合q o s 参数的实用、 有 效算法还有待研究 各种q o s 度量参数 的聚合问题 表 1 . 三种路由策略的比较 目前还没有处理n p 完全问题的高效率分布式算法， 特别是在多播传送中。 这主要是 由于没有详细的拓扑信息和链路信息可供使用.而如果在不同节点的全局信息不一致的 话，就有可能产生环路。环路可以通过控制包到达同一节点两次来检测，但环路将导致 路由失败，因为距离向量信息不能给出足够的信息来确定替代路由。 层次路由对扩容性问题给出了清晰的解决方案。由于每个节点仅保存经聚合的全局 信息，远端物理节点的信息用经过聚合的逻辑节点信息代替.这种聚合信息的规模仅是 全局信息规模的对数函数。因而其具有良好的可扩容性。另外由于计算是分布式进行的， 因此也具有分布式路由的优点。然而，由于信息聚合会产生附加的不确定性，其算法性 能会随网络规模而急剧降低.因为q o s路由对网络状态的不确定性比较敏感，故而研究 能适应网络不确定性的路由算法就变得十分重要。另外，由于层次路由是把有复杂拓扑 结构的组用一个逻辑节点代替，因而在做本地计算时，远端节点的具体信息是不可见的， 从而使箱确计算本地物理节点到远端物理节点的q o s 度f参数值不可能。此问题在涉及 叁 q o s 鱼 丛 c i 里 些 理 鱼 . o ft ,鱼 i1 n j v x 道 旦 9 j r 鱼 华 中 科 技 大 学 博 士 学 位 论 文 解决的问压 。 1 . 4 . 4 小结 q o s路由是下一代网络中传抽视频、音频信息的关键部分，它具有两个功能:( 1 ) 寻 找满足q o s 约束的路由: ( 2 ) 优化地利用网络资源. 根据网络状态信息的保存位里和方法， 单播/ 多播q o s 路由可分为三类:源路由、分布式路由和层次路由.源路由是研究最广 泛也最深入的一种，但存在规模性问题。分布式路由可以解决规模性问题， 但在一些n p 完全问题上还有待进一步研究。层次路由为规模性问题给出了很好的解决方案，但其多 q o s 度饭参数的聚合问题也有特解决。 因此，下一步研究应集中于:高效率 n p完全路由算法的搜索性算法、多 q o s 度量 、参数的状态聚合问皿、不精确信息下的层次路由。 肠 1 . 5基于q o s的传翰调度和级冲区管理算法 当数据包抵达愉出端口时，它甜要按顺序等待以便传送到输出链路上.调度算法的 墓本功能是从节点的每一个输出链路中挑选在下一个有效周期发送的分组.q o s传输调 度控制要基于几个原则，例如，带宽的保证、流的隔离、时延的保证和公平选择等.协 议和算法的复杂性要适应网络高速传愉和便于实现，使其具有可扩展性和鲁棒性。调度 算法可以分为两类:墓于速率的调度算法和基于时间的调度算法. 目 前最主要的调 度策略都是近似广义处 理器共享( g e n e r a l i z e d p r o c e s s o r s h a r i n g ， 简称 g p s ) 的调度策略.在i n t e r n e t 中，有关近似g p s 调度策略的规定在文献 1 5 1 中有所描述. 在处理器共享( g e n e r a l p r o c e s s o r s h a r i n g ， 简称g p s ) 调度中， 对于 每个连接 ( 会话 ) 都有一 个先进先出( f i f o ) 队列，它们共享着相同的链路.在任何时间间隔都正好有n个非空队 列，服务器以链路速率的 i n 同时传送在队列头部的n个分组. p s 方案以相同速率服务 所有非空队列，g p s方案则是p s 方案的扩充，允许不同的会话有不同的服务速率。g p s 方案1 2 4 1 有两个特性:可以保证端到端有界时延服务和确保带宽的公平分配。 一一-一一一一一一一- - - 一 1 1 华 中 科 技 大 学 博 士 学 位 论 文 g p s方案只是一个理想的流体模型，而不能完全在实际中应用. g p s的调度器是要考虑分组传输并按速率比例服务的调度器 2 5 - 2 8 . 大多数感兴趣近似 在流体系统和分组 网络之间的区别是:在任何时间，在流体系统中有多个分组同时接受服务，而在分组网 络中仅能有一个分组接受服务。时延保证是所有这些近似 g p s调度器的公共特性，但公 平特性每个调度算法却各不相同。在近似 g p s调度器的节点，服务器使用系统虚拟时间 函数为系统中的分组计算时间标签，时间标签规定这个分组相对于其他分组应当被服务 的时间，分组的服务按照它们时间标签值增加次序排列。在每个会话队列头部的分组时 间标签值作为会话的时间标签值。系统虚拟时间函数决定这类算法的时延和公平特性。 近似 g p s 策略调度算法实现的复杂性主要是由维持和分类所有连接时间标签的复杂 性决定的，具体包括:( i ) 系统虚拟时间函数所要求计算的复杂性:( 2 )为了选择和发送 具有最小时间标签分组而进行分类操作的复杂性:( 3 )处理和存储时间标签的花费。 简化近似g p s 策略调度算法实现的复杂性是q o s 调度策略的主要研究方向. 最近提 出的离散速串调度算法 i 8 并不要求给每一个连接计算和存储一个时间标签， 仅对每一种 速串维持一个时间标签。这种调度器有非常简单的两层层次结构.在这个层次结构的低 层.使用先进先出( f i f o ) 队列，一种速率一个f i f o队列，一个队列仅有一个时间标签. 具有相同速率的所有连接使用一个队列，这样就减少了时间标签的数童，因而降低了实 现的复杂性. 在这个层次结构的高层， 使用一个最坏情况公平调度器， 在不同f i f o队列 中进行调度。 现在 已研究的近似 g p s调度策略的例子有 自时钟公平排队( s e l f - c l o c k e d f a i r q u e u e i n g ,简称 s c f q ) 方案 2 9 .虚拟时钟( v i r t u a l c l o c k ，简称 v c ) 方案、最坏状况公平 加权公平 排队( w o r s t - c a s e f a i r w e i g h t e d f a i r q u e u e i n g ， 简称w f 2 q ) 方案 3 0 和最小时 延自 时 钟公平排队( m i n i m u m - d e la y s e l f - c l o c k e d f a i r q u e u e i n g ， 简称m d - s c f q ) 方案 2 5 等. 公 平排队方案最根本的思路就是给每一个会话以对有效带宽的公平共享，亦即相等的存取 权力.在加权公平排队方案中.调度器可以分配不同的权力给不同的会话。 在加权公平排队方案中，一个连接中的每个服务节点除了服务时延外都要有等待时 延. 这 些 等 特 时 延 要景 加 起 来 ， 将 形 成 会 话 传 翰 时 延 的 一 部 分 文 献 1 川提lb 工 边 鱼 鱼 早 华 中 科 技 大 学 博 士 学 位 论 文 到期优先( c o o r d i n a t e d - e a r l i e s t - d e a d l i n e - f i r s t .简称c e d f ) 的调度算法来克服等待时延的累 加。 一旦一个分组通过它的第 i 个服务器， 它就能很快地通过它所有剩下的服务器. c e d f 算法没有累加分组通过每个服务器的等待时延。 1 1 . 6综合服务网的q o s 控制 气 硕 在综合服务网络【 3 2 , 3 3 1 中.传愉流基本可以分成两大类:q o s传输流和尽f做好 ( b e s t - e f f o r t ) 传翰流. q o s传愉流目 前又可分为 保证服务 ( g u a r a n t e e d s e r v i c e ) 3 3 1 、 控制负 载服务( c o n t r o l l e d - l o a d s e r v i c e ) 3 4 和区分服务( d if f e r e n t ia t e d s e r v i c e s ) 3 5 等传输流.它们 需要 q o s控制，必须为其选路，预留带宽、缓冲和处理能力等资源 3 6 1 并进行实时调度 控制.而尽a做好的传输流没有q o s 保证，其带宽分配可以动态地改变，可以根据当前 时刻的传输要求和网络的有效带宽进行分配。 在网络中.实时传输一般使用常数位速率( c o n s t a n t b i t r a t e . 简称c b r ) 和实时可变位 速率( v a r i a b l e b i t r a t e ，简称v b r ) 服务;非实时传输一般使用非实时可变位速率、有效位 速率( a v a i l a b l e b i t r a t e ， 简称a b r ) 、 无规定位速率( u n s p e c i f ie d b i t r a t e ， 简称u b r ) . 实时 传抽属于q o s 控制的传物，典型的应用包括音频和视频互放的应用. a b r服务属于典型 的尽it做好传输，典型的应用包括文件和 e - m a i ! 的传输. 如果仅分别考虑不同服务级别的选路，q o s传输流选路重视减少新用户呼叫阻塞概 率，而尽t做好传翰流的选路，重视避免链路拥塞和改进每个会话的吞吐量。但在综合 服务网络中包含着多个服务流时，如果仅为每一个流选择一个优化的通路，这样优化的 通路将可能增加其他级别流的拥塞条件。因此，需要一个机制能够根据当前的负载情况 在不同服务流之间动态地分配链路资源， 这是综合服务网络q o s 选路的性能关键 3 7 - 4 5 ) . 综合服务网络 q o s 选路可使用下述3 种策略。 ( 1 )静态链路共享策略.将链路的容里静态地在 q o s传输流和尽1 t 做好传输流之间 分配。问皿是在两种传输流比例随着时间而动态改变时，如何静态地决定资源的分配比 例.另外，每种传输流在网