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===
[[파일:Causes-costs of congestion- scenario 1 .png|대체글=Figure 1. Congestion: scenario 1|섬네일|Figure 1.  Congestion: scenario 1 ]]
[[파일:Congestion- scenario 1 Graph.png|대체글=Figure 2. Congestion: scenario 1 Graph|섬네일|Figure 2. Congestion: scenario 1 Graph]]
해당 시나리오는 figure 1과 같은 상황이다.
* 두 송신자 A, B와 두 수신자가 존재한다.
* 송신자와 수신자 간의 재전송은 존재하지 않는다.
* 각 호스트는 버퍼의 크기가 무한대인 하나의 라우터로 연결되어 있다.
*output link의 capacity(transmission rate)는 R이다.
위와 같은 상황에서 호스트 A와 B의 application layer는 데이터를 <math>\lambda</math><sub>in</sub>의 속도로 link에 보낸다. 이때 '''<math>\lambda</math><sub>in</sub>는 오리지널 데이터(payload)의 평균 전송률'''을 의미한다. 즉, <math>\lambda</math><sub>in</sub> byte/sec는 A와 B가 각각 라우터에 제공하는 트래픽의 양을 의미한다. 또한 '''<math>\lambda</math><sub>out</sub>은 수신측의 goodput'''을 의미한다. '''Goodput은 단위 시간 당 수신측의 application에 의해서 실제로 처리된 payload의 양'''을 의미한다. 이는 재전송된 패킷이나, 헤더, 폐기된 패킷까지 포함하여 측정하는 throughput과는 구분되는 개념이다.  

Figure 2는 A의 전송률에 따른 수신측의 throughput과 delay의 크기를 보여준다. 먼저 왼쪽 그래프는 <math>\lambda</math><sub>in</sub>가 0 ~ R/2 사이일 때는 <math>\lambda</math><sub>out</sub>이 송신률과 같은 것을 보여준다. 하지만 송신률이 R/2 이상이 되면 수신측의 <math>\lambda</math><sub>out</sub>은 R/2로 고정되는데, 이는 link capacity R을 두 연결이 나눠쓰기 때문이다. 어쨌든, Throughput의 관점에서는 송신률을 높인다고 해서 나쁠 것은 없다. 하지만 오른쪽 그래프는 <math>\lambda</math><sub>in</sub>가 R/2에 근접할 수록 delay가 기하급수적으로 커지며, R/2를 초과할 경우에는 버퍼에 쌓이는 패킷의 수가 무한정 늘어나므로 평균적인 delay도 무한대가 되는 것을 볼 수 있다. 즉, <math>\lambda</math><sub>in</sub>가 커짐에 따라 <math>\lambda</math><sub>out</sub>도 커지지만, delay의 관점에서는 별로 좋은 상황이 아니다. 즉 '''congestion의 비용 중 하나는 delay의 증가'''이다.

===Scenario 2: Two Senders and a Router with Finite Buffers===
[[파일:Causes-costs of congestion- scenario 2 .png|가운데|섬네일|500x500픽셀|Figure 3. Congestion: Scenario 2]]
[[파일:Causes-costs of congestion- scenario 2 Graph1.png|대체글=Figure 4. Congesiton: Scenario 2-1 graph|섬네일|180x180px|Figure 4. Congesiton: Scenario 2-1 graph]]
해당 시나리오는 시나리오 1을 더욱 현실화한 버전이며, 아래와 같은 변화가 생긴다.
* 라우터의 버퍼의 크기가 유한하여 버퍼가 꽉 차면 패킷을 버린다.(packet drop)
*Rdt 서비스를 구현하기 위해 손실된 세그먼트는 재전송 한다.
이와 같은 상황에서는 figure 1에 나타난 <math>\lambda</math><sub>in</sub>과 <math>\lambda</math>'<sub>in</sub>을 구분할 필요가 있다. <math>\lambda</math><sub>in</sub>가 application layer의 payload의 평균 전송률인 반면, <math>\lambda</math>'<sub>in</sub>는 <math>\lambda</math><sub>in</sub>에 실재로 transport layer에서 발생한 재전송까지 포함한 전체 segment의 평균 전송률에 해당한다. 즉, '''<math>\lambda</math>'<sub>in</sub>는 실제로 네트워크에 해당 연결로 인해 가해지는 부하(offered load)'''에 해당한다.
[[파일:Causes-costs of congestion- scenario 2 Graph2.png|alt=|섬네일|Figure 5. Congesiton: Scenario 2-2 graph]]
이때 다음과 같은 세 가지 상황을 추가로 고려할 수 있다. 첫 번째 상황(perfect knowledge)은 A가 라우터의 버퍼의 상태에 대해 "마법처럼" 알고있어서 버퍼가 비어 있을 때에만 데이터를 전송할 수 있다고 가정해보자. 이 경우, 재전송이 존재하지 않으므로 <code><math>\lambda</math><sub>in</sub> = <math>\lambda</math>'<sub>in</sub> = <math>\lambda</math><sub>out</sub></code>와 같은 수식이 성립한다. 그럼에도 그래프와 같이 <math>\lambda</math><sub>out</sub>의 값은 R/2를 넘을 수 없다.

