Telecom Networks Test 3 Solution

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.
3. Capacity Requirements.
But do not discuss the questions and solutions with your classmates. Do not ask anyone else to

helpConsideryousolveantheMPEGproblemsvideo. 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
Questionbucketfeeds1[20intomarks]bu↵ered link with capacity C = 300 kbps.

MPEG

stream

Token


bucket


C



(a) (5 marks) Determine the maximum backlog and the maximum delay at the bu↵ered Figure 1: Shaper and queue for the MPEG video stream.
link.

(b)As in(5Figmarks.1,A) Insteadtokenbucketofa singleisusd buto↵shapeered liank,MPEGnow assumevideostreamthat. theThetratokenffic goesbucketthroughhas rate r =a 0.sequence15Mbps (Mbpsofthree= Megabitsbu↵ered perlinkssecond),with ratesandburstC1 size=400b= kbps15,000Cbits2=. The200outputkbps, ofand the tokenC3bucket=300 feedskbps,intofor theabufirst,eredsecondlinkwithandcapacitythirdlink,C=respectively300kbps.. Determine the maximum
backlog and the maximum delay in the network.
a) Sketch the arrivals curve at the bu ered switch if the MPEG tra  c is being generated at such

Solution:aratethat the tra  c 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. You get an idea of the solution if you first draw the envelope and the service curve. We know
[3 marks]
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.
b) On the same graph, show the service curve of the bu ered link. [2 marks]

c)(a)ForWethehavebu eredanenvelopelink,calculateforthethe arrivalsmaximumof backlogR(t)=and(b +thertmaximum)I,anddelayservice.Show curvewhere of
t>0
theseS(t)occur=(Cton)Iyourt>0. plot. [5 marks]
From the lecture we know that

d) Let us assume that rather than going through a single bu ered link, the tra  c goes through three bu ered links in succession.  The↵rates of the  rst, second and third links are C1 =
bmax = E    S(0) = sup (b + rt    Ct)
400 kbps, C2 = 200 kbps, and C3 = 300 kbps, respectively≥0.  Specify the service curve for
the combination of three bu ered links and hence determine the maximum backlog and the For the given envelope, we see that the expression is decreasing in t (since r < C). In
maximum delay in the network. [4 marks]

other words, the largest value (sup) is attained when t is selected as small as possible Now( let= us0) .considerWeget:a VoIP system and the impact of xed or adaptive playout delay.
bmax = b = 15, 000 bits
e) Suppose rst that the VoIP system uses a xed playout delay of 400 ms. Three packets are To get the max. delay, look up your lecture notes and find
received with timestamps 28.04, 28.08, and 28.12.  The timestamp is expressed in seconds
✓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
= 50 msec




300 kbps


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 rst 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]




Question 2 [10 marks]

Suppose there are 6 classes of tra c: 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 tra c 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




































Question 3 [10 marks]

Packets are arriving from two ows 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 ows have weights such that the WFQ weight for ow 1 is 1 = 1=3 and the weight for ow 2 is 2 = 2=3.

    a) Devise the transmission schedule of a uid- ow 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 gure 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 modi cation of PIM to avoid the randomness and improve fairness. It involves the following three steps:
        ◦ Router Design
Request: Each input sends a request to every output for which it has a queued cell.

    10. Consider GranttheiSLIP:If ancrossbaroutputschedulingrceives algorithmnyrequests,. it chooses the one that appears next in a  xed,
round-robin schedule starting from the highest priority element.  The output noti es each
(a) For a router with N ports, what is the maximum number of iterations iSLIP could take to complete?

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  xed, 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
(b) Place packets in the virtual output queues (VOQs) below such that during the next time slot the accepted output.

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.


VOQ
I    1




VOQ
I    1


NEXT
NEXT

O1




OUTPUT: 1
INPUT: 1







NEXT
NEXT

O2
OUTPUT: 1
INPUT: 1











    (c) Place packets in the virtual output queues (VOQs) below such that during the next time slot the FigureSLIP 2:algorithmSwitch takeswith two1iterationinputs toandcompletetwooutputsandeachusingoutputaVOQisgivenmechanismpacket andtotransmitiSLIPscheduling.Assme.
that input 1 is the next input in both output 1’s and output 2’s round robin schedule.

        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


VOQ1


NEXT
NEXT


is given a packet to transmit. Assume that input 1 is the next input in both output 1’s and
I1
VOQ

OUTPUT: 1
INPUT: 1
O1








output 2’s round robi2n 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
I

VOQ



O










the next time slot the1
iSLIP algorithm NEXTtakes 1 iterationNEXT to complete and each output is

2



OUTPUT: 1
INPUT: 1

2
given a packet toVOQtransmit. Assume that input 1 is the next input in both output 1’s and


2






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 open ow switches available to con gure, 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 con gured 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 com-municate 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 tra c has source address 222.222.221.17 (and all tra c to your network should be sent to this address).

Show how you could con gure the switches using generalized forwarding ow tables to ac-complish the con guration. Draw a diagram of your network providing clear labels of ports, IP addresses, server and client allocations. Provide the ow table for each switch.





























6