（计算机软件与理论专业论文）计算机网络优先级服务策略的建模研究.pdf

，k 论文摘要 x 3 9 7 5 3 现代计算机通信网正朝着a t m 交换网和宽带综合业务数 g - 网( b i s d n ) 的方向发展。f 其服务业务包括话音、数据、传 真和视频等。每种业务都有不同的统计特性并需要不同的服务 质量( q o s ) 。为了充分利用网络资源并满足每种业务的q o s ， 需要进行优先级控制。但原有的网络协议中的优先级控制只适- 用于优先级较少的情况，因此需要进行改进j 为了找到更适合在 b i s d n 中使用的优先级服务策略，本文对i e e e 80 2 5 协议进行 了改进，提出“高优先级中断策略”，改善了原来协议中低优先 级数据长时f 司得不到发送的局面：并对一种实用的a t m 优先 级系统模型进行分析，采用信息量理论( t r a f f i c ) 的方法完成了数 学建模的解析，通过数值分析进行了性能评价，得到了系统队 长的概率分布和信元交换的平均等待时间等重要参数指标。本 文的理论创新不仅对于设计、建造a t m 交换网，有重要的理 论指导意义，而且也为今后在该前沿方向的创新研究打开了通 路，卜一 关键词优先级，a t m 网络，建模研究广 a b s t r a c t m o d er n c o m p u t e r c o m m u n i c a t i o nn e t w or kis h e a d i n g f or a t ms w i t c h i n gn e t w or k sa 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 s tr a f f icss u c ha sv o i c e ，d a t a ，f a xa n dv i d e oe a c ht y p eo ft r a f f i c h a sd i f f e r e n tt r a f f icc 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 er e n tq u a l i t y o fs er v ice ( q o s ) r e q u ir e m e n t s t h u s ，apr o p e r p r i or i t yc o n t r o li s n e e d e di nor d ert ou t i l i z et h en e t w o r kr es o ur e e se f f i c i e n t i ya n d s a t i s f y t h e q o so fe a c h t r a f f i ch o w e v e r ，t h epr i or i t y c o n t r 0 1 s tr a t e g yi n pr i m a r yp r o t o c 0 1 0 n l ya d a p t st ot h es t a t ew i t hf e w r a n ks i tn e e d st ob ei m pr o v e dt o a d a p tt oa t ma n db i s d n i n t h is p a p e r ，a ni m p r o v e ds tr a t e g yi ni e e e 8 0 2 5t o k e n r i n g p r o t o c o l ，t h a t is ，”h i g h p r i o r i t y r a n ki n t e r r u p ts t r a t e g y ”i s pr o p o s e dw h i c hc a n p r e v e n tt h e1 0 w r a n k si n f or m a t i o n ( e s p e c i a l l yt h el o w e s tr a n ki n f o r m a t i o n ) w a i t i n gf o ra1 0 n gt i m e w ea ls o a n a l y z e a p r a c t i c a b l ea t mpr i o r i t y s c h e m ew i t ht w o k i n dso ft r a f f i c t h es c h e m eiss t u d i e db ys e t t i n gu pm a t h e m a t i c m o d e lw i t htr a f f i ct h e o r y w eo b t a i ns e v er a l i m p o r t a n t p a r a m e t e r ss u c hast h e pr o b a b i i i t y d is t r i b u t i o no ft h e q u e u e 1 e n g t ha n dt h ea v er a g ew a i t i n gt i m eo fc e l lb yn u m e r i c a lm e t h o ds t h et h e o r y i n n o v a t i o ni n t h is p a p e rn o t o n l y c a ni ns tr u c tt h e d e s i g n a n dc o n s t r u c t i o no fa t mn e t w o r k i n g a n db - i s d n ，b u t a 1s ol a yaf o u n d a t i o nf orf u t u r ei n n o v a t i o nr e s e a r c hi nt h i sf i e l d k e y w o r d s ：p r i or i t y ，a t mn e t w o r k ，m o d e l i n gr e s e a r c h 第一节引言 计算机网络优先级服务策略的建模研究 1 引言 计算机通信网络发展的早期，数据传输的优先级控制策略 就得到重要应用。而现代计算机通信网正朝着a t m 交换网和宽 带综合业务数字网( b is d n ) 的方向发展，其服务业务包括话 音、数据、传真和视频等。每种业务都有不同的统计特性并需 要不同的服务质量( q o s ) 。由此可见，为了充分利用网络资源 并满足各种业务的q o s ，更需要进行优先级控制。即根据不同 业务传输信元的特性，将信元标以不同的优先级。 然而要将数据通信网中的优先级策略直接应用到a t m 交 换网和宽带综合业务数字网中，还有一定的困难与不足，必须 对宽带综合业务数字网中的优先级策略进行创新性研究，包括 将原有数据通信协议中的优先级策略扩展到a t m 交换网和宽 带综合业务数字网的研究中来。扩展的关键问题是综合业务网 中的优先级较多，而原来数据通信网中优先级较少。由于数据 通信网中只传送一种业务一数据，通常全网优先级取两个级别 ( 即非优先级和优先级) 。如果取三个级别( 0 ，1 ，2 三级，0 级为非优先级，2 级最高) 就更好i l 2 ，3 1 。由于级别少，能较好 地兼顾低优先级数据的传送。但在综合业务中，至少涉及到数 据、话音、静止图像、活动图像4 种业务，全网优先级至少涉 及8 个级别。在优先级较多的情况下，低优先级业务特别是最 低优先级业务往往得不到应有的服务。因此，在将原有协议中 的优先级策略扩展到a t m 交换网和宽带综合业务数字网中时， 如何在保证高优先级业务得到及时服务的同时，尽量兼顾低优 第一节引言 先级业务的服务质量是需要重视的问题。这个问题正是本文前 期研究( 在下面论述) 中提出的所谓优先级“准公平性”问题。 另外，为了对a t m 交换网和宽带综合业务数字网的优先级 策略进行创新研究，需要对其进行建模研究，包括数学建模和 仿真建模。在a t m 交换网和综合业务数字网中，交换节点、复 用器以及业务接入点等处均有缓冲区来实现对信元的收发以及 缓存。信元到达排队系统后还要根据其优先级采取相应的排队 策略，这是一个多优先级排队问题。利用排队理论分析优先级 控制下信元排队的队长分布，计算信元丢失率、时延等关键参 数，对于a t m 交换节点、复用器以及业务接入等设备的设计是 至关重要的，对业务控制策略的选择同样也是很重要的。 关于准公平性问题，在本文前期的研究工作中已取得较大 进展。其研究报告的学术论文即将在国家一级杂志“电子与信 息学报”等发表”“。 关于上面提到的第二个研究问题，即对a t m 交换网和 b i s d n 的优先级控制所涉及诸多方面的建模研究，也己取得进 展。为此在本硕士答辩论文中予以重点报告。题目为“计算机 网络优先级服务策略的建模研究”。 第= 节本文的前期研究进展 2 本文的前期研究进展 在本文的前期研究工作中，对优先级所涉及的准公平性问 题进行了深入讨论”i 。针对i e e e 80 2 5 协议，提出“高优先级 中断策略”。为了支持本文数学建模和仿真建模，以保持硕士研 究课题的连续性，不妨对准公平问题的研究略加回顾。 1 基本原理 i e e e 8 0 2 5 协议是著名的令牌环协议，现已成为国际标准。 该协议使用优先级控制机制，使优先级较高的数据可以较早地 发送出去，从而能满足各种业务不同的实时性要求。当我们将 其扩展到综合业务城域网时，所传信息将包括数据、话音、静 止图像、活动图像等多种业务，如果为每种业务都划分两种优 先级，全网的优先级类型就有8 个之多。从协议的运行机理可 以看出，当优先级较多时，预约过程中会出现多站嵌套和多重 嵌套的现象，比较复杂。优先级较高的数据很容易获得发送权， 而优先级较低的数据，尤其是最低优先级数据较难获得发送权， 特别是当网上高优先级的数据较多时，低优先级数据往往在很 长时间内得不到发送。为了在尽可能保证高优先级信息能提前 进行预约的同时，又防止出现低优先级信息长时间得不到预约 或服务的局面，我们提出了高优先级中断策略。它的基本原理 如下： 当环网上连续多圈通过较高优先级的信息单元时，就中断 高优先级信息单元的运行，让环网上某站重新产生个初始空 令牌，使网恢复到初始状态，以便为低优先级信息单元尽可能 提供一个发送的机会。为此，选多级别优先级的某一个优先级 为门限值m ，当忙令牌的优先级等于或大于m 时，就对通过的 信息单元计数( 在站点设立计数器计数) ，否则不计数；规定连 第二节本文的前期研究进展 续计数的最大次数为k ，当计数次数达到k 时，就中断计数，重 新放出初始空令牌；计数是连续进行的，在未达到k 次前，如 果有一低于m 的信息单元通过，则计数器清零，以准备重新开 始计数。 2需要解决的几个问题 ( i )采用分布式计数控制。只在环网中的某个站设立计 数器，还是每一个站都设立计数器。前者是集中式控制，后者 是分布式控制。对于集中式控制，只有一个站设立计数器，当 它计满k 次时，就要放出个初始空令牌，而不管其它站是否 处于嵌套状态，由于其它站不能及时将寄存器清零，容易引起 混乱。而对于分布式控制，在每一个站上都设立计数器，只要 计数器计数为k ，就可以将自己的寄存器清零。当然必须保证 在初始空令牌放出的时候，全网各站的寄存器都处于零状态， 新令牌的运行才不会受到干扰。这点在环网上是容易实现的， 稍后说明。 ( 2 ) 无论是空令牌还是忙令牌( 帧) 中的优先级，都不能 充当计数对象。因为它们都存在漏计情况。 ( a ) 如果计数对象为空令牌的优 先级。如图1 所示，设m 站由于n 站 预约而进入嵌套，m 站放出空令牌 去为n 站服务，但在空令牌经过q 站时，q 站有一个优先级更高的数 据要发，于是直接利用该空令牌发 送数据，q 站也进入嵌套。如果计图】 环形l a n 示意图 数器只计空令牌，就出现在下游站漏计的现象。 ( b ) 现在看一下忙令牌的情况。忙令牌一旦发出后，就会在 网上循环整整周，不会出现利用空令牌计数存在的弊端。但 第二节本文的前期研究进展 也有问题，有时忙令牌的优先级并非与其所携带数据的原优先 级p 。一致。按协议，只要某站数据的优先级不小于空令牌的优 先级，就可以利用该空令牌，这时被利用空令牌的优先级不改 变。我们称这样的忙令牌为优先级隐式忙令牌。当隐式忙令牌 的p3 p2 p l 低于门限值m 、而其所携带原数据的优先级p 。高于 m 时，就会漏计。 3 解决方案 由上可见，空令牌、忙令牌都不能充当计数对象，为此必 须对计数对象另作考虑。研究表明，可以通过在忙令牌中设立 一个计数标志位来实现。i e e e 8 0 2 5 的m a c ( m e d i a a c c e ss c o n tr 0 1 ) 帧格式如图2 所示，其中的r 位为保留位，尚未定义。 我们就利用帧状态( f s ) 中的第3 、4 两个保留位作为高优先 级计数标志位，若r t - 为ll ，则标志着该帧数据的优先级不小于 门限值m ，满足计数条件。若r r 为0 0 ，则标志着该帧数据的优 先级低于门限值m ，不满足计数条件。另外两种组合10 和0 l 可以留作优先级门限分档时使用。 当某站要发送一帧数据时，先要将所发数据的优先级p 。 与m 相比较，若p 。m ，则将高优先级标志位置为1 1 ，若p 。 n 。进入共享缓冲区的交换失败者等待 下一时隙与新到达的分组一起竞争输出端口。所以如果一个时 隙内有k 个分组的目的地址相同，则按每个时隙一个分组的方 法在k 个时隙中将其交换到输出端口。当然在交换这k 个信元 的时间内又到同目的输出端口的信元还未记入其中。 ( a ) 组合的输入输出缓冲区结构 为了改善传统输入缓冲结构的性能和减小输出缓冲结构的 图7带有回环机制的交换机的系统模型 篁三堇竺竺生塑垡生丝茎堕墨墨堡望竺墨一 复杂度，通常可采用具有有限加速因子s ( 1 s n ) 的组合输 入输出缓冲结构。如图8 所示。在每一对输入和输出缓冲器( i b 和o b ) f 司存在着两种控制方式：反压机制( b p ) 和队列丢失 ( q l ) ，在b p 方式中，一个i b 中队头信元的读出将取决于s 和其目的o b 的可用空间两因素。而在q l 方式时，该队头信 元的读出仅与s 有关。很明显，b p 方式要求在每一对i b 和o b 之间有一个反向控制信号，以便在队头信元传送前把o b 的状 态信息送到每个i b ，这种操作j , q - 会增加a t m 交换机内部运行 速率。 n n 交换 网络 图8具有输入输出缓冲排队结构的交换机 ( 5 ) 共享存储器排队 在共享存储器缓冲结构中，所有到达的信元都将被放在一 个共享存储器中，这个存储器由a t m 交换结构的所有输入和输 出端i z i 共享，如图9 所示。每个时隙，信元从输入端到输出端 的交换就体现在对这个共享存储器的读写操作上。为了便于信 元的调度和输出，在共享缓冲区内是按各个输出端排队，也就 是每个输出端有一个队列，当信元输入时，按信元的目的输出 端号码写入相应的输出队列，排队等待调度。各个输出队列为 逻辑队列，队列中各个信元的存储地址在物理位置上并不连续， 而是用地址链的方法。 苎三堇坚坚! 塑垡生丝茎堕垄墨堡堡塑堑 变换弼一络 入 口 交 换 鱼 兀 二 共享缓冲 出 口 交 换 苎 兀 2 n 图9具有共享存储器排队结构的交换机 ( 6 ) 在缓冲区中引入优先机制 为了在a t m 网络中满足综合业务( 话音，数据，图象等) 对服务质量( 如端端延时和信元丢失率) 的不同要求，人们常 常在上述交换系统模型的基础上引入优先级机制。举两例说明， 在输入排队中为各优先级信元设置独立的缓冲区，如图l0 所 示，各优先级信元到达后在各自的缓冲区中进行排队，高优先 级的信元在该端口排头为空时比低优先级信元优先占有该端口 排头，只有当高优先级输入缓冲器为空时低优先级业务才会得 排队室排头 图l0在输入端为各优先级 设立独立的缓冲区 图11在输出端为各优先级 设立独立的缓冲区 到服务。成为某输入端口排头的信元与其他输入端口的排头信 元( 如果去同一输出端口) 一起以无优先级处理方式竞争输出 第三节a t 坚生箜垡生堡茎堕墨墨堡堡堕墅 一 若竞争成功，就被交换机送至输出缓冲区，否则继续占据排头 位置并参加下一轮的竞争。同样的结构也可运用在输出端，如 图11 所示。如果某优先级的缓冲区中信元较满，则新到达的信 元即使被丢弃也不能占据其他优先级的缓冲区。 为了提高缓冲区的空间利用率，可采用部分缓冲共享策略 ( p b s ) 或挤出策略( p o ) 。部分缓冲共享策略是指，在排队时 为各优先级信元设置独立的缓冲区或者在一个大缓冲区中为高 优先级信元设立一块独占区。当缓冲区的信元数未超过阈值k 时，各优先级信元先来先进入，当缓冲区中的信元数超过阈值 k 时，再到达的信元只允许高优先级信元进入，低优先级信元 被丢弃【”，3 8 l ，如图12 。挤出策略并不设置阈值，只是当缓冲区 满时，如有新的高优先级信元到达，则可随机占据排队室中已 有的低优先级信元的位置。p o 策略的效率比p b s 更高。 b闽值k0 r - i _ il 口口 高优先级高低优先级 信元独占区信元共享区 图l2部分缓冲区共享示意图 在a t m 交换机中，常常综合使用时间和空间优先级控制策 略，例如在图10 中，可将非实时信元的缓冲区设置得比实时缓 冲区大，以满足非实时信元对丢失率往往较敏感的特性。也可 将实时信元和非实时信元都按照丢失率要求再分两类，在各自 的缓冲区中采用p b s 或p o 策略，这样就可以使每类信元中对 丢失率敏感的那些都能优先占用缓冲区，从而保证了对延时和 丢失率都敏感的信元的服务质量。 笙三堇竺兰生塑垡枣堡茎堕墨墨堡竖竺圣 3 3一种优先级模式的实现及性能分析 有关文献1 25 , 26 】指出，输出排队的交换性能比输入排队的性 能要好得多，从吞吐量和排队时延角度考虑是最佳的交换结构a 下面分折一种在输出端设立排队室的实用系统模型 38 4 引。该系 统模型并非本文首次提出，但按a t m 交换机的实际运行机理设 定解析条件后建立排队模型且数学建模，本文是首次进行的。 3 3 1 排队模型的确定 系统模型的建模研究在优先级的条件下需要附加一些设定 ( 如图1 1 分析) 。 ( 1 ) 交换机同步运行，交换机交换一次的耗时为1 个时隙。 时隙的定义是：在每个时隙内，每条输入线最多有1 个信元到 达。于是，整个输入端在1 个时隙内最多到达n 个信元。 ( 2 ) 本文将综合业务( 话音、数据、传真、电视图像等) 分为两大类：实时业务( 有严格的延时要求) ，简称业务1 ，非 实时业务( 有严格的丢失率要求) ，简称业务2 。对两种类型的 业务，在输入端不予区分，而在输出端区分。为此将每一输出 端缓冲区分为两部分，即排队室l ，排队室2 ，让两类业务分别 排队等待，即业务1 对应排队室1 ，业务2 对应排队室2 。 ( 3 ) 为了满足两类业务的不同质量要求，对业务l 提供传 输服务优先权。由于业务1 的实时性有一个上限要求，因此， 它的排队室l 容量没有必要太大，只要能保证最后进入排队室 l 的一个信元的滞留时间刚好能满足实时性的上限要求为准。 从实时性要求看，后面再继续排队是多余的。这样设置排队室 1 可减轻设立缓冲区的繁冗程度。对业务2 要提供足够的排队 塑三蔓坚坚! 塑垡垒望丝堕星基堡! 塑 室2 ，以满足丢失率。设业务i 的排队室1 的容量为q l ，业务 2 的排队室l 的容量为q2 ，q 2 n 。缓冲器的总容量q = q i + q 2 。 ( 4 ) 业务l 的服务优先级高于业务2 ，当业务1 的排队室1 的信元未服务完时，服务员( 输出线) 不服务业务2 。当服务 业务2 时，空闲的排队室l 又到达业务1 ，则服务员服务结束 当前1 个业务2 后，马上转向去服务业务1 ，待无业务1 后再 返回排队室2 为业务2 服务。这种方式正是非占先优先权服务 策略。经同批交换到达同一缓冲器的信元，因很难区分先后顺 序无法实现先来先服务。为此可以出现两种服务规则：随机 选择服务；有序服务一一给排队室的存储区间编号，由小号到 大号的顺序服务其中的顾客，小号区间存储小号输入端交换来 的信元。有序服务策略不同于先来先服务。本文设定两路顾客 都按随机选择服务。显然在本文的排队模型中，服务规则有自 己的特色。 ( 5 ) 到达交换机某输入e l 的信元以相等的概率选择输出线。 经某次交换离开交换机去某一输出线缓冲器的信元能否进入缓 冲器的两个排队室，还要看当前两个排队室的剩余容量，当业 务1 信元群使排队室l 的剩余容量满员时，其超出的部分被溢 出。虽然业务2 信元的排队室2 容量很大，但也可能溢出，但 本文设定溢出的概率忽略不计。 ( 6 ) 设每个信元( 顾客) 被服务时间是定数s 个时隙，即 服务遵从定长分布。也就是说，如果某顾客从r 时刻开始服务， 到r + 1 时刻服务结束而离开交换系统。本文在解析中，为了与 常见交换机的运行机理相符合，设s = 1 ，即一个时隙离开个， 且设定前一时隙到达排队室的顾客，最快要在后一时隙离开， 这一点也是本文的特色。s 1 的情况正在研究，待取得进展后另 行报告。 笙三翌竺坚生塑垡壅堡箜堕丝基垄堡竺壅一 由于交换机n 路输入过程和n 路服务过程完全独立，因此 我们仅需研究其中的某一路输入及某一路输出，权且称为观察 入口及观察出口。观察出口也称标记出口a 通常我们将不提出肯达尔模型的建模称为隐式分析，凡提 出肯达尔模型的为显式分析。显然上面的设定和分析是隐式进 行的。如果仔细考虑上述设定，且将交换机考虑到到达系统， 就会得到显式分析的如下扩展肯达尔模型： l 有上限q l ( 高优先级排队室1 有限) r s s ( 对同批顾客) 限制的批d l q2 ( 低优先级排队室2 很大) f c f s ( 对不n 批顾客) 量到达 q2 ，q l p r ( 两排队室顾客) 其中，l ：二项式到达 d ：定长服务 q t 、q2 ：两排队室大小，q2 一c o 33 2数学分析 n a ( n ) p a fn 1 ： 参数设定( 参见图13 ) r s s ：随机选择 f c f s ：先来先服务 p r ：优先权服务 n l 时隙n 时隙i 1 + l 时隙 ，。、，。、，。、_ 、 r i t 石百沔订1 卉啊时间 + 到达开始服务结束服务 图i3 到达时间与服务时间 用户终端数 第n 个时隙各输入端出现的去同一输出端( 也称标 记出线) 的信元数 a ( n ) = m l 的概率，m l = 0 、 1 、2 、n ， 令 苎三羔竺坚塑垡垄丝壁堕墨基堡堡旦窭一 a ( n ) p a ，fn1=m2 a 1 ( n ) a 2 ( n ) y 枷 0 。3 口 q b i ( r ) b2 ( r ) a 。【= p ( a ( n ) 2 m i ) 。p a ( n ) = m 1 第n 个时隙通过交换机到达标记出线缓冲器入口处 的信元数。如果交换机对去标记出线的信元为全交 换，则a ( n ) = a ( n ) 。如果交换机有上限限制， 则a ( n ) a ( n ) 。设上限为k ，则a ( i 1 ) = m i n ( k a f n l ) 。当a ( n ) k 时，其超出部分被淘汰后待下 次再参加交换。设被交换者是从参加交换者中随机 选择的，而且各类优先级信元以相等概率参加选 择。 a ( n ) = m2 的概率，m 2 = 0 、1 、2 、n ， 令 a m2 = p ( a ( n ) = m2 ) 2 p a ( n ) ；m2 a ( n ) 中的实时信元数，即有优先权的信元数， 由于排队室1 的剩余容量的限制，这些信元并不一 定都能完全进入缓冲区，多余的被丢弃。 a ( n ) 中的非实时信元数，即无优先权的信元数， 由于排队室2 容量很大，这些信元一般都能完全进 入缓冲区。 a l ( n ) = m x 的概率，即为p a ，1 ( 。) ；。3 a2 ( n ) = m 4 的概率，即为p a ，2 ( 。) ；。4 在一个时隙，即at 时间内，服务一个顾客的概率。 若本时隙开始时有顾客，口= l 。 在一个时隙，即at 时问内，无顾客离开的概率。 若本时隙开始时无顾客，0 9 = 1 。 标记出线缓冲器的容量，q = q - + q2 ，其中q l 为排队 室1 的最大容量，q2 为排队室2 的最大容量。 第r 个时点排队室1 中的信元数 第r 个时点排队室2 中的信元数 笙三堇 坚翌生箜垡塞丝箜堕墨墨堡堕堡茎一 p 某空闲终端的输入线上在某时隙到达1 个信元( 优 先级不限) 的概率。不到达信元的概率q = l - p 。该 信元的去向在产生之前是完全随机的，是等概率产 生的，因此准备去交换机某一输出线的概率应为 p n 到达交换机的业务1 与业务2 的比率分别占p1 、 p2 。显然pl 、p2 是平均量。在某输入线上在某 时隙已确定到达1 个信元的条件下，该信元为业务 l 和业务2 的比率为已知时，则到达信元为业务l 的概率应为pp1 ，到达信元为业务2 的概率应为 pp2 ，其中p1 + p2 = l p 。) ( r 1 ，r )在r 1 时点系统状态b l ( 卜1 ) = m 、b2 ( r 1 ) = h 在r 时点系统状态bi ( r ) = i 、b2 ( r ) = j ，其转移概率为 p ( 。h 】( ) ( r l ，r ) 平衡状态下，系统在r 时点出现b 1 ( r ) = i 、b2 ( r ) = j 的绝对概率。 则在同一时隙产生要去标记出线的信元数为m i 的概率服从二 项式分布，即 = c ：1 ( 号) ”( 1 一万p ) “n 考虑到要去标记出线的信元在通过交换机时，有上限k 的要求， 因此 爿( ”) = m i n ( k ，4 ( 月) ) h z m 2 ( 0 ，j ) ) ，b ( ( 0 ，h ) 一 ( i ，j ) ) ，c ( ( 1 ，h ) 一 ( 0 ，j ) ) ， d ( ( m ，h ) 一 ( i ，j ) ) 表示。 m = 0 ，h = 0 且( 卜m ) + ( j h ) k 时，转移概率为0 。 m 0 或h 0 ，且( 卜m ) + ( j h ) = k 时，转移概率为0 。 ( 卜m ) + ( h j ) - h - 1 ( 10 ) 其它 i q i i = q 。 笙三蔓竺翌! 堕垡垒丝篁堕墨苎堡! 塑塑一 y n 8 0 y o p ， 0 y 0 8 o d ( ( 伽，h ) _ ( 自# o ，朋= h = o ，1 = o h = o j 0 h o ，j = o ( 1 1 ) a o ，0 且 o ，0 且j h c p , 成 妒j p 0 【p j b “ 0 h = o ，j = o h = o ，o o j = o 矗o ，o 且( 12 ) o ，o 且j q l ，就可达到 q2 一。的效果，即能保证非实时信元的丢失率。 ( a ) ( b ) 图i7 稳态概率曲线 综上所述，在输出端考虑优先级问题时，利用本节的优先 级模式，在通常条件下，即本文的条件下，可以在有限资源( 缓 冲区适当小) 的情况下，既满足实时信元的延时要求，又满足 非实时信元的丢失率要求。 耄n斜率心嚣 笙璺羔堕壅垦望一 4 研究展望 优先级服务策略在计算机通信网的交换、流控等环节起着 十分重要的作用，并为多媒体业务的传送提供了可能。为了让 某些类型的业务( 比如对延时或丢失率敏感) 得到高质量的服 务，通过赋予它们较高的优先级，使其在传输过程的时间和空 间上得到照顾。我们称这类问题为“非公平性”问题。关于a t m 中非公平性的问题，已经取得了一定进展。 然而在a t m 交换网和b i s d n 中，由于优先级很多，如果 绝对保证高优先级的服务质量，就有可能使低优先级的服务质 量得不到保证。并且，人们发现在静态优先级模式中，即使是 高优先级业务的负载量适中，其服务质量也明显高于所要求的 目标服务质量。因此，在确保满足实时业务服务质量的条件下， 适当提高非实时业务的服务质量是可能的。这种既照顾高优先 级业务又适当兼顾低优先级业务的策略，我们称之为“优先级 准公平性”问题。目前关于准公平性策略及其建模研究已经起 步，这是发展综合业务网络的需要。 在优先级服务策略的领域内，“非公平性”问题和“准公平 性”问题已经形成两大研究热点。青大网络与通信研究室与国 外的一些研究单位同步开展了研究工作，近期内国外也展开了 该课题研究，近期需要研究的问题很多，为此本文展望如下。 1 基于阂值的优先级模式的研究。这是“准公平性”问题 的典型代表，如图l8 所示，考虑有两个缓冲区的排队系统，分 别对应两种业务，一种为实时业务( 高优先级) ，另一种为非实 时业务( 低优先级) 。对同种业务，先来先服务，对非同种业务， 非占先优先服务。低优先级业务有两个阂值，分别为高阈值h 和低阈值l 。根据低优先级的顾客数，将系统分成两种状态， 第四节研究展望 即轻态和重态，系统要么处于轻态，要么处于重态。状态的定 义和相互转化过程如下：当低优先级队长小于l 时，系统处于 轻态：当系统处于轻态且低优先级的队长增加到高阈值h 时， 系统从轻态转向重态：当系统处于重态且队长降低至低阂值l 时，系统从重态转向轻态。状态转移如图19 所示。用两个阈值 而不用一个阈值的原因是，个阂值用来确定何时系统转成重 。耋羔 。 队列2 2 类呻苴 。l 。- 。j 。- 。一 服务员 。一 图18基于闽值的排队系统 态，而另一个阈值用来确定何时系统转成轻态。因此，两个阂 值比一个阈值更加灵活。实际上，当低阀值等于高阈值时，两 个阈值的优先级策略与普通的阈值优先级策略相同。 n 图19状态转移 y 服务规则如下：1 ) 如果系统处于轻态，则优先服务1 类信 元，1 类信元的排队室空闲后再服务2 类信元。如果正在服务1 第四节研究展望 类信元的过程中，2 类信元数增加至h ，则系统由轻态转向重 态，当前正在服务的1 类信元服务完后，服务员转去服务2 类 信元，服务进入交替状态。2 ) 如果系统处于重态，则服务员处 于交替服务的过程中，如果2 类信元数减少至低于l 时，系统 由重态转入轻态，当前正在服务的一个2 类顾客服务完后，暂 停服务2 类顾客，转去连续服务l 类顾客。3 )若一种类型的 顾客全部被服务完，则服务另一种类型的顾客。 同样可以将阈值设在高优先级缓冲区中，当高优先级信元 的队长低于阂值时服务员将交替服务两个队列：当高优先级 队长高于闽值时，则优先服务高优先级信元。不论将阈值设置 在哪个缓冲区内，其目的都在于适当照顾低优先级信元，使其 等待时间不至于过长。 目前，我们对该模式的数学建模正试图开展研究，同时就 准公平性问题的实现策略继续深化研究。 2 a t m 优先级策略( 包括照顾低优先级策略) 的数学建模 在“非公平性”问题的研究中，a t m 中优先级策略的数学 建模是研究的热点，正处于极盛研究状态。主要有以下两个方 面的问题： 优先级策略的数学模型必须考虑优先级数大于2 的情况， 以便尽可能与综合业务的实际情况相符合。 随着各种新型优先级策略的相继提出，急需对其进行建 模研究以评价其性能。 目前，两个优先级a t m 交换机产品已投入市场( 如日本 n e c 公司开发的a t o m i s 一5 型a t m 交换机) 。相信有关多个 ( 多于两个) 优先级问题的研究将对a t m 交换机性能的提高产 生重要的推动作用，为a t m 交换网和宽带综合业务数字网的发 展奠定基础。 茎至翌至茎苎堕 5 参考文献 1 m az i l i w a n gs i r u i n g ac l a s so fc y c t i cq u e u ew i t h p r i o r i t y b a t c hs e f v i c e ，a p p l m a t h m o d e l i n g ，199 1 ，l5 ( 9 ) ，4 5 0 458 。 2 王思明，逯昭义，带有优先级令牌环形l a n 守恒律的探讨， 计算机学报，l9 9 3 ，l6 ( 1 1 ) ，8 6 2 8 6 6 3 wusch ，per f or m ancem e asu re m en tintokenr in g1 2e t w or ks co m pu tern e t wo rksan disd nsys te ms ，1992 ，25 ( 1 ) ，15 9 一l6 8 4 逯昭义，罗秀秀，“综合业务城域网i e e e 8 0 2 5 预约级协议 改进策略”，电子与信息学报，录用待刊 5 罗秀秀，王立宏，逯昭义，“i e e e 80 25 令牌环协议的一种 简化协议”，计算机工程与应用，录用待刊 6 y l i m ，j k o b z a ，a n a l y s iso fa d e l a y - d e p e n d e n tp r i o r i t y d isc i p i i n ei nar n u l t i c l as str a f f i 。p a c k e t s w i t c h i n gn o d e p r o i e e ei n f o c o m 8 8 ，n e wo r i e a ns ，l a ，l9 8 8 p p 9 a 4 1 10 7 t m c h e n ， j w a l r a n d d 。g m e ss e r s c h m i t t ，d y n a c o , i c p r i o r i t yp r o t o co lsf or p a c k e tv o i c e ，i e e ej s a c 19 88 ( 7 ) 8 w a n gs i m i n g ，t h ep r o b a b i j i t i eso ft h ec p bs y s t e r n ，a p p l m a t h m o d e l l i n g ，19 9 3 ，17 ( 2 ) ：2 3 3 l 9 p i tsj m ，e ta 1 a n a l y s iso fa t ms w i t c h m o d e i 、v i t ht i m e p r i or i t i es e l e c tr o n i cl e t t er s ，19 9 0 ，2 6 ( 15 ) 10 m i tr o nnm ，e t a l ，c e l l - l e v e ls t a t is t i c a l m u l t i p l e x i n g i n a t mn e t w or k s 7 ”i t cse m i n a r n j 199 0 11 r c h i p a l k a t t i ，j f k r os e ，d t o w s l e y ，s c h e d u l i n gp o l ic i e s f o rr e a i 一“m ea n dr i or l r e a i t i m e t r a f f i c p a c k e ts w i t c h i n gn o d e i n ：i e e ei n f o c o m ，8 0 ，19 8 9 ，p p7 7 4 78 3 12 b d c h o i ，y l e e ，d j c h o i ，x l ，g e 0 x 2 d ch o lp r i o f j t y 3 7 蔓亘兰釜耋塞堕 一 _ _ 一一。 q u e u e ir t gs y s t e mw i t hr a n d o m 。r d e rs e l e c t i 0 1 2w i t h i ne a c hc i 8 s s ， pr ob a b i l i t y i 1 1 e n g i n e er i n g a n dir l f or m a t i o n a !sc i e n c e 19 98 ，12 ( 1 ) ：125 139 13 ag r a v e y g h e b t t t er n e ，m i x i n gt i l t i e a n d1 0 ss p r i 0r i t i esir l a s i n g l es er v er q u e u e ，i n ：i t c 13 ，n 0r t h h 0 1 1 a n d ，a m s t er d a m ， 1 9 9 1 ，p p 1 4 7 15 2 14 y l i m j e k o b z a ，a h a l y s is0 fad e l a y d e p e n d e n tp r i 0r i t y d isc i p l i n ei na ni n t e gr a t e dm u l t i c l a s str a f f i cf a s tp a c k e ts w i t c h ， i e e et r a r ls a c t i 0 1 1s0 nc 0 m m u n ic a t i 0 1 2s ，19 9 0 ，38 ( 5 ) ：659 685 15 c c h a n g ，h t a n ，q u e t i e i n ga n a l y s is0 fe x p l i c i t a s s i 9 1 3 m e n t p u s h 一0 u tb u f f ers h a r i n g f ora t mr l e t w or ks ，i 1 1 _ ：i e e e l n f o c o m 9 4 ，p p 9 2 9 9 3 4 16 lg u i ，cfa n ，a n a l ys is0 f8 p r i 0 r i t y c e l ld is c a r d i n g m e t h o df o ra t m1 3 e t w or ks t e l e c o m m u n i c a t i o ns ys t e r n s ，l995 、4 ： 5 1 6 0 l7 g h eb l a t er 1 1 _ e a g r f l v e y a s p a c ep r i 0 r i t yq u e u e i n g m e c h a n is mf or m l l l t i p l e x i n ga t mc h a n n e ls ，c o m p h t e rn e t w or ks a n di s d ns ys t e m s ，19 9 0 ，2 0 ( 1 5 ) ：3 7 - 4 3 18 h kr o n e r c 0 m p a r a t i v e p e r f or m a f i c e s t u d y 0 f s p a c e p r i 0r i t ym e c h a n is msf ora t mn e t w or ks i n ：【e e ei n f 0 一 c o m 9 0 19 9 o p p 1 】36 1 j4 3 i9 h ，k r o t i e r ，g h e b u t e er n e ，p b 0 y er ，a gr a v e y ，p r i 0 r i t y m a n a g e m e l l t i r la t ms w i t c h i n gn o d es ，i e e ej o ur n a l0 nse 1e c t e d ar e asi nc 0 m i l l u n i c a t i o ns 19 91 ，9 ( 3 ) ：418 4 27 2 0 c h u n gg k a n g ，q h e u e i n ga f t a l y s is0 f e x p i i c i tp r i 0r i t y ass i g n m er l tb u f f era c c es ss c h e m ef o ra t mr l e t w o r k s c 0 m p u t e r c or n m u n i c a t i o n s ，19 98 ( 2 1 ) ，9 9 6 10 0 9 一 笙至蔓至耋苎堕 ，_ h ，一 一 2 1 y ml i n ，j o h na s i l v es t er ，pr i 0 r i t yq u e u e i n gs t r a t e g i e s a n d1 3u f f e ra l l o c a t i 0 r lpr o t o c o lsf ort r a f f i cc 0 n tr o l