두 번째 상황(known loss)은 송신자가 패킷 손실 여부에 대해 정확히 알고 있어서 손실된 경우에만 재전송을 하는 경우이다. 이때 버퍼가 가득 차면 패킷이 버려지고, 이에 대한 패킷만 재전송하므로 duplicate 패킷은 존재하지 않는다. 그럼에도 <code><math>\lambda</math><sub>in</sub> < <math>\lambda</math>'<sub>in</sub></code>와 같은 수식이 성립한다. 또한 이를 바탕으로 그래프를 보면, 초기에는 <math>\lambda</math><sub>in</sub>에 따라 <math>\lambda</math><sub>out</sub>이 선형적으로 증가한다. 하지만 <math>\lambda</math><sub>in</sub>이 증가함에 따라 패킷 손실이 잦아지고, 이에 따라 효율이 저하된다. 결국 <math>\lambda</math><sub>out</sub>은 R/2에 수렴하지만 그 증가폭은 점점 작아진다. 즉 '''congestion의 또 다른 비용은 재전송에 네트워크의 자원을 낭비하고, 이에 따라 goodput에 제약이 생긴다는 것'''이다.
[[파일:Causes-costs of congestion- scenario 2 Graph 3.png|alt=|섬네일|Figure 6. Congesiton: Scenario 2-3 graph]]
세 번째 상황(duplicates)는 더욱 현실적으로 premature timeout과 같은 상황이 발생하여 수신자에 중복(duplicate) 패킷이 도착하는 경우이다. 이때 동일한 패킷이 여러번 수신되므로 수신자는 하나만 사용하고 나머지는 폐기한다. 이 때문에 두 번째 상황보다 더 goodput이 감소하며, 라우터는 불필요한 중복 패킷을 추가로 전송하므로 link capacity가 낭비된다.

===Scenario 3: Four Senders, Routers with Finite Buffers, and Multihop Paths===
[[파일:Four senders, routers with finite buffers, and multihop paths.png|대체글=Figure 7. Four senders, routers with finite buffers, and multiple paths|가운데|섬네일|500x500픽셀|Figure 7. Four senders, routers with finite buffers, and multiple paths]]
[[파일:Figure 4. Congesiton- Scenario 3 graph.png|대체글=Figure 8. Congesiton: Scenario 3 graph|섬네일|Figure 8. Congesiton: Scenario 3 graph|200x200픽셀]]
해당 시나리오는 figure 1과 같은 상황이다.
* 4개의 호스트(A, B, C, D)와 2개의 라우터가 존재하며, A와 C, B와 D는 두 개의 라우터를 사이에 두고 연결되어 있다.
* 각각의 호스트는 <math>\lambda</math><sub>in</sub>의 속도로 전송되며, link capacity는 R이다.
* 라우터의 버퍼의 크기가 유한하여 버퍼가 꽉 차면 패킷을 버린다.(packet drop)
*Rdt 서비스를 구현하기 위해 손실된 세그먼트는 재전송 한다.
이때 <math>\lambda</math><sub>in</sub>이 작다면 버퍼의 overflow는 거의 존재하지 않으며, <code><math>\lambda</math><sub>in</sub> <math>\approx</math> <math>\lambda</math>'<sub>in</sub> <math>\approx</math> <math>\lambda</math><sub>out</sub></code>가 성립한다. 즉 <math>\lambda</math><sub>in</sub>이 증가함에 따라 <math>\lambda</math><sub>out</sub>도 사실상 비례적으로 증가한다. 하지만 <math>\lambda</math>'<sub>in</sub>이 어떤 임계점을 넘어버리면, figure과 같이 <math>\lambda</math><sub>out</sub>이 극단적으로 감소한다. 또한, 만약 R1~R2 경로(Host A → Host C)의 트래픽이 점점 증가하면,
버퍼를 호스트 A의 패킷이 가득 채움에 따라 공유 라우터에서 호스트 B에서 전송된 패킷이 드롭되기 시작한다. 즉, 큐 선점 효과(queue buildup) 때문에 R2~R3 경로(Host B → Host D)의 throughput은 0에 수렴하게되는 불공정한 상황(unfairness)이 나타난다.

==[[TCP Congestion Control]]==
자세한 내용은 [[TCP Congestion Control]] 문서를 참조하십시오.

==Explicit Congestion Notification==
TCP는 전통적으로 end-to-end congestion control 방식을 사용했는데, 이는 network layer에서는 TCP 혼잡 제어에 직접 관여하지 않는다는 것을 의미한다. 이 때문에 송신자는 네트워크 상태를 직접적으로 알 수 없고, 오직 패킷 손실이라는 간접적인 신호만 보고 네트워크의 congestion 상태에 대해 추론한다. 하지만 이는 패킷 손실이라는 간접적인 단서로 congestion을 추론하기 때문에 congestion 상황에 대한 대처가 느리며, delay난 queueing과 같은 다른 congestion의 결과 요소는 무시된다는 한계가 있다. 이를 보완하기 나온 게 '''ECN(Explicit Congestion notification)으로 network layer가 직접 congestion 상태를 알려주는 방법이다. 

ECN을 구현하기 위해서는 ToS(Type of Service) 필드에 포함된 ECN 비트를 이용해야 한다. ECN은 2비트로 이루어져, 4가지의 상태를 나타낼 수 있다:

==각주==
[[분류:컴퓨터 네트워크]]