TCP Congestion control

KVV·2024년 12월 4일
컴퓨터네트워크

전통적인 TCP는 "End system" 간의 Congestion control을 사용한다.

A) Traditional TCP Congestion control

TCP는 Network Congestion에 따라 연결에 트래픽을 보내는 전송률을 각 송신자가 제한하도록 한다.

  • Congestion이 없다면? 송신자는 송신율을 높인다.
  • Congestion이 있다면? 송신자는 송신율을 줄인다.

세 가지 주요 방법

1. TCP 송신자가 연결로 Traffic을 보내는 전송률을 어떻게 제한하는가?

  • congestion window (cwnd)라는 추가적인 변수를 추적한다.
  • 이는 TCP 송신자가 Network로 Traffic을 전송할 수 있는 속도에 제약을 가한다.
  • min{cwnd, rwnd} ≥\ge LastByteSent - LastByteAcked

TCP Receive buffer가 매우 크다고 가정한다면

  • cwnd 만큼의 Segment는 항상 전송된다.
  • RTT 시작 때마다 cwnd 만큼의 데이터가 전송되므로, 송신자의 송신 속도는 대략 cwnd/RTT byte/s 이다.

2. TCP 송신자는 Network에 Congestion이 존재하는지 어떻게 감지하는가?

Loss event: Timeout 또는 수신자로부터 3개의 Duplicate ACK의 수신이 발생했을 한 경우 TCP 송신자 측에 발생하는 Event

  • Congestion이 발생하면, 경로에 있는 하나 이상의 Router buffer들이 overflow되고 TCP Datagram이 버려지며 Loss event를 발생시킨다.
  • Loss event가 발생하면 TCP 송신자는 Congestion을 감지할 수 있다.

이 과정에서 Congestion이 존재하지 않으며 Loss event도 발생하지 않는다. TCP Acknowledgment 또한 정상적으로 TCP 송신자에 도착한다.

  • TCP는 확인 응답이 높은 속도로 도착하면 Congestion window를 빠르게 증가시키고, 느린 속도로 도착하면 Congestion window를 느리게 증가시킨다.

  • Self-clocking: TCP가 확인 응답을 Congestion window size의 증가를 유발하는 Trigger, clock으로 사용한다.

3. TCP 송신자는 자신이 송신할 속도를 어떻게 셜정하는가?

처리 원칙

a. 손실된 Segment는 Congestion을 의미하며, 이에 따라 TCP 전송률은 한 Segment를 손실했을 때 줄어야 한다.

b. 확인 응답된 Segment는 Network가 송신자의 Segment를 수신자에게 전송된다는 것이고, 이에 따라 이전에 확인 응답되지 않은 Segment에 대해 ACK가 도착하면 송신자의 전송률은 증가할 수 있다.

  • Network에 Congestion이 존재하는 의미를 함축한다.

c. Bandswidth 탐색

  • Loss event가 발생하기 전까지는 전송률을 증가시키고, Loss event가 발생한 순간부터 전송률을 감소시킨다.

TCP Congestion-control algorithm

세 가지의 구성 요소를 가진다.

1. Slow start

a. TCP Connection이 시작될 때, cwnd 값을 1 MSS로 초기화한다.

  • 이때의 전송률은 MSS/RTT가 된다.
    b. 이후 한 전송 Segment가 첫 번째로 확인 응답을 받을 때마다 cwnd를 1 MSS씩 증가한다.

  • 전송률을 각 단계마다 지수적으로 증가한다.

c. Event가 발생하면 cwnd의 증가를 멈춘다.

  • Timeout이 발생한 경우 cwnd = 1 MSS로 설정하고 새로운 Slow start를 시작한다.
  • ssthresh (slow start threshold) 의 값을 cwnd/2 (혼잡이 검출되었을 시점의 cwnd)로 정하고 ssthresh = cwnd 라면 slow start를 종료하고 Congestion avoidance 상태로 전환한다.

2. Congestion avoidance

a. Congestion avoidance로 전환되는 시점에서 cwnd 값은 Congestion이 검출되었을 때의 값의 절반으로 업데이트 된다.

b. Congestion이 한 번 검출된 상태이기 때문에 cwnd 값을 RTT마다 1 MSS씩 증가시키는 보수적인 방법을 사용한다.

  • 각 Segment의 첫 번째 확인 응답을 받을 때마다 TCP 송신자가 cwnd를 MSS byte (MSS/cwnd) 만큼 증가시킨다.
  • 이 경우에는 선형적인 증가 형태를 가진다.

c. Event가 발생하면 Congestion을 종료한다.

  • Timeout이 발생한 경우 cwnd = 1 MSS로 설정하고 ssthreash의 값은 Loss event가 발생할 때의 cwnd 값의 반으로 설정한다.

  • Duplicate ACK를 받은 경우, cwnd의 값을 반으로 줄이고 ssthresh 값을 cwnd 값의 반으로 기록한다. 이후 Fast Recovery 상태로 전환한다.

3. Fast Recovery

필수 요소는 아니지만 초기 TCP 버전인 TCP Tahoe는 채택하지 않았지만, TCP Reno는 채택하였다.

  1. 손실된 Segment에 대해 수신된 모든 Duplicate ACK에 대해 cwnd 값은 1 MSS만큼 증가시킨다.

  2. 만약 손실된 Segment에 대한 ACK가 도착하면 TCP는 cwnd Congestion avoidance 상태로 들어간다.

  3. 만약 Timeout이 발생한다면 cwnd = 1 MSS, ssthresh 값을 cwnd 값의 반으로 기록한 후 Slow start 상태로 전환한다.

