排隊(duì)論與計(jì)算機(jī)系統(tǒng)網(wǎng)絡(luò)性能評(píng)價(jià)

1、introduction 排隊(duì)論與計(jì)算機(jī)系統(tǒng)/網(wǎng)絡(luò)性能評(píng)價(jià) 計(jì)算機(jī)系統(tǒng)計(jì)算機(jī)系統(tǒng)性性能評(píng)價(jià)主要目的 n1選擇 n 在眾多的系統(tǒng)中選擇一個(gè)最需要的系統(tǒng)（計(jì)算機(jī)， 網(wǎng)絡(luò)，其他），或在眾多的方案中選擇一個(gè)較好的方 案，即在一定的價(jià)格范圍內(nèi)選擇性能最好的系統(tǒng) （或方案），達(dá)到較好的性能 / 價(jià)格比。 n2改進(jìn) n 對(duì)已有系統(tǒng)的性能缺陷進(jìn)行改進(jìn)，以便提高其運(yùn) 行效率。 n3.設(shè)計(jì) n 對(duì)未來設(shè)計(jì)的系統(tǒng)進(jìn)行性能預(yù)測(cè)，在性能成本方 面實(shí)現(xiàn)最佳設(shè)計(jì)或配置。 性能參數(shù)性能參數(shù) 1 可靠性或可利用性 系統(tǒng)能正常工作的時(shí)間，其指標(biāo)可以是能夠持續(xù)工作的時(shí)間長 度，如平均無故障時(shí)間, 也可以是在一段時(shí)間內(nèi), 能正常工作

2、 的時(shí)間所占的百分比。 2 處理能力或效率 l吞吐率：系統(tǒng)在單位時(shí)間內(nèi)能處理正常作業(yè)的個(gè)數(shù)。 l響應(yīng)的時(shí)間：系統(tǒng)得到輸入到給出輸出之間的時(shí)間。 l利用率：在給定的時(shí)間區(qū)間中，各種部件(包括硬設(shè)備和軟系 統(tǒng))被使用的時(shí)間與整個(gè)時(shí)間之比。 l丟失率(或阻塞率)：信息傳輸(用戶呼叫)丟失量與信息傳輸(用 戶呼叫)總量之比。 性能評(píng)價(jià)方法性能評(píng)價(jià)方法(1) 計(jì)算機(jī)和網(wǎng)絡(luò)系統(tǒng)性能評(píng)價(jià)常用的有以下三種方法： 1 測(cè)量方法（測(cè)量方法（measurement） l測(cè)量：通過一定的測(cè)量設(shè)備或一定的測(cè)量程序直接 從系統(tǒng)測(cè)得各項(xiàng)性能指標(biāo)或與之密切相關(guān)的量； l運(yùn)算：求出相應(yīng)的性能指標(biāo)。 優(yōu)缺點(diǎn)： l最直接、最基本的

3、方法，其它方法也要依賴于測(cè)量 的量 l測(cè)量方案和測(cè)量手段是測(cè)量方法的關(guān)鍵 l比較費(fèi)時(shí)間 l適用于已經(jīng)存在并運(yùn)行的系統(tǒng) 性能評(píng)價(jià)方法(2) 2 仿真（仿真（simulation）/模擬模擬(emulation)方法方法 用程序動(dòng)態(tài)地模擬系統(tǒng)及其負(fù)載。 l描述：模擬語言建立系統(tǒng)模型； l執(zhí)行：事件或時(shí)間驅(qū)動(dòng)系統(tǒng)模型； l統(tǒng)計(jì)分析：性能參數(shù)。 優(yōu)缺點(diǎn) l詳細(xì)地刻劃系統(tǒng) l較精確的性能指標(biāo) l費(fèi)時(shí)、費(fèi)用較高 性能評(píng)價(jià)方法(3) 3 分析方法分析方法(analysis) 用數(shù)學(xué)模型工具的理論與方法描述性能與系統(tǒng)、負(fù)載之間的關(guān)系。 l(stochastic process algebras)隨機(jī)過程代數(shù)

