Starting from:
$29
Assignment 2 A router multiplexes four traffic flows
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.
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.
1 file (573.0KB)
