TCP variant versions -- congestion control.

(From http://icc.skku.ac.kr/~hedwig/pds/2006/CN_20060419.doc)

CN_20060419.doc

1.        Basic

Transmission Control Protocol(TCP)은 Sender 측의 buffer overflow를 방지하기 위해 intermediate router 단에서 Congestion Control을 수행한다. TCP는 송신자 측에 CongestionWindow(cwnd)라는 변수를 두어 네트워크 혼잡제어를 수행한다.

                  TCP는 패킷 손실이 발생하지 않는 한 slow start와 congestion avoidance를 통해서 윈도우의 크기를 지속적으로 증가시키므로 언젠가는 혼잡으로 인한 패킷 손실이 발생한다. 따라서 TCP는 패킷 손실을 감지하고 복구하기 위한 손실 복구(loss recovery) 기능을 수행한다. TCP의 Slow start와 Congestion avoidance를 비롯하여 TCP variants의 Fast Retransmit, Fast Recovery 과정을 살펴본다.

1.1.     Slow Start

ACKs가 정상적으로 도착하였을 때 작은 Window size로부터 시작하여, 개별 segment가 acknowledged 되었을 때 마다 exponentially(지수적)으로 증가한다. 이때 지속적으로 체크되는 CongestionWindow(송신자-cwnd)라는 변수를 운용한다. 그림 1의 파란색 부분을 참고한다.

1.2.     Congestion Avoidance

Slow Start의 지수적 증가가 어떤 threshold(ssthresh 변수) 에 도달하게 되면 network congestion이 곧 일어나게됨을 간주하고, 이를 회피하기 위해 cwnd 변수가 linear 하게 증가하도록 한다. 그림 1의 노란색 부분이 Additive Increase로 Congestion Avoidance에 해당한다. 이 밖에도 Multiplicative Decrease은 time out이 발생하였을 때 TCP는 Multiplicative Decrease 상태로 진입하고 ssthresh값을 cwnd의 반으로 두고 cwnd는 다시 1로 세팅한다.

그림 1) Slow Start, Congestion Avoidance. Ssthresh가 16이 될 때까지 지수적으로 증가(SS), 그 후 ssthresh를 넘어서는 선형증가(AI), Time-out이 걸리게 되면 MD상태로 진입하고 ssthres는 cwnd의 반이 되고 다시 SS상태로 진입. 만일 3-ACKs(dup ACKs)가 되면 loss로 간주하고 MD상태로 진입

1.3.     Fast Retransmit

기존 TCP에서는 timeout을 segment loss로 간주하였고, 그 밖에도 Receiver 측이 발생시키는 duplicate ACK를 Sender측이 수신하는 경우에도 loss로 간주하는 방식이 있다. Duplicate ACK는 예를 들어 여러 개의 segment가 전송되었을 때 수신된 Segment의 순서가 틀렸을 경우 Receiver가 미처 못 받은 Segment를 계속해서 요청하는 것이다. 그렇지만 이 Segment가 실제로 손실되었는지 아니면 단순히 Segment 사이의 시간차에 의해 발생되는 dup ACK인지 판단할 방법이 없어 보통 dup ACK를 loss로 간주하는 경우에도 1~2개의 dup ACK는 인정한다.

                  TCP Tahoe는 Receiver측으로부터 적은 수(보통 n=3)의 duplicate acknowledgment (dup ACKs)가 오더라도 Sender는 loss가 일어난 것으로 간주하고, retransmission timer가 파기되기를 기다리지 않고 해당 패킷을 바로 재전송한다.

1.4.     Fast Recovery

Fast recovery 가 구현되기 전의 TCP에서는 duplicate Ack에 의해 fast retransmit한 이후 새로운 segment를 전송하기 위해서는 다시 slow start를 실행하도록 되어 있었다. 그러나, duplicate Ack가 발생한다는 사실은 곧 손실된 segment이외의 다른 segment들은 문제없이 전송되었다는 것을 의미한다. 따라서 새로 slow start를 통해서 설정된 연결의 안정한 상태에 도달할 필요 없이 fast retransmit한 이후 바로 congestion avoidance 상태에서 전송할 수 있도록 하자는 것이 fast recovery이다. Fast recovery는 특히 Bandwidth-Delay product 값이 큰 경우에 효율적이다.

                  TCP Reno는 TCP Tahoe의 Fast Recovery에서 Fast Recovery를 추가하였다. TCP Tahoe에서 dup ACKs를 loss 의 기준으로 보는 것과 달리, 이 기법은 dup ACKs를 가용될 수 있는 채널이 남아있는 것으로 간주하고, cwnd 변수를 실제로 이 기간 동안 증가시킨다. 그후 dup ACKS된 segment에 대해 ACK가 발생하면 cwnd값을 1/2로 줄이고 Congestion Avoidance 단계로 진입한다. 반면, TCP Tahoe에서는 cwnd는 1로 세팅되고, slow start phase로 진입하였다.