4、l(stochastic petri nets)隨機(jī)petri網(wǎng) l(queueing theory)排隊(duì)論 優(yōu)缺點(diǎn)優(yōu)缺點(diǎn) l模型進(jìn)行簡(jiǎn)化和假設(shè) l刻劃系統(tǒng)的詳細(xì)程度較低 l與實(shí)際性能指標(biāo)有差距 l理論基礎(chǔ)強(qiáng)、刻劃各種因素之間的關(guān)系 l省時(shí)、費(fèi)用也較低 本課程的主要內(nèi)容：排隊(duì)論及其模型本課程的主要內(nèi)容：排隊(duì)論及其模型 重點(diǎn)講述排隊(duì)模型、排隊(duì)網(wǎng)絡(luò)模型及在計(jì)算機(jī)中的應(yīng)用 本課程的預(yù)修課程為：概率論和隨機(jī)過程、計(jì)算機(jī)體系結(jié)構(gòu) introduction 隨機(jī)過程固定服務(wù)時(shí)間;2個(gè)服務(wù)器；系統(tǒng)容量無限； first-come-first-serve n通常假定系統(tǒng)容量無窮，顧客源數(shù)量無窮和fcfs， 因

5、此常用a/b/c描述一個(gè)排隊(duì)系統(tǒng) n比如，m/m/1，m/m/c，m/m/m/m，m/g/1， */d/ ，等等 distributions nm: stands for markovian / poisson , implying exponential distribution for service times or inter-arrival times. nd: deterministic (e.g. fixed constant) nek: erlang with parameter k nhk: hyperexponential with param. k ng: general

