Congestion Avoidance And Control

1984년 John Nagle은 Congestion Collapse 로 알려진 상태를 문서화 했다. Congestion Collapse는 네트워크 노드사이에서 대역폭 용량의 불균형으로 네트워크에 영향이 끼쳐지는 것을 말한다.

Congestion Control은 복잡한 네트워크상에서 발생되는 문제이다. 미국방부의 IP, TCP 계층이 동시에 하용될 때 전송계층과 datagram계층 사이의 상호작용으로 예기치않게 congestion 문제가 발생되는 것을 발견했다. 특히 IP 게이트웨이들이 광범위한 다른 대역의 네트워크와 연결할 때 congestion collpse 라고 부르는 현상에 취약했다.

어떤 호스트이건 네트워크로 동일한 datagram을 복사하여 전송을 시작할 때, roundtrip 시간이 최대 재전송 간격보다 길어야 한다. 이제 네트워크는 심각한 문제에 봉착한다. 결국 스위칭 노드에서 사용가능한 버퍼가 가득차게되고 다른 패킷들은 무시된다. 전송되는 패킷의 roundtrip time은 최대값이 된다. 호스트들은 같은 패킷을 여러번 반복해서 보내고 결국 몇몇의 동일한 패킷이 목적지에 도착하게 되어 congestion collapse가 발생하게 된다.

이 상황은 안정적이다. 한번 포화상태에 도달하게 되면 패킷을 선택하는 알고리즘에서 패킷을 무시하고 네트워크는 성능이 저하된 상태에서 계속 동작한다.

위의 내용은 ARPANET에서는 congestion collapse가 문제가 되지 않는다는 것을 나타낸다. 왜냐하면 ARPANET의 대부분 노드는 비슷한 대역을 사용하고 허용량을 초과하는 경우 이를 처리할 대체 알고리즘을 갖고 있다. 그러나 오랫동안 이주장이 사실로 알려졌지만, 1986년 5천개가 넘는 다양한 노드가 네트워크에생성되면서 일련의 Congestion collapse 사고들이 네트워크에서 퍼져나갔다. 어떤 경우에는 천가지 정도의 요인들로 인해 효율이 떨어지고 네트워크가 사용 불가능하게 되었다.

이 문제를 해결하기 위해 TCP에 여러가지 방법들이 적용되었다. 양 방향으로 보내질수 있는 데이터의 비율을 조정하는 방법으로 흐름제어, 체증제어, 체증회피라고도 한다.

Flow Control

흐름제어는 Receiver가 바쁘거나 큰 데이터를 처리하거나 할당된 버퍼의 크기가 초과하여 Sender가 보내더라도 처리될수 없는 데이터를 과도하게 보내는 것을 막는 구조이다. 이러한 현상을 해결하기 위해 TCP 연결 양단에서 입력 데이터를 처리할 수 있는 버퍼 Window의 크기(rwnd)를 알려준다.

연결이 처음 수립되었을 때 수\/발신측은 각자의 rwnd의 값을 기본 시스템 세팅에 따라 초기화한다. 전형적인 웹 페이지는 서버로부터 클라이언트에게 다량의 데이터를 전송하여 Client의 Window는 병목 현상이 발생하게 된다. 그러나 만약 Client가 SErver에게 이미지나 비디오 같은 대량의 데이터를 업로드하면 서버의 Receive Window는 제한 조건이 된다.

여러가지 양측 중에 하나가 지속할수 없다면 Sender에게 더작은 Window를 알릴 수 있다. 만약 Window가 0에 도달한다면 응용프로그램 계층에서 버퍼가 비워질 때까지 더이상 데이터를 보내지말라는 신호를 보낸다. 이러한 흐름은 모든 TCP연결이 지속되는 동안 계속된다. 각각의 ACK 패킷은 최근의 rwnd(Reciever Window)의 크기를 전달하고 동적으로 데이터 흐름의 비율을 조정한다.

Slow-Start

합 증가\/곱 감소 방식이 네트워크의 수용량 주변에서는 효율적으로 작동하지만 처음에 전송 속도를 올리는 데 걸리는 시간이 너무 길다는 단점이 있다. 느린 시작(Slow Start) 방식은 합 증가\/곱 감소 방식과 마찬가지로 패킷을 하나씩 보내는 것부터 시작한다. 그러나 이 방식은 패킷이 문제없이 도착하면 각각의 ACK 패킷마다 창 크기를 1씩 늘린다. 즉, 한 주기가 지나면 창 크기가 2배로 된다. 따라서 전송 속도는 합 증가\/곱 감소와는 다르게 지수 함수 꼴로 증가한다. 대신에 혼잡 현상이 발생하면 창 크기를 1로 떨어뜨린다. 처음에는 네트워크의 수용량을 예상할 수 있는 정보가 없지만 한번 혼잡 현상이 발생하고 나면 네트워크의 수용량을 어느 정도 예상할 수 있으므로 혼잡 현상이 발생하였던 창 크기의 절반까지는 이전처럼 지수 함수 꼴로 창 크기를 증가시키고 그 이후부터는 완만하게 1씩 증가시킨다.

