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

1、introduction排队论与计算机系统/网络性能评价计算机系统计算机系统性性能评价主要目的n1选择n 在众多的系统中选择一个最需要的系统（计算机，网络，其他），或在众多的方案中选择一个较好的方案，即在一定的价格范围内选择性能最好的系统（或方案），达到较好的性能 / 价格比。n2改进n 对已有系统的性能缺陷进行改进，以便提高其运行效率。n3.设计n 对未来设计的系统进行性能预测，在性能成本方面实现最佳设计或配置。性能参数性能参数1 可靠性或可利用性系统能正常工作的时间，其指标可以是能够持续工作的时间长度，如平均无故障时间, 也可以是在一段时间内, 能正常工作的时间所占的百分比。 2 处理能力

2、或效率l吞吐率：系统在单位时间内能处理正常作业的个数。l响应的时间：系统得到输入到给出输出之间的时间。l利用率：在给定的时间区间中，各种部件(包括硬设备和软系统)被使用的时间与整个时间之比。l丢失率(或阻塞率)：信息传输(用户呼叫)丢失量与信息传输(用户呼叫)总量之比。性能评价方法性能评价方法(1)计算机和网络系统性能评价常用的有以下三种方法： 1 测量方法（测量方法（measurement）l测量：通过一定的测量设备或一定的测量程序直接从系统测得各项性能指标或与之密切相关的量；l运算：求出相应的性能指标。优缺点：l最直接、最基本的方法，其它方法也要依赖于测量的量l测量方案和测量手段是测量方法

3、的关键l比较费时间l适用于已经存在并运行的系统性能评价方法(2)2 仿真（仿真（simulation）/模拟模拟(emulation)方法方法用程序动态地模拟系统及其负载。l描述：模拟语言建立系统模型；l执行：事件或时间驱动系统模型；l统计分析：性能参数。 优缺点l详细地刻划系统l较精确的性能指标l费时、费用较高性能评价方法(3)3 分析方法分析方法(analysis)用数学模型工具的理论与方法描述性能与系统、负载之间的关系。l(stochastic process algebras)随机过程代数l(stochastic petri nets)随机petri网l(queueing theory

4、)排队论优缺点优缺点l模型进行简化和假设l刻划系统的详细程度较低l与实际性能指标有差距 l理论基础强、刻划各种因素之间的关系l省时、费用也较低本课程的主要内容：排队论及其模型本课程的主要内容：排队论及其模型重点讲述排队模型、排队网络模型及在计算机中的应用本课程的预修课程为：概率论和随机过程、计算机体系结构introduction随机过程&排队论初步内容提要n两个重要分布：指数分布、poisson分布n随机过程简介n排队论初步exponential distributionn a continuous r.v. x follows the exponential distribution

5、 with parameter , if its pdf is:n= probability distribution function:nusually used for modeling service timeexponential distribution (contd.)memoryless propertyn无后效性无后效性 不管多长时间不管多长时间( t)已经过去，逗留时间的概率分已经过去，逗留时间的概率分布与下一个事件的概率相同布与下一个事件的概率相同npast history has no influence on the futureproof: nexponential:

6、 the only continuous distribution with the memoryless property(exp(x+t)=exp(x)exp(t)nexample : problem 3.5|p xxt xtp xx(),|x txtp xxt xtp xxtp xxt xtp xtp xteep xxe指数分布例题-习题3.53.5 记性不好的教授在同一时间约了两个学生记性不好的教授在同一时间约了两个学生(应分别约见应分别约见). 第一个学生准时到达第一个学生准时到达, 第二个学第二个学生迟到生迟到5分钟分钟. 假定和每个学生谈话的时间为指假定和每个学生谈话的时间为指数

7、分布的随机时间数分布的随机时间, 均值为均值为30分钟分钟. 试计算整试计算整个谈话的平均个谈话的平均(expected)时间时间.习题3.5 （contd.）n解解: 如果和第一个学生的谈话在如果和第一个学生的谈话在5分钟内没分钟内没结束，剩余的谈话时间仍为均值结束，剩余的谈话时间仍为均值30分钟的分钟的指数分布时间指数分布时间.如果如果5分钟内谈完了则和他剩分钟内谈完了则和他剩余的谈话时间为余的谈话时间为0.所以和第一个学生剩余谈所以和第一个学生剩余谈话时间平均话时间平均为为:px530+px50=px530.所以和第一个学生谈话的平均时间为所以和第一个学生谈话的平均时间为:n 5+px5

8、30=30.38n 整个谈话的平均整个谈话的平均(expected)时间为时间为60.38习题3.6n假设某一银行有假设某一银行有4个服务窗口个服务窗口. 某人进到银行时某人进到银行时,看看到有到有4个客户在个客户在4个窗口接受服务个窗口接受服务,而且没有其它客而且没有其它客户等待户等待.假定每个客户的服务时间都是独立的相同假定每个客户的服务时间都是独立的相同的指数分布的指数分布(平均平均1分钟分钟, =1). (1)这个人最后离开银行的概率是多少这个人最后离开银行的概率是多少?(2)这个人平均在银行里停留多长时间这个人平均在银行里停留多长时间?习题3.6 （contd.）n(1)这个人最后离

9、开银行的概率是多少这个人最后离开银行的概率是多少?n 当这当这4个人中有一个人离开时该人接受服务个人中有一个人离开时该人接受服务,这时其它这时其它3人的人的剩余服务时间仍有相同的指数分布剩余服务时间仍有相同的指数分布.从对称性可知从对称性可知,这这4个人中个人中任何一个最后离开的概率都是任何一个最后离开的概率都是1/4.n(2)这个人平均在银行里停留多长时间这个人平均在银行里停留多长时间?n 这个人从进入银行到接受服务的时间等于这个人从进入银行到接受服务的时间等于min(x1,x2,x3,x4), x1,x2,x3,x4为正在接受服务的为正在接受服务的4个客个客户的剩余服务时间户的剩余服务时间

10、,都是指数分布的随机变量都是指数分布的随机变量. n 随机变量随机变量 min(x1,x2,x3,x4)有以下分布有以下分布:n pmin(x1,x2,x3,x4)x=exp(-4x), n 仍为指数分布仍为指数分布, 均值均值=1/(4)=0.25分钟分钟.n 所以这个人平均在银行停留的时间为所以这个人平均在银行停留的时间为1.25分钟分钟.n作业：习题作业：习题3.6（c）,3.8(a)(try to prove!)poisson distributionpoisson distribution (contd.)sum of poisson random variablessum of p

11、oisson random variables (cont.)sampling a poisson variablesampling a poisson variable (contd.)how come?poisson approximation to binomialsmall interval probabilities内容提要n两个重要分布：指数分布、poisson分布n随机过程简介n排队论初步随机过程n随机变量x，分布函数不变n如果随机变量的分布函数随时间变化，对时间集合t，得到一组随机变量，称之为随机过程随机过程n如果时间集合t离散，如t=0,1,2,，称为离散离散时间的随机过程时

12、间的随机过程，xn: ntn如果时间集合t连续，称为连续时间的随机过程连续时间的随机过程，x(t): ttn如果xn或者x(t)离散/连续，称这个随机过程离散随机过程离散/连续连续n例：n某路由器的ip包t时刻进入缓存等待转发，等待时间w(t): t0是一个连续时间的连续随机过程n从时间0到t到达路由器的ip包个数n(t): t0是一个连续时间的离散随机过程nxn表示一周7天中某一天某计算机启动的进程数，n1,2,3,4,5,6,7。xn是一个离散时间的离散随机过程。nxn表示一周7天中某一天某计算机的工作时间， n1,2,3,4,5,6,7。xn是一个离散时间的连续随机变量。计数过程n令n(

13、t)表示在时间段0, t)内的某种事件发生的次数。n(t)称为该事件的计数过程计数过程。计数过程是一种随机过程。n事件：数据包到达路由器；顾客到达商店n性质：1.n(0)=02.n(t)非负3.如果s0内事件发生的个数，则n证明：定义 ，取h0 代入初始条件 ，得到(),0,1,2,!kttp ykekk( )( )np tp n tn000()( ) ()( )0( )(1( )p thp t p n thn tp tho h0000()( )( )lim( )hp thp to hp thh 00( )( )dp tp tdt 0(0)1p0( )tp te参数为t的泊松分布000()(

14、)( )( )p thp to hp thh 对时间t+h时n个事件发生的情况pn(t+h)，三种情况1.时间t时已经发生了n个事件，2.时间t时发生了n-1个事件，t,t+h)这段时间发生了1个事件3.时间t 时发生了n-k个事件， t,t+h)这段时间发生了k个事件，k1取h0， 初始条件 ，迭代求解得到1()( )(1( )( )( )nnnp thp tto hhpto h10()( )( )lim( )( )nnnnhp thp to hp tpthh 1( )( )( )nnndp tp tptdt (0)0np()( )!tnnetp tnn定理： n(t)，t0是一个速率为的泊

15、松过程。令0t1t2t3s，n(tn-1+s)-n(tn-1)=0所以，pns=pn(tn-1+s)- n(tn-1)=0=pn(s)=0 =e-s1,0snpses 指数分布n定理： n(t)，t0是一个计数过程，事件发生间隔记为n。如果n为独立同分布的随机变量，且服从参数的指数分布，则n(t)是一个泊松过程。n证明：略merging & splitting poisson processesmodeling arrival statisticsnpoisson process widely used to model packet arrivals in numerous netw

16、orking problemsnjustification: provides a good model for aggregate traffic of a large number of “independent” usersn n traffic streams, with independent identically distributed (iid) interarrival times with pdf f(s) not necessarily exponentialn arrival rate of each stream /nnas n, combined stream ca

17、n be approximated by poisson under mild conditions on f(s) e.g., f(0)=0, f(0)0nmost important reason for poisson assumption: analytic tractability of queueing modelsn总结泊松过程n从时间0到时间t发生的事件个数是参数t的泊松分布n事件发生间隔n是指数分布泊松过程36n例:某商店，假设顾客按照以下比例单个或者成双到达，f(1)=p，f(2)=1-p。客户到达批次间隔服从以下分布证明时间0,t)内累计到达的客户数量服从分布n如果总共有