6、 (anything) the pdf (x0) to different symbols nm: nd: nek: nhk: ng: b(x) is arbitrary x exb )( ) 1 ()( 0 xxb )!1( )( )( 1 k exkk xb xkk )0, 1( ,)( 11 k i ii k i x ii i exb 服務(wù)規(guī)則 fcfs：先來先服務(wù)； lcfs：后來先服務(wù)； rss：隨機(jī)選擇服務(wù)； pr：優(yōu)先級(jí)服務(wù) gd：一般規(guī)約服務(wù)，即通用規(guī)約服務(wù)。 ba：集體（批量）服務(wù)。 57 排隊(duì)系統(tǒng)常見的性能指標(biāo) n客戶等待時(shí)間 n客戶在隊(duì)列中等待的時(shí)間(wq) n客戶在整個(gè)

7、排隊(duì)系統(tǒng)中消耗的時(shí)間(w)=隊(duì)列等待 時(shí)間+服務(wù)時(shí)間 n客戶在排隊(duì)系統(tǒng)中的累積程度 n等待隊(duì)列中的客戶數(shù)目(nq) n整個(gè)排隊(duì)系統(tǒng)中的客戶數(shù)目(n)=等待隊(duì)列客戶數(shù) 目+正在接受服務(wù)的客戶數(shù)目 n空閑服務(wù)器 n服務(wù)器空閑的時(shí)間比例 n系統(tǒng)設(shè)計(jì)目標(biāo)：提高服務(wù)器利用率，縮短客戶 等待時(shí)間等等，目標(biāo)往往是相互矛盾的 n排隊(duì)論中的假設(shè)：排隊(duì)論中的假設(shè)： 在排隊(duì)分析中，最重要的一個(gè)假設(shè)是到達(dá)速率服從泊松分布， 等效的說法是到達(dá)間隔時(shí)間服從指數(shù)分布，這又等價(jià)于說到 達(dá)是隨機(jī)的并彼此獨(dú)立。我們幾乎一直要作這一假定。沒有 它，大部分的排隊(duì)分析是不可能的。在這個(gè)假定的條件下， 我們會(huì)發(fā)現(xiàn)僅僅知道到達(dá)速率和服務(wù)時(shí)

8、間的均值和標(biāo)準(zhǔn)差就 可以得到許多有用的結(jié)果。 基本排隊(duì)關(guān)系：基本排隊(duì)關(guān)系：little定理定理 nlittle公式是排隊(duì)論中的通用公式公式是排隊(duì)論中的通用公式 nlittles定理可以對(duì)排隊(duì)系統(tǒng)進(jìn)行確定性分析. n排隊(duì)系統(tǒng)是隨機(jī)過程,但它的一次實(shí)現(xiàn)(運(yùn)行) 是確定的過程. nergodicity:時(shí)間平均=隨機(jī)平均. nlittles定理中時(shí)間平均換成處于穩(wěn)態(tài)的隨機(jī) 過程的數(shù)學(xué)期望值仍成立. littles theorem n : customer arrival rate n n: average number of customers in system n t: average dela

9、y per customer in system nlittles theorem: system in steady-state n n = t the 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 average time a customer spends in the system, t. littles theorem (contd.) generality

10、 of littles theorem nlittles law is a pretty general result nit does not depend on the arrival process distribution nit does not depend on the service process distribution nit does not depend on the number of servers and buffers in the system. napplies to any system in equilibrium, as long as nothin

11、g in black box is creating or destroying tasks counting processes of a queue nn(t) : number of customers in system at time t n(t) : number of customer arrivals till time t nb(t) : number of customer departures till time t nti : time spent in system by the ith customer (t) n(t) t b(t) time averages n

12、time average over interval 0,t nsteady state time averages nlittles theorem n=t napplies to any queueing system provided that: limits t, , and d exist, and = d above assumptions : stable system we give a simple graphical proof under a set of more restrictive assumptions 0 ( ) 1 1 ( )lim ( ) lim 1 li

13、m ( ) ( ) lim t tt t tt t a t tit t i tt t nn s dsnn t a t t tttt a t t t b ddd proof of littles theorem for fcfs nassumption: n(t)=0, infinitely often. for any such t nif limits ntn, ttt, t exist, littles formula follows nwe will relax the last assumption (n(t)=0, infinitely often). nfcfs system, n

14、(0)=0 (t) and b(t): staircase graphs n(t) = (t)-b(t) shaded area between graphs 0 ( )( ) t s tn s ds t (t) t1 n(t) t2 ti i b(t) ( ) 1 ( ) 00 1 1( ) ( )( ) ( ) t i t tt ittt i tt n s dstn s dsnt ttt proof of littles theorem for fcfs (cont.) nin general even if the queue is not empty infinitely often:

15、 nresult follows assuming the limits tt t, t, and dtd exist, and =d (t) t1 n(t) t2 ti i b(t) ( )( ) 11 ( )( ) 00 11 ( )1( ) ( )( ) ( )( ) tt ii tt tt ii ii ttttt tttt tn s dstn s ds ttttt tnt b b b b d proofoflittlestheoremwithoutfcfs i delayt1 delay delayt3 delayt4 delayt5 (t) t t1t2 t4 assume d(t)

16、 is the set of customers who have departed the system by time t assume is the set of customers who are still in the system at time t the delay experienced up to time t by a customer still in the system at time t is t-ti so therefore proofoflittlestheoremwithoutfcfs(cont.) probabilistic form of littl

17、es theorem nhave considered a single sample function for a stochastic process nnow will focus on the probabilities of the various sample functions of a stochastic process nprobability of n customers in system at time t nexpected number of customers in system at t ( )( ) n p tp n tn 00 ( ). ( )( ) n

18、nn e n tn p n tnnp t probabilistic form of littles theorem (cont.) npn(t), en(t) depend on t and initial distribution at t=0 nwe will consider systems that converge to steady-state nthere exist pn independent of initial distribution nexpected number of customers in steady-state stochastic aver. nfor

19、 an ergodic process, the time average of a sample function is equal to the steady-state expectation, with probability 1. lim( ),0,1,. nn t p tpn 0 lim( ) n t n ennpe n t limlim( ) t tt nne n ten probabilistic form of littles theorem (cont.) nin principle, we can find the probability distribution of

20、the delay ti for customer i, and from that the expected value eti, which converges to steady-state nfor an ergodic system probabilistic form of littles formula: arrival rate define as lim i i ete t 1 limlim i i ii t te tet i .enet ( ) lim t et t time vs. stochastic averages n“time averages = stochas

21、tic averages,” for all systems of interest in this course nit holds if a single sample function of the stochastic process contains all possible realizations of the process at t ncan be justified on the basis of general properties of markov chains 結(jié)論： nlittles定理在任何調(diào)度規(guī)則下都成立 littles 定理可用于系統(tǒng)的任一部分，只定理可用于

22、系統(tǒng)的任一部分，只 要該部分有客戶到達(dá)和離開要該部分有客戶到達(dá)和離開. nlittles 定理可用于系統(tǒng)的任一特定的客定理可用于系統(tǒng)的任一特定的客 戶類戶類. little 定理應(yīng)用舉例 1：little定理可用于排隊(duì)系統(tǒng)的任何部分 2 : 隊(duì)列內(nèi)平均客戶數(shù)和利用率隊(duì)列內(nèi)平均客戶數(shù)和利用率(example 3.1) n設(shè)設(shè)是傳輸線內(nèi)數(shù)據(jù)包的到達(dá)速率，是傳輸線內(nèi)數(shù)據(jù)包的到達(dá)速率，設(shè)設(shè)nq為隊(duì)列內(nèi)為隊(duì)列內(nèi) 等待傳輸?shù)陌鼣?shù)，等待傳輸?shù)陌鼣?shù)，w 是數(shù)據(jù)包在隊(duì)列中的平均等待是數(shù)據(jù)包在隊(duì)列中的平均等待 時(shí)間（不包括傳輸時(shí)間），則按時(shí)間（不包括傳輸時(shí)間），則按littles 定理，有定理，有 nq=w n設(shè)

