Principles of congestion control (1)

1. Congestion control

• 네트워크 혼잡 (네트워크에서의 데이터 트래픽이 과도하게 많거나 관리되지 않을 때 발생하는 상황)을 관리하고 제어하기 위한 기술 및 메커니즘

• 네트워크 혼잡이 발생하면 패킷이 queueing 됨에 따라 긴 지연 시간이 발생하거나, 라우터 버퍼가 꽉 차게 되면 overflow되어 packet loss가 발생할 수 있다.

• flow control VS congestion control

  • flow control: 수신자와 송신자 사이의 통신에서 수신자의 수신 버퍼 상태를 확인하여, 데이터를 전송하는 속도를 조절하여 수신자와의 데이터 처리 속도를 맞추는 과정이다.
    주로 두 종단 시스템 간의 통신에서 사용되며, 수신자의 Receive window를 확인하고, 데이터를 처리할 수 있는 속도로 데이터를 보내도록 조절하여 버퍼 오버플로우를 방지한다.
    
    
  • congestion control: 혼잡 제어는 네트워크에서 발생하는 혼잡을 관리하고 데이터 패킷의 손실을 방지하기 위한 과정이다.
    혼잡 제어 알고리즘(예: AIMD)을 통해 송신자는 네트워크의 데이터 처리 속도와 자신의 데이터 전송 속도 간의 차이를 조절하여 혼잡을 완화하고 데이터 패킷의 손실을 방지한다.

• causes / costs of congestion
  → x-axis: 데이터증가량
  → y-axis: 데이터 도달량

  • 송신 데이터량이 증가하면 데이터 도달량이 감소(Throughput↓)하면서 특정 시점 이후로 congestion 발생

---

2. Solution

1. end-end congestion control: 송신자가 패킷을 전송한 후, 해당 패킷에 대한 응답이 돌아오지 않을 때 송신자가 관찰적으로 손실 또는 지연을 추론하여 혼잡을 판단
   → 네트워크의 도움 없이 송신자가 혼잡을 감지하고 대처할 수 있는 방법

2. network-assisted congestion control: 네트워크 내의 라우터나 다른 네트워크 요소가 혼잡을 감지하고, 해당 혼잡 정보를 송/수신자에게 피드백으로 전달하는 방식

---

3. AIMD(Additive Increase Multiplicative Decrease)

• TCP의 혼잡 제어 알고리즘 중 하나로, 데이터 전송 속도를 조절하는 메커니즘이다.
  → cwnd(혼잡 윈도우 크기): 송신자가 네트워크로 전송할 수 있는 데이터 양을 나타내는 변수이며, RTT 및 혼잡 제어 알고리즘에 따라 동적으로 최적화되어 계산된다.

  1. 증가 (Additive Increase): Congestion window size(cwnd)를 점진적으로 증가시키는 단계로, 송신자는 네트워크 혼잡을 감지하지 않으면 전송 속도를 additive하게 증가시킨다.
     
  2. 감소 (Multiplicative Decrease): 혼잡이 발생하면 송신자는 cwnd를 줄이는 감소 단계로 들어간다.
     → cwnd를 줄이게 되면 동시에 전송할 수 있는 데이터이 양이 줄게되고, 이에 따라 네트워크 혼잡을 완화하고 데이터 손실을 줄일 수 있다.
     • TCP Reno: Triple Duplicate ACK를 감지하고 이를 이용하여 혼잡 윈도우 크기를 반으로 줄인다.
       → Fast retransmission: Congestion 상태가 심각하지는 않으므로 cwnd 사이즈를 절반으로 감소시킨다.
     • TCP Tahoe: Timeout이 발생하면 혼잡 윈도우 크기를 1로 줄인다.

---

4. Slow start

• 시작 cwnd를 1로 설정하고, RTT마다 cwnd를 2배, 4배, 8배와 같이 지수적으로, 급격하게 증가시키는 TCP 혼잡제어 알고리즘이다.
  

---

5. Congestion avoidance

• slow start에 의해 지수적으로 증가하면 너무 빠른속도로 증가되기 때문에 금방 congestion이 발생하여 sending rate가 떨어질 수 있다.

• Slow start 단계를 마치고 혼잡 회피 단계로 들어갔을 때 사용되는 혼잡 제어 알고리즘이다.
  → ssthresh (slow start threshold) 값을 넘어서면 linear 하게 cwnd가 증가시킨다.
  → Slow start로 증가하다가 ssthresh를 넘어서면 linear하게 증가하는 것을 확인할 수 있다.

• Slow start는 초기 송신 속도를 빠르게 증가시키기 위해 지수적 증가를 사용하고, Congestion avoidance는 안정적인 데이터 전송을 위해 혼잡 윈도우 크기를 선형적으로 증가시키는 방식을 사용한다.
  AIMD는 이러한 혼잡 제어 알고리즘에서 혼잡 감지 및 혼잡 윈도우 크기를 조절하는 원칙을 설명하는 일반적인 개념이다.