[네트워크] 혼잡 제어

본 내용은 Computer Networking: A Top-down Approach 를 읽고 공부한 내용입니다.

목차
1. 혼잡제어의 원인과 비용
  1) 시나리오1: 두 개의 송신자와 무한 버퍼를 가지는 하나의 라우터
  2) 시나리오2: 두 개의 송신자, 유한 버퍼를 가지는 하나의 라우터
  3) 시나리오 3: 네 개의 송신자와 유한 버퍼를 가지는 라우터, 그리고 멀티홉 경로
2. 혼잡제어에 대한 접근법
  1) 종단간의 혼잡제어
  2) 네트워크 지원 혼잡제어
3. 혼잡제어의 여러 사례
  1) ATM ABR
  2) RM
4. TCP 혼잡제어
  1) TCP의 알고리즘
  2) AIMD
  3) Slow Start
  4) TimeOut
  5) Fast Recovery
5. TCP 공정성

---

1. 혼잡제어의 원인과 비용

1.1 시나리오1: 두 개의 송신자와 무한 버퍼를 가지는 하나의 라우터

그림에서 볼 수 있듯 Host A에서도 한 쪽으로, Host B에서도 한 쪽으로 데이터를 보내고 있다. R/2만큼의 공간을 쓴다고 하면, 아래에 볼 수 있는 그래프처럼 R/2까지 전송함에 따라 처리량도 R/2까지 점차 증가한다. 하지만 링크는 전송량이 R/2를 넘어가면 더이상 R/2를 초과하여 전송할 수 없다. 따라서 R/2에 근접함에 따라 지연률이 극한에 달하게 된다.

1.2 시나리오 2: 두개의 송신자, 유한 버퍼를 가지는 하나의 라우터

다음은 버퍼가 유한하게 존재한다고 생각하자. 
이번에는 known loss가 생길 수 있다. 이런 경우에는 버퍼가 유한하다고 하므로 R/2의 in을 가질 때 R/2만큼에 도달하지는 않을 수 있다. 하지만 계속해서 밀어내면 어느순간 R/2의 out에 근접하는 결과가 나올 수 있다. 
현실에서는 duplicates도 생길 수 있을 것이다. 이럴 때에는 오히려 더 받을 수 있는 데이터들을 duplicates들 때문에 받지 못하는 현상이 생길 수 있어 R/2에 미치지도 못하는 현상을 볼 수 있다.
R/2에 도달할 수 있다면 "goodput"이지만 아닌 경우에는 cost가 생김을 알 수 있다.

1.3 시나리오 3: 네 개의 송신자와 유한 버퍼를 가지는 라우터, 그리고 멀티홉 경로
간단히 말하면 이 경우에서는 Tradeoff가 발생할 수 있다. 즉 Host A에서 마구 보내게 되면, A-C 트래픽과 B-D 트래픽은 버퍼 공간을 한 버퍼에서 경쟁해야 하므로 오히려 Host D에서 congestion 문제가 생길 수 있다.
따라서 성능이 오른쪽 그래프처럼 급격히 낮아짐을 볼 수 있다.

---

2. 혼잡제어에 대한 접근법

 

2.1 종단간의 혼잡제어(end-end congestion control)

네트워크 계층은 혼잡제어 목적을 위해 트랜스포트 계층에게 어떤 직접적인 지원도 제공하지 않는다. 따라서 end system에서 혼잡(패킷 손실 및 지연 등)을 추론한다.
요즘에는 주로 이 방법을 채택한다.

2.2 네트워크 지원 혼잡제어(network-assisted congestion control)
네트워크 계층 구성요소는 네트워크 안에서 혼잡 상태와 관련해 송신자에게 직접적인 피드백을 제공한다. 
ex. ATM ABR 혼잡제어의 한 형태는 라우터 자신이 출력 링크에 제공할 수 있는 전송률을 송신자에게 명확히 알릴 수 있게 해준다.

---

3. 혼잡제어의 여러 사례

3.1 ABR
사용 가능한 대역폭을 검출하고, 이에 따라 트래픽 속도를 동적으로 조절한다. ABR은 라우터와 호스트 간 통신에서 사용되며, 라우터는 혼잡 상황에서 호스트로 전송되는 패킷 수를 제한한다.

3.2 RM
혼잡 제어를 위해 패킷을 일부로 손실시킨다. 라우터는 일정 기준에 따라 패킷을 버림으로써 네트워크의 혼잡을 방지한다. RM은 라우터와 호스트 간의 통신에서 사용된다. 아래와 같은 여러 종류의 bit을 사용한다. 

NI bit : 예비경보
CI bit : 본경보
EFCI bit : 앞으로 congestion이 발생할 것 같을 때

 

---

4. TCP 혼잡제어

