7.Flow and Error Control – Express Learning: Data Communications and Computer Networks

7

Flow and Error Control

1. Differentiate between flow control and error control.

Ans: Flow control and error control are the most important functions of data link layer. Flow control refers to a set of procedures that allows the communicating devices having different speed and memory characteristics to communicate with each other in an efficient manner. It ensures that a slow receiver is not being flooded by the fast sender. Thus, flow control restricts the amount of data that can be sent from the sender before waiting to receive an acknowledgement (ACK) from the receiver. Each receiver has a block of memory known as buffer for reserving the incoming data before they can get processed. The flow control mechanism can be achieved in two ways. First, if the receiver's end buffer begins to fill up, then the receiver should tell the sender either to stop the transmission completely or send fewer frames. Second, the receiver must acknowledge the received frames by sending ACK frame to the sender. For the frames, which are damaged or lost during transmission, the receiver should send negative acknowledgement (NACK) to the sender by transmitting NACK frame. Two basic protocols that can be used to control the flow of data include stop-and-wait and sliding window protocol.

Error control, on the other hand, refers to a set of procedures that ensure that all the frames have eventually been received at the destination. If any frames are lost or damaged during transmission, the error control mechanism allows the receiver to inform the sender about it and coordinates the retransmission of those frames by the sender. In data link layer, the error control is based on an automatic repeat request (ARQ) in which whenever any error is detected, the lost or damaged frames are retransmitted. The basic protocols that can be used for error control include stop-and-wait ARQ, Go-back-N ARQ and selective-reject ARQ.

2. Explain the working of stop-and-wait flow control protocol.

Ans: Stop-and-Wait is the simplest protocol used to control the flow of data between a sender and a receiver. As the name implies, the sender sends one frame, then stops and waits for the ACK frame from the receiver to confirm the receipt of the frame. Only after getting an ACK frame from the receiver, the sender sends the next frame (Figure 7.1). In stop-and-wait flow control, the receiver can stop the flow of the data by not sending the ACK frame, thereby keeping the sender in waiting state.

Figure 7.1 Stop-and-Wait Flow Control

Mostly, the sender breaks the large block of data into smaller blocks called frames because sending the message in the larger blocks may increase the transmission time and errors are more likely to occur. In contrast, when message is transmitted in smaller frames, errors may be detected earlier and a smaller amount of data needs to be transmitted. Another reason of breaking into frames may be the limited buffer size of the receiver due to which entire large frame cannot be processed at a single time, thus causing long delays. But the disadvantage of sending small frames for a single message is that stop-and-wait method cannot be used effectively because in this protocol only one frame can be sent at a time (either from sender to receiver or vice versa) which results in underutilization of the communication link.

Link Utilization

To understand the link utilization in stop-and-wait flow control, consider tframe that denotes the time taken in transmitting all bits of a frame and tprop denotes the propagation time from the sender to receiver. Now, the propagation delay (a) which is defined as the time taken by one bit to reach from the sender to receiver can be expressed as

a = tprop/tframe

If a < 1 then tprop< tframe, which implies that the frame is longer enough such that the leading bits of frame reach the receiver before the entire frame is transmitted. That is, link is inefficiently utilized. On the other hand, if a > 1, then tprop > tframe, which implies that the sender has transmitted the entire frame and the leading bits of that frame have still not arrived at the receiver. This results in underutilization of the link.

3. Derive the expression for the maximum possible utilization of link in stop-and-wait flow control.

Ans: Suppose a long message is to be transmitted between two stations. The message is divided into a number of frames F1, F2, F3,…, Fn. The communication between stations proceeds in such a manner that the frames (from station 1) and the ACKs (from station 2) are sent alternatively. That is, initially sender (station 1) sends F1, then receiver (station 2) sends an ACK and then sender sends F2 then receiver sends an ACK and so on.

Now, if Tf denotes the time taken in sending one frame and receiving an ACK, then the total time (T) taken to send the message can be expressed as

T = nTF

where n is the total number of frames and TF can be expressed as

Tf = tprop + tframe + tproc + tprop + tack + tproc

where

tprop is the propagation time from station 1 to station 2.

tframe is the time taken in transmitting all bits of the frame.

tproc is the processing time by each station to respond to an incoming event.

tack is the time to transmit an ACK.

tprop + tframe + tproc is the total time taken by the station 1 to send the frame and getting it processed at the receiver's end and tprop + tack + tproc is the total time taken by the station 2 to send the ACK frame and getting it processed by the sender.

Therefore,                      T = n(tprop + tframe + tproc + tprop + tack + tproc)

Assuming that the processing time is negligible and the ACK frame is very small as compared to the data frame, we can neglect tproc and tack. Thus, T can be written as

T = n(2tprop + tframe)

As n*tframe is the time that is actually involved in sending the frames and rest is considered as overhead, the link utilization (U) may be given as

⇒ U = 1/(1 + 2a)

where a = tprop/tframe = propagation delay.

This is the maximum utilization of the link, which can be achieved in situations where propagation delay (a) is constant and fixed-length frames are often sent. However, due to overhead bits contained in a frame, the actual utilization of the link is usually lower than this.

4. Derive the expression for the propagation delay showing that it is proportional to the bit length of the channel.

Ans: We know, propagation delay (a) = propagation time/transmission time.

Now, propagation time                                                 = d/V

where d is the distance of the link and V is velocity of propagation. For guided media, V = 3*108 m/s and for unguided transmission, V = 0.67 *3*108 (approximately).

