[Network] TCP 혼잡 제어 알고리즘의 3가지 요소와 혼잡 제어 모델 정리

---

전통적인 TCP의 혼잡 제어

• 종단 간의 혼잡 제어를 사용

 

---

TCP의 접근 방식

• 네트워크 혼잡에 따라 연결에 트래픽을 보내는 전송률을 각 송신자가 제한하도록 함
  • TCP 송신자가 자신과 목적지 간의 경로에서 혼잡이 없음을 감지
    → 송신자는 송신율을 높임
    
    
  • 송신자가 경로 사이에 혼잡을 감지
    → 송신자는 송신율을 낮춤

 

TCP 송신자가 연결로 트래픽을 보내는 전송률을 제한하는 방법

• 송신 측에서 동작하는 TCP 혼잡 제어 메커니즘은 추가적인 변수인 혼잡 윈도를 추적
  • 혼잡 윈도(congestion window, cwnd)
    • TCP 송신자가 네트워크로 트래픽을 전송할 수 있는 속도에 제약을 가함
      
      
• LastByteSent - LastByteAcked ≤ min(cwnd, rwnd)
  → 송신하는 쪽에서 확인응답이 안 된 데이터의 양은 cwnd와 rwnd의 최솟값을 초과 X
  
  
• cwnd의 값을 조절하여, 송신자는 링크에 데이터를 전송하는 속도를 조절 가능
  • 가정
    • 송신자의 확인응답이 안 된 데이터의 양은 오로지 cwnd에 의해 한정됨
      • 수신 윈도의 제약 조건을 무시할 정도로 TCP 수신 버퍼가 큰 경우 가능
        
        
    • 송신자가 항상 보낼 데이터가 있다고 가정 → 혼잡 윈도의 모든 세그먼트는 전송됨
      
      
  • 위의 가정은 송신자에서 확인응답 안 된 데이터 크기와 송신자의 송신 속도를 간접 제한
    • 이유 - 손실과 패킷 전송 지연이 무시될 수 있는 연결 고려
      1. 매 왕복 시간(RTT)의 시작 때, 송신자는 cwnd바이트만큼 데이터 전송 가능
         • 이는 위 가정에 따라 cwnd에 의해서만 한정될 때
           
           
      2. RTT가 끝나는 시점에 데이터에 대한 확인응답을 수신
         → 송신자의 송신 속도 = 대략 cwnd/RTT바이트/초

 

TCP 송신자가 전송 경로 사이에 혼잡이 존재하는지 감지하는 법

• TCP 송신자 측에 손실 이벤트(loss event) 발생
  • 손실 이벤트 발생 원인
    • 타임아웃
    • 수신자로부터 3개의 중복된 ACK의 수신이 발생했을 때
      
      
• 과도한 혼잡이 발생하면, 경로에 있는 하나 이상의 라우터 버퍼들이 오버플로
  → 그 결과, TCP가 포함된 데이터그램이 버려진다.
  → 버려진 데이터그램은 송신 측에서 손실 이벤트를 발생시킴
  → 송신자는 송/수신자 사이의 경로상의 혼잡이 발생했음을 알게 됨
  
  
• 손실 이벤트가 발생하지 않는 네트워크가 혼잡이 없는 경우(낙관적인 경우)
  • 이전에 확인응답 안 된 세그먼트들에 대한 확인응답들이 TCP 송신자에서 수신됨
    • TCP는 모든 것이 올바르게 동작하고 있다는 표시로 이 확인응답을 받음
    • TCP는 혼잡 윈도 크기와 이것의 전송률을 증가시키기 위해 확인응답을 사용
      
      
• TCP는 확인응답을 혼잡 윈도 크기의 증가를 유발하는 트리거 또는 클록(clock)으로 사용
  → 자체 클로킹(self-clocking)이라고 함.
  • 확인 응답이 상대적으로 늦은 속도로 도착한 경우
    → 혼잡 윈도는 상대적으로 낮은 속도로 증가
    • 원인
      • 종단 간의 경로가 높은 지연을 가질 때
      • 낮은 대역폭 링크를 포함할 때
        
        
  • 확인 응답이 높은 속도로 도착하는 경우
    → 혼잡 윈도는 더 빨리 증가

 

전송률(송신율)을 변화를 위한 메커니즘 선택 방법

