Move Fast

▶ Congestion Control

- 너무 많은 출발지(네트워크 장비)에서 네트워크가 감당하기에는 너무 많은 데이터를 너무 빠르게 전송하여 발생하는 네트워크 혼잡 현상이다.

- 징후

• 라우터에서 버퍼가 오버플로우되어 패킷 손실의 발생
• 라우터 버퍼에서 긴 큐잉 지연(Queueing delay) 발생

- 흐름 제어(Flow Control)와는 다르다.

▶ 라우터가 무한한 크기의 버퍼를 갖는 경우

- 출력 링크의 수용력을 R이라고 가정했을 때,

• 전송률이 아무리 커도 링크 처리량(수용력)은 R/2을 넘을 수가 없다.
• 지연 시간이 지수적으로 증가하므로 혼잡 시 큰 지연이 발생한다.

▶ 라우터가 유한한 크기의 버퍼를 갖는 경우

- 송신측에서는 타임아웃된 패킷(손실 패킷)의 재전송이 이루어진다. 즉, 큐가 유한할 경우 패킷의 손실이 발생한다.

• (λin : 입력 버퍼에 패킷이 들어오는 속도, λout : 출력 버퍼의 송신 속도)
• 입력 버퍼의 속도와 출력 버퍼의 속도가 같은 경우 : λin = λout
• 전송 계층의 입력 버퍼의 속도가 재전송 속도까지 포함할 경우 : λ'in = λout

[왼쪽부터 가장 이상적인 상황, 덜 이상적인 상황, 가장 현실적인 상황]

- 가장 이상적인 상황 : 라우터 버퍼가 이용가능할 때만 송신측에서 패킷을 전송하므로 어떤 패킷의 손실도 발생하지 않음.

λin = λ'in = λout

- 덜 이상적인 상황 : 라우터 버퍼가 꽉 차서 패킷이 손실될 수 있으므로 송신자는 패킷이 손실되었을 때만 재전송한다.

λ'in > λout

- 가장 현실적인 상황 : 라우터 버퍼가 꽉 차서 패킷이 손실될 수 있고, 패킷이 크게 지연되어 송신측의 타이머가 타임아웃될 수 있으므로, 두 상황 모두 재전송한다. 즉, 패킷의 큰 지연으로 불필요한 재전송이 늘어난다.

λ'in >> λout

- 혼잡 비용

• 손실된 패킷을 재전송한다.
• 큰 지연으로 인한 불필요한 재전송이 발생 => 라우터가 패킷의 불필요한 복사본을 포워드(입력버퍼->출력버퍼)하는데 링크의 대역폭을 사용하므로 네트워크 자원이 비효율적으로 사용된다.

▶ 여러 개의 네트워크 장비를 거쳐가는 경우

- λ'in : 재전송을 포함하여 입력버퍼에 패킷이 들어오는 속도

- 데이터의 traffic이 증가하게 되므로 혼잡이 커지고 지연 시간이 길어진다.

- λ'in 이 계속 증가하게 되면(재전송 발생 증가), 패킷이 경로 상에 버려지는 상황이 증가한다는 뜻으로, 버려지는 지점까지 패킷을 전송하기 위해 상위 라우터에서 사용되는 전송 용량은 낭비된다.

▶ AIMD (Additvie Increase Multiplicative Decrease)

- 혼잡 윈도우 크기(Congestion Window Size, cwnd) : 수신측의 윈도우 크기(rwnd)에 영향을 받으며, 송신측에 있는 윈도우 크기이다.

- 전송 후 ACK받지 못한 세그먼트들 : LastByteSent - LastByteRead <= cwnd <= rwnd

- 송신측에서 ACK를 못받고 타임아웃되면 패킷 손실이 발생한 것으로 알고 Congestion으로 받아들인다. 따라서 송신측은 윈도우 크기(cwnd)를 줄여서 데이터 전송 속도를 조절한다.

- 송신측에서 패킷의 손실이 발생할 때까지 이용가능한 대역폭을 탐지하면서 전송률(Congestion Window Size, cwnd)을 증가시킨다.