Transmission time                                               = L/R

where L is the length of the frame in bits and R is the data rate of transmission. Therefore,

Since, we know that the bit length of channel (B) = Rd/V

                                                                    ⇒ a = B/L

Hence,                                                                 a ∝ B

5. Explain the mechanism of sliding window flow control.

Ans: The sliding window flow control technique was introduced to remove the disadvantage of the stop-and-wait protocol in which only one frame can be transmitted at a time, thus, reducing the efficiency of the link. The efficiency can be greatly improved by using the sliding window flow control protocol as in this technique multiple frames can be sent at the same time.

The mechanism of sliding window protocol is as follows. Let there be two stations, A and B, connected to each other via a full-duplex link. Station B (destination) has buffer space that can accommodate N frames, that is, B can accept N frames at a time, and station A (source) is allowed to send N frames to station B without waiting for any ACKs from B. Each frame is assigned a sequence number that helps to keep track of the frames which have been acknowledged and which have not yet been received. Station B acknowledges each frame by sending a receive-ready (RR) frame that contains the sequence number of the next expected frame. An RR frame from station B indicates to the station A that B is ready to receive next N frames starting with the frame having the sequence number specified within the RR frame. Instead of sending ACK to each frame, the station B can also acknowledge many frames at the same time by sending a single RR frame, that is, acknowledgements are cumulative. For example as shown in Figure 7.2, after receiving frame 3 (F3), station B can hold to send the ACK of the frames 0, 1, 2 and 3 until frame 4 arrives. After frame 3 has arrived, B can send an ACK with the sequence number 4 indicating to A that frames 0, 1, 2 and 3 have been received and now it is expecting to receive frame 4.

At any instant, B can also ask A to stop the flow of frames by sending a receive-not-ready (RNR) message which acknowledges the former frames and indicates the sender not to transmit more frames. For example, an RNR 3 message from B means that it has received all frames up to number 2 and cannot accept any further frames. Later, B must send a normal ACK to A to restart the transmission process.

To keep track of the frames to be sent or received, the sender and receiver maintain a list of sequence numbers called the sender's window and receiver's window (indicated by the boxes in Figure 7.2), respectively. The sender's window indicates the sequence numbers of the frames that the sender can send while the receiver's window indicates the sequence numbers of the frames that the receiver is expecting to receive. For example, in Figure 7.2, the initial window of A and B indicates that A can transmit frames numbered from 0 to 6 without having to wait for any ACK from B and B can receive frames numbered from 0 to 6 from A, respectively. As the frames are sent or received at the sender's and receiver's end respectively, the window size shrinks. For example, after transmitting frames F0, F1, F2 and F3, the size of A's window shrinks to three frames and after receiving frames F0, F1, F2 and F3, the size of B's window shrinks to three frames (Figure 7.2). Similarly, the window size expands as the ACKs are received or sent by the sender and receiver, respectively. Therefore, the scheme is named as sliding window flow control.

Figure 7.2 Sliding Window Flow Control

Notice that at A's end in Figure 7.2, the frames between the vertical line and the box indicate those frames that have been sent but not yet acknowledged by B. Similarly, at B's end, the frames between the vertical line and the box indicate those frames which have been received but not yet acknowledged.

As each sequence number used occupies some field in the frame, the range of sequence number that can be used gets limited. In general, for a k-bit field, the range of sequence number will be from 0 to 2k - 1 and frames will be numbered as modulo 2k. That is, after sequence number 2k - 1, the next number again will be 0. For example, for a 3-bit sequence number, the frames will be numbered sequentially from 0 to 7 and the maximum window size will be 7 (23 – 1). Thus, seven frames can be accommodated in the sender's window and the receiver can also receive a maximum of seven frames at a time.

Link Utilization

In sliding window flow control, the link utilization (U) depends on the window size (N) and propagation delay (a) and is expressed as

6. Define piggybacking. What is its usefulness?

Ans: Usually, the link used between the communicating devices is full duplex and both the sender and receiver need to exchange data. In addition to data, both sender and receiver send ACK for the received data to each other. To improve the efficiency in a two-way transmission, a technique called piggybacking can be employed, which permits an ACK from either device (sender or receiver) to be assembled with the next outgoing data frame from that device instead of sending a separate ACK frame. In case a device has only ACK but no data to send, it needs to use a separate ACK frame. However, if the device has to send the ACK followed by data, it can temporarily withhold the ACK and later, include the ACK in the outgoing data frame.

By temporarily delaying the outgoing ACKs and sending them along with data frames, piggybacking results in better use of the available channel bandwidth. Moreover, by using piggybacking technique, less number of frames needs to be sent which further implies less number of interrupts as well as less number of buffers required at the receiver's end.

7. What is meant by lost frame and damaged frame? List the common techniques of error control method.

Ans: A frame that fails to arrive at the destination node due to noise burst is called lost frame. In this case, the receiver does not know that the frame has been transmitted by the sender. A damaged frame is the frame in which some bits have been changed or altered during the transmission. In case of lost frame, no frame is received by the receiver while in case of damaged frame, a frame is received but not in the exact order.

8. Explain the mechanism of stop-and-wait ARQ.

Ans: Stop-and-Wait ARQ is the extended form of stop-and-wait flow control technique where data frames are retransmitted if the sender does not receive any ACK for the frame. In this method, the sender transmits a single frame and waits for the ACK from the receiver before sending the next frame. The sender cannot transmit a new frame until the ACK is received from the other side. Since either the frame or the ACK can be transmitted at a time, this technique is also known as one-bit sliding window protocol.

