Exercises – Lower layers

Exercise 7.1.
A receiver that implements the bit destuffing procedure of the HDLC protocol receives the 78-bit sequence (a point is inserted after each group of 10 bits): 0111001111.1100111111.0010111110.1110111110.1101011110.1111011111.1011111100.11111100. Si chiede di Identify the occurrence of flags, any stuffing bits entered by the transmitter and the possible occurrence of errors in the received string.

As shown in Figure E7.1, the string 01111110 representing the flag occurs in bits 6-13, 14-21, 55-62, 70-77, since 6 consecutive bits set to 1 are found only in these strings. Stuffing bit 0, on the other hand, occurs in bits 30 and 40, as only these are preceded by five bits set at 1. Bits 63-68 set at 1 reveal the occurrence of a line error as they cannot be part of a flag (bit 62 is the last bit of the previous flag), nor is the bit stuffing procedure applied. Without counting the stuffing bits, 31 bits are included between the two flags, again highlighting the presence of errors, as the minimum number of bits should be 24 or 32 for an S-type frame (16 bits of the FCS field plus 8 or 16-bit control field).

Figure E7.1 Frame transmission with HDLC protocol according to Exercise 7.1.

Exercise 7.5.
On a link between stations A and B, station B receives a frame whose content, after the removal of the flags and downstream of the bit destuffing operation, is the 15 bit string 101000110101010 (it is assumed that the fields address, control, information of a frame can have arbitrary length). Knowing that the divisor polynomial is , determine whether the received string indicates the occurrence of transmission errors or not.

The verification of error occurrence requires the division into modulo-2 arithmetic of the polynomial P’(x) obtained from the binary string received with the polynomial D(x), as shown in Figure E7.2. Since the remainder is different from 0, we deduce the occurrence of an error during the frame transmission.

Figure E7.2 Verification of error occurrence according to Exercise 7.5.

Exercise 7.7.
Two stations A and B are connected by a bidirectional data transmission system. The line protocol, which controls the frame transmission on this link, is ARQ of type go-back-n. The exchange of frames between the two stations takes place with these hypotheses:
• the two stations operate regularly and the data connection has already been established, when station A sends the first frame at time t = 0,
• only station A sends frames to station B and the transmission buffer is never empty; therefore station B sends only acknowledgment frames (positive and negative),
• the transmission time of a frame and an acknowledgment is, respectively, = 1 ms and = 0.5 ms, the propagation time between the two stations is = 0.6 ms, the time-out for frame retransmission is given by o = 4,
• the transmission medium is subject to errors which can affect any type of frame; it is assumed that only one error occurs when exchanging frames,
• the sender window has the maximum possible opening based on the ARQ protocol features,
• the frame processing time Tp is considered null. Knowing that:
• station A sends 10 consecutive frames starting from t = 0,
• station B sends acknowledgments on the reception of all the frames except the third, it is requested to:
• draw the space-time diagram showing the exchange of frames by associating the type of IU to each frame/ acknowledgment followed by the numbering related to that type of IU (for example, the sequence I,2,3 indicates an information frame with N(S) = 2 and N(R) = 3), assuming that I,0,0 is the first frame sent by station A,
• determine the minimum opening of the sender window and of the receiver window,
• find the minimum number b of bits for the frame numbering consistent with the frames exchanged.

The data provided gives rise to the space-time pattern of transmission/reception of frames and acknowledgments shown in Figure E7.3a. From the lack of acknowledgment sending at the time in which the third frame had to be received by station B it can be deduced that this was lost or was received corrupt. Therefore, the acknowledgment that is sent upon receipt of the fourth frame is necessarily of a negative type (REJ) as it must require the retransmission of the frames transmitted starting from the third one, that is frame number 2. The subsequent information frames are discarded in station B, as their reception is not allowed from the receiver window, which for the GBN protocol has unitary opening. The correct reception of these frames, however, gives rise to the retransmission of the last ACK issued. The numbering of the resulting frames is shown in- Figure E7.3b, which highlights how the set time-out does not come into operation as it is preceded by the receipt of the negative acknowledgment. The supervisory frame REJ, 2 is received by station A when this has already transmitted frame number 5, thus having 4 frames in the retransmission buffer. Therefore the minimum opening of the transmission window is = 4 frames, while by definition the receiving window has unitary opening = = 1. Therefore, at least b = 3 bits are required to number the information frames

Figure E7.3 Frame identification with HDLC GBN protocol according to Exercise 7.7.

Exercise 7.15.
Determine the block code which provides the same coding as the AMI code, also providing the corresponding correspondence table.

Since a positive and a negative signal alternately correspond to the binary symbol 1, while the absence of a signal is associated with the binary symbol 0, the AMI code can also be represented as a block code 1B1T. In this case, the alternation between signals that encode the binary symbol 1 is obtained by defining two states, as indicated in Table E7.1; the transmitted ternary symbol is that given by different states (0 and 1) for consecutive occurrences of the same input binary symbol.

Table E7.1 Coding rule in code 1B1T according to Exercise 7.15.