Timeout

• sender는 segment를 보내고 그에 대한 ACK을 일정 시간만큼 기다린다
  RTO : Retransmission TimeOut
• ACK이 도착하면, timer는 제거된다
• ACK이 도착하지 않아서 timer가 expired되면,
  TIMEOUT이 발생하고, segment는 재전송된다.

• 그렇다면, sender가 얼마나 기다려야 할까?
• 만약 RTO가 너무 작으면 segment가 lost되지도 않았는데 timeout이 발생할 수 있다.
• 그렇다고 RTO가 너무 크면 segment가 lost되었을 때 어차피 재전송할 거 sender가 쓸데없이 너무 많은 시간을 사용하게 된다.

• 적절한 RTO는 어느 정도인가?

---

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를 측정한다.
  • 측정된 RTT를 SampleRTT라고 한다.

• 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)
  • 0 ≤ 𝛿 ≤ 1

• 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

• Timeout
• 3 duplicate ACKs

• 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