COMP 5416 Week 10
Q1. In this question, you are going to understand how a Markov chain can address a queue serving different types of packets.
Given a queue with limited buffer size. The queue can accommodate 4000 bytes of data. There are two types of packets, type 1 packets have a size of 1000 bytes. Type 2 packets have a size of 2000 bytes. Let x and y be the numbers of type 1 and 2 packets, we have x + 2y ¡Ü 4 (why?). Suppose that the arrivals of types 1 and 2 packets follow independent Poisson processes, both with arrival rates 1 unit/s. The service time of each type of packets follows exponential distribution. The service rate of type 1 packets is 4 units/s. The service rate of type 2 packets is 2 units/s. (The service rate of type 2 is smaller than that of type 1 as type 2 packets are larger!)
If a new arriving packet cannot be accommodated, it will be dropped. The packets are served by the First-Come-First-Served rule.
(1) Let (a,b) denote the number of types 1 and 2 packets. Could you draw the transition diagram of the system? Complete the following diagram.
(2) Verify the stationary distribution of the system. (You are not required to know how to derive the stationary distribution, but you need to know how to verify them.)
(3) What is the average number of packets in the system?
Q2. Consider the figure below. Answer the following questions:
a. Assuming FIFO service, indicate the time at which packets 2 through 12 each leave the queue. For each packet, what is the delay between its arrival and the beginning of the slot in which it is transmitted? What is the average of this delay over all 12 packets?
b. Now assume a priority service, and assume that odd-numbered packets are high priority, and even-numbered packets are low priority. Indicate the time at which packets 2 through 12 each leave the queue. For each packet, what is the delay between its arrival and the beginning of the slot in which it is transmitted? What is the average of this delay over all 12 packets?
c. Now assume round robin service. Assume that packets 1, 2, 3, 6, 11, and 12 are from class 1, and packets 4, 5, 7, 8, 9, and 10 are from class 2. Indicate the time at which packets 2 through 12 each leave the queue. For each packet, what is the delay between its arrival and its departure? What is the average delay over all 12 packets?
d. Now assume weighted fair queueing (WFQ) service. Assume that odd-numbered packets are from class 1, and even-numbered packets are from class 2. Class 1 has a WFQ weight of 2, while class 2 has a WFQ weight of 1. Note that it may not be possible to achieve an idealized WFQ schedule as described in the text, so indicate why you have chosen the particular packet to go into service at each time slot. For each packet what is the delay between its arrival and its departure? What is the average delay over all 12 packets?
e. What do you notice about the average delay in all four cases (FIFO, RR, priority, and WFQ)? Why?