排队论与计算机系统-网络性能评价.ppt

Introduction 排队论与计算机系统/网络性能评价;计算机系统性能评价主要目的;性能参数;性能评价方法(1);性能评价方法(2);性能评价方法(3);Introduction 随机过程排队论初步;内容提要;Exponential Distribution;Exponential Distribution (contd.);Memoryless Property;指数分布例题-习题3.5;习题3.5 （Contd.）;习题3.6;习题3.6 （Contd.）;Poisson Distribution;Poisson Distribution (contd.);Sum of Poisson Random Variables;Sum of Poisson Random Variables (cont.);Sampling a Poisson Variable;Sampling a Poisson Variable (contd.);Poisson Approximation to Binomial;Small Interval Probabilities;内容提要;随机过程;例： 某路由器的IP包t时刻进入缓存等待转发，等待时间{W(t): t0}是一个连续时间的连续随机过程 从时间0到t到达路由器的IP包个数{N(t): t0}是一个连续时间的离散随机过程 Xn表示一周7天中某一天某计算机启动的进程数，n∈{1,2,3,4,5,6,7}。{Xn}是一个离散时间的离散随机过程。 Xn表示一周7天中某一天某计算机的工作时间， n∈{1,2,3,4,5,6,7}。{Xn}是一个离散时间的连续随机变量。;计数过程;例，Bernoulli过程 X1，X2，…是独立同分布的Bernoulli变量，成功的概率为p。令Sn=X1+X2+…+Xn，即前n次伯努力实验的成功次数，{Sn}是一个计数过程，被称为伯努力过程。Sn的分布是二项分布。;Poisson过程;定理：{N(t)，t≥0}是一个速率为λ的泊松过程。Y表示一段时间t0内事件发生的个数，则 证明：定义 ，取h→0 代入初始条件 ，得到;对时间t+h时n个事件发生的情况Pn(t+h)，三种情况 时间t时已经发生了n个事件， 时间t时发生了n-1个事件，[t,t+h)这段时间发生了1个事件 时间t 时发生了n-k个事件， [t,t+h)这段时间发生了k个事件，k1 取h→0， 初始条件 ，迭代求解得到;定理： {N(t)，t≥0}是一个速率为λ的泊松过程。令0t1t2t3…为事件发生的一系列时间。定义事件发生的间隔τ0=t1-0， τ1=t2-t1，τ2=t3-t2，…， τk=tk+1-tk，…。时间间隔{τi}是独立同分布的，服从参数为λ的指数分布。 证明：对任意n和τ，下面两个事件等价{τns}，{N(tn-1+s)-N(tn-1)=0}所以，P[τns]=P[N(tn-1+s)- N(tn-1)=0]=P[N(s)=0] =e-λs;定理： {N(t)，t≥0}是一个计数过程，事件发生间隔记为{τn}。如果{τn}为独立同分布的随机变量，且服从参数λ的指数分布，则N(t)是一个泊松过程。 证明：略 ;Merging Splitting Poisson Processes;Modeling Arrival Statistics;总结泊松过程 从时间0到时间t发生的事件个数是参数λt的泊松分布 事件发生间隔{τn}是指数分布??泊松过程 ;例:某商店，假设顾客按照以下比例单个或者成双到达，f(1)=p，f(2)=1-p。客户到达批次间隔服从以下分布证明时间[0,t)内累计到达的客户数量服从分布 如果总共有n个客户，假设其中发生k次成对到达，n-2k次单个到达，分别可以用速率为(1-p)λ和pλ的泊松过程表示。;k次成对到达， n-2k次单个到达， k的取值范围从0到 ;例: 给定两个泊松过程，事件发生速率分别为λ1，λ2。从时间t=0开始，问首先观察到第一个过程事件发生的概率。 假定过程1的第一个事件发生的时间是t1，过程2的第一个事件发生的时间是t2。t1和t2是参数为λ1和λ2 的指数分布  ;内容提要;排队问题;(Kleinrock) “We study the phenomena of standing, waiting, and serving, and we call this study Queueing Theory. Any system in which arrivals place demands