Study & Project repository

Principles of congestion control

• 네트워크상에 패킷이 많아져서 발생하는 congestion을 최대한 줄이기 위해 여러 경로로 패킷을 보내주는 알고리즘이 필요
• flow control과 다름
• 패킷 손실이나 긴 지연 발생

혼잡제어의 3가지 시나리오

• 2개의 송신자와 무한 버퍼를 갖는 하나의 라우터

• 2개의 호스트가 각자의 목적지 사이에 단일 홉을 공유하는 연결을 가진다고 가정
• 두 호스트는 같은 byte/sec의 평균 전송률로 연결에 데이터를 보내고 있음
• 라우터는 무제한의 버퍼 공간을 가진다고 가정
• 두 호스트가 매우 많은 데이터를 동시에 목적지로 전송한다면?

• 링크의 최대 전송 용량이 R이라면 각자의 서버가 R/2씩 사용하면 유한한 지연으로 수신자에게 수신
• 그러나 R/2를 넘어가면 데이터 처리량은 R/2로 그대로이고 한 라우터에 공유된 버퍼에 쌓이는 패킷들이 많아질 것이며 딜레이 또한 무한하게 증가
• 이렇게 되면 타임아웃으로 불필요한 재전송 또한 많아지고 함께 전송되는 새로운 패킷들과 합쳐져 보내는 양도 많아짐 -> 결국 네트워크가 느려짐

• 2개의 송신자, 유한 버퍼를 가진 하나의 라우터

• 무한하지 않은 유한한 라우터의 버퍼라고 가정 -> 버퍼가 가득 찼을 때는 버려짐

1. 람다는 원래 데이터, 람다 프라임은 원래 데이터 + 재전송되는 데이터
2. sender가 버퍼의 빈 공간을 인식하고 꽉 차있지 않을 경우에만 보낸다면? - λ와 λ'값이 같으므로 어떠한 손실도 발생하지 않고, 연결의 처리량은 λin이 됨, 이 경우 아래와 같은 그래프로 표현됨

• 패킷이 확실히 손상된 것을 알았을 때만 송신자가 재전송하는 좀 더 현실적인 경우 -> 손상됐다고 판단된 것만 재전송 수행
• 송신자에게서 너무 일찍 타임아웃되는 바람에 패킷이 손실되지 않았지만 큐에서 지연되고 있는 패킷을 재전송하는 경우 -> 라우터가 패킷을 불필요한 복사본들을 전송하는데 링크 대역폭을 사용하는 원인

• 4개의 송신자와 유한 버퍼를 가지는 라우터, 그리고 멀티홉 경로

• 그림과 같이 겹쳐지는 2홉 경로를 통해 패킷을 전송
• 모든 호스트는 동일한 값을 가지고, 모든 라우터 링크는 R byte/sec 용량을 가진다고 가정
• λin값이 매우 커지는 경우 모든 라우터의 버퍼는 각 연결된 호스트가 보내는 패킷으로 채워지며 계속 쌓인다면 각 라우터의 처리량은 0이 되어 제공된 부하와 처리량 간의 트레이드오프가 발생

TCP congestion control

• additive increase : 손실이 감지될 때 까지 매 RTT마다 1 MSS씩 증가
• multiplicative decrease : 손실 후 1/2로 줄임

• 삼각파형이 생성됨

• 발신자 제한 : 마지막보낸 바이트 - 마지막 ACK받은 바이트 ≤ cwnd
• 결론적으로 cwnd의 값을 조절하여, 송신자는 링크에 데이터를 전송하는 비율을 조절

TCP Slow Start

1. 처음 시작은 cwnd = 1 MSS로 시작
2. 이상이 없다면 2 MSS -> 4 -> 8 -> 16.... 증가시킴
3. 타임아웃에 의한 손실 이벤트가 발생한다면 TCP 송신자는 cwnd를 1MSS로 한 후 새로운 슬로 스타트를 실행
4. 그리고 임계치를 ssthresh = cwnd/2로 지정
5. ssthresh의 값에 도달하게 되면 슬로 스타트는 종료되고 혼잡 회피 모드에 들어감

• TCP Tahoe : Timeout이 발생한 경우, ssthresh에 도달한 후 1 MSS씩 증가하다가 혼잡 발생시 1로 내려간 후 다시 슬로우 스타트 실행
• TCP Reno : ACK의 3중복으로 손실이 발생했다고 판단하는 경우 -> ssthresh를 손실이 발생한 순간의 반으로 설정 후 거기서부터 다시       1 MSS씩 증가시킴

TCP throughput

• 초기 슬로 스타트 기간을 무시하고 손실이 타임아웃이 아니라 중복 ACK로 표시된다고 가정
• TCP의 혼잡제어는 매 RTT마다 1 MSS씩 cwnd의 선형 증가와 3개의 중복 ACK 이벤트에서 cwnd의 절반화로 구성
• 이런 경우 위의 단락에서 제시된 그림처럼 톱니모양의 Reno알고리즘으로 나타남
• 톱니모양의 TCP 동작이 주어지면 장시간 연결된 TCP 연결의 평균 처리율은? - 타임아웃 후 슬로스타트의 재시작 부분은 무시할 정도로 짧음

• 윈도우 크기가 w 바이트이고 왕복시간은 RTT초이면, TCP의 전송률은 대략 w/RTT
• TCP는 손실 이벤트가 발생할 때까지 RTT당 하나의 MSS만큼 w를 증가
• 손실 이벤트가 발생하는 시점의 w값을 W로 지정
• RTT와 w가 대체로 링크 동안 일정하다고 가정하면 TCP전송률은 W/(2*RTT)부터 W/RTT까지의 범위를 가짐

• 따라서 평균 처리율은 3W/4RTT bytes/sec

TCP Fairness

• 목적 : Rbps의 동일한 병목 link를 공유하는 경우 K개의 TCP연결이 되어있다면 각각 평균 R/K비율을 가져야 함

• 만약 연결된 두 TCP연결이 가장 아래에 있는 화살표의 시작부분에서 전송량이 증가하기 시작한다면 RTT당 1MSS씩 늘어나게 됨
• 두 연결의 전송률 합이 R을 넘어가면 손실이 생기며 알고리즘에 따라서 각각 절반씩 감소하고 다시 1MSS씩 증가하는 양상을 반복하게 됨
• 반복하다보면 결국 동등한 대역폭의 공유선으로 수렴

• Fairness and UDP

1. reliable과 congestion control을 따지면서 전송할 때, 오히려 TCP보다 UDP가 나을 수 있음
2. 병렬 TCP연결 : R의 링크에 9개의 기존 연결이 있었다고 가정하고 새로운 애플리케이션이 하나의 TCP연결을 한다면 R/10의 전송률을 얻음 -> 그러나 11개의 TCP연결을 사용한다면? -> 결국 이 연결은 R/2이상의 불공평한 연결이 되는 것

Explicit Congestion Notification(ECN)

• 네트워크-지원 혼잡 제어

• 혼잡을 나타내기 위해 네트워크 라우터에 의해 표시된 2bit의 IP헤더(ToS field)
• 수신 호스트로 운반되는 혼잡 표시, ECN = 11
• 수신자는 송신자에게 혼잡을 알리기위해 ACK에 ECE비트 설정후 ACK를 전송
• ACK안의 ECE비트를 확인한 sender는 전송하는 양을 줄이는 등의 조치를 취함