네트워크가 혼잡하면 송신자가 보낸 패킷이 수신자에게 너무 늦게 도착하거나, 혹은 전송 도중에 네트워크 상에서 사라져버릴 수도 있다. 이런 네트워크 혼잡 문제를 해결하기 위한 제어를 혼잡 제어(congestion control)이라 하는데, 우선은 보다 일반적인 맥락에서 혼잡 제어 문제를 다뤄보고, 그 다음에 TCP에서의 혼잡 제어에 대해 알아보자.

1.Congestion Control (in general)

(1) The Causes and the Costs of Congestion

여러 개의 시나리오를 보면서 어떤 경우에 네트워크 혼잡이 발생하는지, 또 그 결과는 어떻게 되는지 알아보자.

1. 시나리오 1
   두 명의 송신자 A, B가 각각 연결된 수신자 C, D에게 데이터를 보낸다고 하고, 다음과 같이 가정하자.

• A와 B의 애플리케이션은 모두 $\lambda_{in}$의 속도로 데이터를 보낼 수 있다.
• 신뢰성 있는 데이터 전송을 위한 메커니즘 및, 전송 계층과 그 이하 계층의 헤더 오버헤드 등은 없다고 가정한다.
• A, B는 출발지와 목적지 사이에 있는 한 홉을 공유한다.
• 무한한 크기의 버퍼를 가지고 있는 라우터가 하나 있다.
• 라우터의 아웃고잉 링크의 대역폭은 R이다.

A, B가 동시에 데이터를 보낸다고 하자. 공유된 링크 하나를 서로 나눠 쓰게 될 것이므로 처리량은 R/2를 넘지 못한다. 이때 호스트의 송신 속도($\lambda_{in}$)를 생각해보면,

• 송신 속도가 R/2보다 느리면, C, D는 송신하는 족족 수신할 수 있다.
• 송신 속도가 R/2보다 빠른 경우 공유되는 링크는 곧 가득차게 된다. 호스트 A, B가 라우터가 처리할 수 있는 속도 R보다 빠르게 패킷을 보내므로, 라우터 버퍼에는 패킷이 무한히 쌓이게 되고, 처리량도 R/2를 넘지 못하게 된다.

두 호스트가 너무 빠르게 데이터를 보내는 경우, 라우터에도 패킷이 무한히 쌓이면서 지연 또한 무한히 증가한다. 라우터의 버퍼 크기가 무한하다고 가정했기 때문에 패킷 손실이 일어나지는 않지만, 지연은 매우 크다.

2. 시나리오 2
   이번에는 위와 같기는 하지만, 라우터의 버퍼가 유한하고 TCP처럼 라우터에서 드롭되어 손실된 패킷은 재전송한다고 가정하자. 애플리케이션이 소켓에 데이터를 집어 넣는 속도는 $\lambda_{in}$이지만, 전송 계층에서 네트워크로 세그먼트(재전송 포함)를 내보내는 속도는 $\lambda'_{in}$이라 하자. 이를 네트워크에 대한 제공 부하(offered load)라 부르기도 한다.

• 라우터 버퍼에 여유 공간이 있는지를 알고, 손실이 일어나지 않도록 속도를 조절하는 경우
  - 애플리케이션의 처리량이 $\lambda'_{in} = \lambda_{in}$이 되고, 지연도 낮다. 단 평균 처리량이 R/2를 넘지는 못한다.
  - 하지만 실제로는 불가능하다.
• 패킷 손실이 확실한 경우에만 재전송
  - 긴 타임아웃 간격을 두는 방식 등으로 손실을 감지한다.
  - 라우터 버퍼의 크기가 작아 패킷이 손실되는 경우 재전송한다.
  - 제공 부하 $\lambda'_{in}$에는 새로 보내는 세그먼트 + 재전송 세그먼트가 모두 있기에, 수신자 애플리케이션의 처리량은 R/2에 미치지 못한다.
