（通信与信息系统专业论文）分组调度算法及接入允许控制算法研究.pdf

摘要 摘要 随着网络技术的不断发展和网络应用的日益普及，为用户提供高质量的服务 越来越成为人们关心和研究的课题。 用户业务的 服务质量 ( q o s ) 与网络带宽资 源的分配以及网络对用户信息流的服务规则息息相关。在分组交换网络中，分组 调度算法在交换机和路由器中决定着分组的服务规则，而接入允许控制算法则决 定着带宽资源的预留和释放。因此分组调度算法及其接入允许控制算法对于确保 q o s起着关键作用，这方面的研究己 经成为当今网络技术的一个重要研究方向。 本文就是围绕着这一方向展开了探索和研究，主要的工作和贡献包括下面几个方 面: 1 . 提出了一种通用的调度模型 g s s ，证明著名的流体调度算法 g p s也属于 g s s 。本文研究发现，在g s s模型中，系统通常有富余的服务能力。这时一些服 务要求己经被满足的连接可以 把带宽资源暂时出让给更需要得到服务的连接，改 善这些的服务质量。为此本文提出了一种新的流体调度参考模型 s p f ，证明 s p f 也属于 g s s ，与 g p s有着相同的时延性能。本文分析了s p f出让带宽的性能， 证明在确保各个连接时延要求的前提下， s p f 具有 g s s 模型中最大的可出让带宽， 并能将这一带宽出让最长的时间。由于这一特性，s p f算法可以使系统的带宽资 源得到充分而有效地利用。 2 . 对调度算法v i r t u a l c l o c k 的接入允许控制算法进行了深入研究。 现有v i r t u a l c l o c k的接入允许控制算法难以确保连接的时延特性，原因在于现有算法没有充 分考虑到系统内有连接不断建立和拆除的情况，对连接带宽的释放时机没有作出 完善规定。 本文证明， 流体s p f 模型与v i r t u a l c l o c k 算法很相近， 因而将研究s p f 算法的思路用于研究v i r t u a l c l o c k的接入允许控制算法。 提出了基于生存期的接 入允许控制算法和改进算法，前者简单易行，后者使得系统带宽的利用率更高。 本文分析了 这两种算法的性能，证明二者都能够完全确保v i r tu a l c l o c k系统的时 延特性。仿真也证明了这一结果。 3 .针对当前研究非常广泛的p f q算法中空闲带宽使用的不合理现象，提出了 一种新的分组调度算法 f b r s . f b r s采用两种规则为分组服务，分别称为 m服 务器和 f 服务器。 m 服务器用来确保各连接的时延要求得到满足，f 服务器用来 公平地分配系统内的空闲带宽。f b r s算法不仅可以使空闲带宽能够按需分配， 它的 其它性能也很优良。 本文分析表明， f b r s具有p f q类调度算法最佳的时延 特性: f 服务器与m服务器的公平性分别达到或接近p f q算法的最佳性能; f b r s 算法的计算复杂度低，能够在高速路由器和交换机中实现。本文还给出了 f b r s 西安电子科技大学博士学位论文: 分组调度算法及接入允许控制算法研究 旦 旦 旦 些 绝 里 里 旦 旦 里巴 里 里旦 旦 旦旦 旦皿 旦 里旦 旦 旦旦 旦巴 绝 的两种引申 算法，一种是通用的p f q算法，另一种是与缓存管理相结合的算法。 第一种算法在p f q类算法中综合性能很优良， 第二种算法可以降低分组丢失率。 4 . 提出了一种新的分组循环调度算法 l f r r . l f r r可以使循环调度表中分配 给各个连接的时隙均匀分布，从而改善了 wr r算法的时延性能。l f r r在确定 连接的时隙分配时，采用权值大的连接优先分配的原则，改变了一些 wr r改进 算法从各个连接的时间标签中选取最小值的做法，因而降低了实现复杂度。 l f r r 中还采用了等权值合并的技术，使得算法需要处理的连接集数量比实际的连接数 目 大为减小，由此不但减小了存储时间标签的开销，而且进一步改善了时延特性。 本文还提出了一种用硬件电路构造调度表的方法，采用并行比较加译码，可以很 快构造出循环调度表。 计算机仿真和理论分析表明， l f r r算法的时延特性比wr r 有了很大提高。 关键词:服务质量， 分组调度算法， 接入允许控制算法， 时延， 公平性， 计 算复杂度， 系统带宽利用率。 a b s t r a c t ab s t r a c t wit h r a p i d d e v e l o p m e n t o f n e t w o r k t e c h n o l o g y a n d e x t e n s i v e p o p u l a r i t y o f n e t w o r k a p p l i c a t i o n , p r o v i d i n g q o s g u a r a n t e e t o v a r i o u s t r a ff i c h a s a t t r a c t e d s i g n i f i c a n t a t t e n t i o n . q o s d e p e n d s o n t w o e s s e n t i a l m e c h a n i s m . o n e i s b a n d w i d t h a l l o c a t i o n , t h e o t h e r i s n e t w o r k s e r v i c e d i s c i p l i n e . i n t h e p a c k e t s w i t c h i n g n e t w o r k , 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 i n t h e r o u t e r s a n d s w i t c h e s d e c i d e h o w t o s e r v e p a c k e t s , a d m i s s i o n c o n t r o l a l g o r i t h m s d e c i d e b a n d w i d t h r e s e r v a t i o n a n d r e l e a s e . t h e r e f o r e p a c k e t s c h e d u l i n g a n d a d m i s s io n c o n tr o l a l g o r it h m s p l a y a k e y r o l e i n q o s g u a r a n t e e . t h i s d i s s e r t a t i o n i n v e s t i g a t e s t h e s e p r o b l e m s . t h e m a j o r a c h i e v e m e n t s a r e o u t l i n e d a s f o l l o ws . i .a n e w g e n e r a l i z e d s c h e d u l i n g m o d e l n a m e d g s s i s p r e s e n t e d . we p r o v e t h e w e l l k n o w n g p s m o d e l b e l o n g s t o g s s . i n t h e g s s m o d e l , s y s t e m m a y h a v e s u r p l u s s e r v i c e a b i l i t y d u r i n g s o m e p e r i o d s . i n s u c h p e r i o d s s o m e c o n n e c t i o n s c a n l e n d t h e i r b a n d w i d t h t o o t h e r c o n n e c t i o n s t h a t n e e d m o r e s e r v i c e t o i m p r o v e t h e i r q o s . a n e w fl u i d s c h e d u l i n g m o d e l s p f i s p r o p o s e d f o r t h i s c a s e . w e p r o v e s p f b e l o n g s - t o g s s a n d i t h a s t h e s a m e d e l a y p r o p e r t y a s g p s . t h e a b i l i t y o f s p f t o l e n d b a n d w i d t h i s a n a l y z e d . i t i s s h o w n t h a t s p f c a n l e n d l a r g e s t b a n d w i d t h a m o n g a l l g s s a l g o r i t h m s a n d i t c a n l e n d t h i s b a n d w i d t h f o r t h e l o n g e s t t i m e . t h i s p r o p e r ty l e a d s t o a h i g h b a n d w i d t h u t i l i z a t i o n i n s p f s y s t e m. 2 . a p r o f o u n d s t u d y f o r t h e a d m i s s i o n c o n t r o l s c h e m e o f v i r tu a l c l o c k a l g o r i t h m i s m a d e . we f i n d t h e e x i s t i n g s c h e me c a n n o t g u a r a n t e e t h e d e l a y p r o p e r t y o f v i r t u a l c l o c k . t h e r e a s o n i s t h e e x i s t i n g s c h e m e d o e s n o t c o n s i d e r t h e c a s e t h a t c o nn e c t io n s m a y b e s e t u p o r t o r n d o w n a n d d o e s n o t g iv e t h e r u l e t o r e l e a s e c o n n e c t i o n s b a n d w i d t h . w e p r o v e v i r t u a l c l o c k a l g o r i t h m i s c l o s e t o s p f m o d e l . s o t h e i d e a o f s p f i s u s e d t o s t u d y t h e a d m i s s i o n c o n t r o l s c h e m e o f v ir t u a l c l o c k . t w o m e c h a n i s m i s p r e s e n t e d . o n e i s b a s e d o n a l i v e p e r i o d , t h e o t h e r i s i t s i m p r o v e d s c h e m e . t h e f o r m e r m e c h a n i s m i s e a s y t o b e i m p l e m e n t e d , t h e l a t e r i m p r o v e s t h e b a n d w i d t h u t i l i z a t i o n . i t i s p r o v e d t h a t t h e s e t w o s c h e m e s c a n f u l l y g u a r a n t e e t h e d e l a y p r o p e rt y o f v i rt u a l c l o c k. t h e s i mu l a t i o n a l s o v e r i ti e s t h i s r e s u l t . 3 . w e f in d f r e e b a n d w i d t h i s u n r e a s o n a b l y u s e d i n t h e p f q a l g o r i t h m s . s o a n e w s c h e d u l i n g a l g o r i t h m n a m e d f b r s i s p r o p o s e d t o r e s o l v e t h i s p r o b le m . t h e r e a r e t w o s e r v e r s i n t h e f b r s s y s t e m . o n e i s m s e r v e r w h i c h g u a r a n t e e s t h e d e l a y r e q u i r e m e n t o f e a c h c o n n e c t i o n , t h e o t h e r i s f s e r v e r u s e d t o d i s t r i b u t e f r e e b a n d w i d t h . f b r s c a n m a k e 西安电子科技大学博士学位论文: 分组调度算法及接入允许控制算法研究 旦 旦 旦旦旦旦旦旦口组皿巴旦旦旦里些吧 旦旦 旦 旦旦 旦旦 旦旦 旦 旦 旦 旦旦 旦 旦 旦 旦 旦 旦 旦 旦 旦旦 旦 旦 旦 旦旦 旦 旦 旦 旦 旦 r e s i d u a l b a n d w i d t h b e s h a r e d o n c o n n e c t i o n s d e m a n d , i t s o t h e r p e r f o r m a n c e i s a l s o p e r f e c t . t h e d e l a y p r o p e rt y o f f b r s i s b e s t a m o n g p f q a l g o r i t h ms . t h e f a i r n e s s o f m s e r v e r a n d f s e r v e r a c h i e v e t h e b e s t o r n e a r - b e s t p e r f o r m a n c e o f p f q a l g o r i t h m s . t h e c o m p u t a t i o n c o m p l e x it y o f f b r s i s v e r y l o w . i n t h i s d i s s e rt a t i o n , w e a l s o p r e s e n t t w o d e d u c e d a l g o r i t h ms . o n e i s a g e n e r a l i z e d p f q a l g o r i t h m , t h e o t h e r c a n r e d u c e p a c k e t l o s t r a t e i n t h e s y s t e m . 4 . a n e w r o u n d r o b i n a l g o r i t h m , l f r r i s p r o p o s e d . l f r r c a n m a k e s l o t s a l l o c a t e d t o a c o n n e c t i o n b e e v e n l y d i s t r i b u t e d i n t h e s c h e d u l e t a b l e . s o t h e d e l a y p e r f o r m a n c e o f wr r i s i m p r o v e d . i n l f r r , c o n n e c t i o n s w i t h s a m e w e i g h t a r e a g g r e g a t e d i n t o a g r o u p t h e n u m b e r o f g r o u p s i s m u c h s ma l l e r t h a n t h e n u m b e r o f a c t u a l c o n n e c t i o n s . l f r r d e a l s w i t h t h e s e g r o u p s . wh e n l f r r a l l o c a t e s s l o t s , g r o u p s w i t h l a r g e w e i g h t h a v e h i g h p r i o r i t y t o p o s s e s s s l o t , i n s t e a d o f c h o o s i n g m i n i m u m v a l u e f r o m e a c h c o n n e c t i o n s t i m e s t a m p t o d e c i d e t h e s l o t a l lo c a t i o n . s o t h e c o m p l e x i t y o f l f r r i s l o w . a h a r d w a r e i m p l e m e n t a t i o n f o r l f r r i s p r o p o s e d . p a r a l l e l c o m p a r a t o r a n d e n c o d e r l e a d t o a f a s t c o n s t r u c t i o n o f s c h e d u l e t a b l e . t h e o r e t i c a l a n a l y s i s a n d s im u l a t i o n s h o w t h a t t h e d e l a y p r o p e rt y o f l f r r i s m u c h b e t t e r t h a n t h a t o f wr r . k e y w o r d s : q o s , p a c k e t s c h e d u l i n g , a d m i s s i o n c o n t r o l , d e l a y , f a i r n e s s , c o m p u t a t i o n c o m p l e x i t y , b a n d w i d t h u t i l i z a t i o n 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中加以标注和致谢中罗列的内容以外，论文中不包含其 他人己经发表或专写过的研究成果;也不包含为获得西安电子科技大学或其它教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均己在论文中做了明确的说明并表示了谢意。 本 人 签 名 : 一 手c队日 期 : .7, o 0 2 三三 全 关于论文使用授权的声明 本人完全了 解西安电 子科技大学有关保留和使用学位论文的规定，即:学校 有权保留送交论文的复印件，允许查阅和借阅论文:学校可以公布论文的全部或 部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在 解密后遵守此规定) 期期 日日 本人签名:,k i f , 1 o 0 2 . . 2 宁 导师签名:a -二b , 丫 数学符号定义 论文中的数学符号定义 a ( i , , f , ) : 6 , t , 】 期间连接i 输入系统的业务量 kr , :分组 kp . 到达系统的时刻 气 ; : l f r r 算法中 在调度表第k 个时 隙前己 经 分 配给 连接 的 时隙 数量 c 输出链路的带宽 刃:分组对在v i r t u a l c l o c k 系统和l f r r系统中的离去时刻 可:分组对在s p f 系统中的离去时刻 d in , : f b r s 系 统中， 如果分组可被m服务 器调度 服务， d m 产 为对在m服务 器 中被服务完的时刻 : f b r s 系统中， 如果分组对被f 服务 器调 度服务，或 为对在f 服务 器中 被 服务完的时刻 d m f , :分组对在f b r s 系统中 被服务完的时刻， d m f , 一 d n , ik 。 :d m f , = 或 e , ( r ) : f b r s 系统中 距离t 时刻 最近的 上一 个连接j 忙期内 最后一 个空闲 时隙的 结 束时刻 e , : 在l f r r调度算法中， 可以占 用调度表中 第k 个时隙的 连接集合。 连接i e e , 当 且 仅 当 b , x 、 且 bb= k w f k : 在l f r r 调 度 算 法中， 优先占 有 第k 个时 隙 的 连 接 集 合。 连 接i e f , 当 且 仅当 b ; , 、 、 且 鱼 止 2 、 k 厂: l f r r 算 法中 连 接i 第。 个时 隙 的 时 间 标 签。厂一 n 势 对: v i r t u a l c l o c k 系统中分组对的 虚拟完成时刻 f b , ( i ) : f b r s 系 统中t 时 刻 连 接1 所 在 忙期 的 忙期 起 始时 刻 气( p 与: f b r s 系 统中 分 组对在m 服 务 器中 的 虚 拟 完 成 时 刻 凡( p 勺: f b r s 系 统中 分 组对在f 服 务 器中 的 虚 拟 完 成 时 刻 凡(t ) ; f b r s 系统中 连 接i 在m服 务 器中 的 虚 拟 完 成时 刻 函 数 气( t ) ; f b r s 系统中 连接i 在f 服 务 器中 的 虚 拟 完 成时 刻函 数 i ( t ) : t 时刻系统中复用的连接集合 ( t) : t 时刻s p f 系统中归一化超前服务量最小的连接集合 l e f t ) : ut ) 中 被积压的连接集合 v i :分组可的一长 度 l , m a 、 : 连接i 最大的 分 组长度 l - :系统中的最大分组长度 数学符号定义 l f r r系统中的分组长度 (t ) ; f b r s 系 统 中 t 时 刻 连 接 j 分 组 队 列 中 队 头 分 组 的 分 组 长 度 ll n w , ( r) :连接i 在s 服务器中的归一化超前服务量 n w s ( r) = w() n w , ( i u t , ) : b t z l 期间 连接i 在s 服务器中 超前服务量的 增量n w ,s (t ，2 ) = 些 q ,t,) 对: 连 接i 第k 个到 达 系 统的 分组 ( 在l f r r 算 法中对指 连接1 的 一 个 忙 期中 第k 个离开系统的分组) p t (t) : f b r s 系 统 中 连 接 j 在t 时 刻 之 前 被 f 服 务 器 服 务 的 最 后 一 个 分 组 对: t 时刻连接i 的队头分组 p hn : f b r s 系统中m服务 器在对被 服务之前为 连 接i 服务的 最后一 个分组 醉( 1 ) : t 时刻连接i 在调度算法s 中的队列长度 r ; : l f r r 算法中系统为连接i 提供的 平均服务带宽，r ; 一 v ;c 二 兰c 了 r :为连接i 预留的服务带宽 ( 在f b r s 系统中， 指连接i 需要系统为其提供的 基本服务带宽) r , : f b r s 系 统中 有空闲 带宽时 连接i 希望获 取的 空闲 带 宽 s w , , ( 1 t z ) : 在lt t i l 期间 连接i 在参考f 服务 器中 获得的 服务 量 必 : 分组对在v i r t u a l c l o c k 系 统中的 虚 拟起始时 刻，寸= m a x ( 讨 ， 对 一 ， s , , ( p , ) : f b r s 系 统 中 分 组对在m 服 务 器 中 的 虚 拟 起 始 时 刻 凡( p , ) : f b r s 系 统中 分 组对在f 服 务 器 中 的 虚 拟 起 始 时 刻 s , ( t ) : f b r s 系 统中 连 接i 在m服 务 器中 的 虚 拟 起始时 刻函 数 s f ( t ) : f b r s 系 统中 连 接i 在f 服务 器中 的 虚 拟 起 始时 刻函 数 s 呱( t r , ) : f b r s 系统中m服 务器在( t z l 期间 为 连接i 提 供的 服 务量 s 叭( r t , ) : f b r s 系 统中f 服务 器 在( 1 , , t , 期间 为 连 接i 提 供的 服 务 量 s t介f b r s 系 统 中 ， 如 果对被f 服 务 器 服 务 ， 对表 示f 服 务 器 开 始 服 务对的 时 刻 t - :还没有到时刻t ，但任意接近t 的一个时刻 t, ;, : v ir t u a l c lo c k 系 统中 连 接i 在t， 时 刻 后 生 存期 的 起 始时 刻， 即 如 果 连 接i 在 时 刻 之 前 建 立， 则t 1 ;, = r i ， 如 果 连接i 在，. 时 刻 后 建 立， 则t .、 为 连 接i 建 立 的 时刻 t2 , : v i r tu a l c lo c k 系 统 中 连 接i 生 存 期 在t, 时 刻 前 的 截 止 时 刻， 即 如 果 连 接i 在 时 刻生 存期还 未结 束， 则t ;l 二 t, ， 否 则f2 , 为 连 接i 最 后一 个分 组的 虚拟 完 成 时刻 数学符号定义 t,0 :连接i 首次输出业务的时刻 t :循环调度算法中调度表的长度 u ;( t ) : f b r s 系 统 中 在 连 接j 的 本 次 忙 期 中 ， t 时 刻 之 前f 服 务 器 为 连 接j 服 务 完 的最后一个分组的开始服务时刻 v . ( t ) : f b r s 系统中m服务器的系统虚拟时间f数 v , ( t ) : f b r s 系 统 中f 服务 器 的 系 统 虚 拟 时 间 函 数 w , ( t ) : t时刻连接 i 在 s服务器中获得的相对于r , 服务器的超前服务量 卜，今 5 ( :) 一 s w .(t0 , t) 一 s w j c t0 , r) w ,s u , tz ) : t , t z l 期间连接i 在s 服务器中 超前服务量的 增量 n ; 5 ( t r, ) 一 s w 5 ( t t, ) 一 s w ,j ( t tz ) * ， : 循环调度算法中为每个连接i 分配的时隙数 叽( t ) : f b r s 算 法中 连 接j 的 前 期 等 待时 间 p ; : 漏桶模型( a p , ) 中 令牌到达速率 q , : 漏桶模型( q p , ) 中漏桶的容量 英文缩写词 论文中的英文缩写词 b s f q :b i - s e r v e r f a ir q u e u in g双 服 务 器 公 平 排队 d r r :d e f i c i t r o u n d r o b in亏缺循环调度 e d f :e a r l i e s t d e a d l i n e f i r s t最小时延期限首先发送 f b r s : f r e e b a n d w i d t h r e a s o n a b l e s h a r i n g空闲带宽合理共享 f b r s - l f : f b r s l o n g e s t q u e u e f i r s t最长队 列 首先发 送的f b r s g p 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 s s :g u a r a n t e e d s e r v i c e s e r v e r能确保服务的服务器 l f r r : la r g e s t w e i g h t f i r s t r o u n d r o b in最 大 权 值首 先 发 送的 循 环 调 度 m d - s c f q : m i n i m u m - d e l a y s c f q最小时延的自 定时 公平排队 p f q :p a c k e t f a i r q u e u i n g分 组公 平排队 q o s :q u a l i t y o f s e r v i c e服务 质量 s c f q :s e l f - c l o c k e d f a i r q u e u in g r 定时公平排队 s p f : s m a l l e s t p r e c e d i n g s e r v i c e f i r s t最小 超前， 首先服务 w f q : w e i g h t e d f a i r q u e u i n g加 权公 平 排队 w f 2 q :w o r s t - c a s e f a ir w e i g h t e d f a i r q u e u i n g 最 坏 情 况 亦公 平的 加 权公 平 排队 wr r : w e i g h t e d r o u n d r o b i n加权循环调度 第一章 绪论 第一章 绪论 1 . 1 前言 近年来网络技术的发展日 新月异，以 通信网 络技术为基础的“ 数字化” 生活 方式正以其特有的魅力冲击和改变着人们的生活。网络以独特的方式和内容为人 们提供了全新认识和把握事物的环境，拓宽了人们认识世界的视野，改变了人们 的社会互动方式，对人们的工作和生活产生了广泛而深远的影响。 目前网络有两种业务承载方式， 一是a t m， 另一个是i p . a t m技术出现于2 0 世纪 8 0年代中期， 它采用 5 3 b y t e的 定长小分组作为 信息传送的基本单元， 分组 拆装时延短，网络交换节点的处理简单，而且可以通过信令为业务预留带宽资源， 因此a t m可以有效地支持多媒体实时业务。 i p出现于2 0 世纪 6 0 年代末， 基于i p 的i n t e r n e t 目 前己 经成为拥有几亿用户的巨 大网 络。 i n t e rn e t 的 特点是能够有效地 支持数据业务而且扩展性强。 但是传统的i n t e rn e t 只提供 “ 尽力而为” ( b e s t - e f f o rt ) 式的 传送服务， 而网 络中 的业务丰富多彩，用户的需求日益多样化，新的业务不断涌现。现有的 i n t e r n e t 无法有效地支持具有不同 特征的业务， 无法确保具有严格时延要求业务的q o s ( 服 务质量) 。因此从 1 9 9 6年起，对下一代 i n t e rn e t 的研究越来越受到广泛关注 1 -3 1 . 作为新一代的因特网技术， i n t e r n e t 2 从一开始提出 就把配置、 计算q o s 和进行q o s 管理作为一大目 标。 此外i n t e r n e t 2中还采用新的安全协议，对网络中数据的安全 提供更有效的支持;i n t e m e t 2 具有多播功能，多播发送方只需要发送一个数据包， 网络就负责将该数据包向多个目的地进行传送。i n t e me t 2的成功推广与应用，将 会推动远程教育、远程医疗、远程合作的开展，使得网络中视频、音频业务更加 丰富。 1 .2 q o s 概述 服务质量是指用户要求网络系统所必须保证的关于信息传输的质和量的特征 集，它反映服务提供者 ( 网络系统)和服务使用者 ( 用户)之间的能力和需求关 系，用来描述网 络的性能。能否为用户提供满意的服务，是一个网络技术能否生 存和发展的前提. q o s 无论对于a t m网络还是i n t e rn e t 都具有非常重要的意义。 q o s 的参数主要包括分组时延( d e l a y ) 、 时延抖动( d e l a y j i tt e r ) 、 丢失率( l o s s r a t e ) . a t m 4 - 5 1 技 术的 核心 是与q o s 紧密 联系 在一 起的。 a t m提供q o s 协商接口 ， 面向连接， 提供资源预留，采用连接允许控制、流量控制和拥塞控制等措施来确 保网 络的q o s . 2西安电 子科技大学博士学位论文: 分组调度算法及接入允许控制算法研究 巨里 里 巴 口组里 里 旦 巨 旦 纽 旦 里 巴 曰 目 旦 里 月皿旦 旦 旦旦 旦 理 i n t e r n e t 最初只支持单一的数据业务。 近年来，i e t f提出了多种业务模型和 机 制， 力 求 满 足 各 种q o s 要 求 1 1 。 其 中 主 要 包 括 : 综 合 服 务 / 资 源 预留( i n t e g r a t e d s e r v i c e s / r s v p ) 6 -2 1 1 模型，区分服务 ( d i ff e r e n t i a t e d s e r v i c e s ) 模型2 9 -3 0 1 ，多协议 标记交换 ( m p l s ) 3 一， 2 1 ，流量i程 ( t r a ff i c e n g in e e r in g ) 3 3 和受限选路 ( c o n s t r a in t - b a s e d r o u t in g ) 3 4 -3 6 等 这 些 都 在一 定 程度 上 加强了i n t e rn e t 对q o s 的支持能力。 综 合 服务 / 资 源预留 模 型 在 数 据 传 输前 首 先 要 通 过r s v p协 议 建 立 路 径 和预 约 资 源， 网 络节点 通过分 组 调度算 法 根据时 延 敏 感 类 业务 预留 的 带 宽 确 保其时 延上 限 。 综 合 服务 模型的 优点 是能 够充 分 地 保 障 业务 的q o s ， 但 是它 是需 要 记 录 和维 护 每 个 数 据 流的 状 态， 当网 络节 点中 存 在 大 量的 数 据 流时， 需 要占 用 较多的 资 源， 因而其可扩展性遭到质疑。 区 分 服 务的 思 想是 在网 络 边界 将 数 据 流 按 照 其q o s 要 求 进行 简 单分 类， 将同 种 类 型的 流 合 并 起 来 进 行 集 束 传 输 3 7 1 ， 流的 接 入 允 许 控 制 在网 络中 的 边缘 节 点 完 成 3 8 -4 2 1 。 每 一种 类型的 流 在网 络内 部 分别 进 行处 理， 分类的 工 作 在网 络的 入口 进 行， 每 个 分 组 被 标 识 为 一 定的 服务 类 型 ， 每 种 类型 的 分 组 都 按照 各自 的 流 量 控 制 策 略 进 入网 络。 网 络内 部的 路由 器 通 过 检 查 分 组 的 服 务 类 别 来决 定 将 分 组 置 入哪 一种队列，以 及当拥塞发生时如何丢弃分组。 目 前 区 分 服 务 将 不同 业 务 划 分 为 几 大 服务 类 型: 具 有 低时 延 及 低 时 延 抖 动的 特级 服务 4 3 1 ( p r e m iu m s e r v ic e ) , l l b e s t - e ff o rt可 靠性 更高的 确 信服务( a s s u r e d s e r v i c e ) 2 4 1 、以及 b e s t - e ff o rt服务。 为了 确 保 特 级 服 务 业 务 的 时 延， 在 路由 器中 特 级 服务 的 分 组比 其 它 类 别的 分 组 优 先 发 送， 系 统中 只 要 存 在 特 级 服 务 的 分 组， 它 们 就1 0 0 % 占 用 输出 链 路 带 宽 。 而 接 入 允 许 控 制 算 法 保 证 系 统 中 特 级 服 务 的 业 务 量 只占 总 业 务 量的 一 小 部 分( 要 在网 络中 的 每 个 路由 器 都作 到 这 一 点 需 要 依 靠 流 量 工 程以 及受 限 选路) ， 这 样 特 级 服 务的 业 务 到 达 速 率 就 远 小 于 其 服务 速 率， 其 低时 延 低 抖 动的 要 求 就 可以 被 满 足。 区 分 服务的 优点 是路由 器可以 凭分 组的 服务 类别 仅仅 依靠 优先级 机制 转发分 组， 实 现 简 单， 同 时 不 需 要 保存 每 个 业 务 流的 状 态 信 息， 可 扩 展 性 强。 但 是 它的 不 足 是目 前 无 法 确 保 端 到 端的 服 务 质 量。 原 因 在 于: 网 络 中 的 负 载时 刻 变 化， 如 果 流 量 工 程 和 受限 选 路 没 有 及时 反 映 网 络 负 载 的 变 化， 可 能 导 致 在网 络内 部 的 某 些 路由 器中 特 级 服务的 负 载 较 大， 特 级 服 务 的 时 延 要 求 将因 此 无 法 被 保 证。 另 外 各 类 实 时 业 务 的 吞 吐 率 与 时 延 要 求 相 差 各 异， 如 果 对 它 们 一 视 同 仁， 都 归 结 为 同 一 种 类 型 的 服 务 ， 在 满 足 各 类 业 务q o s 要 求 的 同 时 ， 难 免 会 使 系 统 带 宽 利 用 率 降 低。 为了克服区分服务的缺点， 4 4 4 5 1 中提出了 利用 c l o c k分组调度算 第一章 绪论3 里 里 巴 巴 里 巴 里 里 里 里 里 里 里 里 里 里 法，即由分组自 身携带业务流状态信息的系统模型。在这一模型中，业务流的状 态信息只在网络的边缘路由器中维护，在复用有大量业务流的核心路由器中不保 留状态信息。分组由 边缘路由 器进入网络后，边缘路由器将业务流的状态信息一记 录在每个分组中，核心路由器只负责更新这些状态信息。该模型可以确保实时业 务的时延，而且由于核心路由 器中不需要存储状态信息，故其可扩展性强。 1 .3分组调度算法及接入允许控制算法的作用 无论是在 a t m 网中还是在下一代 i n t e r n e t 中，分组调度算法及其接入允许控 制算法都在确保q o s 方面起着至关重要的作用。 连 接 1 一 一-州卜 连 接 2 输 出 分 组 调 度 器 口 口 口 连 接 3 卜 啼几 石 蔽露- 一 连 接 4 图1 . 1 分组调度器模型 图 1 . 1中给出了一个分组调度的模型。交换机和路由器的输出端口和输出链 路，通常被大量连接 a t m 中称为连接，i n t e rn e t中称为流，为了方便起见，本 文中将二者统称为连接)所复用。分组调度算法的作用就是根据一定的规则选择 分组输出到输出链路上。分组调度算法决定着分组的输出次序，因此它决定着分 组的时延、时延抖动。另外如果一个连接中的分组在较长时间内得不到服务，该 连接的队列就有可能溢出，因此分组调度算法也影响着分组丢失率。由此可见分 组调度算法与q o s 关系十分密切。由 于调度器相当 于排队论中的 服务器，因此本 文中也把调度器和调度算法分别称为服务器和服务规则。 由 于服务规则不同，不同的调度算法对于 q o s的 支持能力也不同。例如在 i n t e rn e t 的路由 器中广泛采用的先来先服务 ( f c f s )算法， 在实时业务与非实时 业务共存的情况下，即便系统中的带宽很宽，实时业务分组的时延也都无法被确 保。这是因为如果一个实时业务的分组在大量非实时业务的分组之后到达系统， 它将不得不等到所有先到的分组离去后才能得到服务。同样，采用简单的优先级 机制，高优先级业务的分组永远在低优先级业务的分组前得到服务，低优先级业 务的时延就难以 保证。 在综合业务的环境下，一个良 好的调度算法应该能够满足 第一章 绪论 前，只有连接 1 、连接 2存在积压分组，它们分享系统带宽， 服 务 速 率 均 为 c2 在 看出 时 刻 之 后 ， 连 接 3 也 被 积 压 ， 于 是 三 个 连 接 的 服 务 速 率 分 别 为 导 导 号 可 以 ， 在g p s 算法中各连接是根据其权值共享系统带宽的。 g p s 算法有三大特点: 第一， 只要连接i 被积压， g p s 服务器就保障以一定的速率为其服务。 设v为g p s 系 统 中 复 用 的 连 接 集