Loss-based 알고리즘의 진화와 표준 (Reno & CUBIC)

이 노트는 패킷이 손실되어야만 속도를 줄인다는 천학을 가진 알고리즘들이 어떻게 발전해왔는지 그리고 왜 현대 고속 네트워크에서는 CUBIC이 표준인지 분석한다.

고전 알고리즘 계보. #

초기 tcp congestion control에서는 얼마나 빨리 복구하느냐를 기준으로 발전했다.

TCP Tahoe는 Slow Start가 핵심 특징이고 패킷 손실 3 dup acks를 감지시 cwnd를 무조건 1로 초기화하고 slow start를 다시 수행했다. (공격적으로 속도 저하)

TCP Reno는 Fast Recovery를 도입했고 패킷 손실시 cwnd를 1이 아닌 cwnd / 2로 줄이고 slow start를 건너뛰고 바로 혼잡 회피 단계로 진입해 대역폭 낭비를 줄였다.

TCP NewReno는 Partial ACK를 개선한 버전으로 Reno는 한 윈도우 내에서 여러 패킷이 손실되면 성능이 급격하게 떨어진다. NewReno는 Partial Ack(일부만 확인된 응답)을 인식해, 한 윈도우 내의 다수 손실을 타임아웃없이 모두 복구한다.

Partial ACK랑 SACK랑 헷갈릴수있는데 손실된 패킷을 감지한다는 것 자체는 같고. 그것을 수신자가 하느냐 송신자가 하느냐에 따라서 나누어진다.
Partial ACK는 윈도우에서 패킷 하나만 복구할 수 있었던 reno를 개선한 NewReno에서 사용되는 방식으로 송신자가 1~5번 패킷을 보냈는데 2, 4번이 손실되었을 경우 송신자가 2를 재전송, 수신자가 2를 받았음 하지만 4도 없기때문에 3까지는 받았다는 ack 4라고 응답 송신자는 원래 5까지 보냈는데 3까지 받았다길래 아직 복구가 덜 됐음을 판단한다. 이처럼 복구 시작 시점의 최고 전송 번호보다 낮은 ack를 partial ack라고 부른다.
결과적으로 fast recovery를 끝내지 않고 아 4번도 잃어버렸구나 하며 즉시 4번을 재전송한다. 한계로는 하나 고치고 확인하고 하는 방식이라 느림.
근데 여기서 헷갈리는게 SACK이다. 선택적응답. 손실된 패킷을 선택한다는 개념으로는 같은데 동작이 다르다 수신자는 ack 1을 보내면서 2를 기다린다. tcp 옵션 필드에 sack가 3-3 5-5라고 적어서 보낸다. 의미는 1까지는 받았는데 3이랑 5는 가지고있어 2,4는 없다는 뜻. 그니까 송신자가 이걸 보고 2 4를 콕집어서 보낼 수 있음

TCP CUBIC #

현재 linux, windows, macos, android 등 거의 주요 운영체제의 기본 tcp 알고리즘이다.

3차 함수 곡선 cubic function으로 reno의 단순한 선형증가 sawtooth(톱니바퀴)와 달리, cubic은 3차함수 곡선을 사용하여 윈도우 크기를 조절한다.

원리는 마지막 패킷이 손실이 발생했던 지점 $W_{max}$ 를 기억하고, 그 지점에 가까워질수록 증가 속도를 조절한다.

Concave: $W_{max}$ 에 도달하기 전에 빠르게 증가하다가 가까워지면 증가 폭을 줄여 안정적으로 탐색한다
Plateau: $W_{max}$ 근처에서는 아주 천천히 증가하며 최대 대역폭을 유지하려고 한다.
Convex: $W_{max}$ 를 넘어서도 패킷 손실이 없다면, 새로운 대역폭이 생겼다고 판단하고 급격하게 왼도우를 키운다.

RTT 독립성과 공정성

Reno의 문제: cwnd가 RTT 단위로 증가하므로 RTT가 짧은 연결은 예를들면 물리적으로 가깝다거나. ㅇㅇ 대역폭을 독점하는 불공점함이 존재한다.
CUBIC의 해결: 윈도우 증가가 RTT가 아닌 마지막 손실 이후 경과 시간에 대한 함수로 결정된다. 따라서 RTT가 긴 연결에도 공정하게 대역폭을 확보할 수 있다.

단점 및 해결방안 #

bufferbloat가 있는데 loss based 알고리즘은 패킷이 버려져야만 멈춘다 하지만 하드웨어 발전이 역설적인 문제를 낳았다.

현대의 라우터/스위치는 메모리가 저렴해서 거대한 버퍼 queue를 가지고 있다.

문제점은

cubic이 패킷 손실이 날 때까지 데이터를 밀어 넣는다.
버퍼가 너무 커서, 패킷이 버려지지 않고 거대한 큐에 쌓이기만한다.
결국 패킷 손실은 발생하지 않지만, 지연 시간이 폭증한다.

이 문제를 개선한 차세대 프로토콜과 알고리즘 글은 다음글에 적겠다.

물론 라우터 단에서 timeout걸어서 버려버린다거나, tcp 송신레벨에서 따다다닥 쏘지말고 페이싱해서 일정한간격으로 쏜다거나 물론 그럼 처리량은 낮아지겠지만, nic 드라이버에서 동적 한계를 조절한다거나 뭐 그런 방법으로도 해결이 되겠다.

CoDel이라는 버퍼에 너무 머물면 패킷을 버리는 알고리즘도 있고, (AQM Active Queue Management 알고리즘), FQ-CoDel이라는 Fair Queueing + CoDel 이라는 리눅스 안드로이드 최신 공유기 등의 표준인 Bufferbloat의 킬러 솔루션을 쓰는 방법도 있다.

FQ Codel은 트래픽 흐름별로 차선을 나눠 cubic을 쓰게하는건데, 유튜브 트래픽같이 뚱뚱한건 Bufferbloat가 발생해도 CoDel로 관리, 그 외에 트래픽은 가벼운거. 그런건 cubic 통과하도록 ㅇㅇ 그런느낌의