Principles of congestion control

상위 문서: Transport Layer

개요

TCP가 reliable data transfer를 위해 사용하는 여러 메커니즘들은 network congetion등으로 인해 패킷이 손실되거나 손상되었을 경우, 이에 대처하는 방법이다. 하지만 이러한 메커니즘은 network congestion 자체를 해결하지 못한다는 한계를 가지고 있다. Network congestion의 원인을 해결하기 위해서는 congestion이 발생하였을 때 송신자의 전송 속도(transmission rate)를 제어하는 메커니즘이 필요하며, 이를 congestion control이라고 한다. 이때 목적은 송신측의 전송 속도가 지나치게 커지지 않도록 하여 네트워크에 가해지는 부하를 적정 수준으로 조정하기 위함이므로 receive buffer의 overflow를 막기 위한 목적으로 사용되는 flow control과는 구분된다.

Causes/costs of congestion

Congestion control에 대해 이해하기 위해서는 먼저 congestion이 왜 일어나는지, 그리고 어떤 피해가 발생하는지에 대해서 이해할 필요가 있다. 해당 문단에서는 호스트들이 그들의 전송 속도를 높임에 따라 네트워크가 어떻게 혼잡해지는지 관찰하기 위해서 세가지의 시나리오를 참고한다.

Scenario 1: Two Senders, a Router with Infinite Buffers

해당 시나리오는 figure 1과 같은 상황이다.

• 두 송신자 A, B와 두 수신자가 존재한다.
• 송신자와 수신자 간의 재전송은 존재하지 않는다.
• 각 호스트는 버퍼의 크기가 무한대인 하나의 라우터로 연결되어 있다.
• output link의 capacity(transmission rate)는 R이다.

위와 같은 상황에서 호스트 A와 B의 application layer는 데이터를 $\lambda$_in의 속도로 link에 보낸다. 이때 $\lambda$_in는 오리지널 데이터(payload)의 평균 전송률을 의미한다. 즉, $\lambda$_in byte/sec는 A와 B가 각각 라우터에 제공하는 트래픽의 양을 의미한다. 또한 $\lambda$_out은 수신측의 throughput을 의미한다.
이와 같은 상황에서 figure 2, 3은 A의 전송률에 따른 수신측의 throughput과 delay의 크기를 보여준다. 먼저 figure 2는 $\lambda$_in가 0 ~ R/2 사이일 때는 $\lambda$_out이 송신률과 같은 것을 보여준다. 하지만 송신률이 R/2 이상이 되면 수신측의 $\lambda$_out은 R/2로 고정되는데, 이는 link capacity R을 두 연결이 나눠쓰기 때문이다. 어쨌든, Throughput의 관점에서는 송신률을 높인다고 해서 나쁠 것은 없다. 하지만 figure 3은 $\lambda$_in가 R/2에 근접할 수록 delay가 기하급수적으로 커지며, R/2를 초과할 경우에는 버퍼에 쌓이는 패킷의 수가 무한정 늘어나므로 평균적인 delay도 무한대가 되는 것을 볼 수 있다. 즉, $\lambda$_in가 커짐에 따라 $\lambda$_out도 커지지만, delay의 관점에서는 별로 좋은 상황이 아니다. 즉 congestion의 비용 중 하나는 delay의 증가이다.

Scenario 2: Two Senders and a Router with Finite Buffers

해당 시나리오는 시나리오 1을 더욱 현실화한 버전이며, 아래와 같은 변화가 생긴다.

• 라우터의 버퍼의 크기가 유한하여 버퍼가 꽉 차면 패킷을 버린다.(packet drop)
• Rdt 서비스를 구현하기 위해 손실된 세그먼트는 재전송 한다.

이와 같은 상황에서는 figure 1에 나타난 $\lambda$_in과 $\lambda$'_in을 구분할 필요가 있다. $\lambda$_in가 application layer의 payload의 평균 전송률인 반면, $\lambda$'_in는 $\lambda$_in에 실재로 transport layer에서 발생한 재전송까지 포함한 전체 segment의 평균 전송률에 해당한다. 즉, $\lambda$'_in는 실제로 네트워크에 해당 연결로 인해 가해지는 부하(offered load)에 해당한다.

이때 다음과 같은 세 가지 상황을 추가로 고려할 수 있다. 첫 번째 상황은 A가 라우터의 버퍼의 상태에 대해 "마법처럼" 알고있어서 버퍼가 비어 있을 때에만 데이터를 전송할 수 있다고 가정해보자.(perfect knowledge) 이 경우, 재전송이 존재하지 않으므로 다음과 같은 수식이 성립한다:

$\lambda$in = $\lambda$'in = $\lambda$out (하지만 throughput은 R/2 이상 될 수 없다.)

두 번째 상황은 송신자가 패킷 손실 여부에 대해 정확히 알고 있어서 손실된 경우에만 재전송을 하는 경우이다.(known loss) 이때 버퍼가 가득 차면 패킷이 버려지고, 이에 대한 패킷만 재전송하므로 duplicate 패킷은 존재하지 않는다. 그럼에도 $\lambda$in < $\lambda$'in와 같은 수식이 성립한다.