18、n个客户，假设其中发生k次成对到达，n-2k次单个到达，分别可以用速率为(1-p)和p的泊松过程表示。( )ta te/220(1) ()( )(2 )! !nnkkn ktnkpptp tenkknk次成对到达，nn-2k次单个到达，nk的取值范围从0到(1)(1)( )!kp tkptp tek22()( )(2 )!nkptnkp tptenk/ 2n/22(1)0/220(1)()( )!(2 )!(1) ()(2 )! !nknkp tptnknnkkn ktkptp tp teeknkpptenkkn例: 给定两个泊松过程，事件发生速率分别为1，2。从时间t=0开始，问首先观察到第

19、一个过程事件发生的概率。n假定过程1的第一个事件发生的时间是t1，过程2的第一个事件发生的时间是t2。t1和t2是参数为1和2 的指数分布n1 22 212220211212(1)1ttp tteedt 内容提要n两个重要分布：指数分布、poisson分布n随机过程简介n排队论初步排队问题n排队随处可见n顾客在超市收银柜台排队n飞机在机场排队等待起飞n进程在操作系统排队等待调度nn排队的原因：由于服务需求大于服务能力n规范用语n客户（customer），请求并接受服务者，例如顾客、飞机、进程、等等n服务器（server），提供服务的设施，例如收银员、机场跑道、cpu 、等等n(kleinroc

20、k) “we study the phenomena of standing, waiting, and serving, and we call this study queueing theory. any system in which arrivals place demands upon a finite capacity resource may be termed a queueing system.”nleonard. kleinrock is distinguished professor of computer science at ucla. known as a fat

21、her of the internet, he developed the mathematical theory of packet networks, the technology underpinning the internet, while a graduate student at mit. n他在其博士论文中最早用排 队论证明了分组交换网络的优越性(1961)。并在1969年12月，参与了美国四所大学使用接口消息处理器（imp) 建立起阿帕网(arpa net)。leonardkleinrock关于排队的定义nbook：queueing systems: computer app

