Network Design Performance Evaluation and Simulation 6 Section 4 7 Section 5 7 Appendix A Network Performance 1 Network Design Problem Goal Given QoS metric e g Average delay Loss probability Characterization of the traffic e g Average interarrival time arrival rate Average holding time message length Design the system Three systems will be studied Circuit switch Determine the lines System 1 M M S S M M S S Ideal router output port Determine link capacity System 2 M M 1 M M 1 Real router output port Determine link capacity and buffer size System 3 M M 1 N M M 1 N Network Performance 2 Network Performance Evaluation Solution methodologies Mathematical analysis Model this type of process as a Queueing System good for initial design Simulation techniques good for more detailed analysis Network Performance 3 Network Performance Evaluation Elements of a Queueing System System Server Server Queue Departing customers Server Blocked customers Network Performance 4 Network Performance Evaluation Elements of a Queueing System Number in Servers Number in Queue Servers Delay Number in system Network Performance 5 Network Performance Evaluation Specific cases for theoretical analysis Assumptions Interarrival times are exponentially distributed Service times are exponentially distributed Holding time Packet length Types of systems One server Stat Mux Infinite memory Finite memory S servers and a system size of S Circuit Switch Network Performance 6 Network Performance Evaluation Approach Analysis of a pure birth process to characterize arrival processes Extension to general birth death processes to model arrivals and departures Specialization to the specific cases to find Probability of system occupancy Average buffer size Delay Blocking probability Goal Design and analyze statistical multiplexers and circuit switching systems Network Performance 7 Network Performance Evaluation Analysis of a Pure Birth Process Arrivals and no departures 0 1 Arrival rate 2 K Only Births Arrivals Allowed K System State number in system number of arrivals for 0 to t sec number in system at time t Goal Find Prob k arrivals in a t sec interval Network Performance 8 Network Performance Evaluation Analysis of a Pure Birth Process Arrivals Interarrival Time Network Performance 9 Network Performance Evaluation Analysis of a Pure Birth Process The number represents the State of the system In networks this is usually the number in the buffer plus the number in service The system includes the server The time to clock the message bits onto the transmission facility is the service time The server is the model for the transmission facility Goal Find Prob k arrivals in a t sec interval Network Performance 10 Network Performance Evaluation Analysis of a Pure Birth Process Assumptions Prob 1 arrivals in t sec t Prob 0 arrivals in t sec 1 t Number of arrivals in non overlapping intervals of times are statistically independent random variables i e Prob N arrivals in t t T AND M arrivals in t T t T Prob N arrivals in t t T M arrivals in t T t T Network Performance 11 Network Performance Evaluation State How to get to state k at t t k k 1 t t t time Network Performance 12 Network Performance Evaluation Analysis Define probability of k in the system at time t Prob k t Probability of k in the system at time t t Prob k t t Prob k in the system at time t and 0 arrivals in t or k 1 in the system at time t and 1 arrival in t 1 t Prob k t t Prob k 1 t Network Performance 13 Network Performance Evaluation Analysis Rearranging terms Prob k t t Prob k t t Prob k t Prob k 1 t Letting t 0 results in the following differential equation Network Performance 14 Network Performance Evaluation Analysis For k 0 the solution is Prob 0 t For k 1 the solution is Prob 1 t For k 2 the solution is Prob 2 t Network Performance 15 Network Performance Evaluation Analysis In general the solution is a Poisson probability mass function of the form Network Performance 16 Network Performance Evaluation Analysis A Possion pmf of this from has the following moments Poisson Arrival Process The number of arrivals in any T second interval follows a Poisson probability mass function Network Performance 17 Network Performance Evaluation Interarrival Time Analysis Arrival Ta Arrival Ta interarrival time t Prob t Ta t t Prob 0 arrivals in t sec and 1 arrival in t Prob t Ta t t Prob k 0 t Prob k 1 t t Prob t Ta t t Network Performance 18 Network Performance Evaluation Interarrival Time Analysis Let t 0 results in the following Network Performance 19 Network Performance Evaluation Interarrival Time Analysis MAIN RESULT The interarrival time for a Poisson arrival process follows an exponential probability density function Network Performance 20 Network Performance Evaluation Birth Death Process Analysis Now allow arrivals and departures The Model for the Birth Death Process Network Performance 21 Network Performance Evaluation Birth Death Process Analysis Arrivals Departures Network Performance 22 Network Performance Evaluation Birth Death Process Analysis The departure process is Poisson Prob 1 departure in t sec when the system is in state k k t Prob 0 departure in t sec when the system is in state k 1 k t Number of departures in non overlapping intervals of times are statistically independent random variables Probability arrival AND departure in t 0 Network Performance 23 Network Performance Evaluation Birth Death Process Analysis Poisson service process implies an exponential probability density function for the message length Network Performance 24 Network Performance Evaluation Birth Death Process Analysis To solve for the state probabilities Follow the procedure used for the pure birth process and use the transitions shown Network Performance 25 Network Performance Evaluation Birth Death Process Analysis Specific queueing systems are modeled by Setting state dependent arrival rates k Setting the state dependent service rates k Solving for the steady state probabilities For details see Queueing Systems Volume 1 Theory by Leonard Kleinrock Wiley 1975 or any queueing theory book Network Performance 26 Network Performance Evaluation Queueing System Notation Kendall s notation A b m K L A type of arrival process b type of service process m number of servers K maximum number of elements allowed in the system system size L population size if L missing then Network Performance 27 Network Performance Evaluation Special cases A b m K L A M the arrival process is Poisson and