hamburger

Flow and Error Control Important Techniques and best Study Notes.

By BYJU'S Exam Prep

Updated on: September 25th, 2023

‘Flow & Error Control Techniques’ is one of the important topics of Computer Networks for GATE and other Computer Science Engineering exams.
Flow & Error Control Techniques notes for Computer Science Engineering will help you understand the concept of the computer networks needed for GATE and other Computer Science engineering exams. Every year, 6 to 7 questions come from computer networks in the exam.
This note will help you prepare for various engineering exams such as GATE CS / BARC/ ISRO and other important competitive exams.

Flow Control: Flow control coordinates the amount of data that can be sent before receiving an acknowledgment.

  • It is one of the most important duties of the data link layer.
  • Flow control tells the sender how much data to send.
  • It makes the sender wait for some sort of acknowledgment (ACK) before continuing to send more data.
  • Flow Control Techniques: Stop-and-wait, and Sliding Window

Error Control: Error control in the data link layer is based on ARQ (automatic repeat request), which is the retransmission of data.

  • The term error control refers to methods of error detection and retransmission.
  • Every time an error is detected in an exchange, specified frames are retransmitted. This process is called ARQ.

To ensure reliable communication, there needs to exist flow control (managing the amount of data the sender sends), and error control (that data arrives at the destination error-free).

  • Flow and error control needs to be done at several layers.
  • For node-to-node links, flow and error control is carried out in the data-link layer.
  • For end-point to end-point, flow and error control is carried out in the transport layer.

Flow & Error control:

  • Error Detection and ARQ (error detection with retransmissions) must be combined with methods that intelligently limit the number of ‘outstanding’ (unpacked) frames.
  • Flow & Error control techniques: Stop-and-Wait ARQ, Go-Back-N ARQ, and Selective Repeat ARQ

Flow Control Techniques:  

  • One important aspect of the data link layer is flow control.
  • Flow control refers to a set of procedures used to restrict the amount of data the sender can send before waiting for an acknowledgement.

image005

Stop and Wait for Flow control:
  • The sender has to wait for an acknowledgment of every frame that it sends.
  • Only when an acknowledgment has been received is the next frame sent. This process continues until the sender transmits an End of Transmission (EOT) frame.
  • In Stop-and-Wait flow control, the receiver indicates its readiness to receive data for each frame.

slidingwindow

  • For every frame that is sent, there needs to be an acknowledgement, which takes a similar amount of propagation time to get back to the sender.
  • Only one frame can be in transmission at a time. This leads to inefficiency if propagation delay is much longer than the transmission delay
  • Advantages of Stop and Wait:
    • It’s simple and each frame is checked and acknowledged well.
  • Disadvantages of Stop and Wait:
    • Only one frame can be in transmission at a time.
    • It is inefficient if the distance between devices is long. The reason is propagation delay is much longer than the transmission delay.
    • The time spent for waiting acknowledgements between each frame can add a significant amount to the total transmission time.

Sliding Window Flow Control:

  • It works by having the sender and receiver have a “window” of frames.
  • Each frame has to be numbered in relation to the sliding window. For a window of size n, frames get a number from 0 to n – 1.  Subsequent frames get a number mod n.
  • The sender can send as many frames as would fit into a window.
  • The receiver, upon receiving enough frames, will respond with an acknowledgement of all frames up to a certain point in the window. It is called slide.
  • This window can hold frames at either end and provides the upper limit on the number of frames that can be transmitted before requiring an acknowledgement.
  • For example, if n = 8, the frames are numbered 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1…so on. The size of the window is (n -1) = 7.
  • When the receiver sends an ACK, it includes the number of the next frame it expects to receive. When the receiver sends an ACK containing the number 5, it means all frames upto number 4 have been received.
  • If the window size is sufficiently large the sender can continuously transmit packets:
    • If W >= (2a+1), sender can transmit continuously. (Efficiency =1)
    • If W < (2a+1), sender can transmit W frames every (2a+1) time units. (Efficiency = W/(1+2a) )

Error Control Techniques:

  • Many factors including line noise can alter or wipe out one or more bits of a given data unit.

image001

  • Reliable systems must have mechanisms for detecting and correcting such errors.
  • Error detection and correction are implemented either at the data link layer or the transport layer of the OSI model.

Error Detection

  • Error detection uses the concept of redundancy, which means adding extra bits for detecting errors at the destination.

image002

  • The checking function performs the action that the received bitstream passes the checking criteria, the data portion of the data unit is accepted else rejected.