22、lications by leonard kleinrock, published by john wiley &sons, 1975一般性定义n排队论是专门研究带有排队论是专门研究带有随机随机因素，产生拥因素，产生拥挤现象的优化理论。挤现象的优化理论。n排队系统也称为排队系统也称为随机随机服务服务系统系统nincomputerscience,queueingtheoryisthestudyofqueuesasatechniqueformanagingprocessesandobjectsinacomputer.naqueuecanbestudiedintermsof:nthesour

23、ceofeachqueueditem,nhowfrequentlyitemsarriveonthequeue,nhowlongtheycanorshouldwait,nwhethersomeitemsshouldjumpaheadinthequeue,nhowmultiplequeuesmightbeformedandmanaged,ntherulesbywhichitemsareenqueuedanddequeued.queueingtheoryforcomputersciencequeueingtheoryforstudyingnetworksnview network as collec

24、tions of queues nfifo data-structures nqueuing theory provides probabilistic analysis of these queuesnexamples: naverage length (buffer) naverage waiting timenprobability that queue is at a certain length nprobability that a packet will be lost sources of network delaynprocessing delaynassume proces

25、sing power is not a constraintnqueueing delayntime buffered waiting for transmissionntransmission delaynpropagation delayntime spend on the link transmission of electrical signalnindependent of traffic carried by the linkfocus: queueing & transmission delay排队系统六要素n一个排队系统包括六要素n客户到达过程n服务过程n服务器数量n系

26、统容量n顾客源数量n排队规则排队系统六要素n客户到达过程n耐心客户/非耐心客户：中途离开？n客户到达时间间隔可以看作一个随机变量n用一个随机过程描述客户到达模式n例如：可以用一个泊松过程表示客户到达，到达间隔服从指数分布n平稳/非平稳（stationary）到达模式n例如：突发大批到达客户n服务过程n状态无关/状态相关n服务时间可以看作一个随机变量n例如：可以用一个指数分布描述服务时间n平稳/非平稳（ stationary ）服务时间n例如：服务器可以学习，提高服务效率n服务器数量n单个/多个服务器n多服务器多队列，多服务器单队列多服务器多队列多服务器单队列n系统容量n客户不能立即获得服务时选

27、择等待/离开n有限/无限个等待位n系统的顾客源数量n有限n无限n排队规则nfcfs，lcfs，优先级n抢占优先（preemptive），非抢占优先（ nonpreemptive ）52排队系统命名法则(kendallnotation)n一个排队系统表示为a/b/c/x/y/zna：客户到达模式 nb：服务模式nc：服务器数量nx：排队系统的最大容量n当队列缓冲区容量无限时可省略ny：顾客源数量n当顾客源数量无限时可省略nz：排队规则n缺省值是fcfs53符号取值解释a、bm、d、ek，hk，g客户到达间隔/服务时间的概率分布，m表示指数分布（马尔可夫），g表示任意分布，d表示固定值c，x ，y

28、1,2,服务器/系统容量/顾客源数量zfcfs，lcfs，rss，pr，gd先到先服务，先到后服务，随机，优先级，任意n例：m/d/2/ / fcfs，客户到达符合泊松过程;固定服务时间;2个服务器；系统容量无限；first-come-first-serven通常假定系统容量无穷，顾客源数量无穷和fcfs，因此常用a/b/c描述一个排队系统n比如，m/m/1，m/m/c，m/m/m/m，m/g/1， */d/ ，等等distributionsnm: stands for markovian / poisson , implying exponential distribution for se

