CS计算机代考程序代写 capacity planning COMP9334

程序代写 CS代考 / capacity planning

COMP9334
Capacity Planning for Computer Systems and Networks
Week 5B_1: Discrete event simulation (3). Comparing two systems.
COMP9334
1

Discrete event simulations so far
• You have learnt:
• Howtowritesimulationprogram
• Youknowyoucannotgetexactmeanresponsetimefrom simulation but you can get a confidence interval
• Youcanreducethewidthoftheconfidenceintervalby
• Simulate for longer
• Increase the number of independent replications
• Today, you will learn how you can compare two systems in a statistically sound way
• Before that, we show you that comparing systems can be tricky
T1, 2021 COMP9334 2

Problem: How do we compare 2 alternative choices?
• Week4B’sRevision Problem #2. The question asks you to simulate each of the following 2 queues 10 times:
• M/M/1 queue with l = 0.9 and μ=1
• M/M/2 queue with l = 0.9 and μ = 0.5
T1, 2021 COMP9334 3

Comparing two systems: motivation
• An application of simulation is to compare two systems
• For example, in Week 4B’s revision question, you used simulation to compare the mean response time of
• System1:M/M/1queuewithl=0.9andμ=1
• System2:M/M/2queuewithl=0.9andμ=0.5forbothserver
• If you use analytical method, you can find the steady state mean response time of both systems exactly and you compare two numbers
• If you use simulation, you get a confidence interval for each system instead. How do you compare them?
T1, 2021 COMP9334 4

Example: Comparing two systems
• Letusassumeourgoalistousesimulationtocompare:
• System1:M/M/1queuewithl=0.9andμ=1
• System 2: M/M/2 queue with l = 0.9 and μ = 0.5 for both server
• Foreachsystemwecarryout3independentreplications
• That is, we use 6 sets of independent random numbers together
• Afterremovingthetransient,theestimatedmeanresponsetimesare:
• System 1: 6.8769, 8.5769, 10.6340
• System 2: 8.8087, 7.4616, 9.1565
• Inordertocomparethem,letuspairuptheseresults
• 1st experiment for System 1 with 1st experiment for System 2
• 2nd experiment for System 1 with 2nd experiment for System 2 etc.
T1, 2021 COMP9334 5

A paired-t confidence interval • Letussummarisethedatainatable
• EMRT=estimatedmeanresponsetime
EMRT System 1 EMRT System 2 EMRT System 2 – EMRT System 1
Rep. 1
6.8769
8.8087
1.9318
Rep. 2
8.5769
7.4616
-1.1154
Rep. 3
10.6340 9.1565 -1.4775
• Wecomputethe100(1-a)%confidenceintervalofthedifferencebetween2 systems (= last column)
• Letusdenotethecomputedconfidenceintervalby[p,q]
• • •
Case 1: p,q > 0 ! System 1 is better than System 2 with probability (1-a)
Case 2: p,q < 0 ! System 2 is better than System 1 with probability (1-a) Case 3: q > 0 & p < 0 ! Systems 1 and 2 are not different with probability (1-a) T1, 2021 COMP9334 6 Example: Paired-t confidence interval • We compute the 95% confidence interval of the data showed in the last slide, the confidence interval is: • [-4.8721,4.4314] • Therefore, with 95% probability that the mean response times of the two systems are not different • Hmmm, we have a problem here, we know from queueing theory that System 1 has a better mean response time than System 2, but our simulation does not seem to be able to distinguish them. • What can we do? T1, 2021 COMP9334 7 Let us increase the number of replications • Since increasing the number of replications can reduce the width of the confidence interval, let us try that. • Let us try 5, 10, 20, 30 replications # independent replications 5 10 20 30 95% Confidence interval of EMRT System 2 - EMRT System 1 [-4.9540, 5.0242] [-1.5347, 2.8020] [-1.2724, 1.9870] [-0.6001, 1.8046] • Increasing the number of replications does reduce the width of the confidence interval • However, we still cannot conclude which system is better T1, 2021 COMP9334 8 Let us have a look at how we did our experiments ... • Wedidourexperimentwithindependentrandomnumbers Arrivals System 1 Job # 1 2 3 ... arrival time 0.6329 3.6392 4.3919 ... service time 0.3431 0.4319 0.1049 .... μ=1 Identical probability distribution but different numbers Different probability distribution and independently generated Arrivals System 2 Job # 1 2 3 ... arrival time 0.2548 4.1194 6.4435 ... service time 0.3228 0.3877 0.0728 .... T1, 2021 COMP9334 9 1 2 μ = 0.5 Common random numbers method • Analternativeistocomparetwosystemsundersimilarcondition System 1 Job # 1 2 3 ... arrival time 0.6329 3.6392 4.3919 ... service time 0.3432 0.4320 0.1050 .... μ=1 Arrivals = Multiply by 2 Arrivals System 2 Job # 1 2 3 ... arrival time 0.6329 3.6392 4.3919 ... service time 0.6864 0.8640 0.2100 .... T1, 2021 COMP9334 10 1 2 μ = 0.5 Common random numbers method • A method to reduce the variance when comparing two alternative systems is to subject them to similar experimental condition • In each replication, generate only one arrival time and one service time sequence • Applythistobothsystems • Note:Servicetimemayneedtobeadjustedaccordingtoservicerate • In next replication, generate a new arrival time and a new service time sequence • Applythistobothsystems • This method can reduce the variance if the behaviour of the two systems is positively correlated T1, 2021 COMP9334 11 Applying common random numbers to our problem (1) • Let us apply the common random numbers method to compare • System1:M/M/1queuewithl=0.9andμ=1 • System2:M/M/2queuewithl=0.9andμ=0.5forbothserver • Let us carry out 5 replications • In each replication, we generate one arrival time sequence and one service time sequence (adjusted by service rate) and apply to both systems T1, 2021 COMP9334 12 Applying common random numbers to our problem (2) • Letuscomparetheestimatedmeanresponsetime(EMRT)fromthe5 replications: EMRT System 1 EMRT System 2 EMRT System 2 - EMRT System 1 Rep. 1 8.3022 8.8087 0.5065 Rep. 2 6.8809 7.4616 0.5807 Rep. 3 8.5769 9.1565 0.5796 Rep. 4 10.6340 11.3409 0.7069 Rep. 5 16.2648 16.6485 0.3837 • Observation:TheEMRTofSystem2ishigherthanthatofSystem1inall 5 replications • Ifwecomputethe95%confidenceintervalofthelastcolumn,weget [0.4046,0.6983] • Thereisa95%probabilitythatSystem1isbetterthanSystem2 T1, 2021 COMP9334 13 Comparing two methods • Letuscompareusingcommonrandomnumber(CRN)methodornot # independent replications 5 10 20 30 95% Confidence interval of EMRT System 2 - EMRT System 1 Not using CRN [-4.9540, 5.0242] [-1.5347, 2.8020] [-1.2724, 1.9870] [-0.6001, 1.8046] Using CRN [0.4046, 0.6983] [0.4705, 0.6103] [0.5127, 0.5942] [0.5026, 0.5786] • Observations • ByusingCRN,all95%confidenceintervaldoesnotinclude0 • ThewidthoftheconfidenceintervalforCRNmethodisalotlower! T1, 2021 COMP9334 14 Approximate visual test • Letusassumethatyouknowthemeanresponsetimeanditsconfidence interval (CI) for 2 systems: System 1 and System 2 • Considerthefollowing3possibilities: Mean Mean Mean Sys 1 Sys 2 Sys 1 Sys 2 Sys 1 Sys 2 CIs overlap and mean of any one is not in the CI of the other: do t-test CIs do not overlap Mean of System 1 > Mean of Sys. 2
T1, 2021
COMP9334
15
CIs overlap and mean of a system is in the CI of the other: System are not different