Notice that the ACK will not be received by the sender if the frame has been lost during the transmission, that is, it has not been received by the receiver or if the receiver has received the frame free of errors but its ACK has been lost or delayed during the transmission. In both cases, the sender needs to retransmit the frame. For this, the sender maintains a copy of sent data frame in its buffer so that they can be retransmitted whenever required.

To identify the frames to be retransmitted, sequence numbers are attached to the consecutive data frames and ACKs. As only one frame or one ACK can be on the transmission link at a given time, only two numbers 0 and 1 are needed to address the data frames and ACK. Data frames are alternatively numbered 0 and 1, that is, first data frame will be marked as F0, second will be F1, third again will be marked as F0 and so on. The numbers that are attached with ACK indicates the sender to send that numbered data frame. For example, if ACK1 is sent by the receiver, then the sender comes to know that F0 has been received successfully and now, it has to send F1 to the receiver. This process helps the receiver to discard the duplicate frames; however, ACKs need to be sent by the receiver for the duplicate frames also so as to keep the sender in synchronization.

Lost or Damaged Frames

To handle the problem of lost or damaged frames, the sender maintains a timer. Whenever the sender sends a frame, the timer starts. In case the frame is lost during the transmission, the receiver does not send any ACK to that frame. If the sender does not receive any ACK before the time-out (timer expires), it retransmits the same frame after the time-out. On the other hand, if the frame is received by the receiver with errors in it, then the receiver simply discards the frame and sends NACK to the sender indicating the sender to retransmit the same frame.

Lost or Delayed ACKs

Now, consider the case where the receiver receives the frame with no errors and therefore, sends an ACK to the sender but the ACK frame is lost or delayed. In both scenarios, the sender retransmits the same frame after the time-out. This results in the duplication of frames at the receiver's end. To identify the duplicate frames, the receiver maintains a buffer at its end hold those frames for which ACK has been sent.

Link Utilization

The link utilization (U) in the stop-and-wait ARQ is given as

U =(1 - p)/(1+2a)

where

p is the probability of receiving a bit in error

a is the propagation delay which is also equal to (tprop*R)/L where tprop, R and L denotes propagation time, data rate of the link and number of bits in the frame, respectively.

9. What are the two types of sliding window ARQ error control?

Ans: To provide the efficient utilization of the link, the sliding window error control technique is adopted. The sliding window ARQ is also known as continuous ARQ because it allows the sender to send many frames continuously without waiting for an ACK. There are two techniques, namely, Go-back-N ARQ and selective-reject ARQ that are based on the concept of sliding window.

10. Explain the mechanism of Go-back-N ARQ technique.

Ans: Go-back-N ARQ is the most commonly used form of error control that is based on the sliding window flow control. In this technique, the sender sends the data frames depending on its window size but at the receiving end window size is always one. That is, the sender can send many frames without waiting for an ACK from the receiver but the receiver can receive only one frame at a time. For each frame that is received without any error, the receiver acknowledges the frames by sending RR message. However, when it detects error in the frame, it discards that frame and sends a negative acknowledgment reject (REJ) to the sender. The receiver continues to discard the further transmitted frames until the frame in error is received correctly. When the sender receives an REJ, it retransmits the frame in error plus all the succeeding frames that it has sent already.

Figure 7.3 shows the mechanism of Go-back-N ARQ where the sender's window size is seven. That is, the sender can transmit frames F0-F6 to the receiver without waiting for an ACK.

Figure 7.3 Go-Back-N ARQ Mechanism

Lost or Damaged Frames

As shown in Figure 7.4, initially, the sender sends F0, which is received by the receiver. In response the receiver sends RR1 frame to the sender and slides its window to F1–F7. By the time the sender receives RR1, it has transmitted F1 which is either lost or damaged during the transmission. On receiving RR1, the sender transmits F2 and shrinks its window to F3–F7. Though F1 and F2 have been transmitted, the sender stores them in the buffer until they are acknowledged by the receiver. When the receiver receives F2, it accepts F2 and stores in its buffer. It also comes to know that F1 has not arrived. Thus, it sends SREJ1 to the sender to indicate the retransmission of F1. Now, the receiver cannot send RR frame until it receives F1 because sending RR3 would indicate that all frames up to F2 have been received. By the time the sender receives SREJ1, it has transmitted F3 which is accepted by the receiver and kept in the buffer. When sender receives SREJ1, it retransmits frame F1. On receiving F1, the receiver replies with RR4 indicating to the sender that all frames up to F3 have been received successfully. This procedure continues until all the frames have been transmitted.

Figure 7.4 Selective-reject ARQ Mechanism

Lost or Delayed RR or REJ

To understand how lost or delayed RR frame is handled, suppose that the receiver receives F2 frame error free and thus, responds to sender with RR3 which is either lost or delayed. As the sender does not receive any acknowledgement before the time-out, it retransmits F2 after the timer expires. Now, as the receiver has already received F2, it simply ignores F2 thus, avoiding the duplication. However, as the acknowledgements in the Go-back-N method are cumulative, it might be possible that before the timer associated with frame F2 expires, the sender receives next RR frame (that is, RR4) which acknowledges all the previous data frames. In such a case, the sender remains unaware of the fact that RR3 has lost in the network and the operation remain unaffected.

