Tietoliikenneohjelmistojen ja multimedian laboratorio
Suomeksi

TML / Studies / Tik-110.300 Homeworks

2000: Homework 3 - Model answer

Notice! The role of this model answer is instructional only. The answers might not cover everything in detail that the questions asks. The answers give you the content of the answer and idea what it should be. The things that are important in the grading of the homework have been emphasized. If you think there is a mistake in the model answer, please let the course staff know!


1. Warm-up (4 points)

  1. A 4 kbps channel has a propagation delay of 20 msec. With frames of what size can a Stop-and-Wait protocol achieve >50 % utilization rate?

    Let's mark the number of bits in a frame with b, the transmission time with s and the delay with v.

    Then, the transmission of the frame and getting an acknowledgement will take time t (neglecting the handling):

    t = b/s + 2v
    

    The time to transmit the payload is t2:

    t2 = b/s
    

    And the utilization rate therefore:

       b/s
    ---------- .
    b/s + 2v 
    

    In order to solve the number of bits in a frame, an inequality is formed:

       b/s
    ---------  > 0.5
    b/s + 2v
    

    where everything but b is known. This is then solved according to b:

    b/s > 0.5(b/s)+5
    
    0.5(b/s) > v
    
    b > 2sv  | s=4000, v=0.02
    
    b > 2*4000*0.02
    b > 160
    

    Therefore, the number of bits needed is 160.

  2. A 3000 km E1-line is used to transfer 64-byte frames using Go-back-n protocol (protocol nr. 5). If the propagation speed is 6 usec/km, how many bits should the sequence numbers consist of?

    Let's mark the transmission speed with s, the size of the frame with b, transmission delay with v and the largest sequence number needed with n.

    The sequence number must be large enough to enable contiguous transmission, so, neglecting the time needed to create acknowledgements and handling of frames, we have:

    (n-1)b/s > b/s + 2v
    

    and therefore

           b/s + 2v
    n >   ----------  +  1 .
    	  b/s
    

    Now,

    v = 6 us * 3000 = 18 ms
    b = 64 byte * 8 bits/byte = 512 bits
    s = 2048 bits/s
    

    and therefore

    n > (512/2048000 + 2 * 0.018)/(512/2048000) +1
    n > 146
    

    so the number of bits needed will be

    n_b > log2(n)
    n_b > 8
    

2. Channel utilization rate (9 points)

The following markings will be used:

b = number of bits in frame = 1000 bits
s = transmission speed = 1Mbps
v = transmission delay = 270 ms

The transmission delay is presented in the course book (p. 166) as typical for a satellite link.

  1. Stop-and-Wait

    Functionality: Send frame, wait for it to arrive, send acknowledgement, wait for it to arrive.

    Therefore, the utilization rate will be

       2b         b
    --------- = ----  | b = 1000, v = 270, s = 1000000 
    vs+b+vs+b   vs+b
    
    	  = 0.2 %
    
  2. Go-back-N

    Functionality: n frames can be sent before an acknowledgement must arrive

    n = 2^3-1 = 7
    

    Therefore the utilization rate will be

       nb           
    --------- = 1.3%
    vs+b+vs+b   
    
  3. Selective-repeat

    Using selective-repeat, only half of the window size can be sent before receiving an acknowledgement (why?).

    n = 2^3/2
    

    Therefore the utilization rate will be

       nb
    --------- = 0.7%
    vs+b+vs+b   
    

3. Effect of bit errors (6 points)

Assume that frames are being transmitted over a channel, in which the probability for a frame to be lost or to be received erroneously is p. Consider how the erroneous frames affect the result. How many re-transmissions are needed on an average compared to the number of transmitted frames using the following protocols?

In the assignment a ratio

   re-transmissions
-----------------------
successful transmissions

is calculated.

Using this ratio, also

   re-transmissions
-----------------------
  all transmissions

can easily be calculated.

  1. Stop-and-Wait

    For each lost or broken frame another one will be sent. Therefore, the expected number of retransmissions will be

    p+p^2+p^3+... = p/(1-p)
    

    where p is the probability of losing a frame.

  2. Go-back-n

    For each lost or broken frame the whole contents of the transmission window will be sent.

    Let's mark the number of frames transmitted before the error is noticed with k.

    Therefore we need to send k frames for each sent frame with probability p. Each of these k frames can also be corrupted.

    Let's assume the number of retransmissions is distributed binomially i.e when n frames are sent, pn of them will be corrupted. Out of these ppn will be further corrupted and so on.

    Therefore the total number of retransmissions will be

    np+np^2+np^3+... = n/(1-p)
    

    For each corrupted frame, k frames needs to be transmitted, that is nk/(1-p) frames.

    So we have,

    p(1/2k)+(p(1/2k))^2+(p(1/2k))^3+p(1/2k)^4+... = p(1/2)k/(1-p(1/2)k)
    
  3. Selective repeat

    The expected value will be the same as in a) (why?).

4. Windows in several layers (3 points)

The basic functionality is the same for both layers - contents of a window will be sent in pieces of certain size (pipelining) and acknowledgements will be expected.

On datalink layer the the transmission time is about constant whereas on the transport layer the selected route, congestion and possible duplicates affects the time elapsed. However, the transport layer may be working on a reliable architecture that guarantees that the packets are always delivered successfully.

What also affects the flow control is that you do not necessarily know the capasity of the underlying network, which may become a bottleneck. The windowing on the transport layer should adapt to the restrictions of the network and the receiving party, depending on which of them are lower.


This page is maintained by assistants of tlark, E-mail: tlark@tml.hut.fi
The page has been updated 13.11.2000

URL: http://www.tml.hut.fi/Studies/Tik-110.300/2000/Homeworks/assignment_03_model.html