• 너무 일찍 타임아웃해, 아직 라우터 버퍼에 대기 중인 패킷을 재전송하는 경우
  - 한 세그먼트의 원본 + 재전송본이 모두 수신자에게 도착할 수 있다. 수신자는 재전송 패킷은 무시하기 때문에 불필요한 낭비다.

3. 시나리오 3
   마지막으로는 네 명의 호스트가 서로 교차하는 두 홉의 경로를 따라 패킷을 전송한다고 해보자. 각 호스트는 타임아웃/재전송 방식으로 신뢰성 있는 데이터 전송 서비스를 구현하고 있고, $\lambda_{in}$ 값은 동일하다. 모든 라우터 링크의 용량은 R바이트/초다.

A에서 C로 데이터를 보낸다고 하자. 이 연결은 R1, R2라우터를 거치는데, R1에서는 D-B 연결과, R2에서는 B-D 연결과의 트래픽 경쟁이 일어난다.

• $\lambda_{in}$ 가 충분히 작은 경우
  - 버퍼 오버플로가 드물게 일어나고, 처리량도 $\lambda_{in}$에 근접해진다.
  - 작은 $\lambda_{in}$의 경우 $\lambda_{in}$가 증가함에 따라 $\lambda_{out}$도 증가하게 된다.
• $\lambda_{in}$이 너무 큰 경우
  - R1에서 D-B 연결과의 경쟁이 일어나므로 패킷 드롭이 발생한다.
  - 이후 R2에서도 B-D 연결과의 경쟁이 일어나는데, 이미 한 번 경쟁을 거친 A-C 트래픽의 비율은 B-D보다 작을 수 밖에 없다.
  - R2 버퍼에 B-D 트래픽이 더 많이 쌓이게 되고, A-C는 더 많이 드롭된다.
  - 재전송과 패킷 드롭이 잦아지면서 처리량이 뚝 떨어지게 된다.

(2) Approaches to Congestion Control

그럼 인터넷은 어떻게 네트워크 혼잡을 제어할까? 일반적으로 혼잡 제어는 네트워크가 제공하는 정보를 바탕으로 종단 시스템, 즉 송수신자가 실행한다. 일반적으로는 다음의 네 방식을 사용한다.

1. 종단 시스템 기반 혼잡 제어. 네트워크 피드백 없음
   IP에서는 네트워크 혼잡에 대한 피드백을 제공하지 않기 때문에, TCP에서는 이 방식을 사용해야 한다. 송신자는 패킷 손실, 긴 RTT, ACK 지연 등을 바탕으로 혼잡이 발생했다고 간주한다. 혼잡이 발생했다고 판단되면 송신 속도를 줄이고, 그렇지 않으면 송신 속도를 점진적으로 늘린다.

2. 종단 시스템 기반 혼잡 제어. 명시적 피드백
   라우터 등의 네트워크 장치가 혼잡 상태를 감지하고, 이에 대한 명시적인 신호를 송신자에게 전달한다. 이 신호를 받은 송신자는 혼잡을 줄이기 위해 송신 속도를 낮춘다.

3. 네트워크 기반 혼잡 제어. 종단 시스템 개입 없음
   라우터가 혼잡을 감지하고 직접 제어한다. 예를 들면 혼잡 상태에서 특정 패킷을 드롭하거나, 큐잉 지연을 줄이기 위해 패킷을 미리 드롭하는 식이다.

일반적으로는 혼잡 회피(congestion avoidance)라 부르는 방식으로, 송신자는 네트워크 내부에서 어떤 일이 일어나는지 모르고, 송신자의 행위와 무관하게 네트워크 장비가 스스로 혼잡을 관리한다.

4. 네트워크와 종단 시스템이 함께 혼잡 제어
   송신자는 네트워크 장치가 주는 정보를 바탕으로 적절히 송신 속도를 조절한다. 네트워크 장치도 혼잡 제어에 참여한다. 복잡하기는 하지만 가장 효과적일 수도 있다고 여겨진다.

