Exercise 5 (22.-25.2.) (Tanenbaum pp. 175-239)

1. Answer shortly the following questions ("review type" problem: answers are usually found in lecture notes or in Tanenbaum's book).
a) What is Hamming distance?
b) Why in link protocols the checksum CRC is in the trailer and not in the header?
c) What is the sliding window? How does it govern the life of the sender/receiver? What effect does the increasing of the window size have on the protocol performance?
d) Why is it enough to have one bit sequence number in IRQ-protocol?
e) If the window size is K, then in the Selective Repeat method 2K sequence numbers are needed.
Give an example of a situation where a smaller amount of sequence numbers leads to erroneus situation. I
f) What is the Petri Net? What is it used for?
g) How do the HDLC communication modes NRM and ABM differ?
h) What is PPP? How does PPP relate to broken/lost frames?
i) Why is it difficult for the receiver to find out where an ATM cell begins?

2. a) The following data fragment occurs in the middle of a data stream for which the character stuffing algorithm is used: DLE, STX, A, DLE, B , DLE, ETX. What is the output after stuffing? How does the receiver distinguish the end of the frame from the LDE ETX character in the middle of the data stream? What happens to the frame synchronization, if some DLE-, STX- or ETX-character gets crooked?
b) When bit stuffing is used, is it possible for the loss, insertion, or modification of a single bit to cause an error not detected by the checksum? If not, why not? If so, how? Does the checksum length play any role here?

3. Simulate
a) the operation of Go-Back -N protocol,
b) the operation of selective repeat protocol that does not use NAK,
c) the operation of a selective repeat protocol using NAK. NAK(N) informs the sender that frame I(N) is either missing or corrupted
in the situation when an error burst destroys frame I(N+1), ACK(N) and the following acknowlegdement.

4. a) What are the different ways the sender can notice the need to retransmit a frame? How do these ways influence the performance of the different protocols?
b) The Go-Back-N protocol uses cumulative acknowledgement (= ACK(n) acknowledges the frame n and all the frames sent before it) and explicit repeat request (= NAKs). Is it possible to use individual acknowledgement (every received frame is acknowledged) instead? Is it possible to do without NAK acknowledgements?
c) Is the timer inevitable in all protocols mentioned above?

5. Frames of 1000 bits are sent over a 1-Mbps satellite channel. Acknowledgements are always piggypacked onto data frames. The headers are very short. Three-bit sequence numbers are used. What is the maximum achievable channel utilization for
a) Stop and wait (IRQ)
b) Go-back N
c) selective repeat?

6. An data communication protocol follows the HDLC standards and uses the Selective Repeat method to recover from errors. Describe the essential content of the HDLC frames needed in order to cause the following sequence of actions:
- (the primary station P wakes up a secondary station S for reception of data)
- P sends to S a set of data frames
- an error burst destroys the frame N+1 and the acknowledgement N
- exchange of frames and acknowledgements continue