• It adds a simple error control mechanism to the Stop-and- Wait Protocol.




• To detect and correct corrupted frames, we need to add redundancy bits to our data frame. When the frame arrives at the receiver site, it is checked and if it is corrupted, it is silently discarded. The detection of errors in this protocol is manifested by the silence of the receiver.




• Lost frames are more difficult to handle than corrupted ones. In our previous protocols, there was no way to identify a frame. The received frame could be the correct one, or a duplicate, or a frame out of order. The solution is to number the frames. When the receiver receives a data frame that is out of order, this means that frames were either lost or duplicated.




• The corrupted and lost frames need to be resent in this protocol. If the receiver does not respond when there is an error, how can the sender know which frame to resend? To remedy this problem, the sender keeps a copy of the sent frame. At the same time, it starts a timer. If the timer expires and there is no ACK for the sent frame, the frame is resent, the copy is held, and the timer is restarted.




• Since the protocol uses the stop-and-wait mechanism, there is only one specific frame that needs an ACK even though several copies of the same frame can be in the network.




• Since an ACK frame can also be corrupted and lost, it too needs redundancy bits and a sequence number. The ACK frame for this protocol has a sequence number field. In this protocol, the sender simply discards a corrupted ACK frame or ignores an out-of-order one.

Sequence Numbers

• The protocol specifies that frames need to be numbered. This is done by using sequence numbers. A field is added to the data frame to hold the sequence number of that frame.




• One important consideration is the range of the sequence numbers. Since we want to minimize the frame size, we look for the smallest range that provides unambiguous communication. The sequence numbers of course can wrap around. For example, if we decide that the field is m bits long, the sequence numbers start from 0, go to 2^m - 1, and then are repeated.




• Let us reason out the range of sequence numbers we need. Assume we have used x as a sequence number; we only need to use x + 1 after that. There is no need for x + 2. To show this, assume that the sender has sent the frame numbered x. Three things can happen :




1. The frame arrives safe and sound at the receiver site; the receiver sends an acknowledgment. The acknowledgment arrives at the sender site, causing the sender to send the next frame numbered x + 1.




2. The frame arrives safe and sound at the receiver site; the receiver sends an acknowledgment, but the acknowledgment is corrupted or lost. The sender resends the frame (numbered x) after the time-out. Note that the frame here is a duplicate. The receiver can recognize this fact because it expects frame x + 1 but frame x was received.




3. The frame is corrupted or never arrives at the receiver site; the sender resends the frame (numbered x) after the time-out.




• We can see that there is a need for sequence numbers x and x + 1 because the receiver needs to distinguish between case 1 and case 2. But there is no need for a frame to be numbered x + 2.




• In case 1, the frame can be numbered x again because frames x and x + 1 are acknowledged and there is no ambiguity at either site. In cases 2 and 3, the new frame is x + I, not x + 2. If only x and x + 1 are needed, we can let x = 0 and x + 1 =: 1. This is modulo-2 arithmetic.

Acknowledgment Numbers

• The acknowledgment numbers always announce the sequence number of the next frame expected by the receiver.




• For example, if frame 0 has arrived safe and sound, the receiver sends an ACK frame with acknowledgment 1 (meaning frame 1 is expected next).




• If frame I has arrived safe and sound, the receiver sends an ACK frame with acknowledgment 0 (meaning frame 0 is expected).

Design of Stop-and- Wait Automatic Repeat Request

• The sending device keeps a copy of the last frame transmitted until it receives an acknowledgment for that frame.




• A data frames uses a seqNo (sequence number); an ACK frame uses an ackNo (acknowledgment number). The sender has a control variable, which we call S_n (sender, next frame to send), that holds the sequence number for the next frame to be sent (0 or 1).




• The receiver has a control variable, which we call R_n (receiver, next frame expected), that holds the number of the next frame expected.




• When a frame is sent, the value of Sn is incremented (modulo-2), which means if it is 0, it becomes 1 and vice versa. When a frame is received, the value of Rn is incremented (modulo-2), which means if it is 0, it becomes 1 and vice versa.




• Variable S_n points to the slot that matches the sequence number of the frame that has been sent, but not acknowledged; R_n points to the slot that matches the sequence number of the expected frame.





• The Stop-and-Wait ARQ is very inefficient if our chan- nel is thick and long. By thick, we mean that our channel has a large bandwidth; by long, we mean the round-trip delay is long. The product of these two is called the bandwidth delay product.