23、設(shè) 正在傳輸線上傳輸?shù)钠骄櫩蛿?shù)，正在傳輸線上傳輸?shù)钠骄櫩蛿?shù)， 為包的平均為包的平均 傳輸時(shí)間傳輸時(shí)間,則則 n在排隊(duì)系統(tǒng)中在排隊(duì)系統(tǒng)中 通常稱為系統(tǒng)的利用率通常稱為系統(tǒng)的利用率: 為為server 忙的忙的 時(shí)間時(shí)間(比例比例),1- 為為server閑的時(shí)間閑的時(shí)間(比例比例). x x 3：網(wǎng)絡(luò)平均延遲(example 3.2) 設(shè)1,.,n為網(wǎng)絡(luò)的各個(gè)結(jié)點(diǎn)的packet到達(dá)率, n為網(wǎng)絡(luò)內(nèi)平均packet數(shù),packet平均延遲 設(shè)ni,ti為結(jié)點(diǎn)i的traffc在網(wǎng)絡(luò)中的平均packet數(shù) 和平均延遲,將littles定理用于節(jié)點(diǎn)i的traffic流 有: n i i n t 1

24、iii tn 4：包到達(dá)和服務(wù)時(shí)間固定時(shí)的傳輸線性能（例題3.3） napacketarrivesatatransmissionlineeveryk secondswiththefirstpacketarrivingattime0.all packetshaveequallengthandrequirekseconds fortransmissionwhere1.theprocessingand propagationdelayperpacketispseconds calculate： ntheaveragetimetapacketspendsinthesystem ntheaveragen

25、umberninthesystem 性能分析 n傳輸時(shí)間小于到達(dá)間隔，系統(tǒng)無排隊(duì)延遲。又因傳播 延遲p為常數(shù),每個(gè)包經(jīng)歷確定的端-端延遲t :接收到 的包間隔等于發(fā)送方發(fā)出的包間隔k(見圖3.3)。 n應(yīng)用littles 定理得到鏈路上的平均分組數(shù)n: n假定kk+p2k,則系統(tǒng)中至多2個(gè)包.當(dāng)n(t)=2時(shí) 線路上有在途中的packet，n(t)=1時(shí)僅有packet在傳 輸。 k1pkt k p tn 注意： 1：從圖中可以看到系統(tǒng)中顧客數(shù)隨時(shí)間不收斂 2：使用little定理分析的結(jié)果是能得到隨時(shí)間平均的顧客數(shù) 5：窗口流控系統(tǒng)（example 3.4 ） n網(wǎng)絡(luò)使用窗口流控限制進(jìn)入網(wǎng)絡(luò)

26、的流量以防止網(wǎng)絡(luò) 擁塞.假定每個(gè)session使用的窗口大小為w,則任何 時(shí)刻網(wǎng)絡(luò)中該session的packets不會(huì)多于w個(gè)。 n設(shè)為每個(gè)session中packet的到達(dá)速率, t 為packet 平均延遲. 根據(jù)littles定理，packet的平均延遲t滿 足w*t. n假定網(wǎng)絡(luò)出現(xiàn)擁塞，每個(gè)會(huì)話在單位時(shí)間內(nèi)只能傳 輸個(gè)數(shù)據(jù)包，這時(shí)有w*t。 n在擁塞情況下，增加窗口大小，僅可能導(dǎo)致包的平 均延遲增加，不可能得到更大的吞吐率。 tw 6：有：有k個(gè)個(gè)server的排隊(duì)系統(tǒng)的排隊(duì)系統(tǒng)（example 3.4 ） n(1)consider a queueing system with k

27、 servers, and with room for at most nk customers (either in queue or in service). nthe system is always full: we assume that it starts with n customers and that a departing customer is immediately replaced by a new customer( closed queueing systems). suppose the average customer service time is , we

28、 want to find the average customer time in the system t. n(2) assume that customers arrive at but are blocked (and lost ) from the system if they find the system full (open queueing system). then the number of servers that are busy may be less than k. let n be the average number of busy servers and let be the proportion of customers that are blocked from entering the system. we want to find the lower bound on the blocking proba