TCP Congestion Control 문서 원본 보기

상위 문서: [[Principles of congestion control]], [[TCP]]

==개요==
본 문서의 상위 문서인 [[Principles of congestion control]]에서는 congestion의 문제 상황이 무엇을 의미하고 어떠한 문제를 야기하는지, [[TCP]]에서는 본 문서에서 사용할 여러 개념에 대해서 다루었다. 본 문서에서는 상위 문서에서 다룬 개념을 바탕으로 TCP가 어떻게 congestion을 조절하는지에 대해 설명할 것이다.

==TCP congestion의 기본 배경==
===Send Rate and Congestion Window===
TCP이 congestion에 취하는 기본적인 접근 방식은 송신자가 감지한 네트워크 congestion의 정도에 따라 자신이 해당 연결에 대해 보내는 트래픽의 전송 속도를 조절하는 것이다. 즉, 송신자가 자신과 목적지 사이의 경로에 congestion이 거의 없다고 판단되면 send rate를 증가시키고, 반대로 congestion이 있다고 판단되면 send rate를 줄인다. 이때, TCP는 송신자의 send rate를 조절하기 위해 '''cwnd(congestion window)'''라는 추가적인 변수를 활용한다. 이때 cwnd는 TCP 송신자가 네트워크로 트래픽을 보낼 수 있는 속도를 제한하는 제약 조건을 제공한다. 이 제약 조건은 송신자의 바이트 스트림(byte stream)에서 미확인된(unackowledged) 바이트의 양은 cwnd와 rwnd(receive window) 중 작은 값보다 클 수 없다는 것이다. 즉 다음과 같은 공식을 만족한다.
 LastByteSent − LastByteAcked ≤ min{cwnd, rwnd}
이때 rwnd의 값이 충분히 크다면, 송신자의 미확인 바이트의 양은 오직 cwnd에 의해서 제한되며, 이를 통해 send rate를 간접적으로 제한할 수 있다. 이를 이해 하기 위해 패킷 손실과 transmission delay가 무시할 수 있을 정도로 작다고 가정한 연결을 생각해 보자. 이 경우, 매 RTT의 시작에서 송신자는 cwnd 바이트의 데이터를 연결로 보낼 수 있고, RTT가 끝날 때쯤 송신자는 해당 데이터에 대한 확인 응답을 받는다. 따라서 send rate는 약 <code>cwnd/RTT bytes/sec</code>이다. 즉 송신자는 swnd 값을 조절하여 send rate를 조절할 수 있다.