2. TCP Congestion Control

앞서 봤듯 TCP는 종단 시스템 기반의 혼잡 제어 메커니즘을 사용한다. 기본 아이디어는 간단하다.

빡빡하면 줄이고, 널널하면 늘린다.

그럼 다음의 세 질문이 자연스럽게 나온다.

1. TCP 송신자는 어떻게 트래픽 속도를 제한할까? (메커니즘)
2. TCP 송신자는 어떻게 네트워크 혼잡을 감지할까?
3. TCP 송신자는 어떤 속도로 데이터를 보내야 할지 어떻게 결정할까? (정책)

우선 첫 번째부터 보자.

(1) TCP 송신자는 어떻게 트래픽 속도를 제한할까?

송신자는 한 번에 보낼 수 있는 데이터량을 조절함으로써 간접적으로 데이터 전송 속도를 제한한다.

TCP의 송/수신자는 각각 수신 버퍼, 송신 버퍼, 그 외의 여러 변수들을 가지고 있다. 이전에 봤던 흐름 제어에서 수신자의 수신 버퍼 윈도우(rwnd)크기를 바탕으로 송신자의 송신 윈도우 크기를 조절했던 것과 같이, 혼잡 제어에서는 네트워크 혼잡도를 바탕으로 송신자의 송신 윈도우 크기를 조절한다.

TCP는 네트워크 혼잡도에 따라 송신 윈도우 크기를 조절하기 위해 추가적인 변수로 혼잡 윈도우(cwnd)를 추적하며, 혼잡 윈도우는 TCP 송신자가 네트워크로 보내는 트래픽의 속도를 제한하는 제약으로 작용한다.

구체적으로 송신 윈도우의 크기는 수신자의 수신 윈도우를 초과하면 안되고, 혼잡 윈도우도 초과해서는 안되기 때문에, 두 값의 최솟값으로 설정된다.

LastByteSent - LastByteAcked <= min(cwnd, rwnd)

간단히 혼잡 윈도우만 신경 쓴다고 가정하자. 송신자는 cwnd 바이트의 데이터를 연결에 전송할 수 있고, RTT 후에 그에 대한 확인 응답을 받는다. 전송 속도의 측면에서 보면 $\frac{\text{cwnd}}{\text{RTT}} \text{byte/sec}$로 속도를 제한한다고 볼 수 있다.

Q. 엥? 데이터 전송 시간만 보면 되니까 RTT의 절반 쯤 아닌가?
A. 한 번 보내기만 하는 데 걸리는 시간은 RTT/2 쯤 되지만, TCP에서는 ACK을 받아야 다음 데이터를 보낼 수 있다. 다시 말해 한 번 cwnd만큼 데이터를 보냈으면, 그에 대한 ACK를 받아야만 다음 cwnd만큼의 데이터를 보낼 수 있다. 때문에 1RTT 동안 보낼 수 있는 데이터량이 cwnd로 제한된다고 본다.

(2) TCP 송신자는 어떻게 네트워크 혼잡을 감지할까?

TCP 송신자는 패킷 손실을 네트워크 혼잡의 신호로 여긴다. 혼잡이 발생하면 소스-목적지 경로 상에 있는, 적어도 한 라우터의 버퍼가 오버플로우되고 데이터그램이 드롭되기 때문이다.

패킷 손실을 감지하는 방법은 이전에도 많이 봤다. 타임 아웃이 발생하거나, 중복 ACK을 세 번 이상 받는 경우다.

반대로 보낸 세그먼트들에 대한 ACK이 잘 도착한다면, 네트워크가 널널한 상태라고 판단할 수 있다. 이 경우 ACK을 받을 때마다 혼잡 윈도우를 늘린다. ACK를 빠르게 받으면 혼잡 윈도우도 빠르게 증가할 것이고, 느리게 받으면 혼잡 윈도우도 천천히 증가할 것이다.

