TCP Congestion Control

혼잡 제어(Congestion Control)은 안정적인 네트워크 구축을 위해 필요한 기능이다. 인터넷을 비롯한 모든 네트워크는 하드웨어적 한계가 존재하므로 감당할 수 있는 용량이 정해져 있다. 

 

이러한 용량을 초과하는 경우, 높은 대기 시간, 연결 시간 초과 및 패킷 손실과 같은 현상들이 발생하게 된다. 네트워크를 사용하는 입장에서는 이러한 정체가 발생하는 것을 좋아하진 않을 것이다. 또한 이러한 상황이 계속 누적되어 네트워크 정체가 점점 악화될 수도 있는데, 이를 혼잡 붕괴(Congestion Collapse)라고 부르기도 한다.

 

따라서 정체가 발생했다면 전송하는 패킷의 수를 줄이는 등의 작업이 필요하다. 그리고 이러한 관리 기법을 혼잡 제어(Congestion Control)이라고 한다. 

 

TCP의 경우도 혼잡 제어를 통해 최대한 네트워크의 혼잡을 줄일 수 있도록 노력한다. 다만 TCP가 그렇다는 것이고, UDP 위에서 구현된 다른 프로토콜은 혼잡 제어를 수행하지 않을 수도 있다(즉, 네트워크를 배려하지 않을 수도 있다는 이야기다). 이후 알게 되겠지만, Slow Start와 같은 기법이 결국엔 성능을 저하시키기 때문이다.

 

Congestion Window

flow control을 정리할 때, 윈도우라는 개념이 등장했었다. 잠깐 복기해보자면 TCP의 경우 Selective Repeat(Sliding Window 구현의 일종) 방식을 사용해 윈도우 크기를 동적으로 조절하면서 수신측의 버퍼가 넘치지 않게 흐름제어를 했다.

 

비슷한 개념으로 TCP는 혼잡 제어에서 Congestion Window를 사용한다. Congestion Window란 송신측이 ACK를 받기 전에 보낼 수 있는 패킷의 최대 개수를 의미한다. 

 

말로만 이해하면 어려우니 그림을 통해 이해해보자. 송신측은 cwnd(Congestion Window Size) 값에 따라 보내는 패킷 수를 제한하고 있다. 가령 cwnd가 4라면 4개의 패킷을 전송한 뒤 더 이상 보내지 않고 ACK 패킷을 기다린다. 이처럼, flow control의 window와 congestion control의 window는 동일한 의미를 가진다.

 

여기서 'rwnd와 cwnd의 역할이 중복되지 않나' 라는 생각이 들 수 있겠으나, TCP의 경우 rnwd 값과 cwnd 값 중 더 작은 값을 송신 윈도우 크기로 두기 때문에, 결국은 두 값 모두를 사용하는 것이라 볼 수 있겠다. 수식으로 표현하면 다음과 같다.

sender window size = min(rwnd, cwnd)

 

이처럼 TCP는 cwnd 값을 조절하면서 송신 측의 윈도우 사이즈를 조절하고, 이를 통해 혼잡제어를 수행한다. 그럼 어떻게 cwnd 값을 결정할까?

해당 질문에 대한 답을 하기 전에, 미리 알아두어야 할 점이 있다. TCP의 혼잡 제어 구현 방식은 하나가 아니라는 것이다. 관련 표준도 여러 개가 있으며 그에 따른 혼잡 제어 방식도 여러개가 존재한다. 따라서 단순히 'TCP는 이러이러한 혼잡제어 방식을 사용한다' 라고 단언해서는 안될 것이다.

 

대표적인 혼잡제어 구현 방식은 TCP Tahoe와 TCP Reno인데, 각각 1988년, 1990년에 릴리즈된 방식이다. 각각의 혼잡 제어 구현 방식이 사용하는 구체적인 기법들은 다음과 같은데, 이제 차례대로 하나씩 알아보도록 하겠다.

TCP Tahoe = Slow Start + AIMD + Fast Retransmit

TCP Reno = Slow Start + AIMD + Fast Retransmit + Fast Recovery

 

AIMD (Additive Increase / Multiplicative Decrease)

