ECE6101/CSE6461
Midterm Exam
Autumn 2022
1. Consider a queuing system where the customer inter-arrival times are uniformly distributed between 2 and 6 seconds independent of each other. The service time is fixed at X seconds for all customers.
(a) If the average number of customers in the system is Navg = 0.35, what is the average time spent in the system T by a customer? (5pt)
(b) What is the average number of customers Nobs an arriving customer sees in the system? (5pt)
(c) Calculate the average waiting time W and the average service time X . (5pt)
2. In the small network depicted below, three external Poisson sources generate packets with rates 5, 4, and 3 packets per second, respectively. All sources generate packets with expo- nentially distributed lengths with the same mean. All nodes have infinite queue capacity and can process 8, 7, and 6 packets per second, respectively. A packet leaving node 1 joins node 2 with a probability of 0.2 and with the same probability node 3. Similarly, a packet leaving the second node joins the third queue with probability 0.2.
(a) Calculate the probability Pall that a packet that enters the system at any queue goes through all nodes in the network. (5pt)
(b) Calculate steady state probability P (n1 ; n2 ; n3 ) that queues 1, 2, and 3 have n1 , n2 , and n3 packets, respectively. (10pt)
(c) What is the probability that there is only onesk packet in the system? (5pt)
(d) Calculate the average packet delay. (5pt)
3. Consider a small office that handles forms. There is a single teller at the counter, and every customer has two forms to be processed, where processing of each form. takes an exponentially distributed amount of time with average µ/1. People arrive at the office following a Poisson process with rate λ. There is only one seat in the waiting area, and if this seat is occupied, customers leave without entering the office. Assume that inter-arrival and service times are independent.
(a) Draw a Markov chain that represents this system and write all the global balance equa- tions. (5pt)
(b) What is the average number of forms Nf in the office (as a function of steady state probabilities)? (5pt)
(c) What is the average number of people Np in the office (as a function of steady state probabilities)? (5pt)
(d) What is the average time spent in the system by a person? (5pt)
4. Consider a queuing system where future arrivals are independent of the system state, i.e., for every time instance t and increment δ > 0, the number of arrivals during the interval (t, t+ δ) is independent of the system state at time t. Show that, in such systems, the average number of customers in the system observed by an arriving customer Nobs is equal to the time average of the number of customers in the system Navg. (25pt)
Hint: Define A(t, t + δ) as the number of arrivals during the interval (t, t + δ), and St as the system state at time t. Consider the relationship between the observed steady state occupancy probability an = lim t→∞ Pr{St = njA(t, t + δ) = 1} and the unconditional steady state probability Pn = lim t→∞ Pr{St = n}.
5. Consider two hosts A and B connected over a half-duplex communication channel using Stop- and-Wait ARQ. Let tData , t Prop, and tACK represent the data packet transmission time, the propagation delay, and the ACK packet transmission time, respectively. Assume that ACK and NACK packets are of the same size.
(a) What is the maximum utilization Ua of the communication channel if the channel is error- free, where utilization is defined as the fraction of time actual data bits are transmitted on the channel? (5pt)
(b) If the data packets are transmitted without errors but the ACK packets contain errors with probability p, how many times does A transmit a data packet on the average before correctly receiving an ACK packet? (5pt)
(c) Calculate the channel utilization Ub for part b). (5pt)