TCOM501 – Networking: Theory & Fundamentals KMidterm Examination Professor Yannis A. Korilis March 5, 2003 Answer all problems. Good Luck! Problem 1 [20 points]: Consider an M/M/1 queue that can accommodate at most K customers in the system (queued or in service), and suppose that a customer that arrives and finds the system full is not lost, but stored in an external queue with infinite space as shown in the figure. Kλµikexternal queue server queue The transition of a customer from the external to the server queue is instantaneous. Therefore, a customer that arrives when the number of customers in the server queue is less than K enters instantaneously the server queue. Similarly, when a customer departs from the server queue, the customer at the head of the external queue moves to the server queue instantaneously. This two-queue system can be modeled as a two dimensional Markov chain with states(, , where . )ik0,0ik≤<∞ ≤ ≤2. Find the (steady-state) probability that there are customers in the external queue and k customers in the server queue, . [10 points] 1. Draw the state transition diagram of the two-dimensional chain. [3 points] ( , )pik0iK, 0ik≤<∞ ≤ ≤ 3. Find the average number of customers in the server queue, and the average number of customers in the external queue. [5 points] 4. Find the average total time that a customer spends in the two-queue system. [2 points] 1 of 4Problem 2 [20 points]: Customers arrive at a service station according to a Poisson process with rate λ. For each of the following cases, we assume that service times are exponentially distributed and independent of each other and the arrival process. Queue buffers are infinite and customers are served on a first-come-first-served basis. Consider the following types of service stations: Type 1: There are two servers sharing a common queue. Each server provides service at rate µ. A customer that upon arrival finds the system empty is routed randomly to one of the servers. If the customer finds one server free, it is routed to that server. Otherwise, it enters the queue and waits for service. Type 2: There is a single server (with a single queue) that provides service at rate 2µ. Type 3: There are two servers, each with its own dedicated queue. The service rate of each server is µ. Upon arrival to the combined service system, a customer is routed to the first queue with probability ½, or to the second queue with the same probability. Answer the following questions expressing, whenever possible, the quantities of interest in terms of the load /2 .ρ=λ µ2. For a Type 2 station, find the average number of customers in the system and the average time a customer spends in the system. [2 points] 1. For a Type 1 station: [10 points] a. Draw the state transition diagram, and derive the stationary distribution , 0,1,...npn= b. Find the average number of customers in the system and the average time a customer spends in the system. c. Find the average number of customers that are queued and wait for service. 3. For a Type 3 station, find the average number of customers and the average time delay for the simple two-queue network. [3 points] 4. Compare the average time delay of these three systems from parts 1b, 2, and 3. Is it better to use two identical servers or a single server with double processing power to serve a single queue? If we have two servers, is it better to use dedicated queues, or a common queue for waiting. Explain the results intuitively. [5 points] Problem 3 [20 points]: Poisson arrivals with rate λ join a queue in front of two parallel servers A and B, with exponentially distributed service times with rates µand µ , respectively, where . A customer that upon arrival finds the system empty is allocated to the fastest server. Otherwise, the head of the queue takes the first free server. 1 21µ>µ3. Find the transition rates of the reversed Markov chain and draw its state-transition diagram. Is the system reversible? [5 points] 21. Define the states describing the system as a Markov chain and draw the state-transition diagram. [5 points] [Hint: You will need to introduce state 1A corresponding to 1 customer in the system served by server A.] 2. Find the stationary distribution. [10 points] 2 of 4Problem 4 [20 points]: Consider a simple network that consists of two queues in tandem. Customers arrive at queue 1 according to a Poisson process with rate λ and depart from queue 2. 1µλ2µ The service times at queue i are exponentially distributed with mean 1/ , independent of each other, the service times at the other queue and the arrival process. iµProblem 5 [20 points]: Consider a ring network with nodes 1,2,…,K. In this network, a customer that completes service at node i exits the network with probability p, or it is routed to node i+1 with probability 1-p, for i = 1,2,…,K-1. Customers that complete service at node K, either exit the network, or are routed to node 1, with respective probabilities p and 1-p. 1. Prove that the stationary distribution of the network is: by guessing the arrival rates and routing probabilities of the network reversed in time. These guesses determine the transition probabilities of the reverse Markov chain, where m and n are states in the two-dimensional state space. Then, prove that: 12112 1 2 2(, ) (1 ) (1 )nnpn n=−ρ ρ ⋅ −ρ ρ1. Find the aggregate arrival rates . [5 points] 2. Find the stationary distribution of the network. Under what conditions does this stationary distribution exist? [4 points] *(,)qmn3. Find the average time that a customer spends in the network. [5 points] **() (, ) ( )( ,), ,(, ) (, ),mn mnpnq nm pmqmn mnqnm qnm n≠≠=∀=∀∑∑4. Is this ring network reversible? Justify your answer. [3 points] Then, applying a theorem for time-reversed Markov chains, it follows that is indeed the stationary distribution, and are the transition rates of the reverse chain. [10 points] ()pn*(,)qmn5. Is the flow on the link between nodes 1 and 2 Poisson? Justify your answer. [3 points] 2. Prove that the stationary distribution of the network is the one described in part (1) using Burke’s theorem. [10 points] At each node, external customers arrive according to a Poisson process with rate γ. The service times at each node are exponentially distributed with rate µ. The arrival processes and the service times at the various nodes are independent. , 1,