우선 AIMD 기법에 대해 살펴본다. AIMD는 Additive Increase, Mulitiplicative Decrease의 약자로, cwnd를 1씩 증가시키다가 절반으로 감소시키는 기법을 의미한다.

 

앞서 cwnd를 통해 송신측의 패킷 전송량을 조절할 수 있다고 하였다. 즉, AIMD는 송신측의 전송량을 차근차근 늘리다가, Packet Loss가 발생하면 전송량을 절반으로 줄여 혼잡을 회피하는 방법이다.

 

조금 더 구체적으로는, 요청을 보내고 응답이 오기까지의 시간인 RTT(Round Trip Time) 당 한 개의 패킷을 더 보낼 수 있도록 윈도우 크기를 증가시킨다. 그리고 혼잡이 감지되는 상황이 발생하면 cwnd 값을 절반으로 줄인다.

 

보다 이해하기 쉽게 그림으로 나타내면 아래와 같다.

https://www.learnsteps.com/do-you-know-about-the-aimd-method-in-tcp-congestion-control/

 

전송하는 패킷의 개수가 선형적으로 1씩 증가하다가(Linear Increase), 혼잡이라고 판단되는 순간에 절반으로 감소(Exponential Decrease)를 수행한다. 그리고 여기서 '혼잡이라고 판단되는 순간'이란, Packet Loss나 Time out이 발생하는 상황 등을 의미한다.

 

이러한 AIMD 기법은 공평함을 보장한다는 특징이 있다. 네트워크에 가장 처음 접속한 디바이스든, 가장 나중에 접속한 디바이스든 윈도우 크기가 동적으로 계속 커졌다 작아졌다를 반복하며 균등한 기회를 보장한다.

 

하지만 AIMD의 경우 직관적으로 예측할 수 있듯, '선형적으로 증가한다는 특징' 때문에 빠르게 패킷을 전송하기는 어렵다. TCP를 기준으로 생각해보면 소켓 연결 이후는 항상 패킷을 하나만 보낼 수 있게 되는 것이다. 

 

Slow Start

이와 비슷하지만 살짝 다른, Slow Start 혼잡 제어 기법이라는게 존재한다. AIMD의 경우 선형적으로 증가하지만, Slow Start의 경우는 지수 차원으로 증가한다.

 

예를 들어, cwnd값이 1이었다면 Slow Start 기법을 사용하는 경우 RTT마다 1, 2, 4, 8, 16 ... 과 같은 형태로 증가하게 된다. 따라서 AIMD 방식에 비해 빠르게 패킷 수를 늘려나갈 수 있어서 효율적이다.

 

Data Communications and Networking, 5th Edition

 

Slow Start의 경우, 혼잡이 감지된다면 윈도우 크기를 1로 줄이게 된다. AIMD의 경우에는 윈도우 크기를 절반으로 줄인 것과 대비하면 큰 낙폭이나, 지수적으로 증가한다는 점을 감안하면 어느정도 납득이 된다.

 

Fast Retransmit

마지막으로 Fast Retransmit 과정을 살펴보도록 하겠다. TCP Tahoe와 Reno의 혼잡 제어 기법들을 다시 복기하자면 다음과 같았다.

TCP Tahoe = Slow Start + AIMD + Fast Retransmit

TCP Reno = Slow Start + AIMD + Fast Retransmit + Fast Recovery

 

Fast Retransmit은 Tahoe, Reno 둘 다 지원하는 기능이며, Fast Recovery는 Reno에서만 지원한다. 용어가 비슷하니 해당 내용을 잊어버리지 말고 넘어가도록 하자.

 

Fast Retranbmit은 직역하면 '빠른 재전송'이다. 이는 즉, 오류가 발생한 상황이라면 빠르게 재전송을 하겠다는 의미이다. TCP의 경우 내부적으로 타이머가 존재해서 타이머가 작동하는 시간 내에 응답이 왔는지 오지 안왔는지로 패킷의 재전송 여부를 판단한다. (Retransmission Timeout)

 