TCP Congestion control에 대한 정리

AIMD(additive-increase multiplicative-decrease) Congestion control 이라고도 불린다.

손실이 Timeout이 아니라, 3개의 Duplicate ACK로 표시된다고 가정하자.

  • TCP는 RTT마다 1 MSS씩 cwnd의 additive-increase
  • 3개의 Duplicate ACK에 대해 multiplicative-decrease

TCP CUBIC

cwnd = 1 MSS로 초기화된 이후, 패킷 손실 발생 임곗값보다 바로 아래의 패킷 전송 속도를 즉시 탐색하는 방법

Congestion avoidance를 수정하였다.

  • WmaxW_{max}손실이 마지막으로 감지되었을 때의 window size
  • K: window size가 다시 WmaxW_{max}에 도달하는 미래 시각

✅ 큐빅은 혼잡 윈도를 현재 시각 t와 K 시각 사이 거리의 세제곱 함수로 증가시킨다.

  • t가 K에 가까울 때보다 멀리 떨어졌을 때 혼잡 윈도 크기 증가가 훨씬 더 커진다.

✅ 큐빅은 손실 전 속도인 WmaxW_{max}에 가까워지도록 TCP의 전송 속도를 빠르게 증가시킨 다음, WmaxW_{max}에 가까워지면 대역폭을 조심스럽게 탐지한다.

✅ 손실을 유발한 링크의 수준이 크게 변경된 경우 큐빅이 새 작동 지점을 더 빨리 찾을 수 있다.

  • t가 K에 가까울 때는 큐빅의 혼잡 윈도 증가가 작다.
  • t가 K를 크게 초과함에 따라 혼잡 윈도가 급격히 증가한다.

TCP Reno의 처리율

TCP의 Steadt-state를 가정하며, Slow start 부분은 무시한다.

  • Window size = w, Loss event가 발생하는 시점 = W라 하면 현재 전송률은 w/RTT이다.
  • W 이전까지는 w를 RTT마다 1 MSS씩 증가시킨다.
  • TCP 전송률은 W/(2 ⋅\cdot RTT) ~ W/RTT 까지의 범위를 갖는다.
    • Loss event가 발생하면 cwnd가 절반으로 줄어들기 때문이다.
    • 따라서 평균 처리율은 다음과 같다.

B) 네트워크 지원 혼잡 제어

1. Explicit Congestion Notification (ECN)

혼잡해지는 Router에서 Buffer가 가득 차서 Packet이 삭제되기 전에 송신자에게 혼잡 시작을 알리는 혼잡 알림 비트를 설정할 수 있다. 즉, 패킷 손실 이전에 전송 속도를 줄여 패킷 손실이 발생하기 전에 혼잡 시작을 사전에 감지할 수 있다.

  1. 한 Router에서 Congestion이 발생하면 IP datagran의 Type of Service field에 있는 ENC 2 bit를 설정한다.

    • 한 비트는 Router에 Congestion이 존재한다는 것을 의미
    • 나머지 한 비트는 Router에게 송수신자가 ECN bit를 설정할 수 있다는 것을 알려준다.

  2. 수신 Host가 ECN를 수신하면 수신자는 수신자-송신자 TCP ACK Segment의 ECE(Explicit Congestion Notification Echo) bit를 설정하여 TCP에 혼잡 표시를 알린다.

  3. ECE echo를 받으면 송신자는 cwnd를 절반으로 줄이고 다음 전송되는 TCP 수신자 Segment Header에 CWR (Congestion Window Reduced) bit를 1로 설정한다.

2. Delay-based Congestion Control

RTTminRTT_{min}: 혼잡하지 않을 때의 RTT
cwnd/RTTminRTT_{min}: 혼잡하지 않을 때의 처리율

  • 만약 현재의 처리율이 cwnd/RTTminRTT_{min}보다 현저히 작으면 전송 속도를 낮춘다.
  • 만약 현재의 처리율이 cwnd/RTTminRTT_{min}과 비슷하면 전송 속도를 높인다.

C) 공평성

다른 경로에서, 모두 R bps의 전송률인 Bottleneck link를 지나는 K개의 TCP 연결에서, 각 연결의 평균 전송률이 R/K에 가깝다면 혼잡 제어 메커니즘이 공평하다고 할 수 있다.

  • 두 연결이 같은 MSS와 RTT를 가진다고 가정하자.

  • 두 연결 사이에서 링크 대역폭을 똑같이 공유하는 경우는 45도 각도의 화살표를 따르는 것이다.

  • 이상적으로는 완전한 대역폭 이용 선에 근접해야한다.

A: 두 연결에 의해 소비되는 링크 대역폭이 R보다 적으므로, 어떠한 손실도 발생하지 않는다.

  • 두 연결은 RTT당 1 MSS씩 window를 증가시킨다.

B: A이후 B의결과를 얻을 수 있다. 이 경우 패킷 손실이 발생할 수 있는데 이때 cnwd를 절반씩 줄여 C 위치에 위치하게 된다.

C: A와 동일하다.

D: B와 동일하다

과정을 거치게 되면 동등한 대역폭 공유 선으로 수렴한다. 이는 TCP가 연결 사이에서 대역폭을 똑같이 공유하는지를 보여준다.

profile
KVV
이전 포스트

Principle of Congestion Control

다음 포스트

Network Layer introduction

0개의 댓글