（概率论与数理统计专业论文）大偏差原则在intree网中的应用.pdf

摘要 样本轨道大偏差原则在排队论中有重要的应用f 5 1 利用压缩原则推导 了样本轨道大偏差原则的一系列闭性质这些性质包括和，复合和离开过 程利用这些性质得到了路径可由一列递归方程得到的i n t r e e 网的平稳状 态队长的指数衰减率【1 】1 证明了当到达过程在安装了弱拓扑的测度空间 满足大偏差时离开过程也满足大偏差原则，并将此结果用到i n t r e e 网中， 得到了与【5 】相同的结论而本篇论文利用【18 j 提供的方法，在空问中利 用压缩原则推导了样本轨道大偏差原则的一系列闭性质，并将其结果应用 到i n t r e e 网中，处理了每个节点有固定服务速率且离开过程平稳的情况 关键词：大偏差原则，有效带宽。i n t r e e 网 a b s t r a c t t h e s a m p l ep a t hl d p h a sb e e ne f f e c t i v e l yu s e di nq u e u e i n gt h e o r y u s i n gt h ec o n t r a c - t i o np r i n c i p l e 。c h a n g 【5 】h a sd e r i v e das e to fd e s u r ep r o p e r t i e sf o rs a m p l ep a t hl d p t h e s e p r o p e r i t i e si n c l u d es a m , c o m p o s i t i o na n d r e f l e c t i o nm a p p i n g u s i n gt h e s ep r o p e r i t i e s ，t h e y s h o wt h a tt h ee x p o n e n t i a ld e c a yr a t e so f t h es t e a d ys t a t eq u e u el e 】1 9 t hd i s t r i b u t i o n si na n i n t r e en e t w o r kw i t hr o u t i n gc 叭b ed e r i v e db yas e to fr e e u r s i v ee q u a t i o n s i np a p e r 1 t h e y c o n s i d e ra r r i v a lp r o c e s s e ss a t i s f y i n gt h el d pi nas p a c eo fm e a s u r e se n d o w e dw i t ht h e w e a k t o p o l o g y , a n dt h ed e p a r t u r ep r o c e 日e ss t i l ls a t i s f i e st h es a m p l ep a t hl d p t h er e s u l t i st h e na p p l i d e dt oo b t a i nt h ee x p o n e n t i a ld e c a yr a t eo ft h eq u e u e 】e n g t hp r o b a b i l i t yi n a ni n t r e en e t w o r k 拍w a so b t a i n e db yc h a n g 【5 】i nt h i sp a p e r ，w ec o n s i d e ra r r i v a lp r o c e s s e s 姐t i 8 f y i n gt h el d pi nas p a c eo fc o n t i n u o u sf u n c t i o n s 略w ed e r i v et h ec k 舭r ep r o p e r t i e s f o rs a m p l ep a t hl d p u s i n gc o n t r a c t i o np r i n c i p l e t h e nt h r o u g ht h ep r o p e r t i e sw eg e tt h e e x p o n e n t i a ld e c a yr a t e so f t h es t e a d ys t a t eq u e u el e n g t hd i s t r i b u t i o n si n 眦i n t r e en e t w o r k w h i c hh a sc o n s t a n t8 翱n r a t ea n ds t a t i o n a r yd e p a r t u r ep r o c e s s k e yw o r d s ：l d p , e f f e c t i v eb a n d w i d t hj n t r n e t w o r k 首都师范大学位论文原创性声明 本人郑重声明t 所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果除文中已经注明引用的内容 外，本论文不含任何其他个人或集体已经发表或撰写过的作品成 果对本文的研究做出重要贡献的个人和集体，均已在文中以明 确方式标明本人完全意识到本声明的法律结果由本人承担 学位论文作者签名t 房效娟亲蒌乏耍再 fq 日期。2 0 0 7 年4 月1 5 日 首都师范大学位论文授权使用声明 本人完全了解首都师范大学有关保留、使用学位论文的规定， 学校有权保留学位论文并向国家主管部门或其指定机构送交论文 的电子版和纸质版有权将学位论文用予非赢利目的的少量复制 并允许论文进入学校图书馆被查阅有权将学位论文的内容编入 有关数据库进行检索有权将学位论文的标题和摘要汇编出版 保密的学位论文在解密后适用本规定 学位论文作者签名，房效娟栾菽弱 。日期l2 0 0 7 年4 月1 5 日 1 1 综述 介绍 现在通信网络要求在同一个网络上同时传输不同的服务，如声音。图 像，传真和数据等因为不同种类的服务通常要求不同的服务级别( c o b ) 那么对网络设计者而言一个有挑战性的开问题时如何有效的组合不同种类 的服务处理这个问题一个有效的途径是有效带宽理论一个随时间变化 的源的有效带宽是能满足他的( g 0 回的带宽的最小值而且，有效带宽理 论也提供了计算有效带宽的一种方法 近年来关于有效带宽理论有大量的文献早期的工作主要是在【2 l 】，【2 2 】，f 1 5 】，【1 6 】 等【2 1 1 主要介绍了对于一个不带缓冲的简单模型，我们可以通过要求从 j 类源接受访问的次数满足( 1 1 1 ) 而使溢出的概率低于希望的水平 芝：q 唧s o ( 1 1 1 ) ， 其中c 为资源的容量，q 为j 类源的有效带宽有效带宽哪依赖于j 类源 的特征，比如突发性和资源统计的多路复用的度源的带宽在网络中是随 不同的资源而变化的【2 2 】介绍了有效带宽的定义及不同种类的源的有效 带宽的可加性，总结了带缓冲的资源的模型对于各种简单的模型k e y 说 明了有效带宽可以与每个源联系起来，且通过限制服务的源可以使队伍传 输它的性能保证使得它们的有效带宽的和小于队伍的容量 这个理论进一步的发展可以看【2 】，【3 】，【1 1 】，【1 4 】，【2 5 】， 2 7 1 ，【2 9 】，【3 1 】，1 3 3 】，【4 】，m ，【9 】，【1 9 】， 【5 】，【6 】，【1 0 】等t h e g n 提供了刻画交通的两个新概念tb i e r 与关于p 的 m e r ，然后基于这两个新概念发展了关于网络运算的规则，这些规则提供 了一种解决两类排队网络稳定性问题的方法-( i ) 使排队网络的顾客有有 界时延和队长的条件，( i i ) 排队网络的队伍的队长分布有关于率口的指数 2 硕士毕业生毕业论文 2 0 0 7 篮 型尾分布的条件对于不带反馈的单类顾客的网络，他们提供了在f c f o 的条件下建立稳定性结果的方法值得注意的是关于口的m e r 在通信网络 中有重要的实际意义在通信网络中当到达过程为两个状态的马尔可夫修 正过程时，关于口的m e r 等价于近来发展的有效带宽理论，且这种等价性 可以扩展到马尔可夫过程进一步，当输入过程的关于8 的m e r 得到时， 计算网络中队伍的尾分布的界和近似值的工具可以得到，在【2 】中提供了 高速数字网的允许控制的暂行解c h 觚g 5 】利用压缩原则推导了样本轨道 l d p 的一系列闭性质，这些性质包括和，缩减，复合和离开过程利用这些 性质，他们说明了i n t r e e 网的路径可由一组递归方程得到，且平稳状态的队 长有指数衰减率而这组方程的解与近来发展的高效数字网尤其是a t m 网 络的有效带宽有关在此篇论文中证明了当到过程满足样本轨道l d p 时， 离开过程也满足样本轨道l d p 而【1 】利用1 2 6 】的结论证明了当到达过程在 安装了弱拓扑的测度空间中满足l d p 时，离开过程也满足样本轨道l d p 然 后利用此结果得到了i n t r e e 网中队长的指数衰减率为了对有效带宽理论 提供进一步的支持，论文 6 】更好地定义了在【4 9 ，2 5 中提供的计算新的计 算包括多路复用的网络计算，输入一输出关系和路径，允许我们计算i n t r e e 网中队长的尾分布的更紧的指数界特别地，如果外部到达过程和路径过 程是马尔可夫到达过程或者是自回顾过程，则局部节点的平稳队长是随机 有解的，小于等于一个常数与一个爱尔朗随机变量的和爱尔朗随机变量 的衰减率小于等于实际队长衰减率眠爱尔朗随机变量的级数是外部到达 过程和路径过程的数目【1 0 】主要考虑了服务率随时间变化的队伍，确定 了这个队伍的平稳离开过程的有效带宽然后将此结论用到服务率随时间 变化的i n t r e e 网中和有优先级的串联排队网络，在这种网络中队长的尾分 布的逼近算法也得到了另外，本篇论文中有两个重要的结果- ( i ) 服务率 随时间变化的队伍的瞬时离开过程与平稳离开过程的有效带宽一般是不同 的，( i i ) 有时候为了对平稳离开过程有更好的认识首先形成一个队伍是必 第一章介绍 3 要的我们尽管得到了队长的指数型衰减，但这些结果不能提供p ( q z ) 的 准确值。模拟经常是唯一可能的方法。对于a t m 网络总的交换机，必须确 定缓冲长度。使得p ( q $ ) 需要较长的模拟这促使了许多人做关于应用抽 样f 2 0 】【1 7 】对排队系统的。快速”模拟技术相关的文献可看【2 5 】，f 9 】，【2 4 】等 其中在例中，通过模拟他们考虑了循环a t m 排队网络的缓冲库溢出概率的 有效估计我们将应用有效带宽理论和马尔可夫可加性过程来推导为得到 单个队伍的概率估计而进行的模拟方法我们考虑的是有多个独立源，且 每个独立源为马尔可夫修正过程或自回归性过程的单个队伍这些结果将 以前关于有独立到达或者一个马尔可夫修正到达的队伍的结论扩展了进 而这些结果又被扩展到估计i n t r e e 网的损失概率实验结果表明这种方法对 很难分析的复杂排队网络在方差上可以提供许多数量级的降维f 2 2 】，i s 等 主要得到了离散时间的排队系统的有效带宽，【1 4 | 得到连续时间马尔可夫 源的队伍的有效带宽的结果而在【2 5 】中解决了更一般的连续源的有效带 宽的存在性具体地，得到了多类顾客马尔可夫流和用于模拟a t m 交通的 其他类型的源的有效带宽的存在性而且，说明了当这些源共享一个有固 定服务率的缓冲库时，对缓冲库占用的概率分布的尾分布的限制是对源的 数日的线性限制也就是说，以一个很小的损失概率我们可以假定每个源 以固定的速率传输，我们称这个固定的速率为有效带宽当交通参数知道 时，我们可以计算其有效带宽，且利用有效带宽可以得到a t m 网络的循环 交错型呼叫接收和路径算法这样，一个源的有效带宽不依赖于共享缓冲 库的源的数目，也不依赖于共享缓冲库的源的其他类型的模型参数 近来【2 3 】，删，【8 】，删对此理论作了部分总结与进一步的发展现在设计 的a t m 交换机允许连接被划分成有优先级的种类，即信息包在发送到低优 先级类之前先发送到高优先级的类当面对在a t m 网络传输中不同的交 通的不同要求时这种优先级的结构非常有用典型的实现有两种到四种优 先级类最高优先级类或许是常数- 比特一速率( c b r ) 交通，次优先级类或 4 硬士毕业生毕业论文2 0 0 7 矩 许是实时图像交通，非实时v b r 交通为更低的优先级类，这也可以进一步 被划分成两类很自然的想法是如何将有效带宽的理论进一步扩展以考虑 这些优先级类i 删回答了这个问题在这篇论文中，作者说明了当有效 带宽的定义被适当扩展时可用于实现这些目标关键是连接集合的可容纳 性可容纳性是由对每个优先级水平的线性限制包括每个优先级水平的性 能准则决定的为了这个目的，设计的连接不仅一个有效带宽，一个是它 自己优先级水平的，一个是较低优先级水平的在先到先服务的原则下， 每个优先级水平的候选有效带宽可由以前的方法决定，包含以大缓冲逼近 为基础的方法有效带宽的结构使得将积形式的随机损失网络结构用于维 数是可能的大偏差理论为统计力学，信息理论和排队论提供了一个统一 的基础有效带宽理论从某些方面平行于从古典力学到统计力学的发展 【8 】从这个角度对此理论进行了总结，给出对有效带宽理论一种直观的可以 理解的整体认识文章从一个网络的行动方程开始，然后确定了一个源的 合适的能量函数，熵函数和有效带宽函数的定义然后是有效带宽函数的 计算这计算包括多路复合，一个节点的输入输出关系和多路分离的网 络计算我们将计算运用到带宽分配和缓冲库管理上也讨论两个补充多 种( g o s ) 的方法t 简单优先级和截止类似于渐近有效带宽函数的交通描 述词我们也提供了四个参数t 平均速率，渐近方差，极值速率和平均爆发 间隔为了得到比渐近结果更好的结果，给出了信封过程和共轭过程的定 义，这可用于快速模拟，并且在论文中还指出了为了更好地应用于实践， 有效带宽理论可能的补充方向 【5 】 1 j 【10 】用相同的方法得到了一些结论即利用压缩原则推导了样本 轨道大偏差原则的一系列闭性质这些性质包括和，复合，离开过程利 用这些性质，说明了路径可由一组递归方程得到和i n t r e e 网中平稳状态队 长的指数衰减率，从而得到有效带宽 5 | 主要得到有固定服务率但离开过 程不要求平稳的i n t r e e 网的结果，【1 证明了当到达过程在安装了弱拓扑的 第一章介绍 5 测度空间中满足l d p 时离开过程也满足l d p , 然后将此结果用于i n t r e e 中， 这里到达过程包含了【5 】中不含的一些情况【1 0 】处理了当服务率随时间变 化但离开过程平稳的情况这篇论文主要利用在【l8 】中的方法处理了有固 定服务率且离开过程平稳的情况 1 2 预备知识 定义1 对数矩母函数称函数a ：r 一彤为一个实值随机变量x 对数矩母 函数 a ( 0 ) = l o ge ( e 9 x )( 1 2 1 ) 定义2 ，的f _ l 变换，的f - l 变换，是上的广义实值函数， ，+ ( p ) = s u p p 茁一，( z ) )( 1 2 2 ) z e 月p 其中口z 表示p 与z 的内积 引理1 令a 为随机变量x 的对数矩母函数，”是他的f - l 变换。则 ( i ) a 是非负，凸的且下半连续； ( i i ) ( a + r = a a ( 0 ) 在原点的邻域里是有限的，那么 o f f ) # = e x 是有限的，且等于a ，( o ) ； ( i v ) ”( p ) = o ； ( v ) a 在( 一o o ，川上是非增的，在+ o o ) 上是非降的，且 a 。( 茹) = s u p o z a ( 口) ，霉p( 1 2 3 ) f 2 0 a 。( $ ) = s u p 8 z a p ) ，z p( 1 2 4 ) 0 s o 令z 表示一个h a u s d o r i f 空间 定义3 率函数函数，：刀一丑称为率函数，若它是非负且下半连续的此 外，一个率函数称为一个好的率函数若它的水平集是紧集 令 ，n ) 为搿上的b o r e l 概率测度序列，且b 为b o r e l 矿一代数 6硬士毕业生毕业论文 2 0 0 7 篮 定义4 ( l d p ) ：我们称蜥在爿上关于i 满足l d p 是指i 是一个率函数，且 v b b 一皂鹦1 骢磐：l o g 鲰( b ) 噤罂云1l o g ( b ) 一鉴。( z ) ( 1 2 5 ) 定理1 ( 压缩原则) 【1 8 ，甩】若在z 中关于好的率函数i 满足l d p , 且，：疋一y 是到另一个h a u s d o r f f 空间的连续映射，那么，( 蜀) 在y 中满足l d p , 关于好 的率函数 j ( y ) = i n f j ( z )( 1 2 6 ) $ 爿：t 忱j = y 当我们要证明某个过程满足l d p 时，我们通常要用到这个过程的时间 加速过程和连续化过程，下面我们给出其定义过程a 的时间加速过程为 a 工( t ) = 亭a ( l t ) ( 1 2 7 ) 1 _ 设离散时间过程为僻( t ) ，t z ) ，定义它连续化过程为2 ( 0 ，t r 贾( t ) = ( p + 1 j t ) x ( l e j ) + ( t 一 t d x ( l t + l j )( 1 2 8 ) 在证明某过程满足l d p 时首先我们要确定合适的拓扑空间使得在 上面满足l d p 且，是连续的，当然这个空间也依赖于应用这就有一个权 衡。若安装的拓扑太好，将很难证明大偏差原则；若安装的拓扑太粗糙， 将很难证明连续性下面定义了一个对于单服务台的队伍和许多其他系统 都适用的空间 定义5 空间钆为连续函数的集合z ：矿一r 且满足z ( o ) = o ，恕若等= “ 且安装由比例一致范数诱导的拓扑 i i * 忙等l 等i ( 1 2 9 ) t f t 十 比例一致范数一个简单但非常重要的性质如下t 引理2 假定在吼中矿一z ，那么在紧区间上，矿一致收敛于z 换句话说， 对订 0 ， 第一章介绍 7 s u pi 矿( 力一z ( t ) i 一0 o s t s t 由于下面这个结果，紧区间上一致收敛的拓扑在与队长有关的函数中起了 重要作用 引理3 函数霉一s u p 茹( t ) 关于区闯上一致收敛的拓扑是连续的 为了得到我们需要的结论，我们需要给出时间加速的连续化过程贾在气 中满足样本轨道l d p 的定义 定义6 我们说过程 贾，n n ) 关于线性测地线，瞬时率函数h 满足样本轨 道l d p , 若它满足， ( i ) 九是一个凸的率函数，且_ 7 l ( p ) = o ，p 为平均速率； ( i i ) 贾nn n ) 在中关于好的率函数f ( 茗) 满足l d p , 其中 m ) ： 铲谁o ) ) 幽， 蚝却 ( 1 2 1 0 ) io o ， 否则 有了大偏差原则，我们利用此原则可对队长的尾概率进行估计而在通信 领域中我们常遇到这种形式上的保证，即对于给定的某个衰减参数7 0 ， 当服务速率c 为多大时能保证 p 旧 q ) 0 有 霉1 0 9 e e x p n ，萎，f ) c o ( 1 删 = 5 + i 且存在可微函数a ( 0 ) o o ，和与s , t 无关的函数0 。) = 一矿o a 3 ) 其中蝼( 目) - “罂l p s u p l o g e 撕州，口o ，a a ( 0 ) = u m _ 1 l o g e e e 蛳，p 0 s o 。 t _ ；一 ( 2 ) 4 】考虑一列非负随机变量化，t z ) ，表示我们的到达过程，定义a ( t l ，t 2 ) = k 若满足；l o g e e 9 ( t l , t a ) a ( o ，如一t 1 ) ，我们称a ( o ，t ) 为关于口( e p ) 的信封 第一章介绍 9 过程我们一般考虑其最小信封过程，定义为 ( 口，t ) = 骤泸1 g e e 0 a 卅 0 口 定义最小信封率矿( 口) = 熙s u p 竺孚兰 假定t k ，t z 还满足下列条件， ( a 1 ) k ，t z 是乎稳且遍历的； ( a 2 ) 口( 口) = 恕尘笋对o t o o 成立； ( a 3 ) 对0 t c o ，o a 是严格凸且可微的 令0 = s u p o ：d + ( 口) g ，若 m ，t z ) 表示t 时刻到达的顾客数，满足我们的 假定条件且0 0 z ) = 一矿( 1 3 4 ) ( 3 ) 【1 8 】，i 1 1 儡，t z ) 为平稳的随机过程，表示我们的到达过程，且e y o t q ) = 一t 嚣t a * ( 。+ 口。) ( 1 3 5 ) t 我们又可以得到， 恕了j - l o g p ( q 。) = 一蕊n ( 。+ 1 i t ) 6 ) _ * f r，1 口4 、 = - - s u p o 0 ：a ( 口) o ， 戈e l o ，t 】，n n ) ，在c t 中关于好的率函数五( z ) 满足l d p 驰) ； 肛 。) ) 幽蚝印 ( 1 3 7 ) i o 。， 否贝0 其中，”为a 的凸变换，”( z ) = s u p p z a ( 口) 定理2 在上述条件及假定下，戈关于线性测地线，均值p = v a ( o ) ，及瞬时 率函数a 满足样本轨道l d p , 即它在拓扑空间关于好的率函数l ( x ) 满足 l d p i 堆) ： 胂弋烈冲蚝也 ( 1 3 8 ) i o o ， 否则 令a ( 一t ，o 】表示( 一厶0 】内到达的工作量，c 为服务台的固定服务率，由l i n d l e y 递归方程我们推得q o = s u p a ( 一t ，o l c t ， 则簪= ，( 五) ，其中，( 口) = s u po ( 一t ，o 】一d 引理4 若p 0 ，b n ，当n n 时，i ，( 矿) 一，( 口) 0 ，一方面，由于矿一口在c 中，则存在满足对n n t 唧6 r + i 业笔塑l n 和t 20 a n ( - - t ，o 】 t 时， 掣一pi t ， 矿( 一t ，o 】 t ， 所以 同理 。，( 一t o 】 c ( - - t ，o 】 ，( n ”) = s u p 妒( - t ，o 】一c ( - t ，o 】 t 肘 = s u p 矿( - t ，o 】一e ( - t ，0 1 ， 0 t ? 1 1 ，( 口) = s u p 陋( 一岛o 】一c ( - t ，o j 】 o s t s l 由于在在厶上，矿一a 意味着紧区间上的一致收敛性，由引理2 我们得到 ( 1 3 9 ) 是连续的所以 ( a - ) 一，( o ) 由于o 厶，则d c 是连续的所以，( o ) = s u pf n ( 一t ，o 】一c ( 一t ，o 】中上确界可 以取到由于口为实值函数，则上确界是有限的 定理3 若p 关于线性测地线，及瞬时率函数”满足样本轨道l d p , # c ，则 鲁在r + 上关于好的率函数，( g ) 满足l d p ，( g ) 2t i n 尉ft h ( c + 删 ( 1 3 l o ) 证明；由引理4 ，是连续的，我们利用压缩原则可得到静在r + 上关于好 的率函数j ( q ) 满足l d p j ( q ) = i n f j ( o ) ：口o ，( d ) = 订 ( 1 3 1 1 ) 1 2 礤士毕业生毕业论文2 0 0 7 篮 m ，= 硼如茹 s 加， 下面我们化简率函数由于当口0 时，f ( $ ) = 0 0 ，因此我们可以将下界 限制在 口 ，( n ) = 订上 对满足，( n ) = q 的任意路径口已，肯定存在0 o ( c + g t ) 一 ，o j = d + 口 、 最后一个不等式由j e n a e n 不等式得到对t 0 ，考虑定义的路径口 以= h 几= 。 则这条路径满足，( 。) = q 且有率函数，( z ) = t a + ( c + q t ) 则 j ( q ) t a 。( c + q t ) ， 0 由此我们得到 ，( 口) 2 伽i n ft a + ( c + q f ) 且当a ( 日) 本质光滑时，我们可以得到 引理5 【1 8 】，p 1 1 ) t i n 肘f 州蚪q o 2 t i n 肘fs 口u p 。p ( q + d ) 一卿) = q s u p 0 0 ：a ( p ) ) = 一s u p 0 0 ：a ( 日) ) = 一0 + 由此我们可推得 第一章介绍 p ( q o n ) e 一扩 ( 1 3 t 3 ) 1 4 小述t 主要结果 ( 1 ) 若p 关于线性测地线，及瞬时率函数a 满足样本轨道l d p , # c ，则离 开过程西关于线性测地线，及瞬时率函数满足样本轨道l d p ， o ，o ) ： a 弋动 。 ( 1 4 1 ) 【o o ， 否则 ( 2 ) 若趸在靠关于线性测地线。均值p 及瞬时率函数峰满足样本轨道 l d p , y n 在。关于线性测地线。均值p 及瞬时率函数婶满足样本轨道l d p , 则戈+ 矿在“，关于线性测地线，均值p + ”及瞬时率函数屹满足样本 轨道l d p 。 a 皇( 霉) = s u p o z - a z ( 0 ) ( 1 4 2 ) 其中h z ( o ) = a x ( o ) + a y ( o ) ( 3 ) ( 和，p ) 关于线性测地线，及瞬时率函数心( 善) + 婶( 们满足l d p , 4 n ( t ) 按 t 递增，则p ( 弘) 关于线性测地线，及瞬时率函数a ：( z ) 满足l d p 嵫( 力；s u p 0 2 一a a ( a p ( 8 ) ) ) ( 1 4 3 ) f t o ( 4 ) 将封闭性结果用于i n t r e e 网中，采用与f 1 ，趔相同的步骤得 第一步。计算每个节点的到达过程和路径过程的对数矩母函数( 假定它们 是存在的) a j ，( = 2 骧l 。g 刀矿 j ，。o 力 ( 1 4 4 ) j ( 口) = 熙e e o 力 ( 1 4 45 ) bt 2 其中，山 ( t 1 ，t 2 ) = 叼，k ( 8 ) ，易( t l ，t 2 ) ；马( s ) 第二步t 对j = 1 ，j 递归地定义下列函数 1 4 硬士毕业生毕业论文 2 0 0 7 盎 a a o ) = “础( 9 ) + 讯( 口) ( 1 4 6 ) 女p r c d ) 奶c 2 i ：! ：。+ a 。旬， 面( 口) = n j ( a p j ( 口) ) 为a ，( 口) = c 的解 第三步t 队伍j 的平稳队长的近似估计为 其中吩是a a o ) = 勺口的解 e ( q j 2 。) e - o ；。 ( 1 4 7 ) ( 1 4 8 ) ( 1 4 9 ) 一f _ p 口 p 2 离散时间g i d i i 离开过程的大偏差原则 现在我们考虑这个队伍的离开过程，定义为 d ( - t ，0 】= a ( - t ，0 l + 口一t 一鼠 我们定义其连续化的离开过程为 d ( - t ，0 1 = o ( - t ，o 】+ q - t 9 0 其中q - t ：乙一r g t ( 口) ；s u p 口( 一8 ，一t l c ( s t ) 一s t 则按照我们时间加速的离开过程的定义我们可以得到 西= ，( 铲) 引理6 若口勺，p c ，则d o 证明要证d 靠，我们需要证明d ( t ) 是连续的，kd ( o ) = o ，8 u p i 嚣等i 是有限 的，及黯_ p 连续性若我们要证烈0 或等价的d ( 一t ，0 】按t 连续，将( 2 2 ) 写为 d ( 一t ，o j = c ( 一t ，o j + s u pt a ( 一u ，0 j c ( - u ，0 】) 一s u p d ( 一缸，o j c ( 一口，o 】) 一u 蔓一t一“s 0 显然c ( 一t ，o j = d 是连续的，而第三项不含t ，易得s u p - - 。_ 0 ，存在t ，使得对t t ，l a ( t ) 一p t i 瓯所以 则对t t l a ( - u ，一铂一l z ( - u ，- t l e ( t + q - t =s u p a ( 一u ，一t | 一c ( - u ，- t l 一u s 一# = s u pa ( - u ，一t 1 一p ( 一t ) + p ( 让一t ) 一c ( - u ，- t 】 一u s l = s u p ( 口( 一一t 】一p ( t 一力) + ( p c ) ( 一t ) s t s u pe c t + t ) + ( p c ) ( t 一t ) 一u s c = s u p 一( c p ) ( u t ) + o + 让) 现在我们假定s c 一“ 贝lq - t s u p 【- e ( u t ) + e c t + t ) = 2 e - t l 一- - t 当t ? 时，g t 主啬一o ( 由s 的任意性) ，所以差等一p 由 叫嚣i = o _ s 仰t t 时，i 器等一川 1 ，所以。t d + c t ) i i p + 1 而辫l 簧等i 上界必存在，设为m ，则 即为有限的 综上，得d 以 s u t p l 器l _ m + “+ 引理7 当p c 时，：o d 是0 0 的连续映射 2 0 0 7 芷 第二章 离敢时问g d i 离开过程的大偏差原则 1 7 证明。令矿一口，我们要证扩一d ，即 咿一d l i ：。u p i 坚粤掣l 剖坚铲i + 剖错j + 哿i 皆l 由于矿一口，则第一项显然趋于0 ，第二项上确界在t = 0 时取得，由于卯是口 的连续函数，则上确界可以取到且有限，因此它也是趋于0 的现在我们 只需要证第三项趋子0 对任意的t ， 哿i 芋i 嗡s u s p r l 芋i + 凹s u p l q 等l + s 。揖u p 毫 由引理6 ，对给定的( 假定g c p ) ，存在一个t ，对t 2 t ， g t 驰 另外，我们选取，使得当n n 时，l l 扩一a l l ，所以 i a ( - u ，- t 一a - ( - t ，一州o + t + 2 ) ，对所有的t ，“ 由相同的讨论( 且假定2 e c p ) ，则对t t 及n n ， 贮t 0 ，存在t 和，当t t 及n 2 n 时 罂i 爵l + 攀咯i 钯 现在我们来考虑第一项，t 和仍是上面选定的，则 口( 一一司一c ( 一缸，- t - ( e p ) 似一t ) + e ( u + t ) = ( c p 一) 札 4 - ( c p + s ) t d “( 一u ，一q c ( 一一t 】= 一( c i l 一2 e ) u + ( c 一芦+ 2 ) f 若假定2 e c p ，那么存在一个r ，使得对一缸一f 口( 一1 1 & ，一t 】一c ( - u ，- t 0 ，及矿( 一，- t 一e ( - u ，- t 0 颈士毕业生毕业论文 则在口一t 和贮t 中，对一u 一t 可以被替换为一r 一u 一t 现在，对一t 一t 及一t i 一让s t ， 2 0 0 7 担 l d ( 一t ，一t 】一c ( 一，一司一( n “( 一，一t 】一c ( 一让，一叫) l = a ( - u ，- t 一a - ( - ，一司 s ( t + “+ 2 ) ( r + t i + 2 ) 所以， = i ( s u pa ( - u ，- t 一c ( - u ，- t 1 ) 一( s u p 口n ( - - u ，一司一c ( 一，一叫) t s u s l t s “s 1 s u pl a ( - u ，一t 】一c ( - u ，一司一矿( 一u ，- t + c ( - u ，一t 】l t s u s l = s u pi a ( - u ，一司一矿( 一缸，一t 】l t s u s l s ( t + r + 2 ) 这个界并不依赖于t f o ，司，所以 由此证得 。鎏i 芋陋( t + r + 2 ) 定理4 若a 关于线性测地线，及瞬时率函数”满足样本轨道l d p , p c 则离开过程西关于线性测地线，及瞬时率函数q 满足样本轨道l d p n - ( 茁) = a $ ) 霉c ( 2 5 ) 【o o ， 否则 证明由压缩原则我们可以得到，( d ) = 。i ，( o n f ) ：d j ( n ) 其中 m ) ： ) d t ， o i o o ，否则 第= 章 离散时同g d 1 离开过程的大偏差原则 1 9 与n ( 茁) 对应的率函数为 刚- ，劫戤嚣 眨。， 下面证，( d ) = h c d ) 首先证明，( d ) 日( 回，假定日( d ) m ，即五c ，则n ( a 9 = f _ o 。a ( 6 ) d r 现 在我们我一个特殊的到达过程，满足 以= 也= ：s 一。 c ) 】， 硕士毕业生毕业论文 显然，在【t 鼽一2 ，梳一1 ) 内，n = 1 ，2 ，也= 以 由于”是凸函数，由j e n s e n 不等式得 熹广a ( 也) 出a ( 氅些；丝过) t 细一t 2 t i 一1 ，t 2 h l 一、t 鼽一t 2 n 一1 7 若t 2 n 刃， a ( o ) = s u p o z a ( z ) ) z = o a ( o ) 一a + ( a ，( 口) ) n ( o ) = a ( 口) a ( 口) = o a ( o ) 一a ( a ，( 口) ) 而n ( = s u p x 8 一甜，由于棚一伊0 ) 为凹函数，所以最大值在g = c 时取 $ s o 得。所以 而 所以 由此证得 n ( o ) ；o c a ( c ) a ( 力= 口c a ( 功 n ( 护) = 阮一死十a ( 刃 若到达过程互关于好的率函数c a ) 满足样本轨道l d p , i ( a ) 由式( 1 3 1 2 ) 给定”是弛( 的凸变换，即a 1 0 ) = s u p o z 一阢p ) ，而由定理4 我们知道 o e r 离开过程西关于好的率函数，( 回满足样本轨道l d p , j ( d ) 由式( 2 6 ) 给定 同样的我们也可以推导离开过程的有效带宽由于a 是凸的且下半连续 n 也是则根据凸变换的对偶性，甜满足 其中 n 0 ) = s u p o x 一口j 徊) 口j 王 ( 2 7 ) 5 ( 口) ；讹1 u p o x - i l * 。) ) = ；霉。z a + ( $ ) ) ( 2 8 ) 顼士毕业生毕业论文 2 0 0 7 越 由于此处的6 ( 口) 与到达过程的a ( 口) 起了相同的作用，我们称6 ( p ) 为离开过 程的有效带宽函数 由凸变换的对偶性质我们可以得到 1 。( 9 ) 2 ；( 8 u p 蚀一a + ( 害) ) ( 2 9 ) 与式( 2 8 ) 比较我们可以得到离开过程的有效带宽函数小于( 点点) 到达过 程的有效带宽函数 3 在i n t r e e 网中的应用 3 1 介绍i n t r e e 网及对输人流的假定 i n t r e e a t m 网络是高效数字网的一种模拟i u t r e e 网就是循环的树网。 信息包从树的叶子流向树的根部，并且在树的每个节点处都可以有外部源 的到达我们将要考虑的是离散时间有，个队伍的i n t r e e 网在这样的一 个网络里有自然的偏序关系如果从队伍t 离开的有部分进入歹，我们称队 伍i 为队伍歹的前导，队伍，为队伍i 的后继我们用p r e ( i ) 表示队伍i 的所 有前导的集合，用b u e ( i ) 表示队伍 的所有后继的集合由于网络结构是 i u t r e e ，因此s u c ( i ) 只有一个元素我们将，个队伍按顺序排，因此对所有的 i p r e ( j ) 都有i j 队伍j 是树根 我们假定路径仅依赖于顾客离开的队伍，用 p j ( 行) ，n21 = 1 j 一1 表示j 一1 个路径的随机变量序列若从队伍j 的第n 次离开进入了j 的后 继，则弓( n ) = 1 ；若从队伍j 的第n 次离开，就离开了i n t r e e 网，则弓( n ) = 0 另外，在每个节点处，比如j ，除了由队伍的前导p r e ( j ) 到达的，还有向个外 部到达过程用 ( t ) ，t = 0 ，1 ，2 批= 1 磅表示t 时刻到达的顾客数 令q j ( t ) 和勺分别表示队伍j 的队长和服务率由l i n d l e y 递归方程得 奶( t + 1 ) = ( q j ( t ) + 叼( t + 1 ) 一勺) + ，j = 1 ， 叼( t ) 表示t 时刻到达j 的工作量( z ) + = m ( o ，z ) 对外部到达过程及路径过程的假定 ( a 1 ) 所有的外部到达过程和路径过程都是独立的。且相互独立； ( a 2 ) 对，七 吩，k ( t ) ，t = 0 ，1 ，2 ) 是非负的，有界平稳且遍历的r d 取值的随机 硕士毕业生毕业论文 2 0 0 7 燕 变量序列，v t o ，- - n ，明在c t 中关于好的率函数五( 窖) 满足l d p 聊) ： f ( s ”如蚝 ( 3 1 1 ) 【o o ， 否则 其中，a j j , k 为a a j ，k ( 口) 的凸变换， a a j ，k ( 口) = 妲丙1l o g e 唧( p 。礁( 1 ) ) 存 在，为一广义实数，在原点的邻域里可微，且本质光滑 ( a 3 ) 对所有的j ， 弓 ) ，t = 0 ，1 ，2 ) 是平稳且遍历的过程 v t o ，孝( 0 1 o , v 在d r 中关于好的率函数五( 霉) 满足l d p , 其中 砸) ： 后晚忙。) ) 如蚝印 ( 3 l 2 ) 【o o ， 否则 a b ( z ) 是j ( 口