그림 2) Fast Retransmit and Fast Recovery

1.5.     TCP Tahoe

위의 Slow Start. Congestion Avoidance. Fast Retransmit. 세 가지의 알고리즘을 사용한다. TCP Tahoe는 Receiver측으로부터 threshold 이상의 dup ACKs가 오면 Sender는 loss가 일어난 것으로 간주하고, 해당 패킷을 바로 재전송(Fast Retransmission)한다.

1.6.     TCP Reno

TCP Tahoe에서와 같이 Slow Start. Congestion Avoidance. Fast Retransmit을 사용하고 추가적으로Fast Recovery 알고리즘을 사용한다. TCP Reno에서는 처음 connection이 이루어질 때 혹은 dup ACKs에 의해 loss 가 발견될 때가 아니면 Slow start 단계에 잘 들어서질 않는다. 따라서 단 하나의 segment loss가 일어났을 때 효과적이며, 다중 loss 발생 시에는 부적합하다. 다중 loss 발생시 TCP Reno는 time out을 기다리고, 재전송하며, Slow start 단계로 진입한다.

                  dup ACKS된 segment에 대해 ACK가 발생하면 cwnd값을 1/2로 줄이고 Congestion Avoidance 단계로 진입한다. 반면, TCP Tahoe에서는 cwnd는 1로 세팅되고, slow start phase로 진입하였다.

1.7.     TCP New-Reno

TCP New-Reno에서는 multiple loss가 partial ACK가 오면 Fast Recovery를 하지 않기 때문에 발생한다고 가정하고, partial ACK가 와도 Fast recovery에서 빠져나가지 않는다. TCP New-Reno에서는 dup ACKs가 왔을 때, 재전송 timeout이 일어났을 때, Full ACK가 왔을 때 이 세가지 경우에만 Fast Recovery를 시작한다.

1.8.     TCP SACK

Multiple loss에 적합한 TCP New-Reno 이외의 또 하나의 TCP로써 TCP SACK(Selevtive Acknowledgment)가 있다. 이 기법은 Receiver가 TCP SACK block을 통해 Sender측에 성공적으로 전송된 segment 정보를 알려주는 것이다. Sender는 TCP SACK block을 통해 알아낸 정보를 토대로, Retransmission timeout을 기다리지 않고 손실된 Segment를 전송한다.

1.9.     TCP Vegas

실제 throughput과 예상되는 throughput의 차이를 계산하여 Congestion을 제어한다. Cwnd를 이용하지 않고 RTT값을 매번 계산하여 사용한다. 현재 throughput과 예상되는 throughput(Expected = WindowSize / BaseRTT) 의 차이가 2를 넘지 않으면 cwnd를 증가, 4를 넘으면 cwnd를 감소한다. loss를 일으키지 않고 애초에 Slow Start를 수정하였고, 1-dupACK가 오면 바로 재전송한다.

2.        Read [paper-1] and describe the following questions.

2.1.     Describe the objective of the simulation.

TCP Tahoe, TCP Reno, TCP New-Reno 와 TCP SACK을 시뮬레이션을 통해 비교분석하고, SACK을 추가하였을 때 생기는 이점에 관해 알아본다. TCP Reno의 문제점(multiple loss)를 해결하는데 SACK(Selective Acknowledgment)이 어떤 역할을 하는지 탐색한다.

                  SACK 정보 없는 TCP는 data lost로부터 복구하는 다음의 방법을 사용한다. 1) RTT마다 가장 빈번하게 drop 되는 패킷의 재전송, 2) 방금 성공적으로 전송했던 패킷의 재전송. Reno와 New-Reno는 첫번째 방법을, Tahoe는 두번째 방법을 사용한다. SACK은 Reno congestion control알고리즘에 Selective acknowledgment와 selective retransmission을 덧붙인 것으로 위 정보를 이용하면 불필요한 delay나 재전송을 막을 수 있고 throughput을 높일 수 있다.

2.2.     Describe the simulation scenario.

TCP Tahoe, Reno, New Reno, SACK에 대해 각각 1~4개의 packet drop이 발생하였을 때를 시뮬레이션 한다. 그 후 각각의 시나리오 (1~4 packet dtop)에 대해 각 TCP version에 대한 성능을 측정하고, 이를 비교분석 한다.

