（概率论与数理统计专业论文）离散时间排队系统及其在计算机网络中的应用.pdf

摘要 = = = ：= = = = ：! = = ：! = = = = = ：= ：! = = = = = = = = = = = = = = = = = = ! = = ! ! = = = = = = 离散时间排队系统及其在计算机网络中的应用 专业；概率论与数理统计 博士生：周文慧 。 指导老师：邓永录教授 摘要 二十一世纪是一个信息化时代，而这一信息化极大地依赖于信息的传送工 具计算机网络。正是计算机网络才使得人们可以方便、迅速、可靠地传送 和交换信息。计算机网络的系统研究始于上个世纪八十年代，现在已经发展成 了一个研究热点。 本篇博士论文主要分析了离散时间的排队系统及其在计算机网络中的应用。 在这里主要应用在计算机网络中对特定机制或策略的性能分析。在已有的许多 工作中，很多研究者使用连续时间排队模型来分析计算机网络。可是，在计算 机网络中大多数实际模型都是离散时间的，即把时间轴按被称为时隙( s l o t ) 的基 本计时单位划分成小时间段。如；t d m a 机制，b 4 s d n 赠络中a t 珏多路复用技 术，c s m a 协议等等都需要离散时问模型来刻划。如果使用连续时间排队模型去 分析这些模型得烈的研究结果往往与实际情况有些差距，只能作为一种近似。 因而利用离散时间排队模型去分析更符合实际情况得到的结果也更精确。 对一般的数学模型来说，离散时间模型要比连续时问模型要简单些，而且连 续时间模型的处理方法可以通过时间参数的离散化直接应用到离散时间情形。 但对于排队模型则并不如此，其中离散时间模型不但不能由连续时间模型离散 化得到，而且研究起来比连续时间模型更为复杂。这主要由于在处理连续时间 排队模型时一般假设在同一时刻点上顾客的到达和离去不会同时发生。但是， 对离散时间排队模型却不能这样处理。这时顾客的到达与离去发生在同一对刻 点是正常现象。因此我们需要把离散时间排队系统单独提出来讨论。 本文共分四章讨论了三个模型，着重于有相关弱达的离散时间排队系统。 第一章为引言，回顾了排队论的历史，阐述了计算机网路的一些基本技术及 术语，分析了离散时间排酞系统的特殊性。 z h o u ，w e n j a u i h o t m a i e 渺第i 页。共7 0 页博士学位论文 在第二章中我们考虑一个用两个状态的马尔可夫过程刻划的相关源到达 的离散时间排队系统。我们把这样的到达过程称为有b e r n o u l l i 突发性的到达。 并考虑服务器有中断( i n t e r r u p t i o n l 。这一模型来源于计算机网络中的接纳控制 问题。在这一章中我们利用矩阵分块和概率母函数的方法得到了模型稳态队长 的概率分布n j 。通过这个模型的稳态解，我们分析了两种报文抛弃策略：部分 报文抛弃策略( p m d ) 和早期报文抛弃策略( e m d ) ，得到了两种策略的有效输出 率( g o o d p u tr a t i o ) ，即稳态下，到达的报文被完整传送出去的比例，并做了数值 解，以验证有效输出率与各参数之间的关系( 特别是与突发性因子b 的关系) 。 第三章则研究了一个用时间序列一阶离散自回归过程( d a r ( 1 ) ) 来描述相 关到达的d 4 r ( 1 ) g e o 1 离散时间排队系统。在求解过程我们使用平常的概率母 函数的方法，但对于其中的圣( 2 ，o ) ，我们使用了嵌入马氏过程的方法来进行求 解。 在最后一章我们使用了随机比较方法来分析到达的正相关性对排队性能的影 响t 介绍了多维随机序超模序( s u p e r m o d u l a ro r d e r ) ，并得到了它的一些性 质。再利用超模序分析有正相关到达的离散时间排队系统的一些稳态随机比较 结果。并讨论了第二、三章的到达的正相关性。 关键词：离散时间排队系统，相关达到，报文抛弃策略，随机比较方法。 z h o u 、e n h u i h o t m a i l c o r n 第i i 页，共7 0 页博士学位论文 英文摘要 a n a l y s i so fd i s c r e t e t i m eq u e u e a n di t sa p p l i c a t i o n i nc o m p u t e rn e t w o r k m a j o r ：p r o b a b i l i t ya n d s t a t i s t i c s n a m e ：z h o u ，e n h u i s u p e r v i s o r ：p r o f e s s o rd e n gy o n g l u a b s t r a c t t h e2 1 t hc e n t u r yi st h et i m eo fi n f o r m i z a t i o n a n dt h ei n f o r m i z a t i o nm a i n l yr e l i e so n t h et o o l so f t r a n s f e r r i n gi n f o r m a t i o n c o m p u t e r n e t w o r k i ti sc o m p u t e rn e t w o r kt h a t m a k e s p e o p l et r a n s f e ra n de x c h a n g ei n f o r m a t i o nr a p i d l y , h a n d i l ya n dr e l i a b l y r e s e a r c h i nc o m p u t e rn e t w o r ks t a r t e df r o mt h e8 0 so ft h el a s tc e n t u r y n o w ，i tb e c o m e sar e s e a r c h h o t s p o t i nt h et h e s i s ，w em a i n t ya n a l y z ed i s c r e t e - t i m eq u e u e sw h i c hh a v ea p p l i c a t i o ni n c o m p u t e rn e t w o r k ( h e r et h ea p p l i c a t i o ni st h a tw eu s ed i s c r e t e - t i m eq u e u et oe v a l u a t e t h ep e r f o r m a n c eo fs o m es c h e m eo rp r o t o c 0 1 ) i nm o s to ft h ee x i s t i n gl i t e r a t u r eo nt h e p e r f o r m a n c ee v a l u a t i o n ，c o n t i n u o u s - t i m eq u e u e sw e r eu s e dt oa n a l y z ec o m p u t e rn e t w o r k h o w e v e r ，t h e r ea r em a n yr e a lm o d e l si nc o m p u t e rn e t w o r ka r eb a s e do nd i s c r e t e t i m e ，i nt h e s em o d e l s ，t h et i m ea x i si sd i v i d e di n t of i x e d - l e n g t hs l o t sa n dt h es e r v i c e o fac u s t o m e rm u s ts t a r ta n de n da ts l o tb o u n d a r i e s ，e q t i m e - d i v i s i o nm u l t i p l ea c c e s s ( t d m a ) s c h e m e s ，a s y n c h r o n o u s t r a n s f e rm o d e ( a t m ) i nt h eb r o a d b a n d i n t e g r a t e ds e r - v i c e sd i g i t a ln e t w o r k ( b i s d n ) ，s l o t t e dc a r r i e r s e n s em u l t i p l ea 一2 c e s s ( c s m a ) p r o t o c o l s e t c i fw eu s ec o n t i n u o u s t i m eq u e u et od e s c r i b et h er e a lm o d e l ，t h er e s u l tm a yb e i n a c c u r a t e s ow en e e du s ed i s c r e t e - t i m eq u e u et oa n a l y z er e a lm o d e l s i n g e n e r a l m a t h e m a t i c a lm o d e l s ，t h ed i s c r e t e - t i m em o d e l sa r e s i m p l e r t h a n c o n t i n u o u s - t i m em o d e l s ，a n dt h em c t h o do fc o n t i n u o u s - t i m em o d e l si sa v a i l a b l et o d i s c r e t e - t i m em o d e l sb yd i s c r e t i z a t i o n h o w e v e r ，i nq u e u e i n gt h e o r yt h ed i s c r e t e - t i m e m o d e l sa r em o r ec o m p l i c a t e dt h a nc o n t i n u o u s - t i m eo n e s w h a ti st h ec a u s e ? i n c o n t i n u o u s - t i m eq u e u e st h ep r o b a b i l i t yo ft h a t8 , 1 1a r r i v a la n d8d e p a r t u r eo c c u r r i n g z h o u w e n _ h u i h o t m a i l c o r n 第i i i 页，共7 0 页博士学位论文 s i m u l t a n e o u s l yi sz e r o ，w h e r e a si ti sn o t s oi nd i s c r e t e 。t i m eq u e u e s t h ep a p e ri sa r r a n g e da sf o l l o w s ： c h a p t e r 1i si n t r o d u c t i o n ，w el o o kb a c ko nt h eh i s t o r yo fq u e u et h e o r y , a n d i n t r o d u c e s o m eb a s i ct e c h n o l o g ya n dg l o s s a r yo fc o m p u t e rn e t w o r k i nc h a p t e r2 ，w ed i s c u s sad i s c r e t e - t i m eq u e u ew i t hb e r n o u l l ib u r s t ya r r i v a lw h i c h i s d e s e r i b e db yt w o - s t a t em a r k o vc h a i n t h i sm o d e l i sf r o ma d m i t t a n c ec o n t r o lo fc o m p u t e r n e t w o r ki nt h i sc h a p t e rw eo b t a i nt h ec o m p l e t es t e a d y - s t a t eq u e u el e n g t hp r o b a b i l i t y d i s t r i b u t i o np l jb rt h em e t h o do fb l o c km a t r i xa n dg e n e r a t i n gf u n c t i o n u s i n gt h e s t e a d y s t a t ed i s t r i b u t i o n ，w ee v a l u a t et w om e s s a g ed i s c a r d i n gp o l i c e s ：p a r t i a lm e s s a g e d i s c a r d i n g ( p m d ) p o l i c ya n de a r l ym e s s a g ed i s c a r d i n g ( e m d ) p o l i c y , a n dc o m p u t e t h e p e r f o r m a n c ei n d e x 一g o o d p u tr a t i o a tt h ee n do ft h i sc h a p t e r ，w em a k es o m e n u m e r i c a lr e s u l ta n dv a l i d a t et h er e l a t i o nb e t w e e ng o o d p u tr a t i oa n dp a r a m e t e r s ( i n p a r t i c u l a r ，t h ei n f l u e n c eo fb u r s t yf a c t o r ) i nc h a p t e r3 ，w ec o n s i d e rad a r ( 1 ) l g e o 1d i s c r e t e t i m eq u e u e i n gs y s t e m ，w h e r e d a r ( i ) i st h ed i s c r e t ea u t o r e g r e s s i o nw i t ho r d e r1 _ t ot h i sm o d e lw eu s ep r o b a b i l i t y g e n e r a t ef u n c t i o nt os o l v e b u t 垂( z ，0 ) i sd i f f i c u l tt oo b t a i n h e r ew eu s ee m b e d d e d m a r k o vc h a i nt oa n a l y z e f i n a l l y ，w ea n a l y z et h ee f f e c t o fp o s td e p e n d e n to fa r r i v a lo nq u e u eb e h a v i o rb y s t o c h a s t i cc o m p a r i s o nm e t h o d h e r e ，w ei n t r o d u c em u l t i v a r i a b l eo r d e r 一s u p e r m o d u l a ro r d e ra n ds t u d yi t 7 sp r o p e r t i e s u s i n gt h e s ep r o p e r t i e s ，w eo b t a i nt h ec o m p a r i s o n r e s u l to fd i s c r e t e - t i m eq t i e u ew i t hp o s td e p e n d e n ta r r i v a l s ，a n da n a l y z et h ep o s td e p e n d e n to ft h ea r r i v a l si nc h a p t e r2a n d3 k e y w o r d ：d i s c r e t e - t i m eq u e u e ，c o r r e l a t i o n a la r r i v a l ，m e s s a g ed i s c a r d i n gp o l i c y ， s t o c h a s t i cc o m p a r i s o nm e t h o d z h o u w e n j m i h o t m a i l c 0 1 1 2第i v 页，共7 0 页博士学位论文 第一章引言 第一章引言 1 1 计算机网络与通信技术 计算机是2 0 世纪最重要的发明之一。计算机的发明使彳导对信息的处理和加 工更加简便、直接，借助于计算机，人类具有了处理异常复杂系统的能力。在 现代社会中信息已成为经济发展的重要源动力，人们对信息的需求量越来越 大，范围越来越广，对信息收集、传送、存储和处理的能力要求也越来越高。 显然，单枪匹马的计算机操作己不能满足人们的这些需求。这样计算机网络就 应运而生了，计算机网络的发展与完善，真正使得人类跨入了信息社会。目 前，从政府、企业、学校到生活小区，各行备业社会的各个角落都感受到了 计算机网络所带来的新变化。2 l 世纪，我们面临的是一个网络化时代。 计算机网络是计算机技术与通信技术相结合的产物。利用通信线路和通信设 备，将地理位置不同的、功能独立的多台计算机相互连接起来，以功能完善的 网络软件来实现资源共享和信息传递就构成了计算机网络系统。当前人们熟知 的因特网，就是一个全球最大的计算机网络。 对计算机网络进行系统地研究始于上个世纪八十年代，现在已经发展成r 一 个研究热点。丽对计算机网络的性能评价( p e r f o r m a n c ee v a l u a t i o n ) 是计算机网路 和计算机系统研究与应用的重要理论基础和支撑技术，是通信和计算机科学领 域的重要研究方向。本文正是乖j 用排队论来做网路性能评价。为了更好地理解 后面分析的排队模型的背景以及叙述的方便，下面介绍下一些通信专业术语和 基本通信技术。 缓冲器 英文是b u f f e r ，又称缓冲区，存储器的一部分用于储存一定数量的数据或 文本，直到其被处理或显示。其实也就是我们平时所说的排队等待房。 时隙 英文是s l o t 计算机网络中的基本时间单位。般以处理机的机械循环时问 z h o u w e n h u i h o t m a i l c o n l 第1 页，共7 0 页博士学位论文 1 1 计算机网络与通信技术 ( 对于计算机称为时钟周期) ，或通道、传输线上的信号的比特时间。或固定 数量的任何数据单元的脉冲持续时闻等作为基本时间单位。例如，我们用电话 机说话，如果做如下规定：每人说一分钟，轮流说。在对方说的时候已方不许 说。这时我们就可以说每个时隙是一分钟。 数据包 又称报文分组，信息包，英文是p a c k e t ，在网络上发送的数据的单位。分组 中除了数据外，还包括发送者和接收者的地址以及差错控制信息。 报文 又称消息、电文，英文是m e s s a g e ，在网络上需要传送的完整信息，例如： 封电邮或一个网页等。在分组交换中，往往被拆分成若干个数据包进行传送。 数据交换技术 在大型计算机网络中，计算机之间传输的数据往往要经过多个中间节点才能 从源地址到达目的地址。数据如何透过中问节点进行存储转发就是数据交互技 术要讨论的内容。下面我们就来介绍三种关键的交换技术：线路交换、报文交 换和分组交换。 ( 1 ) 线路交换 也叫电路交换，其特征是为源节点和日的节点之问建立一条专用的物理连 接直到数据传输结束。我们常用的电话网就是采用电路交换的。线路交换的 优点是传输可靠、迅速、连续稳定，但是信道利用率不高。 ( 2 ) 报文交换 报文交换属于存储交换其原理是：把要传送的数据存储起来，等到线路空 闲时再发出去。如果报文较大。则经过网络时的延迟相：长，不能满足实时或 交互式的通信要求。 ( 3 ) 分组交换 分组交换是为了减少报文交换的缺点而提出来的。再分组交换中将传输 z h o u w e n _ h u i h o t m a i l c o r n 第2 页，共7 0 页博士学位论文 第一章引言 的数据分为几个短的数据包( 或称分组，p a c k e t ) ，一般数据包长度为1 0 0 0 - - 2 0 0 0 个 字节，每个数据包中加有控制信息，其中包含报文传送的目的地址。同一报文 拆分的数据包到达目的地后合并成原来的报文。由于各个数据包较小，在网 络中的延时比单独传送一个大的报文要短得多。但是，当同一报文拆分出来 的数据包有一个丢失后，则整个报文都不能恢复。此时，我们称该报文损坏 了( d r o p p e d ) 。当前社会上许多通信公司推出的i p 电话正是基于分组交换技术的， 因为利用分组技术使得信道利用率大大地提高了。从而降低了运营成本，所以 通常的i p 电话价格低廉。但效果却比不上传统电话，时有间断，这是因为技术还 不成熟，分组在传送过程中丢失比较严重。 a t m 网络 a t m 的英文全称为a s y n c h r o n o u s t r a n s f e rm o d e ，含义是异步传输模式。它是 线路交换与分组交换相结合的产物。a t m 网络是一种以信元为基础的快速分组 交换光纤网络，其特点是采用面向连接方式，信息被分成4 8 个字节f 外) m 5 个字节 的控制信息) 的固定长度的单元，成为信元( c e l l ) 。当网络终端向网络提出通信要 求网络根据带宽资源利用情况建立通向另一端的同定通道，建立连接后，信 元就可以沿着这条通道传送。因而a t m 网络支持多种信息传输业务f 既可以传送 实时性不强的数据，又可以传送实时性很强的语言、图象等) ，当然这些需要引 入优先权机制。 统计多路复用 英文：s t a t i s t i c a lm u l t i p l e x e r 。在a t m 网络中都采用统计多路复用技术。即 多个通信连接共用同4 高速信道，因丽往往需要缓冲器临时保存不能立即传 送的信元。这些信元在缓存器中排队等待传输。常用的排队规则有：先进 先出( f i f o ) 、后进先出( l i f o ) 、优先权服务( p r i o r i t y ) 、最短时限最先( e a r l i e s t d e a d l i n ef i r s t ，e d f ) 、一般处理共享( g e n e r a l i z e dp r o c e s s o rs h a r i n g ，g p s ) 等等。 z h o u w e n h u i h o t m a i l c o m 第3 页，共7 0 页博士学位论文 1 2 排队论的历史与发展简进 1 2 排队论的历史与发展简述 排队论( q u e u e i n gt h e o r y ) ，又称随机服务系统理论，是研究计算机网络性能 的有力工具。排队论起源于2 0 世纪初的对电话交换机问题的研究。可以这样说， 丹麦数学家a k e r l a n g 是排队论的奠基人，他在1 9 0 9 年发表的一篇关于电话通 讯的文章是一般公认最早的一篇有关排队论的著作，他完成于1 9 0 9 1 9 2 0 年间 的著作主要研究有泊松型到达，指数通话时间的多线路电话系统和有泊松型到 达、固定通话时间的单线路电话系统。随后从事排队论研究的先驱人物有法 国的f p o l l a c z e k 和前苏联的a k h i n c h i n ，他们有关排队论的工作主要在二十世纪 三、四十年代。前者主要研究了泊松型到达和一般服务时间的单服务员以及多 服务员的排队系统，后者的贡献则在于在数学理论上使排队论更加系统化和严 格化从而为吸引更多的数学家参与排队论的研究创造了条件。稍晚些时间， 瑞典的p a l m 也做了不少工作。但是直到第二次世纪大战前这些先驱所做的工 作尚未能掀起排队论研究的高潮。战后随着计算机的出现和现代科学技术的迅 速发展，许多领域提出了大量的排队论问题，排队论发展缓慢的局面很快得到 了改变。为了解决非马尔可夫排队模型，5 0 年代初英国数学家d g k e n d a l l 等人通 过引入排队过程的嵌入马尔可夫链以及c o x 等人引入补充变量使得人们在排队系 统的研究中能广泛应用马氏过程这一有用工具，从而大大推动了排队论的进一 步发展。进) k 6 0 年代后，随着计算机和通信技术的发展按优先权服务的排队问题 和排队网络的研究逐渐升温，而且随着应用深度和广度的发展，为了满足较为 。一般的复杂排队系统研究的需要，作为嵌入马尔可夫链方法的发展和补充人 们引入马尔可夫更新过程模型。另一方面又开始了系统特征的近似解和上、下 界问题的研究。到了7 0 年代，由于实际问题的复杂性，往往不能某种已有的数学 模型来描述，而且要求出问题的精确解变得越来越困难。因而排队论的研究重 点逐渐由寻找精确解转移到新模型的建立与近似方法的研究。模拟、数值方法 和随机比较方法成为研究的热点。 到了二十世纪八、九十年代，随着计算机技术与通信技术的飞速发展，在计 算机网络与计算机系统的研究i l 涌现了大量的离散时问排队模型。如：t d m a 机 制【6 3 l ，b i s d n 网络中a t m 多路复用技术，c s m a 协议等等，都需要离散时间模 z h o u w e n - h u i h o t m a i l ，c o l n 第4 页，共7 0 页博士学位论文 第一章引盲 型来刻划。使得离散时间排队系统在计算机网络中得到广泛的应用，从而带动 了离散排队系统研究的热潮。b r u n e e l ，k i m 和t a k a g i 等人在这方面做了大量的工 作。 在计算机网络和计算机系统中。我们往往把数据单位( 字节、字符、数据 包、帧、报文) 看成顾客，而处理枫、传输线、通道、终端用户看成服务台， 要求存储或记忆看成排队，存储器、缓存器看成排队等待空间，这就是一个排 队系统。由于处理机是间断时间操作的，一般把处理机的机械循环时间( 对于 计算机称为时钟周期) ，或把通道、传输线上的信号的比特时问，或固定数量 的任何数据单元的脉冲持续时间等取作基本单位时问。在这样的系统中，所有 事件的发生( 输入、预算、操作、输出) 都是在离散时刻出现。这就是一个离 散时间的排队系统。 1 3 离散时间排队系统的特殊性 如上节所说，实际当中计算机系统及计算机刚络中出现的真实模型大 部分是离散型的，而在以往处理离散时间排队模型时，大多数情形是用连 续时间排队模型来近似，即把它们看成连续时间系统，再用相应的连续时 间排队模型的公式或采用相应的方法进行研究。事实上，这与离散时间 情形下的研究结果还是有差距的，因而近年来人们已逐渐重视对离散时 间排队问题的研究了，也有了许多重要的成果。h u n t e r 4 5 讨论了几类基本 的离散时问排队模型( 如：g e o g e o 1 ，g e d a a ，g i g e o 1 等等) 。近- 一、二十 年来，随着计算机网络的发展，涌现了许多的离散时间随机问题。基于 应用的日的，b r u n e e l ，c h a u d h r y ，k i m 等人在离散时间排队系统方面做了大 量的工作这些工作主要集中在：服务器有- p 断的( f 2 、1 1 、3 2 1 ) ，多服务员 的( 【1 4 、1 5 、2 0 ) ，模型有相关性( 【l o 2 6 、3 3 、4 0 、4 7 、4 8 、6 s ) 。缓冲器容量有 限的( ( 1 6 、1 7 、3 9 ) ，到达为批量的( 【1 8 2 0 】) | 有优先权的( f 5 2 、6 3 】) 服务器有休 假( 或修理) 的( 1 7 2 】) ，重试( r e t r i a l ) 离散排队系统( 【5 4 】) 等等。要对离散时问排队系 统的已有工作有更好的了解，可参看t a k a g iy o ，b r u n e e | i 1 7 ，w o o d w a r d1 7 7 】o 对。般的数学模型来说，离散时间模型要比连续时问模型要简单些，而且连 续时问模型的处理方法可以通过时问参数的离散化直接应用到离散时问情形。 z h o u w e n - h u i h o t m a i lc o l l l 第5 页共7 0 页 噻士学位论文 1 3 离散时间排队系统的特殊性 但对于排队模型则并不如此，其中离散时间模型不但不能由连续时间模型离散 化得到，而且研究起来比连续时间模型更为复杂。这主要由于在处理连续对闯 排队模型时一般假设在同一时刻点上顾客的到达和离去不会同时发生。但是， 对离散时间排队模型却不能这样处理，这时顾客的到达与离去发生在同一时刻 点是正常现象。因此我们需要把离散时间排队系统单独提出来讨论。 对于实际计算机系统，我们把时间轴分成固定长度的区间，称为时隙 ( s l o t ) ，一般来说就是计算机系统的时钟周期或者其倍数。我们用整数n = 0 ，1 ，2 ，表述时隙的边界点( 或分割点) ，并且指定时隙1 1 为时间区域 1 ，霹) ，顾 客到达、服务开始与结束都发生在边界点上。相邻到达的顾客的时间间距 1 是 独立同分布的离散型随机变量序列，概率分布是a k = p h = 耐，( = 1 ，2 ，) 。 再假定顾客的服务时间同分布且相互独立，概率分布是& = p s = ) ，陋= 1 ，2 ，) 。而且假定到达过程与服务相互独立。由于服务机构性能的关系，顾客 到达与离开有三种关系，从而把离散时间排队系统划分成三种系统如下： 1 ) 早到系统( e a r l ya r r i v a ls y s t e m ) 顾客只可能在( n ，礼+ ) 中到达系统，在( 礼一，礼) 中离开系统。也就是说，当顾客 在( n ，竹+ ) 中到达系统m = 0 ，1 ，2 ，) ，如果服务器空闲，这个顾客将立即接受服 务，如果服务时间只需要一个时隙，则其将在( ( n + 1 ) 一，( 札+ 1 ) ) 中离开系统。 2 ) 迟到系统( l a t ea r r i v a ls y s t e m ) 顾客只可能在m 一，佗) 中到达系统，在( n ，n + ) 中离开系统。由服务器机制的 不同，迟到达系统又可分为两种： 2 1 ) 迟到立接系统( l a t ea r r i v a ls y s t e mw i t hi m m e d i a t ea c c e s $ ) 当顾客在( n 一，n ) 中到达系统，( 礼= 1 ，2 ，) ，如果服务器空闲，这个 顾客将立即接受服务，如果服务时间只需要一个时隙，则其将在( n ，礼+ ) 中离开系统。 2 ，1 ) 迟到迟接系统( l a t ea r r i v a ls y s t e mw i t hd e l a y e da c c e s s ) 当顾客在( n 一，扎) 中到达系统，( n = 1 ，2 ，) ，即使服务器空闲，这个 顾客也不能立即接受服务，如果服务时间只需要一个时隙，则其将在 ( + 1 ) ，十1 ) + ) 中离开系统。 z h o u _ w e n _ h u i h o t m a i l c o a l第6 页共7 0 页 博士学位论文 第一章引言 下图很明显地描述了早到系统与迟到系统的分别。 可能的离去 ( a ) 早到系统 图1 1 可能的到达 可能的离去 ( b ) 迟到系统 离散时间排队模型可以与连续时间排队模型平行地进行讨论，只不过离散时问 排队模型都使用离散型分布刻划到达与服务。常使用的分布有： ( i ) 确定性分布 p k = p s 。= 女) = 1 ( k 1 ，礼 0 ) 这在计算机系统中经常用来描述服务器的服务时问： ( i i ) 几何分布。 p k = p ( a 。= ) = p ( 1 一p ) 卜1 ( k 1 ，0 p 1 ) 我们知道几何分布是离散型分布中唯一具有无记忆性的分布，而指数分布是连 续型分布中唯具有无记忆性的分布。因而几何分布具有指数分布同样的地 位，用来描述具有无记忆性的到达或服务； ( i i j ) 负二项分布， p k = p = 七) = c 鼻p r q ( k 1 ，0 p 1 ) 其中r 为正整数。负二项分布类似于1 1 分布，r 个相互独立且具有相同几何分布的 随机变量和的分布是阶数为r 的负二项分布。这种性质与指数分布和r 分布的关系 是。致的。 由于离散时问排队在同时刻有可能同时发生顾客的到达和离去，因而在研 究队长时，选择时刻点也很重要，不同的时刻不同的服务机构性能的关系有可 能稳态分布不同。 z h o u w e n - h u i h o t m a i l c o l n 第7 页，共7 0 页 博士学位论文 1 3 高散时闻排队系统的特殊性 x 。：0 l2 l l0i22i y 。：0 110001i10 乙： 121 lo l22 l0 ( a ) 平列糸统 x 。( i ，：0 11000 i1 10 y j ” 12i 10i22 10 z n ( j ) =1l000 l1l00 ( b ) 迟到立接糸境 ( c ) 迟到连接盎统 图1 2 i2 23 22 下面我们就以g e o g e o 1 排队系统为例来看看系统队长的稳态分布在不同时刻点 的取值。记q ( t ) 衰示在时刻t 系统中的顾客数。 对于早到系统。记 x n = q 一) ，k = q ( n ) ，磊= q ( n + ) ，n = 0 ，1 ，2 ， 对于迟到立接系统，记 螬= q ( u 一) ，蟛= q 何) ，磷= q ( n + ) ，= 0 1 ，2 ， 对于迟到迟接系统，记 x ? = q ( n 一) ，h 8 ) = q ( n ) ，z 磐) = q ( n + ) ， n = 0 ，1 ，2 ， z h o u w e n h u i h o t m a i c o i n 第8 页，共7 0 页博士学位论文 l l o 2 l 2 2 l 2 2 o l 1 蚺俨冰 第一章g 盲 圈1 2 详细地描述上述三种系统在相同的到达以及有相同的服务时间下的样本 路径。系统分别在时刻0 ，1 ，3 ，5 ，6 ，7 各到达一个顾客，其相应的服务时间分别 为：2 ，l ，l ，2 ，1 ，1 。通过图1 - 2 中的样本路径，我们可看出： k ) 与 k 是两个不 同的过程但存在如下关系： z 。 = ) 0 + ， ， 碟) = k ) ， 1 ) = x 。+ - ) ， 甜) = k 4 - 1 ) ， 强d ) ) = 墨) ， 球) = 义。+ 。) ， 而f “m ) 却跟上面的任何个过程都不相同。所以，在只需要研究稳态分布的情 况下，我们只要考虑( k ， k 、 硬4 三个过程即可。 1 4 论文的主要工作与安排 本文分析了几种离散时闻的排队系统，其中着重于有相关到达的离散排队系 统，并应用于对计算机网络中特定机制或策略的性能评价。 文章的主要创新点是： 1 ) 在计算机网络中成功地利用离散时间排卧、系统分析网路的性能，比以往使 用连续时间排队系统去分析得到的结果更加精确些： 2 ) 考虑了几种不同模型描述的相关到达，一种通过马尔可夫过程描述的有突 发性的到达，种则是利用时问序列刻划的。分析了到达的相关对排队性能的 影响： 3 ) 通过引入和研究超模序，利用随机比较方法获得具有正相关到达的离散时 间排队系统的排队性能指标的随机比较结果： 4 ) 做了数值算法得到一些数值解，并在m a t l a b 的环境巾实现，进步验证分 析结果的可靠性。 下面再来介绍- 下本文的主要结构，文章共分四章讨论了三个模型。 第一章为引言，简要回顾排队论的历史和介绍计算机网络的一些基本技术及 术语，指出了离散时间排队系统的特殊性， 在第二章中我们考虑个用两个状态的马尔可夫过程刻划的相关源到达 的离散时问排队系统。我们把这样的到达过程称为有b e r n o u l l i 突发性的到达， z h o u ，w e n 3 m i h o t m a i lc o i n第9 页共7 0 页博士学位论文 1 4 论文的主要工作与安排 并考虑服务器有巾断：( i n t e r r u p t i o n ) 。这一模型来源于计算机网络中的接纳控制 问题。在这一章中我们利用矩阵分块和概率母函数的方法得到了模型稳态队长 的概率分布p 。j 。通过这个模型的稳态解我们分析了两种报文抛弃策略：部分 报文抛弃策略( p m d ) 和早期报文抛弃策i 略( e m d ) ，得到了两种策略的有效输出 率( g o o d p u tr a t i o ) ，即稳态下，到达的报文被完整传送出去的比例，并做了数值 解，以验证有效输出率与各参数之问的关系( 特别是与突发性因子b 的关系) 。 第三章则研究了一个用时间序列一一阶离散自回归过程( d a r ( 1 ) ) 来描述相 关到达的d a r ( 1 ) g e o 1 离散时间排队系统。在求解过程我们使用平常的概率母 函数的方法，但对于其中的中( 2 ，0 ) ，我们使用了嵌入马氏过程的方法来进行求 解。 在最后章我们使用了随机比较方法来分析到达的正相关性对排队性能的影 响。首先介绍并研究了多维随机序 超模序( s u p e r m o d u l a ro r d e r ) ，得到了它 的一些性质。然后利用超模序分析有正相关到达的离散时间排队系统并得到系 统的一些稳态随机比较结果，最后讨论了第二、三章中提到的相关到达的正相 关性。 z h o u w e n j m i ( h o t m a i l ，c o l l l 第1 0 页，共7 0 页博士学位论文 第二章具有b e r n o u l l i 突发性源到达的早期报文 抛弃策略( e m d ) 分析 2 1 模型描述与说明 在采用分组交换技术的计算机网络中，报文( m e s s a g e ) 被拆分成若干个数据 包( p a c k e t ) 进行传送，如我们在引言中所述。而往往连续到达的数据包属于同一 报文，传送到目的地后将被重新组成报文。c i d o n 等在文献【2 1 】中介绍并分析了 这种报文分解模型。本章也正是基于这一报文分解模型进行讨论的。如果传送 过程中有一个或更多的属于同一报文的数据包丢失，则这些数据包将组不成报 文。这些报文称为损坏的报文( d r o p p e d ) 。损坏了的报文是没有用处的，因而， 我们要尽量不传送损坏的报文，以便有效地利用有限的网络资源。 在实际中计算机网络的缓冲器容量都是有限的。当缓冲器为满时，到达的数 据包将丢失。从而该数据包所属的报文也就损坏了，我们应该抛弃这个报文。 而要把整个报文抛弃，实现起来却是有难度的f 主要是很难剔除已经进入缓存器 的那部分数据包) 。因而一般都采用接纳控制技术，即对已损坏报文的已经进 入缓冲器那部分数据包我们不予理会，但是已知是损坏了的报文还没进入缓冲 器的部分将被抛弃。在a t m 网络中，传输层协议a a l ，正是基于这一思想f 见文 献【4 1 】) 。 计算机网络的接纳控制技术的一个主要方面是引入报文抛弃策略。现在已有 许多文献研究各种报文抛弃策略( 参看文献【2 7 、2 8 、5 5 】) ，其中最主要的两种策略 是部分报文抛弃策略( p m d l 和早期报文抛弃策略( e m d ) 。p m d 藏略指的是抛弃 属于损坏了的报文的数据包。这就是说，如果当一个数据包到达时，若缓冲器 已满。则将抛弃该数据包以及接着来到的属于同一报文的数据包。e m d 策略是 在p m d 策略基础上改进的，除了具有p m d 策略相同的机制外，还增加了一个阈 值k 当系统队长达到阈值k 时，新到达的报文将全部被抛弃。因而，当k 等于缓 冲器容量时e m d 策略便变成了p m d 策略了。所以，我们只需要研究e m d 策 略即可。 z h o u w e n _ h u i h o t m a i l e o m 第1 1 页，共7 0 页博士学位论文 2 1 模型描述与说明 迄今已有的对报文抛弃策略的性能进行分析的研究成果，大多数还是停 留在使用计算规仿真、流分析近似等方法上，如：k i m 和“f 5 3 】k a w a h a r a 和k j r a j i m a 等【5 1 】都利用仿真手段得到一些数值例子，以说明p m d 策略和e m d 策略要比不使用报文策略要好。d u b e 和a l t m a n 则在【2 7 、2 9 】中利用流( f l u i d ) 分 析p m d 鼻t 略和e m