- 가법적 증가(Additive Increase) : 손실이 발견될 때까지 매 RTT(왕복시간)마다 1MSS씩 cwnd를 증가시킨다. 추가로 매 ACK마다 cwnd는 MSS * (MSS/cwnd) 바이트씩 증가한다.

- 승법적 감소(Multiplicative Decrease) : 손실이 발생한 후에 cwnd를 절반으로 감소시킨다.

- 그래프 상에서 cwnd 값이 톱니 모양의 패턴을 가지게 된다. 값이 꺾일 때마다 패킷의 손실이 발생한 것이다.

▶ Congestion Control Details

- 송신자에서 ACK받지 않은 데이터 양을 제한하여 송신률을 제한한다.

- 송신자의 송신률(Bytes/sec):

- 송신자의 혼합감지

• 손실 이벤트 : 타임아웃 또는 3개의 중복 ACK
• 손실 이벤트가 발생하면 송신률을 감소시킨다.

- 혼잡제어 알고리즘의 3가지 요소

• AIMD
• 슬로 스타트(slow start)
• 타임아웃에 대한 반응

▶ Slow Start

- TCP 연결이 시작될 때 혼잡 윈도우 크기(cwnd)의 초기값은 1MSS 이다.

- TCP 연결이 시작한 이후 데이터의 첫 번째 손실이 발생하기 전까지 송신률을 지수적으로 증가시킨다.

- 매 RTT마다(오류없이 ACK가 올때마다) cwnd는 2배씩 증가한다.

- 즉, 연결가능한 대역폭이 MSS/RTT(송신률)보다 아주 큰 경우, 송신률은 cwnd와 비례하므로 초기에는 느리지만 지수적으로 빠르게 증가한다.

▶ 타임아웃에 대한 반응

- TCP Tahoe : 타임아웃 또는 3개의 중복ACK 상황에서 항상 cwnd를 1 MSS 로 설정한다.

- 타임아웃에 의해 감지된 손실 : 전혀 전송되지 않은 것으로 간주하고, 심각한 혼잡 상황으로 받아들인다.

• cwnd = 1MSS (Slow Start 발생)
• cwnd는 지수적으로 증가하다가 임계값(threshold)에 달하면, 선형적으로 증가(혼잡 회피)한다.

- 3개의 중복 ACK에 의해 감지된 손실 : 다른 세그먼트(or 패킷)는 잘 도착했으므로 일부 세그먼트들은 전송해도 된다는 것으로 간주하고, 조금 혼잡한 상황으로 받아들인다.

• TCP Reno : cwnd는 절반으로 감소하고 이후에 선형적으로 증가한다.
• 이전의 TCP Tahoe 는 슬로 스타트(Slow Start)로 진입한다.

[ Loss 발생 시, TCP Tagoe는 1MSS로 뚝 떨어짐, TCP Reno 절반으로 떨어짐 ]

- cwnd 값이 타임아웃 전의 1/2 크기에 도달할 때, 지수적 증가는 선형적 증가로 변경된다.

- 가변적 임계값(variable threshold) 설정 : 손실 이벤트가 발생 시 임계값을 손실 이벤트 전의 cwnd의 1/2 크기로 설정한다.

[전체적인 구상도] 

▶ Throughput

- cwnd와 RTT 함수로써 TCP의 평균처리율은 슬로스타트는 무시하고, 항상 전송한 데이터로 추정한다.

- 평균 처리율 

- 손실이 발생하면 윈도 크기는 1/2로 감소하고 전송률도 비례하므로 1/2로 감소한다.

- cwnd가 커지면 처리율이 증가(데이터 전송 속도가 빨라짐)하므로 Congestion도 증가한다.

- 미래에 장거리 및 고속링크일 경우 cwnd = 83,333 만큼 요구되는데 이는 많은 양의 세그먼트이며 손실 가능성이 높다.

- 손실 관점에서 평균 처리율 (L:손실률)

- 고속 환경을 위한 새로운 버전의 TCP 연구가 필요하다.

▶ 공평성 (TCP Fairness)

