flow control과 congestion cotrol의 차이
TCP의 flow control과 congestion cotrol는 모두 자신의 데이터의 전송을 조절하여 지원한다.
그렇다면 둘의 차이는 뭘까?
-
flow control
플로우 컨트롤은 리시버의 버퍼의 오버플로우를 고려하여 데이터 전송을 조절한다. -
congestion cotrol
리시버의 버퍼는 고려하지 않고, 네트워크의(링크,라우터) 혼잡 상황을 고려하여 데이터 전송을 조절한다.
그러니까 받는 사람의 상황을 생각하여 데이터를 보내는 것이 flow control이고,
전달되는 링크와 라우터의 상황을 생각하여 데이터를 보내는 것이congestion cotrol이다.
즉 플로우 컨트롤은 받는 사람의 버퍼의 오버플로우와 loss를 생각한다면
혼잡제어는 라우터의 큐잉딜레이 상황이나 라우터 버퍼의 오버플로우, loss를 고려한다.
네트워크의 혼잡 상황 시나리오
TCP의 congestion cotrol의 과제는 다음의 두가지가 있다.
-
송신자는 혼잡상황을 어떻게 detection 하는가?
-
detection이 되면, 송신자의 윈도우 사이즈를 어떻게 조절을 해야하는가?
우선 1번에 대해 논하기 앞서 어떤 혼잡상황이 발생하는지에 대해 알아보자.
시나리오 1. 하나의 라우터, 무한 버퍼
가정 상황 - 2개의 다른 연결이 하나의 라우터를 지난다.
1. 라우터 1개
2. 무한 버퍼 (재전송 X)
3. 2개의 연결
4. 링크 용량 : R
1개의 라우터를 두고 전송률이 R인 링크에 두 연결이 지나가고 있다.
두 연결이 지나가고 있으므로, 각 연결이 동시에 최대 전송률을 가지려면 R/2 이다.
Q. arrival rate 람다 in 이 R/2에 가까울수록?
연결당 처리량(per-connection throughput)
-
0 ~ R/2 사이의 전송률: 수신자 측의 처리량은 송신자의 전송률과 같다. -
R/2 이상의 전송률: 처리량은 R/2
즉, 호스트 A와 B가 전송률을 아무리 높게 설정하더라도 각자 R/2보다 높은 처리량을 얻을 수 없다.
평균 지연
-
전송률이 R/2에 근접할 경우: 평균 지연은 점점 커진다. -
전송률이 R/2를 초과할 경우: 무제한 (무한한 사용 가능한 버퍼링을 가정)
패킷 도착률이 링크 용량에 근접함에 따라 큐잉 지연이 커진다.
시나리오 2. 하나의 라우터, 유한 버퍼
가정 상황 - 2개의 다른 연결이 하나의 라우터를 지난다.
1. 라우터 1개
2. 유한 버퍼 (재전송 가능)
3. 2개의 연결
4. 링크 용량 : R
라우터 버퍼가 유한하므로
버퍼가 가득 찼을 때 도착하는 패킷들은 버려진다.
➡️ 재전송이 일어난다.
- 애플리케이션이 원래의 데이터를 소켓으로 보내는 송신율 : λin 바이트/초
- 트랜스포트 계층에서의 송신율(제공된 부하, offered load)
: λ'in 바이트/초 = 최초의 데이터 전송과 재전송 합의 속도
어플에서는 데이터가 들어온 만큼 나가니까, λin = λout 이고,
트랜스포트 레이어 입장에서는 재전송이 발생할수 있으니, λin <= λ'in 이다
상황1. 어떠한 손실도 발생하지 않는 경우 (버퍼가 비어 있을 때만 패킷을 송신)
이때는 송신자가 라우터 큐의 상황을 알고 있어, 큐가 비었으면 보내고 비어있지 않으면 안보내는 상황을 가정한다.
(so, loss 발생 X)
- 연결의 처리량 = λin
- 평균 호스트 송신율은 R/2를 초과할 수 없다.
상황2. 패킷이 확실히 손실된 것을 알았을 때만 송신자가 재전송하는 경우
송신자는 보낸 패킷이 loss가 나면 바로 detection 할 수 있는 상황 가정.
(타임아웃, 3중복 ACK 를 기다리지 않고 바로 알 수 있는 상황)
즉, 정확한 loss detection 이 가능한 상황이다
- λ'in이 R/2일 경우 처리량 : R/2보다 작다 (R/3 정도)
전송된 데이터의 R/2 중
0.333R 바이트/초는 원래의 데이터 (R/3)
초당 0.166R 바이트/초(평균)는 재전송 데이터 (R/2 - R/3)
R/2 전송률로 라우터에 도착하면, 송신자는 버퍼 오버플로 때문에 버려진 패킷을 보상하기 위해 재전송을 수행해야 한다.
상황3. 송신자에서 너무 일찍 타임아웃되어 패킷이 손실되지 않았지만, 큐에서 지연되고 있는 패킷을 재전송하는 경우
송신자는 보낸 패킷의 loss를 time out 혹은 3중복 ACK로 loss detection하는 상황 가정.
즉, 정확한 loss detection 이 불가능한 상황이라 불필요 중복 data 재전송이 발생
-
데이터는 잘 도착 했지만 타임아웃으로 인해 재전송을 하는 상황이 발생할 수 있다.
-
위의 1,2상황(이상적인 상황)과 달리 현실적인 상황이다.
위의 시나리오2. 에서 혼잡 상황의 cost는
1. 재전송으로 인한 처리량 감소
2. 불필요한 중복패킷의 재전송으로 인한 처리량 감소
이렇게 두가지 이다.
시나리오 3. 여러개의 라우터(멀티 홉), 유한 버퍼
가정 상황 - 4명의 송신자가 각 2개의 라우터(2 홉 경로)를 통해 데이터 전송
1. 라우터 4개
2. 유한 버퍼 (재전송 가능)
3. 2홉 경로 (2개 라우터를 지남)
4. 링크 용량 : R
만약 빨간 연결에서 λ'in이 증가하면, 파랑 연결에서 온 데이터들은 빨간 연결에서 온 데이터보다 늦게 오기 때문에 큐의 상단에 쌓인다.
계속 λ'in이 증가하면 결국 파랑의 throuput은 0이 될수 있다.
혼잡으로 인해 downstream 에서 빨강이 때매 loss 가 일어나면 결국
이미 사용된 upstream의(파랑의 이전 라우터에서의) 전송 용량과 버퍼링 자원이 낭비된 것이다
TCP가 혼잡제어를 탐지하는 방식
1. end-end 혼잡 제어
송신자는 네트워크로(라우터,링크)부터 명시적인 피드백을 받지 않는다.
(플로우 컨트롤 처럼 자신의 여유공간을 직접 알려주지 않음)
즉, 이 방식은 손실과 지연을 통해 혼잡상태를 간접적으로 예측을 하는 것이다.
• 패킷 손실: TCP에서 패킷 손실이 발생하면, 이를 혼잡으로 해석합니다.
패킷이 손실되는 주된 이유 중 하나가 네트워크 혼잡에 의해
라우터나 스위치의 버퍼가 가득 차서 패킷을 드롭하는 경우이기 때문입니다.
• 지연 증가: 패킷 지연 시간이 길어지면, 이를 네트워크가 혼잡해지고 있다는 신호로 해석할 수 있습니다.
혼잡이 증가하면 패킷이 네트워크 장비에서 대기하는 시간이 길어져 지연이 발생하기 때문입니다.2. Network-assisted 혼잡 제어
라우터가 송신자/수신자에게 직접 피드백 제공
라우터가 혼잡 수준이나 송신 속도를 설정해서 피드백을 해주는 방식이다
ex) TCP ECN, ATM, DECbit protocols
AIMD (Additive Increase Multiplicative Decrease)
TCP는 sending rate를 RTT마다
1 MSS만큼 점진적으로 올리고,
loss가 발생하면 sending rate를 반으로 줄인다.
(점진적 향상 / 반값 할인)
MSS - TCP에서 송신자가 한 번에 전송할 수 있는 최대 데이터 크기를 의미(이 크기는 TCP 헤더와 IP 헤더를 제외한 순수 데이터(payload)의 크기)
-
수신자의 sending rate이 적절한지 판단
sending rate를 점진적으로 올리면서 내가 보내는 패킷에 대해 정상 ACK를 받으면 계속 속도를 1 MSS만큼 올린다. -
혼잡 detection
loss가 발생하거나 3 중복 ACK를 받으면 sending rate를 줄여야 한다.
sending rate을 조절하는 방법은 congestion 윈도우 사이즈를 조절하면 된다.
Additive Increase
1 RTT마다 congestion 윈도우 사이즈를 1 MSS 만큼 점진적으로 증가시킨다.
(1RTT: 데이터를 보내고 ACK를 받을 때 마다.)
최종적으로 조금씩 loss가 나지 않는 sending rate에 도달한다.
Multiplicative Decrease
loss가 발생하면 윈도우 사이즈를 반으로 줄인다.
-
TCP Reno
타임아웃 시 -> 윈도우 사이즈 1 MSS로 초기화
3중복 ACK 시 -> 윈도우 사이즈 반으로 줄인다. -
TCP Tahoe
타임아웃 시 -> 윈도우 사이즈 1 MSS로 초기화
3중복 ACK 시 -> 윈도우 사이즈 1 MSS로 초기화
AIMD방식의 이점
분산되고 비동기적 알고리즘을 사용한다.
이 뜻은 TCP의 혼잡제어가 하나의 서버(디바이스)가 관리하는게 아니라
각각의 송신자(디바이스)가 각자 판단하여 sending rate를 조절한다.
➡️ 알고리즘이 효율적이고, 구현이 단순하다.
➡️ 공정하다.
혼잡 제어의 동작
TCP 송신자의 congestion 윈도우는 아래와 같다.
이때 TCP rate = cwnd / RTT bps 이다
cwnd는 송신자가 한번에 보낼수 있는 data 사이즈이고(한번에 보낼수 있는 패킷개수)
RTT는 한번 data를 주고 ACK를 받는데 까지 걸리는 시간이다.
그러므로 TCP는 cwnd를 크기를 바꿔 전송속도를 조절할 수 있다.
송신자의 전송 리밋
마지막 보낸 패킷의 byte-마지막으로 ACK받는 패킷의 byte<=cwnd 사이즈
참고
flow와 혼잡제어를 동시에 고려 한다면 송신자의 sending rate는
MIN[rwnd, cwnd] 의 값을 기준으로 정해야 한다.
TCP slow start
윈도우의 사이즈를 늘릴 때 받은 정상 ACK 만큼 윈도우의 사이즈를 늘린다.
예를 들어 초기 윈도우 사이즈가 1 MSS라면
1개패킷을 보내고 ACK를 받으면 윈도우 사이즈가 2 MSS가 된다
다시 2개의 패킷을 보내고 ACK를 받으면 윈도우 사이즈 - 4 MSS
다시 4개를 보내고 ACK를 받으면 윈도우 사이즈 - 8 MSS....
이렇게 처음에는 느리게 증가하지만 점차 지수적으로 전송률이 증가하게 된다.
그렇다면 혼잡상황을 피하기 위해 어떤 방식으로 전송속도를 늦추게 될까?
Congestion Avoidance
윈도우 사이즈가 어떤
ssthresh(임계값)을 넘게 되면
그때부터 loss가 탐지 될 때 까지1 RTT마다1 MSS만큼 윈도우를 늘린다.
Q. 언제 지수 증가에서 선형 증가로 전환해야 하는가?
혼잡이 발생하기 직전에 선형 증가로 전환해야 한다.
즉, cwnd 크기가
타임아웃 발생 시 cwnd 크기의 절반에 도달할 때 전환해야 한다.
ssthresh(임계값)의 설정
ssthresh = loss 발견 시점의 윈도우 사이즈(타임아웃) / 2
임계값의 설정은 loss가 발견 시점에서의 윈도우 사이즈의 반 값으로 설정한다.
TCP Reno의 FSM
TCP Reno는 3중복 ACK시 (fast transmit) 윈도우의 크기를 반으로 줄이는데,
이 때 이미 임계값 만큼으로 윈도우의 크기가 도달 했으니 바로 선형증가하는 상태로 전이 된다.
3중복 ACK상태에서 재전송된 패킷이 타임아웃이면 생각보다 혼잡상황이 매우 심각한 상황이다.
➡️ 때문에 다시 임계값을 윈도우의 크기의 반으로 설정하고 (3중복 ACK당시 윈도우/4)
윈도우의 크기를 1로 초기화 한다.
TCP Cubic
TCP 타오, 레노 보다 발전된 방식으로
처음에는 전송속도를 더욱 빠르게 증가시키고
최대 전송속도에 가까울 수록 전송속도를 증가시킨다.
-
Wmax : 손실이 마지막으로 감지되었을 때 sending rate(윈도 크기)
-
K 시각 : 윈도 크기가 Wmax에 도달하는 시점
(그러니까 최대 사이즈에 도달하는 시간)
이라 하면, (K - 현재시간T)^3 만큼 증가하게 된다.
➡️ 초기에는 (K - T)의 값이 크니까 가파르게 증가하는 것이고
➡️ 막판에는 (K - T)의 값이 작으니까 완만하게 증가하는 것이다.
큐빅은 리눅스 요즈음의 TCP 웹 서버에서 주로 사용된다.
병목링크에서의 혼잡 제어
TCP는 loss가 발생하기 전까지 전송속도를 높이는 방식으로 데이터를 전송한다.
하지만 패킷의 loss와 딜레이는 하나의 병목링크 때문에 일어난다.
즉, 병목링크의 용량 이상으로 throughput이 나올 수 없다.
그러니까 TCP는 전송속도를 조절할 때 병목링크의 용량을 기준으로 전송속도를 조절해야 한다.
(병목링크보다 빠르게 전송해도 병목링크에서 큐잉 딜레이와 loss가 발생하기 때문에 의미가 없다)
떄문에 병목 링크의 큐가 아주 가득 차기 전에 혼잡을 detection하여
미리 sending rate를 조절하면 좋은 성능을 기대할 수 있다.
다음의 두 가지방식은
- Delay-based TCP congestion control
- Explicit congestion notification (ECN)
loss가 일어나기 전에 혼잡상황을 detection하여 sending rate를 조절하는 방식이다.
loss 없는 혼잡 제어
Delay-based TCP congestion control
송신자는 패킷을 보낼때 마다 RTT를 측정하며 딜레이를 계산하여 미리 sending rate를 조절한다.
RTT(min): 혼잡 없는 상황에서 최소 RTT- 비혼잡 경로에서의 이상적인(최대) 처리량 = cwnd / RTT(min)
(전체 윈도우 크기 / 최소 RTT) - 측정된 처리량 = 마지막 RTT에서 보낸 패킷들의 총 byte / RTT(최근)
cwnd 조절 규칙
1. 측정된 처리량이 비혼잡 처리량과 “아주 가깝다면”
• cwnd을 선형적으로 증가.
• 이는 네트워크 경로가 혼잡하지 않다는 신호이므로, cwnd를 선형적으로 증가시켜 더 많은 데이터를 전송할 수 있도록 함.
2. 측정된 처리량이 비혼잡 처리량보다 “현저히 낮다면”
• 혼잡 창(cwnd)을 선형적으로 감소.
• 이는 네트워크 경로가 혼잡 상태라는 신호이므로, cwnd를 줄여 혼잡을 완화.
처리량 최대화: “파이프를 가득 채우되…”
• 네트워크 경로의 용량을 최대한 활용하여 높은 처리량을 유지하려고 합니다. 이는 전송 가능한 모든 대역폭을 활용하여 네트워크의 사용 효율을 극대화하는 것을 의미합니다.
• 지연 최소화: “더 가득 채우지는 않기”
• 혼잡으로 인해 추가적인 지연이 발생하지 않도록 조절합니다. 너무 많은 패킷을 보내지 않음으로써, 네트워크가 혼잡해져서 불필요한 대기 시간이 발생하는 것을 방지합니다.특징
RTT와 대역폭 관찰하여 손실없이 혼잡을 감지한다.
지연기반은 파이프를 가득 채우되(처리량 최대화) 더 가득 채우지는 않는(지연 최소화)것을 목표로 한다.
ex) Google의 BBR (Bottleneck Bandwidth and RTT)
Explicit congestion notification (TCP ECN)
network-assisted 혼잡제어 방식으로, 각 라우터가 혼잡 상황을 수신자에 알리고, 수신자는 송신자에 알림으로서 미리 혼잡 상황을 감지하는 방법이다.
-
라우터가 혼잡을 감지하면 패킷의
IP 헤더의 ECN bit를 설정하여 수신자에 보낸다. -
수신자는 ACK 패킷에
TCP 헤더의 ECE bit를 1로 설정하여 혼잡 상황을 송신자에 공유한다. -
송신자는 혼잡상황임을 알았으니 윈도우를 조절하여 sending rate를 조절한다.
TCP fairness
TCP fairness의 목표는 K개의 TCP 세션이 대역폭 R인 한 병목링크에 연결되어 있다면, 각각 R/K 만큼 공평히 나누도록 하는 것이 목표이다.
TCP는 fairness 한가?
두개의 세션
같은 RTT 상황을 가정한다.
UDP와 TCP의 fairness
• 멀티미디어 애플리케이션은 TCP의 혼잡 제어를 원하지 않기 때문에 주로 UDP를 사용합니다.
• 이유: 오디오/비디오 스트리밍은 일정한 속도로 데이터를 전송해야 하므로, 혼잡 제어로 인해 전송 속도가 제한되는 것을 피하려 합니다.
• UDP는 혼잡 제어가 없어 패킷 손실을 감수하고서라도 일정한 속도로 데이터를 보냅니다.
• 공정성 문제: 인터넷에는 TCP 같은 혼잡 제어를 강제하는 규제가 없기 때문에, UDP가 네트워크 자원을 많이 사용할 경우 TCP 연결들이 불리해질 수 있습니다.
병렬 TCP 연결에서 fairness
• 애플리케이션은 두 호스트 간에 여러 개의 TCP 연결을 동시에 열어 전송 속도를 높일 수 있습니다.
• 예를 들어, 웹 브라우저는 여러 연결을 열어 더 많은 데이터가 동시에 전송되도록 합니다.
• 공정성의 예시:
• 네트워크의 링크 대역폭이 R이고, 현재 9개의 TCP 연결이 있다면 새로운 TCP 연결을 추가할 때마다 각 연결이 R/10의 비율로 대역폭을 나누어 가집니다.
• 그러나 하나의 애플리케이션이 11개의 TCP 연결을 열면, 총 20개의 연결 중 절반을 차지하여 R/2만큼의 대역폭을 차지할 수 있게 됩니다.
이로 인해 다중 TCP 연결을 여는 애플리케이션이 더 많은 대역폭을 가져가는 비공정한 상황이 발생할 수 있습니다.