IND426 Tutorial 3 (Solutions)
(Roberto Togneri 1998)

3.

(a) (b)

1.

(a) (b)

A channel has a data rate of 4 kbps and a propagation delay of 20 ms. For what range of frame sizes does stop and wait give an efficiency of at least 50%? Consider the use of 1000-bit frames on a 1-Mbps satellite channel with a 270-ms delay. What is the maximum link utilisation for: (i) Stop-and-wait flow control? (ii) Sliding-window flow control with W = 127? (iii) Sliding-window flow control with W = 255? (iv) Sliding-window flow control with W = 511?

With a k-bit sequence number field the maximum window should be 2k. Why is the maximum allowable window 2k -1? Two stations communicate via a 1-Mbps satellite link with a propagation delay of 270 ms. The satellite serves merely to retransmit data received from one station to another, with negligible switching delay. Using HDLC frames of 1024 bits with 3bit sequence numbers, what is the maximum possible data throughput (not counting the 48 overhead bits per frame)?

Solution (a) Consider a window W = 2k and a sender that has successfully transmitted all frames in that window (SEQ = 0 … 2k - 1). The receiver will return an RR 0, but does this mean all 2k frames have been received (next SEQ is 0) or that all frames have been lost (next SEQ is also 0)? (b) Tprop = 270 x 10-3, Tframe = (L=1024)/(R=106) = 1.024 x 10-3 so a = 263.7 and 1 + 2a = 528.3. With k = 3 then W = 7 and since W < 1 + 2a, the utilisation is: W 7 U= = = 13.25 × 10 −3 which means an effective throughput of U x R = 13.25 kbps. 1 + 2a 528.3 But only (1024-48)/1024 = 0.9531 of the transmissions pertain to actual data, so the data throughput is 12.63 kbps.

Solution (a) 50% efficiency implies a utilisation U = 0.5. For stop-and-wait: 1 U= 1 + 2a a = 0.5. So at 50% efficiency 1 + 2a = (0.5)-1 Now Tprop = 20ms = 20x10-3 and Tframe = L/(4x103), and a = (Tprop/Tframe) = 80/L = 0.5 and as long if L ≥ 160 bits then efficiency is at least 50%.

Æ

Æ

(b) What is a and hence 1 + 2a? Tprop = 270 ms = 270x10-3 and Tframe = L/R = (1000 / 1x106) = 10-3, a = (Tprop/Tframe) = 270 and 1 + 2a = 541. W ≥ 1 + 2a  1 1  and for sliding-window: U =  W For stop-and-wait: U = W < 1 + 2a 1 + 2a  (1 + 2a)  -3 (i) U = 1/(541) = 1.8x10 (ii) U = 127/541 = 0.23 (iii) U = 255/541 = 0.47 (iv) U = 511/541 = 0.94

Î

4.

Consider a satellite system with a bit error probability p. The data rate is R bps, the average frame length is L bits, Lh is the length of the frame header and RTT is the roundtrip-time for the shortest time an acknowledgment can be returned after a frame has been transmitted. (a) Derive an expression for the maximum normalised data rate of a go-back-N ARQ scheme. (b) Hence explain why for a 48 kbps satellite system with an RTT of 700 msec and p = 10-5 the size of the HDLC frame is 2250 bits. Assume a 48-bit frame header.

2.

A channel has a data rate of R bps and a propagation delay of t sec/km. The distance between the sending and receiving nodes is L km. Nodes exchange fixed-size frames of B bits. Find a formula that gives the minimum sequence field size in bits of the frame as a function of R, t, B and L. Assume that ACK frames are negligible in size, the processing at the nodes is instantaneous, and that maximum utilisation is required.

Solution Maximum utilisation implies W = 1 + 2a Tprop = Lt Tframe = B/R 2 Lt 2 RLt = 1+ Hence W = 1 + B/R B RLt   ) where x  is the smallest Now W = 2 - 1 so k = log2(W + 1), hence k = log 2 ( 2 + B    integer greater than x. k Solution (a) For a frame to be successively received no bits have to be in error. For a frame of length L and a bit error probability of p, this means that the frame error probability: P = 1 − (1 − p ) L and the maximum normalised frame rate for a go-back-N ARQ scheme is: 1− P U= , but with a Lh bits in a frame wasted by header normalised data rate is: 1 + 2aP L − Lh 1 − P , now RTT = 2Tprop and Tframe = L/R, so: Ud = ( ) L 1 + 2aP L − Lh (1 − p ) L L − Lh (1 − p ) L Ud = ( ) ) =( L 1 RTT (1 (1 p ) L ) L 1 RRTT RRTT (1 p ) L + − − + − − L/R L L (b) Let p = 10-5, R = 48 kbps, RTT = 700 msec and L - Ld = 48, then we have: L − 48 0.99999 L Ud = ( ) 33600 33600 L 1 (0.99999) L + − L L For L = 1500 For L = 2000

Î U’ = 0.715 Î U’ = 0.718

For L = 2250 For L = 2500 For L = 3000 For L = 3500

Î U’ = 0.718 Î U’ = 0.718 Î U’ = 0.717 Î U’ = 0.716

Hence the maximum data rate will occur for frames of around length 2250 bits. 5. To improve network throughput and efficiency in a cost-effective manner, what would you do first? (i) Double the bandwidth of the communication channel. (ii) Improve the routing algorithm to reduce the processing and queuing delays. (iii) Increase the window size of the flow control algorithm. What would you do next? Assume a sliding-window protocol is being used.

Solution (i) Double the bandwidth would halve the transmission time Tframe. This would also double a (anew = 2aold). If W is large enough (i.e. W ≥ 1 + 2anew) then this would double the data throughput, but with more packets in the network this can be offset by increased queuing delays. But if W was initially chosen optimally (i.e. W = 1 + 2aold) then this would yield little improvement on the data throughput and halve the link utilisation (although the data throughput would actually increase slightly). Not very cost-effective solution. (ii) The net Tprop would decrease slightly, but more importantly a would decrease yielding both improved link utilisation and the need for a smaller W. The latter would make the network more robust to congestion. Very cost-effective solution. (iii) Increasing W is a “brute-force” to improve link utilisation since it would increase the number of frames in the network, increase end-to-end delays and even create congestion. Option (ii) first then (i) in tandem with (iii).