Section 12.6. Exercises

12.6. Exercises

1.	In a leaky-bucket traffic-shaping scheme, ‰ = 4 grants are initially allocated to a session. The count is restored back to 4 every 4 /g seconds. Assume a Poisson arrival of packets to the system. Develop the first five balance equations for the corresponding Markovian process. Sketch a Markov chain representing the number of grants allocated to packets, and indicate as many transition values as you have computed.
2.	A small router is equipped with the leaky-bucket traffic-shaping scheme; the capacity of the grant buffer is set on window size ‰ = 2. Packet arrival during 1 /g is uniformly distributed, with four possibilities of k = 0, 1, 2, and 3 packets. Assume P = 0.008. Find the probability that k packets arrive during 1 /g , denoted by P X (k) . Find the probabilities that 0, 1, 2, or 3 grants are allocated to arriving packets. Find all the transition probabilities for three states 0, 1, and 2. Sketch a Markov chain representing the number of grants allocated to packets for the first three states.
3.	A router attached to mail server is responsible only for receiving and smoothing e-mail. The router is equipped with the leaky-bucket traffic-shaping scheme, whereby the capacity of the grant buffer is set on window size ‰ = 4. Packets arrive at » = 20 packets per second, and grants arrive at g = 30 packets per second. Packet arrival during 1 /g is distributed according to Poisson. Assume that P = 0.007. Find the probability that k packets arrive during 1 /g , denoted by P X (k) . Find the probabilities that 0, 1, 2, and 3 grants are allocated to arriving packets. Find all the transition probabilities for four states 0, 1, 2, and 3. Sketch a Markov chain representing the number of grants allocated to packets for the first four states.
4.	Consider a token-bucket traffic shaper. Let the bucket size be b bits and the token arrival rate be ½ b/s; let the maximum output data rate be z b/s. Derive an equation for T b , the time consumed for a flow to be transmitted at the maximum rate. Find T b when the bucket size is b = 0.5 Mb, ½ = 10 Mb/s, and z = 100 Mb/s.
5.	Does nonpreemptive priority queueing change the packet transmission orders if bit-by-bit round- robin service is used?
6.	Derive an expression for a priority scheduler to present the mean residual service time, r i , used in Equation (12.10). ( Hint: Use µ i .)
7.	Assume that all components of a three-flow ( n = 3) priority scheduler are identical: » i = » = 0.2/ms, 1 / µ i = 1 / µ = 1/ms, and r i = r = 0.5/ms. Find the total system delay for a packet passing each of the three queues 1, 2, and 3 and the server denoted by E [ T 1 ], E [ T 2 ], and E [ T 3 ], respectively. Do the following. Use a nonpreemptive priority scheduler for the task. Use a preemptive priority scheduler for the task. Comment on results obtained in parts (a) and (b).
8.	We want to compare the impact of an increased number of inputs on total delay in priority schedulers . Assume that all components of a three-flow ( n = 3) and a four-flow ( n = 4) priority scheduler are identical: » i = » = 0.2/ms, 1 / µ i = 1 / µ = 1/ms, and r i = r = 0.5/ms. Find the total system delay for a packet passing queue 3 denoted by E [ T 3 ]. Do the following Use a nonpreemptive priority scheduler for the task. Use a preemptive priority scheduler for the task. Justify the results obtained in parts (a) and (b).
9.	Suppose that four flows are processed in a router that accepts only equal-size packets. Packets in these flows arrive at the following virtual clock times: Flow 1: 4, 5, 6, 7, 9 Flow 2: 1, 6, 9, 12, 14 Flow 3: 1, 4, 8, 10, 12 Flow 4: 2, 4, 5, 6, 12 For each packet, give the virtual clock count at which it is transmitted, using fair queueing. If the arrival times of two packets are the same, the smaller flow number is selected. Now consider weighted fair queueing, whereby flows 1, 2, 3, and 4 are given 10 percent, 20 percent, 30 percent, and 40 percent of the output capacity, respectively. For each packet, give the virtual clock count at which it is transmitted.
10.	Consider the router interfaces in Figures 3.11 and 3.16. Explain where and how fair queueing can be implemented.
11.	We define the timing parameters s i , f i , and a i for a weighted fair-queueing scheduler similar to what we did for the fair-queueing scheduler. Derive a relationship among these parameters, taking into consideration the weight of each flow (packet), ‰ i .
12.	In a nonpreemptive priority queueing scheme, a low-priority flow is guaranteed to receive 10 percent of the total bit rate s of the transmission link. How much better does this low-priority flow perform? What would be the impact on the performance of the high-priority flows?
13.	Each output port processor unit of a router has four inputs designated to four different flows. The unit receives the packets in the following order during a period in which the output port is busy but all queues are empty. Give the order in which the packets are transmitted. Flow:1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 3, 4 Packet: 1, 2, 3, 4, 5, 6, 7,8, 9, 10, 11, 12 Packet size: 110, 110, 110, 100, 100, 100, 100, 200, 200, 240, 240, 240 Assume a fair queueing scheduler. Assume a weighted fair-queueing scheduler with flow i ˆˆ{1, 2, 3, 4} having weights ‰ i ˆˆ{10%, 20%, 30%, 40%} of the output capacity, respectively.
14.	In Figure 12.16, flows A, B, C, and D are processed at one of the outputs of a router. For each packet, the time it arrives and its label are indicated in the figure. Specify the order of packets transmitted at this output, using the following three schedulers. All schedulers scan the flows, starting from flow A. Priority queueing . Priorities decrease from line A to line D. Fair queueing . If the arrival times of two packets are the same, the smaller flow number is selected. Weighted fair queueing , where flows A, B, C, and D are given 10 percent, 20 percent, 30 percent, and 40 percent, respectively, of the output capacity. Figure 12.16. Exercise 14 comparison of priority queueing, fair queueing, and weighted fair queueing on processing of four flows
15.	Figure 12.17 shows four flows (A, B, C, and D) to be processed at one of the outputs of a router. For each packet, the time it arrives and its label are indicated in the figure. Specify the order of packets transmitted at this output, using the following three schedulers. All schedulers scan the flows, starting from flow A. Priority queueing. Priorities decrease from line A to line D. Fair queueing. If the arrival times of two packets are the same, the smaller flow number is selected. Weighted fair queueing , where flows A, B, C, and D are given 20 percent, 10 percent, 40 percent, and 20 percent, respectively, of the output capacity. Figure 12.17. Exercise 15 comparison of priority queueing, fair queueing, and weighted fair queueing on processing of four flows