To understand how lost or delayed REJ is handled, suppose that the receiver receives F4 frame with some errors in it. Thus, the receiver discards F4 and transmits REJ4 to the sender, which is either lost or delayed. In both cases, the sender does not receive any further acknowledgements because the receiver will deny accepting any frame other than F4. Thus, the sender has to retransmit F4.

Link Utilization

The link utilization (U) in Go-back-N ARQ method can be considered in the following two situations:

1. When N > 2a + 1, U = (1 - p)/(1 + 2ap) and

2. When N < 2a + 1, U = N(1 - p)/((2a + 1)*(1 – p + Np)).

11. Explain the mechanism of selective-reject ARQ technique.

Ans: Selective-reject ARQ (also known as selective-repeat ARQ) method offers an improvement over Go-back-N by retransmitting only the lost or damaged frame but not all the frames succeeding it. In this method, usually the size of receiver's window is same as that of sender's window and the damaged frames are acknowledged by the receiver by transmitting selective reject (SREJ) frame to the sender. As this method retransmits only lost or SREJ frames, a large buffer needs to be maintained at the receiver's end so that if some frame is not received in proper order then the receiver can accept the rest incoming frames and buffer them until that valid frame has been received. When all the data frames are reached, the receiver arranges all frames in proper sequence and sends them to the next upper layer.

Figure 7.4 shows the selective-reject ARQ mechanism where the window size of both sender and receiver is seven. That is, the sender can transmit frames F0-F6 to the receiver without waiting for an acknowledgement and the receiver can also receive frames F0-F6.

Lost or Damaged Frame

As shown in Figure 7.3, initially, the sender sends F0. As the receiver's window size is 1, the receiver accepts F0 and replies with RR1 to the sender and slides its window to F1. By the time the sender receives RR1, it has transmitted F1 which gets lost in the transmission. At the time the sender receives RR1, it transmits F2 and slides its window from F3 to F7. Though F1 and F2 have been transmitted, the sender stores them in the buffer until they are acknowledged by the receiver. On receiving F2, the receiver finds that F1 is still not received. Therefore, the receiver discards F2 and sends REJ1 to the sender. Before the sender receives REJ1, it transmits F3 which is also discarded by the receiver. When the sender receives REJ1, it needs to retransmit F1, F2 and F3. First it sends F1, which is accepted by the receiver and the receiver responds with RR2 to the sender. This procedure continues until all the frames have been transmitted.

In case the receiver receives a damaged frame, it simply discards the frame and sends REJ to the sender indicating the retransmission of that frame.

Lost or Delayed RR

To understand how lost or delayed RR is handled, suppose that the receiver receives frame F2 and in response sends RR3 which either gets lost or gets delayed. In both cases, when RR4 reaches the sender, the sender assumes it as a cumulative ACK of frames up to F3 and thus, the operation remains unaffected.

Lost or Delayed SREJ

To understand how lost or delayed SREJ is handled, suppose that the receiver receives F4 frame with some errors and thus, sends SREJ4 to the sender, which either gets lost or delayed. To handle this, the receiver maintains a timer at its end, which is started at the time the receiver sends a SREJ frame. If the receiver does not receive the frame F4 before the time-out, it retransmits SREJ4 to the sender after the timer expires. Thus, eventually, the sender receives SREJ4 and retransmits F4.

Link Utilization

The link utilization (U) in selective-reject ARQ can be considered in the following two situations:

1. when N ≥ 2a + 1, U = 1 - p and

2. when N < 2a + 1, U = (N*(1 - p))/(2a + 1).

12. What do you mean by a bit-oriented and byte-oriented protocol?

Ans: In a bit-oriented protocol, the data received from the upper layers whether text, images, audio or video is carried in the form of bits; the data field of each frame comprises a sequence of bits. To distinguish between the consecutive frames, a special eight-bit pattern flag 01111110 is used in the beginning and at the end of each frame. In case the flag bit pattern appears in the data field of frame, bit stuffing is used at the sender's end. After each five consecutive 1s in data, an extra bit 0 (a single bit) is inserted to prevent the bit pattern from looking like a flag. The extra bit stuffed by the sender is then destuffed at the receiver's end. An example of bit-oriented protocol is high-level data link control (HDLC) protocol.

On the other hand, in a byte-oriented (also called character-oriented) protocol, the data received from upper layers is carried in the form of eight-bit characters (that is, bytes) from a coding system such as ASCII. Each frame comprises a sequence of bytes. To distinguish between the consecutive frames, a 1-byte (instead of single bit) flag is used in the beginning and at the end of each frame; the flag is usually composed of special characters depending on the protocol being used. In case the flag byte appears in the data field of frame, byte stuffing (also called character stuffing) is used at the sender's end. An extra byte, called escape character (ESC), is stuffed in the data when there appears a character with the same pattern as flag. The extra byte stuffed by the sender is then destuffed at the receiver's end. An example of byte-oriented protocol is point-to-point (PPP) protocol.

13. Explain in brief HDLC protocol.

Ans: The HDLC is the most commonly used data link protocol developed by ISO. It supports both half-duplex and full-duplex communication lines and switched or non-switched channels. That is why it has been widely implemented throughout the world. It is a bit-oriented protocol that is used to provide communication in point-to-point and multipoint networks. Further, HDLC protocol implements the ARQ mechanism and satisfies a variety of applications. In addition, HDLC defines three types of stations, two types of link configuration and three modes of data transfer to work in various possible network configurations.

Types of stations

Three types of stations defined by HDLC are as follows:

Primary Station: This station has the responsibility of controlling the operation of the link. The frames that are sent by a primary station are called commands.
Secondary Station: This station works under the control of the primary station and the frames that are sent by a secondary station are called responses. Each secondary station on the line is linked with the primary station via a separate logical link. During communication between primary and secondary stations, the primary station is responsible for establishing, managing and terminating the link.
Combined Station: This station can act as both a primary and a secondary station and thus, can send both commands and responses. It does not rely on any other stations on the network and thus, no other station can control a combined station.

Types of Link Configurations

For three stations, two link configurations supported by HDLC are as follows:

Unbalanced Configuration: This type of configuration consists of one primary and one or more secondary stations. Both full-duplex and half-duplex transmissions are possible in unbalanced configuration and the primary station polls each secondary station for input.
Balanced Configuration: This type of configuration consists of two or more combined stations and supports both full-duplex and half-duplex transmissions.

Modes of Data Transfer

Three types of data transfer modes defined by HDLC are as follows:

Normal Response Mode (NRM): This mode of transfer is used with an unbalanced configuration. In this mode, the data transfer is initiated by the primary station to a secondary station. The secondary station is allowed to transmit only in a response to a command from primary station and not by itself. In other words, the secondary station must get an explicit permission from the primary station to send responses.
Asynchronous Balanced Mode (ABM): This mode of transfer is used with a balanced configuration. In this mode, any of the combined stations can start data transmission without the need of any permission from other combined stations. This mode is used widely as it results in an efficient utilization of full-duplex point-to-point link.
Asynchronous Response Mode (ARM): This mode of transfer is used with an unbalanced configuration. In this mode, secondary station may initiate data transfer without needing the permission from the primary station. Despite of this, the primary station is still responsible for link establishment, link disconnection and error recovery. This mode helps to reduce overhead on the link, as no frames need to be sent to provide explicit permission to secondary stations. However, this mode is used only in rare situations where it is necessary for a secondary station to initiate transfer.

14. Explain the frame structure of HDLC.

Ans: The HDLC defines three types of frames, namely, information frames (I-frames),supervisory frames (S-frames) and unnumbered frames (U-frames) to support all modes of data transfer and link configurations. The I-frames are used to carry user data. The ACK of the received frames can also be piggybacked on I-frames. The S-frames do not carry any user data and are used to transport only control information, which cannot be piggybacked on I-frames such as RR, REJ, RNR and SREJ frames. The U-frames are reserved for carrying information regarding management of the link, mode setting or other control information.

Frame Structure

The frame structure of I-frames and U-frames is exactly similar (Figure 7.5) and consists of six fields: starting flag field, an address field, a control field, an information field, a frame check sequence (FCS) field and an ending flag. Since S-frame cannot carry user data, it consists of rest of the five fields excluding the user information field. When multiple frames are transmitted between the communicating stations, then the ending flag field of one frame may act as the starting flag field of the next frame and each frame is transmitted from left to right.

Figure 7.5 Frame Structures in HDLC

The description of the fields in different types of frames in HDLC is as follows:

Flag: It is an eight-bit long field having the unique bit pattern of 01111110. This pattern is used to identify the starting and ending of a frame and the pattern can also be inserted whenever there is some idle time between the consecutive frames. This field serves as a synchronization pattern for the secondary station.
Address: It is usually an eight-bit (1 byte) long field but can be extended up to several bytes depending on the need of the network. This field contains the address of the secondary station irrespective of whether the frame is transmitted by the primary station or the secondary station. If the frame is transmitted by the primary station, then the address field contains a to address and thus, indicates that the frame is a command. If the frame is transmitted by the secondary station then the address field contains a from address and thus, indicates that frame is a response. The last bit of address field always ends with one whether the address field is of one byte or of many bytes. However, if the address field is of more than one byte then the last bit of every intermediate byte ends with a zero indicating to the receiver that there are more address bytes to come.
Control: It is an eight-bit long field that can be extended up to 16 bits. This field identifies the type of HDLC frame and is used for carrying the sequence number, acknowledgements request for retransmission and other control information. The implementation of bits in control field depends on the frame type (discussed in Q15).
Information: It is a variable-length field that contains the user's data bits in I-frame. However, in U-frames, the information field is used to carry system management information.
FCS: It is a 16-bit long field that contains cyclic redundancy check (CRC) for detecting errors in the address, control and information fields. This field can be extended up to 32 bits.

15. Explain the format of control field in all types of frames in HDLC.

Ans: The HDLC defines three types of the frames I, S and U and the control field of each frames differs from each other. This field comprises various subfields (Figure 7.6) that define the functions associated with the frame.

Control Field for I-frame

The first bit of the control field specifies the type of the frame. For an I-frame, this bit is always set to zero. The next three bits comprise N(S) subfield that defines the sequence number of the frame. As three bits are defined for sequence number, the frames can be numbered from 0 to 7. However, if the extended frame format in which the control field is of 16-bits is used then N(S) field becomes larger. The next single bit after N(S) is the P/F bit where P stands for poll and F stands for final. If P/F bit is set to one, it means poll, that is, frame has been sent by a primary station to a secondary station. On the other hand, if P/F bit is zero, it means final, that is, frame has been sent by a secondary station to the primary station. The last three bits in control field comprise the N(R) subfield that defines an ACK number corresponding to received frame, which has been piggybacked on the I-frame.

Figure 7.6 Control Field Format for HDLC Frame Types

Control Field for S-frame