초기에 지수 함수꼴로 창 크기를 빠르게 증가시키는 방식의 이름이 느린 시작인 것이 어울리지 않는 것이라고 생각할 수도 있다. 하지만 느린 시작의 의미는 선형 증가 방식과 비교해서는 안 되고 느린 시작이 발명되었을 당시 TCP의 동작 방식과 비교해야 한다. 이전의 TCP 동작은 처음에 최대한 보낼 수 있는 만큼의 패킷을 보내는 것으로 시작하고, 느린 시작은 이것과 달리 창 크기를 1에서부터 시작하여 지수함수 꼴로 증가시켜가면서 네트워크의 수용량을 감지한다.

이 방식은 합 증가\/곱 감소 방식보다 더 효율적인 방법이지만 마찬가지로 혼잡한 상황이 된 경우에는 타임아웃이 될 때까지 기다리는 동안 큰 시간의 공백이 있다.

-from Wikipedia

TCP에서 흐름제어가 존재함에도 불구하고 1980년데 중반부터 후반까지 Congestion Collapse는 실제 이슈가 되었다. Receiver가 Sender로부터 데이터로 인한 성능이 저하되는 것을 막는 흐름제어의 문제는 양쪽 모두를 네트워크상의 과도한 데이터로부터 보호할수 있는 장치가 없었다. 새로운 연결을 수집할 때 Sender나 Receiver 모두다 가능한 대역폭을 알수 없었고 이를 측정할 수 있는 과정이 추가적으로 강화되었다.

Adaption이 적합한 예를 한가지 들어보자, 당신이 집에 있고 큰 동영상 파일을 서버로부터 받는다고 상상해보자 당신의 집 네트워크에 열려있는 다른 사용자의 새로운 연결은 몇몇 소프트웨어를 업데이트 한다 그러면 갑자기 비디오 다운로드 가능 속도가 급격히 줄어들고 비디오 서버는 다운로드 속도를 조절한다. 그렇지않으면 같은 성능 상황에서 중개 게이트웨이에 패킷이 쌓이고 패킷들은 무시되어 네트워크 비효율을 가져온다.

1988년 Van Jacobson과 Michael J. Karels는 이 문제를 해결하기 위해 몇몇 알고리즘을 문서화 했다. Slow-Start, Congestion Avoidance, Fast Retransmit, Fast Recovert. 4가지 모두 빠르게 TCP 명세에 의무적인 조건이 되었다. 실제로 이 부분들은 광범위하게 적용되었고 TCP를 업데이트 함으로써 80년대 중반부터 90년대 초까지 기하급수적으로 계속 증가하는 트래픽으로 인한 인터넷의 재앙을 막았다.

Slow-Start는 동작을 살펴보는 것이 가장 이해하기 쉽다. 일단, New York에 있는 Client의 상황으로 돌아가보자, London에 있는 서버로부터 파일을 받으려고 한다. 먼저 Three-Way Handshake가 수행되고 그러는 동안 서로의 receive Window 사이즈를 ACK 패킷을 통해 알린다. 마지막 ACK Packet이 전달되면 응용프로그램 데이터의 교환을 시작할수 있다.

Client와 Server 간의 사용가능한 용량을 측정하기 위한 유일한 방법은 교환된 데이털르 통해 측정하는 것 밖에 없다. 그리고 이것은 Slow-Start가 고안된 방법이기도 하다. Server는 새로운 Congestion Window(cwnd)를 TCP Connection마다 초기화하고 시스템에 명시된 값을 세팅한다.

Congestion window size (cwnd)

• Sender 측에서 Client로 부터 받는 ACK이전에 전달할수 있는 데이터의 제한이다.

cwnd값은 알려지지도 않고 Sender와 Receiver간에 통신되지 않는다. 이와같은 상황에서 London에 있는 서버에 의해 공개되지 않은 값으로 유지된다. Client와 Server 사이의 전달할수 있는 데이터의 최대크기는 rwnd와 cwnd의 최소값이다. 여태까지는 그런대로 잘 동작했지만 Server와 Client가 각자의 Congestion Window Size의 최적화 값을 어떻게 확인할까. 무엇보다도 같은 노드에 존재하더라도 네트워크 상황이 시간마다 다르고 이전 예를 보았듯이 두 네트워크 사이에\/\/ 각각의 연결마다 윈도우 사이즈를 직접 조정할 필요가 없는 알고리즘을 사용할수 있다면 최고일 것이다. 이 해결방법은 ACK된 패킷의 Window Size를 키우는 것과 Start-slow를 하는 것이다. 본질적으로 cwnd의 초기값은 1 Segment로 설정되도록 RFC 2581에 선언되어 있었고 1999년 4월에 4Segment 로 증가하였다 2013년 4월에 발표된 RFC 6928에서는 한번에 10 Segment이상까지 값이 증가하였다.

새로운 TCP 전송간에 최대 데이터 양은 rwnd와 cwnd값중 최소값이다. Server는 Client에게 10 네트워크 Segment들을 전송할 수 있다. Slow-Start 알고리즘은 모든 ACK가 수신되면 Server가 cwnd window 크기를 1 Segment 증가시킬수 있다고 알려준다. 이러한 TCP 연결의 양상은 Expotential Growth 알고리즘이라고 알려져 있다. Client와 Server가 둘 사이의 네트워크 경로에 가능한 대역폭을 빠르게 결합을 시도한다.

Slow-Start는 브라우저를 사용하는 응용프로그램을 만들때 명심해야하는 중요한 요소인 이유가 무엇일까? 사실 HTTP와 많은 TCP 위에서 동작하는 다른 많은 응용프로그램 프로토콜들은 모두다 반드시 slow-start 단계를 거쳐야한다.