（计算机软件与理论专业论文）atm交换网优先级控制的研究.pdf

y6 j 8 弓( 7 a 论文题目：a t m 交换网优先级控制的研究 专业：计算机软件与理论研究生：吕磊指导老o i l i 逯昭义 摘要 现代计算机通信网正朝着a t m 交换网和宽带综合业务数字网( b i s d n ) 的方 向发展，其服务业务包括话音、数据、传真和视频等。每种业务都有不同的统计特 性并需要不同的服务质量( q o s ) 。为了充分利用网络资源并满足每种业务的q o s ， 需要进行优先级控制。但原有网络协议中的优先级控制只适用于优先级较少的情况， 需要进行改进。为了找到更适合在综合业务中使用的优先级服务策略，本文对 i e e e 8 0 2 4 协议优先级进行了改进，改善了原协议中低优先级数据长时间得不到发 送的局面。 在对局域网与广域网中的优先级策略研究的基础上。本论文对优先级调度输入 线群多通道输出a t m 交换系统提出了如下的扩展肯达尔( k e n d a l l ) 模型 a g t ：冀蛩妻器慧 f c f s ( 对于同类信元) 非典型非占先式p r ( 对于不同类信元) ，然后本文利用平均值法对该非典型非占先式p r 模型进行了数学建模和解析。该 研究进展，本文是首次进行的，与典型非占先式p r 相比，该模型更准确地表达了 优先级调度输入线群多通道输出a t m 交换系统的特性。仿真实验表明优先级调 度输入线群多通道输出a t m 交换系统比较好地改善了h o l 阻塞，提高了输入 排队a t m 交换网络的性能。 关键词输入排队a t m 网络优先级建模研究 答辩日期：指导教师签字 t h er e s e a r c ho n p r i o r i t y c o n t r o li na t mn e t w o r k a b s t r a c t m o d e m c 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 i sh e a d i n gf o ra t m s w i t c h i n gn e t w o r k s a n db i s d n ，w h i c hi n t e g r a t e dv a r i o u st r a f l i c ss u c ha sv o i c e ，d a t a ，f a xa n dv i d e o e a c h t y p eo ft r a f f i ch a sd i f f e r e n tt r a f f i cc h a r a c t e r i s t i ca n dr e q u i r e sd i f f e r e n tq u a l i t yo f s e r v i c e ( q o s ) t h u s ，ap r o p e rp r i o r i t yc o n t r o li sn e e d e di no r d e rt ou t i l i z et h en e t w o r kr e s o u r c e s e f f i c i e n t l ya n ds a t i s f yt h eq o s o fe a c ht r a f f i c h o w e v e r , t h ep r i o r i t yc o n t r o ls t r a t e g yi n p r i m a r yp r o t o c o lo n l ya d a p t st ot h es t a t ew i t hf e w r a n k s i tn e e d st ob ei m p r o v e dt oa d a p t t oa t ma n db i s d n i nt h i sp a p e r , i no r d e rt of i n dam o r e p r o p e rp r i o r i t yc o n t r o ls t r a t e g y w h i c hc a nh eu s e di ni n t e g r a t e ds e r v i c e s ，a ni m p r o v e ds t r a t e g yi ni e e e s 0 2 4t o k e nb u s p r o t o c o l i sp r o p o s e dw h i c hc a n p r e v e n t t h el o wr a n k si n f o r m a t i o nw a i t i n gf o ral o n gt i m e b a s e do nt h er e s e a r c ho fp r i o r i t y s t r a t e g yo nj o c a la r e an e t w o r ka n dw i d ea r e a n e t w o r k ，i nt h i st h e s i s ，w ep u tf o r w a r da ne x t e n d e dk e n d a l lm o d e lf o rt h ep r i o r i t y s c h e d u l i n gi n p u t l i n eg r o u po u t p u t w i t l lm u l t i - c h a n n e li na t m e x c h a n g es y s t e m a g 1 l 1 ：t h e s z e0 f b u 髓r 1 f c f s ( f o r s a m ek j n d s “c e l l s ) l 2 ：t h es i z eo f b u 仃e r 2 n o n - t y p i c a ln o n - p r e v a i lp rf f o rd i f f e r e n tk i n d so f c e l l s ) a n dt h e nu s et h ea v e r a g em e t h o dt om o d e la n da n a l y z em a t h e m a t i c a l l yt h en o n t y p i c a l a n dn o n - a n t i c i p a t i v ep rm o d e l t h i sr e s e a r c hi sf i r s t l ys t u d i e di nt h i sp a p e r c o m p a r e d w i t ht h e t y p i c a l a n d n o n a n t i c i p a t i v e p rm o d e l ，i t e x p r e s s e s m o r e e x a c t l y t h e c h a r a c t e r i s t i c so ft h ep r i o r i t ys c h e d u l i n gi n p u t l i n eg r o u po u t p u tw i t hm u l t i c h a n n e l i na t m e x c h a n g es y s t e m t h ef i n a ls i m u l a t i o ne x p e r i m e n ts h o w st h a tt h i sm o d e lc a l l b e t t e rt h eh o lb l o c k ，a n d i m p r o v et h ep e r f o r m a n c eo fi n p u t q u e u e da t ms w i t c h d r a m a t i c a l l y l v l c i ( c o m p u t e r s o f t w a r ea n d t h e o r y ) d i r e c t e db y l u z h a o y i k e y w o r d si n p u t q u e u e d a r mn e t w o r k p r i o r i t y m o d e l i n gr e s e a r c h 第1 章引言 第1 章引言 计算机通信网络发展的早期，数据传输的优先级控制策略就得到重要应用。 而现代计算机通信网正朝着a t m 交换网和宽带综合业务数字网( b i s d n ) 的方 向发展，其服务业务包括话音、数据、传真和视频等。每种业务都有不同的统计 特性并需要不同的服务质量( q o s ) 。为了充分利用网络资源并满足各种业务的 q o s ，更需要进行优先级控制，即根据不同业务传输信元的特性，将信元标以不 同的优先级。 然而要将数据通信网中的优先级策略直接应用到a t m 交换网和宽带综合业 务数字网中，还有一定的困难与不足，必须对宽带综合业务数字网中的优先级策 略进行创新性研究，包括将原有数据通信协议中的优先级策略扩展到a t m 交换网 和宽带综合业务数字网的研究中来。扩展的关键问题是综合业务网中的优先级较 多，而原来数据通信网中优先级较少。由于数据通信网中只传送一种业务一数据， 通常全网优先级取两个级别( 即非优先级和优先级) 。如果取三个级别( 0 ，1 ，2 三级，0 级为非优先级，2 级最高) 就更好【1 ，2 ，3 1 。由于级别少，能较好地兼顾低优 先级数据的传送。但在综合业务中，至少涉及到数据、话音、静止图像、活动图 像4 种业务，全网优先级至少涉及8 个级别。在优先级较多的情况下，低优先级 业务特别是最低优先级业务往往得不到应有的服务。因此，在将原有协议中的优 先级策略扩展到a t m 交换网和宽带综合业务数字网中时，如何在保证高优先级业 务得到及时服务的同时，尽量兼顾低优先级业务的服务质量是需要重视的问题。 这个问题正是本文前期研究中提出的优先级“准公平性”问题。关于准公平性问 题，在本文前期的研究工作中已取得较大进展。其研究报告的学术论文已在国家 核心刊物“计算机工程与应用”发表1 4 。 为了对a t m 交换网和宽带综合业务数字网的优先级策略进行创新研究，需要 对其进行建模研究，包括数学建模和仿真建模。在a t m 交换网和综合业务数字网 中，交换节点、复用器以及业务接入点等处均有缓冲区来实现对信元的收发以及 缓存。信元到达排队系统后还要根据其优先级采取相应的排队策略，这是一个多 优先级排队问题。利用排队理论分析优先级控制下信元排队的等待时间，滞留时 间，系统长度等关键参数，对于a t m 交换节点、复用器以及业务接入等设备的设 计是至关重要的，对业务控制策略的选择同样也是很重要的。 l 第l 章引言 在对局域网与广域网中的优先级策略综述的基础上，本论文对优先级调度输 入线群多通道输出a t m 交换系统提出了如下的等效系统模型， 出信道 顾客到达! 在排队室排队!服务员服务i 顾客离开 在重负载下，经过分析得到了该系统模型的肯达尔( k e n d a l l ) 扩展模型。 a g 胜羹默萎豁鬟；嚣磊予不同类 该非典型非占先式p r 服务模型虽然在有关文献中也曾提出过i 卯，但并未进一 步建立数学模型和仿真实验。为此，经深入研究本文就非典型非占先式p r 服务 的扩展肯达尔模型进行了数学解析及模拟实验，解决了重负载下一种a t m 交换网 的性能评价。该研究进展本文是首次进行的。 2 第2 章本文的前期研究进展 第2 章本文的前期研究进展 本文的前期研究工作，对优先级所涉及的准公平性问题进行了深入讨论f 4 1 。针 对i e e e 8 0 2 4 协议，提出“高优先级中断策略”。 1 i e e e 8 0 2 4m a c 层协议简介 i e e e 8 0 2 4 优先级协议是人们熟知的协议1 6 r 1 ，为了在综合业务中改进该协议， 不妨略加简介。 令牌总线介质访问控制的基本操作包括两个状态，一个是信息传送状态，另一 个是令牌传送状态。令牌控制发送权，取得令牌的站就有权在特定的时间内发送帧。 令牌在站之间的传递是在逻辑环上进行的，在逻辑环上的每个站由三个地址决定它 的位置，即本站地址( z s ) ，前趋站地址( p s ) 和后继站地址( n s ) 。前趋站地址( p s ) 和后继站地址( n s ) 可以动态地设置和保持。环上运行的信息帧分为数据帧和m a c 控制帧。m a c 控制帧用于环的维护、环的初始化、新站的插入和站的删除等功能。 在逻辑环上的令牌( 短帧的形式，代表发送权) ，依次从站地址大的站传递给站 地址小的站，最后由最小地址的站把令牌交给最大地址的站。工作站接收了令牌时 才能发送数据，整个数据发送结束，把令牌传送给下一站。 令牌总线为数据定义了0 、2 、4 和6 四种优先级。最低为0 ，最高为6 。任何站 点都可以按这中间的一种或多种方式来发送数据。自然，对6 类帧最优先发送。但 为了防止某个工作站长时间独占网络频宽而发送6 类帧，规定了一个最大令牌保持 时间。当发送时间超过了这个保持时间，即使某个站还有6 类帧，也要停止发送， 必须等待下一次令牌到达时，才能发送。 对不同优先级，具有不同的令牌保持时间，用瓦表示，则 瓦：定常时间用瓦表示 丘= 6 j m a x ( 0 ，乃w r t r y ) ，用瓦表示，k = 4 ，2 ，0 其中，m r 为网上设定的目标令牌循环时间，豫r 为实际测量的令牌循环逻 辑环一周的时间，它等于本站自上次接收到令牌至当前接收到令牌所经过的时间。 规定它们的时间单位为帧的数目。 2 改进策略的提出 由上述优先级的运行机理可知，优先级较高的信息帧很容易获得发送权，而优 第2 章本文的前期研究进展 先级较低的信息帧则相对较难，特别是当网络负载较重、用户争先利用高优先级发 送信息帧时低优先级信息帧往往在很长时间内得不到发送。为了在尽可能保证高 优先级信息帧提前得到服务的同时，又防止出现低优先级信息帧( 特别是最低优先 级信息帧) 长时间得不到服务的局面，对i e e e 8 0 2 4 优先级进行了以下改进。 逻辑上将m a c 层划分成四小部分，暂且称为子域，分别对应四个优先级。每 个子域各有1 个虚拟缓存。当数据从上层进入m a c 层时，先检查其优先级，然后 送到对应的一个子域。于是各子分域分别管理自己缓存的帧发送队列。 当令牌到达时，就被传递给优先级为6 的子域，对6 类优先级的信息帧最优先 发送。通常为6 类帧规定了一个最大令牌保持时间，它不受目标令牌循环时间的影 响，在规定的最大令牌保持时间内，只要有6 类帧就接连发送之，有多少6 类帧就 发送多少6 类帧。 当6 类子域发送完所有帧或超时时，令牌被交给优先级为4 的子域。改进策略 预先为4 、2 、0 类帧各规定了一个目标令牌循环时间丌冗、7 豫瓦、z 豫矗，而不是 象i e e e 8 0 2 4 那样只规定1 个目标令牌循环时间力w r 4 类子域能发送4 类信息帧 的最大数目= 4 类帧目标令牌循环时间一当前站实际测量的令牌循环时间= 7 豫一，r e ， 然后令牌又传递给优先级为2 的子域，可发送2 类帧的最大数目= 2 类帧目标 令牌循环时间一当前站实际测量的令牌循环时间一当前站发送的4 类帧的实际数 目= r 豫t 一豫贮一当前站发送的4 类帧的实际数目。 最后令牌传递给优先级为0 的子域。可发送0 类帧的最大数目= 0 类帧目标令 牌循环时间一当前站实际测量的令牌循环时间一当前站发送的4 类帧的实际数目 一当前站发送的2 类帧的实际数目= r 豫瓦一豫c 一当前站发送的4 类帧的实际数 目一当前站发送的2 类帧的实际数目。 设瓦为各站点当前可以发送不同优先级信息帧的最大数目。k = 6 ，4 ，2 ，0 ， 其中瓦为最高优先级帧的值，通常为定长时间。设、e 表示各站本次发送优先级 4 、优先级2 信息帧的实际帧数，则 = m a x ( o 。7 了w 一豫e ) t2 m a x ( 0 ，刀w e 一豫一只) ( 1 ) 瓦2 m a x ( 0 r r n r o r r r c e ) 第2 章本文的前期研究进展 由上述设定可见，当前站能发送优先级k ( 6 类除外) 的帧数与两个条件有关： 与豫r 有关：与当前发送的较高优先级信息帧的帧数有关。 ( 1 ) 在网络负载较轻时，6 类、4 类、2 类、0 类优先级的信息帧都有可能得到发 送，但在网络负载较重的情况下，每个站点6 类帧的发送有可能达到其最大值，即疋 因此，对于一个有站点的环网，在令牌循环一圈中，能传输第6 类信息帧的最大 时间是瓦，显然为了保证在任何条件下结点还能发送4 类优先级的信息帧，只 有满足丌r 五 瓦 ( 2 ) 由( 1 ) 式可知，当每个站4 类优先级帧的发送达到其最大值时，可得2 类帧 发送数目的最大值为 t 2m a x ( 0 ，m 一豫i 一) l 吐= m a x ( 0 ，m 一豫乏一l ) = m a x ( 0 珊t 一豫正一m a ) 【( 0 ，m 一豫c ) ) 2 m a x ( 0 ，m 正一珊l ) ( 2 ) 若m 瓦的值小于等于玎踢，则是= m a x ( 0 ，m l r r r r , ) = 0 ：即若丁了兄乏的值小 于等于7 豫瓦，2 类帧有可能长时间得不到发送。显然为了保证在任何条件下，结点 还能发送2 类帧，只有m 疋一m l o ，即丌r t m ( 3 ) 同样的道理，为了保证在任何条件下，结点还能发送0 类帧，只有满足r 豫矗一 m 正 o ，即m 瓦 m 瓦 当网络负载较重时，为了保证在任何条件下，让高优先级信息尽可能提前发送 的前提下，如何兼顾低优先级信息，使之有可能得到传送，本文提出将目标令牌循 环时间t t r t 按优先级不同丽分别设定且让其满足m 气 m m l 这就是对原 i e e e s 0 2 4 优先级协议的改进策略l ，另外还同时要兼顾改进策略2 ，稍后阐述。 根据上述分析，我们可以看出，改进后的i e e e s 0 2 4 协议保证了0 类帧的服务 质量。站点接到令牌后，若其能发送4 类帧，那么可发送的4 类帧的最大数目不超 过r r r r , 一豫不，故令牌传至2 类子域时其实测时间最大为豫i + ( 7 豫一孺7 ：_ ) = f r e t , 由于玎r 瓦 玎r ，站点必能发2 类帧。同理，当2 类子域接到令牌后，若能发2 类 第2 章本文的前期研究进展 帧，站点发送完2 类帧，将令牌传至0 类子域时，其实测时间豫i 最大不超过玎r t 由于力w 瓦 7 豫l ，所以也必能发0 类帧。总的来说改进后的i e e e 8 0 2 4 协议保证 了最低优先级帧的发送。 然而上述改进协议也存在着不足，当站点接收令牌后，若其豫c 仃w 五，r r n r o ) ， 则因为出现豫t 刑，不能发4 类帧，而同时由于r r n r o 豫t ，必可发0 类帧。 也就是造成高优先级信息帧得不到发送的条件下，而低优先级信息帧却可发送。出 现优先级倒置情况。为此需要对改进后的策略l 进一步加以修正，提出改进策略2 ， 即高优先级中断策略。若站点4 类子域接收令牌后，不能发4 类帧，则令牌不再传 送到该站点的2 类予域及0 类子域，强制性的将令牌传至下游站，即使本站的豫r 小 于m 或珊瓦，也是如此。这就保证了若4 类帧不能发，则2 类、0 类帧必定不能 发；若4 类帧能发，2 类、0 类帧必能发。另外，当令牌经4 类子域发送后进入2 类 子域时，如果2 类帧不能发，则0 类帧必不能发送。故不需对2 类子域设置优先级 中断策略。 综上所述，对原有的i e e e 8 0 2 4 协议我们做了如下两点改进： 为4 类、2 类、0 类优先级信息帧分别设立了目标令牌循环时间，且满足m c 7 豫正 m 五从而适当照顾了低优先级信息帧的发送。 为4 类子域设定了高优先级中断策略，防止了某站有4 类帧而不能发送，却 有可能发2 类、0 类帧的优先级倒置局面出现。 改进后的i e e e 8 0 2 4 协议具有很大的灵活性，在网络负载轻时，调节目标令牌 循环时间，使m 瓦= m t = m 瓦= t t r t ，网络按原协议运行；当网络负载较重时， 调节m 疋、m 瓦，使m 瓦大于m 瓦，m 五略大于m 瓦，适当照顾低优先级的发 送；当网络负载重时，进一步调大r r n r ：、r r n r o ，以较好的保证低优先级( 特别是最 低优先级) 信息帧的发送。 为了比较原i e e e 8 0 2 4 协议和改进的i e e e 8 0 2 4 协议，下面举例画出令牌沿逻 辑环旋转图。如图1 ( a ) 、( b ) 所示。设瓦= 5 帧时间( 以帧为单位，帧长固定) 。设 肿= 5 6 ，力翟t - - 5 8 ，仃r 兀= 5 9 ，1 7 r t = 5 9 设环网由八个站组成，即i = 0 ，l ，2 ，3 ， 第2 章本文的前期研究进展 4 ，5 ，6 7 x m i t 为各站点发送帧的数目。设多次循环的总计时为( 总t r t ) 。e ， 为各站实发的6 类、4 类、2 类、0 类帧的数目。 矗五壬正墨一矗五五百南 瞰( 船m 霹m 种oe 珥 剖 e = 4 仍 d 锄 酷圩爿 e j 。 ：0 丘砷 母e = 5 6 ：o 町 e = 0 e 曲 石q e = 0 片踯 面 e ：5 e ：0 e 椰 5 硼 e e ：0 旧 一 ：o e = 0 e m e 铂 e 劬 五却 * e 彻 e 2 劬 丘：0 5 e 寺 曲 e 爿 e ：o 丘劬 璎懈d 碑m 循哪勰m 砬m 街5 币伽4 4e = 5 船丘珥僻) 国e ：8 e qe = 8e = 0厅却 = 3e ：7压= 0e = 0 砘丘：05 却聊 0 母) 仪e = 5 f = 0 e 田 五司 口曲国e ：5 古钔 印 e 劬 钾i ) 鄹e ：5 ：o 劬 钔 毋国e 为 丘铀 町 丘铀 e e 田 丘锄 ( 蛳$ e 片却 丘 ) e 却 4 4e e 1 5 e ：o e ：0 e = 5 片= 3 e ：3 e = 8 ( 1 鳓斟丘叫 丘：0 e 司 e ：0 口m e ：5 w e 揶 e = o 口商田e ：6 f = o 尼自 币 f f = 0 = o 丘：0 鳓e = 5 f = 0 丘：0 e = 5 脚 f = 0 丘劬 伍l 田e ：5 = o e 司 片钿 0 唧4 4e = 5 e l l e = 0 5 l 丘= 5 e 劬 聊 田e e 劬 【瑚) 劬丘= 5 e = 0 = 0 石面 ( 1 劢4 4 e 韦 捌5 ：0 e 却 品e = 5 e 叩 e 劬 锄) 田e = 5e ：5 5 铂五：o 丘= 05 = 0 耳目j 印 鲫国丘= 5s = s 5 = 0e 劬 5 = oe 司 e ：0脚 e = 5 坶固丘：5 j i = of = o e 0e = 0 斥毋斥劬 卿国斥丢固五= 6 脚e = 0 卿e ：0 职，鼬 佑m 田曙乇g 国舶丘毛 脚e m e = oe = 0 辱日斥m ( a ) 原协议令牌轮转图 7 啮跏砸珥舸l 啊m 仃1 ) 7 1 e 珥衢e = 5 由礓舯， 5 e 铀e = 0 丘劬 压= 0e 劬，= 0 5 0i 目脚 ( 1 神位e = 5 = 0 厅= 0 ( 1 蚴毋e 爿 疗 e 司 e = o 4 4 e = 5 目5 丘二0 e 司 曲i ) g e f = 4 丘铀 脚 目e 丘= o 疗= 0 丘= 0 ( 4 0 0 ) 田丘= 5 e = 0 厅砷 印脯 片= 0 e j l 翱e ：0 丘= o e 司 ( i 卿6 3e = 6 e 哪 疗 石劬 l 蛐e e ：1 丘劬 e ：0 me c 钔 丘砷 4 4 乎1 s e = 0 斥= 0 $ e 4 e = o 臼墙e 为 f 砷 丘：0 尊= 5 ； j 正q l e e = 0 = 0 厅劬 0 4 3 ) 鸱e = 5 ：0 f = 0 厅司 5 0 鄹 岛 聊 1 ) 丘书 ，砷 丘却 e = 0 向b e 斥目 疗m 席钟 侮0 搿五巧 斤= 1 5 片= 0 e = 0 ( 4 1 9 ) 5 5e 弓 e 爿 司 e = o $ e 片= 0 ：o ， e 丘哪 f 钿 e 铀 劬 籼 脯删翩鼬 岛嘞 第2 章本文的前期研究进展 妄i 妄c 无王正五石矗 瞰( 拼功婀x m l 蛐。丘爿 戽i l e 司 e 爿 髑) 描丘爿 f ：0 加 片却 g e ：6 ： e ：0 m e r ：0 丘司 5 9 e 呻 旧 一 砷 五劬 ( 3 m i 辫e ：6 m 丘= 0 劬 e 叩 ( 4 4 蛐 e 。1 2 e 砼 e ：i ( 蝴) 5 5 e 彻 e ；l 砘 e ：i ( 1 姗m ：m t c 种2 6e 苒 f 爿 e = 3 e 娟 f 砷 = 0 e 加 ( i s 3 ) 6 1e ：6 ：0 e m ( 2 1 0 ) 5 7 丘毛 f 劬 e 司 e = 0 ( 栅d 珥m ( 尊咖珥m 蛳n 4 1e 二5 日曲阱e 爿 嘟) 国丘= 3 万：8e 卸钔 巧= 6e = 06 却 丘 丘铘丘：0 e e 司 e l 鲫6 4e 目 f 铘 e 砷 e 卸 锄对5 7 = s f 却 e d 凹i ) 6 1e c 硐6 1e = 6 e = 0e 劬 e = 0e 劬 5 却e 卸 田e = 5 回国丘：5 e 砷e m 五= 0= 0 e 甜e = o 6 ( ：t 9 0 6 = 0丘啡 = o5 丘曲e 铘 5 0e e 5 = 0e l e 钟5 ：0 耳= 0丘却 4 4e 斥u e e = j ( 1 删4 4 丘= 6 斥l l e 司 e ：l ( t 6 z , 5 4e ：6 f 宅 e 号 e = l 嘶5 8 丘弓 f 钔 石= 0 i ) 6 1e 苒 e 巾 e = 0 e = 5 e 司 e 加 5 0e e 却 e = 0 ( 翻) e = 5 f = 0 丘司 0 曲5 9 = 6 ( 5 1 7 ) 5 9e = 5 司e 砷 e 却e 劬 e = 0e 揶 ( 啪) 哪c 面 丘砷 劬 e ：0 f i 协4 4 丘= 5 f , - - 1 2 f , - - 2 e = 】 瞬辩= 5 e ：3 丘= 2 丘：i a 嘲6 1e = 6 e = 0 e = 0 捌 f m e 劬 e 丘= 0 e ：o 疙：0 国丘每 f 卸 e = 0 鼬 仨必：5 f = 0 e 钏 ( 姗田m 孵 埘w n 仃i ) 7 1 乓叫o s ) 7 5 丘弓卸舯酗 e = 0e m尉) e = 0e 目唧 e = 05 m唧 ( 1 叻窜丘爿 丘m f ：0 e 哪 c 础4 4e ：5 e 口 e = 2 e = i 囟1 ) 5 5 丘= 5 f = t e = i e ：6 e 哪 ：0 e 司 ( 删$ e e 砷 硇 = 0 ( 蜘e e 钿 5 硼 e 钿 e 丘砷 ：0 e ：0 ( b ) 加入高优先级中断策略的扩展仇议 图l 令牌轮转图 8 丘高 五钿 e = 0 e 踯 ( 1 9 6 ) 爨e 气佃i ) 辅目 e=0，o 卸 f , - o e = 0印 嘲n me = 6 e 硼 e = 0 c t l j o ) 4 4 坛巧 扛1 2 丘：l 0 嘟5 6e = 5 e = 1 e = 2 e = l “娜瓣五韦 丘j i 五 ) “脚5 9e 韦 丘：0 e 司 f i 9e f = n e 钏 岱i ) 8 1 ) 五鬲 e = 0 5 郇 e = 0 e e m e 司 4 4e f , = t 2 五宅 e 2 l ( 4 1 9 ) 5 5e = 5 = i ：2 丘= i 4 e = 0 丘：0 ( s 3 7 ) 5 9 丘韦 = 0 丘印 丘却 茁 科 弓却铘钟 e 乓e 回哪 钿劬砷 五5 e e 慢荤 即聊 噼辩 第2 章本文的前期研究进展 3 改进策略在网中的实现 ( a ) 设置两种计时器，即令牌循环计时器( t r t ) ，令牌保持计时器( t h t ) 。 t r t ：测量从上一次接收令牌到第二次令牌到达的时间，其计时值为豫z ，当 站点接收令牌后，赋t r t 的值豫e 给t h t ，同时t r t 清零并同时开始重新计时。 t h t ：保存t r t 的值豫t 后，暂时保持不动，等待在站点发送完6 类帧后， 在值豫r 基础上继续计时。 ( b ) 网络中每个站点设置3 个只读存储器分别存储丌r 矗，力喂正，m 兀目标令牌 循环时间。这三个时间必须预先设定，供结点中发送控制器发送各类帧时，计算各 类优先级帧可发送的最大时间( 即计算瓦，k = 4 。2 ，0 ) 时使用。 下面讨论各站点发送规则，设网络运行之初各站点的令牌循环计时器从t r t = 0 开始计时。当某站下一次重新获得令牌后，发送规则如下： t r t 将计时值豫l 保存在t h t 中，t r t 清零，并重新开始计时。 站点内部将令牌传递给优先级为6 的子域。当该子域发送完6 类帧或超时时， 停止发送6 类帧，并将令牌交给优先级为4 的子域。在发送6 类帧时，t h t 只保持 豫c 值，不累加计时，但各站t r t 要计时。 优先级为4 的子域开始发送4 类帧。若力喁一豫c 0 则不能发4 类帧， 立即把令牌传至下游站：若r 豫一豫i 0 ，则发送4 类帧。在4 类帧开始发送时 t h t 从保持的豫值开始累加计时。当该子域发送完4 类帧或超出发送时间时停止 发送，将令牌交优先级为2 的子域。在发送4 类帧时，不仅t h t 计时，各站的t r t 也继续计时。 优先级为2 的子域开时发送2 类帧。发送时间不超过m t 一豫t c = 玎兄t 一( 豫+ ) ，其中豫i + 正是t h t 的当前值。当该子域发送完2 类帧或超 出发送时间时停止发送，将令牌交给优先级为0 的子域。在发送2 类帧时，不仅t h t 计时，各站t r t 也继续计时。 优先级为0 的子域开时发送0 类帧，发送值不超过7 豫瓦一豫t 一一e = 9 第2 章本文的前期研究进展 m 瓦一( 豫i + + ) ，同理t r t , + 只+ 正是t h t 的当前值。当该子域发送完0 类帧或超出发送时间时停止发送，令牌传送下游站。勿论，在发送0 类帧时，各工 作站t r t 要继续计时。显然由于t h t 的计时及累加计时，完成了各类信息帧最大 发送值的计算任务。完成计算后，t h t 就应该清零，供令牌下一次到达本站时再重 新承担计时任务。 关于高优先级中断策略研究的仿真建模，限于篇幅不再赘述，请参见文献“1 。 第3 章局域网与广域网中的优先级策略 第3 章局域网与广域网中的优先级策略 网络发展到现在，要求的不仅仅是高速度、宽频带，更要求能够支持多媒体应 用，支持较简单的网络管理策略。而进行优先级控制是提高综合业务网络服务质量 ( q o s ) 的有效手段。有关优先级的多种控制机制已被广泛用于流量控制，拥塞控 制，缓冲区管理和带宽管理。目前出现的优先级控制可以分为三类：服务优先级( 即 顾客服务优先级，也称时间优先级) 、缓冲优先级( 即排队优先级，要考虑排队室溢 出，也称空间优先级) 和服务员优先级( 要考虑服务员能力，也称人力优先级) 。从 应用角度讲，有关优先级的研究主要集中在两方面：接入控制和存储转发机制，即 服务控制和缓存控制。下面就局域网和广域网分别阐述。 一、局域网 局域网一般是多个结点共享传输介质，在一个结点发送数据之前首先要解决由 哪个结点占用传输介质，妥善解决共享通道而有可能发生冲突的问题。局域网的主 要标准有：i e e e 8 0 2 3 、i e e e 8 0 2 4 、i e e e 8 0 2 5 、i e e e 8 0 2 6 、f d d i 这些协议标准 有的原来并没有优先级机制，如1 9 8 0 年颁布的i e e e 8 0 2 t 3 标准主要针对数据交换， 而不提供服务质量和优先级控制。千兆以太网继承了这一协议，也就继承了它的缺 点。因此，千兆以太网虽然具有速度快且简单实用的优点，却不能提供真正意义上 的服务质量q o s ，从而不适用于对延时敏感的多媒体应用等实时业务。 时至今日，实现q o s 很重要的一个要求是能够进行优先级控制。因此，人们尝 试在原来没有优先级机制的协议中引入优先级，或对原来就有优先级机制的协议进 行改进，以期让它们能够提供更高质量的优先级服务，局域网中的优先级机制一般 属于时间优先级。 1 将预约机制引入以太网实现优先级控制 基本思想是：在每个以太网结点内部都维持一张预约表，表的长度是网内结点 的数目，每一个表项对应一个节点，表项内容包括逻辑结点号、是否预约和预约的 优先级。初始化预约表的过程如下：将冲突后的以太网传输时间划分为一个个时间 片，在每个时间片里，节点根据自己的逻辑节点号顺序依次申明自己的预约和所要 求的优先级。网上的所有节点聆昕这些申明，并据此更新自己的预约表。 由逻辑节点号和预约优先级共同决定发送次序，高优先级的预约先于低优先级 的预约得到满足，同级预约中逻辑节点号低的先于逻辑节点号高的得到满足，未进 行预约的帧必须等到高优先级或同级预约被满足后才有资格发送。每一个节点都必 须遵守这张预约表，但是未预约的高优先级帧可以中断低优先级帧，优先发送，丽 披干扰的低优先级帧必须多等待一个帧的时间才能按预约表发送【。 第3 章局域网与广域网中的优先级策略 采用预约表可以有效降低网络的冲突率。与传统的c s m a c d 算法相比，它能 实现在保证低负荷情况下的低等待时间的同时，实现重负荷情况下极低的冲突率。 该方法的另一个优点是采用分布式优先级控制，在每一个节点内维护一个预约表， 而不是采用一个中心控制节点来实施优先级控制。这虽然付出了一些内存上的代价， 却继承了以太网分布式控制的思想，增加了可靠性、健壮性和实现上的简单性。 2 轮询中的优先级机制 轮询系统是多个独立的信元共享一个设备的系统，此设备一般为传输信道。其 基本工作过程为：在网内有一个中央控制器及服务器担任对每一个站点的探询工作， 探询按顺序进行，两个队列之间的探询时间称为步行时间，接收探询的队列获得访 问信道的机会，如果该站有要发送的数据，它可以利用信道的全部数据速率将数据 送往目的地：否则，中央控制器继续对下一个队列探询【9 】。 在轮询系统中设立优先级机制的方法很多，比如在中央控制器中设置优先级， 优先级的大小根据当前网络运行状态设定，当中央控制器对每一个站点探询时，在 接收探询的队列中只有优先级等于或高于中央控制器优先级的数据才能被送往目的 地，而低于中央控制器优先级的数据将得不到服务。 3 i e e e 8 0 2 3 中的分优先级控制机制 在i e e e s 0 2 3 中用户共享传输介质，由于采用随机接入来存取介质，就可能出 现多个用户同时发送信息而冲突，这时冲突各站都要后退重发。有关文献提出了多 优先级随机接入算法( r a a u m p 算法) ，此算法可以在系统接近拥塞时，有效地拒 绝低优先级的业务，保证高优先级业务的业务质量。又有人对其进行了改造，提出 了一种分优先级随机接入控制算法【l o i ，大致思想是采用以太网的冲突后退方式，只 是当冲突发生时，让高优先级数据后退一段很短的时间重发，而低优先级数据后退 一段较长的时间重发，从而保证了高优先级数据的尽快发送。 4 i e e e 8 0 2 4 中的优先级控制 1 e e e 8 0 2 4 令牌总线网协议也有相应的优先权机制，站内为各优先级设置独立 的缓冲区，当某工作站点接到令牌时，令牌在站点内部从最高优先级传往最低优先 级。当某一级别接到令牌后，在此级别缓冲区排队的信息将被传送，直到队长为0 或计时结束。有关文献导出了i e e e 8 0 2 4 令牌总线网在重负载条件下的循环时间和 吞吐量指标，在假设各级的信道并不总是满负荷的条件下，要导出平均循环时间和 平均信元服务时间的分析表达式是十分困难的。在很多文献中，对这类情况的处理 是对每级求出它的平均循环时间和平均信元服务时间的上下限，而非具体地提出表 达式。针对这点不足，有关文献i l l j 研究了i e e e 8 0 2 4 标准协议各项性能指标的一般 算法，算法中重点考虑了i e e e 8 0 2 4 标准协议用于实时通信的4 类通信优先级别，2 第3 章局域网与广域网中的优先级策略 种类型时间控制器：令牌保持时间和令牌循环时间。此外还考虑了网络中各站点具 有有限的缓冲区容量、不同的信元产生率和不同的网络服务时间等参数的限制。文 献【4 1 对i e e e 8 0 2 4 标准协议优先级准公平性进行了研究，对原有的i e e e 8 0 2 4 协议做 了如下两点改进：为4 类、2 类、0 类优先级信息帧分别设立了目标令牌循环时 间，且满足m 瓦 力偬t 仃冀从而适当照顾了低优先级信息帧的发送；为4 类 子域设定了高优先级中断策略，防止了某站有4 类帧而不能发送，却有可能发2 类、 0 类帧的优先级倒置局面出现。改进协议在确保高优先级信息优先得到服务的同时， 兼顾低优先级信息得到一定的服务。 5 i e e e s 0 2 5 中的优先级控制 i e e e s 0 2 5 令牌环协议是一种常见的局域网协议，令牌环是依靠介质( 电缆) 连接若干工作站的环状局域网络。源工作站产生的数据信元循环传送于介质环的其 它工作站，最终被目的工作站接收。令牌标志着发送权，不携带数据帧的令牌为闲 令牌，闲令牌到达某站，如该站无数据要发送，则迅速通过，如果有信息数据要发 送，则将闲令牌改为忙令牌，随后携带发送数据向下游传送。每个工作站的数据根 据缓急轻重分为若干个优先级，为了让优先级高的数据优先级得到发送，令牌具有 优先级和预约级，只有某站要发数据的优先级不低于经过该站的闲令牌的优先级时， 才能发送。当经过该站的是忙令牌或是一个不能利用的闲令牌时则可以通过预约 来竞争下一次的发送权，详细情况可参见文献【6 】。有关文献【12 1 3 1 对i e e e 8 0 2 5 令牌 环协议优先级准公平性也进行了研究。在确保高优先级信息优先得到服务的同时， 兼顾低优先级信息得到一定的服务。 6 分布式队列双总线( d q d b ) 中的优先级控制 i e e e 8 0 2 6 城域网标准d q d b 网包含两条数据流向相反的单向总线，是基于 优先级接入控制的分布式排队概念。d q d b 的主要特点是它的m a c 比较简单，在 网络轻载时可以充分利用网络的容量( 带宽) ，且不依赖于网络的大小和数据速率。 但在重载时，由于d q d b 结构本身不对称的特点，使得上游结点比下游结点有更多 的机会利用空时隙来发送信元，而下游结点则比上游结点有更多的机会发送请求信 息。另外，上游结点低优先级的业务也会推迟下游结点高优先级业务的发送。 针对上述不足，有关文献1 1 4 1 提出了扩展计数带宽平衡机制e c b w b ( e x t e n d e d c o u n t i n gb w b ) 。带宽平衡( b w b ) 机制的基本思想是：网上的结点并不全部使用 提供给它的带宽，而是放弃一部分带宽的使用权留给下游结点使用。它为每个结点 设置了一个带宽平衡模数( b w b m o d ) ，以便限制结点对带宽的使用权。扩展计数 带宽平衡机制e c b w b 使用多优先级管理机制和带宽平衡机制，实现具有优先级控 第3 章局域网与，域网中的优先级策略 制的带宽平衡。在e c b w b 机制中，设置三个带宽平衡计数器，分别统计对应结点 的三种优先级信息端发送成功的次数。计数器c d i 保存各结点相应的优先级信息， 其增值是优先级级别的函数：高优先级信息的计数器增值小，低优先级的计数器信 息增值大，这样，在结点处于“递减计数”状态时，由于高优先级的c d 计数器值 小，递减至0 快，低优先级的c d 值大，递减至0 慢，从而保证优先级高的信息可 先获得空槽发送信息，因为只有c d = 0 时才可获得空槽。带宽平衡的门限值 b w b 、m o d 的大小可以根据网络活动结点数动态调整，当活动结点较多而需占用较 大的带宽时，降低门限值以便释放更多的带宽：反之如果当前网络活动结点较少， 则将门限值调高一些，以便提高吞吐量改善网络性能。 上述针对d q d b 控制机制进行的探讨，目的在于实现具有优先级控制的带宽平 衡。有关d q d b 的性能分析也是近来学术界研究的一个热点。例如d q d b 城域网 的稳态和暂态公平性，信元的等待时间，实现局域网互连时的性能。 7 光纤分布式数据接口( f d i ) i ) 中的优先级控制 光纤分布式数据接口f d d i 是一个高性能的光纤令牌环l a n ”】，能提供 1 0 0 m b p s 的传输速率。典型的f d d l 网是由两条独立的传输方向相反的环组成，但 进行数据传输的始终是一个环形线路，与单环令牌网类似，为了实现优先级控制， f d d i 采用“时控令牌协议”，提供同步数据服务和异步数据服务。网络初始化时， 由各站点协商“目标令牌