In an S-frame, the first two bits of the control field define the type of the frame. For an S-frame, these bits are always set to 10. Since an S-frame carries control information, the next two bits of the control field, called code, indicate the type of control information being carried in an S-frame. There can be four possible combinations of two bits and accordingly, four types of ACKs that an S-frame may carry. These types are as follows:

Receive Ready (RR): If the value of code is 00, then the frame is an RR S-frame. This kind of frame sends the ACK to the sender for a frame or a group of frames that have been received.
Receive not Ready (RNR): If the value of code is 10, then the frame is an RNR S-frame. This kind of frame is similar to RR frame, however, includes some additional features. In addition to acknowledging the frames, it also asks the sender to slow down or not to send any more frames as the receiver is busy.
Reject (REJ): If the value of the code is 01, then the frame is an REJ S-frame. This kind of frame is used in Go-back-N ARQ to inform the sender about the loss or damage of the received frame before the sender's timer expires.
Selective-Reject (SREJ): If the value of the code is 11, then the frame is an SREJ S-frame. This kind of frame is used in selective-repeat ARQ to inform the sender about the loss or damage of a specified frame before the sender's timer expires.

The next single bit after code bits is P/F bit having the same purpose as in I-frame and the last three bits comprise N(R) subfield that defines positive ACK number or NACK depending on the type of S-frame.

Control Field for U-Frame

In U-frame, the first two bits specify the type of the frame. For a U-frame, these bits are always set to 11. The next two bits before the P/F bit and the last three bits following the P/F bit correspond to the code bits in the control field. These five code bits together can create up to 32 different types of U-frames.

16. Describe the frame structure of SDLC. How HDLC frame format is superior to SDLC frame format?

Ans: Synchronous Data Link Control (SDLC) is a data link layer protocol that is widely used by IBM. It is a subset of HDLC protocol with some minor additional features. The frame structure of SDLC (Figure 7.7) is somewhat similar when compared with the HDLC frame structure. The description of various fields used in SDLC is as follows:

Flag: It is an eight-bit long field having the unique bit pattern of 01111110. The same bit pattern is also used for the last field in the frame. The flag field in the beginning of the frame is used for synchronization while the flag field at the end is used to indicate the end of frame.
Address: It is an eight-bit long field that is used to carry the address of the secondary station.
Control: It is an eight-bit long field that is used to carry the sequence number of frames. The implementation of control field depends on the frame type and can be extended up to 32 bits.
Data: It is a variable-length field that is used to carry user's data.
Error Checking Field (ECF): It is a 16-bit long field that is used for the error control.

The HDLC frame format is superior to SDLC frame format because in HDLC, FCS field can be of 32-bits but in SDLC, it is limited to 16-bit only.

Figure 7.7 SDLC Frame Format

17. Describe the services provided by the PPP protocol. Also, list some services which PPP does not provide.

Ans: The PPP protocol operates over a link, which directly connects two nodes, one on each end of the link. Thus, PPP is the most commonly used data link layer protocol for PPP access. This protocol is used by several users who need to connect their home computers with the server of ISP. The PPP protocol can control and manage the transfer of the data, which a modem was unable to provide. That is why PPP has become the popular choice among users accessing Internet over a dial-up connection.

PPP provides a wide variety of services, some of which are as follows:

It can operate over various types of links such as serial/parallel, synchronous/asynchronous, etc.
It defines the format of frames that are exchanged between the communicating nodes.
It defines how link should be established between two nodes and how data should be exchanged.
It defines authentication mechanism to be used by the communicating devices to authenticate each other.
It provides a mechanism for the communicating nodes to learn the network layer address of each other.
It supports many network layer protocols such as IP and DECnet.
It can detect the errors in the received frames.

In order to keep PPP simple, some services have not been implemented in PPP. These services are as follows:

It does not concern about flow control. However, it provides error control to some extent. It enables to detect errors; however, the errors cannot be corrected.
It operates only where there is single sender and single receiver. Thus, cannot be used over multipoint links.
It does not support frame sequencing, thus, frames are delivered to the destination not necessarily in the same order in which they were sent by the sender.

18. Explain the frame format of the PPP.

Ans: The PPP is a byte-oriented protocol and uses an HDLC like frame format (Figure 7.8). The description of each field in PPP frame is as follows:

Flag: It is a one-byte long field having the unique pattern of 01111110. This unique pattern is inserted at the start and end of each PPP frame. Though the flag field in PPP uses the same bit pattern as that of HDLC, the flag is treated as a byte in PPP.
Address: It is a one-byte long field that is set to a constant value of 11111111, which means a broadcast address. This byte can be omitted upon an agreement between two parties during negotiation.
Control: It is a one-byte long field that is set to a constant value of 00000011, which indicates an unnumbered frame. This implies that PPP does not use sequence numbers and ACKs and thus, does not provide reliable transmission. Though PPP does not provide flow control and error control is also limited to error detection only, the control field can also be omitted if both parties agree to do so during negotiation.
Protocol: It is a two-byte long field that defines what is being carried in the payload field, that is, user data or some other information. Only one byte of this field can be used if both parties agree during negotiation.
Payload: It is a variable-length field containing either the user data or other information in the form of sequence of bytes. The default maximum length of payload field is 1,500 bytes; however, two parties can negotiate on this maximum length. If the flag byte appears in the data in payload field, the data is byte stuffed. In case the size of payload field is less than 1,500 bytes or the maximum negotiated value, padding is required.
FCS: It is a two-byte or four-byte long field that is used to detect errors in the transmitted frame. This two- or four byte is simply a CRC.