그림 3) 동그라미는 finite-buffer droptail gateway(RED로 세팅), 네모는 Sending 혹은 Receiving station. 실선은 bandwidth capacity와 delay를 표현하고, 각각의 시나리오는 S1-K1으로의 connection 3개로 이루어진다. (sack.tcl 파일[MF95]에 NS setting을 위한 tcl 설정이 되어있음)

1-way Traffic을 가정하고 ACK의 생략 및 손실은 가정하지 않는다. 그래프는 R1에서의 packet trace (incoming/outcoming)의 개수로 생성되고, x축은 time, y축은 packet number(mod 100)으로 표현한다. drop되지는 않았지만 delay 되는 packet은 본 직선과 동일선상에 직선으로 표시하고, packet drop은 x 로 표시한다. 점선(네모)은 해당 패킷이 congested gateway를 빠져나갔는지를 보여준다.

2.3.     Describe Fig. 2, 3, 4, and 5.

2.3.1    Figure 2. Simulations with one dropped packet

1) TCP Tahoe - 0~13번 패킷까지는 Tahoe의 기본 알고리즘인 Slow Start를 통해 cwnd가 지수적으로 증가하고 있다. Intermediate node, 라우터의 queue가 꽉 차서 14번 패킷이 drop이 일어나고(그 이전의 7개의 패킷에 대해서는 ACKs가 발생했다-조그만 점선참조), 7개의 ACK를 받았으므로 Window를 8-15로 sliding한다. 그 후 다음 14개의 패킷인 15-28 패킷을 보낸다. 13개의 ACK를 받게 되면 Receiver는 14번 패킷에 대해 dupACK를 보내게 되고 Fast Retransmission 알고리즘이 작동한다. 그 후 TCP Tahoe는 ssthresh와 cwnd를 조절하여 다시 Slow Start로 상태로 진입한다.

2) TCP Reno – TCP Tahoe와는 다르게 14번 패킷 dtop에 대해, dupACK 발생 시 Fast Recovery (cwnd=1/2cwnd, Congestion Avoidance 단계로 진입) 알고리즘을 사용한다. TCP Reno 경우 TCP Tahoe와 대처는 같고, 그 후 진입단계가 다르기 때문에 Tahoe와 drop이 일어나기 직전 까지 같은 결과를 보인다.

3) TCP New-Reno – 1-packet drop의 경우에는 TCP Reno와 다르지 않다.

4) TCP SACK - 1-packet drop의 경우에는 TCP Reno와 다르지 않다.

2.3.2    Figure 3. Simulations with two dropped packets

TCP Tahoe – 1 packet drop이 일어났을 때와 같은 방식으로 13 dupACK를 처리한다.

TCP Reno – 2 packet drop에 걸쳐 모두 Fast Retransmit 과 TCP Recovery를 사용하여 cwnd 값을 1/2씩 만든다. 14번 패킷이 drop 되었을 때의 행동은 1 packet drop의 Reno와 같고, 다만 28번 패킷이 drop 되었을 때는 27번에 대한 dupACK를 유발시켜 14번 패킷을 재전송한다.

TCP New-Reno – 27번 패킷에 대한 ACK가 올때까지는 Reno의 행동과 같으나, 그 후 partial ACK에 대해서 New-Reno는 28번 패킷을 바로 보내고 Fast Recovery를 유지한다.

TCP SACK – TCP Reno와 비슷하나 27번 패킷에 대한 partial ACK에 대한 처리방법이 다르다.

2.3.3    Figure 4. Simulations with three dropped packets

TCP Tahoe – 14번 packet drop은 예전과 같고, 37번 패킷까지 Slow Start로 Recovery를 시도하다가 Congestion Avoidance단계로 진입한다.

TCP Reno - 3개의 packet drop이 발생하면 TCP Reno는 Retransmission Timeout을 기다리게 된다. 14번 패킷을 보낸 뒤 12개의 dup ACKs로 인해 TCP Reno Sender는 29-32번 패킷을 보낸다.

TCP New-Reno – 25번 패킷에 대한 첫 ACK이 올 때까지 Reno와 동작방식이 같다. ACK가 온 뒤 26번 패킷을 재전송하고, cwnd를 7로 조정한다. 25번에 대한 dupACKs 발생시, cwnd는 11로 증가한다. 27번에 대한 partial ACK가 발생하고, 이는 28번 재전송 및 cwnd를 7로 재조정한다. 36번에 대한 ACK로 인해 Fast Recovery로부터 빠져나오고 cwnd는 7로 돌아간다.

