ReviewM/M/1 QueueM/M/1 AnalysisExamplesOther MarkovianReview Examples M/M/mPoisson processes, Markov chains andM/M/1 queuesAdvanced Communication NetworksLecture 5Review Examples M/M/mM/M/1 AnalysisPoisson Arrivals, Exponential service times, 1 server (FIFO)Look at discrete times δWith high prob., only one arrival or departureDiscrete-time Markov chain0 1 2 3λδλδ λδµδµδµδ1−λδ1−λδ−µδ 1−λδ−µδ 1−λδ−µδReview Examples M/M/mAnalysis Contd..Steady state prob.s {pn}Balance equationspnµδ = pn−1λδ⇒pn=λµpn−1=λµnp0= ρnp0Xnpn= 1 ⇒ p0= 1 − ρpn= (1 − ρ)ρnStability of system: λ < µReview Examples M/M/mComputing system averagesComment: pn6= f(δ)As δ & 0 same answers for cont. time modelAverage number in systemN =∞Xn=0npn=∞Xn=0nρn(1 − ρ)=ρ1 − ρ=λµ − λAverage system delay: Little’s lawT =Nλ=1µ − λAs ρ → 1, N, T → ∞Review Examples M/M/m0 0.2 0.4 0.6 0.8 10102030405060708090100ρNSingle pole response - typical of queuing systemsOther system variablesW = T −1µ=ρµ−λNQ= λW =ρ21−ρReview Examples M/M/mCompare to D/D/1 queueone arrival every1λsec, 1 departure every1µsecNQρ=1D/D/1NQ= 0 ρ < 1.M/M/1: queue size, delay blows up for ρ near 1Intuition: Variability causes performance lossReview Examples M/M/mChanging transmission rateM/M/1 queue: Arrival rate and Service time is doubledWhat happens to delay? N?λ → 2λ, µ → 2µ ⇒ ρ stays sameN =ρ1 − ρ⇒ N stays sameT =1µ − λ=1µ1 − ρ⇒ T reduces by12Review Examples M/M/m1TnewToldReview Examples M/M/mExample 2λ µλλλµµµ/ M/ M/ M / M/ M/ MStatistical Multiplexing TDMM independent Poisson streams, rateλMTSM=1µ − λTTDM=mµ − λDelay reduced by factor of m ⇒ “Statistical Multiplexing gain”Cons: Difficult to isolate Bad flows ; Provide guaranteesReview Examples M/M/mDistribution of System VariablesWhat about distribution for N?For eg: VarianceVar(N) =∞Xn=0ρn(1 − ρ) · n2−ρ1 − ρ2=ρ(1 − ρ)2Likewise, Distn. for T in Prob. 3.1 (M/M/1 queues)Review Examples M/M/mPASTA propertyInterested in state of system just before packet arrivesEg: to calculate Blocking probabilitySteady-state prob. arriving packet sees in the systemlimt→∞Pr(N(t) = n| arrival @t+) ?Is’nt this same as pn?Not necessaryEg: D/D/1 system, λ < µAbove prob. is zero, but no steady-state existsReview Examples M/M/mPASTA property Contd..For Poisson traffic,The two quantities are equal ⇒ “PASTA”Proofan= P{N(t) = n| arrival @t+}= P{N(t) = n| A(t, t + δ)}=P(N(t)=n,A(t,t+δ))P(A(t,t+δ))=P(A(t, t + δ)| N(t) = n) P (N(t) = n)P(A(t, t + δ))But A(t, t + δ) ind. of N(t) = n ⇒ an(t) = P(N(t) = n)Holds for broad class of queuing systems w/ Poisson arrivals, indservice distribution (Memoryless property)Review Examples M/M/mM/M/1 - Last slideWhat is the prob arriving customer finds system empty?p0= 1 − ρReview Examples M/M/mOther Markovian systems: M/M/m0 1 2λδλδ λδ2µδ3µδµδ3 m+1mλδµδmm servers in systemGiven 2 packets in service,Prob of departure = Prob(1st packet departs) + Prob(2nd packetdeparts)= µδ + µδService time of state n = mµ n > mEx: Circuit switched networks, blocked calls waitReview Examples M/M/mM/M/m analysisBalance equationspn−1(λδ) = pn(nµδ) n = 1, 2, · · · , mpn−1(λδ) = pn(mµδ) n > m⇒ pn=λnµλ(n − 1)µ· · ·λµp0n ≤ mpn=λmµn−m1m!λµmp0n > mReview Examples M/M/mM/M/m analysis Contd..pn=1n!(mρ)np0n ≤ mmmρnm!n > m,If stable:P∞n=0pn= 1Stability condition: ρ =λmµ< 1p0= m−1Xn=0(mρ)nn!+(mρ)mm!(1 − ρ)!−1Review Examples M/M/mErlang C formulaWhat is the prob arriving packet has to wait for service?Same as prob that servers are busy (Follows from PASTA property)PQ= Pr(Queuing) = Pr(N ≥ m)=∞Xn=mpn= p0(mρ)mm!(1 − ρ)Widely used in telephonyModel for Blocked delay callsFormula also hold for M/G/1 systems (Invariance