• TCP 송신율 결정을 위한 2가지 주요 사항 → 아래 2가지를 만족시키는 전송률?
  1. TCP 송신자들은 가용한 대역폭을 최대한 사용해야 함
  2. 반면에 네트워크를 혼잡시키지 않아야 함
     
     
• TCP 처리 원칙
  • 손실된 세그먼트는 혼잡을 의미, 즉 TCP 전송률은 한 세그먼트를 손실했을 때 줄여야 한다.
    • 타임아웃 이벤트나 4개의 확인응답의 수신은 손실 세그먼트의 재전송을 야기한다.
      • 4개의 ACK 세그먼트가 묵시적으로 손실 이벤트 지시로 해석됨
      • 4개의 확인 응답 = 하나의 원래 ACK와 3개의 중복된 ACK
        
        
    • 혼잡 제어 관점에서 문제
      • TCP 송신자가 혼잡 윈도 크기의 전송률을 줄이는 방법
      • 혼잡 윈도 크기에 따른 손실 이벤트에 대응하는 전송률을 줄이는 방법
        
        
  • 확인응답된 세그먼트는 네트워크가 송신자의 세그먼트를 수신자에게 전송된다는 것,
    즉, 전에 확인응답되지 않은 세그먼트에 대해 ACK가 도착하면 송신자의 전송률은 증가 가능
    • 확인응답 도착의 의미
      → 세그먼트들이 성공적으로 전송되었고, 네트워크는 혼잡하지 않다.
      → 모든 것이 좋다는 묵시적 표시로 받아들여짐
      → 혼잡 윈도 크기가 증가할 수 있다.
      
      
• 대역폭 탐색
  • ACK와 손실 이벤트가 주어질 때 TCP의 전송률을 조정하는 TCP의 전략
    • 이때의 ACK → 혼잡이 없는 출발지에서 목적지까지의 경로를 표시
    • 이때의 손실 이벤트 → 혼잡한 경로를 표시
    • TCP 송신자의 전송률 탐색 방법
      • 손실 이벤트가 발생할 때까지는 ACK가 도착함에 따라 전송률을 증가시킴
      • 손실 이벤트가 발생한 시점에서 전송률을 줄인다.
      • 전송률을 줄인 이후부터는, 다시 혼잡 시작이 발생했는지를 보기 위해 탐색 시작
        
        
  • 네트워크에 의한 혼잡 상태의 어떠한 명시적인 신호가 없다.
    • ACK와 손실 이벤트는 묵시적 신호
      
      
  • 각 TCP 송신자들은 다른 TCP 송신자들과는 비동기적으로 로컬 정보에 근거해 동작

 

 

---

TCP 혼잡 제어 알고리즘

(TCP congestion-control algorithm)

• 위의 이러한 개념을 바탕으로 TCP 혼잡 제어 알고리즘을 상세히 고려
• 이 알고리즘은 중요한 3가지 구성 요소를 가짐
  1. 슬로 스타트(slow start)
  2. 혼잡 회피(congestion avoidance)
  3. 빠른 회복(fast recovery)
     • 빠른 회복은 권고되지만, TCP 송신자들에게 필수 사항은 아님
       
       
  • 슬로 스타트와 혼잡 회피는 TCP의 필수 요소
    • 수신된 ACK에 대응하여 cwnd 크기를 얼마나 증가시키느냐는 것이 차이

 

---

슬로 스타트

• TCP가 연결이 시작될 때, cwnd의 값은 일반적으로 1 MSS로 초기화됨
  → 그 결과 전송률은 대략 MSS/RTT가 됨
  
  
• TCP 송신자에게 가용 대역폭은 MSS/RTT보다 훨씬 큼
  → TCP 송신자는 가용 대역폭 양을 빠르게 찾고자 함
  
  
• 슬로 스타트 상태에서는 cwnd 값을 1 MSS에서 시작하여,
  한 전송 세그먼트가 첫 번째로 확인응답받을 때마다 1 MSS씩 증가

 

---

슬로 스타트 예시

슬로 스타트

• 동작 과정
  1. TCP 송신자는 첫 번째 세그먼트를 네트워크로 보내고 확인응답을 기다림
  2. TCP 송신자에게 확인응답이 도착하면, 하나의 MSS만큼 혼잡 윈도를 증가시킴
  3. TCP 송신자가 다시 2개의 MSS를 전송
  4. 송신자에게 확인응답이 도착하면, 각 확인응답에 대해 하나의 MSS만큼 혼잡 윈도 증가
     → 4개의 MSS 혼잡 윈도가 주어지게 됨
     
     
  5. 이러한 과정이 반복

