minzzl
[Congestion control] -혼잡제어에 대한 소개 본문
안녕하세요,
앞으로 혼잡제어 알고리즘과 관련하여 포스팅을 해볼 예정입니다.
*
아래에 작성해 가는 글들은 오리뎅이님의 블로그와 아래의 글들을 보고, 제 머리 속에 새기기 위해 써내려가는 글임을 미리 밝힙니다...
https://meetup.nhncloud.com/posts/53
https://brainbackdoor.tistory.com/111
https://www.inven.co.kr/webzine/news/?news=165870
혼잡제어는 TCP를 배울 때, TCP는 신뢰할 수 있는 프로토콜로 흐름제어, 오류제어, 혼잡제어 기능을 수행한다고 하며 들어보셨을겁니다.
흐름제어와 헷갈린다면 여기 클릭 https://minzzl.tistory.com/53
이미 Flow Control에 대해서는 위의 링크를 통해 확인하셨겠지만, TCP Rx Socket Buffer가 꽉 차서 넘치는 것을 방지하는 매커니즘이라는 것을 알았습니다. 그럼 Cogestion Control은 왜 하는 것일까요?
혼잡제어
Congestion Control은 네트워크에서 Congestion이 발생한 것을 감지해서, Congestion을 경감시키기 위해서 동작하는 TCP 송신제어 알고리즘입니다. 혼잡제어란 네트워크 혼잡정도에 따라, 송신자가 데이터 전송량을 제어하는 것입니다. 또한 혼잡 정도의 판단 기준은 데이터의 손실 발생 유무로 판단합니다. 전송한 데이터에 누락이 발생하면 네트워크가 혼잡한 상태로 판단하여 전송량을 조절합니다
즉, Congestion Control은 발생하지 않도록 예방하는 알고리즘이 아니라, 이미 Congestion이 발생하고 난 이후에 congestion을 줄이기 위해서 동작하는 알고리즘입니다. 그렇기 때문에 네트워크에서 Congestion이 발생한 이후에 Congestion Control은 동작합니다.
Network Congestion Situation
흔히 네트워크 혼잡 상황이란, 네트워크에서 존재하는 스위치, 라우터, AP, 방화벽, L4 등의 네트워크 장비에 존재하는 Buffer, FIFO, 또는 Quere 등으로 부르는 트레픽 임시 저장 공간이, 트래픽 처리하는 속도가 트래픽이 들어오는 속도를 감당하지 못해여 꽉 차서 넘치는 것을 의미합니다.
그렇다면 TCP는 네트워크에서 Congestion이 발생했는지 어떻게 알 수 있을까요?
사실 TCP는 congestion이 발생했는지 어떤 다른 이유에 의해 데이터가 drop되었는지 알 수 없습니다. TCP는 아래의 두가지 조건으로 TCP Congestion이 발생했다고 판단하기 때문입니다.
1) TCP Retransmission Timeout이 발생하면 TCP는 네트워크에서 congestion이 발생한 것으로 인식한다.
TCP 는 매 패킷 전송시마다 Retransmission Timer를 구동시킵니다. Retransmission Timer가 만료될 때까지 그 패킷을 수신자가 잘 받았다는 의미의 ACK 수신이 되지 않으면 TCP 송신자는 네트워크에서 congestion이 발생하여 패킷이 드랍된 것으로 판단합니다.
2) 동일한 ACK 패킷이 연속해서 3회 수신되면 TCP는 네트워크에서 congestion이 발생한 것으로 인식한다.
TCP 수신자는 패킷 하나가 드랍이 되고, 그 이후의 다른 패킷이 수신되면 드랍된 패킷을 재전송해달라는 의미로 드랍된 패킷에 대한 ACK를 다른 패킷 수신에 대한 ACK로 보냅니다. 즉 1, 2, 3, 4, 5, 6 의 패킷을 송신자가 보냈을 때, 수신자가 3번 패킷을 받지 못했다면 3번을 받아야하기 때문에 4, 5, 6 번 패킷에 대한 ACK를 3번에 대한 것으로 보냅니다. 이렇게 연속해서 동일한 패킷에 대한 ACK가 3번 수신되는 경우 TCP 송신자는 네트워크에서 congestion이 발생한 것으로 판단합니다.
즉 , TCP 송신자가 네트워크에서 congestion이 발생했다고 판단하는 2가지 조건 모두 실제로 congestion에 의한 패킷 drop인지 다른 이유에서 인지 알길이 없습니다. 어찌되었던 TCP 송신자는 TCP Congestion이 발생했다고 판단되면, Congestion window를 Congestion이 발생하기 이전의 window sizedml 절반으로 줄이고, TCP Window로 cwnd를 사용합니다. 즉 Send window 크기를 줄임으로써 트래픽 전송량을 줄입니다. 이는 트래픽 전송량을 줄임으로서 network에서 발생했다고 판단되는 congestion을 해소 시켜주기 위한 동작입니다.
TCP의 속도를 높여주기 위해서는 Window size를 키워야하는데, congestion이 발생하면 window 사이즈를 줄여주기 때문에 당연히 속도는 저하됩니다.
Congestion Control의 탄생
1980년 10월 , 사건이 발생하게됩니다.
당시 최첨단 32Kbps 회선이 40bps 밖에 전송을 못하는 일이 발생하는 것입니다. 즉, 1000분에 1의 속도 밖에 못내는 일이 발생한 것이죠.
연구자들이 확인해보니, 중간에 패킷을 전달하는 장비인 라우터가 문제였습니다. 그런데 장비가 고장이라는 뜻이 아니라 인터넷이 여러 연구기관에서 쓰다보니 그 라우터에 과부하가 걸려 상당히 많은 패킷을 놓치고 있던 것이죠. 그런데 TCP는 패킷이 유실되는 확률이 올라가면 ACK와 재전송때문에 그 속도가 더욱 느려집니다. 또한 앞선 상황에서 모두 재전송을 시도하면 상황은 더욱 악화되었을 것입니다. 그 때 반 제이콥슨이 등장합니다.
그는 패킷이 유실되면 무식하게 바로 쏴대는 것이 나리라, 중간 장비에 과부하가 걸린 것일 수 있으니 양을 조절하자고 제안합니다. 또한 중간의 장비가 과부하 걸려서 패킷들을 놓치는 것을 길에 차들이 몰려서 꽉막히는 것에 빗대어 체증이라고 합니다. 그리고 라우터 장비등은 교통 교차로에 비유됩니다. 이 사건 이후로 TCP에는 이런 교통 체증을 벗어나기 위한 반 제이콥슨의 알고리즘이 도입되었습니다. 이것이 TCP Taeoe에 등장입니다. 이후에 이를 개량하기 시작해서 TCP Reno, TCP Vegas 등이 등장하기 시작합니다.
Network에서 congestion이 발생하는 상황
그렇다면, 언제 혼잡제어가 발생할까요?
- Case 1 : 1G port 2개에서 들어오는 input traffic이 1개의 1G output port로 나갈 때 // Aggregation
- Case 2 : 1G port 1개에서 들어오는 input traffic이 1개의 100Mbbs output port로 나갈 때 // Speed mismatch
case 1번은 2개 이상의 Input port에서 들어오는 트래픽이 하나의 port 로 몰리는 경우이고, case 2번은 input port의 speed가 output port의 speed보다 큰 경우입니다.
두 가지 상황 모두, 입력되는 트래픽 양의 출력 포트에서 처리할 수 있는 양보다 많은 경우 발생할 수 있습니다. Speed mismatch 상황인 case 2에서는 buffering이 발생하는 장소는 output port 의 buffer 입니다. 그러나 Aggregation의 경우 output queue 뿐만아니라 input queue에서도 발생합니다. 2개 이상의 port가 동시에 하나의 포트로 트래픽을 보내려고 하는 상황은 경쟁 상황이라고 하고, 그러한 상황에서는 1개의 포트의 트래픽만 처리 될 수 있고 다른 포트의 트래픽은 input queue에 저장되어 대기해야합니다. 실시간으로 처리가 안되는 패킷들은 input queue 또는 output queue에 저장되어 대기해야합니다. Queue의 크기가 너무 작으면 쉽게 넘쳐서 drop이 발생할 것이고 크기가 너무 크면 buffering delay가 증가합니다. 이러한 queue의 크기로 인해 어떠한 일이 발생할까요?
크기가 작을 경우, buffer overflow에 의한 패킷 drop으로 TCP 송신자가 DUP_ACK를 연속 3회 수신할 수 있습니다. 만약 크기가 클 경우 buffering delay 증가로 인한 TCP Retransmission timeout이 발생할 수 있습니다.
혼잡제어 .. 그래서 어떻게 하는건데 ...
RFC 2001에서는 Congestion Contro의 4가지 알고리즘에 대한 소개가 나옵니다. 1) Slow Start 2) Congestion avoidance 3) Fast Retransmit 4) Fast Recovery 입니다.
그럼 각각 알아봅시다.
Slow Start
Slow start 단계에서는 segment 1개을 보내고, ACK이 돌아오면 2개를 보내고, 또 ACK이 돌아오면 4개를 보내고 하는 식으로 한번에 보내는 데이터를 segment 갯수를 2배씩 증가시킴으로서 exponential하게 증가시켜나갑니다. 제일 처음에 보내는 setment(initial cwnd)는 OS에 따라서 1,2 또는 10을 사용합니다. 처음에는 대부분 1을 사용했었지만 네트워크 기술 발달로 좀 더 빠른 네트워크에서 속도를 빠르게 알리기 위한 방법으로 10을 사용하는 경우도 나타나게됩니다. 사실 계속해서 exponential 하게 cwnd가 증가하더라도, send window는 congestion window와 recieve window. 송신자 retransmission quene 중에서 가장 작은 값이기 때문에 무한대로 올라가지는 않습니다.
네트워크에서 bottleneck이 존재해, congestion 이 발생하는 경우 어느 순간 buffer는 꽉차서 넘치게 됩니다. 그러면 TCP 송신자는 congestion control을 수행해서 congestion window sizw를 줄입니다. 당연히 TCP의 속도는 줄어듭니다. 위에서 이야기 했든, Bottleneck을 없애기 위해 마냥 buffer의 크기를 키울 수도 없습니다. 왜냐하면 Buffer size를 키우기 위해서 그만큼 buffering delay가 증가하기 떄문입니다. 그래서 마냥 늘리는 것이 아니라 최적화해야합니다. Network bottleneck의 bandwidth와 buffer size를 알면 TCP 최고 속도가 얼마까지 나오는지 알 수 있고, 최대 buffering delay가 얼마나 발생할 수 있는지도 알 수 있습니다.
slow start를 설명하는 그림에는 항상 congestion window가 2배만큼 segment가 증가하다가, 어느 순간 네트워크의 어느 버퍼가 꽉차서 넘치는 packet loss 상황이 오고, 그럴 경우 ssthresh 만큼 congestion window 크기를 줄여서 거기서부터 segment 수를 1개씩 증가 시키는 congestion avoidance 단계로 들어갑니다.
어찌되었던 정리해보면
slow start는 TCP connection이 맺어진 직후에 네트워크 congestion이 발생하는 window size를 탐지하기 위해서 ACK가 돌아올 때 마다 segment를 2배씩 키워보내는 것입니다. 또한 packet loss가 감지되면 이전 congestion window size를 ssthresh 값으로 설정하고 이후에 congestion avoidance 단계에서 ssthresh 값으로 부터 segment 를 하나씩 증가시키면서 network congestion이 발생하는 지점을 찾아나섭니다.
그럼 TCP window는 항상 2배로 증가하는 것이 아니다?
사실 앞에서는 이해가 쉽도록 하기 위해 TCP Sender는 TCP segment를 1개 보내고 ACK가 돌아오면 2배씩 해서, exponentioal 하게 증가시켜 보낸다고 이야기했습니다. 사실 실제로는 Congestion window는 정확하게 2의 배수로 증가하지 않습니다. 모든 segment마다 ACK를 보내지 않을 수 있기 때문입니다. 이러한 방식을 Delayed ACK라고 하며, 이를 사용하는 경우에는 매 segment 마다 ACK를 보내는 것이 아니라 아래의 2가지 경우에 ACK를 보냅니다.
- 1개 segment를 받은 후에 timeout 이전에 n번 째 segment를 받은 경우
- 1개 segment를 받은 후에 timeout이 발생한 경우
Delayed ACK를 사용하는 경우에는 매 segment 마다 보내는 것이 아니라, 대개 2 segment에 한번 씩 ACK가 오기 때문에 CWND는 2의 배수로 증가하지 않습니다. 그리고 꼭 Delayed ACK 방식을 사용해야하는 것은 아닙니다. Cumulative ACK 방식과 같은, TCP Sender가 ACK 1000을 받았다면, 999번까지 잘 받았으니 이제 1000번을 달라는 의미의 ACK 일 수도 있습니다.
요약해보면, 3가지 패턴의 ACK가 가능합니다.
- Delayed ACK, AckFrequence = 2, 적어도 2 segment에 한번 ACK를 보냄
- Delayed ACK, AckFrequence = 1, 매 segment마다 ACK를 보냄
- Cumulated ACK, 여러 segment 마다 불규칙하게 ACK를 보냄
어찌되었건.. CWND가 2배씩 증가하지 않더라도 당황하지 않으셔도 됩니다 !~!
congestion avoidance
SSTHRESH dafault value ... 있는건가 .. 없는건가 ..
우리는 congestion control을 배울 때 아래의 그림들을 본 적이 있습니다.
그럼, 둘의 차이점은 무었일까요? 보이시나요?
그림 1은 처음에 하늘 높이 뾰족하게 솟아 올랐다가 뚝 떨어지는 부분이 있고, 그림 2는 뒤에 slow start가 한번 더 있습니다. 그림 2에서는 Slow Start 과정에서 Window Size가 ssthresh1에 도착한 이후에 Congestion Avoidance 단계로 바뀌었습니다. ssthresh는 slow start threshold를 의미합니다. Exponential 하게 증가하는 slow start 단계를 언제까지 수행 할 것인지를 결정하기 위해서 ssthresh 라는 변수를 사용합니다. RFC 5681 에는 CWND가 sstresh를 초과하거나 congestion이 목격되면 slow start가 종료된다고 되어 있습니다.
TCP Connection이 맺어지고 바로 직 후에 시작되는 Slow Start 단계에서는 TCP sender의 ssthresh defalt 값이 얼마로 정해져 있을까요? 만약 초기 defalut 값으로 정해진 값이 없다면 그림 1과 같이 packet loss가 발생할 때까지 Window Size가 증가하다가 packet loss가 발생하면, congestion이 발생한 것으로 판단하고, 이 때의 Congestion Window의 절반크기를 ssthresh로 설정하고 다시 slow start 단계를 시작합니다. 다시 slow start를 시작한 경우에는 Congestion WIndow Size는 packet loss가 발생하지 않으면 ssthresh까지 증가한 이후에 congestion avoidance 단계로 진입합니다.
TCP Throughput이 Saturation(포화)되는 경우
대표적으로 많이 사용되는 linux 의 경우 congestion control 알고리증으로 CUBIC을 사용하는데, ssthresh default 값이 없다는 것을 경험할 수 있습니다. 이말은 즉슨, Slow start 단계에서 packet loss가 발생하지 않으면 CWND 크기는 수신자의 최대 socket buffer 크기인 TCP Rx Maximum window size 까지 증가하게 됩니다. CWND가 slow start 단계에서 TCP Rx Maximum Window Size까지 증가하는 경우는 아래의 3가지가 있습니다.
- 네트워크 구간에 병목구간이 없다
- 네트워크에 병목구간이 있고, TCP Rx Maximum WIndow Size 로는 병목구간 BW를 모두 사용하지 못하지만, Rx Maximum WIndow Size가 병목구간 buffer크기에 비해 작아서 buffer overflow가 발생하지 않는다.
- 네트워크에 병목구간이 있고, TCP Rx Maximum Window Size는 병목구간 BDP에 비해 훨씬 크지만 병목구간 buffer가 워낙커서 buffer overflow가 발생하지 않는다.
Congestion avoidance... 그거 왜하는건데...
병목구간의 버퍼가 아무리 크다고 할지라고 여러개의 TCP traffic들이 동시에 몰려서 congestion이 발생하면 buffer overflow에 대한 packet 유실은 피할 수 없습니다. 그러한 network congestion 상태를 TCP sender에서 감지하고 network congestion 상태를 회피하기 위해서 TCP Congestion Control 알고리즘이 도입되었습니다. Slow start와 Congestion Avoidance는 TCP Sender가 network에서 congestion이 밸생하는 Window Size를 탐지하기 위해서 사용하는 알리즘들입니다. 다시 말하면 network에서 가용한 bandwidth를 찾아내기 위해서 TCP는 Slow Start와 Congestion Avoidance를 사용합니다. 사실 병목구간의 가용한 bandwidth를 찾는다기 보다는, packet loss 가 발생할 때까지 계속 Window size를 증가하니까 packet loss가 발생하지 않는 window size를 찾는다고 말하는 것이 맞겠습니다.
다시 그림을 보며 설명하겠습니다.
Slow start 단계에서 CWND는 packet loss가 발생하지 않을 경우, 매 RTT마다 exponetial 하게 증가합니다. Fast Retransmission과 Fast Recovery 알고리즘이 등장하기 전까지는 초기 Slow Start 단계에서 packet loss가 발생하는 경우 TCP 송신자는 retransmission timeout으로 packet loss를 감지했습니다. packet loss를 감지한 TCP 송신자는 sstresh 값을 바로 직전의 CWND 값으로 설정하고, CWND를 초기값으로 되돌려서 Slow Start 를 처음부터 다시 수행합니다. CWND 가 ssthresh 값에 도달하면 이 때 부터는 packet loss 가 발생한 지점을 더욱 정밀하게 탐지하기 위해서 CWND 값을 RTT 마다 1씩 증가시키면서 packet loss 발생지점을 찾습니다. 이렇게 CWND를 매 RTT 마다 1씩 증가시키는 구간을 Congestion Avoidance라고 합니다.
CWND 크기를 exponential하게 증가시키는 Slow start 단계에 비해서 1씩 증가하는 것은 congestion을 실제로 회피하는 것이 아니고, 단지 congestion 발생지점을 천천히 찾아 가는 것일 뿐이라는. . 아주 신기한 점을 기억하면됩니다 ..!
어찌되었던 실제 network에 congestion이 발생하고 있다면, CWND를 1씩 증가시키더라도 어느 순간엔 packet loss가 발생하게 될 것입니다. packet loss가 발생하면 다시 ssthresh 값을 직적 SWND의 절반으로 줄이고 다시 slow start를 수행합니다.
그런데, Packet loss 가 발생할 때마다 매번 Retransmisson Timeout이 발생할 때까지 기다려야하고, CWND 초기 값부터 다시 slow start를 수행해야했으니 packet loss가 발생하는 환경에서는 얼마나 비효율적일까요? 이러한 불합리한 것을 해결하기 위해 도입된 것이 Fast Retransmission 과 Fast Recovery 알고리즘입니다.
그렇다면 Fast Retransmission 과 Fast Recovery에 대해 알아봅시다.
Fast Retransmisson 과 Fast Recovery 는 초기 TCP congestion control 알고리즘에 포함되어 있었던 것은 아닙니다. 초기에는 slow start와 congestion avoidance만 있었습니다. congestion avoidance 단계에서 packet loss event (Retransmisson timeout)가 발생하면 ssthresh를 CWND의 절반으로 줄이고 Slos start를 Initial CWND부터 다시 시작했었습니다. 아래의 그림이 Fast Retransmission과 Fast recovery가 없을 때 Congestion Control 알고리즘 동작을 설명하는 그래프입니다.
Retransmission과 Fast recovery는 패킷 유실의 상황인 Retransmission Timeout 과 DUP_ACK 3번 중, DUP_ACK 3번과 관련이 있습니다.TCP는 수신자가 ACK를 보내는 경우는 앞에서 살펴 본 바와 같이 delayed ACK나 cumulative ACK나 어떤 정해진 룰에 의해서 새로운 packet을 받았거나 timer가 expired 됐을 때 보냅니다. Packet loss가 발생함 경우, 실제로 받아야할 다음 패킷이 아니라 나중에 받아야할 packet이 더 먼저 수신됩니다. 이렇게 packet loss에 의해서 순서에 맞지 않는 packet을 먼저 받는 경우 수신자는 delayde ACK나 cumulative ACK 방식에 상관없이 그런 packet을 받을 때마다 즉시 아직 받지 못한 packet에 대한 ACK를 다시 보냅니다. 만일 packet loss 가 아니라 network 에서 순서가 역전되어 이전 packet이 들어 오는 out of order의 경우라고 하더라도 3개의 다른 packet이 들어오기전에는 순서 역전되었던 이전 packet이 들어올 것이라고 가정한 것입니다. wmr 3개의 연속된 DUP_ACK를 받는 경우는 수신자가 packet loss 이후 다른 3개의 packet을 수신해서 보낸 것이라고 반단하고 바로 retransmission을 수행하도록 했습니다.(Fast Retransmission) 그리고 이 경우에는 굳이 CWND 를 초기값에서 부터 다시 slow start를 하지 않고 CWND를 현재의 절반으로 줄인 후에 바로 congestion avoidance를 수행해서 packet loss가 발생했던 CWND의 직전까지 빠르게 찾아갑니다. (Fast Recovery) 물론 Fast retransmission과 Fast recovery를 사용하는 경우라고 하더라도 RTO가 발생하는 경우는 이전과 동이랗게 ssthresh를 현재 CWND의 절반으로 설정하고CWND를 초기값으로 되돌려서 Slow start를 수행합니다.
지금까지 설명한 것은 packet loss 기반의 전통적인 TCP Congestion COntrol 알고리즘입니다. Tahoe, Reno, New Reno, BIC, CUBIC 등의 packet loss based congestion algorithm을 사용하는 TCP들입니다.
Packet Loss based congestion control 알고리즘
Packet loss를 이용해서 network의 congestion 을 감지하고 congestion control을 수행하는 TCP는 CWND를 무식하게 증가시킵니다. Buffering delay가 아무리 증가해도 packet loss만 나지 않으면 CWND를 계속해서 올립니다.. 병목 구간의 bandwidth가 얼마이던지 상관없이 무조건 TCP sender의 media seppd로 쏟아부어버립니다. 이러한 불합리한 점들을 개선하기위해, packet loss 대신에 delay증가를 이용해서 네트워크의 congestion을 rkawlgksms delay based congestion control 알고리즘이 등장합니다.
Delay based congestion control 알고리즘
Vegas, Westwood, Westwood + 등이 delay를 이용해서 congestion control을 수행합니다. Window에서 사용하는 Compound TCP는 packet loss와 delay를 모두 사용해서 congestion control을 수행합니다. 가장 최근에 나온 congestion control 알고리즘은 Google에서 개발한 TCP BBR입니다. 이름에서 느껴지듯이 병목구간의 bandwidth와 delay를 모두 고려한 것입니다. buffer float도 개선하면서 throughput도 높일 수 있다고 하니 ... 굿입니다.
'논문 > QUIC' 카테고리의 다른 글
| Network Simulator - NS-3 소개, 그리고 설치 방법 (0) | 2023.03.07 |
|---|---|
| [Congestion control] -혼잡제어 알고리즘 (0) | 2023.03.03 |
| TCP의 window based Flow Contorl (흐름제어) (0) | 2023.02.21 |
| 리눅스 tc 명령어 사용법 (0) | 2023.02.19 |
