Flow Control Techniques PDF

Flow Control Techniques ◻ 2 protocols developed 1. Stop-and-wait 2. Sliding window 1. Stop-and-wait Each data packets to be acknowledged before the next frame sent ◻ Simplest form of flow control ◻ Sender sends single frame and receiver take one frame at a time and sent a...

Flow Control Techniques ◻ 2 protocols developed 1. Stop-and-wait 2. Sliding window 1. Stop-and-wait Each data packets to be acknowledged before the next frame sent ◻ Simplest form of flow control ◻ Sender sends single frame and receiver take one frame at a time and sent acknowledgment for the new frame ◻ Stop and wait means whatever the data the sender wants to send, he sends the data to receiver ◻ After sending the data, he stops and wait until he receives the acknowledgment from the receiver ◻ Provides unidirectional data transmission  Operations 1. Sender sends one data packet at a time 2. Sender sends the next data packet only when it receives acknowledgment from previous packets ◻ Eg: RPC Drawbacks: ◻ Only one frame at a time □ inefficiency ◻ Propagation delay  2. Sliding window protocol ◻ Required when reliable in-order delivery of packets is needed ◻ Allows multiple frames to be transmit at the same time ◻ TCP, Internet stream transfer protocol etc are of this type ◻ To keep track of frames sender station sends sequentially numbered frames. The sequence numbers are used to find the missing data in the receive end. The purpose of sliding window is to avoid duplicate data, so it uses sequence number ◻ Sender transmits various frames before receiving acknowledgment Operation ◻ Sending window ◻ Receiving window  How flow control is achieved Receiver maintains a buffer to manage the flow of packets. The receiver buffer holds the packet that have been send by the sender but have not yet acknowledged. During data transmission, the receiver notifies the sender the amount of free space available in the receive buffer. This space is referred to as receive window. The sender cannot send more data packets than the amount of space available in the receive window. Sending Window Receiving Window  ARQ Techniques – Error Control ◻ When an error is detected in a message, the receiver sends a request to the transmitter to retransmit the ill-fated message or packet. ◻ The most popular retransmission scheme is known as Automatic-Repeat-Request (ARQ). ◻ Such schemes, where receiver asks transmitter to re-transmit if it detects an error, are known as reverse error correction techniques ◻ 3 Popular ARQ Techniques  Stop and wait ARQ ◻ Simplest among all protocols ◻ The sender transmits a frame and then waits till it receives positive acknowledgement (ACK) or negative acknowledgement (NACK) from the receiver ◻ Receiver sends an ACK if the frame is received correctly, otherwise it sends NACK. ◻ Sender sends a new frame after receiving ACK; otherwise it retransmits the old frame, if it receives a NACK. ◻ To tackle the problem of a lost or damaged frame, the sender is equipped with a timer. ◻ In case of a lost ACK, the sender transmits the old frame ◻ There are 2 possibilities 1. Retransmission due to lost frames 2. Retransmission due to receive of NACK frame Retransmission due to lost frames The frame ( second PDU (Protocol Data Unit )of Data) is lost during transmission. ◻ The sender is unaware of this loss, but starts a timer after sending each PDU. ◻ Normally an ACK PDU is received before the timer expires. ◻ In this case no ACK is received, and the timer counts down to zero and triggers retransmission of the same PDU by the sender. ◻ The sender always starts a timer following transmission, □ In the second transmission receives an ACK PDU before the timer expires, Retransmission due to receive of NACK ◻ To tackle the problem of damaged frames, say a frame that has been corrupted during the transmission due to noise, there is a concept of NACK frames ◻ i.e. Negative Acknowledge frames. ◻ Receiver transmits a NACK frame to the sender if it founds the received frame to be corrupted. ◻ When a NACK is received by a transmitter before the time-out, the old frame is sent again  Go-back-N ARQ ◻ Most popular ARQ protocol is the go-back-N ARQ ◻ Here the sender sends the frames continuously without waiting for acknowledgement. ◻ That is why it is also called as continuous ARQ. ◻ As the receiver receives the frames, it keeps on sending ACKs or a NACK, in case a frame is incorrectly received. ◻ When the sender receives a NACK, it retransmits the frame in error plus all the succeeding frames  GO-BACK-N ARQ employs the protocol pipelining idea, in which numerous frames can be delivered before getting acknowledgment of the first frame. If we have 5 frames and the window size is 3, then frame 1, frame 2, and frame 3 can be sent before anticipating the acknowledgment of frame 1. The frames in Go-Back-N ARQ are numbered consecutively because Go-Back-N ARQ delivers numerous frames at a time, which necessitates the numbering strategy to identify one frame from another, and these numbers are known as the sequential numbers. The number of frames that may be sent at the same time is entirely determined by the size of the sender’s window. As a result, ‘N’ is the number of frames that can be delivered at the same time before getting an acknowledgment from the recipient.  If a frame’s acknowledgment is not received within a certain time period, all frames in the window will be retransmitted. If we sent frame 5 but did not receive acknowledgment, and the current window is holding three frames, then these three frames will be retransmitted. The outgoing frame sequence number is determined by the size of the sender’s window. If the sender’s window size is four, the sequence number will be 0,1,2,3 and then the sequence repeats.  Selective-Repeat ARQ ◻ The selective-repetitive ARQ scheme retransmits only those for which NAKs are received or for which timer has expired ◻ This is the most efficient among the ARQ schemes, but the sender must be more complex so that it can send out-of-order frames. ◻ The receiver also must have storage space to store the post NAK frames and processing power to reinsert frames in proper sequence  Explanation Step 1 − Frame 0 sends from sender to receiver and set timer. Step 2 − Without waiting for acknowledgement from the receiver another frame, Frame1 is sent by sender by setting the timer for it. Step 3 − In the same way frame2 is also sent to the receiver by setting the timer without waiting for previous acknowledgement. Step 4 − Whenever sender receives the ACK0 from receiver, within the frame 0 timer then it is closed and sent to the next frame, frame 3. Step 5 − whenever the sender receives the ACK1 from the receiver, within the frame 1 timer then it is closed and sent to the next frame, frame 4. Step 6 − If the sender doesn’t receive the ACK2 from the receiver within the time slot, it declares timeout for frame 2 and resends the frame 2 again, because it thought the frame2 may be lost or damaged. Sliding Window Protocol  Full-duplex data transmission is to have two separate communication channels and use each one for simplex data traffic (in different directions). If this is done, we have two separate physical circuits, each with a ''forward'' channel (for data) and a ''reverse'' channel (for acknowledgements). In which cases, the bandwidth of the reverse channel is almost entirely wasted. In effect, the user is paying for two circuits but using only the capacity of one A better idea is to use the same circuit for data in both directions. 24  Data frames from A to B are intermixed with the acknowledgement frames from A to B. By looking at the kind field in the header of an incoming frame, the receiver can tell whether the frame is data or acknowledgement Another improvement is possible: When a data frame arrives, instead of immediately sending a separate control frame, the receiver restrains itself and waits until the network layer passes it the next packet. The acknowledgement is attached to the outgoing data frame (using the ack field in the frame header). In effect, the acknowledgement gets a free ride on the next outgoing data frame. The technique of temporarily delaying outgoing acknowledgements so that they can be hooked onto the next outgoing data frame is known as piggybacking 25 Sliding Window Protocols The principal advantage of using piggybacking over having distinct acknowledgement frames better use of the available channel bandwidth. The ack field in the frame header costs only a few bits, whereas a separate frame would need a header, the acknowledgement, and a checksum. Other advantages: In addition, fewer frames sent means fewer ''frame arrival'' interrupts, fewer buffers required in the receiver, depending on how the receiver's software is organized. 26 Sliding Window Protocols Piggybacking introduces a complication not present with separate acknowledgements. How long should the data link layer wait for a packet onto which to piggyback the acknowledgement? If the data link layer waits longer than the sender's timeout period, the frame will be retransmitted, defeating the whole purpose of having acknowledgements. Of course, the data link layer cannot foretell the future So it must take an option to use a scheme, such as waiting a fixed number of milliseconds. If a new packet arrives quickly, the acknowledgement is piggybacked onto it; otherwise, if no new packet has arrived by the end of this time period, the data link layer just sends a separate acknowledgement frame 27 Sliding Window Protocols In all sliding window protocols, each outbound frame contains a sequence number, ranging from 0 up to some maximum Maximum is usually 2n - 1 so the sequence number fits exactly in an n-bit field. The stop-and-wait sliding window protocol uses n = 1, restricting the sequence numbers to 0 and 1 Essence of all sliding window protocols at any instant of time, the sender maintains a set of sequence numbers corresponding to frames it is permitted to send. These frames are said to fall within the sending window. Similarly, the receiver also maintains a receiving window corresponding to the set of frames it is permitted to accept. 28 Sliding Window Protocols A sliding window of size 1, with a 3-bit sequence number. (a) Initially. (b) After the first frame has been sent. (c) After the first frame has been received. (d) After the first acknowledgement has been received. 29 Sliding Window Protocols The sender's window and the receiver's window need not have the same lower and upper limits or even have the same size. In some protocols they are fixed in size, but in others they can grow or shrink over the course of time as frames are sent and received The sequence numbers within the sender's window represent frames that have been sent or can be sent but are as yet not acknowledged. Whenever a new packet arrives from the network layer, it is given the next highest sequence number, and the upper edge of the window is advanced by one. When an acknowledgement comes in, the lower edge is advanced by one. In this way the window continuously maintains a list of unacknowledged frames. Since frames currently within the sender's window may ultimately be lost or damaged in transit, the sender must keep all these frames in its memory for possible retransmission. 30 Sliding Window Protocols Bidirectional Protocols A One-Bit Sliding Window Protocol A Protocol Using Go Back N A Protocol Using Selective Repeat Three protocols differ among themselves in terms of efficiency, complexity, and buffer requirements 31 A One-Bit Sliding Window Protocol A sliding window protocol with a maximum window size of 1. Such a protocol uses stop-and-wait since the sender transmits a frame and waits for its acknowledgement before sending the next one starting machine fetches the first packet from its network layer, builds a frame from it, and sends it. When this frame arrives, the receiving data link layer checks to see if it is a duplicate If the frame is the one expected, it is passed to the network layer and the receiver's window is slid up 32 A One-Bit Sliding Window Protocol The acknowledgement field contains the number of the last frame received without error. If this number agrees with the sequence number of the frame the sender is trying to send, the sender knows it is done with the frame stored in buffer and can fetch the next packet from its network layer. If the sequence number disagrees, it must continue trying to send the same frame. 33 A One-Bit Sliding Window Protocol Scenario (a) Normal case. The notation is (seq, ack, packet number). An asterisk indicates where a network layer accepts a packet. 34 A One-Bit Sliding Window Protocol Scenario (b) Abnormal case. The notation is (seq, ack, packet number). 35 An asterisk indicates where a network layer accepts a packet. Pipelining In computer networking, pipelining is the method of sending multiple data units without waiting for an acknowledgment for the first frame sent. Pipelining ensures better utilization of network resources and also increases the speed of delivery, particularly in situations where a large number of data units make up a message to be sent.  Data Link Protocols that uses Pipelining Two data link layer protocols use the concept of pipelining − Go – Back – N Selective Repeat  Sliding Window Protocol Using Go Back N ❑ Two basic approaches are available for dealing with errors in the presence of pipelining. ❑ One way, called go back n, is for the receiver simply to discard all subsequent frames, sending no acknowledgements for the discarded frames. ❑ This strategy corresponds to a receive window of size 1. ❑Eventually, the sender will time out and retransmit all unacknowledged frames in order, starting with the damaged or lost one. ❑ ❑This approach can waste a lot of bandwidth if the error rate is high. 39 Sliding Window Protocol Using Go Back N Pipelining and error recovery. Effect on an error when receiver’s window size is 1 ❑ Frames 0 and 1 are correctly received and acknowledged. ❑ Frame 2, however, is damaged or lost. ❑ The sender, unaware of this problem, continues to send frames until the timer for frame 2 expires. ❑ Then it backs up to frame 2 and starts all over with it, sending 2, 3, 4, etc. all over again 40  Sliding Window Protocol Using Selective Repeat ❑ Other general strategy for handling errors when frames are pipelined is called selective repeat. ❑ When it is used, a bad frame that is received is discarded, but good frames received after it are buffered. ❑ When the sender times out, only the oldest unacknowledged frame is retransmitted. ❑ If that frame arrives correctly, the receiver can deliver to the network layer, in sequence, all the frames it has buffered. ❑ Selective repeat is often combined with having the receiver send a negative acknowledgement (NAK) when it detects an error, ❑ for example, when it receives a checksum error or a frame out of sequence. ❑ NAKs stimulate retransmission before the corresponding timer expires and thus improve performance 41  Sliding Window Protocol Using Selective Repeat Pipelining and error recovery. Effect on an error when receiver’s window size is large. 5 2 4 ▪ Selective repeat corresponds to a receiver window larger than 1 ▪ require large amounts of data link layer memory if the window is large 42  Sliding Window Protocol Using Selective Repeat ❑ Frames 0 and 1 are again correctly received and acknowledged and frame 2 is lost. ❑ When frame 3 arrives at the receiver, the DLL notices that is has missed a frame ❑ So it sends back a NAK for 2 but buffers 3. ❑ When frames 4 and 5 arrive, they, too, are buffered by the DLL instead of being passed to the network layer. ❑ Eventually, the NAK 2 gets back to the sender, which immediately resends frame 2. When that arrives, the DLL now has 2, 3, 4, and 5 and can pass all of them to the network layer in the correct order. ❑ It can also acknowledge all frames up to and including 5 ❑ If the NAK should get lost, eventually the sender will time out for frame 2 and send it, but that may be a quite a while later 43