Vertical Redundancy Check (VRC)

  • In this technique, a redundant bit, called a parity bit, is appended to every data unit, so that the total number of 1’s in the unit (including the parity bit) becomes even.
  • If a number of 1’s are already even in data, then the parity bit will be 0.

image003

  • Some systems may use odd parity checking, where the number of 1’s should be odd. The principle is the same, the calculation is different.

Checksum

  • There are two algorithms involved in this process, checksum generator at sender end and checksum checker at receiver end.
  • The sender follows these steps
    • The data unit is divided into k sections each of n bits.
    • All sections are added together using 1’s complement to get the sum.
    • The sum is complemented and becomes the checksum.
    • The checksum is sent with the data.
  • The receiver follows these steps
    • The received unit is divided into k sections each of n bits.
    • All sections are added together using 1’s complement to get the sum.
    • The sum is complemented.
    • If the result is zero, the data are accepted, otherwise, they are rejected.

Limitation of checksum:

  • It is not possible to detect the vertical error from the data which is received at receivers end.
  • If noise modify the data in such a way that vertically placed bits can cancel the change made to them then calculated checksum will always be same as received checksum. Such errors cannot be detected and they are known as vertical errors.

Cyclic Redundancy Check (CRC):

  • CRC is based on binary division.
  • A sequence of redundant bits called CRC or the CRC remainder is appended to the end of a data unit, so that the resulting data unit becomes exactly divisible by a second, predetermined binary number.
  • At its destination, the incoming data unit is divided by the same number. If at this step there is no remainder, the data unit is assumed to be intact and therefore is accepted.

Selection Criteria for CRC generator:

  • Generator shiould be of more than 1 bit.
  • when x is part of our generator, than it will detect all the errors. So for a generator to detect all type of errors, it should not contain x.
  • if generator contains x+1, then all the odd bit errors are detected.
  • A good generator always contain x other it will bw multiple of x.
  • CRC 32 will always detect all type of errors in the network. it is considered as ideal network detector.

 

Error Correction:

  • Error correction in data link layer is implemented simply anytime.
  • An error is detected in an exchange, a negative acknowledgement NAK is returned and the specified frames are retransmitted. This process is called Automatic Repeat Request (ARQ).
  • Retransmission of data happens in three Cases: Damaged frame, Lost frame and Lost acknowledgement.

Flow and Error Control Techniques (ARQ schemes):

image004

Stop and Wait ARQ:

  • Include re-transmission of data in case of lost or damaged framer.
  • It is addition to the basic flow control mechanism with re-transmissions.
  • (i) Sender sends an information frame to receiver.
  • (ii) Sender waits for an ACK before sending the next frame.
  • (iii) Receiver sends an ACK if frame is correctly received.
  • (iv) If no ACK arrives within time-out, sender will resend the frame.

Time-out period > Rround trip time

  • 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 numbered, tell the sender to retransmit the last frame sent.
  • Piggybacking: In bidirectional communications, both parties send & acknowledge data, i.e. both parties implement flow control. Outstanding ACKs are placed in the header of information frames, piggybacking can save bandwidth since the overhead from a data frame and an ACK frame (addresses, CRC, etc) can be combined into just one frame.

Sliding Window ARQ:

  • To cover retransmission of lost or damaged frames, some features are added to the basic flow control mechanism of sliding window.
  • A Sender may send multiple frames as allowed by the window size.
  • The sending device keeps copies of all transmitted frames, until they have been acknowledged. .
  • In addition to ACK frames, the receiver has the option of returning a NAK frame, if the data have been received damaged. NAK frame tells the sender to retransmit a damaged frame.
  • Here, both ACK and NAK frames must be numbered for identification.
  • ACK frames carry the number of next frame expected.
  • NAK frames on the other hand, carry the number of the damaged frame itself.
  • If the last ACK was numbered 3, an ACK 6 acknowledges the receipt of frames 3, 4 and 5 as well.
  • If data frames 4 and 5 are received damaged, both NAK 4 and NAK 5 must be returned.
  • Like stop and wait ARQ, the sending device in sliding window ARQ is equipped with a timer to enable it to handle lost acknowledgements.
  • Sliding window ARQ is two types: Go-back-n ARQ, and Selective Reject ARQ.
  • There are two ACK processing methods in sliding windows:
    • Selective ACK: The ACK N message acknowledges only the frame with sequence number N
    • Cumulative ACK : The ACK N message acknowledges all frames with sequence number <= N

