이전 포스팅에서 congestion control은 송신 서버의 데이터 전송과 네트워크의 처리 속도 차이로 인한 네트워크 혼잡을 해결하기 위한 기법이며 이를 위해 송신측에 혼잡 윈도우(cwnd)를 설정한다고 하였습니다.
Congestion Window 구조
cwnd는 sliding window 방식을 이용하기 때문에 ① cwnd 위치 ② cwnd 크기 두 가지가 움직이게 됩니다.
- cwnd 위치: 패킷을 전송하고 ACK를 수신할 때 cwnd 위치를 오른쪽으로 옮겨 이동하게 됩니다.
- cwnd 크기: Congestion control 알고리즘에 따라 cwnd 전체 크기가 변화하게 됩니다.
데이터 전송 시에 cwnd를 이동시키지 않기 때문에, cwnd 안에는 1) 이미 보냈지만 ACK를 받지 못한 패킷, 2) 전송 가능한 패킷 두 가지가 존재하게 됩니다. 이를 통해 드랍이 일어난 패킷의 재전송을 가능하게 해주며, 만약 ACK를 연속적으로 받지 못하여 cwnd가 ACK를 받지 못한 패킷으로 가득 차게 되면 데이터 전송이 불가능하게 됩니다.
송수신측이 패킷을 전송하는데 걸리는 시간이 없다고 가정하면, 첫 패킷의 ACK를 받는 RTT (round-trip time) 동안 cwnd 만큼의 패킷을 전송 후 기다리다가, ACK들을 수신 시 다음 cwnd 만큼의 패킷을 다시 전송할 수 있습니다. 따라서 TCP의 throughput을 일반적으로 아래와 같이 표현합니다.
$$ \text{Throughput}=\frac{cwnd\times MSS}{RTT}~~\text{[bytes/s]} $$
cwnd의 단위는 패킷 수나 byte 두 가지 모두 많이 사용하며, byte로 표현 시 패킷 단위 cwnd에 MSS (maximum segment size)를 곱해주게 됩니다.
cwnd 크기를 조절하는 congestion control은 ① slow start, ② congestion avoidance, ③ fast recovery의 세 가지 state로 구성되어 있습니다.
1) Slow Start
TCP session이 처음 생성됐을 때나 RTO (retransmission timeout)가 발생했을 시 동작하며, 네트워크의 상태를 모르니 혼잡이 발생하지 않도록 cwnd를 천천히 증가시켜보는 state입니다. cwnd는 1로 시작하며 전송이 성공하여 ACK를 수신할 때마다 1씩 증가합니다.
$$ \text{For each ACK,}~~cwnd \leftarrow cwnd + 1~\text{[packets]}$$
송신측은 RTT 동안 cwnd 만큼의 패킷을 전송할 수 있으므로, 모든 전송된 패킷의 ACK를 받으면 slow start에서 cwnd는 RTT 마다 두 배씩 exponential하게 증가하게 됩니다.
지수 형태로 cwnd가 증가하는데 왜 'slow'인지 의문을 가질 수 있겠지만, UDP의 경우는 이러한 제약 없이 처음부터 최대로 전송을 수행하므로 TCP는 상대적으로 느리게 경로의 상태를 확인해가며 전송 속도를 높이는 것으로 볼 수 있습니다.
그렇다면 slow start는 언제 종료될까요? Slow start는 두배씩 전송을 늘리다가 패킷 드랍에 의한 RTO가 발생하면, 네트워크가 수용 가능한 전송량에 도달했다고 판단하고 slow start를 종료하는 임계값인 ssthresh를 설정하게 됩니다. cwnd를 두배를 늘려서 드랍이 발생했으므로 ssthresh는 두배를 늘리기 전인 cwnd 값으로 설정하고, cwnd 값을 1로 리셋시킵니다.
$$ \begin{align} \text{For each RTO,}~~&ssthresh\leftarrow \frac{cwnd}{2}~\text{[packets]} \\\\ &cwnd \leftarrow 1~\text{[packets]} \end{align}$$
이후 slow start를 다시 수행하는데, cwnd 값이 ssthresh 값보다 커지게 되면은 네트워크 용량에 도달했다고 판단하여 slow start를 종료하고 congestion avoidance 단계로 넘어가게 됩니다.
2) Congestion Avoidance
Congestion control의 핵심이며 사용하는 알고리즘에 따라 각기 다른 방식을 사용합니다. 텍스트북에서는 주로 Reno 계열 알고리즘을 설명하기 때문에 이를 기준으로 정리해보도록 하겠습니다.
Reno 계열의 congestion avoidance는 ACK를 수신하면 cwnd를 1/cwnd 씩 늘립니다. 따라서 모든 전송된 패킷의 ACK를 수신한다면, cwnd는 RTT마다 1씩 선형적(linear)으로 증가하게 됩니다.
패킷 드랍이 일어난 경우는 어떨까요? Congestion avoidance에서는 ① RTO, ② 3 dup-ACK (3 duplicate ACK) 두가지 경우로 패킷 드랍 이벤트를 나눕니다. 먼저 RTO가 일어났을 경우는 slow start 상태로 돌아가며 앞과 동일하게 ssthresh를 cwnd/2로, cwnd를 1로 리셋합니다.
3 dup-ACK이란, 동일한 sequence number의 ACK를 세 번이나 연속적으로 받으면 timeout이 일어나지 않아도 패킷 드랍이 일어났다고 판단합니다. 이는 수신측에서 먼저 도착해야 할 패킷이 아닌 다음 패킷이 도착하면, 이전 패킷의 ACK를 재전송하기 때문입니다. 따라서 3 dup-ACK를 수신하면 송신측은 재전송을 수행하는데 이를 fast retransmit이라고 합니다.
$$ \begin{align} &\text{For each ACK,}~~cwnd \leftarrow cwnd + \frac{1}{cwnd}~\text{[packets]} \\\\ \text{*}~&\text{For each 3 dup-ACK (loss),}~~~cwnd \leftarrow \frac{cwnd}{2}~\text{[packets]} \end{align}$$
3 dup-ACK가 발생하면 RTO에 비해 심각한 상황이 아니므로 cwnd를 1로 초기화 대신 절반으로 줄여 전송량을 유지하고자 하는데 이를 위해 fast recovery 상태에 돌입합니다. (※ 위 수식의 3 dup-ACK 부분은 fast recovery 부분을 단순화한 대략적인 동작이며 실제 동작은 다음 포스팅에서 정리해보도록 하겠습니다.)
Reno 계열의 congestion avoidance에서는 RTT마다 cwnd를 1씩 선형적으로 증가시키고 패킷 드랍 (= 3 dup-ACK) 발생 시 1/2씩 공격적으로 줄이기 때문에 이를 AIMD (additive increase multiplicative decrease) 방식이라고 합니다.
따라서 AIMD 방식의 congestion avoidance에서는 위 그림과 같이 cwnd가 변화하는데 이를 saw-tooth 패턴이라고도 합니다. 분량이 길어져서 세 번째 state인 fast recovery의 구체적인 동작에 관해서는 다음 포스팅에서 정리해보도록 하겠습니다.
References
[1] J. F. Kurose and K. W. Ross, Computer Networking: A Top-Down Approach, Pearson, 2016.
[2] W. Stallings, Data and Computer Communications, Pearson, 2014.
네트워크 스터디의 다른 글 목록
- TCP Flow Control & Congestion Control 비교
- TCP Congestion Control: (1) 기본 동작 - 1편
- TCP Congestion Control: (2) 기본 동작 - 2편
- TCP Congestion Control: (3) Cubic
- TCP Congestion Control: (4) BBR
오타나 잘못된 부분 있으면 댓글 부탁드립니다. 도움이 되셨다면 공감 눌러 주시면 감사하겠습니다 :)
'통신 & 네트워크 > 네트워크 일반' 카테고리의 다른 글
| [네트워크] TCP Congestion Control: (2) 기본 동작 - 2편 (0) | 2022.03.19 |
|---|---|
| [네트워크] TCP Flow Control & Congestion Control 비교 (1) | 2022.03.01 |
댓글