Figure 7.8 PPP Frame Format

19. Explain all the transition phases of PPP.

Ans: A PPP connection transits through various phases while configuring, maintaining, and terminating the PPP link (Figure 7.9). These phases are described as follows:

Dead: This is the initial phase of protocol, which means the line is quiet and no physical layer connection exists. When an event such as a physical carrier detection occurs, the connection goes into establishment phase. The PPP protocol always begins and ends with this phase.
Establish: In this phase, one of the nodes starts the communication and negotiations are made between the communicating nodes. The link control protocol (LCP) packets and several other packets are exchanged between the nodes if the negotiation is successful. With this, the connection transits to authenticate phase. Notice that if authentication is not required, the connection directly switches to network phase.
Authenticate: This is an optional phase that can be skipped upon an agreement between both nodes during the negotiation in the establishment phase. If both parties agree to undergo this phase then several authenticate protocols are used by the communicating nodes to verify each other's identity. If the authentication becomes successful, then the connection moves to the network phase else it goes to the terminate phase.
Network: In this phase, two nodes negotiate on the network layer protocol that should be used so that the data can be received. As PPP supports multiple protocols and many protocols may run simultaneously at the network layer, the receiver node should negotiate with the sender node on a common protocol to be used for exchanging the data at the network layer. After the protocol has been decided, the connection switches to open phase.
Open: In this phase, data packets are exchanged between the communicating nodes. The connection remains in this phase until one of the nodes wants to close the connection.
Terminate: In this phase, the connection link is closed and the nodes now cannot transfer any data packets between themselves. Certain packets are exchanged between two nodes for house cleaning the connection and then the link is terminated. After this, the connection goes to dead phase.

Figure 7.9 Transition Phases of PPP

20. Write a short note on LCP and NCP.

Ans: The link control protocol (LCP) and network control protocol (NCP) are the PPP protocols that are used to establish the link, authenticate the communicating nodes and move the network layer data.

Link Control Protocol

This protocol has the responsibility of establishing, configuring, maintaining and terminating the link. The link can be established when both the communicating nodes agree on certain options. For this, LCP provides the negotiation mechanism. Each LCP packet is encapsulated in the payload field of PPP frame and a value 0xC021 (hexadecimal) is placed in the protocol field of PPP frame to indicate that PPP is carrying an LCP frame (Figure 7.10).

Figure 7.10 LCP Packet Encapsulated into PPP Frame

The frame structure of LCP consists of various subfields, which are described as follows:

Code: It is a one-byte long field that defines the type of LCP packet. There are 11 types of LCP packets that are divided into three categories. The first category includes four packets and is used to configure the link during the establishment phase. The second category includes two packets that are used to terminate the connection. The third category includes five packets that are used to debug and monitor the link.
ID: It is a one-byte long field that contains a value to match a request with a reply. When one node sends the data to another node then the sender node inserts a value in the ID field, which is then copied by the receiver and placed into the reply packet to be transmitted.
Length: It is a two-byte long field that defines the length of the whole LCP packet.
Information: It is a variable length field, which carries options like authentication protocol, payload field size, etc. These options can be negotiated between the two communicating nodes.

Network Control Protocol

PPP supports multiple network layer protocols defined by OSI, Novel, DECnet and Xerox. To carry a network layer data packet from these protocols, PPP has defined an NCP for each network layer protocol. The NCP consists of a set of protocols that encapsulate the data received from the network layer protocols into the PPP frame. The NCP also configures the link at the network layer. Like LCP, each NCP packet is also included in the payload field of PPP frame and the protocol field of PPP is set to a value 0x8021 (hexadecimal) which indicates that PPP frame is carrying the NCP packet.

21. Explain two authentication protocols that are used in PPP.

Ans: As PPP is used over point-to-point link, authentication is important between the communicating nodes for the effective transmission of resources. The PPP uses two protocols, namely, password authentication protocol (PAP) and challenge handshake authentication protocol (CHAP) for the verification of user identity during the authentication phase.

Password Authentication Protocol

PAP uses three types of packets for authentication, namely, authenticate-request, authenticate-ack and authenticate-nak. A node that wishes to access the system uses authentication-request packet to send its username and password to the system. After receiving authentication-request packets, the system checks the validity of username and password. If the requesting node is validated, the system sends an authenticate-ack packet to the node indicating that access is allowed. However, if the node is not validated, then the system sends an authenticate-nak packet indicating that access is denied. Whenever a PAP packet is being carried in a PPP frame, the protocol field of PPP frame is set to a value 0xC023 (hexadecimal).

Challenge Handshake Authentication Protocol

This is a three-way handshaking authentication protocol. It uses four packets, namely, challenge, response, success and failure. The system sends a challenge packet containing a challenge value to the user needing access to the system. The user retrieves the challenge value from the challenge packet and inputs this value along with its password to a predefined function to generate an output. The user encapsulates the output obtained in the response packet and sends it to the system. The system also applies the same function on the challenge value and the user's password. If the output obtained is same as the output received in the response packet, the user is validated. The system sends a success packet to the user indicating that the access is granted. Otherwise, the system sends a failure packet indicating that the access is denied. Whenever a CHAP packet is being carried in a PPP frame, the protocol field of PPP frame is set to a value 0xC233 (hexadecimal).

Further, CHAP provides more security as compared to PAP as it prevents the need of sending the password online. In case an intruder gets access to the challenge value and the output in the response packet, he/she cannot know the password. That is, password always remains secret.