(i) Go-back-n ARQ:

  • The sliding window method using cumulative ACK is known as the Go-Back-N ARQ protocol.
  • Receiver window size is 1.
  • In this method, if one frame is lost or damaged all frames sent, since the last frame acknowledged are retransmitted.
  • For example, sender may send frames 1,2,3,4 and get an NAK with a value of 2. The NAK acknowledges everything that came before it, and asks for frame 2 (and subsequent frames) to be resent.
  • NAK number refer to the next expected frame number.
  • Example: In the following figure, frame 2 has an error, then all subsequent frames are discarded. After timeout sender sends all frames from frame 2.

Gobackn

 

  • Damaged/Error Frame :
    • In go-back-n ARQ, The receiver sends the NAK for this frame along with that frame number, that it expects to be retransmitted.
    • After sending NAK, the receiver discards all the frames that it receives, after a damaged frame.
    • The receiver does not send any ACK (acknowledgement) for the discarded frames.
      After the sender receives the NAK for the damaged frame, it retransmits all the frames onwards the frame number referred by NAK.
  • Lost frame:
    • In go-back-n ARQ, Receiver easily detects the loss of a frame as the newly received frame is received out of sequence.
    • The receiver sends the NAK for the lost frame and then the receiver discards all the frames received after a lost frame.
    • The receiver does not send any ACK for that discarded frames.
    • After the sender receives the NAK for the lost frame, it retransmits the lost frame referred by NAK and also retransmits all the frames which it has sent after the lost frame.
  • Lost Acknowledgement :
    • In go-back-n ARQ, If the sender does not receive any ACK or if the ACK is lost or damaged in between the transmission.
    • The sender waits for the time to run out and as the time run outs, the sender retransmits all the frames for which it has not received the ACK.
    • The sender identifies the loss of ACK with the help of a timer.
    • The ACK number, like NAK number, shows the number of the frame, that receiver expects to be the next in sequence.
    • The window size of the receiver is 1 as the data link layer only require the frame which it has to send next to the network layer.
    • The sender window size is equal to ‘w’. If the error rate is high, a lot of bandwidth is lost wasted.

(ii) Selective Repeat ARQ:

  • Selective Repeat ARQ overcomes the limitations of Go-Back-N by adding two new features:
    • Receiver window > 1 frame: Out-of-order but error-free frames can be accepted
    • Retransmission mechanism is modified: Only individual frames are retransmitted
  • In this method, only specific damaged or lost frame is retransmitted
  • Sender only retransmits frames for which a NAK is received.
  • NAK number refer to the frame lost.
  • If a frame is corrupted in transmit, a NAK is returned and the frame is resent out of sequence.
  • The sender needs to maintain all data that hasn’t been aknowledged yet.
  • The receiving device must be able to sort the frames it has and insert the retransmitted frame into its proper place in the sequence.
  • It has advantage that few re-transmissions than go-back-n. But complexity at sender and receiver is involved.
  • Example: Frame 2 has an error, so receiver maintains buffer to store the next frames.

Selective

  • Damaged frames :
    • In Selective reject, If a receiver receives a damaged frame, it sends the NAK for the frame in which error or damage is detected.
    • The NAK number, like in go-back-n also indicate the acknowledgement of the previously received frames and error in the current frame.
    • The receiver keeps receiving the new frames while waiting for the damaged frame to be replaced.
    • The frames that are received after the damaged frame are not be acknowledged until the damaged frame has been replaced.
  • Lost Frame :
    • As in a selective repeat protocol, a frame can be received out of order and further they are sorted to maintain a proper sequence of the frames.
    • While sorting, if a frame number is skipped, the receiver recognise that a frame is lost and it sends NAK for that frame to the sender.
    • After receiving NAK for the lost frame the sender searches that frame in its window and retransmits that frame.
    • If the last transmitted frame is lost then receiver does not respond and this silence is a negative acknowledgement for the sender.
  • Lost Acknowledgement :
    • In Selective reject, If the sender does not receive any ACK or the ACK is lost or damaged in between the transmission.
    • The sender waits for the time to run out and as the time run-outs, the sender retransmits all the frames for which it has not received the ACK.
    • The sender identifies the loss of ACK with the help of a timer. 

Candidates can also practice 112+ Mock tests for exams like GATE, NIELIT with BYJU’S Exam Prep Test Series check the following link:

Click Here to Avail GATE CSE Test Series!

Thanks

#DreamStriveSucceed

Our Apps Playstore
POPULAR EXAMS
SSC and Bank
Other Exams
GradeStack Learning Pvt. Ltd.Windsor IT Park, Tower - A, 2nd Floor, Sector 125, Noida, Uttar Pradesh 201303 help@byjusexamprep.com
Home Practice Test Series Premium