Timeout
- sender는 segment를 보내고 그에 대한 ACK을 일정 시간만큼 기다린다
RTO : Retransmission TimeOut
- ACK이 도착하면, timer는 제거된다
- ACK이 도착하지 않아서 timer가 expired되면,
TIMEOUT이 발생하고, segment는 재전송된다.
- 그렇다면, sender가 얼마나 기다려야 할까?
- 만약 RTO가 너무 작으면 segment가 lost되지도 않았는데 timeout이 발생할 수 있다.
- 그렇다고 RTO가 너무 크면 segment가 lost되었을 때 어차피 재전송할 거 sender가 쓸데없이 너무 많은 시간을 사용하게 된다.
Proper RTO
- RTT + margin
- margin은 RTT variation을 handle할 필요가 있다
- 근데 TCP는 end-to-end protocol이기 때문에,
RTT를 아는 게 쉽지가 않다.
- 또한, RTT는 시간에 따라 변할 수가 있다.
- intermediate router들의 상태에 depends on
- RTT를 어떻게 측정해야 하는가?
- 적절한 margin은 어느 정도인가?
RTT Estimation
Original Algorithm
- sending data 와 receving ACK을 통해 RTT를 측정한다.
- exponential averaging을 통해 EstimatedRTT를 계산한다
- EstimatedRTT = a * EstimatedRTT + (1-a) * sampleRTT
- RTO = 2 * EstimatedRTT
- margin을 추가하기 위해, 그냥 2배 해버려
Original Algorithm : Problem
- 만약 segment가 재전송되고 ACK이 왔으면, 그 ACK이
original segment에 대한 ACK인지 retransmitted segment에 대한 ACK인지 알 수가 없다.
Karn / Partridge Algorithm
- 재전송한 segment의 ACK은 SampleRTT로 사용하지 않는다
Karn / Partridge Algorithm : Problem
- 재전송 segment에 대해서는 SampleRTT 계산을 안하니까,
계속 재전송되면, 계속 SampleRTT을 안잡고,
RTT가 update되지 않고, 계속 timeout이 발생한다.
- 그래서, timeout이 발생하면 RTT를 두 배로 늘린다.
exponential backoff
Jacobson / Karels Algorithm
- RTT의 variation을 고려한다.
- variation이 작으면, margin을 작게 잡고,
variation이 크면, margin을 크게 잡는다.
- Difference = SampleRTT - EstimatedRTT
- Deviation = Deviation + 𝛿 * (|Difference| - Deviation)
- EstimatedRTT = EstimatedRTT + (𝛿 * Difference)
- RTO = EstimatedRTT + 4 * Deviation
Fast Retransmission and
Fast Recovery
Fast Retransmission
- Segment가 lost되면, sender는 언제 timeout이 일어났는지 알게 된다
- 하지만, 시간이 너무 오래 걸린다
- Fast Retransimission은 segment loss를 빠르게 detect하고, segment를 빠르게 재전송할 수 있도록 해준다.
- 같은 data를 보내달라는 ACK이 여러 개가 온다 : duplicate ACK
- duplicate ACK이 많이 온다는 건,
- 1, 3, 4, 5 가 먼저 도착하고, 2 가 느리게 가고 있거나
- 2가 drop되었다.
- 하나의 segment에 대해 3개의 duplicate ACK이 오면,
the segment is considered lost
and retransmit the segment
Indication of a Segment Loss
- Slow start + Congestion Avoidance + Fast Retransmission
= TCP Tahoe (1988)
Fast Recovery
- segment loss가 detect되었을 때, CWND is reset to 1
하지만 이러면 속도가 너무 급격하게 줄어든다.
- 3 duplicate ACK으로 segment loss가 감지되었을 때,
slow start로 가지 말고
restart from the congestion avoidance phase
- 즉, 1로 돌아가지 말고 절반으로 돌아가자
- SSThresh = CWND / 2
- CWND = SSThresh
- TCP Tahoe + Fast Recovery
= TCP Reno (1990)
TCP Congestion Control
- Timeout -> Slow start
- Fast retransmission -> Congestion avoidance