TCP SACK – 12번째 dupACK가 올 때까지 TCP Reno의 동작방식과 비슷하며, 그 후에는 SACK 정보를 통하여 각각의 패킷 (i.e. 26번 패킷)의 drop을 알린다.

2.3.4    Figure 5. Simulations with four dropped packets

TCP Tahoe - 14번 packet drop은 예전과 같고, 14번 패킷을 재전송한 후에는 11 dup ACKs를 받는다. 그 후 Sender는 23번 패킷에 대한 ACK를 받게 된다.

TCP Reno – Sender는 거의 강제적으로 Retransmit Timeout을 기다린다. Timer가 expires 되면 Sender는 26번 패킷을 재전송하고 27번 패킷에 대한 ACK를 받은 후 28번, 29번 패킷을 전송한다. Timer expiration 그 후에는, Reno는 Tahoe랑 비슷한 방식으로 동작한다.

TCP New-Reno – 23번 패킷에 대한 ACK 전까진 3-packet drop의 Reno와 같다. 이 패킷에 대한 ACK를 받게 되면, Sender는 24번패킷을 재전송하고 Congestion Window를 7로 만든다. 34번 패킷에 대한 ACK는 Fast Recovery에서 New-Reno가 빠져나오게끔 한다.

TCP SACK – 13번째 패킷에 대한 dupACK이 오기 전까지는 4-packet drop의 Reno와 비슷하다. Pipe 변수에 대한 제어는 3-packet drop의 SACK과 비슷하다. 23번 패킷에 대한 dup ACK는 SACK information으로부터 얻을 수 있으며, 31번에 대한 ACK를 받게 되면 Fast Recovery로부터 빠져 나와 Congestion Avoidance단계로 진입한다.

2.4.     What’s the difference between Tahoe, Reno, NewReno, and SACK?

TCP Tahoe의 경우 4가지 시나리오에서 모두 비슷한 결과를 보였다. 그 이유는 Fast Retransmit 직후 Slow Start 상태로 진입하기 때문이다. Reno (without SACK)는 2개 이상의 packet loss가 발생할 경우 Reno sender는 multiple loss를 발생시키고 Retransmission Timer의 회복을 기다린다. New-Reno와 SACK은 모든 4가지 시나리오의 경우에 Retransmission Timer를 기다리지 않고 모두 정상적으로 회복했다. Reno (그리고 Tahoe)의 multiple loss의 문제점을 해결한 면에서 New-Reno와 SACK은 비슷해 보이지만, congestion 및 packet drop의 개수가 많아지면 drop된 packet이 delay를 유발시키며, Sender의 버퍼를 잠식해 가용한 bandwidth를 사용하지 못한다.

3.        Read [paper-2] and describe what the strengths of TCP Vegas are.

TCP Vegas는 대역폭이 허용하는 전달 데이터 양을 초과하는 데이터 양(extra data)을 측정하고 조정한다. TCP Vegas의 목적은 네트워크상에서 데이터 양을 적정수준으로 유지하는 것이다. 확실히 발신지가 데이터를 너무 많이 전달하면 지연시간이 늘어나게 되고 혼잡상태로 될 가능성이 커진다. 또한 너무 적은 여분의 데이터를 전달하면 가용 네트워크 대역폭의 순간적인 증가에 빠르게 반응하지 못할 수 있다.

                  이 논문에서는 TCP Vegas가 throughput을 높이고, loss를 줄이기 위해 사용한 3가지 technical 한 알고리즘을 소개한다.

3.1.     New Retransmission Mechanism

RTT 상에서 2-3개 이상의 drop된 segment이 성능평가(loss)에 중요한 영향을 끼친다. TCP Reno는 timeout이 일어나거나(이 경우 대부분 정확하지 않다), 3개 이상의 dupACKs이 온 경우 재전송을 시도한다. Packet 2번이 도착하고, Packet 3번이 drop된 경우, Packet 4번과 Packet 5번의 도착은 무시 당하고 계속해서 dupACK를 발생시킨다.

                  TCP Vegas는 Reno의 재전송 매커니즘을 다음과 같이 확대한다. Segment가 보내질 때마다, ACK가 도착할 때마다 System clock을 읽고 기록한다. ACK가 도착하면 이러한 timestamp를 이용하여 RTT를 계산한다. Timestamp를 통해 dupACK가 왔을 때도 timeout의 여부를 확인할 수 있다. 이를 통해 3번의 dupACK를 기다리지 않고 바로 재전송이 가능하다. dupACK가 아닌 ACK가 올 경우, time stamp를 통해 segment를 재전송할 수 있다.

                  즉, TCP Vegas는 ACK를 timeout의 여부를 확인하는 도구로 사용하며, time stamp를 이용한다. 또한 Vegas는 Congestion Window를 segment가 최근의 decrease 직후 재전송된 경우에만 감소시킨다.

