Data Link Layer
Flow Control
Flow Control
n
Flow Control is a technique for speed-matching of transmitter and receiver. Flow control ensures that a transmitting station does not overflow a receiving station with data We will discuss two protocols for flow control:
n n
Stop-and-Wait Sliding Window
For the time being, we assume that we have a perfect channel (no errors)
2
Copyright by Jorg Liebeherr 98,99
Stop-and-Wait Flow Control
n n
Simplest form of flow control In Stop-and-Wait flow control, the receiver indicates its readiness to receive data for each frame Operations:
1. Sender: Transmit a single frame 2. Receiver: Transmit acknowledgment (ACK) 3. Goto 1.
Copyright by Jorg Liebeherr 98,99
Analysis of Stop-and-Wait
Last bit received End of Transmit of ACK
Receiver
propagation delay
Frame
ACK
Efficiency = ?
Frame
transmission delay Start Transmit End Transmit
ACK
Sender
Last bit of ACK received
Copyright by Jorg Liebeherr 98,99
Sliding Window Flow Control
n
Major Drawback of Stop-and-Wait Flow Control:
n
Only one frame can be in transmission at a time This leads to inefficiency if propagation delay is much longer than the transmission delay Allows transmission of multiple frames Assigns each frame a k-bit sequence number Range of sequence number is [0..2k-1], i.e., frames are counted modulo 2 k 5
Sliding Window Flow Control
n n n
Copyright by Jorg Liebeherr 98,99
Operation of Sliding Window
n
Sending Window:
n
At any instant, the sender is permitted to send frames with sequence numbers in a certain range (the sending window)
Frames already transmitted Window of frames that may be transmitted
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6
Frame sequence number
Copyright by Jorg Liebeherr 98,99
Last frame transmitted Window shrinks as frames are sent
Window expands as acknowledgements are received
Operation of Sliding Window
n
Receiving Window:
n
The receiver maintains a receiving window corresponding to the sequence numbers of frames that are accepted
Frames already received Window of frames that are accepted by receiver
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6
Last frame acknowledged Window shrinks as frames are received
Copyright by Jorg Liebeherr 98,99
Window expands as acknowledgements are sent
Operation of Sliding Window
n
How is flow control achieved?
n
Receiver can control the size of the sending window By limiting the size of the sending window data flow from sender to receiver can be limited
Interpretation of ACK N message:
n
Receiver acknowledges all packets until (but not including) sequence number N
8
Copyright by Jorg Liebeherr 98,99
Example
Transmitter 0 1 2 3 4 5 6 7 0 1 2 3 F0 F1 F2 0 1 2 3 4 5 6 7 0 1 2 3 Receiver 0 1 2 3 4 5 6 7 0 1 2 3
0 1 2 3 4 5 6 7 0 1 2 3 ACK4 3 0 1 2 3 4 5 6 7 0 1 2 3
0 1 2 3 4 5 6 7 0 1 2 3
Copyright by Jorg Liebeherr 98,99
Example Continued
Transmitter 0 1 2 3 4 5 6 7 0 1 2 3 F3 0 1 2 3 4 5 6 7 0 1 2 3 F4 F5 F6 0 1 2 3 4 5 6 7 0 1 2 3 ACK3 4 0 1 2 3 4 5 6 7 0 1 2 3 Receiver
0 1 2 3 4 5 6 7 0 1 2 3
0 1 2 3 4 5 6 7 0 1 2 3
Copyright by Jorg Liebeherr 98,99
10
Analysis of Sliding Windows
0 a 1st frame received a+1 Wth frame received a+W
Receiver
...
0 1 2 W
W
Sender
2a+1 1st ACK received
11
Copyright by Jorg Liebeherr 98,99
Analysis of Sliding Windows
n
If the window size is sufficiently large the sender can continuously transmit packets: W 2a+1: Sender can transmit continuously
normalized efficiency = 1
W < 2a+1: Sender can transmit W frames every 2a+1 time units
normalized efficiency = W 1 + 2a
12
Copyright by Jorg Liebeherr 98,99
ARQ Error Control
n n
Types of errors: Lost frames, damaged frames Most Error Control techniques are based on (1) Error Detection Scheme (e.g., Parity checks, CRC), and (2) Retransmission Scheme Error control schemes that involve error detection and retransmission of lost or corrupted frames are referred to as Automatic Repeat Request (ARQ) error control
13
Copyright by Jorg Liebeherr 98,99
ARQ Schemes
n
The most schemes:
n
common
ARQ
retransmission
Stop-and-Wait ARQ Go-Back-N ARQ Selective Repeat ARQ
The protocol for sending ACKs in all ARQ protocols are based on the sliding window flow control scheme
14
Copyright by Jorg Liebeherr 98,99
Stop-and-Wait ARQ
n
Stop-and-Wait ARQ is an addition to the Stop-andWait flow control protocol: Frames have 1-bit sequence numbers (SN = 0 or 1) Receiver sends an ACK (1-SN) if frame SN is correctly received Sender waits for an ACK (1-SN) before transmitting the next frame with sequence number 1-SN If sender does not receive anything before a timeout value expires, it retransmits frame SN
15
n n
Copyright by Jorg Liebeherr 98,99
Stop-and-Wait ARQ
n
Lost Frame
ACK 0 ACK 1 Frame 1 Frame Frame
Timeout
A
ACK 0 Frame 1
B
Copyright by Jorg Liebeherr 98,99
16
Stop-and-Wait ARQ
n
Lost ACK
ACK 0 Frame 1 Frame
Timeout
A
ACK 1 Frame
B
Copyright by Jorg Liebeherr 98,99
ACK 1
Go-Back-N ARQ
n
Go-Back-N uses the sliding window flow control protocol. If no errors occur the operations are identical to Sliding Window
0
17 18
Copyright by Jorg Liebeherr 98,99
Go-Back-N ARQ
n
Operations:
n
A station may send multiple frames as allowed by the window size Receiver sends a NAK i if frame i is in error. After that, the receiver discards all incoming frames until the frame in error was correctly retransmitted If sender receives a NAK i it will retransmit frame i and all packets i+1, i+2,... which have been sent, but not been acknowledged
19
Copyright by Jorg Liebeherr 98,99
Go-Back-N ARQ
n
Lost Frame
Frame 0 Frame Frame Frame Frame
Frames 4,5,6 are retransmitted
Frame Frame
A
Frame Frame Frame
NAK 4
B
Frames 5 and 6 are discarded
20
Copyright by Jorg Liebeherr 98,99
ACK 3
ACK 6
10
Go-Back-N ARQ
n
Lost ACK
Timeout
Frames 0-4 are retransmitted
A
Frame Frame 0 Frame 1 Frame 2
ACK 3
ACK 3
B
Copyright by Jorg Liebeherr 98,99
Frames 3 and 4 are discarded
ACK 5
Selective-Repeat ARQ
n
Similar to Go-Back-N ARQ. However, the sender only retransmits frames for which a NAK is received Advantage over Go-Back-N:
n
Frame 3
Frame 4
Frame 0
Frame 1
Frame 2
Frame 4
Frame 5
21
Fewer Retransmissions.
Disadvantages:
n n
More complexity at sender and receiver Each frame must be acknowledged individually (no cumulative acknowledgements) Receiver may receive frames out of sequence
22
n
Copyright by Jorg Liebeherr 98,99
11
Selective-Repeat ARQ
n
Lost Frame
Frame 0 Frame Frame Frame Frame
only Frame 4 is retransmitted
Frame Frame
A
Frame Frame Frame
ACK 6, NAK 4 ACK 7
ACK 3
ACK 4
ACK 5
B
Frames 5 and 6 are buffered
Copyright by Jorg Liebeherr 98,99
ACK 2
ACK 0
ACK 1
ACK 1
Example of Selective-Repeat ARQ
Frames waiting for ACK/NAK
1 2 3 2 3 4 2 3 4 5
Frames received
ACK2 frame 1 is correct, send ACK 2
Receiver must keep track of `holes in the sequence of delivered frames Sender must maintain one timer per outstanding packet
0
23
3
NAK2
frame 2 is in error, send NAK2
retransmit frame 2
1 3 4
24
Copyright by Jorg Liebeherr 98,99
12