信息网理论基础第三章 时延分析(二)

第三章网络时延分析赵永祥2005/3/17TheM/M/1Queue到达过程是参数为λ的Poisson过程服务时间独立同分布：参数为µ的负指数分布服务时间和到达时间间隔互相独立一个服务器无限等待空间N(t):t时刻系统内的顾客数目排队系统状态描述排队系统有三个变量：t时刻系统里的顾客数目N(t)，正在服务的顾客剩余服务时间，剩余到达时间由于负指数的无记忆性，剩余到达时间、剩余服务时间的分布与原来相同。系统的状态只由N(t)决定.系统未来的变化只与现在状态有关,与队长演变的历史无关.M/M型排队系统的队长具有Markov性.因此我们可以采用Markov随机过程的分析手段.分析步骤写转移概率画状态转移图求平稳概率M/M/1Queue:Discrete-TimeApproach考察离散时间点0,d,2d,…(d任意小)研究离散时间点过程Nk=N(dk)转移概率计算转移概率计算M/M/1Queue:Discrete-TimeApproach离散时间生灭过程d→0:Done!01n+1n2性能分析（一）平稳概率分布平均队长性能分析（二）平均滞留时间平均等待时间和平均等待顾客数目对长超过N的概率问题：如果是后到先服务，概率是什么？启发ρ=λ/μ:利用率服务器处于工作的状态概率ρ=1-p0:对任何M/G/1排队系统成立系统稳定的条件:ρ<1达到速率应该小于服务速率队长增加非线性例子1路由器A每秒平均发送8个分组到路由器B,分组间隔服从负指数分布,分组长度服从均值为400字节的负指数分布.路由器A,B之间的链路速率为64kbit每秒.问:路由器A的缓存里平均有多少分组等待发送?路由器A的缓存里分组数目>=10的概率?解::λ=8packets/s,µ=64kbit/s/(400×8bit/packet)=20packets/s),ρ=λ/µ=8/20=0.4E[N]=0.4/(1−0.4)=0.67.缓存里分组数目>=10的概率=0.410=10−4.例子2M/M/1:到达速率和服务速率同时降低m倍利用率保持不变⇒平稳分布不变，平均顾客数目不变低速系统的时延增加m倍队列里面的平均顾客数目不变，但是第一个系统里的顾客移动更快概率知识复习R阶爱尔兰分布的概率密度平均值，方差，方差系数设x1,x2…..,xr服从参数为负指数分布，这些随机变量的和服从r阶爱尔兰分布方差系数小于1，当N趋向于无穷大，则接近定长分布等待时间概率分布（一）假定先到先服务假定某个顾客在时刻到达队列时发现系统里有N个顾客，则该顾客需要等到这N个顾客全部离开系统才能开始接受服务。每个顾客的服务时间是一个负指数分布，则N个顾客全部离开需要的时间是一个N阶爱尔兰分布等待时间概率分布（二）设W(x)为等待时间分布函数，则根据PASTA定理，到达时刻看见的队列长度等于任意时刻看见的队列长度等待时间概率分布（三）因此有这是什么分布？几点说明对于M/M/1排队系统,我们解出队长分布为求解过程中没有要求调度规则,该队长分布适用于FIFO,LIFO同样,平均滞留时间也与调度规则无关但是,滞留时间、等待时间的分布与调度规则有关在M/M/1FIFO排队系统里，队长分布只与利用率有关，与服务时间无关M/M/*排队系统Poisson到达过程到达间隔:iid,exponential服务时间:iid,exponential服务时间和到达间隔:独立N(t):t时刻系统里顾客数目(状态){N(t):t≥0}是一个连续时间Markov过程转移速率取决于系统特征PASTA定理成立M/M/c/cQueue:c个服务器的损失系统C个服务器,没有等待空间新到的顾客发现所有服务器忙,则损失平稳分布:阻塞概率(PASTA):只与λ/μ的比值有关，与λ、μ本身的值无关结果对M/G/c/cqueue

有效01c2定义λ/μ=aM/M/c/cQueues(proof