TCP가 취한 접근방법은 네트워크 혼잡에 따라 연결에 트래픽을 보내는 전송률을 각 송신자가 제한(congestion window)하도록 하는 것이다. 만약 TCP 송신자가 자신과 목적지 간의 경로에서 혼잡이 없음을 감지하면, 송신자는 송신률을 높인다. 

그럼 올릴 땐 얼마나 / 어느정도 빨리 올릴 건지에 대한 아이디어는 어떻게 도출되었을까?
이 알고리즘은 크게 3가지 구성요소로 이루어진다. 
*참고 : 아래에서 congwd는 congestion window를 의미한다.
1. AIMD(additive-increase, multiplicate-decrease; 아래처럼 증가는 서서히, 그리고 떨어질때는 뚝!)
2. slow start - 연결 초기에 전송되는 데이터 양을 제어하기 위한 메커니즘으로 전송하는 세그먼트 수를 지수적으로 늘려나감
3. time out

TCP는 flow control과는 달리 congestion control에서는 
[LastByteSent-LastByteAcked] <=min(cwnd, rwnd) 이다.  --> flow control에서는 cwnd가 없다.
이 때 TCP sending rate은 대략 cwnd/RTT 정도이다.

4.1 AIMD
위에서 볼 수 있는 그래프가 톱니바퀴 모양인 이유를 알 수 있는 알고리즘이다. 자신의 혼잡 윈도우의 값은 선형으로 증가하다가, 손실 사건이 발생하면 갑자기 그 현재 값의 반으로 떨어지는 사이클을 반복한다. 
늘어날 때는 cwnd의 사이즈 + 1, 줄어들 때는 cwnd의 사이즈 * 0.5이다.

4.2 Slow Start
슬로 스타트라고 부르는 초기 단계에는 TCP 송신자는 느린 비율(주로 1MSS)로 전송을 시작하지만, 지수적으로 전송률을 빠르게 증가시킨다. 그래프의 모양은 위에서 볼 수 있듯 선형이지만, 기울기는 1-> 2 -> 4 ..등으로 지수적으로 증가함을 볼 수 있다. 하지만 혼잡이 감지되면 윈도우 크기를 1로 줄여버린다는 특징이 있다.

4.3 Timeout
Timeout은 Loss가 생긴 것을 의미한다. 이 외에도 TCP LOSS에서는 3 duplicate ACK를 해결하는 방법도 존재한다. 3 duplicate ACK를 처리하는 TCP 통신방법 fast transmit 참고

TCP Tahoe일 때와, TCP Reno일 때 cwnd를 조절하는 방법이 각각 다르다.
아래에서 Tahoe와 Reno의 혼잡 윈도우 전개 그래프를 보자. 이 내용에 대해서는 자세히 다루지는 않겠다..
Threshold 초기값인 1부터 시작하여, 이후에 에러를 만나 해당 초기값으로 뚝 떨어지기도 하고, 임계값(ssthresh는 최고점(Tower)인 12의 절반인 6까지 뚝 떨어지기도 하는 구나..라는 그래프의 특징 정도만 알고 가자.
CA(congestion avoidance) : RTT 마다 1MSS 증가 -> ACK마다는 RTT당 ACK(=cwd/MSS) 수, 즉 MSS*MSS/cwd만큼 증가
SS(slow start)에서는 ack 하나 올 때 1 MSS 증가

4.4 Fast Recovery
위에서 볼 수 있듯 TCP는 데이터 전송 중 패킷 손실을 감지하면 CA와 SS를 통해 전송 속도를 줄이는 방식을 사용한다. 그러나 Fast Recovery는 이보다 더 빠르게 복구하는 방법이다. TCP Reno에서 사용되고, 3 duplicake ACK을 수신했을 때, 이전에 전송한 패킷이 손실되었음을 가정하고 cwd를 줄인만큼 패킷을 빠르게 다시 전송한다.

쉽게 말해 cwnd의 가장 앞에 있는 이빨빠진 것(1번째 것이라고 가정하자)이 계속해서 오지 않을 때, cwnd가 고정적인 값(N)이라면 A가 오고 난 후 cwnd가  (1+N)부터 다시 시작해야 한다. 이 때 in-flight 상태의 데이터가 존재하지 않아 네트워크 상의 비효율이 일어나기 때문에 cwnd를 유동적으로 바꾸는 것을 의미한다.

---

5. TCP 공평성

K개의 TCP session이 있다면, 각 세션들이 R/K만큼의 버퍼를 사용하도록 하는 것이 fairness의 목표이다.
아래 그래프에서 보면 Connection 1과 Connection 2는 결국 똑같은 양만큼의 bandwidth를 공유하는 쪽으로 진전됨을 알 수 있다. 

공평성 관련 이슈에는, 기본적으로 UDP는 이 fairness가 보장되지 못한다는 점과,TCP가 다중 병렬로 연결되어 있을 때 multiple object connection issue 등이 있다.