다만 여기서 문제점은, 패킷의 전송 속도에 비해 time-out 시간이 너무 길 수 있다는 의미다. 즉, 패킷 손실이 발생했다고 하더라도 타이머가 종료되지 않으면 재전송을 하지 않는데, Fast Retransmit은 이러한 문제점을 해결하기 위한 기법이다. 타이머가 울리기도 전에 재전송을 시도한다는 것이다.

 

이를 구현하기 위한 방법은 여러 가지가 있지만, 주로 Duplicate ACK 기법을 사용한다. 이는 말 그대로 중복된 ACK를 여러번 보내서 해당 패킷에 대한 소실 여부를 알려주겠다는 의미다. 송신측에서는 여러 번 ACK 응답을 받으면 Fast Retrasmit을 해야 한다고 판단하고, 타이머가 울리기도 전에 패킷을 재전송한다.

 

통상 Duplicate ACK의 기준이 되는 ACK 개수는 3개이며, 3개 이상의 ACK가 오면 손실이 아닌 지연이라고 판단한다.

Data Communications and Networking, 5th Edition

 

Fast Recovery

Fast Recovery는 '빠른 회복' 이라는 뜻이다. Slow Start 기법에 대해 조금 생각해보면, 다음과 같은 의문점이 들 수 있을 것이다. '매번 혼잡이 감지될 때마다 cwnd 값을 1로 줄이면, 비효율적이지 않나?' 라는 것이다.

 

따라서 실제 TCP Reno에서는 이러한 단점을 보완하기 위해 Fast Recovery라는 기법을 사용한다. 이는 Duplicate ACK가 탐지되었을 때 cwnd 값을 1로 줄이는게 아니라, 일정 비율만 줄이는 방식을 의미한다.

 

앞서 혼잡을 탐지하는 대표적인 방법으로 time-out과 Duplicate ACK가 있다고 했다. Fast Recovery의 경우 time-out은 신경쓰지 않고, Duplicate ACK에 대해서만 cwnd 값을 일정한 비율로 줄인다. 반대로 time-out에 대해서는 그대로 cwnd 값을 1로 줄인다.  이는 Dupliate ACK가 time-out에 비해 혼잡의 정도가 떨어진다고 가정을 하는 것이다.

 

All in together

이제 각각의 기법을 살펴봤으므로, TCP Tahoe와 Reno가 어떤 방식으로 혼잡을 제어하는지 종합적으로 살펴본다. 

 

TCP Tahoe

우선 Tahoe의 경우를 살펴보자. 앞서 Tahoe는 AIMD + Slow Start + Fast Retransmit 방식을 사용한다고 했다(Fast Recovery는 사용 X). 그림으로 나타내면 아래와 같은데, 하나씩 차례대로 설명하도록 하겠다. 

 

Data Communications and Networking, 5th Edition

 

x축이 의미하는 바는 RTT(Round Trip Time)이고, y축이 의미하는 바는 cnwd다. 앞서 RTT 하나 당 cwnd 하나를 증가시키는게 AIMD, 2배씩 증가시키는게 Slow Start라고 했으므로 참고하면 좋을 듯 하다.

 

아무튼, Tahoe의 경우 그래프를 살펴보면 다음과 같은 특징이 있음을 알 수 있다.

• 송신을 시작한 뒤, cwnd는 1이 되고, Slow Start 방식으로 동작한다.
• Time-out이 발생하면 cwnd는 1이 되고, Slow Start 방식으로 동작하다가 ssthresh 값을 넘어서면 AIMD로 동작한다.
• Duplicate ACK가 발생하면 cwnd는 1이 되고, Slow Start 방식으로 동작하다가 ssthresh 값을 넘어서면AIMD로 동작한다.

여기서 ssthresh 값은 Slow Start Threshold라는 의미로, Slow Start를 끝낼 임계점을 의미한다. 매번 Slow Start로 (지수적으로) 증가하게 되면 cwnd 값이 큰 경우는 너무 빠르게 증가하기 때문에, 오히려 비효율적이기 때문이다. 

 

벌써 눈치 챈 분도 있겠지만, Tahoe의 경우 ssthresh를 '혼잡이 발생한 cwnd 크기의 절반' 으로 설정한다. Time-out이 발생했던 지점은 cwnd가 8일 때이므로, 이후 ssthresh는 절반인 4로 설정된다. Duplicate ACK가 발생하는 순간에는 cwnd가 12이므로, 6으로 설정되는 것을 알 수 있다.

 

