第三章 时延分析(二)-new

1、第三章 网络时延分析 赵永祥 2006/11/16 复习:Poisson过程定义 Poisson过程的三种互相等价 定义 在很小的时间间隔内只发生一 件事情，概率为t。该事件 的发生与t以外发生的事件无 关 不同时间区间内发生事件的次 数互相独立；在有限时间间隔t 内发生n个事件的概率为 事件发生的间隔互相独立，且 都服从参数为的负指数分布 数学知识：Poisson过程性质 给定时间区间(0,t)发生n个事件，则这n个时间在(0,t)独立、均匀分布 产生Poisson过程的一个方法：首先根据计数过程产生(0,t)发生的事件 次数N 在(0,t)产生N个均匀分布的随机变量 Poisson过程的叠

2、加： Poisson过程的叠加仍然是Poisson过程 Poisson过程分裂 Poisson过程的随机分裂仍然是Poisson过程 数学知识： Poisson过程性质 等车悖论 车之间的间隔10分钟，负指数分布 顾客随机到达路边打车 等到下一辆车的平均等车时间？ 根据负指数的无记忆性，等车时间是负指数分布，平均时间10分 钟 为什么不是5分钟？ 等车人观察到时间区间 平均长度为20分钟，出错？ 数学知识： Poisson过程性质 原因在于：顾客随机到达，以更大的概 率落在区间长度更大的时间段内 平均等车时间的推导 Xi:车之间的时间间隔 数学知识： Markov链 设状态发生变化的时间为：t

3、1,t2,t3,tn 时刻tn的状态为xn Markov链有如下特点 给定当前时刻的状态，未来的演变与过去 无关。 如果转移概率与时间n无关，则称齐次 Markov链 |,.,| 111111 nnnnnnnn ixixPixixixP 数学知识： Markov链 一步转移概率 | 1 iXjXPP nnij 210 121110 020100 iii PPP PPP PPP P 一步转移概率矩阵 数学知识： Markov链 平稳概率 如果存在Pj,使得 Pj,定义为稳态概率 稳态概率也可以表示为从任意初始态出发最 终转入状态i的概率 稳态概率也可以表示为系统访问状态i的频率 1 , 0 0

