|
Netmanias white papers |
TCP Congestion Control Mechanism
분석 및 정리: 김범준
게재일: 09/20/2000
연세대학교 네트워크 연구실 박사과정
E-mail: ibrow00@hanmail.net
1. Introduction
TCP (Transmission Control Protocol)의 congestion control mechanism은 1988년의 TCP Tahoe[1]이래 1990년 TCP Reno[3], 1995년 TCP Vegas[4]에 이르기까지 다양한 버전으로 구현되었다. TCP의 congestion control mechanism의 기본적인 알고리즘은 Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery로 구성되어 같이 작동하도록 되어 있다.
TCP의 congestion control mechanism의 주 목적은 송신 단말의 전송률을 직접 제어하여 congestion으로 인해 손실된 데이터를 재전송하기 위함이다. TCP는 OSI reference model의 4계층에 속하는 프로토콜로 송신 단말과 수신 단말사이의 노드의 수에 상관없이 종단간 동작한다. TCP는 송신 단말과 수신 단말을 양 끝으로 하는 하나의 roop를 형성하여 이 roop에 수신측이 전송하는 Acknowledge 정보와 window 그리고 timeout 기능을 이용하여 congestion control mechanism을 구현하고 있다.
2. Slow Start
TCP Tahoe 이전의 TCP는 수신 단말이 알려주는 윈도우의 크기 만큼의 segment들을 전송함으로써 연결(connection)을 맺고 전송을 시작했다. 즉, 수신 단말이 알려주는 윈도우의 크기가 한 segment의 크기보다 크다면 처음부터 여러 개의 segment를 전송하는 것이 가능하였다. 그러나 두 종단 단말 사이에 congestion이 발생하거나 속도가 느린 링크가 존재한다면 중간의 node, 즉 일반적으로 router들은 packet들을 buffering 할 필요가 생기게 되는데 이 같은 경우에 도중에 하나의 router라도 buffer의 용량이 충분하지 않다면 packet의 손실이 발생하게 된다. 손실이 발생하면 손실이 발생했다는 것을 감지하기 위한 지연과 재전송으로 인한 지연이 발생하므로 TCP의 처리율(throughput)은 급격하게 감소하게 된다. 이것이 “congestion collapse” 의 의미이다.
“congestion collapse” 을 해결하기 위해서 “conservation of packets“ 원칙이 나오게 되었다. “conservation of packets“ 원칙은 현재 설정되어 있는 연결이 평형상태에 있다는 것, 예를 들어서 하나의 packet이 완전히 전송되기 전까지는 새로운 packet을 전송하지 않는 상태를 의미한다. 이론적으로 이런 상태에서는 congestion이 발생하는 것이 불가능하지만 실제 internet에는 congestion이 발생하는데 이 원인은 다음의 세가지를 생각해 볼 수 있다.
1) 현재 설정된 연결이 평형상태에 이르지 못 했거나,
2) 송신 단말이 하나의 packet의 전송이 종료되기 전에 새로운 packet을 전송했거나,
3) 망 자원의 한계로 인해서 현재의 path에서는 평형상태에 이를 수 없는 경우
이 중 첫번째 원인을 해결하기 위해서 고안된 알고리즘이 Slow Start이다. 말 그대로 천천히 전송을 시작하여 현재 설정된 연결이 평형 상태에 이르도록 한다는 뜻이다. 송신 단말은 수신 단말로부터의 Ack가 전송되지 않은 상태에서는 새로운 segment를 전송하는 것이 불가능하고 수신 단말 역시 송신 단말이 전송한 segment가 도착하기 전에는 Ack를 전송할 수 없으므로 수신 단말이 전송하는 Ack는 설정된 연결의 일종의 시계역할을 한다고 생각할 수 있는데 이것이 “self-clocking”의 개념이다. 다음 그림 1과 같이 self-clocked된 시스템은 가장 전송속도가 느린 링크에 의해서 영향을 받게 된다.
그림 1. Self-clocking system
즉, 같은 데이터 크기를 갖는 segment를 전송하는 경우 전송 속도가 느린 링크를 통과할 때 전송 지연이 가장 크므로 그 때의 지연 간격으로 Ack도 발생하게 되고 따라서 송신 단말은 그 이상의 전송 속도로 segment들을 전송할 수 있다고 하더라도 Ack가 수신되지 않은 상황에서는 새로운 segment를 전송 할 수 없게 된다. 이와 같이 self-clocked된 시스템은 가장 속도가 느린 링크에 맞추어서 새로운 segment를 전송하므로 당연히 안정 상태에 있게 된다. 그런데 clock역할을 하는 Ack는 송신 단말이 segment를 전송하는 경우에만 발생되므로 맨 처음에 송신 단말이 segment를 전송하기 위한 일종의 규칙이 필요한데 이를 위한 것이 바로 Slow Start이다. 다시 말하면 현재 설정된 연결 및 시스템들을 self-clocking하기 위해서는 수신 단말로부터의 Ack가 필요하고, 이 Ack를 발생시키기 위해서는 송신 단말은 어떤 방법으로든 segment를 전송해야 하는데 이를 위한 것이 Slow Start인 것이다.
Slow Start에서는 기존의 TCP에 cwnd로 표현되는 congestion window가 추가되었다. 처음 연결이 설정될 때 또는 congestion에 의해서 segment의 손실이 발생한 경우 cwnd의 값은 1로 초기화된다. 그리고 송신 단말은 수신 단말이 알려주는 window와 이 cwnd 중 작은 것의 크기 만큼 전송한다. 수신 단말로부터의 Ack가 전송될 때마다 cwnd의 값은 1씩 증가한다. 즉, 송신 단말이 새로운 연결을 설정하고 하나의 segment를 전송한 후 이 segment에 대한 Ack를 수신하면 송신 단말인 2개의 segment를 전송할 수 있다. 그리고 만약 이 두개의 segment에 대한 Ack가 수신되면 다시 4개의 segment를 전송할 수 있고, 다음에는 8개, 16개, 지수적으로 증가한다. 이런 식으로 cwnd는 계속적으로 증가하다가 임계 값인 ssthresh에 이르게 되면 congestion avoidance로 동작하게 된다.
그림 2. Slow Start operation
3. Congestion Avoidance
송신 단말과 수신 단말 사이에 발생하는 packet의 유실은 크게 두 가지의 원인으로 생각해 볼 수 있다. 하나는 물리적인 오류에 의한 경우이고 다른 하나는 congestion에 의해서 buffering되는 과정에서 buffer의 공간이 부족한 경우이다. 최근 전송 기술 및 매체의 발전으로 물리적으로 손실되는 비율은 크게 낮아졌고 따라서 대부분의 packet 손실은 congestion에 의한 것으로 생각할 수 있다. 물론 이 가정은 상대적으로 높은 전송 오류 확률을 가지는 무선 링크의 경우에는 성립하지 않는다.
Congestion avoidance는 congestion이 발생했다는 것을 알리는 과정과 congestion이 발생한 경우 현재의 망 사용을 감소시키는 과정으로 동작한다. Slow start와 congestion avoidance는 별개의 알고리즘이지만 같이 동작한다. 다음의 예는 두개의 알고리즘이 같이 동작하는 예이다.
1) 새로운 연결을 설정할 때 cwnd의 값을 1 segment의 크기로 그리고 ssthresh의 값을 65535로 설정한다.
2) 송신 단말의 TCP는 cwnd와 수신 단말의 window 크기 중 작은 값 만큼 전송한다.
3) Congestion이 발생한 경우 현재 window 크기, 즉 cwnd와 수신 단말의 window중 작은 값의 1/2로 ssthresh의 값을 갱신한다. 이 때 ssthresh의 값은 적어도 1 segment 보다는 커야 한다. 그리고 만약 congestion의 원인이 timeout에 의한 것이라면 cwnd의 값은 1 segment가 되어 다시 slow start 상태가 된다.
그림 3. Combined operation of slow start and congestion avoidance
4) Congestion이 발생하지 않는 경우에는 cwnd의 값은 계속 증가하게 되는데 증가하는 방식은 현재 상태가 slow start인지 congestion avoidance인지에 의해 따라 다르다. 만약 slow start인 경우에는 앞에서 설명한 것과 같이 매번 ack가 수신될 때마다 cwnd의 값을 1 segment 만큼 증가시키고, 만약 cwnd의 값이 현재 설정된 ssthresh값과 같아지게 되면 이후에는 congestion avoidance 상태로 들어가게 된다. Congestion avoidance 상태에서는 매번 ack가 수신될 때마다 cwnd를 1/cwnd만큼 증가시킨다. 이것은 slow start에서의 cwnd의 증가가 지수적인데 반해서 선형적인 증가라고 할 수 있다. 예를 들어서 현재 cwnd의 값이 10이고 따라서 10개의 segment를 전송한 후에 10개의 ack를 수신했다면 cwnd의 값은 원래의 10에 10*1/10을 더한 값이 되므로 11이 된다. 즉, slow start의 경우 한번의 round trip time 동안에 수신된 Ack의 개수 만큼 cwnd를 증가시키는 반면, congestion avoidance인 경우 한번의 round trip time에 최대 한 segment 크기 만큼을 증가시킬 수 있는 것이다.
4. Fast Retransmit
Segment가 손실되었다는 사실은 송신 단말의 TCP가 timeout되는 경우와 수신 단말이 발생시키는 duplicate Ack를 수신하는 두 가지 경우에 의해 알 수 있다. duplicate Ack는 송신 단말이 여러 개의 segment를 전송했는데 수신된 segment의 순서가 틀렸을 경우 수신 단말이 발생시키는 Ack이다. 예를 들어서 송신 단말이 1에서 8까지의 segment를 한꺼번에 전송했는데 이 중 5번 segment를 수신하지 못한 상태에서 6번 segment를 수신한 경우에 수신 단말은 5번 segment에 대한 Ack를 발생시키게 되고 이후 7번, 8번 segment가 수신되더라고 5번 segment에 대한 Ack만을 발생시키게 되는데 이것이 duplicate Ack이다.
그런데 송신 단말의 TCP는 어떤 중복 Ack가 전달되었을 때 과연 segment가 congestion에 의해 손실되었는지 아니면 단순히 순서가 바뀌어서 전달되었는지 알 수 없으므로 일단은 몇 개의 duplicate Ack가 도착하기 까지는 기다리게 된다. 만약 단순히 segment의 순서가 뒤바뀐 것이라면 1개에서 2개까지의 duplicate Ack가 수신되는 동안 순서가 바뀐 segment가 전달되어 새로운 Ack가 발생할 가능성이 높다고 할 수 있는 반면, retransmit threshold(=duplicate acknowledge threshold) 이상의 duplicate Ack가 연속적으로 수신된다면 순서가 바뀐 그 segment는 손실되었을 가능성이 높다고 할 수 있다. 즉, retransmit threshold 이상 연속된 duplicate Ack를 수신하는 경우 TCP는 해당 segment를 retransmission timer가 expire되는 것과 상관없이 바로 전송한다. 예를 들어서 retransmit threshold 값이 3이라면 세 개의 연속된 duplicate Ack가 수신되는 경우에 송신 단말은 해당 segment가 손실된 것으로 판단하고 retransmit하게 된다.
5. Fast Recovery
Fast recovery 가 구현되기 전의 TCP에서는 duplicate Ack에 의해 fast retransmit한 이후 새로운 segment를 전송하기 위해서는 다시 slow start를 실행하도록 되어 있었다. 그러나, duplicate Ack에 의해서 fast retransmit하는 경우 이미 전송중인 segment들이 존재하고 또 duplicate Ack가 발생한다는 사실은 곧 손실된 segment이외의 다른 segment들은 문제없이 전송되었다는 것을 의미한다. 따라서 새로 slow start를 통해서 설정된 연결의 안정한 상태에 도달할 필요 없이 fast retransmit한 이후 바로 congestion avoidance 상태에서 전송할 수 있도록 하자는 것이 fast recovery이다.
Fast recovery는 특히 Bandwidth-Delay product 값이 큰 경우에 효율적이다. Bandwidth-Delay product는 현재 설정된 연결을 통해서 전송되고 있는 데이터의 양을 의미한다. 예를 들어서 segment의 크기가 1Kbyte이고 설정된 연결의 bandwidth가 8Mbps, transmission delay가 1초라고 했을 때 bandwidth-delay product는 8Mbit이 된다. 한 segment의 크기는 1Kbyte이므로 현재 설정된 연결을 통해서 전송되고 있는 segment의 수는 1000개가 된다. 이 bandwidth-delay product의 값은 TCP의 성능 뿐 아니라 fairness에도 큰 영향을 미친다. 다음 그림은 retransmit threshold가 3이고 bandwidth-delay product가 15인 연결을 통해서 fast retransmit과 fast recovery하는 과정을 보여준다.
그림 4. Fast recovery
위의 그림에서 1번 segment가 손실되었다면, 수신 단말은 2번, 3번 그리고 4번 segment가 수신될 때마다 한번씩 duplicate Ack를 발생시키게 된다. Retransmit threshold가 3이므로 4번 segment에 의해서 발생된 duplicate Ack에 의해서 송신 단말은 1번 segment가 손실되었다는 것을 알 수 있게 되고 송신 단말은 즉시 1번 segment를 fast retransmit에 의해 timeout 없이 즉시 전송하게 된다. 이때 2번, 3번, 4번 segment는 수신 단말의 buffer에 저장된다. 송신 단말이 1번 segment가 손실되었다는 것을 알게 된 순간에도 12개의 segment는 전송 중에 있으므로 이 segment들에 의해서 Ack를 얻을 수 있으므로 fast retransmit이후에 slow start를 실행하지 않고 바로 congestion avoidance 상태에서 전송하는 것이 가능한 것이다. 다음 그림 5는 fast retransmit과 fast recovery가 같이 동작하는 것을 보여준다.
1) 세 번의 연속된 duplicate Ack를 받게되면 ssthresh 값을 현재 cwnd/2로 설정하고 손실된 segment를 retransmit한다. 그리고 cwnd값을 ssthresh + 3*segment로 설정하는데 이것은 세 개의 duplicate Ack가 수신되는 동안 송신 단말은 전송을 중단하는데 이 예에서의 retransmit threshold는 3이므로 이것을 보상하기 위한 것이다.
그림 5. Combined operation of fast retransmit and fast recovery
2) Retransmit을 한 이후에 duplicate Ack가 수신되는 경우 수신될 때마다 cwnd의 값을 한 segment size만큼 증가시킨다.
3) 한 round trip delay 후 retransmit한 segment에 대한 Ack가 수신된다면 이것은 buffer에 있던 segment를 포함한, 첫번째 duplicate Ack를 발생시킨 segment와 retransmit 한 segment사이의 모든 segment들은 정상적으로 전송되었다는 것을 의미한다. 이 때는 1) 에서 설정한 ssthresh 값으로 다시 congestion avoidance 상태에서 전송을 계속 하게 된다.
참고로 Fast retransmit은 4.3BSD TCP Tahoe release에서 구현되었고, retransmit 후에는 다시 slow start를 시작하였다. Fast recovery는 4.3BSD TCP Reno에서 구현되었고 앞에서 설명한 바와 같이 retransmit 후에 congestion avoidance 상태에서 계속 전송한다.
6. Reference
[1] V.Jacobson, “ Congestion Avoidance and Control ”, Proceeding of the SIGCOMM’88 Symposium, Aug. 1988.
[2] W.Stevens, “ TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithms”, RFC2001, Jan. 1997
[3] V.Jacobson, “ Modified TCP Congestion Avoidance Algorithm”, end2end-interest mailing list, Apr. 1990.
ftp://ftp.isi.edu/end2end/end2end-interest-1990.mail
