In the data link layer, the term error control refers primarily to methods of error detection and retransmission.
Automatic Repeat Request (ARQ)
Error correction in the data link layer is implemented simply: anytime an error is detected in an exchange, a negative acknowledgment (NAK) is returned and the specified frames are retransmitted. This process is called automatic repeat request (ARQ).
It sometimes happens that a frame is so damaged by noise during transmission that the receiver does not recognize it as a frame at all. In those cases, ARQ allows us to say that the frame has been lost. A second function of ARQ is the automatic retransmission of lost frames, including lost ACK and NAK frames (where the loss is detected by the sender instead of the receiver).
ARQ error control is implemented in the data link layer as an adjunct to flow contro1. In fact, stop-and-wait flow control is usually implemented as stop-and-wait ARQ and sliding window is usually implemented as one of two variants of sliding window ARQ, called go-back-n or selective-reject (see Figure 8.3-1).
Stop-and-wait ARQ is a form of stop-and-wait flow control extended to include retransmission of data in case of lost or damaged frames. For retransmission to work, four features are added to the basic flow control mechanism:
• The sending device keeps a copy of the last frame transmitted until it receives an acknowledgment for that frame. Keeping a copy allows the sender to retransmit lost or damaged frames until they are received correctly.
• For identification purposes, both data frames and ACK frames are numbered alternately 0 and l. A data l frame is acknowledged by an ACK l frame, indicating that the receiver has gotten data l and is now expecting data 0. This numbering allows for identification of data frames in case of duplicate transmission (important in the case of lost acknowledgment, as we will see below).
If an error is discovered in a data frame, indicating that it has been corrupted in transit, a NAK frame is returned. NAK frames, which are not numbered, tell the sender to retransmit the last frame sent. Stop-and-wait ARQ requires that the sender wait until it receives an acknowledgment for the last frame transmitted before it transmits the next one. When the sending device receives a NAK, it resends the frame transmitted after the last acknowledgment, regardless of number.
The sending device is equipped with a timer. If an expected acknowledgment is not received within an allotted time period, the sender assumes that the last data frame was lost in transit and sends it again.
When a frame is discovered by the receiver to contain an error, it returns a NAK frame and the sender retransmits the last frame. For example, in Figure 8.3-2, the sender transmits a data frame: data 1. The receiver returns an ACK 1, indicating that data l arrived undamaged and it is now expecting data 0. The sender transmits its next frame: data 0. It arrives undamaged, and the receiver returns ACK 0. The sender transmits its next frame: data l. The receiver discovers an error in data land returns a NAK. The sender retransmits data l. This time data l arrives intact, and the receiver returns ACK 1.
Any of the three frame types can be lost in transit.
Lost Data Frame Figure 8.3-3 shows how stop-and-wait ARQ handles the loss of a data frame. As noted above, the sender is equipped with a timer that starts every time a data frame is transmitted. If the frame never makes it to the receiver the receiver can never acknowledge it, positively or negatively. The sending device waits for m ACK or NAK frame until its timer goes off, at which mint it tries again. It retransmits the last data frame, restarts its timer, and waits for an acknowledgment.
Figure 8.3-3 Stop-and-wait ARQ, lost data frame
Figure 8.3-3 Stop-and-wait ARQ, lost data frame
Lost Acknowledgment In this case, the data frame has made it to the receiver and been found to be either acceptable or not acceptable. But the ACK or NAK frame returned by the receiver is lost in transit. The sending device waits until its timer goes off, and then retransmits the data frame. The receiver checks the number of the new data frame. If the lost frame was a NAK, the receiver accepts the new copy and returns the appropriate ACK (assuming the copy arrives undamaged). If the lost frame was an ACK, the receiver recognizes the new copy as a duplicate, acknowledges its receipt, then discards it and waits for the next frame (see Figure 8.3-4).
Sliding Window ARQ
Among the several popular mechanisms for continuous transmission error control, two protocols are the most popular: go-back-n ARQ and selective-reject ARQ, both based on sliding window now control. To extend sliding window to cover retransmission of lost or damaged frames, three features are added to the basic flow control mechanism:
• The sending device keeps copies of all transmitted frames until they have been acknowledged. If frames 0 through 6 have been transmitted, and the last acknowledgment was for frame 2 (expecting 3), the sender keeps copies of frames 3 through 6 until it knows that they have been received undamaged.
• In addition to ACK frames, the receiver has the option of returning a NAK frame if the data have been received damaged. The NAK frame tells the sender to retransmit a damaged frame. Because sliding window is a continuous transmission mechanism (as opposed to stop-and-wait), both ACK and NAK frames must be numbered for identification. ACK frames, you will recall, carry the number of the next frame expected. NAK frames, on the other hand, carry the number of the damaged frame itself. In both cases, the message to the sender is the number of the frame that the receiver expects next. Note that data frames that are received without errors do not have to be acknowledged individually. If the last ACK was numbered 3, an ACK 6 acknowledges the receipt of frames 3 and 4 as well as frame 5. Every damaged frame, however, must be acknowledged. If data frames 4 and 5 are received damaged, both NAK 4 and NAK 5 must be returned. However, a NAK 4 tells the sender that all frames received before data 4 have arrived intact.
• Like stop-and-wait ARQ, the sending device in sliding window ARQ is equipped with a timer to enable it to handle lost acknowledgments. In sliding window ARQ, n-1 frames (the size of the window) may be sent before an acknowledgment must be received. If n-1 frames are awaiting acknowledgment, the sender starts a timer and waits before sending any more. If the allotted time has run out with no acknowledgment, the sender assumes that the frames were not received and retransmits one or all of the frames depending on the protocol. Note that as with stop-and-wait ARQ, the sender here has no way of knowing whether the lost frames are data, ACK, or NAK frames. By retransmitting the data frames two possibilities are covered: lost data and lost NAK. If the lost frame was an ACK frame, the receiver can recognize the redundancy by the number on the frame and discard the redundant data.
In this sliding window go-back-n ARQ method, if one frame is lost or damaged, all frames sent since the last frame acknowledged is retransmitted.
Damaged Frame What if frames 0,1,2, and 3 have been transmitted, but the first acknowledgment received is a NAK 3? Remember that a NAK means two things: (1) a positive acknowledgment of all frames received prior to the damaged frame, and (2) a negative acknowledgment of the frame indicated. If the first ackflowledgment is a NAK 3, it means that data frames 0, l, and 2 were all received in good shape. Only frame 3 must be resent.
What if frames 0 through 4 have been transmitted before a NAK is received for frame 2? As soon as the receiver discovers an error, it stops accepting subsequent frames until the damaged frame has ken replaced correctly. In the scenario above, data 2 arrives damaged and so is discarded, as are data 3 and data 4 whether or not they have arrived intact. Data 0 and data l, which were received before the damaged frame, have already been accepted, a fact indicated to the sender by the NAK 2 frame. The retransmission therefore consists of frames 2,3, and 4.
Figure 8.3-5 gives an example where six frames have been transmitted before an error is discovered in frame 3. In this case, an ACK 3 has been returned, telling the sender that frames 0, l, and 2 have all been accepted. In the figure, the ACK 3 is sent before data 3 has arrived. Data 3 is found damaged, so a NAK 3 is sent immediately and frames 4 and 5 are discarded as they come in. The sending device retransmits all three frames (3, 4, and 5) sent since the last acknowledgment, and the process continues. The receiver continues to discard frames 4 and 5 (as well as any subsequent frames) until it receives a good data 3.
Lost Data Frame Sliding window protocols require that data frames be transmitted sequentially. If one or more frames are so noise corrupted that they become lost in transit, the next frame to arrive at the receiver will be out of sequence. The receiver checks the identifying number on each frame, discovers that one or more have been skipped, and returns a NAK for the first missing frame. A NAK frame does not indicate whether the frame has been lost or damaged, just that it needs to be resent. The sending device then retransmits the frame indicated by the NAK, as well as any frames that it had transmitted after the lost one.
In Figure 8.3-7, data 0 and data l arrive intact but data 2 is lost. The next frame to arrive at the receiver is data 3. The receiver is expecting data 2 and so considers data 3 to be an error, discards it, and returns a NAK 2, indicating that 0 and l have been accepted but 2 is in error (in this case lost). In this example, because the sender has transmitted data 4 before receiving the NAK 2, data 4 arrives at the destination out of sequence and is therefore discarded. Once the sender receives the NAK 2, it retransmits all three pending frames (2, 3, and 4).
Figure 8.3-7 (io-back-n, lost data frame
Figure 8.3-7 (io-back-n, lost data frame
Lost Acknowledgment The sender is not expecting to receive an ACK frame every data frame it sends. It cannot use the absence of sequential ACK numbers to identify lost ACK or NAK frames. Instead, it uses a timer. The sending device can send as many frames as the window allows before waiting for an acknowledgment. Once that limit has been reached or the sender has no more frames to send, it must wait. If the ACK (or, especially, if the NAK) sent by the receiver has ken lost, the sender could wait forever. To avoid tying up both devices, the sender is equipped with a timer that begins counting whenever the window capacity is reached. If an acknowledgment has not been received within the time limit, the sender retransmits every frame transmitted since the last ACK.
Figure 8.3-8 shows a situation in which the sender has transmitted all of its frames and is waiting for an acknowledgment that has been lost along the way. The sender waits a predetermined amount of time, and then retransmits the unacknowledged frames. The receiver recognizes that the new transmission is a repeat of an earlier one, sends another ACK, and discards the redundant data.
In selective-reject ARQ, only the specific damaged or lost frame is retransmitted. If a frame is corrupted in transit, a NAK is returned and the frame is resent out of sequence. The receiving device must be able to sort the frames it has and insert the corrected frame into its proper place in the sequence. To make such selectivity possible, a selective-reject ARQ system differs from a go-back-n ARQ system in the following ways:
The receiving device must contain sorting logic to enable it to reorder frames received out of sequence. It must also be able to store frames received after a NAK has ken sent until the damaged frame has been replaced.
The sending device must contain a searching mechanism that allows it to find and select only the requested frame for retransmission.
A buffer in the receiver must keep ail previously received frames on hold until all retransmissions have been sorted and any duplicate frames have been identified and discarded.
To aid selectivity, ACK numbers, like NAK numbers, must refer to the frame received (or lost) instead of the next frame expected.
•This complexity requires a smaller window size than is needed by the go-back-n method if it is to work efficiently. It is recommended that the window size be less than or equal to (n+l)/2, where n-l is the go-back-n window size.
Damaged Frames Figure 8.3-9 shows a situation in which a frame is received in error. As you can see, frames 0 and l are received but not acknowledged. Data 2 arrives and is found to contain an error, so a NAK 2 is returned. Like NAK frames in go-back-n error correction, a NAK here acknowledges both the intact receipt of any previously unacknowledged data frames and indicates an error in the current frame. In the figure, NAK 2 tells the sender that data 0 and data 1 have been accepted, but that data 2 must be resent. Unlike the receiver in a go-back-n system, however, the receiver in a selective-reject system continues to accept new frames while waiting for an error to be corrected. However, because an ACK implies the successful receipt not only of the specific frame indicated but of all previous frames, frames received after the error frame cannot be acknowledged until the corrected frame has been received. In the figure, the receiver accepts data 3,4, and 5 while waiting for a new copy of data 2. When the new data 2 arrives, an ACK 5 can be returned, acknowledging the new data 2 and the original frames 3, 4, and 5. Quite a bit of logic is required by the receiver to sort out-of-sequence retransmissions and to keep track of which frames are still missing and which have yet to be acknowledged.
Was this article helpful?
Read how to maintain and repair any desktop and laptop computer. This Ebook has articles with photos and videos that show detailed step by step pc repair and maintenance procedures. There are many links to online videos that explain how you can build, maintain, speed up, clean, and repair your computer yourself. Put the money that you were going to pay the PC Tech in your own pocket.