Exercise 4 Shortest queue We consider a system composed of two queues, q1 and 42, given in Figure At each time instant, the a d₁ 91 92 FIGURE 1 System with two queues. probability that there is a new packet arriving in the system is equal to a. Upon arrival, the packet is sent to the shortest queue. If both queues have the same number of packets, the new packet is sent to queue 1. Each queue has one server and if the queue i is not empty, at each time step one packet is served with probability d. The packet that arrived at time instant t can be served in the same time slot. Let X,(t) be the number of packets in queue i at time t. Then X;(t + 1) = X;(t) + Ai(t) - Di(t), i € {1,2}, where A,(t) the number of packets that arrived at queue i and D,(t) the departures from queue i at time t. 1. Show that X(t) = (X₁(t), X2(t)), 1 € N is a Markov chain. Under which conditions on a, d₁ and d₂ this chain is irreducible and aperiodic? Let a = 0.4 and d₁ = d₂ = 0.25. The the Markov chain s positive recurrent. However, the function h(x) = x1+x2 does not satisfy the Foster condition. Explain why. 2. Which among the following functions satisfy Foster condition? (a) ha(z) = (x1+22)², (b) h₁(x) = (±1 − ×2)², 2 (c) he(x) = x²+x}. For each function, justify your answer. 3. Under which conditions on a, d₁ and d₂ the chain is positive recurrent ? Justify your answer.

Fig: 1