핵심 인사이트 (3줄 요약)

  1. 본질: 칸 알고리즘(Karn's Algorithm)은 TCP가 패킷을 재전송했을 때 뒤늦게 날아온 영수증(ACK)을 보고, "이게 처음 쏜 게 온 건지, 재전송한 게 온 건지" 도저히 구분할 수 없어 타이머 계산(RTT)이 오염되는 치명적 딜레마(재전송의 모호성)를 막기 위해 필 베일(Phil Karn)이 도입한 철통 방어 룰이다.
  2. 재전송 ACK의 완전한 무시 (Ignore): 칸의 법칙은 아주 명쾌하다. "네가 재전송(Retransmit)을 한 번이라도 때린 패킷에 대해서 날아온 영수증은, 그 출처가 썩은 물인지 맑은 물인지 알 수 없으니 무조건 타이머 평균 계산(SRTT)에서 완전히 배제하고 버려라!"
  3. 타이머 백오프 (Timer Backoff): 재전송한 ACK를 무시하면 타이머가 갱신되지 않는데, 계속 통신이 안 되면 어떡할까? 칸은 **"재전송을 할 때마다 묻지도 따지지도 않고 대기 시간(RTO)을 강제로 2배씩 뻥튀기시켜라(Exponential Backoff)!"**라는 두 번째 룰을 박아넣어 네트워크 붕괴를 이중으로 막아냈다.

Ⅰ. 개요 및 필요성 (Context & Necessity)

  • 개념: TCP의 RTT(Round Trip Time) 측정 시, 재전송된 세그먼트에 대한 응답(ACK)을 RTT 샘플 산출에서 배제하고, 재전송 발생 시 RTO를 지수 함수적으로 증가시키는 혼잡 회피 알고리즘 (RFC 2988).

  • 필요성: 내 PC가 구글에 패킷을 쐈다. 3초(RTO)를 기다렸는데 영수증이 안 온다. 나는 눈물을 머금고 패킷을 다시(재전송) 쐈다. 그런데 재전송을 쏘자마자 0.1초 뒤에 띠링~ 하고 영수증이 도착했다! 내 PC의 멘탈은 박살 난다. "이 영수증... 아까 3초 전에 쐈던 1번이 지각해서 이제 온 걸까? 아니면 방금 0.1초 전에 재전송한 2번이 빛의 속도로 튕겨서 온 걸까?" 만약 1번이 온 건데 2번이 온 줄 알고 "오! 이 동네 핑 0.1초 짱 빠르네!" 착각하고 타이머를 0.1초로 확 줄여버리면? 다음번 패킷부터는 0.1초마다 미친 듯이 재전송 폭풍을 갈겨대어 인터넷이 폭파된다. 이 혼돈(Ambiguity)을 멈출 절대자의 룰이 필요했다.

  • 💡 비유: 칸 알고리즘의 딜레마는 **"택배 중복 발송의 헷갈림"**과 같습니다.

    • 내가 쇼핑몰에서 옷을 시켰는데 1주일이 지나도 안 와서 "다시 보내주세요(재전송)"라고 클레임을 걸었습니다. 쇼핑몰은 오늘 새 옷을 다시 보냈습니다.
    • 그런데 내일 덜컥 택배가 도착했습니다!
    • 딜레마: "이 택배는 1주일 전에 출발해서 8일 만에 온 걸까? 아니면 어제 새로 보낸 게 하루 만에 특급으로 온 걸까?" 박스 겉면만 봐서는 도저히 알 길이 없습니다. 배송 기간(RTT)을 측정할 수가 없습니다!

📢 섹션 요약 비유: 칸 알고리즘은 오염된 증거물에 대한 **"법정 증거 능력을 원천 무효화"**하는 판사의 철퇴입니다. "출처가 확실하지 않은 영수증(재전송된 ACK)은 우리 동네 평균 속도(SRTT)를 계산하는 데 단 한 방울도 섞지 말고 즉각 폐기하라!"는 가차 없는 위생 관리법입니다.

Ⅱ. 칸 알고리즘의 2대 룰과 백오프(Backoff) (Deep Dive)

1. 제1법칙: 재전송 ACK는 쓰레기통으로 (Ignore)

  • 송신자가 한 번이라도 재전송(Retransmit) 버튼을 누른 시퀀스 번호에 대해서는, 나중에 돌아오는 ACK를 RTT 샘플로 절대 채택하지 않는다.
  • 이 규칙 덕분에 TCP의 초시계(RTO)는 유령 패킷에 속아 비정상적으로 짧아지는(그래서 미친 재전송 폭풍을 유발하는) 대참사를 완벽하게 피하게 되었다.

2. 제2법칙: 타이머 2배 뻥튀기 (Exponential Backoff)

제1법칙만 쓰면 치명적인 모순이 생긴다. 네트워크가 진짜 막혀서 재전송을 했는데, 재전송 영수증을 RTT 계산에서 무시해 버리면? 내 PC의 타이머(RTO)는 갱신되지 않고 영원히 과거의 짧은 시간(예: 1초)으로 고정되어 버린다! 길이 막혔는데 타이머를 늘려주지 않으면 계속 1초마다 재전송을 때릴 것이다.

  • 칸의 천재적인 2번째 룰: "야! 영수증 무시하는 건 좋은데, 네가 재전송을 했다는 것 자체가 지금 톨게이트 꽉 막혔다는 증거잖아! 재전송 버튼을 누를 때마다 무조건 기존 타이머(RTO)를 2배로 늘려버려!"
  • 최초 RTO가 1초였다면 -> 첫 재전송 시 2초 대기 -> 두 번째 재전송 시 4초 대기 -> 8초 대기 -> 16초 대기...
  • 길이 막혔을 때 스스로 숨을 꾹 참으며 대기 시간을 늘려주는 이 타이머 백오프(Timer Backoff) 기술 덕분에 라우터들은 한숨을 돌릴 수 있게 되었다.
 ┌─────────────────────────────────────────────────────────────┐
 │                칸 알고리즘(Karn's Algo)의 타임아웃 방어 시퀀스     │
 ├─────────────────────────────────────────────────────────────┤
 │                                                             │
 │   [ 평소 ] (현재 RTO 타이머 = 1초)                              │
 │   - 패킷 전송 -> ACK 무사 도착! -> RTT 측정해서 1.1초로 갱신함.      │
 │                                                             │
 │   [ 꽉 막힌 지옥 ]                                             │
 │   - 패킷 전송 -> 1초 지남 -> 타임아웃 펑! (패킷 잃어버렸어!)           │
 │   - Karn의 개입 1: "오케이 재전송 갈겨! 대신 RTO를 2초(2배)로 늘려 놔!"│
 │   - 2초 지남 -> 타임아웃 또 펑!                                  │
 │   - Karn의 개입 2: "또 재전송해! RTO는 4초(2배)로 또 늘려!!"        │
 │                                                             │
 │   [ 기적의 영수증 도착 ]                                         │
 │   - 재전송 후 드디어 ACK 도착!!                                   │
 │   - Karn의 철퇴: "야! 이거 첫 번째 건지 두 번째 건지 모르잖아!        │
 │                 얘는 RTT 평균 계산식에 절.대. 넣지 마!! 무시해!"    │
 └─────────────────────────────────────────────────────────────┘

📢 섹션 요약 비유: 타이머 백오프(Timer Backoff)는 화난 여자친구에게 **"다시 카톡 보내는 타이밍"**과 같습니다. 10분 만에 답장이 안 온다고 다시 카톡(재전송)을 보냅니다. 또 안 오면 이번엔 10분이 아니라 20분을 참고, 또 안 오면 40분을 참고 기다려주는 것이 둘 사이(네트워크)의 완전한 파국을 막는 고도의 눈치 게임(Karn's Algorithm)입니다.