Intro to Telecom Networks  Test 3

ECSE 416 – Intro to Telecom Networks 
Test 3
Please scan your answers and submit the scanned
pages as a single pdf file. Alternatively, you can prepare answers in electronic
format and submit a single pdf.
5 questions, 60 marks
There are 5 questions. Marks allocated to each part are indicated in square brackets.
This exam is open book. You are permitted to consult any resources — textbook, web, notes.
But do not discuss the questions and solutions with your classmates. Do not ask anyone else to
help you solve the problems.
Question 1 [20 marks]
3. Capacity Requirements.
Consider an MPEG video stream that is shaped by a token bucket with rate r = 0.15 M bps
(Mbps = Megabits per second), and burst size b = 15, 000 bits. The output of the token
bucket feeds into a bu↵ered link with capacity C = 300 kbps.
Token
bucket
MPEG
stream C
(a) (5 marks) Determine the maximum backlog and the maximum delay at the bu↵ered
link.
(b) (5 marks) Instead of a single bu↵ered link, now assume that the trac goes through
a sequence of three bu↵ered links with rates C1 = 400 kbps, C2 = 200 kbps, and
C3 = 300 kbps, for the first, second and third link, respectively. Determine the maximum
backlog and the maximum delay in the network.
Solution:
You get an idea of the solution if you first draw the envelope and the service curve. We know
that the max. backlog is the maximum vertical distance between the two curves, and the
max. delay is the maximum horizontal distance between the curve.
(a) We have an envelope for the arrivals of R(t)=(b + rt)It0, and a service curve of
S(t)=(Ct)It0.
From the lecture we know that
bmax = E ↵ S(0) = sup
t0
(b + rt  Ct)
For the given envelope, we see that the expression is decreasing in t (since r<C). In
other words, the largest value (sup) is attained when t is selected as small as possible
(t = 0). We get:
bmax = b = 15, 000 bits
To get the max. delay, look up your lecture notes and find
dmax = sup
t0
✓E(t)  S(t)
C
◆
Plugging in and seeing that the right-hand side is maximal when t = 0, we get:
dmax = b/C = 15, 000 bits
300 kbps = 50 msec
(b) The solution is a simple application of the network service curve, i.e., the service curve
given by the network as a whole is the convolution of the service curves of each node.
You need to realize that the convolution for constant-rate service curves is the smallest
rate. For t 0, we have:
(C1 · t) ⇤ (C2 · t) ⇤ (C3 · t) = min {C1, C2, C3} · t
7
Figure 1: Shaper and queue for the MPEG video stream.
As in Fig. 1, A token bucket is used to shape an MPEG video stream. The token bucket has
rate r = 0.15 Mbps (Mbps = Megabits per second), and burst size b = 15,000 bits. The output of
the token bucket feeds into a buffered link with capacity C = 300 kbps.
a) Sketch the arrivals curve at the buffered switch if the MPEG traffic is being generated at such
a rate that the traffic shaper is always busy. Make sure your sketch includes proper labels for
the axes. Please read parts (a)-(c) to make sure your graph can show everything requested.
[3 marks]
b) On the same graph, show the service curve of the buffered link. [2 marks]
c) For the buffered link, calculate the maximum backlog and the maximum delay. Show where
these occur on your plot. [5 marks]
d) Let us assume that rather than going through a single buffered link, the traffic goes through
three buffered links in succession. The rates of the first, second and third links are C1 =
400 kbps, C2 = 200 kbps, and C3 = 300 kbps, respectively. Specify the service curve for
the combination of three buffered links and hence determine the maximum backlog and the
maximum delay in the network. [4 marks]
Now let us consider a VoIP system and the impact of fixed or adaptive playout delay.
e) Suppose first that the VoIP system uses a fixed playout delay of 400 ms. Three packets are
received with timestamps 28.04, 28.08, and 28.12. The timestamp is expressed in seconds
1
relative to an arbitrary starting time. If the receiver’s clock is synchronized with the sender’s,
when will the receiver play these packets out (relative to the same arbitrary start time). [2
marks]
f) The receiver changes to an adaptive playout mechanism. There is a silence period, and then a
sequences of packets is received with timestamps 40.05, 40.07, 40.09. Prior to this burst, the
average measured delay was 50 ms and the average deviation was 5ms. The measured delay
for the first packet in this burst is 60ms. Suppose the VoIP receiver does one update of the
adaptive playout parameters before playing out the sequence. It uses EWMAs with constants
α = 0.1 and β = 0.1 . When calculating the playout time, the average delay deviation is
multiplied by K = 5. At what times are the three packets played out? [4 marks]
2
Question 2 [10 marks]
Suppose there are 6 classes of traffic: A, B, C, D, E, F. In your design below, you have access to
weighted fair queuing (WFQ) scheduling mechanisms and strict priority queuing (SPQ) mechanisms
(in the latter one input always has priority over the other). The outgoing link has capacity 10 Mbps.
Suppose you wish to satisfy the following requirements:
• Class A should always have priority over all other classes.
• Classes B and C should always have priority over classes D, E, and F.
• Class B should be allocated 3 times as much bandwidth as class C.
• Class D should be allocated 5 times as much bandwidth as class F.
• Class E should be allocated 4 times as much bandwidth as class F.
a) Assign each traffic class into one queue and draw a diagram to describe the queuing discipline.
(Hint: you may need multi-level scheduling, where the output of one queue is the input of
another.) [6 marks]
b) Complete the following table for this queuing system. Recall that the output rate of the
entire link is 10 Mb/s. [4 marks]
Input Rates (Mb/s) Output Rates (Mb/s)
A B C D E F A B C D E F
2 7 3 2 3 4
1 1 1 6 1 2
2 2 2 3 3 3
3
Question 3 [10 marks]
Packets are arriving from two flows at a WFQ scheduler. The arrival times and packet sizes
given as follows:
Flow 1 Flow 2
Packet Label 1a 1b 1c 1d 2a 2b 2c
Arrival Time 1 2 3 11 0 5 9
Packet Size 1 1 2 2 3 2 2
• Assume that the transmission rate is (C = 1), i.e., it takes one time unit to transmit a packet
of size 1, two time units to transmit a packet of size 2, etc..
• Assume the two flows have weights such that the WFQ weight for flow 1 is φ1 = 1/3 and the
weight for flow 2 is φ2 = 2/3.
a) Devise the transmission schedule of a fluid-flow WFQ scheduler (weighted GPS). Multiple
packets can be sent in parallel, with bandwidth allocated according to the weights. The
transmission schedule must specify, for each time interval, which packets are being transmitted
and how much bandwidth is allocated to them. Make sure to provide the departure times
of all packets. (Refer to individual packets using the labels given in the table). A figure
can be used to depict this information, but please make sure it is very clear and everything
important is labelled. [4 marks]
b) Determine the transmission schedule of a packet-level WFQ scheduler. Provide the departure
times of all packets. (Refer to individual packets using the labels given in the table). [4
marks]
c) What is the maximum discrepancy between the departure times of any packet under the two
scheduling approaches? What is the largest this value could be for any set of packet arrivals?
[2 marks]
4
Question 4 [8 marks]
The iSLIP scheduling algorithm is a modification of PIM to avoid the randomness and improve
fairness. It involves the following three steps:
• Request: Each input sends a request to every output for which it has a queued cell.
• Grant: If an output receives any requests, it chooses the one that appears next in a fixed,
round-robin schedule starting from the highest priority element. The output notifies each
input whether or not its request was granted. The pointer gi to the highest priority element
of the round-robin schedule is incremented (modulo N) to one location beyond the granted
input.
• Accept: If an input receives a grant, it accepts the one that appears next in a fixed, round-robin
schedule starting from the highest priority element. The pointer ai to the highest priority
element of the round-robin schedule is incremented (modulo N) to one location beyond the
accepted output.
D Router Design
10. Consider the iSLIP crossbar scheduling algorithm.
(a) For a router with N ports, what is the maximum number of iterations iSLIP could take to complete?
(b) Place packets in the virtual output queues (VOQs) below such that during the next time slot the
iSLIP algorithm takes 2 iterations to complete and each output is given a packet to transmit.
Assume that input 1 is the next input in both output 1’s and output 2’s round robin schedule.
I
1
VOQ1
VOQ2
I
2
VOQ1
VOQ2
NEXT
OUTPUT: 1
NEXT
OUTPUT: 1
NEXT
INPUT: 1
NEXT
INPUT: 1
O1
O2
(c) Place packets in the virtual output queues (VOQs) below such that during the next time slot the
iSLIP algorithm takes 1 iteration to complete and each output is given a packet to transmit. Assume
that input 1 is the next input in both output 1’s and output 2’s round robin schedule.
I
1
VOQ1
VOQ2
I
2
VOQ1
VOQ2
NEXT
OUTPUT: 1
NEXT
OUTPUT: 1
NEXT
INPUT: 1
NEXT
INPUT: 1
O1
O2
Page 6
Figure 2: Switch with two inputs and two outputs using a VOQ mechanism and iSLIP scheduling.
a) Identify a set of packets in the virtual output queues (VOQs) of Figure 2 such that during
the next time slot the iSLIP algorithm takes 2 iterations to complete and each output
is given a packet to transmit. Assume that input 1 is the next input in both output 1’s and
output 2’s round robin schedule. Explain how your solution works. [4 marks]
If
b) Identify a set of packets in the virtual output queues (VOQs) of Figure 2 such that during
the next time slot the iSLIP algorithm takes 1 iteration to complete and each output is
given a packet to transmit. Assume that input 1 is the next input in both output 1’s and
output 2’s round robin schedule. Explain how your solution works. [4 marks]
5
Question 5 [12 marks]
• Your enterprise network is required to support 96 hosts and 3 servers (labelled D, E, F).
• You have been allocated the subnetwork 222.222.221.0/24. You have 3 openflow switches
available to configure, labelled A, B, and C.
• You are required to group the hosts into three groups X, Y, and Z of equal size.
• Server D is a public-facing webserver that should be open to all internal users and available
for secure connection requests from external users. Your network should be configured so
that only appropriate, secure connections are permitted.
• Server E should be accessible to user groups X and Y, but not Z.
• Server F should be accessible to user groups X and Z, but not Y.
• Aside from the connections to the public server, no external parties should be able to communicate to internal hosts or servers. But all internal clients should be able to connect with
external web servers.
• Only switch A should be connected to the public Internet. This should implement a NAT
so that all emerging traffic has source address 222.222.221.17 (and all traffic to your network
should be sent to this address).
Show how you could configure the switches using generalized forwarding flow tables to accomplish the configuration. Draw a diagram of your network providing clear labels of ports, IP
addresses, server and client allocations. Provide the flow table for each switch.
6