Questions 1 to 4 are based on the following scenario: A router multiplexes four traffic

flows on to a given link. Flow A is a constant bit rate service, Flow B is a variable bit rate

service and Flows C and D are best effort services.

Question 1 [3] (on-off model)

This question relates to understanding of average rate, peak rate and link rate of a

source. Link rate is the maximum rate of a physical connection between the nodes.

However, a source need not send data always at its link rate and rather its maximum

rate is usually defined as the peak rate. Flow B sends the traffic using an on-off traffic

model with an ‘on’ duration of 5 sec and ‘off’ duration of 15 secs. The source sends data

at half the link rate (also known as the peak rate) when “on”. What is the average data

rate of this source? How many packets are sent by this source when it is on (called

burst), assuming an average packet size of 2000 bits? Assume that the link bandwidth is

1.5Mbit/sec.

Question 2 [24] (Scheduling)

Consider the four flows A, B, C, and D at the above queuing point. Each of the flows gets

their own separate queue (per-flow queuing) as shown in the above figure. Assume that

all packets are of equal length (assume unit length). We want to give a weight of 1 to

connection A, 2 to B, 3 to C and 4 to D. Assume that there is always a packet waiting in

the queue for each of the flows to be transmitted.

a) Determine a frame (or cycle) for a WRR service schedule, explaining the reasons

why you chose such a service cycle. [4]

b) What is the bandwidth each flow gets as per WRR scheme? [2]

c) Based on virtual finishing times of WFQ scheduler, determine the sequence of

packets transmitted by the scheduler. Consider up to 40 such packet

transmissions and verify that the packets transmitted are as per the weight

allocation of the flows. [5]

A B C Dd) What is the bandwidth each flow gets as per the above WFQ scheme? [2]

e) Comparing the service orders of the packets of the flows for both schedulers

(WRR and WFQ), what can you infer on burst and delay behavior of the two

systems? [2]

f) Would it be possible to make your WRR schedule to mimic WFQ service order? If

so how? [2]

g) Repeat part (c) with variable packet size. Assume A sends 50 byte packets on the

average, B sends 100 byte packets, C and D both send 500 byte packets. [5]

h) What is the bandwidth each flow gets as per the above WFQ scheme? [2]

Question 3 [10] (Hierarchical Scheduling)

Let us divide the traffic as follows: Real-time (Flow A), Guaranteed (Flow B) and Besteffort (Flows C&D). The scheduler in the above question uses a HRR scheme and divides

the link bandwidth as follows by the level 1 scheduler: 10% to Real-time and 90% to

both Guaranteed and Best Effort traffic. The second level divides the allocated

bandwidth as 20% to Flow B and the remaining to the third level. The third level

scheduler divides the allocated bandwidth in the proportion of 1/3 to Flow C and the

remaining to flow D. Determine a schedule based on the HRR scheme discussed in the

class. Assume all packets are of constant length.

Question 4 [5] (Scheduling SCFQ)

Packets of length 10 and 15 arrive at connections A and B at a scheduler serving a link of

unit rate at time 0. Packets of length 5 and 10 arrive at connection A at times 9 and 17.

What are the finish numbers under Self Clocked Fair Queueing (SCFQ) assuming the

flows have equal weights?

Question 5 [3]

Consider two connections with loads 0.2 and 0.4 that have mean waiting times of 0.3

and 0.4s at an FCFS scheduler. If a new scheduler gives the first connection a mean delay

of 0.1, what must be the mean delay of the other connection increase to? (Hint: use the

conservation theorem)

Question 6 [5]

A 10%

B C D

1

3

2

90%A link of 100Mb/s is shared by 6 flows (f1 to f6) at a router. The maximum rate at which

these flows wish to send data are as follows: f1=1Mb/s; f2=2Mb/s; f3=10Mb/s;

f4=20Mb/s; f5=100Mb/s; f6=100Mb/s. Compute the rate allocated to each of these

flows using max-min allocation.

Question 7 [5]

Max-Min allocation algorithm we discussed in the class (Slide 24 of Queuing and

Scheduling slides) uses the concept of equal fair-share where the bandwidth is equally

divided among the flows. Extend this algorithm to include the concept of weighted fair

share where the bandwidth allocated is in proportion to weights of the flows. Use this

algorithm to compute the bandwidth allocation for Question 6 when the weights of

flows are: w1=10; w2=10; w3=20; w4=20; w5=40; w6=100

Question 8 [10]

This question relates to delays experienced by flows in the network. Consider two flows

Class 1 (high priority) and Class 2 (low priority) multiplexed (queued) at a router’s

outgoing link (1Mbps). Please refer to the slides 40 of Queueing and Scheduling. Assume

Class 1 sends 500 bytes packets and Class 2 sends 1000 bytes packets. Assume Si2=2/ µi2.

a) What is the packet service time (=1/µ1=time to transmit a packet) for Class 1?

b) What is the packet service time (=1/µ2=time to transmit a packet) for Class 2?

c) Given Class 1 packet arrival rate = 25 packets/sec and Class 2 packet arrival rate

= 50 packets/sec, what are the expected waiting times for each class? What are

the expected number of customers (apply Little’s law) in each queue? What is

the total utilization of the queue?

d) Now given Class 1 packet arrival rate = 50 packets/sec and Class 2 packet arrival

rate = 50 packets /sec, what are the expected waiting times for each class? What

are the expected number of customers (apply Little’s law) in each queue? What

is the total utilization of the queue?

e) Now given Class 1 packet arrival rate = 100 packets/sec and Class 2 packet arrival

rate = 50 packets /sec, what are the expected waiting times for each class? What

are the expected number of customers (apply Little’s law) in each queue? What

is the total utilization of the queue?

f) Analyze the data from parts (c), (d) and (e), i.e., given a change in class 1 load

(traffic), how much increase in delay is experienced by class 2 traffic?

Little’s Law: E{n} = . E{w}. i.e., average (expected) number of customers in a queue =

average arrival rate to the queue × average (expected) waiting time of the queue.

Sale!