Congestion
혼잡이라는 것은 데이터의 양이 너무 많아 감당할 수 없는 상태를 말한다.
혼잡이 발생하면 전송한 패킷이 queueing 됨에 따라 긴 지연 시간이 발생하거나, 라우터 버퍼가 꽉 차게 되어 overflow가 발생하고 packet loss가 발생할 수 있다.
flow control와의 차이점
flow control은 수신자의 상태(버퍼)를 확인하고 송신자가 패킷을 보내는 속도를 조절하여 수신자와의 데이터 처리 속도를 맞추는 것이다.
congestion control은 송신자의 데이터 전달과 네트워크의 데이터 처리 속도 차이를 해결하는 것이다.
Causes/costs of congestion : scenario 1
첫 번째 상황은 다음과 같은 가정이 있다.
- 두 개의 송신자, 두 개의 수신자
- 하나의 라우터는 무제한의 버퍼를 가지고 있음
- 라우터의 link capacity는 R
- 데이터 전송 속도는 λ
- 재전송하지 않음
-> 두 개의 송신자가 하나의 link를 공유하기 때문에 각자 최대 R/2까지 이용할 수 있다.
-> 지연의 queuing이 계속 발생하기 때문에 무한으로 증가함
Causes/costs of congestion : scenario 2
- 두 개의 송신자, 두 개의 수신자
- 하나의 라우터의 버퍼 크기는 유한
- 송신자는 timeout 되었거나 소실된 패킷에 대해서 재전송
- 응용 계층에서는 시스템이 stable하기 위해 입력 속도와 전송 속도가 같아야 함
- TCP에서는 재전송 하기 때문에 λ'in >= λin
재전송 되는 패킷이 존재하기 때문에 λ'in이 R/2 일 때 λout은 R/2보다는 낮은 값이 된다.
여기서 premature timeout이 발생하여 불필요하게 재전송되는 패킷도 추가될 경우, λout은 더 낮게 형성된다.
Causes/costs of congestion : scenario 3
- 4명의 송수신자
- 여러 개의 경로 및 라우터
- timeout 및 재전송이 발생
만약에 빨간 경로의 λ이 증가하면, 위쪽 라우터의 버퍼 중 빨간 경로의 패킷이 차지하는 비중이 늘어나게 되고 파란 경로의 throughput이 감소하게 된다.
λ이 계속해서 증가하게되면 빨간색 패킷과 파란색 패킷이 지나는 라우터의 버퍼는 유한하기 때문에 통과하는 파란색의 패킷은 점점 줄어들고 Host B에서 파란색의 throughput에서 점점 더 loss가 발생한다.
그래서 c/2 시점 이후로는 0으로 수렴하게 된다.
결론
- throuput은 capacity를 절대 넘을 수 없음
- capacity가 증가할수록 delay는 큰 폭으로 증가
- 손실 및 재전송은 효율적인 throughput을 저해
- 불필요한 중복 전송은 효율적인 throughput을 더 크게 저해
Congestion control
AIMD
maximum segment size(window size)를 점진적으로 증가시키다가 congestion이 발생하면 window size를 절반으로 줄인다.
Additive Increase, Multiplicative Decrease라고 한다.
window size를 cwnd(congestion window)라고도 한다.
sending rate가 증가할 때는 선형적으로 증가하다가, 일정 수준을 만났을 때 그 절반으로 떨어지는 것을 볼 수 있다.
cwnd를 줄일 때 프로토콜 표준에 따라 구현 방식이 조금씩 다르다.
- TCP Reno -> triple duplicate ACK 감지되면 절반으로 줄임
- TCP Tahoe -> timeout이 발생하면 cwnd를 1로 줄임
TCP slow start
AIMD는 감소할 때는 큰 폭으로 감소하는데 증가할 떄는 느리게 증가되므로 성능의 복원이 오래 걸린다.
이러한 부분을 개선한 것이 slow start이다.
slow start는 시작 cwnd를 1로 설정하고, 매 RTT마다 cwnd를 2배씩, 지수적으로 증가시킨다.
처음에는 느릴 수 있지만 지수적으로 성능이 향상될 수 있다.
congestion avoidance
slow satrt에 의해 지수적으로 증가하면, 너무 빠르게 증가되기 때문에 얼마 지나지도 못한채 다시 congestion이 발생한다.
우리는 임계치라는 기준을 도입하고 AIMD와 slow start 방식을 적절히 섞어서 어느 정도 임계 지점까지는 slow start 방식, 임계 지점 이후부터는 AIMD처럼 선형적으로 증가시킬 수 있다.
(임계치는 slow start threshold -> ssthresh)
congestion을 만났을 때는 TCP Reno인지 TCP Tahoe인지에 따라 cwnd가 절반 또는 1로 줄어들 것이다.
sstresh는 congestion을 만나면 cwnd의 절반으로 재설정된다.
TCP CUBIC
AIMD와 비슷한 매커니즘을 가지고 있지만, 점진적으로 증가하는 겅시 아니라 위로 볼록한 곡선형으로 증가시킨다.
파란 선이 CUBIC 방식인데, congestion 발생 직후에 빠르게 성능을 올릴 수 있고, congestion이 발생한 부분 인근에서는 linear하게 증가는 것보다 느리게 증가하여 높은 rate를 오래 유지할 수 있다. 따라서 전반적인 성능이 향상된다.
Delay-based congestion control
수신자의 ACK가 아닌 RTT를 기반으로 congestion을 탐지하거나 제어한다.
먼저 congestion이 발생기 전의 RTT를 구한다. 그러니까 아무런 문제가 없는 순수한 RTT를 구하고나서, 매번 RTT를 구한 후 이 값과 비교한다.
만약에 최근에 측정한 RTT가 원래 RTT와 비슷하면 congestion이 발생하지 않는다고 판단하고, cwnd를 linear하게 증가시키고, 만약 이상적인 RTT값보다 현저히 낮다면 congestion이 발생했다고 간주하고 cwnd를 감소시킨다.
Explicit Congestion Notification(ECN)
네트워크 라우터의 도움을 받아서 혼잡이 발생했다는 것을 표현하는 것이다.
IP 헤더에는 ECN bit marking이라는 필드가 있다.
이 필드가 10 또는 01로 설정되어 있으면 ECN 기능을 지원한다 라는 뜻이다.
그리고 전송을 하는데 네트워크 라우터가 혼잡을 감지하면 이 필드를 11로 수정해서 수신자에게 보낸다.
그러면 수신자는 congestion을 감지하고 TCP 헤더의 E 필드를 1로 만들어서 지금 혼잡이 발생하고 있으니 데이터 양을 줄여서 보내라라는 듯으로 송신자에게 보낸다.
송신자는 TCP 헤더의 E 값을 보고 congestion이 일어남을 인지하고 데이터의 양을 줄이고 이를 알려주는 용도로 C 필드를 1로 설정하여 보낸다.
TCP fairness
K개의 TCP 세션이 R의 대욕폭을 가지고 있을 때, K/R 만큼 대역폭을 공평하게 나누어 가지는 것이다.
만약에 어떤 connection이 K/R보다 더 많은 자원을 사용하고 있으면 congestion control 과정에서 이를 공평하게 재분배할 수 있다.
만약 한 회선을 connection 1, 2가 양분하여 사용하고 있다고 가정하면 검은 점선은 두 connection이 서로 같은 양만큼을 배분받고 있을 때를 나타낸다. 그리고 파란선은 대역폭 R을 나타내며 이 곳보다 위에 존재하는 경우 congestion이 발생한다.
빨간색 점의 위치가 점선보다 오른쪽에 있으면 connection 1이 2보다 더 많은 throughput을 차지하고 있다는 뜻이다.
이 상태가 유지되며 두 connection이 각자의 cwnd를 증가시키다가 파란 선을 넘어 congestion이 발생하게 되면, 두 connection 모두 cwnd를 절반으로 줄인다.
이 과정을 반복하다 보면 검은 점선, 즉 서로 동등하게 대역폭을 나누어 가지는 상태에 수렴하게 된다.
