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은 수신측의 goodput을 의미한다. Goodput은 단위 시간 당 수신측의 application에 의해서 실제로 처리된 payload의 양을 의미한다. 이는 재전송된 패킷이나, 헤더, 폐기된 패킷까지 포함하여 측정하는 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)에 해당한다.

이때 다음과 같은 세 가지 상황을 추가로 고려할 수 있다. 첫 번째 상황(perfect knowledge)은 A가 라우터의 버퍼의 상태에 대해 "마법처럼" 알고있어서 버퍼가 비어 있을 때에만 데이터를 전송할 수 있다고 가정해보자. 이 경우, 재전송이 존재하지 않으므로 $\lambda$in = $\lambda$'in = $\lambda$out와 같은 수식이 성립한다. 그럼에도 그래프와 같이 $\lambda$_out의 값은 R/2를 넘을 수 없다.

두 번째 상황(known loss)은 송신자가 패킷 손실 여부에 대해 정확히 알고 있어서 손실된 경우에만 재전송을 하는 경우이다. 이때 버퍼가 가득 차면 패킷이 버려지고, 이에 대한 패킷만 재전송하므로 duplicate 패킷은 존재하지 않는다. 그럼에도 $\lambda$in < $\lambda$'in와 같은 수식이 성립한다. 또한 이를 바탕으로 그래프를 보면, 초기에는 $\lambda$_in에 따라 $\lambda$_out이 선형적으로 증가한다. 하지만 $\lambda$_in이 증가함에 따라 패킷 손실이 잦아지고, 이에 따라 효율이 저하된다. 결국 $\lambda$_out은 R/2에 수렴하지만 그 증가폭은 점점 작아진다. 즉 congestion의 또 다른 비용은 재전송에 네트워크의 자원을 낭비하고, 이에 따라 goodput에 제약이 생긴다는 것이다.

세 번째 상황(duplicates)는 더욱 현실적으로 premature timeout과 같은 상황이 발생하여 수신자에 중복(duplicate) 패킷이 도착하는 경우이다. 이때 동일한 패킷이 여러번 수신되므로 수신자는 하나만 사용하고 나머지는 폐기한다. 이 때문에 두 번째 상황보다 더 goodput이 감소하며, 라우터는 불필요한 중복 패킷을 추가로 전송하므로 link capacity가 낭비된다.

Scenario 3: Four Senders, Routers with Finite Buffers, and Multihop Paths

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

• 4개의 호스트(A, B, C, D)와 2개의 라우터가 존재하며, A와 C, B와 D는 두 개의 라우터를 사이에 두고 연결되어 있다.
• 각각의 호스트는 $\lambda$_in의 속도로 전송되며, link capacity는 R이다.
• 라우터의 버퍼의 크기가 유한하여 버퍼가 꽉 차면 패킷을 버린다.(packet drop)
• Rdt 서비스를 구현하기 위해 손실된 세그먼트는 재전송 한다.

이때 $\lambda$_in이 작다면 버퍼의 overflow는 거의 존재하지 않으며, $\lambda$in \approx $\lambda$'in \approx $\lambda$out가 성립한다. 즉 $\lambda$_in이 증가함에 따라 $\lambda$_out도 사실상 비례적으로 증가한다. 하지만 $\lambda$'_in이 어떤 임계점을 넘어버리면, figure과 같이 $\lambda$_out이 극단적으로 감소한다. 또한, 만약 빨간색 경로(Host A → Host C)의 트래픽이 점점 증가하면, 버퍼를 빨간색 패킷이 가득 채움에 따라 공유 라우터에서 파란색 패킷이 드롭되기 시작한다. 즉, 큐 선점 효과(queue buildup) 때문에 파란색 경로의 throughput은 0에 수렴하게되는 불공정한 상황(unfairness)이 나타난다.