→ TCP 전송률은 작은 값으로 시작하지만, 슬로 스타트 동안 지수적으로 증가하게 됨

 

---

전송률의 지수적 증가는 언제 끝날까?

TCP 혼잡제어의 FSM 설명

1. 타임아웃으로 표시되는 손실 이벤트(즉, 혼잡)가 있을 경우
   • 이 경우, TCP 송신자는 cwnd 값을 1로 설정하고 새로운 슬로 스타트를 시작
   • 또한, 두 번째 상태 변수 ssthresh(슬로 스타트 임계값)의 값을 cwnd/2로 정함
     • cwnd/2 = 혼잡이 검출되었을 시점에서의 혼잡 윈도 값의 반
     • ssthresh : 연결을 처음 시작했을 때, 연결에 대한 기본 값
       • 처음에는 네트워크에 대한 정보가 없기 때문에 기본값이 필요
         
         
2. cwnd값이 ssthresh와 같을 경우
   • 이 경우, 슬로 스타트 종료 및 TCP는 혼잡 회피 모드로 전환됨
     • 혼잡 회피 모드에서는 cwnd를 좀 더 조심스럽게 증가시킴
       
       
   • cwnd값이 이 값에 도달하거나 초과할 때 cwnd를 두배로 하는 것은 비효율적
     
     
3. 3개의 중복 ACK가 검출되는 경우
   • 이 경우, TCP는 빠른 재전송을 수행하여 빠른 회복 상태로 들어간다.
     
     

• 슬로 스타트 알고리즘의 동작은 위 그림(TCP 혼잡 제어의 FSM 설명)으로 요약됨

 

---

혼잡 회피

• 혼잡 회피 상태로 들어가는 시점에서 cwnd의 값
  → 대략 혼잡이 마지막으로 발견된 시점(혼잡이 거의 목전에 있을 때)에서의 절반
  → TCP는 좀 더 보수적인 접근법을 채택해야 한다.
  • RTT마다 cwnd값을 2배로 하는 것은 위험함

 

좀 더 보수적인 혼잡 회피 접근법

• 새로운 승인이 도착할 때마다 TCP 송신자가 cwnd를 MSS바이트(MSS/cwnd)만큼 증가
  → RTT마다 하나의 MSS만큼 cwnd 값을 증가시킨다.
  
  • 예시 - MSS가 1460바이트, cwnd가 14,600바이트일 때
    • 10개의 세그먼트가 한 RTT 내에 송신될 수 있다.
    • 각 ACK(세그먼트 당 하나의 ACK라고 가정)는 1/10MS만큼의 혼잡 윈도를 증가
      → 10개의 모든 세그먼트가 수신됐을 때의 ACK들 후, 1 MSS만큼만 혼잡 윈도 증가

 

혼잡 회피(RTT당 1 MSS)의 선형 증가는 언제 끝날 것인가?

• TCP 혼잡 회피 알고리즘은 타임아웃이 발생했을 때 → 슬로 스타트의 경우와 같이 동작
  • cwnd의 값은 1 MSS로 설정
  • ssthresh의 값은 손실 이벤트가 발생할 때의 cwnd 값의 절반으로 설정
    
    
• 3개의 중복된 ACK를 수신했을 때
  • cwnd의 값을 반으로 줄인다.
    • 수신된 3개의 중복 ACK를 설명하기 위해 3 MSS를 더함
      
      
  • ssthresh 값을 cwnd 값의 반으로 기록
  • 이후 빠른 회복 상태로 들어감
  • 이와 같은 행동을 하는 이유
    • 손실 이벤트가 3개의 중복된 ACK 이벤트에 의해 야기된다는 점
      → 이 경우, 네트워크는 송신자로부터의 세그먼트를 수신자에게 계속 전달
      → 이 타입의 손실 이벤트에 대한 TCP의 동작은 타임아웃 표시 손실보다 소극적이어야 함

 

---

빠른 회복

• cwnd 값을 손실된 세그먼트에 대해 수신된 모든 중복된 ACK에 대해 1 MSS 만큼씩 증가
  • 손실된 세그먼트 = TCP를 빠른 회복 상태로 들어가게 했던 세그먼트를 뜻함
    
    