4、jPpp i ijij 数学知识： Markov链 全局平衡 方程式： 从状态i转 移出去的 频率等于 转移进状 态i的频率 ,.1 , 0 0 jPpp i ijij 1 0 i ji P ,.1 , 0 00 jPpPp i iji i jij 全局平衡方程式物理意义 01n+1n2 1111 201 )(PPP 全局平衡方程式：从状态i转移 出去的频率等于转移进状态i的 频率 写出状态0的全局方程式 3.3 节：The M/M/1 Queue 到达过程是参数为的 Poisson 过程 服务时间独立同分布：参数为 的负指数 分布 服务时间和到达时间间隔互相独立 一个服务器 无限等待空间 N

5、(t): t时刻系统内的顾客数目 问题难点 到达过程是随机过程，时多时少. 服务时间随机变量，时快时慢。 结果，队长也就时多时少 顾客等待时间也就时多时少 排队系统状态 描述排队系统有三个变量：t时刻系统里的顾客数目 N(t)，正在服务的顾客剩余服务时间，剩余到达时间 由于负指数的无记忆性，剩余到达时间、剩余 服务时间的分布与原来相同。 系统的状态只由N(t)决定. 系统未来的变化只与现在状态有关,与队长演变 的历史无关. M/M型排队系统的队长具有Markov性.因此我 们可以采用Markov随机过程的分析手段. 分析步骤 写转移概率 画状态转移图 求平稳概率 M/M/1 Queue: Di

6、screte-Time Approach 考察离散时间点0, , 2, (任意小) 研究离散时间点过程Nk = N(k) lim ( )lim k tk P N tnP Nn 转移概率计算 ijp ijitokijpekkijktP ijip ijitojkip k et kjkiktP ijip jito j et jtp jitottetptNttNP tp ii kt ii tk ii tj t ij 1, 0)()()1 ()2( 1, 0 1, 0)()( ! )( )2( 1, 0 1, 0)( ! )( )( 1, 0)()()0)(1)( )( 1 1, 个到达个，个顾客到达内

7、服务完 服务完个，个顾客服务完内到达 个顾客内到达 内到达一个顾客 转移概率计算 i=0，j=1 )()()0)(1)(tottetptNttNP t 内到达一个顾客 i=0，j1 )( ! )( )(to j et jtp tj 个顾客内到达 转移概率计算 i0，j=i+1 )()()1 ()2(tokijpekkijktP kt 个到达个，个顾客到达内服务完 i0，ji+1 )( )( )21( ()( 1, tot toete kkktP tPtp tt ii 个顾客个顾客，服务完内到 开）受服务的顾客还没有离内到一个顾客而正在接 转移概率计算 i0，j=i-1 )()()1 ()2(t

8、okijpekkijktP kt 个到达个，个顾客到达内服务完 i0，ji-1 )( 1( ! )( )1 ( ) 11( ()( 1, tot kP k t ee kkktP tPtp k tt ii 个顾客）服务完 个顾客个顾客，服务完内到 接受服务的顾客离开）内没有顾客到达而正在 转移概率计算 )(1 ! )( )1)(1 ( ! )( )(1 ( ,()( tott kP k et tt kP k et et kktPtPtp tk tk tu ii 个顾客离开）（有 个顾客离开）（有 个顾客离开）个顾客到达，有内有（也没有顾客离开）内没有顾客到达 M/M/1 Queue: Discr

9、ete-Time Approach 离散时间生灭过程 0: Done! 1 10 ( )( ) ( )( ) ( )( ) nn n nn 00 000 ( ) limlimlim ( ) nn nn pp 01n+1n2 1111 性能分析（一） 平稳概率分布 平均队长 00 01 1111, if 1 n n nn ppp (1),0,1,. n n pn 1 000 2 (1)(1) 1 (1) (1)1 nn n nnn Nnpnn N 性能分析（二） 平均滞留时间 平均等待时间和平均等待顾客数目 对长超过N的概率 11N T 1 and 1 2 WNTW Q 问题：如果是后到先服务，

10、概率 是什么？ 启发 =/: 利用率 服务器处于工作的状态概率 =1-p0: 对任何 M/G/1 排队系统成立 系统稳定的条件: 1 达到速率应该小于服务速率 队长增加非线性 例子1 路由器A每秒平均发送8个分组到路由器B,分组 间隔服从负指数分布,分组长度服从均值为400 字节的负指数分布.路由器A,B之间的链路速率 为64kbit每秒.问: 路由器A的缓存里平均有多少分组等待发送? 路由器A的缓存里分组大于10的概率? 解: := 8 packets/s, = 64 kbit/s/(4008 bit/packet) = 20 packets/s ) , =/ = 8/20 = 0.4 EN

11、 = 0.4/(1 0.4) = 0.67. 缓存里分组大于10的概率=0.410 = 104. 例子2 /m /m / 11/ 1 / N N T W / 11/ / ( /) / NN Nm TmT m m WmW mm M/M/1 :到达速率和服务速率同时降低 m 倍 利用率保持不变 平稳分布不变，平均顾客数 目不变 低速系统的时延增加 m 倍 队列里面的平均顾客数目不变，但是第一个系 统里的顾客移动更快 教材例3.5 某校一部传真机为2万人服务。每个传真 需要的时间为负指数分布，平均传输时 间3分钟，并假定每个人传真的可能性相 同。如果希望平均排队的队长不大于5人， 试问平均每个人平均

12、间隔多少天才可以 发送一份传真？ 概率知识复习 R阶爱尔兰分布的概率密度 平均值 ，方差 ，方差系数 设x1,x2.,xr服从参数为 负指数分布，这些随 机变量的和服从r阶爱尔兰分布 方差系数小于1，当N趋向于无穷大，则接近定 长分布 0 )!1( )( )( 1 te r t tf t r r 2 r r 1 2 均值 方差 等待时间概率分布（一） 假定先到先服务 假定某个顾客在时刻 到达队列时发现系 统里有N个顾客，则该顾客需要等到这N 个顾客全部离开系统才能开始接受服务。 每个顾客的服务时间是一个负指数分布， 则N个顾客全部离开需要的时间是一个N 阶爱尔兰分布 x y k t t dye

13、 k y kNxWP 0 1 )!1( )( 0lim t 等待时间概率分布（二） 设W(x)为等待时间分布函数，则 根据PASTA定理，到达时刻看见的队列 长度等于任意时刻看见的队列长度 )0()(lim1 )0()0( )()( 1 kNxWPkNP xWPWP xWPxW tt k t 等待时间概率分布（三） 因此有 x x y x k y k y k x k k e e dye k y dye k y xW )1( 0 )1( 0 1 1 1 0 1 1 )1 (1 )!1( )( )1 (1 )!1( )( )1 (1)( 这是什么分布？ 几点说明 对于M/M/1排队系统,我们解出队

14、长分布为 求解过程中没有要求调度规则,该队长分布适用于 FIFO,LIFO 同样,平均滞留时间也与调度规则无关 但是,滞留时间、等待时间的分布与调度规则有 关 在M/M/1 FIFO排队系统里，队长分布只与利用 率有关，与服务时间无关 M/M/* 排队系统 Poisson到达过程 到达间隔: iid, exponential 服务时间: iid, exponential 服务时间和到达间隔:独立 N(t): t 时刻系统里顾客数目(状态) N(t): t 0是一个连续时间Markov过程 转移速率取决于系统特征 PASTA 定理成立 M/M/c/c Queue: c个服务器的损失系统 C个服务

15、器, 没有等待空间 新到的顾客发现所有服务器忙,则损失 平稳分布: 阻塞概率(PASTA): 只与/的比值有关，与、本身的值无关 结果对M/G/c/c queue 有效 01c2 2 c 1 0 ( /)( /) ,0,1,., ! nkc n k pnc nk 1 0 ( /)( /) ! ckc c k p ck 定义/=a M/M/c/c Queues (proof) 局部平衡方程式: 归一化: 1120 0 () (1)(1) ( /) ,0,1,. ! nnnnn n n npppppp nnnnn ppn n 1 0 0 ( /) , for M/M/c/c ! kc k p k

16、01c2 2 c M/M/c/c Queues Erlang-B公式的叠代 算法 0 1 ( )1 ( ) ( ) 1( ) s s s E a aE a Ea sE a 1 0 ( /)( /) ! ckc c k p ck 定义/=a M/M/c/c Queues M/M/c/c Queues M/M/c/c Queues M/M/1/K Queue 有限等待空间 系统最多有 K个顾客 一个顾客到达时，发现系统里已经有 K个顾客，则该顾客被丢弃 平稳分布 平稳条件: 总是稳定即使1 丢失概率 利用 PASTA 定理: 01KK-12 0 0 1 ,1,2,., 1 1 n n K ppnK

17、 p 1 (1) loss( ) 1 K K PP N tK M/M/1/K Queue (proof) 与 M/M/1 类似: 归一化: 01KK-12 1 00 01 0 1 1 111 1 1 1 KKK n n nn K ppp p 0, 1,2,., n n ppnK M/M/s Queue 到达过程为参数为 的Poisson过程 服务时间为参数为 的负指数分布 s个服务器 到达顾客发现系统里有n个顾客 n s:找一个空闲服务器开始接受服务 n s:如果所有服务器空闲，进入缓存等待 生灭过程 ,1 , n nns sns 01s+1s2 s 2 M/M/s Queue 01s+1s2

18、 s 2 s 详细的平衡方程 归一化 1000 000 1() 1:, (1)! 1 : ! n n nn n csn sn ssn nc s nsppppp nnnnns ss nsppppp ssssss 11 11 0 010 ()()()()1 11 !1 ksks ss k s n nkk sk ssss pp ksks M/M/s Queue 排队的概率 到达的顾客发现所有的服务器都 在工作 Erlang-C 公式:用于电话和电路交换 呼叫以速率到达; 呼叫持续时间是参数为 1/的负指数分布 s条中继线 如果呼叫发现所有 s 个电路都忙,则持续呼叫直到有一个空闲 链路 “在队列中等待” M/M/s/s Qu