29、rvice times or inter-arrival times. nd: deterministic (e.g. fixed constant) nek: erlang with parameter knhk: hyperexponential with param. kng: general (anything) the pdf (x0) to different symbolsnm: nd:nek:nhk:ng: b(x) is arbitraryxexb)()1()(0 xxb)!1()()(1kexkkxbxkk)0, 1( ,)(11kiiikixiiiexb服务规则fcfs：

30、先来先服务；lcfs：后来先服务；rss：随机选择服务；pr：优先级服务gd：一般规约服务，即通用规约服务。ba：集体（批量）服务。57排队系统常见的性能指标n客户等待时间n客户在队列中等待的时间(wq)n客户在整个排队系统中消耗的时间(w)=队列等待时间+服务时间n客户在排队系统中的累积程度n等待队列中的客户数目(nq)n整个排队系统中的客户数目(n)=等待队列客户数目+正在接受服务的客户数目n空闲服务器n服务器空闲的时间比例n系统设计目标：提高服务器利用率，缩短客户等待时间等等，目标往往是相互矛盾的n排队论中的假设：排队论中的假设： 在排队分析中，最重要的一个假设是到达速率服从泊松分布，等

31、效的说法是到达间隔时间服从指数分布，这又等价于说到达是随机的并彼此独立。我们几乎一直要作这一假定。没有它，大部分的排队分析是不可能的。在这个假定的条件下，我们会发现仅仅知道到达速率和服务时间的均值和标准差就可以得到许多有用的结果。 基本排队关系：基本排队关系：little定理定理nlittle公式是排队论中的通用公式公式是排队论中的通用公式nlittles定理可以对排队系统进行确定性分析.n排队系统是随机过程,但它的一次实现(运行)是确定的过程.nergodicity:时间平均=随机平均.nlittles定理中时间平均换成处于稳态的随机过程的数学期望值仍成立.littles theoremn

32、: customer arrival raten n: average number of customers in systemn t: average delay per customer in systemnlittles theorem: system in steady-staten n = tthe long-term average number of customers in a stable system n, is equal to the long-term average arrival rate, , multiplied by the long-term avera

33、ge time a customer spends in the system, t.littles theorem (contd.)generality of littles theoremnlittles law is a pretty general resultnit does not depend on the arrival process distributionnit does not depend on the service process distribution nit does not depend on the number of servers and buffe

34、rs in the system.napplies to any system in equilibrium, as long as nothing in black box is creating or destroying taskscounting processes of a queuenn(t) : number of customers in system at time tn(t) : number of customer arrivals till time tnb(t) : number of customer departures till time tnti : time

35、 spent in system by the ith customer(t)n(t)tb(t)time averages ntime average over interval 0,tnsteady state time averagesnlittles theorem n=tnapplies to any queueing system provided that:limits t, , and d exist, and = d above assumptions : stable systemwe give a simple graphical proof under a set of

36、more restrictive assumptions0( )11( )lim( )lim1lim( )( )limttttttta ttittitttnn s dsnnta tttttta tttbdddproof of littles theorem for fcfsnassumption: n(t)=0, infinitely often. for any such tnif limits ntn, ttt, t exist, littles formula followsnwe will relax the last assumption (n(t)=0, infinitely of

37、ten).nfcfs system, n(0)=0(t) and b(t): staircase graphs n(t) = (t)-b(t)shaded area between graphs0( )( )ts tn s dst(t)t1n(t)t2tiib(t)( )1( )0011( )( )( )( )titttitttittn s dstn s dsnttttproof of littles theorem for fcfs (cont.)nin general even if the queue is not empty infinitely often:nresult follo

38、ws assuming the limits tt t, t, and dtd exist, and =d(t)t1n(t)t2tiib(t)( )( )11( )( )0011( )1( )( )( )( )( )ttiittttiiiittttttttttn s dstn s dsttttttntbbbbdproofoflittlestheoremwithoutfcfsidelayt1delaydelayt3delayt4delayt5(t)tt1t2t4assume d(t) is the set of customers who have departed the system by

39、time tassume is the set of customers who are still in the system at time tthe delay experienced up to time t by a customer still in the system at time t is t-tisothereforeproofoflittlestheoremwithoutfcfs(cont.)probabilistic form of littles theoremnhave considered a single sample function for a stoch

40、astic processnnow will focus on the probabilities of the various sample functions of a stochastic processnprobability of n customers in system at time tnexpected number of customers in system at t( )( )np tp n tn00( ). ( )( )nnne n tn p n tnnp tprobabilistic form of littles theorem (cont.)npn(t), en

41、(t) depend on t and initial distribution at t=0nwe will consider systems that converge to steady-statenthere exist pn independent of initial distributionnexpected number of customers in steady-state stochastic aver.nfor an ergodic process, the time average of a sample function is equal to the steady

42、-state expectation, with probability 1.lim( ),0,1,.nntp tpn0lim( )ntnennpe n tlimlim( )tttnne n tenprobabilistic form of littles theorem (cont.)nin principle, we can find the probability distribution of the delay ti for customer i, and from that the expected value eti, which converges to steady-stat

43、enfor an ergodic systemprobabilistic form of littles formula: arrival rate define aslim iiete t1limlim iiiitte teti.enet ( )limtetttime vs. stochastic averagesn“time averages = stochastic averages,” for all systems of interest in this course nit holds if a single sample function of the stochastic pr

44、ocess contains all possible realizations of the process at tncan be justified on the basis of general properties of markov chains结论：nlittles定理在任何调度规则下都成立littles 定理可用于系统的任一部分，只定理可用于系统的任一部分，只要该部分有客户到达和离开要该部分有客户到达和离开. nlittles 定理可用于系统的任一特定的客定理可用于系统的任一特定的客户类户类. little 定理应用举例1：little定理可用于排队系统的任何部分2 : 队列内

45、平均客户数和利用率队列内平均客户数和利用率(example 3.1) n设设是传输线内数据包的到达速率，是传输线内数据包的到达速率，设设nq为队列内为队列内等待传输的包数，等待传输的包数，w 是数据包在队列中的平均等待是数据包在队列中的平均等待时间（不包括传输时间），则按时间（不包括传输时间），则按littles 定理，有定理，有 nq=w n设设 正在传输线上传输的平均顾客数，正在传输线上传输的平均顾客数， 为包的平均为包的平均传输时间传输时间,则则 n在排队系统中在排队系统中 通常称为系统的利用率通常称为系统的利用率: 为为server忙的忙的 时间时间(比例比例),1- 为为server

46、闲的时间闲的时间(比例比例). xx3：网络平均延迟(example 3.2) 设1,.,n为网络的各个结点的packet到达率,n为网络内平均packet数,packet平均延迟设ni,ti为结点i的traffc在网络中的平均packet数和平均延迟,将littles定理用于节点i的traffic流有:niint1iiitn4：包到达和服务时间固定时的传输线性能（例题3.3）napacketarrivesatatransmissionlineeveryksecondswiththefirstpacketarrivingattime0.allpacketshaveequallengthandr

47、equireksecondsfortransmissionwhere1.theprocessingandpropagationdelayperpacketispsecondscalculate：ntheaveragetimetapacketspendsinthesystemntheaveragenumberninthesystem性能分析n传输时间小于到达间隔，系统无排队延迟。又因传播延迟p为常数,每个包经历确定的端-端延迟t :接收到的包间隔等于发送方发出的包间隔k(见图3.3)。n应用littles 定理得到链路上的平均分组数n: n假定kk+p2k,则系统中至多2个包.当n(t)=2时线

48、路上有在途中的packet，n(t)=1时仅有packet在传输。k1pktkptn注意：1：从图中可以看到系统中顾客数随时间不收敛2：使用little定理分析的结果是能得到随时间平均的顾客数 5：窗口流控系统（example 3.4 ）n网络使用窗口流控限制进入网络的流量以防止网络拥塞.假定每个session使用的窗口大小为w,则任何时刻网络中该session的packets不会多于w个。n设为每个session中packet的到达速率, t 为packet平均延迟. 根据littles定理，packet的平均延迟t满足w*t. n假定网络出现拥塞，每个会话在单位时间内只能传输个数据包，这时有w*t。n在拥塞情况下，增加窗口大小，仅可能导致包的平均延迟增加，不可能得到更大的吞吐率。tw6：有：有k个个server的排队系统的排队系统（example 3.4 ）n(1)consider a queueing system with k se