22. Why CRC is always added in trailer and not in the header of all data link protocols?

Ans: All data link protocols comprise a CRC field that stores the checksum for error detection and correction. The CRC is calculated over all the bits that are needed to be transmitted to the destination node and added to the trailer of the outgoing data stream as soon as the last bit is transmitted. If CRC is to be attached in the header part of the data stream, then CRC has to be calculated before the transmission of the frame. This would result in more overhead as each byte of frame needs to be handled twice, once for computing CRC and then for transmission. On the other hand, when CRC is put in the trailer, each byte of frame needs to be handled only once, resulting in less overhead. That is why CRC is added in the trailer and not in the header of data link protocols.

23. A channel has a bit rate of 4 kbps and propagation delay of 20 msec. For what frame size does stop and wait gives an efficiency of at least 50%.

Ans: Given, propagation delay, a = 20 msec

Bit rate, R = 4 kbps = 4 × 103s

Let L denotes the size of frame, then transmission time of a frame (tframe) can be given as

The maximum link utilization (U) can be given as

Given U ≥ 50%

From Eqs (1) and (2), we have

Thus, for achieving at least 50% efficiency, the frame size should be at least 160 bits.

24. If the window size is 15, give the sequence number of frames in Go-back-N ARQ and selective-repeat ARQ.

Ans: In Go-back-N ARQ, the maximum window size is equal to 2m – 1 where m is the number of bits in the frame sequence number and the frame sequence numbers range from 0 to 2m – 1. Here, given that

2m – 1 = 15

⇒2m = 16

Thus, the sequence numbers range from 0 to 15.

In selective repeat ARQ, the maximum window size is equal to 2m–1 and the frame sequence numbers range from 0 to 2m – 1. Here, given that

2m–1 = 15

⇒2m = 30

Thus, the sequence numbers range from 0 to 29.

25. A channel has a bit rate of 20 kbps. The stop-and-wait protocol with a frame size of 4,500 bits is used. The delay for error detection and sending ACK by the receiver is 0.25 seconds because of a fault. Find the maximum efficiency of the channel if the destination is 30,000 km away and the speed of the propagation of the signal is 2.8 ×108m/s. Find the decrease in efficiency due to the fault.

Ans: Given, bit rate (R) = 20 kbps = 20 × 103 bps

Frame size (L) = 4,500 bits

Distance between sender and receiver (d) = 30,000 km = 30,000 × 103 m

Propagation speed (V) = 2.8 × 108 m/s

Now, the frame transmission time (tframe) can be computed as

                                                  tframe = L/R

                                                       = 4,500/(20 × 103) = 0.225 s

The propagation delay (a) can be computed as

                                  a = Rd/VL

                                     = (20 × 103 × 30,000 × 103) / (2.8 × 108 × 4500)

                                     = 0.4761

Now, the maximum utilization (with ignoring the fault) can be computed as

                                               Umax = 1/(1 + 2a)

                                                        = 1/(1 = 2 × 0.4761)

                                                         = 0.512 = 51.2%

If we consider the fault, the time taken in sending each frame and receiving its ACK will be increased by 0.25 s. Thus, the total time spent in sending all the frames (say, n) can be given as

T = n*(2tprop + tframe + 0.25)

The link utilization (in case of fault) can be given as

The decrease in efficiency (in %) due to fault = ((UmaxUfault)/Umax)*100

                                                  = ((0.512 – 0.326)/0.512)*100

                                                  = 36.3%

Multiple Choice Questions

  1. Propagation delay is inversely proportional to________.

    (a) distance of the link

    (b) data rate of transmission

    (c) length of the frame

    (d) none of these

  2. When data and ACK are sent on the same frame, this is called________.

    (a) piggybacking

    (b) backpacking

    (c) piggypacking

    (d) forwarding and backing

  3. A frame that fails to arrive at the destination node due to noise burst is called___________.

    (a) damaged frame

    (b) transmission frame

    (c) undamaged frame

    (d) lost frame

  4. The link utilization (U) in stop-and-wait ARQ is expressed as

    (a) (1 + P)/(1 + a)

    (b) (1 + P)/(1 + 2a)

    (c) (1 – P)/(1 + 2a)

    (d) (1 – P)/(1 + a)

  5. In Go-back-N ARQ, if frames 3, 4 and 5 are received successfully, which ACK number may be sent to the sender?

    (a) 5

    (b) 6

    (c) 7

    (d) 8

  6. ABM in HDLC stands for_______.

    (a) asynchronous balanced mode

    (b) asynchronous balanced modem

    (c) asynchronous bisync mode

    (d) asynchronous bus modem

  7. The shortest frame in HDLC protocol is usually the_________.

    (a) information frame

    (b) supervisory frame

    (c) unnumbered frame

    (d) control frame

  8. The maximum number of unconfirmed frames that can be outstanding at any one time with SDLC is___________.

    (a) 4

    (b) 7

    (c) 8

    (d) 14

  9. PPP is a______-oriented protocol.

    (a) bit

    (b) byte

    (c) both (a) and (b)

    (d) none of these

  10. 10. If you connect to the Internet from your home computer, chances are that you are using:_________.

    (a) PPP

    (b) NCP

    (c) DAP

    (d) FTAM

Answers

1. (c)

2. (a)

3. (d)

4. (c)

5. (b)

6. (a)

7. (b)

8. (a)

9. (b)

10. (a)