（计算机软件与理论专业论文）综合业务数字网atm交换的建模研究.pdf

论文摘要 y s 2 2 7 l q 随着网络的宽带化和综合化，人们在a t m 交换结构的设计上越来 越倾向于易于硬件实现的输入排队交换结构。作为前期“人力优先” 和“空间优先”研究的接续，本论文主要报告采用“时间优先”调度 机制的输入排队a t m 交换的性能情况。 输入排队a t m 交换的最大问题是它的队首( h o l ) 阻塞，它是由 于严格的f i f o 服务规则所引起的，在对该问题的解决上主要涉及两个 方面：调度策略的选择和交换结构的确定。在人们对a t m 交换网络系 统模型综述的基础上，本论文综述了输入队列a t m 交换的调度策略和 各种改进的交换结构。并将时间优先级控制方式应用于线群结构输出 的交换机中，通过对信元传送机理的分析，提出了优先级调度输入一 线群多通道输出的系统模型。在设定工作环境及条件的基础上，本论 文首次为该系统模型建立了肯达尔排队模型。即： | | k | g | 1 | | 排队室1 的大小f c f s ( 对于同类信元) 排队室2 的大小非占先式p r ( 对于不同类信元) 。 o 并运用状态转移方法进行了解析。最后的模拟实验数据表明优先级调 度输入一线群多通道输出a t m 交换系统模型较好地改善了h o l 阻塞， 提高了输入排队a t m 交换网络的性能。 关键词输入排队，a t m 网络，优先级，建模研究 a b s t r a c t w i t ht h em a s s i v e d e v e l o p m e n t o f i n f o r m a t i o n ，t h e i n p u t q u e u e d s w i t c h e s ，w h i c h i se a s i e rt o r e a l i z e ，a r em o r ep r e f e r a b l e t h a nt h e o u t p u t - q u e u e do n e si nt h eb i s d n a sas u c c e s so ft h ef o r m e rs t u d yo n “h u m a np o w e rp r i o r i t y a n d “s p a c ep r i o r i t y ”w ed i s c u s st h ep e r f o r m a n c e o ft h e i n p u t q u e u e d at ms w i t c h e sw i t h “t i m e p r i o r i t y c o n t r o l c a u s e db yt h es t r i c tf i f os e r v i c er u l e ，h o lc e l lb l o c ki st h ev e r y d i s a d v a n t a g eo ft h ei n p u t - q u e u e da t ms w i t c h e s t os o l v et h ep r o b l e m ， t w ot h i n g ss h o u l db ec o n s i d e r e d ，t h a ti s t h es e l e c t i o no fs c h e d u l i n g s t r a t e g y a n d t h ed e c i s i o no fs w i t c hs t r u c t u r e b a s e do nt h e t i m e l y s u m m a r i z a t i o no nat m s w i t c h ，i nt h et h e s i s ，w eh a v ed e t a i l e dm o s to ft h e s c h e d u l i n gs t r a t e g y a n d i m p r o v e d s w i t c hs t r u c t u r er e l e v a n tt o i n p u t - q u e u e ds w i t c h e s ，a n db y t h eo v e r a l l a n a l y s i so ft h e c e l l s e n d i n g p r o c e d u r e ，w ep r e s e n t e das y s t e mm o d e ln a m e dt i m ep r i o r i t ys c h e d u l i n g i n p u t l i n eg r o u po u t p u tw i t hm u t i - c h a n n e lm o d e l w i t ht h es e t t i n go f t h e p e c u l i a rc o n d i t i o n s ，w e c o n t r i b u t et h ea b o v es y s t e mm o d e lf o rt h ef i r s t t i m et oak e n d a l lm o d e l ，i e a g ，l l i ：t h e s i z eo f b u f f e r ：1 ，n n f 。c 。f ，s ，。( 。f o 。r ；。s ，a r m e 。k 。i ，n 。d 。s ，。o 。f ，。e 。e 。1 1 ： 。，。，。， w er e s o l e dt h em o d e lb y “s t a t et r a n s f e r ”m e t h o d t h ef i n a ls i m u l a t i o n e x p e r i m e n t s h o w st h a tt h en e wm o d e lc a nb 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 hd r a m a t i c a l l y k e y w o r d s ：p r i o r 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 删) 正是适应这种要求的现代计算机通信网 的发展方向。 宽带综合业务数字网是一种全数字化、高速、宽带、具有综合业务能力的智 能化通讯网。它可以把当今世界上所有的通讯业务全部集成在一个通讯网络中， 做到电话、电视、电脑一体，话务线、有线电视线、数据线合一，实现通讯系统 和各种通讯业务的高度综合集成，是当今世界上最先进的通讯网。以信元( c e l l ) 为信息传输、复用、交换及处理单位的异步转移传输模式( 爿7 聊技术成为实现宽 带综合业务数字网的关键。a t m 是作为宽带i s d n 的一部分工作被发展起来的， 宽带i s d n 以a t m 技术为信息传输方式。因此研究a t m 交换对于宽带i s d n 的建设， 乃至信息高速公路的建设都有重要意义。 为了描述通信量，理解不同通信量的类型，需要对网络的性能进行建模解析。 但是，b - i s d n 中a t m 交换的建模有其特有的困难。姑且不谈数学解析的难度。仅 就建立肯达尔排队模型而言。有如下困难。从所传输的业务角度看：首先，在b - i s d n 中传输的信息具有多样性、随机性甚至突发性，很难确定业务的到达规律；其次， b - i s d n 中要进行多种业务的综合传输，为了充分利用网络资源并满足各种业务的 o o s ，更需要进行优先级控制，即要综合控制多优先级业务的传输。从交换结构 角度看：一方面，由于要对不能立即转发的信元进行缓存，需要在交换机中设置 缓冲器，不同的缓存设计方法对应于不同的交换结构。即交换结构具有多样性： 另一方面，在交换机输出端交换的信元也可能出现交换失败返回缓冲器而不是一 次交换成功，交换成功的信元有可能在缓冲队列中排队而不是立即被发送，即信 元的服务规律难以确定。综合以上原因，目前对a t m 交换的性能分析大多集中在 仿真分析阶段，定量的数学建模及解析亟待进行。 本章下面对a t m 交换中所涉及的主要内容进行简单介绍，为理解后面的建模 做准备。 一、传输业务的优先级分类标准 传送多优先级业务是b 1 s d n 的一个最大特点。目前对优先级的选取方法分 为时间优先、空间优先和人力( 服务员) 优先。 所谓时间优先是指在竞争服务的次序上有优先权关系。例如与非实时业务相 比，实时业务对传输延迟要求较高，因此应赋予更高的优先级，这种优先即为时 间优先。在计算机网络中，时间优先级的控制问题一直是研究的热点。6 1 。目前 关于占先式优先权和非占先式优先权的研究仍在进行中。 所谓空间优先是指在竞争有限的排队空间上有优先权关系。当有多类业务同 时要到缓存队列中排队时，对丢失敏感的业务应具有更高的优先级，这种优先就 是空间优先。较高的空间优先权可以保证对丢失敏感的业务首先进入缓存队列， 而当缓存队列溢出时，首先丢弃低优先权业务。空间优先权控制在最近几年研究 较多订1 如，主要策略有简单丢弃、挤出( p 0 ) 和部分缓存共享( p b s ) 等。 所谓人力优先是指在对服务员的使用上有优先关系。人力优先主要是为高优 先级业务预留传输链路，即预留服务员，以更好的满足其q o s 。现在对人力优先 的研究还相对较少，本论文的前期研究i l3 j 进展之一是在三类业务的情况下使用人 力优先策略对有关系统进行研究的范例。 二、交换结构的划分介绍 按缓冲器位置所分。交换机主要有输入排队、输出排队、共享缓存三种类型。 输入排队由于其结构内部的运行速率就是输入，输出端口的速率，实现复杂度 较输出缓冲和共享存储器缓冲要小的多，但是输入排队交换机在每个输入端口都 有独立的缓冲器，来自不同输入端口的业务有可能同时要求输出至同一输出端口， 这就产生了所谓的“队首”阻塞问题，这大大降低了输入排队交换机的吞吐量； 输出排队交换机在每一时隙允许所有到达的输入信元交换到输出缓冲器，所以吞 吐量接近i ，但同时它要求输出缓冲器的操作速率为线路速率的倍，实现不易； 共享缓存交换机利用中心控制来解决排头阻塞问题，但需要高速、复杂的存储器 管理逻辑，广播功能也不易实现。三种类型的交换结构均有自己的优势和不足， 更为详尽的综述可以参阅文献 1 4 , 2 9 。 2 三、本课题的前期研究进展介绍 本课题定位于输入队列的交换结构，研究各优先级控制策略在输入队列交换 结构中的性能。为此，在本论文之前已分别对人力优先和空间优先作了相应的研 究工作0 3 j 5 】。 1 在人力优先方面，针对a t m 交换网和综合业务数字网( 删) 中多类业 务( 主要有话音、数据、视频三种) 的传输问题，提出了按照人力优先的策略进 行链路分配，并根据这些新策略给出了系统的排队模型如图1 所示。当设处于忙 状态的服务员数目为k 时，服务规则为： 当且仅当k - = o 时，新到达的优先级最低的1 类顾客能立即获得服务。 当且仅当1 时，新到达的2 类顾客能立即获得服务。 当且仅当七2 时，新到达的3 类顾客能立即获得服务。 这样在同等条件下，服务不同类优先级顾客的服务员数量是有差别的，实现 了所谓的人力优先。 顾客源 + 顾客离开 服务 图1人力优先策略下系统的排队模型 文章设定到达为二项式到达、服务满足负指数分布，通过分析得到状态转移 图如图2 所示。该论文已正式发表在此不再赘述。详细解析过程请参见文献1 。 图2 系统的状态转移 3 2 在空间优先方面，将缓存队列的优先级控制机制应用到了a t m 网络中可 用比特率( a b r ) 业务的流量控制之中，提出了一种改进的相对速率控制算法一 一动态双门限拥塞指示( d y n a m i cd o u b l e t h r e s h o l dc o n g e s t i o ni n d i c a t i o n d d 础) 算法。在交换节点的排队队列中设置高低两个可以变化的动态门限值， 并利用该动态门限值来确定本节点的状态，通过反馈信息控制源端的信元发送速 率。文中使用流体模型对该策略的缓存性能进行理论解析，得出了一些重要的反 映该算法性能的参量表达式。文章最后的仿真结果( 见图3 ) 表明改进算法明显 减轻了源端信元发送速率的波动。该论文正在投稿中，有关的具体内容请参见文 献l5 。 m ：”“”嚣n ”“” ( a ) 确定前向拥塞指示e f c i ( c c r ) 算法( b ) d d t c i 算法 图3 在信元速率波动方面e f c i ( c c r ) 与d d t c i 算法的比较 本论文的主要工作是对一种基于时间优先级调度策略的输入队列, 4 p g 交换结 构进行了完整的建模解析。文章的组织结构为：第2 节介绍了输入队列a t m 交换 中的调度策略；第3 节将一种a t m 交换的物理模型归结成为肯达尔模型，并给出 了模型的解析过程；第4 节是数值计算的结果及实验分析；最后的第5 节对本课 题的研究进行了总结并对进一步的研究作了展望。 4 2 输入队列a t m 交换中的调度综述 2 输入队列月肼交换中的调度综述 根据前面对交换结构划分的介绍可知，在输出队列交换结构中，其交换机的 交换速率以及输出端口的信元发送速率都必须n ( 端口数目) 倍于链路的带宽， 因此输出队列交换机的实现成本高。在宽带网络中，取值较大时，输入队列交 换优势明显。 在输入队列a t m 交换结构中，信元首先按一定规律到达输入端并在缓冲器中 排队。然后，只有当信元排到队首( h o l ) 位置时，才有权参与交换结构的仲裁。 最后，交换成功的信元到达输出线并被发送离开。显然，输入队列本身存在很大 的不足：排在输入端1 3 队首的信元在与其他去往同一目的输出端口的h o l 信元竞 争失败时，仍停留在队首位置：这样其后的信元即使目的端口处于空闲状态，也 没有机会越过队首信元参与竞争，因此可能使得该输出端口空闲，以至于降低链 路的利用率和吞吐量，这就是输入队列交换结构中的队首阻塞现象。 队首阻塞现象是由于严格的先入先出( 肿) 服务规则所引起的，因此一些 改进的交换结构可以通过合适的调度策略来减轻或消除队首阻塞现象。可以说改 进现代交换机性能的主要问题就是排队和调度。 调度算法亦称作选择策略、竞争解决机制或h o l 仲裁机制。好的调度算法应 该具有以下特征：有效性，应该能服务尽可能多的输入队列，以获得较高的吞 吐量。公平性，不能使得某些输入队列长久得不到服务，即不该存在“饥饿” ( s t a r v a t i o n ) 现象。高速，算法本身应具有较低的时间复杂度。实现简单性， 算法应易于硬件的实现。稳定性，无论到达业务的特性怎么变化，算法对某个 输入的期望占用时间应保持有限。对于基于纵横交错( c r o s s b a r ) 结构的内部无阻 塞空分包交换结构，目前常见的单播调度算法主要有以下几种。 1 最大二部图匹配( m a x i m u m b i p a r t i t em a t c h i n g ) 分别将个输入端口和个输出端口看作个顶点，对于各个输入端口，如 果它有队首信元，则看作该输入端口和其队首信元的目的端口之间存在一条边。 由于个输入端1 3 间或个输出端1 3 间不可能存在边，于是队首信元的调度问题 5 2 输入队列a t m 交换中的调度综述 等效为二部图的匹配问题。二部图的最大匹配算法可以直接用到我们的信元调度 上来，但目前较有效的算法i 捕填时间的复杂性太高，为0 ( 肝s 1 2 ) ，算法的运算时 间过长。另有文献【1 9 1 提出准最大匹配算法，对于n x n 的二部图，有m 条边时， 将时间复杂度降为0 ( n - t - m ) ，但算法硬件实现困难，且运算速度慢，不适合高 速交换。 最大匹配算法有其共同的缺点。在允许的流量范围内( 稳定流量) 算法可能 导致不稳定和不公平，而在非允许的流量( 不稳定流量) 到达时可能会导致饥饿 状态产生。 2 神经网络算法( n e u r a ln e t w o r k a l g o r i t h m s ) 图4n n 输入结构a s f 系统框图 常采用的是h o p f i e l d 网络。“圳。该网络是一种单层的回复式网络，是由非线 性元件构成的反馈系统，其系统框图如图4 所示。它的一个重要特点是可以利用 模拟电子线路来实现其网络的电路模型。已有文献m 1 提出用n x n 或n x m 的 h o p f i e l d 神经网络调度信元的方法，一个 l 端口交换机的神经网络由n ，个神经 元组成，每个神经元由模拟放大器和1 7 c 电路实现。设计电路时通常以最小化特定 的能量函数为原则，从而可以得n - 部图匹配问题的解。 6 2 输入队列a t m 交换中的调度综述 结果表明：利用n n 调度信元，明显改善了输入缓冲月删交换结构( a s f ) 的 性能。但是，h o p f i e l d 神经网络调度信元也存在两个缺点：一是所选出的信元不 能保证是最优的；二是h o p f i e l d 神经网络的连接数随神经元数目平方增长，网络 的规模大大受限；另外，需要精确设计放大器和彬电路来保证网络的收敛。 3 并行迭代匹配( p a r a l l e li t e r a t i v em a t c h i n g - - p i m ) 输入队列h o l 信元调度的p i m 算法 2 3 , 2 4 包括三个步骤： 请求( r e q u e s t ) ：每个未匹配的输入向所有可能的输出发送请求。 响应( g r a n t ) ： 如果一个未匹配的输出端接收到任何请求，它将随机选择 一个进行响应，并通知相应的输入端口。 确认( a c c e p t ) ：输入端收到输出端的响应后，从所有响应中随机选择一个 予以确认，从而完成连接。 上面的三步可以不断迭代直至找到最大匹配。 磷法的第2 、3 n 步中的选择都是随机进行的，有文献分析指出，首先，每 次迭代都会在剩下的可能匹配中至少找到或排除3 4 的连接，因而算法会在至多 0 ( 锵m 次迭代后收敛于最大匹配；其次，算法可以保证所有队列最终都会得到 响应，不会出现某个端1 ：3 饥饿的情况；再次，除了排队信元的占用外，不用附加 跟踪系统过去状态的存储空间；最后，各输出端的仲裁依旧保持相对独立，这样 确保了仲裁的速度。但是随机选择也带来一些问题。( 1 ) 每个调度器必须在一个变 化的集合里做随机选择，这使得算法的硬件实现困难且昂贵。( 2 ) 在稳定流量下它 仍可能导致各连接间的不公平性。( 3 ) 户锄算法在单次迭代时对于 较大的交换系统 性能很差，最大吞吐率仅能达到6 3 ，略高于f i f o 队列。 4 轮转算法( r o u n d r o b i n - - b r ) 轮转算法【2 5 l 是为了克服p 1 m 算法的复杂性和不公平性而设计的，它同p i m 一 样由三步组成，但它不是随机调度，而是在输入输出调度器中采用固定的轮转顺 序。三个步骤为： 请求( r e q u e s t ) ：每个输入都向它的队列中的信元可能到达的输出端发送请 求。 7 2 输入队列a t m 交换中的调度综述 响应( g r a n t ) 确认( a c c e p t ) 输出端接收到请求后从它的固定轮转顺序的优先级列表里 选择当前优先级最高的一个输入，然后通知所有的请求输 入端是否被响应，并在固定轮转顺序表里将指向最高优先 级的指针舒增加1 ( 模肋，移到下一个地方。 输入端收到响应后，从它的固定轮转顺序的优先级列表里 选择当前优先级最高的一个输出，发送确认响应，并在固 定轮转顺序表里将指向最高优先级的指针a ，增加1 ( 模肋， 移到下一个位置。 r r 算法很容易在输出仲裁时出现同步现象，所以其吞吐量也不高，限制子 6 3 。 5 乩伊算法 乩伊【2 5 ，2 6 】是在r r m 算法基础上的改进，某输出端口响应优先级指针只有在该 响应被输出端确认时才移动到下一个位置。因此，乩z 尸和r r m 除了第二步之外 都是相同的。 响应( g r a n t ) ： 输出端接收到请求后从它的固定轮转顺序的优先级列表里 选择当前优先级最高的元素。输出端通知所有发送请求输入，指明其请求是否被 响应。且仅当该响应在第三步里得到相应输入的确认后，输出端才将固定轮转顺 序表里将指向最高优先级的指针毋增加l ( 模们，移到下一个地方。 这个小的改变使毗上p 算法具有以下特点： 1 最近刚建立的连接总被置为最低优先级。 2 。可以避免饥饿现象的出现。 3 在高负载情况下，各输出端口都有相同的吞吐率。 在均一的1 0 0 负载下，毗俨适用于时分复用机制，能提供1 0 0 的吞吐率。 毗伊的几种变形： ( 1 ) 优先级s l i p t 2 5 1 该方案中，在每个输入到输出给每一个优先级级别有一个 f i f o 队列。这样有p 个优先级的n x n 交换核心每个输入端都有p x n 个f i f o 队列。优先级算法严格按照优先级的高低服务。它只是对s l i p 算法的第二步稍作 改动，在响应过程中有一个优先级选择。 8 ! ! 塑叁坠型竺! 窒垫塑塑窒堡堕 ： ( 2 ) 阈值乩伊算法【2 5 】这里的阈值相当于优先级乩护中的优先级。每个输入端有 一个排序的阈值集合r = f ，如，打 ，其中f ， 幻 l l ，适当选取l l ；p r ：优先权服 务。 当l c 时，标志输入线七的排队信元不一定受到服务而离开系统，它首先要 参与随机选择以竞争服务权。当竞争失败时，观察信元可以看作被反馈回原队首， 3 基于优先级调度的输入队列a t m 交换模型 延迟一个时隙后参加下一次对输出线，的竞争。显然，在这种情况下，通过优先 级策略选中的排头信元并不一定能立即被发送走，还要取决于交换机的选择情况。 如果设返回的概率为p ，则被服务的概率为1 p 。于是这种优先权服务( p r ) 规约变成了存在反馈的p r 规约。显然它是一种区别于典型p r 4 1 , 4 2 的新的p r 选 择服务，我们称其为非典型非占先p r 规约。于是，肯达尔模型为： a g l 。i ：排队室l 的大小c f s ( 对于同类信元) l 2 ：排队室2 的大小非典型非占先式p r ( 对于不同类信元) ，fj， ( 2 ) 其中，a ：顾客到达规律：g ：一般服务；l 2 l l ，适当选取l l 。 至此得到了如图1 0 所示交换系统的排队模型，优先级调度输入一线群多通道 输出a t m 交换系统的肯达尔( k e n d a l l ) 模型是本论文首次得到的。 三、模型解析 本论文解析的排队模型是上面得到的( 1 ) 式，利用状态转移法进行求解。为 了得到相应的平均意义上的结果，我们首先对平均值求解法予以说明，然后进入 状态转移法。 1 平均值法求解的说明 经分析得知，该模型可以用概率平均值的方法进行求解。由于平均值方法已 经十分成熟，在此我们仅给出了模型的最后计算结果，详细的推导过程请参阅附 录i 、i i 。 在设定以下参数 弼第f 类信元的所需要的服务时间。 信元的平均服务率，显然有：i ：一1 工，c 排队室中f 类信元的数目( 不包括已经开始服务的信元) 。 第f 类信元从到达至开始服务，在队列中的排队等待时间。 乃第i 类信元在系统中的滞留时间。 以上定义中f = l ，2 。 我们得： 1 7 3 基于优先级调度的输入队列 珊交换模型 两：上墨! 生( 3 ) 2 t c p c 一 丽：上 当! 生 ( 4 ) 。2 , u c ( p c 一 一五) ( 一c 一 ) i ；面+ 石：士尘粤+ 上：土坐犁 ( 5 ) 2 c , u c 一 p c 2 t i c c 一 i ：砑+ 一x z ：上_ j 篡b + 上 ( 6 ) 2 , u c ( c 一 一五) ( c 一 ) t c 。 2 状态转移法的相关解 1 ) 优先级调度规则的函数化我们假定1 类信元是延迟敏感型业务，在排头 信元进行竞争时，我们给予l 类信元更高的优先级。当处于排头位置的信元被选 择发送成功后，各优先级信元进入排头位置的概率由一个与各自状态相关的函数 五似圳来确定，其中k = - i ，2 。函数五似，圳表示当系统中有i 个1 类信元，个2 类信 元时，第女类信元被选中的概率。在我们的模型中显然有： 伽，加托篓墨 且当m 或n 不为0 时有：五似，砂= _ 厅阳，彬。 2 ) 设定信元到达输入端口的过程满足p o i s s o n 分布，每个输入端口具有相同的 到达率 。系统中1 、2 两类信元的到达率分别为a i 和 2 ，且满足 ，+ a ? = a 。 于是当有一个信元到达时，该新到的信元属于l 类的概率为 j ，a ，属于2 类的概 率为l ， 。 3 ) 设定信元的服务过程为定常，包含s 个时隙，s o 。 令j ( n ) 表示任意时刻n 系统中f 类信元的数目。用( m ( n ) ，m ( n ) ) 表示系统在 h 时点的状态，由于服务为一般分布，所以 ( m ( n ) 儿( n ) ) ) 不能形成马尔可夫链。 但是当选择信元服务完离开的时点，为嵌入点时，系统的状态只与到达规律有关， 而模型中的到达为泊松流，所以 ( m ( r ) , n 2 ( r ) ) ) 在嵌入点上形成一个二维嵌入马 尔可夫链。 为求解状态转移概率，我们先分析在一个f 类信元服务过程中信元到达情况。 设定口以s j 为信元服务过程中( s 个时隙) 到达，个信元的概率，则有： b ( ，跏掣e - 一。 1 ： 设定d ( 肌，) 为在，个新到达的信元中有m 个属于l 类的概率，则有： 1 8 3 基于优先级调度的输入队列月珊交换模型 | d ( m ，) = 口( 鲁) ”( t - 鲁) “m = 口磅) ”( 鲁) 。 前面已经设定1 、2 两类信元的服务时间相同，令彳( ，m ；如，一) 表示信元正在服 务的过程中新到达m 个1 类信元，行个2 类信元的概率。于是有： 爿( ，m ；五，n ) = p s 个时隙内到达( m + n ) 个信元 p ( 新到达的( m + 疗) 个信元中有 m 个1 类信元 = b ( m + 月，s ) d ( m ，坍+ h ) = 等等e “c 扣争 ：等兰竽要。一m ! 竺掣4 r ( 每) 一 ( 8 ) ( m + n ) 11 7 ! ! 、a 。、 其中州+ n s 记n ，为系统由状态( l = m = ) 转移到状态( m = m ，n 2 = 一) 的状态转移概率， 于是有： ( 1 ) 当i = 0 且j = o 时，无论到达的信元属于哪一类，都立即进入服务，注意到当到 达信元数大于排队室大小时，多余的信元将无法进入队列，于是有： 爿( ，七；五，) 爿( ，；五，) ，一l 爿( ，女； ，f ) ，t b a c & ，；五，r ) r - ，- 岛 0 七 ， 岛 = s s ，l 2 t 厶，l = 上2 s t = 厶，i = 厶，上i + 厶s 其他 ( 2 ) 当i = 0 ，1 j l 2 时。下一个进入服务的信元一定是2 类信元。 4 ( ，女；如。f j + 1 ) ( 五，；五，一，+ 1 ) ( ，t ；如，1 ) ，岛j + i 爿( ，；五，) r - ，= 与一，+ 1 0 k 厶，f k = 上is s ， 厶 k 上1 ，i = 岛，岛一j + 1s s l = 上1 ，= 厶，厶+ 岛一，+ l s s 其他 ( 9 ) ( 1 0 ) ( 3 ) 当1 i l l 时，根据( 7 ) 式可知：下一个进入服务的信元一定是1 类信元。 1 9 3 基于优先级调度的输入队列a t # 交换模型 爿( ，k 一，+ l ；五，一) 彳( ，； ，l 一) ( ，k f + 1 ：五，) ，b 一 ( ，；五，f ) ，i + ib 一 0 i 一1 七 上1 ，j s l ( 2 k = 上1 ，厶一，+ 1 s ，j l l 2 i - i k 厶，l = 厶，l ：一j s ( 1 1 ) k = 厶，l = l 2 ，厶+ 岛一i j + l s 其他 可以看出，系统中所有状态间的转移概率。，形成一个转移概率矩阵 p= p ( o o ) p ( 1 0 ) p ( 0 1 ) p ( 1 , 1 ) p ( o ，l 2 ) p ( 1 ，l 2 ) p ( l l ，o ) p ( l l 1 ) p ( l l ，l 2 ) 其中每个元素p ( i j ) 都是一个矩阵 p r _ o , o ) a , o p o o ) o j ) p ( l i 埘 p m 川i j i p i m ! p l y j l i i | m p f o , l 2 ) o p o l n p ( l | ? l q o j 设平稳状态下，系统处于状态( “) 的绝对概率为p ，则该概率值可以通 过求解下面的状态平衡方程得： 鼻：户( m 吐2 ：) ：圭量鼻脚，置， m ：， “。 1 2 对于稳态概率尸俐的求解无法手工进行，本文中使用c 语言编写程序对其作 数值计算( 程序清单见附录i i i ) 。并利用下面的表达式对系统性能进行估计。 令一( f ) 和巴( f ) 分别表示排队室l 、2 中系统队长为i 的概率，则： 丑( f ) ：量尸( f ，) ， o f 厶 k = o 3 基于优先级调度的输入队列a i m 交换模型 p 2 ( i ) ：量尸( ) ，o f s 厶 从而可以得到1 、2 两类信元的平均队长酉和瓦分别为； 两= 艺嵋( f ) 瓦= i p 2 ( i ) 利用l i t t l e 公式可以求出各类信元的平均滞留时间和平均等待时间： i = 导= 去薯嵋c o = 砑+ 去 i ；等= 去善以c 。= 瓦+ 古 2 l ( 1 3 ) ( 1 4 ) 4 数值计算的结果及实验分析 4 数值计算的结果及实验分析 一、几组数值计算的结果 1 s 不同时，稳态概率的比较，图1 2 显示的是从两个不同角度观察时，稳态概 率的分布情况。 曲面对应的参数： s = 5 ，i = 0 6 ， t = 0 3 ，i2 = 0 3 ，l i = 4 ，l 2 = 1 4 得：1 类信元的平均排队队长b t = 2 3 8 0 1 5 8 l 类信元的平均滞留时间i = 7 9 3 3 8 6 2 2 类信元的平均排队队长酉= 9 4 4 7 4 8 9 2 类信元的平均滞留时间i = 3 1 4 9 1 6 2 9 网格线对应的参数： s = 4 ，a = 0 6 ， i = 0 3 ， 2 = 0 3 ，l i = 4 ，三2 = 1 4 得：l 类信元的平均排队队长瓦= 2 0 3 2 5 6 0 1 类信元的平均滞留时间耳= 6 7 7 5 2 0 0 2 类信元的平均排队队长瓦= 7 3 0 4 4 1 5 2 类信元的平均滞留时间 = 2 4 3 4 8 0 4 9 2 s 值固定取3 、三，和幻固定分别取4 和1 9 ，当1 、2 类信元的到达率分别变化 时，考察平均排队队长和平均滞留时间的变化情况。 分别取： ( 1 ) 且，从0 5 5 到0 1 5 每隔o 0 5 取值一次， l2 恒等于0 2 5 。 ( 2 ) ? 从o 5 5 到0 1 5 每隔0 0 5 取值一次， ，恒等于0 ：2 5 。 计算结果为： 4 数值计算的结果及实验分析 ，0 5 5 05 00 4 504 00 3 50 3 00 2 50 2 0 o 1 5 旦 3 5 4 3 4 9 3 4 3 33 73 3 13 2 63 2 43 2 53 3 1 一6 4 4 6 9 876 384 39 4 71 0 8 81 2 9 51 6 2 52 2 0 7 一 b 1 8 ，0 61 7 9 31 7 7 71 7 5 61 7 3 01 6 9 71 6 5 91 6 3 01 6 2 5 i 7 2 2 4 7 1 7 2 7 1 0 7 7 02 6 6 9 2 l6 7 8 86 6 3 76 51 96 4 9 9 表1 ，变化时对应的信元平均排队队长及平均滞留时间 a j 0 5 5o 5 0 o 4 50 4 00 3 50 3 00 2 50 2 00 1 5 e 3 5 034 93 4 73 ，4 434 03 3 4 3 2 43 0 52 7 2 一 i 1 4 0 01 3 9 51 38 71 3 7 713 6 l1 3 3 61 2 9 51 2 2 l1 0 1 8 7 一 岛 18 0 51 79 41 7 8 l1 76 4 1 7 4 21 7 1 01 6 5 9l5 6 71 3 7 3 一 l 3 28 23 5 8 8 3 9 5 7 4 4 】o 4 9 7 75 7 0 06 6 3 77 8 3 79 1 5 2 表2 1 7 变化时对应的信元平均排队队长及平均滞留时间 在以上两种条件下，两类的信元平均排队队长及平均滞留时间变化曲线如图 1 3 所示。 ( a ) 4 数值计算的结果及实验分析 ( b ) 图1 2 稳态下系统各状态的概率分布情况 到达率变化 到达率变化 半转露*譬岷妲粼n 4 数值计算的结果及实验分析 譬 繁 莽 蒗 业 耧 图1 3 信元平均排队队长及平均滞留时间的变化曲线 二、实验结果分析 1 当s 较小时，说明系统的平均服务率较大，因此当信元到达率一定的情况下， 系统稳态下处于各状态的概率较平缓：当s 较大时，相应的服务率较小，信元因 长时间得不到服务，从而排队的信元数较多，系统中有多个1 类和多个2 类信元 的概率就大。图1 2 就是反映了这种情况。 2 当以相同的幅度减小到达率时，根据图】3 ( 上) 中的左边部分，显然当 ，减小 所对应的l 类信元的平均排队队长变化的更为明显。这说明：同2 类信元相比，1 类信元的到达率对系统中的1 类信元的平均排队个数有更大的控制作用。类似地， 根据图1 3 ( 上) 中的右边部分可知：同2 类信元相比，l 类信元的到达率对系统中 的2 类信元的平均排队个数有更大的控制作用。这正是i 类信元具有优先级的体 现，和我们的服务规则设定是一致的。 下面分析图1 3 ( j k ) 中的左边部分曲线的先降后升的原因。当l 类信元的平均 到达率 ，小到一定的程度后( 比2 类信元的到达率 2 更小) ，则新到达的信元 属于2 类的概率大于属于1 类的概率，这时新到达的信元如果是l 类信元，它往 4 数值计算的结果及实验分析 往需要等待未服务完的2 类信元完成服务。l 类信元需要排队等待的概率增加了， 所以平均效果上，1 类信元的平均排队队长有所增长，这种增长正是非占先优先 服务规则的体现。 图t 3 ( 下1 反映的两类信元到达率变化对平均滞留时间的影响，当1 类信元的 平均到达率减小时，2 类信元因为有更多的机会得到服务因而平均滞留时间呈现 递减状态；另一方面由于2 类信元的服务机会增多，而使l 类信元等待的机会增 多，从而其平均滞留时间反而增加。对2 类信元有类似的结论。 综上，文中的模型能有效的保证l 类信元的优先服务，满足实时业务的延迟 要求：另外由于采用的是非占先优先服务规则，因此可以通过降低高优先级信元 的到达率来提高对低优先级信元的服务效率，从而模型具有很强的灵活性。 5 研究总结与展望 5 研究总结与展望 就输入排队a t m 交换而言，主要有两个研究热点：一个是调度策路的研究i 另一个是交换结构的性能分析。引入多业务后，我们对于时间、空间和人力三种 优先级机制都有所涉及。在所报告的该论文串采用的是对闯优先调度，将系统模 型的服务方式归结为两种：典型非占先优先级控制和非典型非占先优先级控制， 该排队模型的归纳方式是本文的个重大贡献。针对归纳的模型，文章给出了理 论求解的概率平均值法和便于数值计算的概率转移法。最后通过数值计算分析了 模型的性能，从关系式中也可以确定不同参数的设定对系统性能的影响。 由于时间关系，本课题还有相当多的内容没有完成。首先是论文中的第二个 模型还没有解析。这种非典型非占先p r 服务方式是种全新的方式。用传统的 分析工具很难完成，这是今后的主要工作。 其次是时间优先控制与缓冲器使用的结合。满足高优先级业务q 。s 的同时， 尽可能照顾低优先级业务，即所谓的“准公平性”问题，通常是在缓冲器设置门 限值，仲裁逻辑根据排队信元数与门限值的关系确定各类信元服务的顺序。在门 限的设置方面，多门限的清况，包括在单队列设置多门艰和在几个队列里都设置 门限值是可以深入研究的内容。 再次是优先级的种类应该增加。仅对于输入端进行建模时，增加优先级还是 相对较为简单，但如果将交换部分加入进来则信元流向更具有了不确定性。多个 类信元数目为雨，。于 是有： 砑；艺( 可厨：芝一面 ( 3 ) 第三部分：正在服务信元的剩余服务时间。在非占先的排队系统中，高优先 级信元不会挤出正在服务的低优先级信元，所以对于各类信元来讲，它们需要等 待的服务信元的剩余服务时间的平均值相同，记为矿，满足：矿：( ) 观察信元到达时见到一个i 类信元正在殷务的概率为五i = n 记瓦为正在服务的i 类信元的剩余服务时间的期望，于是有 矿= 喜n 耳= 喜n 簧= 喜五竿 其中耳= 警的证明见附录j i 3 3 附录 令正= 岛， 代入( 3 ) 式得 开：i - ib m 彬= q 一可 一l 或：砑= q 可一b 可 结合( 1 ) ( 2 ) ( 5 ) 式有 谚；万+ 订+ 而 整理得： 主一可+ q 一。可+ 万 万( 1 一) = 艺一巧+ 万 类似地，结合( 1 ) ( 2 ) ( 6 ) 式有 可( 1 一q ) = b 巧+ 用( i + 1 ) 替换( 8 ) 式中的i ，得 瓦( 1 一) = 杰一巧+ 矿 联合( 7 ) ( 9 ) 两式得 瓦= 竿掣 其中i 1 ，且记o o = 0 。 而两。而一万= 一两+ i 矿，得 万：旦 。1 一n 将( 1 1 ) 式代入( 1 0 ) 式可得 两：丑：竺： 1 0 2 ( 1 一吒) ( 1 一, 0 1 ) 将( 4 ) 式分别代入( t 0 ) ( 1 1 ) 两式得： 研= 击喜届爰 两= 丽i 善2b 篆 由于模型中的服务为定常服务，所以e x ：= ( q ) 2 = ( 瓯) 2 = 酬= ( 1 ，) ：，从而 ( 5 ) ( 6 ) ( 7 ) ( 8 ) ( 9 ) ( 1 0 ) ( 1 2 ) ( 1 3 ) ( 1 4 ) 两：一1 丑埤(15)2 , u c p c z 7 附录 两= 去石杀 1 s 根据弃= 两+ z 可以求解各类信元在系统中的平均滞留时间： i = 两+ i = 去等+ 面1 = 丽1 等 i = 两+ 瓦二去瓦i 0 + 面1 附录i i ：平均剩余服务时间页的求解 ( 1 7 ) ( 18 ) 考虑只有1 类信兀的情况，注慈到顾客到达系统届其排队时间由两部分组成： ( 1 ) 观察信元到达时，正在排队的信元的总的服务时间；( 2 ) 当前正在服务信元的 剩余服务时间。 由于信元到达时碰到有信元在接受服务的概率为形= d ， 、掣分别是信元 的平均到达率和平均服务率。所以任一顾客等候服务员空出的平均时间都是 p 职。p x 。令岛为排队等待信元的均值，而每个信元平均的服务时间为形，所 以排队顾客的总服务时间为： 彤= 0 i i 根据l i t t l e 公式： = ，其中为信元的平均等待时间。 于是彬：盟：p 睨 “ 由上面的分析得 = 彤+ = p + p 页 从而i = 导 利用已有的解析结果【2 5 】得： i ：生型；笆竖：盟 3 5 附录 附录i i i ：数值计算程序清单的主要部分 十十 + + 十 + $ 十 ， $ + + + 十 + + c o m p u t a t i o n a lp r o g r a m f o rr e s o l v et h e e q u a t i o no f s t a t et r a n s f o r m a l t i o n ， + + + +