• 손실된 세그먼트에 대한 ACK가 도착하면 TCP는 cwnd 혼잡 회피 상태로 들어감
• 타임아웃 이벤트 발생하는 경우의 단계
  1. cwnd 값은 1 MSS, ssthresh 값은 손실 이벤트가 발생할 때의 cwnd 값의 절반
     • 슬로 스타트와 혼잡 회피에서와 같은 동작을 수행
       
       
  2. 슬로 스타트로 전이한다.

 

TCP에서 빠른 회복의 사용

• 빠른 회복은 TCP 구성요소의 권고사항이지만 필수는 아니다.
  • TCP 타호(TCP Tahoe) : 초기 TCP 버전
    • 타임아웃으로 표시됨
    • 3개의 중복 ACK로 표시되는 손실이 발생 시
      → 무조건 혼잡 윈도를 1 MSS로 줄이고, 슬로 스타트 단계로 들어감
      
      
  • TCP 리노(TCP Reno) : TCP의 새로운 버전
    • 타임아웃 시 → TCP 타호와 똑같이 cwnd를 1 MSS로 줄임
      • 이후 슬로 스타트 단계로 들어감
        
        
    • 3개의 중복 ACK 수신 시 → cwnd를 반으로 줄임
      • 1 MSS씩 증가시킴(조심스럽게 증가)
        
        
    • 여기서는 빠른 회복도 채택하였음

 

리노와 타호에 대한 TCP의 혼잡 윈도 변화

리노와 타호 비교

• 위 그래프에서의 가정
  • 임계값 초기 둘 다 8 MSS
  • 처음 8번 전송 동안은 타호와 리노가 동일한 행동을 취함
    
    
• 혼잡 윈도의 변화
  • 슬로 스타트 동안에 지수적으로 빠르게 증가하고, 4번째 송신에서 임계값에 이름
  • 8번째 송신 후에 3개의 중복 ACK가 발생할 때까지 혼잡 윈도는 선형으로 증가
    • 해당 손실 이벤트가 발생했을 때의 혼잡 윈도는 12 MSS
      → 다음 ssthresh 값은 그 절반인 6 MSS
      
      
• 8번째 전송 후의 리노와 타호의 차이
  • TCP 리노 → 혼잡 윈도가 9 MSS로 설정되고 선형적으로 증가
  • TCP 타호 → 혼잡 윈도는 1 MSS로 설정되고 ssthresh에 도달할 때까지 지수적으로 증가

 

---

TCP 알고리즘에 대한 기타 정리

• 가법적 증가 : TCP의 혼잡 제어는 RTT마다 1 MSS씩 cwnd의 선형 증가.
• 승법적 감소 : 3개의 중복 ACK 이벤트에서 cwnd의 절반화
• TCP 혼잡제어는 종종 가법적 증가, 승법적 감소(AIMD)의 혼잡 제어 형식이라고 부름
• AIMD 혼잡 제어는 톱니 동작이 생기게 한다.

• 위 그림은 대역폭에 대한 TCP 탐색의 초기 직관을 보여준다.
  • TCP는 3개의 중복 ACK 이벤트가 발생할 때까지 선형으로 혼잡 윈도 크기를 증가시킴
  • 이후, 혼잡 윈도 크기를 반으로 감소
  • 다시 추가적인 가용 대역폭이 있는지를 탐색하기 위해 선형으로 증가시키기 시작

 

---

TCP 큐빅

가법적 증가, 승법적 감소 접근 방식에 대한 의문

• TCP 리노는 혼잡 제어에 가법적 증가, 승법적 감소 접근 방식을 사용한다.
  → 패킷 손실 발생 임계값보다 바로 아래의 패킷 전송 속도를 탐색하는 것이 가장 좋은 방법인가?
  
  • 전송 속도를 절반으로 줄인 다음, 다소 천천히 증가시키는 것은 지나치게 보수적이다는 의견

 

TCP 큐빅의 특징

• TCP 큐빅은 TCP의 핵심적인 특징으로 알려진 통찰력이다.
• 패킷 손실이 발생한 혼잡한 링크의 상태가 많이 변경되지 않은 경우,
  전송 속도를 빠르게 높여 손실 전 전송 속도에 근접한 다음, 대역폭을 신중하게 조사

 

TCP 큐빅과 TCP 리노