TCP는 이렇게 ACK을 바탕으로 혼잡 윈도우 크기를 늘리기에, self-clocking 방식이라고도 한다.

(3) TCP 송신자는 어떤 속도로 데이터를 보내야 할지 어떻게 결정할까??

TCP 송신자가 너무 빠르게 전송 속도를 올리면 네트워크는 금방 혼잡해질 것이고, 그렇다고 너무 느리게 보내면 네트워크 대역폭을 제대로 활용하지 못하게 된다. 따라서 최대한 빠르게, 그렇다고 혼잡을 일으키지 않을 정도의 속도로 데이터를 보내야 한다.

그렇다면 TCP 송신자는 어떻게 전송 속도를 결정할까? TCP는 다음과 같은 원칙을 따른다.

• 손실된 세그먼트는 혼잡을 의미한다. 송신자는 손실 발생 시 전송 속도를 줄인다.
• ACK는 네트워크 상태가 좋음을 의미한다. 이 경우 전송 속도를 올려도 좋다.
• 대역폭 탐색(Bandwidth probing): 네트워크 혼잡 상태를 직접 알 수는 없고, 위와 같은 긍정적/부정적 피드백으로 추측만 할 수 있다.

어떤 경우에 전송 속도를 증감시킬지는 알게 됐다. 그럼 얼마나 전송 속도를 증감시켜야 할까? 그 표준 알고리즘([RFC 5681])에 대해 알아보자. 이 알고리즘은 아래의 세 구성 요소를 가지고 있는데, 이 중 느린 시작과 혼잡 회피는 필수, 빠른 복구는 권장 사항이다.

1. 느린 시작: 일단 하나부터 시작해서 2배씩 늘려 보기
2. 혼잡 회피: 어느 정도 늘렸으니 천천히 늘리기
3. 빠른 복구: 너무 많이는 말고, 반 정도로만 줄이고 선형적으로 늘리기.

이때 감지하는 이벤트 종류에는 세 가지가 있다. 대충 이렇게 반응한다 생각하자.

1. 타임아웃: 네트워크 터졌음. 망했음.
2. cwnd >= ssthresh: 이 정도면 조금만 늘려도 될 듯.
3. 셋 이상의 중복 ACK 수신: 혼잡하긴 하지만 그렇게 심하진 않음.

(3-1) 느린 시작(Slow Start)

TCP 연결이 시작될 때 cwnd는 1 MSS로 설정된다. 전송 속도의 측면에서 본다면 MSS/RTT다. 단 실제 사용할 수 있는 대역폭이 MSS/RTT보다는 훨씬 클 수 있기 때문에, TCP 송신자는 가능한 한 빨리 사용 가능한 대역폭을 알아내야 한다.

느린 시작에서는 cwnd가 1MSS에서 시작해,전송된 세그먼트에 대한 ACK을 받을 때마다 1MSS 씩 증가하고, 결과적으로는 아래와 같이 지수적으로 늘어난다.

1. 세그먼트 1개 보냄
2. 세그먼트 1개 ACK -> 혼잡 윈도우 + 1MSS = 2MSS
3. 세그먼트 2개 보냄
4. 세그먼트 2개에 대한 ACK -> 혼잡 윈도우 + 2MSS = 4MSS
5. 세그먼트 4개 보냄
6. ...

Q. 엥? TCP는 누적 ACK이라 1MSS씩만 늘어나야 하는 거 하는 거 아닌가요?
A. 실제로 받는 ACK는 누적 ACK 하나지만, 그 앞의 세그먼트들도 ACK을 받았다고 가정합니다.

물론 무한히 늘릴 수는 없고 언젠가 끝나기는 해야 하는데, 다음과 같은 경우에 끝이 난다.

