Note
In the Go-Back-N Protocol, the sequence
numbers are modulo 2m,
where m is the size of the sequence
number field in bits.
Sliding Window
• 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.
• Maximum size is 2m − 1
Send window for Go-Back-N ARQ
Note
The send window is an abstract concept
defining an imaginary box of size 2m − 1
with three variables: Sf, Sn, and Ssize.
Note
The send window can slide one
or more slots when a valid
acknowledgment arrives.
Receive window for Go-Back-N ARQ
Note
The receive window is an abstract
concept defining an imaginary box
of size 1 with one single variable Rn.
The window slides
when a correct frame has arrived;
sliding occurs one slot at a time.
Figure: Design of Go-Back-N ARQ
Figure : Window size for Go-Back-N ARQ
Note
In Go-Back-N ARQ, the size of the send
window must be less than 2m;
the size of the receiver window
is always 1.
Algorithm: Go-Back-N sender algorithm
(continued)
Algorithm: Go-Back-N sender algorithm (continued)
Algorithm: Go-Back-N receiver algorithm
Example
Following Figure shows an example of Go-Back-N. This
is an example of a case where the forward channel is
reliable, but the reverse is not. No data frames are lost,
but some ACKs are delayed and one is lost. The example
also shows how cumulative acknowledgments can help if
acknowledgments are delayed or lost. After initialization,
there are seven sender events. Request events are
triggered by data from the network layer; arrival events
are triggered by acknowledgments from the physical
layer. There is no time-out event here because all
outstanding frames are acknowledged before the timer
expires. Note that although ACK 2 is lost, ACK 3 serves
as both ACK 2 and ACK 3.
Figure: Flow diagram for Example
Example
Following figure shows what happens when a frame is
lost. Frames 0, 1, 2, and 3 are sent. However, frame 1 is
lost. The receiver receives frames 2 and 3, but they are
discarded because they are received out of order. The
sender receives no acknowledgment about frames 1, 2, or
3. Its timer finally expires. The sender sends all
outstanding frames (1, 2, and 3) because it does not know
what is wrong. Note that the resending of frames 1, 2, and
3 is the response to one single event. When the sender is
responding to this event, it cannot accept the triggering of
other events. This means that when ACK 2 arrives, the
sender is still busy with sending frame 3.
Example (continued)
The physical layer must wait until this event is completed
and the data link layer goes back to its sleeping state. We
have shown a vertical line to indicate the delay. It is the
same story with ACK 3; but when ACK 3 arrives, the
sender is busy responding to ACK 2. It happens again
when ACK 4 arrives. Note that before the second timer
expires, all outstanding frames have been sent and the
timer is stopped.
Figure: Flow diagram for Example
Note
Stop-and-Wait ARQ is a special case of
Go-Back-N ARQ in which the size of the
send window is 1.
Link Utilization / Efficiency of Go Back N ARQ
Efficiency (η) = N / (1+2a)
where,
N is the window size
a = T p / Tt
Example: A 20 Kbps satellite link has a propagation delay of 400 ms.
The transmitter employs the “go back n ARQ” scheme with N set to
10. Assuming that each frame is 100 bytes long, what is the maximum
Link Utilization / Efficiency of Go Back N ARQ
Solution:
Transmission delay (Tt) = Frame size / Bandwidth
= 100 bytes / 20 Kbps=40 ms
Propagation delay = 400 ms
a = Tp / Tt
a = 400 / 40 = 10
Efficiency, η = N / (1+2a)
Selective Repeat ARQ
• Go-Back-N ARQ is very inefficient for a noisy link. In a
noisy link a frame has a higher probability of damage,
which means the resending of multiple frames.
• Resending uses up the bandwidth and slows down the
transmission.
• When just one frame is damaged; only the damaged frame
is resent. This mechanism is called Selective Repeat ARQ
Figure: Send window for Selective Repeat ARQ
Figure : Receive window for Selective Repeat ARQ
Figure: Design of Selective Repeat ARQ
Figure: Selective Repeat ARQ, window size
Note
In Selective Repeat ARQ, the size of the
sender and receiver window
must be at most one-half of 2m.
Algorithm: Sender-site Selective Repeat algorithm
(continued)
Algorithm: Sender-site Selective Repeat algorithm (continued)
(continued)
Algorithm: Sender-site Selective Repeat (continued)
algorithm
Algorithm: Receiver-site Selective Repeat algorithm
Algorithm:Receiver-site Selective Repeat algorithm
Figure: Delivery of data in Selective Repeat ARQ
Example
We show how Selective Repeat behaves in the case 1
frame is lost. Figure in the following slide shows the
situation. One main difference is the number of timers.
Here, each frame sent or resent needs a timer, which
means that the timers need to be numbered (0, 1, 2, and
3). The timer for frame 0 starts at the first request, but
stops when the ACK for this frame arrives. The timer for
frame 1 starts at the second request, restarts when a NAK
arrives, and finally stops when the last ACK arrives. The
other two timers start when the corresponding frames are
sent and stop at the last arrival event.
Example (continued)
At the receiver site we need to distinguish between the
acceptance of a frame and its delivery to the network
layer. At the second arrival, frame 2 arrives and is stored
and marked, but it cannot be delivered because frame 1 is
missing. At the next arrival, frame 3 arrives and is
marked and stored, but still none of the frames can be
delivered. Only at the last arrival, when finally a copy of
frame 1 arrives, can frames 1, 2, and 3 be delivered to the
network layer. There are two conditions for the delivery
of frames to the network layer: First, a set of consecutive
frames must have arrived. Second, the set starts from the
beginning of the window.
Example (continued)
Another important point is that a NAK is sent after the
second arrival, but not after the third, although both
situations look the same. The reason is that the protocol
does not want to crowd the network with unnecessary
NAKs and unnecessary resent frames. The second NAK
would still be NAK1 to inform the sender to resend frame
1 again; this has already been done. The first NAK sent is
remembered (using the nakSent variable) and is not sent
again until the frame slides. A NAK is sent once for each
window position and defines the first slot in the window.
Example (continued)
The next point is about the ACKs. Notice that only two
ACKs are sent here. The first one acknowledges only the
first frame; the second one acknowledges three frames. In
Selective Repeat, ACKs are sent when data are delivered to
the network layer. If the data belonging to n frames are
delivered in one shot, only one ACK is sent for all of them.
Figure: Flow diagram for Example
Piggybacking
• In real life, data frames are normally flowing in
both directions
• A technique called piggybacking is used to
improve the efficiency of the bidirectional
protocols
• When a frame is carrying data from A to B, it can
also carry control information about arrived (or
lost) frames from B; when a frame is carrying
data from B to A, it can also carry control
information about the arrived (or lost) frames
from A.
Figure: Design of piggybacking in Go-Back-N ARQ
Link Utilization / Selective Repeat ARQ
Efficiency (η) = N / (1+2a)
where,
N is the window size
a = T p / Tt