TCP Error Control
Background on Error Control TCP Error Control
Presented By Prakhyat Goel C07536
Department of Electronics and Electrical Communication Engineering 1
What is Error Control ?
Error Control:
Algorithms to recover or conceal the effects from packet losses
The goal of each of the control mechanisms is different. But the implementation is combined
Background: ARQ Error Control
Two types of errors: Lost packets Damaged packets Most Error Control techniques are based on: 1. Error Detection Scheme (Parity checks, CRC). 2. Retransmission Scheme. Error control schemes that involve error detection and retransmission of lost or corrupted packets are referred to as Automatic Repeat Request (ARQ) error control.
Background: ARQ Error Control
All retransmission schemes use all or a subset of the following procedures: Positive acknowledgments (ACK) Negative acknowledgment (NACK) All retransmission schemes (using ACK, NACK or both) rely on the use of timers The most common ARQ retransmission schemes are: Stop-and-Wait ARQ Go-Back-N ARQ Selective Repeat ARQ
Background: ARQ Error Control
The most common ARQ retransmission schemes: 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
Background: Stop-and-Wait ARQ
Stop-and-Wait ARQ is an addition to the Stop-and-Wait flow control protocol: Packets have 1-bit sequence numbers (SN = 0 or 1) Receiver sends an ACK (1-SN) if packet SN is correctly received Sender waits for an ACK (1-SN) before transmitting the next packet with sequence number 1-SN If sender does not receive anything before a timeout value expires, it retransmits packet SN
Background: Stop-and-Wait ARQ
Lost Packet
Timeout
A
ACK 0 ACK 1 ACK 0 t Packe 1 t Packe 0 t Packe t Packe 1
B
7
Background: Go-Back-N ARQ
Operations:
A station may send multiple packets as allowed by the window size
Receiver sends a NAK i if packet i is in error. After that, the receiver discards all incoming packets until the packet in error was correctly retransmitted If sender receives a NAK i it will retransmit packet i and all packets i+1, i+2,... which have been sent, but not been acknowledged
Example of Go-Back-N ARQ
packets waiting for ACK/NAK
3 2
ACK2 packets received
1 2 3 2 3 4 2 3 4
In Go-back-N, if packets are correctly delivered, they are delivered in the correct sequence Therefore, the receiver does not need to keep track of `holes in the sequence of delivered packets
packet 1 is received, send ACK 2
Time out for Packet 2 retransmit frame 2,3,4
Background: Go-Back-N ARQ
Lost Packet A
t Packe 0 Packe t1 t Packe 2 t Packe 3
Timeout Packets 4,5,6 for Packet 2 are retransmitted
t Packe
t Packe
B
Packets 5 and 6 are discarded
10
ACK 3
AC K 6
Packe t4
t Packe 5
Packe t6
t Packe 6
Background: Selective-Repeat ARQ
Similar to Go-Back-N ARQ. However, the sender only retransmits packets for which a time-out occured is received Advantage over Go-Back-N: Fewer Retransmissions. Disadvantages: More complexity at sender and receiver Each packet must be acknowledged individually (no cumulative acknowledgements) Receiver may receive packets out of sequence
11
Example of Selective-Repeat ARQ
Packets waiting for ACK/NAK
1 2 3 2 3 4 2 3 4 5
Frames received
ACK2 Packet is correct, send ACK 2 Packet 2 does not arrive
Receiver must keep track of `holes in the sequence of delivered packets Sender must maintain one timer per outstanding packet
3
ACK4
ACK5 Following packets are Acked
Timeout for packet 2: retransmit only packet2
1 3 4
12
Background: Selective-Repeat ARQ
Lost Packet A
Packe t Packe t Packe Packe t Packe 0 Packe t1 t Packe 2 t Packe 3 Packe t4 t Packe
Timeout for Packet 4: only Packet 4 is retransmitted
t4
t6
ACK 6
ACK 4
ACK 7
AC K 5
B
Packets 5 and 6 are buffered
13
ACK 2
ACK 3
ACK 0
ACK 1
ACK 1
Error Control in TCP
TCP implements a variation of the Go-back-N retransmission scheme TCP maintains a Retransmission Timer for each connection: The timer is started during a transmission. A timeout causes a retransmission TCP couples error control and congestion control (I.e., it assumes that errors are caused by congestion) TCP allows accelerated retransmissions (Fast Retransmit)
14
TCP Retransmission Timer
Retransmission Timer: The setting of the retransmission timer is crucial for efficiency Timeout value too small results in unnecessary retransmissions Timeout value too large long waiting time before a retransmission can be issued A problem is that the delays in the network are not fixed Therefore, the retransmission timers must be adaptive
15
Round-Trip Time Measurements
The retransmission mechanism of TCP is adaptive The retransmission timers are set based on round-trip time (RTT) measurements that TCP performs
Segment 1
RTT #1
ACK for Segment 1
The RTT is based on time difference between segment transmission and ACK But: TCP does not ACK each segment Each connection has only one timer
Segment 2 Segment 3
RTT #2 RTT #3
ACK for Segment 4 ACK for Segment 5
+3 ACK for Segment 2
Segment 5
Segment 4
16
Round-Trip Time Measurements
Retransmission timer is set to a Retransmission Timeout (RTO) value. RTO is calculated based on the RTT measurements. The RTT measurements are smoothed by the following estimators srtt and rttvar: srttn+1 = RTT + (1- ) srttn rttvarn+1 = ( | RTT - srttn+1 | ) + (1- ) rttvarn RTOn+1 = srttn+1 + 4 rttvarn+1 The gains are set to =1/4 and =1/8 srtt0 = 0 sec, rttvar0 = 3 sec, Also: RTO1 = srtt1 + 2 rttvar1
17
Karns Algorithm
If an ACK for a retransmitted segment is received, the sender cannot tell if the ACK belongs to the original or the retransmission.
segment
T im e o u t !
retransmission of segment
Karns Algorithm: Dont update srtt on any segments that have been retransmitted. Each time when TCP retransmits, it sets: RTOn+1 = max ( 2 RTOn, 64) (exponential backoff)
RTT ? RTT ?
ACK
18
Measuring TCP Retransmission Timers
argon.tcpip-lab.edu ("Argon") Transfer file neon.tcpip-lab.edu ("Neon")
Web client
Web server
Transfer file from Argon to neon Unplug Ethernet of Argon cable in the middle of file transfer
19
Interpreting the Measurements
The interval between retransmission attempts in seconds is: 1.03, 3, 6, 12, 24, 48, 64, 64, 64, 64, 64, 64, 64. Time between retransmissions is doubled each time (Exponential Backoff Algorithm) Timer is not increased beyond 64 seconds TCP gives up after 13th attempt and 9 minutes.
600 500 400
Seconds
300 200 100 0 0 2 4 6 8 10 12 Transmission Attempts
20
THANK YOU
21