1. 타임아웃 발생 시: ssthresh = cwnd/2, cwnd = 1로 설정하고 느린 시작으로 전환한다.
2. cwnd가 ssthresh값 이상이 되는 경우: 느린 시작을 종료하고 혼잡 회피 모드로 전환한다.
3. 셋 이상의 중복 ACK 수신: ssthresh = cwnd/2, cwnd = ssthresh + 3으로 설정하고 빠른 회복 상태로 전환한다.

(3-2) 혼잡 회피(Congestion Avoidance)

혼잡 회피 상태에서 cwnd는 마지막으로 혼잡이 일어났을 때의 절반이다. cwnd를 확 늘리면 곧 혼잡이 발생할 수 있으므로, 조금은 보수적으로, 이제는 RTT마다 1MSS만큼만 늘린다. 일반적으로는 ACK를 받을 때마다 cwnd를 MSS/cwnd만큼 증가시킨다.

혼잡 회피는 다음과 같은 시점에 끝난다.

1. 타임아웃 발생 시: ssthresh = cwnd/2, cwnd = 1로 설정하고 느린 시작으로 전환한다.
2. 셋 이상의 중복 ACK 수신: ssthresh = cwnd/2, cwnd = ssthresh + 3으로 설정하고 빠른 회복 상태로 전환한다.

Q. 3 MSS는 왜 더하냐고요. 예?
A.

(3-3) 빠른 회복(Fast Recovery)

빠른 회복에서는 네트워크가 어느 정도 안정기에 들어섰다고 가정하고 다시 좀 더 빠르게 높여 본다.

1. 손실 세그먼트 중복 ACK 수신: cwnd를 1 MSS씩 증가시킨다.
2. 손실 세그먼트 정상 ACK 수신: 어느 정도 네트워크 혼잡이 해결되었다고 판단. cwnd = ssthresh로 설정하고 혼잡 회피 상태로 전환해 cwnd를 천천히 늘린다.
3. 타임아웃: cwnd는 1 MSS, ssthresh는 손실 당시의 절반으로 설정한다.

(4) 평가

연결 초기의 느린 시작과 드물게 일어나는 타임아웃을 제외하면, TCP는 대부분 선형적으로 윈도우 크기를 늘려나가다가 중복 ACK이 세 번 들어오면 윈도우 크기를 반으로 줄이는 방식으로 이루어진다. 때문에 종종 TCP 혼잡 제어는 AIMD(Additive increase/Multiplicative decrease) 방식이라고도 불린다.

AIMD
선형적으로 윈도우 크기를 1씩 늘리다가, 패킷 손실이 일어나면 반으로 줄이는 방식

(4-1) 공정성

K개의 TCP 연결이 하나의 병목 링크를 공유한다고 하자. 각 연결은 큰 파일을 전송하고 있고, 이 K개 TCP 연결 트래픽 이외의 트래픽은 없다. 만약 혼잡 제어 메커니즘이 공정하다면, 각 연결의 평균 전송 속도는 R/K여야 한다.

K개 TCP 연결의 MSS와 RTT가 모두 동일하다고 하자. 초기의 느린 시작/타임아웃을 제외하고, TCP가 AIMD 방식으로만 동작한다고 하자. AIMD는 공정한 알고리즘일까?

1. 각 연결이 선형적으로 혼잡 윈도우 크기를 늘려나간다. (RTT마다 1MSS)
2. 그러다가 각 연결이 사용하는 대역폭의 합이 R을 초과하면 패킷 손실이 발생한다.
3. 각 연결은 윈도우 크기를 반으로 줄인다.
4. 다시 윈도우 크기를 선형적으로 늘려나간다.

위 과정을 반복할 때, K개 연결은 링크의 대역폭 R을 공정하게 나누어 갖게 된다.