- K 개의 TCP 연결이 R bps의 전송률(대역폭)의 병목 링크(bottleneck link)를 통과하는 경우, 각 연결의 평균 전송률이 R/K에 가깝다면 TCP 혼잡제어 메커니즘은 공평하다.

- 공평한 이유는 이상적으로 두 처리율의 합은 R과 같아야 한다.

(동등한 대역폭 공유와 전체 대역폭 이용선의 교차 지점 가까운 곳의 처리율)

- 공평성과 UDP

• 멀티미디어 애플리케이션들은 TCP를 사용하지 않으므로, 혼잡제어로 인한 전송 the고 조정을 하지 않는다.
• UDP의 사용은 일정한 속도로 음성과 영상을 전송하며 패킷 손실을 감수한다.
• TCP관점에서 UDP는 공평하지 못한데, 그 이유는 다른 연결과 협력하지 않고, 전송률 조절도 하지 않기 때문이다. 이 부분에 대하여 UDP가 TCP Traffic을 밀어낼 가능성이 있다.
• 관련 연구 분야로는 UDP 트래픽으로 dsl한 인터넷 마비 방지하는 혼잡제어 방식이 있다.

- 명확한 혼잡 제어 통보 (Explicit Congestion Notification, ECN)

• IP헤더의 Tos 필드에 2비트가 Congestion을 나타내기 위해 네트워크 라우터에 의해 값이 저장된다.
• 즉, 네트워크 장비(라우터)가 Congestion을 감지하고 호스트에게 알려준다.
• 주로 심각한 상황이 되면, 송신측의 혼잡을 알리기 위해 수신측에서 ACK세그먼트의 ECE 비트를 설정한다.

▶ Fast Retransmit (빠른 재전송)

- 재전송 타이머 값이 종종 상대적으로 길어지므로, 손실된 패킷의 재전송 전에 지연시간이 커진다.

- 위의 상항을 해결하고자 중복 ACKs를 통해 손실된 세그먼트를 검출한다.

- 송신측에서 바로바로 여러 개의 세그먼트를 전송할 경우, 세그먼트가 손실되면 수신측에서는 중복 ACK를 보내게 되는데, 타임아웃 전에 송신측에서 중복 ACK를 3번받게 되면 세그먼트를 즉시 전송한다. 즉, 수신측이 기다리는 순서번호의 세그먼트보다 큰 순서번호의 세그먼트가 3개 도착할 경우를 의미한다.

[ ACK2 의 중복수신 3번 이후 3번 데이터 즉시 전송 ]

▶ Flow Control

- TCP 송신자가 데이터를 너무 빠르게 또는 너무 많이 전송하여 수신버퍼가 오버플로우(Overflow)하는 것을 방지한다.

- TCP의 수신자는 수신버퍼(receive buffer)를 가지는데, 상위 계층으로 세그먼트를 보내는 애플리케이션 프로세스가 수신버퍼로부터 데이터를 읽는 속도가 느릴 수 있다.

- 목표 : 애플리케이션 프로세스의 읽는 속도 = 송신자가 데이터를 전송하는 속도

- 즉, 흐름제어는 속도를 일치시키는 서비스이다.

- Receive Window(rwnd) : 수신버퍼의 가용 바이트 수로, 송신 윈도우 크기를 결정한다.

LastByteRcvd - LastByteRead <= RcvBuffer

[밑에서 수신 받은 번호 - 위로 올려 보낸 번호 = 수신했지만 상위계층으로 전송되지 않은 데이터들]

=> 항상 수신 버퍼보다 작아야한다. 초과하면 오버플로우 발생.

rwnd = RcvBuffer - (LastByteRcvd - LastByteRead)

    = RcvBuffer - (수신했지만 상위 계층으로 전송하지 않은 데이터들)

- 수신자는 TCP헤더에 수신버퍼안에 있는 여유공간(Receive Window, rwnd) 값을 포함함으로써 버퍼에 공간이 있음을 송신자에게 알린다.

- 수신버퍼의 크기는 소켓의 옵션을 통해 설정되는데 디폴트 값이 4096바이트이다.