다만 이런 Tahoe의 경우 문제점이 존재하는데, 혼잡이 발생하면 매번 cwnd가 1로 초기화된다는 것이다. 이러한 문제점을 개선하고자 한 방식이 바로 TCP Reno이며, 앞서 설명한 Fast Recovery로 해결한다.

 

TCP Reno

TCP Reno의 경우는 거두절미하고 그래프부터 살펴보도록 하겠다. 동작 방식을 빠르게 이해할 수 있을 것이다.

 

그래프를 살펴보면 Tahoe의 경우와는 조금 다른데, Fast Recovery 알고리즘이 추가되었기 때문이다. 알고리즘이 조금 복잡한데, 하나씩 설명해보도록 하겠다.

 

앞서 말했듯 Fast Recovery는 Time-out에 관여하지 않으므로, 우선 Duplicate ACK 부분만 살펴보자. 3 Duplicate ACK가 발생하는 순간, 혼잡이 발생한 것이므로 어떠한 조치를 취해야 한다.

 

Tahoe의 경우라면 cwnd를 바로 1로 내려버리면 그만이었지만, Reno의 경우는 Fast Recovery 알고리즘에 의해 1이 아닌 9로 설정한다. 여기서 9로 설정한 이유는 Fast Recovery에 대한 알고리즘을 규정하는 RFC 2001에서 확인할 수 있는데, 원칙적으로는 cwnd = ssthresh + 3으로 설정하기 때문이다. 어떤 자료들은 Fast Recovery에서 cwnd 값을 절반으로 설정한다고 주장하기도 하는데, 표준에 따르면 ssthresh + 3으로 설정이 되는게 맞다.

 

ssthresh는 혼잡이 발생한 cwnd의 절반으로 설정된다 하였으므로 6이 되고, 그에 따라 Fast Recovery의 시작점도 6 + 3 = 9가 된다. Fast Recovery 시작 이후에도 지수적으로 증가하다가, 'new ACK'를 만나는 순간 cwnd를 ssthreshold 값까지 내린다. 그리고 Fast Recovery를 종료하고, AIMD로 동작한다.

 

말이 조금 어려운데, 순서대로 정리하면 다음과 같다.

 

1. Duplicate ACK를 마주하면 Fast Recovery 단계에 돌입한다.
2. ssthresh 값을 혼잡이 발생한 cwnd의 절반으로 설정, cwnd는 ssthresh + 3으로 설정한다.
3. 이후 지수적으로 증가시키다가, 오류가 발생한 패킷들을 모두 재전송해 새로운 ACK 응답을 받는다면 Fast Recovery를 종료한다.
4. Fast Recovery가 종료된 이후에는 cwnd를 ssthresh로 설정하고 AIMD로 동작한다.

 

마치며

TCP의 혼잡 제어 기법을 살펴봤다. 생각보다 내용이 더 어려웠고, 교차 검증을 하면서 글을 쓰는 데에도 상당한 시간이 걸렸다. 이로써 TCP의 흐름 제어, 혼잡 제어 기법을 살펴봤는데, 오류 제어에 대한 글도 조만간 작성하고자 한다.

 

참고 자료

http://www.ktword.co.kr/test/view/view.php?m_temp1=1469&id=746

http://www.ktword.co.kr/test/view/view.php?no=5249

http://www.ktword.co.kr/test/view/view.php?no=5536

http://www.ktword.co.kr/test/view/view.php?m_temp1=5249&id=1102

https://www.geeksforgeeks.org/what-is-network-congestion-common-causes-and-how-to-fix-them/

https://www.geeksforgeeks.org/tcp-tahoe-and-tcp-reno/

https://www.geeksforgeeks.org/what-is-rttround-trip-time/

https://www.isi.edu/nsnam/DIRECTED_RESEARCH/DR_WANIDA/DR/JavisInActionFastRecoveryFrame.html

https://evan-moon.github.io/2019/11/26/tcp-congestion-control/