===How to detect Congestion===
TCP 송신자가 경로 상에 congestion이 있다고 인식하는 방법은 패킷이 손실되는 상황(loss event)를 탐지하는 것이다. Congestion이 증가한 경우, 경로 상의 라우터 버퍼 중 하나가 overflow되어 datagram이 손실되며, 호스트는 이를 감지하여 경로 상에 congestion이 있다고 간주한다. 이때 호스트는 timeout이 발생하거나, 수신자로부터 [[TCP#Fast Retransmit|3개의 중복(duplicate) ACK를 수신]]할 때 패킷이 손실되었다고 인식한다.

==Additive Increase Multiplicative Decrease==
[[파일:AIMD congestion control.png|섬네일|300x300픽셀|Figure 1. AIMD congestion control]]
만약 congestion이 없다면 데이터의 송수신에는 이상이 없으므로 호스트는 send rate(transmission rate)를 높이고자 할 것이다. 이를 위해서 TCP는 이전에 전송한 세그먼트에 대한 ACK를 모든 것이 잘 되고 있다는 신호로 받아들이며, cnwd(send rate)를 증가시키기 위해 사용한다. 이때 ACK가 비교적 느리게 도착한다면 swnd도 느리게 증가하며, ACK가 빠르게 도착한다면 cnwd는 더욱 빠르게 증가한다. 이처럼 TCP는 ACK를 시계(clock)처럼 사용하여 cwnd를 증가시키므로 self-clocking 방식이라고 불린다. 이때, TCP가 cwnd(send rate)를 조절하는 구체적인 메커니즘을 '''AIMD(Additive Increase Multiplicative Decrease)'''라고 부른다. 이는 다음과 같은 기본 원칙을 따른다:
# 손실된 세그먼트는 혼잡을 의미하므로 send rate를 줄여야 한다.
# 확인된 세그먼트는  네트워크가 세그먼트를 성공적으로 전달하고 있음을 의미하므로 send rate를 증가시킬 수 있다.
# '''bandwidth probing''': ACK가 오면 send rate를 점점 높이고 패킷이 손실되며 send rate를 낮추고 다시 속도를 높히며 이를 반복한다.
이를 구현하기 위해, AIMD는 '''slow start, congestion avoidance, fast recovery'''라는 세 가지 주요 state로 이루어진다.

===Slow Start===
'''Slow start'''는 AIMD의 시작 부분으로, 초기 cwnd가 증가하는 state에 해당한다. TCP 연결을 시작하면 <code>cwnd = 1 MSS</code>로 설정되어 있다. 그리고 이에 대한 ACK가 오면 cwnd를 MSS만큼 증가시키며, 결과적으로 매 RTT마다 cwnd가 2배로 증가한다. 이때 항상 지수적으로 증가하는 cwnd는 문제를 일으키기 쉽기 때문에 어떤 변수 '''ssthresh'''를 사용하여 <code>cwnd < ssthresh</code>가 성립할 때에만 cwnd의 크기를 지수적으로 증가시킨다. 만약 <code>cwnd ≥ ssthresh</code>이 참이 되면 congestion avoidance로 전환한다. 또는 그 전에(slow start 단계일 때) 패킷 손실 이벤트가 발생하면 congestion이 발생하고 있다는 뜻이므로 <code>cwnd = 1 MSS</code>로 줄이고, <code>ssthresh = cwnd / 2</code>로 설정하고, slow start를 처음부터 재개한다.

===Congestion Avoidance===
'''Congestion avoidance'''에 진입하면 cwnd의 값은 마지막으로 congestion이 발생했을 때의 cwnd값의 약 절반(ssthresh)이다. 이 시점부터는 매 ACK을 수신할 때마다 cwnd를 조심스럽게 선형적으로 증가시킨다. 이를 통해 ACK를 수신할 때 마다 두배로 증가했던 slow start 단계와는 달리, congestion를 피하면서도 더욱 빠른 송신을 위해서 cwnd를 선형적으로 증가시키는 것이다. 이때, 패킷 손실 이벤트가 발생하면 congestion이 발생하고 있다는 뜻이므로 <code>cwnd = 1 MSS</code>로 줄이고, <code>ssthresh = cwnd / 2</code>로 설정하고, slow start를 처음부터 재개한다.

===Fast Recovery===
[[파일:Tahoe and Reno.png|섬네일|300x300픽셀|Fugure 2. Tahoe and Reno]]
호스트가 패킷 손실을 감지하는 방법으로는 timeout과 3개의 중복 ACK를 수신하는 것이 있는데, 이 두 방법은 미묘한 차이점을 가지고 있다. Timeout은 네트워크가 메우 혼잡한 상태라고 간주되기 때문에 cwnd의 급격한 감소가 필요하다. 하지만 3개의 중복 ACK가 수신된 경우는 패킷의 손실이 있더라도, 그 외의 패킷들은 모두 정상적으로 도착하고 있기 때문에 timeout보다는 네트워크의 상태가 양호함을 시사한다. 따라서 3개의 중복 ACK를 수신했을 때는 '''fast recovery''' state로 전환하여 더욱 효율적인 송신을 한다. 

Fast recovery가 어떻게 동작하는지 알아보기 위해 다음과 같은 상황을 살펴보자. 만약 송신자가 1~10번 세그먼트를 전송하였으나, 4번 세그먼트가 손실되었고, 수신측은 세그먼트 5, 6, 7을 받았다고 하자. 이 경우, 수신자는 ACK(4)를 3개 보낸다. 이 경우, 송신자는 ACK(4)를 3개 수신한다. 이는 패킷의 손실로 간주되며 <code>ssthresh = cwd/2</code>, <code>cwnd = ssthresh + 3xMSS</code><ref>중복 ACK 3개를 고려해 MSS를 3개 만큼 늘린다.</ref>로 설정된다. 이후 중복 ACK를 추가로 수신할 때마다 cwnd의 값을 MSS만큼 더한다. 해당 과정을 진행하는 중, 누락된 세그먼트에 대한 ACK을 수신하면<ref>ACK(8)</ref>, cwnd를 ssthresh로 갱신하고, congesiton avoidance로 전환한다. 

'''TCP Reno'''는 fast recovery를 이용하는 TCP 버전이며, '''TCP Tahoe'''는 fast recovery를 사용하지 않는다. timeout이던 3번의 중복 ACK던 무조건 cwnd를 1MSS로 줄이고 slow start 상태로 전환한다. 오른쪽의 그래프는 TCP Reno와 TCP Tahoe의 차이점을 잘 보여준다. 

==Macroscopic Description of TCP Throughput==
TCP는 congestion control로 인해서 그 송신 속도가 톱니 모양으로 변화하게 된다. 따라서 TCP의 평균 throughput을 구하는 것은 중요한 일이다. 이때 평균 throughput을 구하는 과정에서 congestion control은 TCP Reno를 따르며, timeout 이벤트 후 발생하는 slow start 구간은 무시한다고 가정하자. 이때 cwnd가 W에 도달하면 패킷 손실이 일어난다고 가정하면, 패킷 손실이 일어날 때마다 TCP는 cwnd를 반으로 줄이고 선형적으로 cwnd를 증가시키는 과정을 반복한다. 즉, TCP의 평균 throughput은 다음과 같은 공식을 통해서 구할 수 있다: 
 avg TCP throughput = 0.75 x W/RTT (bytes/sec)

==TCP Over High-Bandwidth Paths==
Congestion control은 네트워크의 수준이 발달하며 그 수준이 고도화되어 왔으며, 고도화에 대한 요구도 증가되어왔다. 그 이유는 다음과 같은 상황을 통해서 이해할 수 있다. 예를 들어, 세그먼트 크기가 1500바이트, RTT가 100ms인 TCP 연결을 통해 10Gbps의 throughput을 지원하고자 한다.. 이때 다음 수식에 의해서 10Gbps 속도로 데이터를 보낼 때 요구되는 cwnd의 크기는 다음과 같다:(이때, cwnd를 MSS 단위의 세그먼트 수로 본다.)
 <math>Throuput = \frac{cwnd}{RTT} = \frac{W\cdot MSS}{RTT}</math>
 <math>W = \frac{Throughput \cdot RTT}{MSS} = \frac{10\cdot 10^9 bits/sec \times 0.1 sec}{1500 \times 8 bits} \approx 83,333</math>
즉, 약 83,333개의 세그먼트들이 평균적으로 cwnd를 통해서 수신자 측으로 전송되어야 한다. 이는 매우 큰 숫자이며, 이들 중 하나라도 손실이 일어날 가능성을 낮추어야 한다.<br>
또한, 이번에는 패킷이 손실될 가능성을 L이라고 할 때, TCP의 throughput을 구하는 공식을 만들면 다음과 같다:
 <math>TCP \,\,throughput = \frac{1.22 \cdot MSS}{RTT\sqrt{L}}</math>
이를 바탕으로 위의 예시 상황을 기준으로 L의 범위를 구하면, 10Gbps의 throughput을 얻기 위해서는 세그먼트의 손실 확률 L이 2x10<sup>-10</sup>을 초과해서는 안된다는 결론이 나온다. 즉 50억개의 세그먼트를 보내면 1개가 손실되는 수준이다. 따라서 네트워크의 수준이 올라감에 따라 congestion의 수준 또한 더 높아져야 한다.

==Fairness==
K개의 TCP 연결이 각각 end-to-end 경로를 가지고 있지만, 모두 전송 속도가 R bps인 병목 링크(bottleneck link)를 통과한다고 가정하자.<ref>여기서 병목 링크란, 각 연결 경로에 있는 다른 링크들은 혼잡하지 않고, 병목 링크보다 충분한 전송 용량을 가진다는 의미다.</ref>
각각의 연결들은 큰 파일을 전송 중이며, 병목 링크를 통과하는 UDP 트래픽은 없다고 하자. 이때, 혼잡 제어 메커니즘이 '''공정하다(fair)''' 고 말하려면, 각 연결의 '''평균 transmission rate가 R/K에 근접'''해야 한다. 즉, 각각의 연결이 link capacity를 동일하게 나누어 가져야 한다.

TCP는 각각의 연결들이 서로 다른 시점에 시작될 수 있고, 어떤 시점에서는 서로 다른 window size를 가질 수도 있음에도 공정하다고 할 수 있다. 왜 그런지

==각주==
[[분류:컴퓨터 네트워크]]