SEHH2238: Computer Networking
Automatic Repeat Request (ARQ) Protocols
Textbook: Ch.23
SEHH2238 Lecture 9 1
Copyright By PowCoder代写 加微信 powcoder
SEHH2238: Computer Networking
A. Sliding Window
Main Topics
B. Revision on Stop-and-Wait ARQ
C. Go-Back-NARQ Cumulative ACK Window size
D. SelectiveRepeatARQ
Individual Acknowledgement
Sender and Receiver Window Size
SEHH2238 Lecture 9 2
SEHH2238: Computer Networking
Flow & Error Control Mechanisms
Stop and Wait ARQ WCB/McGraw-Hill
Go-Back-N ARQ Selective Repeat ARQ
SEHH2238 Lecture 9 3
SEHH2238: Computer Networking
A. Sliding Window
The sender can transmit several data frames before needing (receiving) an ACK
A (logical) window is used to control the maximum no. of frames can be transmitted
When the (variable) window size becomes zero, the sender stops transmissions and waits for an ACK
A single ACK can be used to confirm the receipt of multiple data frames
SEHH2238 Lecture 9 4
SEHH2238: Computer Networking
Sender Sliding Window
Sequence Number of each frame
In this case: Sequence number: 3 bits (0-7) 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3…
WCB/McGraw-Hill
SEHH2238 Lecture 9 5
SEHH2238: Computer Networking
Variables to define the Window
Sender Sliding Window
SF: Seq. No. of 1st frame
SL :Seq. No. of Last frame
S: Seq. No. of next frame to be sent
SEHH2238 Lecture 9
Figure 23.12: Sliding window in circular format e.g. Window size = 7 ; Seq. no. has 4 bits (i.e. 0 -15)
SEHH2238: Computer Networking
SEHH2238 Lecture 9 7
Figure 23.13: Sliding window in linear SEHH2238: Computer Networking
format e.g. Window size = 7 ; Seq. no. has 4 bits (i.e. 0 -15)
SEHH2238 Lecture 9 8
SEHH2238: Computer Networking
3 bits for Seq. no.
SEHH2238 Lecture 9
The next data is …?
SEHH2238: Computer Networking
B. Stop-and-Wait ARQ
The sender sends one frame and waits for an ACK before sending the next frame
If no ACK is received after a period of time (timeout), the sender retransmits
Use 1 bit sequence number
Both the sender and the receiver use a
sliding window of size 1
Advantage: Simple
Disadvantage: Inefficient
SEHH2238 Lecture 9 10
Example 23.4
Figure 23.22 shows an example of the Stop-and-Wait protocol.
1. Packet 0 is sent and acknowledged.
2. Packet 1 is lost and resent after the time-out.
3. The resent packet 1 is acknowledged and the timer stops.
4. Packet 0 is sent and acknowledged, but the acknowledgment is lost. The sender has no idea if the packet or the acknowledgment is lost, so after the time-
out, it resends packet 0, which is acknowledged.
SEHH2238 Lecture 9 11
Figure 23.22: Flow diagram for Example 3.4
Use the concept of sliding window
At sender, the sliding window (buffer) holds the outstanding frames until they are acknowledged.
SEHH2238: Computer Networking
C. Go-back-N (GBN) ARQ
Multiple frames are in transit while waiting acknowledgement
Operation:
Sender sends multiple frames and set a timer for each frame sent. (The receiver has no timer)
S: Sequence no. of the recently sent frame
SEHH2238 Lecture 9 13
SEHH2238: Computer Networking
Go-Back-N ARQ, normal operation
Receiver side
Case 1: frames arrived safe and in order
Receiver sends positive acknowledgements
R: Sequence number of the frame it expects to receive (R is contained in ACK packet)
SEHH2238 Lecture 9 14
SEHH2238: Computer Networking
Go-Back-N ARQ, normal operation
Send window size is 3
SEHH2238 Lecture 9 15
2 bits for Seq. no.
SEHH2238: Computer Networking
Go-Back-N ARQ, lost frame Case 2: Frame is damaged or out of order
Receiver is silent (send nothing) and discards all subsequent frames until it receives the one it is expecting
In sender, the timer for the unacknowledged frame expires
The sender goes back and resends all
frames, beginning from the one with
the expired timer
SEHH2238 Lecture 9 16
SEHH2238: Computer Networking
Go-Back-N ARQ, lost frame
Send window size is 3
SEHH2238 Lecture 9 17
2 bits for Seq. no.
Figure 23.24: Send window for Go-Back-N
3 bits for Seq. no.
Figure 23.25: Sliding the send window
3 bits for Seq. no.
Send window size is 7
Sliding direction
Figure 23.26: Receive window for Go-Back-N
3 bits for Seq. no.
SEHH2238: Computer Networking
Go-Back-N ARQ: sender window size
m – no. of bits for Seq. no.
SEHH2238 Lecture 9
2 bits for Seq. no.
GOOD G HELLO H
SEHH2238: Computer Networking
Sender Window Size
In Go-Back-N ARQ, the size of the
sender window must be less than 2m; the size of the receiver window is
where m is the number of bits of the sequence number SEHH2238 Lecture 9 22
Example 23.7
Figure 23.29 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 packets are lost, but some ACKs are delayed and one is lost. The example also shows how cumulative ACKs can help if acknowledgments are delayed or lost.
SEHH2238 Lecture 9 23
Figure 23.29: Flow diagram for Example 3.7 Send window size is 7
Example 23.8
Figure 23.30 shows what happens when a packet is lost. Packets 0, 1, 2, and 3 are sent.
• However, packet 1 is lost. The receiver receives packets
2 and 3, but they are discarded because they are received out of order (packet 1 is expected).
• When the receiver receives packets 2 and 3, it sends ACK1 to show that it expects to receive packet 1.
• However, these ACKs are not useful for the sender
because the ackNo is equal to Sf, not greater that Sf .
So the sender discards them.
• When the time-out occurs, the sender resends packets
1, 2, and 3, which will then be acknowledged.
SEHH2238 Lecture 9 25
Figure 23.30: Flow diagram for Example 23.8
Send window size is 7
SEHH2238: Computer Networking
Go-Back-N Advantages & Disadvantages
Maintain correct sequence
Minimize the receiver buffer storage
1 storage unit is enough in the receiver buffer
But need to retransmit some already correctly received frames
Less efficient than selective-repeat
SEHH2238 Lecture 9 27
SEHH2238: Computer Networking
D. Selective Repeat ARQ
In Go-back-N ARQ, the process at the receiver is simple
Receiver keeps track of only one variable
No need to buffer out-of-order frames
But multiple frames are resent when one frame is damaged
Use up bandwidth and slow down transmission Selective Repeat ARQ
Does not resent N frames when just one frame is damaged
Only the damaged frame is resent
SEHH2238 Lecture 9 28
SEHH2238: Computer Networking
Receiver in Selective Repeat ARQ
Receiver detects those frames that are damaged
Receiver retains out-of-sequence frames (without errors) in the link receive list until the next in- sequence frame is received; then a set of consecutive frames could be delivered to the upper layer
Individual ACK
ACK(N) acknowledges only a single frame with
sequence number N
In the sender, when a timer (waiting for ACK) expires, only the corresponding frame is resent
SEHH2238 Lecture 9 29
SEHH2238: Computer Networking
Send Window for Selective Repeat ARQ
Similar to Figure 23.32
SEHH2238 Lecture 9 30
SEHH2238: Computer Networking
Receive Window for Selective Repeat ARQ
Similar to Figure 23.33
SEHH2238 Lecture 9 31
SEHH2238: Computer Networking
Sender and Receiver Window Size
In Selective Repeat ARQ, the sender and receiver window have the same size and it must be
at most one-half of 2m
where m is the number of bits of the sequence number (skip the explanation)
SEHH2238 Lecture 9 32
SEHH2238: Computer Networking
Window Slide and Change of Rn At the receiver, if the received frame is not damaged and the
sequence no. is within the window,
Receiver will store the frame and mark the slot ( e.g. slot 5 and 6 on orange.)
If contiguous frames, starting from Rn have been marked, data is delivered to the upper layer, and the window slides.
(Say just received data No. 0) (data No. 0, 1 and 2 are delivered)
Figure Delivery of data in Selective Repeat ARQ
SEHH2238 Lecture 9 33
xxxxxxxxxxxxxxx
Example 23.9
Assume a sender sends 6 packets: packets 0, 1, 2, 3, 4, and 5. The sender receives an ACK with ackNo = 3. What is the interpretation if the system is using GBN or SR?
If the system is using GBN, it means that packets 0, 1, and 2 have been received uncorrupted and the receiver is expecting packet 3.
If the system is using SR, it means that packet 3 has been received uncorrupted; the ACK does not say anything about other packets.
SEHH2238 Lecture 9 34
Example 23.10
Similar to Example 23.8 (Figure 23.30) in which packet 1 is lost but using Selective-Repeat.
At the sender, packet 0 is transmitted and acknowledged. Packet 1 is lost. Packets 2 and 3 arrive out of order and are acknowledged. When the timer times out, packet 1 (the only unacknowledged packet) is resent and is acknowledged. The send window then slides.
Theoretically, Select-Repeat uses one timer for each outstanding (unacknowledged) packet. When a timer expires, only the corresponding packet is resent. However, implementation with a single timer also works, as shown in this example.
SEHH2238 Lecture 9 35
Example 23.10 (continued)
At the receiver site we need to distinguish between the
acceptance of a packet and its delivery to the application
• At the second arrival, packet 2 arrives and is stored and
marked (shaded slot), but it cannot be delivered because
packet 1 is missing.
• At the next arrival, packet 3 arrives and is marked and
stored, but still none of the packets can be delivered.
• Only at the last arrival, when finally a copy of packet 1 arrives, can packets 1, 2, and 3 be delivered to the
application layer.
• There are two conditions for the delivery of packets to
the application layer:
A set of consecutive packets must have arrived.
The set starts from the beginning of the window.
SEHH2238 Lecture 9 36
Figure 23.35: Flow diagram for Example 3.10
SEHH2238: Computer Networking
Selective Repeat Disadvantages
Order of receiving data frames is not maintained
Re-sequencing is required in Receiver
Number of buffers can be large and non-
deterministic
(Advantage: but the channel is more efficient than Go-Back-N)
SEHH2238 Lecture 9 38
SEHH2238: Computer Networking
Summary on Sliding Window ARQ
The link utilization is much improved at the expense of larger buffer storage requirements
Sender sends data frame continuously without waiting for an ACK
Sender retains a copy of each transmitted data frame in a retransmission list
Receiver returns an ACK for each correctly received data frame
SEHH2238 Lecture 9 39
SEHH2238: Computer Networking
Sliding Window ARQ (cont.)
Each data frame contains a unique identifier (the sequence number)
On receipt of an ACK the corresponding data frame is removed from the retransmission list by Sender
Receiver retains a link receive list containing the correctly received data frames (but may be out-of- order for selective-repeat)
Retransmission strategies when an error occurs
Go-Back-N
Selective Repeat
SEHH2238 Lecture 9 40
SEHH2238: Computer Networking
Stop-and-Wait
Simplest but least efficient
Minimum buffer storage (only 1 in sender & receiver)
Go-Back-N
Maintain correct sequence
Less demand on the buffer storage (1 in receiver)
But need to retransmit some already correctly received frames
Channel less efficient than selective-repeat Selective Repeat
Re-sequencing (and more buffers) required in receiver
Number of buffers can be large and non-deterministic
Channel more efficient than Go-Back-N
SEHH2238 Lecture 9 41
SEHH2238: Computer Networking
References
Go-Back-N Video
http://www.youtube.com/watch?v=yT8SkFyRRrI
Simulation on Go-Back-N and Selective Repeat http://www.ccs-labs.org/teaching/rn/animations/gbn_sr/
Revision Quiz
http://highered.mheducation.com/sites/0073376221/stud
ent_view0/chapter23/quizzes.html
SEHH2238 Lecture 9 42
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com