• 공통점
  • ACK 수신 시에만 혼잡 윈도를 늘리고,
    슬로 스타트 단계와 빠른 복구 단계는 동일하게 유지
    
    
• 차이점 → 큐빅은 혼잡 회피 단계가 수정됐음
  • 큐빅 매개변수들의 역할
    • K값, 즉 프로토콜의 혼잡 윈도 크기가 얼마나 빨리 W(max)에 도달하는지 결정
      • W(max) : 손실이 마지막으로 감지됐을 때, TCP의 혼잡 제어 윈도 크기
      • K : TCP 큐빅의 윈도 크기가 다시 W(max)에 도달하는 미래 시점
        • 이는 손실이 없다고 가정했을 때이다.
          
          
  • 큐빅은 혼잡 윈도를 현재 시각 t와 K 시각 사이 거리의 세제곱 함수로 증가시킴
    • t가 K에 가까울 때보다 멀 때 혼잡 윈도 크기가 훨씬 더 커진다.
    • 큐빅은 손실 전 속도인 W(max)에 가까워지도록 TCP의 전송 속도를 빠르게 증가 후,
      W(max)에 가까워지면 대역폭을 조심스럽게 탐지
      
      
  • t > K 일 때의 큐빅 규칙의 의미
    → t가 K를 크게 초과함에 따라 급격히 증가한다는 것
    → 손실을 유발한 링크의 정체 수준이 크게 변경된 경우 큐빅이 새 작동 지점을 빨리 찾을 수 있음
    • t가 여전히 K에 가까울 때는 큐빅의 혼잡 윈도 증가가 작다.
      • 손실을 유발하는 링크의 혼잡 수준이 많이 변경되지 않은 경우 좋음

 

TCP 리노와 TCP 큐빅의 이상적인 성능 비교

1. 슬로 스타트 단계가 t0에서 끝남
2. 그런 다음 t1, t2, t3에서 혼잡 손실이 발생하면 큐빅은 W(max)에 가깝게 더 빠르게 증가
   → 따라서 TCP 큐빅은 리노보다 더 많은 전체 처리량을 누린다.
   • TCP 큐빅이 혼잡 임계값 바로 아래에서 가능한 오랫동안 흐름 유지하려고 시도
     
     
3. t3에서 정체 수준이 급격히 감소하여 TCP 리노와 큐빅 모두 W(max) 보다 높은 전송 속도 달성

 

---

TCP 리노 처리율의 거시적 설명

TCP 리노 동작에 대한 장시간 연결된 TCP 연결의 평균 처리율 분석

• 해당 분석에서 타임아웃 이벤트 발생 후에 발생하는 슬로 스타트 단계는 무시
  ← 송신자는 지수적으로 빠르게 이 단계를 벗어나서 이 단계는 매우 짧기 때문
  
  
• 하나의 특정 왕복 시간 동안 TCP가 데이터를 보내는 비율
  → 혼잡 윈도와 현재 RTT의 함수
  • 윈도 크기가 w바이트, 왕복 시간이 RTT초인 경우의 TCP 전송률 = w/RTT
    
    
• TCP는 손실 이벤트가 발생할 때까지 RTT당 하나의 MSS만큼 w를 증가시켜 추가 대역폭을 얻음
• RTT와 W 가 대체로 링크 동안 일정하다고 가정할 때의 TCP 전송률
  → W/(2 RTT) ~ W/RTT까지의 범위를 가짐
  • W : 손실 이벤트가 발생하는 시점의 w 값

 

TCP의 안정 상태(steady-state) 동작에 대한 거시 모델

• RTT와 W가 대체로 링크 동안 일정하다는 가정
  → TCP의 안정 상태 동작에 대한 매우 간단한 거시 모델을 제시
  
  
• 비율이 W/RTT까지 증가할 때, 네트워크는 연결로부터 온 패킷을 버린다.
  • 해당 동작의 결과
    • 비율은 절반으로 줄어듦
    • 혼잡 윈도가 다시 W/RTT에 도달할 때까지 왕복 시간당 MSS/RTT만큼 증가
    • 해당 과정을 반복함
      
      
• TCP 처리량이 양 극값 사이에서 선형적으로 증가 → 아래의 식을 얻을 수 있음
  • 이용 가능한 대역폭과 연결의 손실률을 연계하는 식을 유도할 수 있음

연결의 평균 처리율 공식