3.2.     Congestion Avoidance Mechanism

Congestion Control로 Loss가 100% 예방되는 것은 아니다. 이에 TCP-Vages는 Congestion Detection을 수행하는데, 이는 현재 네트워크의 가용상태(channel capacity)를 통해 설정한다. Jain의 CARD(Congestion Avoidance using Round-trip Delay)는 이에 상응하는 연구결과를 보여준다. 또한 Wang and Crowcroft의 Tri-S scheme은 RTT를 통해 sending rate의 평균을 계산하는데, Vegas는 Tri-S의 접근방법과 비슷하다. Slow Start동안에는 비록 의미 없지만 Vages는 실제 throughput과 예상되는 throughput의 차이를 다음과 같이 계산하여 Congestion을 제어한다.

                 

네트워크가 혼잡하지 않을 때의 RTT를 BaseRTT로 놓고 (minimum), Windowsize는 현재 Congestion Window의 사이즈이다. 그 후 실제 Actual Sending rate를 구한 후 이를 다음과 같은 Diff로 계산한다.

                 

이 Diff가 상한값 를 넘지 않는다면 Congestion Window를 linear하게 증가시키고, 하한값 를 넘는다면 Congestion Window를 감소시킨다. 하한값과 상한값 사이에 있으면 아무 Action도 취하지 않는다. 상한값과 하한값은 앞서 언급했던 “대역폭이 허용하는 전달 데이터 양을 초과하는 데이터 양(Extra Data)”으로부터 정한다.

그림 4) (a) The Small Vertical Line – Vegas가 Congestion Control Decision 할 때 (Actual RTT 계산). (b) The gray line – Expected throughput (c) The solid line – Actual Sending rate (d) The dashed line - threshold

3.3.     Modified Slow-Start Mechanism

Reno의 Slow Start 기법은 Sender측의 버퍼가 매우 작거나 할 경우에는 loss를 처리함에 있어 매우 비용이 크다. 종전에는 connection bandwidth를 넘어서고 loss에 더욱 민감할 수 밖에 없다. 이러한 Reno의 loss와 같은 상황을 피하기 위해, Slow Start 동안에도 Congestion을 Detect하고 avoid할 수 있는 매커니즘을 추가하여 Slow Start를 약간 수정하였다.

                  Vegas는 RTT를 계산하여 Congestion Window를 결정하는데, 어떠한 Actual rate이 expected rate 보다  threshold 값만큼 적으면 Slow start mode 대신에 linear increase/decrease 단계로 진입한다. 다음은 실제 인터넷에서의 TCP Vegas의 성능 테스트결과를 Reno와 비교하여 둔 것이다.

3.4.     Results and Discussion

그림 5) 실제 인터넷 트래픽 테스트. 17-hops으로 이루어진 NIH, UA 트래픽 소스

추가적으로 SACK은 불피요한 재전송 패킷을 줄이고자 하는 다른 제안 방법으로, SACK information과 함께 Reno보다 뛰어난 재전송 메커니즘을 보인다. Vegas와 비교해 봤을 때, Congestion 혹은 Slow-start mechanism에 별다른 영향을 끼치지 못했다. 또한 SACK 정보는 불필요한 재전송을 줄이기에는 불충분하고, SACK은 단기간내에 추가적인 loss를 발생시킬 (delay-bandwidth product가 큰 네트워크의 경우) 확률이 높다.

4.        Reference

[1]      Kevin Fall and Sally Floyd, “Simulation-based Comparisons of Tahoe, Reno, and SACK TCP”, SIGCOMM ’96.

[2]      Lawrence S.Brakmo, Sean W.O'Malley and Larry L.Peterson, “TCP Vegas: New Techniques for Congestion Detection and Avoidance”, SIGCOMM ’94.

[3]      Mahbub Hassan and Raj Rain, “High Performance TCP/IP Networking – Concepts, Issues, and Solutions”, Prentice Hall, 2004.

[4]      Bumjun Kim, TCP Congestion Control Mechanism, available at http://www.netmanias.com/contents/whitepaper/20000920-bjkim-tcp1/tcp.htm