• In networking and in other areas, a task is often begun before the previous task has ended. This is known as pipelining. There is no pipelining in Stop-and- Wait ARQ because we need to wait for a frame to reach the destination and be acknowledged before the next frame can be sent.

Figure below shows an example of Stop-and- Wait ARQ.

• Frame 0 is sent and acknowledged. Frame 1 is lost and resent after the time-out. The resent frame 1 is acknowledged and the timer stops.




• Frame 0 is sent and acknowledged, but the acknowledgment is lost. The sender has no idea if the frame or the acknowledgment is lost, so after the time-out, it resends frame 0, which is acknow ledged.

Q.Assume that, in a Stop-and-Wait ARQ system, the bandwidth of the line is 1 Mbps, and 1 bit takes 20 ms to make a round trip. What is the bandwidth-delay product? If the system data frames are 1000 bits in length, what is the utilization percentage of the link?

• The bandwidth-delay product is (1 x 10⁶) x (20 x 10^-3) = 20,000 bits




• The system can send 20,000 bits during the time it takes for the data to go from the sender to the receiver and then back again. However, the system sends only 1000 bits. We can say that the link utilization is only 1000/20,000, or 5 percent.

• To improve the efficiency of transmission (filling the pipe), multiple frames must be in transition while waiting for acknowledgment. In other words, we need to let more than one frame be outstanding to keep the channel busy while the sender is waiting for acknowledgment.




• n this protocol we can send several frames before receiving acknowledgments; we keep a copy of these frames until the acknowledgments arrive.

Sequence Numbers - the sequence numbers are modulo-2^m.

• Frames from a sending station are numbered sequentially. However, because we need to include the sequence number of each frame in the header, we need to set a limit.




• If the header of the frame allows "m" bits for the sequence number, the sequence numbers range from 0 to 2^m - 1. However, we can repeat the sequence.

Sliding Window

• The sliding window is an abstract concept that defines the range of sequence numbers that is the concern of the sender and receiver.




• The range which is the concern of the sender is called the send sliding window; the range that is the concern of the receiver is called the receive sliding window.




• The send window is an imaginary box covering the sequence numbers of the data frames which can be in transit. In each window position, some of these sequence numbers define the frames that have been sent; others define those that can be sent. The maximum size of the window is 2^m - 1




• The window at any time divides the possible sequence numbers into four regions. The first region, from the far left to the left wall of the window, defines the sequence numbers belonging to frames that are already acknowledged.




• The second region defines the range of sequence numbers belonging to the frames that are sent and have an unknown status. The sender needs to wait to find out if these frames have been received or were lost. These are outstanding frames.




• The third range defines the range of sequence numbers for frames that can be sent; however, the corresponding data packets have not yet been received from the network layer. Finally, the fourth region defines sequence numbers that cannot be used until the window slides.

Send and Receive Window

• Three variables define its size and location of send window at any time. We call these variables S_f (send window, the first outstanding frame), S_n (send window, the next frame to be sent), and S_size (send window, size). The variable S_f defines the sequence number of the first (oldest) outstanding frame.






• The variable S_n holds the sequence number that will be assigned to the next frame to be sent. Finally, the variable S_size = 2_m - 1 defines the size of the window, which is fixed in our protocol.




• The acknowledgments in this protocol are cumulative, meaning that more than one frame can be acknowledged by an ACK frame.




• The receive window makes sure that the correct data frames are received and that the correct acknowledgments are sent. The size of the receive window is always 1. The receiver is always looking for the arrival of a specific frame. Any frame arriving out of order is discarded and needs to be resent.

Timers and Acknowledgment

• Although there can be a timer for each frame that is sent, in our protocol we use only one.




• The reason is that the timer for the first outstanding frame always expires first; we send all outstanding frames when this timer expires.




• The receiver sends a positive acknowledgment if a frame has arrived safe and sound and in order.




• If a frame is damaged or is received out of order, the receiver is silent and will discard all subsequent frames until it receives the one it is expecting.




• The silence of the receiver causes the timer of the unacknowledged frame at the sender site to expire.




• This, in turn, causes the sender to go back and resend all frames, beginning with the one with the expired timer. The receiver does not have to acknowledge each frame received. It can send one cumulative acknowledgment for several frames.




• When the timer expires, the sender resends all outstanding frames. For example, suppose the sender has already sent frame 6, but the timer for frame 3 expires. This means that frame 3 has not been acknowledged; the sender goes back and sends frames 3, 4,5, and 6 again. That is why the protocol is called Go-Back-N ARQ.

Previous

Next