Ex: Multicast protocol design for wireless mesh networks
• Comparing3 multicast protocols (WCMA, SPT and RCAM) for wireless mesh networks
• Thethinvertical line shows the confidence interval
• Whatconclusion can you draw?
• Source: Chou et al, “Maximizing Broadcast and Multicast Traffic Load through
Link-Rate Diversity in Wireless Mesh Networks”, you can download it from
my web site: http://www.cse.unsw.edu.au/~ctchou/ T1, 2021 COMP9334
16

Simulation tools and some applications (1)
• You do not always have to write your own simulation programs from scratch
• There are plenty of simulation tools available • ManywithGUI
• Simulation tools are used in a lot in computer networking research
• Protocol#1istheexistingprotocol,youhavedesignedProtocol #2. You want to see whether Protocol #2 is better or not.
• Youhavetwooptions(Option#1andOption#2)todesigna network. Which option is better?
T1, 2021 COMP9334 17

Simulation tools and some applications (2)
• Some examples of publicly available simulation tools • Generalpurpose:OMNet++
• http://www.omnetpp.org/
• Fornetworkingresearch:ns3
• http://www.isi.edu/nsnam/ns/ • Some commercial tools
• Fornetworkdesign:OPNET,Qualnet
• http://www.opnet.com/
• http://web.scalable-networks.com/content/qualnet
• Important note: These tools save you time in writing simulation program but don’t forget that you still need to analyse your simulation results using statistically sound methods!
T1, 2021 COMP9334 18

Summary
• Simulation is not just a computer programming exercise
• You need to make sure that your program is correct
• It is also important to analyse your results using statistically sound methods based on confidence interval
• Unfortunately, a lot of published research papers in computer networking did not do sound statistical analysis
• Optionalreading:Pawlikowskietal,“Oncredibilityofsimulation studies of telecommunication networks”, IEEE Communications Magazine, Pages 132-139, January 2002.
T1, 2021 COMP9334 19

References
• TheprimaryreferenceisLawandKelton,“SimulationModellingand Analysis”
• Comparing two alternatives, Section 10.1, 10.2 (10.2.1 only)
• Common random numbers, Section 11.2
• RajJain,“TheArtofComputerSystemsPerformanceAnalysis”has
materials on
• Comparing two alternatives, Sections 13.3, 13.4 (13.4.1 and 13.4.3 only)
• Notethatwehaveonlytouchedonthebasicofstatisticalanalysisof simulation data. The above two books (outside the specified sections) will provide you with more in depth discussion on the topic.
T1, 2021 COMP9334 20

Related Posts