물론 여기서는 병목 링크에 K개 TCP 연결 외 다른 연결이 없고, 모든 연결이 같은 RTT, MSS를 가지고 있다고 가정했기 때문에 현실적이지는 않다. RTT가 작은 연결들이 더 빠르게 대역폭을 차지하고, 더 높은 전송 속도를 얻는 등, 대역폭이 균등하게 분배되지는 않는다.

(4-2) 공정성과 UDP

UDP의 경우에는 혼잡 제어 기능이 없기 때문에, 네트워크가 혼잡한지 그렇지 않은지 신경 쓰지 않고 일정한 속도로 계속 전송하려 한다. 때문에 UDP는 네트워크 상태에 따라 패킷 손실이 일어날 가능성이 높고, 공정하지도 않으며, TCP 트래픽을 밀어낼 수도 있기 때문에 전체 네트워크에 혼잡을 가져올 수도 있다.

(4-3) 공정성과 병렬 TCP 연결

TCP 연결만 사용한다고 해도 공정성 문제는 남아있다. TCP 애플리케이션이 여러 개의 병렬 연결을 사용할 수 있기 때문이다.

예를 들어 대역폭 R의 링크에 9개의 TCP 연결이 있다고 하자. 이때 어떤 웹 브라우저가 병렬 TCP 연결을 통해 11개의 연결을 만들면, 이 애플리케이션 하나가 반 이상의 대역폭을 차지할 수 있게 된다. TCP 연결만 이용해도 공정성을 해치는 꼼수를 부릴 수는 있다.

(5) Explicit Congestion Notification (ECN): Network-assisted Congestion Control

앞서 TCP는 종단 시스템 기반 혼잡 제어라 했다. 기본적으로는 그렇지만 사실 IP, TCP에 대한 확장 기능도 배포되어 있는데, 이 기능은 네트워크 장치가 TCP 송수신자에게 혼잡 상태를 명시적으로 알릴 수 있게 해준다. 이러한 방식을 명시적 혼잡 알림(ECN)이라 한다.

TCP와 IP가 모두 이 기능에 관여하는데 하나씩 살펴보자.

(5-1) IP 계층에서의 동작

네트워크 계층에서는 IP 데이터그램 헤더의 TOS 필드 내에 있는 두 비트를 ECN 용도로 사용한다.

비트	0	1	2	3	4	5	6	7
의미	DS	DS	DS	DS	DS	DS	ECN	ECN

• DS: 패킷 우선 순위, 서비스 품질 제어 등
• ECN: 송수신자가 모두 ECN을 사용할 수 있는 경우 01 또는 10으로 설정됨
  - 00: ECN 미지원
  - 01: ECN 사용 가능
  - 10: ECN 사용 가능
  - 11: 혼잡 발생

라우터에서 혼잡이 감지되는 경우, ECN 비트가 11로 설정된다. 수신자는 이 데이터그램을 받았을 때 네트워크가 혼잡하다는 것을 알고, 네트워크 혼잡 신호를 송신자에게 다시 전달할 수 있다.

다만 언제 라우터가 혼잡 상태라 파악해야하는지에 대한 공식적인 기준이 따로 정해져 있지는 않고, 라우터 벤더나 네트워크 운영자가 정한다.

(5-2) TCP 계층에서의 동작

TCP 수신자는 ECN = 11로 설정된 데이터그램을 받았을 때, ACK 세그먼트의 ECE 비트를 1로 설정해서 송신 호스트에게 응답을 보낸다.

송신 호스트는 ECE = 1인 ACK을 받으면 혼잡 윈도우 크기를 반으로 줄이고, 다음으로 보내는 TCP 세그먼트의 헤더의 CWR 비트를 설정해 혼잡 윈도우를 줄였음을 알린다.

TCP 이외에도 ECN 신호를 사용할 수 있는 전송 계층들이 있다.

• DCCP(Datagram Congestion Control Protocol): 혼잡 제어를 제공하는 UDP
• DCTCP(Data Center TCP): 데이터센터 환경에서 사용되는 TCP의 변형 버전