지난 시간 배운 내용

sender가 받은 ACK #를 y 라고 할 때, y≤LastByteRcvd+1
(network 상태에 따라 손실이 발생할 수도 있으니 y는 작거나 같다)

y≤SendBase라면 duplicated ACK

Sender TCP’s window size W = min ( rwnd, cwnd )

rwnd: receiver TCP의 receive buffer의 잔여량을 의미하는 파라미터

receiver TCP가 TCP header에 넣어 sender TCP에게 알려줌으로써 sending rate를 조정하게 하는 flow control을 위한 파라미터.

cwnd: Sender TCP의 local parameter로 망 상황을 간접적으로 예측하여 조정하는 값

결과적으로 sender TCP는 rwnd와 cwnd 중 더 작은 값으로 sending rate (즉, the maximum number of inflight bytes (ACK 없이 보낼 수 있는 byte 수))를 조정한다.

한 segment의 크기는 MTU, 즉 outgoing link의 대역폭을 고려해서 결정된다. 그 segment를 몇 개 보낼지 (총 몇 byte를 보낼지)가 window size에 의해 결정된다.

따라서 window size는 최소 한 MSS (<MTU)보단 커야 한다.

TCP round trip time, timeout

PopQuiz

마지막 측정된 SampleRTT 가 1초였다면, update되는 TimeoutInterval값은 1초보다 크다.

⇒ F. 더 클 수도, 작을 수도 있다.

TimeoutInterval=EstimatedRTT+4*DevRTT

TCP reliable data transfer

TCP는 in-order delivery, cumulative ACK이기 때문에 timer를 ACK이 안 된 세그먼트 중 가장 오래된 것(Oldest UnACKed Bute)에 붙이고 이것이 SendBase 가 됨. ( SendBase < NextSequenceNum 일 때만)

만약 SendBase =NextSequenceNum라면 inflight bytes가 없음 (노란색=전송 중인 UnAcked Bytes) → Timer 설정 X

TCP fast retransmit

3 duplicated ACK for same data ⇒ retx the oldest unACKed byte (unACKed segment with smallest SequenceNumber

why not 1, 2?

to detect delayed (not lost) pkt & avoid unnecessary Retx

TCP flow control

TCP 연결의 end host들은 연결에 대한 개별 recv 버퍼를 설정한다. 만약 애플리케이션이 데이터를 읽는 속도가 비교적 느리다면, sender가 더 많은 데이터를 빠르게 전송함으로써 recv 버퍼에 오버플로우를 발생시킬 수 있다. 즉, sender의 sending rate을 애플리케이션이 데이터를 읽어가는 속도와 같게 조절하는 것이 flow control

flow control: 버퍼 잔여량(가용한 버퍼 공간이 얼마나 되는지) 알려줘서 sender의 sending rate을 control

(rwnd 필드에 버퍼의 잔여량을 넣어줌)

TCP는 full-duplex 통신을 하므로 각 sender는 별개의 rwnd 변수를 가진다. 호스트 B가 A로부터 파일을 전송 받아야 할 때, 이 연결에 할당된 수신버퍼의 크기를 RcvBuffer라고 명명하고, 아래 변수들을 정의한다.

LastByteRead 호스트 B의 애플리케이션 프로세스에 의해 버퍼로부터 읽힌 데이터 스트림의 마지막 바이트 수

LastByteRcvd 호스트 B에서 네트워크로부터 도착하여 수신 버퍼에 저장된 데이터 스트림의 마지막 바이트 수

LastByteRcvd - LastByteRead ≤ RcvBuffer

rwnd 는 버퍼의 여유공간.

rwnd=RcvBuffer-(LastByteRcvd-LastByteRead)

Flow control 중 receiver TCP가 rwnd = 0으로 알려준 경우 sender TCP는 sending을 멈추게 됩니다. (만일 TCP receiver측에서 TCP sender 쪽으로 보낼 응용 데이터가 없는 경우라면 TCP receiver가 다시 available 해진 자기의 receive buffer 상황을 sender TCP에게 알려줄 기회가 없으므로) 언제까지 sending을 hold할 것인가, 언제 sending을 재개할 것인가의 문제가 있는데, RFC에서는 이런 경우 sender TCP가 지속적으로 빈 segment을 보내서 TCP receiver가 다시 updated rwnd를 포함한 ACK을 보내도록 유도하는 방식을 설명하고 있습니다.

Agreeing to establish a connection

A needs to sure that B knows A is ready to talk B (3-way)

---

오늘은 rwnd (flow control)는 무시하고, cwnd에 집중하여 TCP가 어떻게 네트워크의 congestion을 제어 하는지 학습할 것

3-way handshaking

2-way handshake failure scenarios:

TCP 3-way handshake

클라이언트가 서버와의 연결을 초기화 하길 원할 때 서버가 클라이언트의 dedicated된 소켓을 여는 과정.

1단계: 먼저 클라이언트 TCP는 서버 TCP에게 TCP 세그먼트를 송신한다. 이 세그먼트는 애플리케이션 계층 데이터를 포함하지 않고, 세그먼트의 헤더에 SYN 이라는 하나의 플래그 비트를 가진다. 추가로 클라이언트는 최초의 SequenceNumber를 선택한다(client_isn). 이것을 TCP SYN 세그먼트라고 한다. 이 세그먼트는 IP 데이터그램 안에서 캡슐화되고 서버로 송신된다.

SYNbit=1, Seq=x, ACKbit=0, ACK ACKnum=쓰레기값

2단계: TCP SYN 세그먼트를 포함하는 IP 데이터그램이 서버 호스트에 도착했을 때, 서버는 데이터그램으로부터 TCP SYN 세그먼트를 뽑아낸다. 그리고 연결에 TCP 버퍼와 변수들을 할당한다. 또한 클라이언트 TCP로 ACK 세그먼트를 송신한다. 이 ACK 세그먼트도 애플리케이션 계층 데이터를 포함하지 않는다.

그러나 3개의 중요한 정보를 포함하는데, 1) SYN 비트는 1로 설정된다. 2) TCP 세그먼트 헤더의 ACK 필드는 client_isn+1 로 설정된다. 3) 서버는 자신의 최초의 SequenceNumber 를 설정하고(server_isn), TCP 세그먼트 헤더의 SequenceNumber 필드에 이 값을 넣는다. 이 ACK 세그먼트는 "나는 당신의 최초 client_isn를 가지고 연결을 시작하기 위해 당신의 SYN 패킷을 수신했다. 나는 이 연결 설정에 동의한다. 내 자신의 최초의 SequenceNumber 는 server_isn 이다."라고 말하는 것이다. ACK 세그먼트는 SYNACK라고도 한다.

SYNbit=1, Seq=y, ACKbit=1, ACKnum=x+1

3단계: SYNACK 세그먼트를 수신하면, 클라이언트는 연결에 버퍼와 변수들을 할당한다. 그 다음 클라이언트 호스트는 서버로 또 다른 세그먼트를 송신한다. 클라이언트는 TCP 세그먼트 헤더의 ACK 필드 안에 server_isn+1값을 넣고, 이 마지막 세그먼트가 서버의 ACK 세그먼트를 확인한다. 연결이 설정되었기 때문에 SYN 비트는 0으로 설정된다. 3-way handshake의 세 번째 단계는 클라이언트에서 서버로 세그먼트 페이로드에 데이터가 운반될 수 있다. (piggyback)

SYNbit=0, ACKbit=1, ACKnum=y+1

이 세 단계가 완료되면, 클라이언트와 서버 호스트들은 각각 서로에게 데이터를 포함하는 세그먼트를 보낼 수 있다. 이 다음의 세그먼트 들의 SYN 비트는 0이다.

• random 한 SequenceNumber 를 설정하는 이유

이전의 connection으로 받는 데이터로 오인하지 않기 위해

TCP: closing a connection

TCP는 full-duplex 통신을 하기 때문에 Client의 send/recv buffer, Server의 send/recv buffer를 각각 닫아 줘야 함.

연결 종료를 결정할 땐, 클라이언트 애플리케이션 프로세스가 종료 명령을 내리고, 헤더의 FIN 플래그 비트가 1로 설정된 세그먼트를 보낸다.

⇒ 클라이언트의 send buffer 종료, 여전히 data를 받을 수는 있음

서버가 이 세그먼트를 수신하면, 서버는 클라이언트에게 확인 세그먼트를 보내고,

⇒ 서버는 여전히 data를 보내고 받을 수 있음

FIN=1로 설정된 자신의 종료 세그먼트를 다시 보낸다. (위와 함께 보낼 수 있음)

⇒ 서버의 send buffer 종료 요청.

마지막으로 클라이언트는 서버의 종료 세그먼트에 ACK을 한다.

⇒ 서버의 send buffer 종료, ACK의 loss를 대비한 retx를 위해 2분 정도 기다림.
클라이언트의 응답 없을 시 서버는 maximum number of retry 후 종료.

이 시점에서 두 호스트의 모든 자원들은 할당이 해제된다.

---

Congestion control

rwnd 무시하고 cwnd 만을 고려해 window size W를 어떻게 조정하는지 학습

Principles of congestion control

• lost packets (output buffer overflow at routers)
• long delays (queueing in router buffers)

Causes and costs of congestion at NW router

네트워크 라우터의 output buffer에서 발생하는 congestion의 원인과 비용

Causes

1. Link capacity = transmission rate (R)
   호스트 A가 라우터를 통해 호스트 B로 메시지를 보내려 할 때

• λin = 애플리케이션이 데이터를 소켓으로 보내는 sending rate (데이터의 양)
• λin = 트랜스포트 계층으로부터 네트워크 안으로 보내는 세그먼트의 sending rate (데이터의 양 재전송 데이터) ⇒ λin = λin + retx ( λ`in > λin )
  라우터로 들어오는 데이터의 양이 R, 라우터 output buffer의 transmission rate이 R이면 부하가 발생하지 않음
  ⇒ 라우터 output buffer의 transmission rate이 라우터의 수신율 보다 작다면 혼잡이 발생할 수 있다. 따라서 link capacity (transmission rate)이 문제가 될 수 o

2. Finite buffer at router
   유한한 버퍼를 가진 라우터

• 만약 라우터의 버퍼가 무한하다면? Queueing delay가 무한히 증가할 것
  but, loss는 발생하지 않음 (loss는 버퍼 size가 유한하기 때문에 발생)
• 유한한 버퍼, sender의 timeout이 고정된 채 버퍼의 사이즈만 늘렸다면?
  loss는 감소하고, Queueing delay는 증가할 것, 이 때 timeout 값이 고정되어 있
  다면 (premature timeout) unnecessary retransmission 이 증가할 것
  결과적으로 throughput이 감소하게 됨

3. multi-hop path
   4개의 sender와 유한 버퍼를 가진 라우터, multi-hop 경로 / A → C, D → B 일 때

D → B와 A → C는 동일한 라우터의 버퍼를 공유한다. but, A는 동일 라우터까지 one-hop, D는 라우터로 2-hop에 오기 떄문에, 버퍼를 빨리 차지하는 A에 비해 D가 불리. 
but, 유한한 버퍼로 traffic이 쏟아지기 때문에 A가 라우터 버퍼를 모두 차지하게 되어 D → B 트래픽은 해당 라우터에서 전부 drop. D → B의 throughput은 거의 0에 수렴하게 됨
만약 downstream(source쪽)으로 가서 그런 일이 생긴다면 upstream의 라우터와 사용한 bandwidth가 모두 낭비가 된 것. 다른 traffic이 썼을 수도 있는 자원을 낭비한 것.
⇒ source에서 dest로 여러 개의 라우터를 거쳐갈 때 upstream의 네트워크 자원이 낭비됨
- λout = goodput, receiver측에서 받는 데이터 양
λin 증가에 따라 λout이 증가하다가, 어느 시점부터 loss와 rtx가 생기며 throughput 증가X
⇒ unneeded retransmissions, upstream transmission capacity was wasted

Approaches towards congestion control

1. network assisted congestion control (L2~L3)
   : 네트워크 지원 혼잡 제어, 네트워크 안에서 혼잡 상태와 관련하여 sender에게 직접 피드백
2. end-end congestion control (L4)
   : 종단 간의 혼잡 제어, 네트워크 상황을 추측(loss를 판단 by Timer-SampleRTT 추측, 3 dup ACK) → delay(RTT)를 고려해 Timeout 조정

(1) Explicit Congestion Notification (ECN)

network assisted congestion control

• 2 bits in IP header (ECN) marked by network router → receiver TCP

(2) TCP congestion control Overview

Goal

• Network congestion이 생기지 않도록 한다 (생기면 loss 발생)
• 동시에 make use of all the available bandwidth

How?

ACK 받았을 떄 increases transmission rate (cwnd높임), loss가 생겼다고 판단되면 (1. Timeout 2. 3 dup ACK) backs off (cwnd낮춤)

⇒ TCP는 네트워크 상황이 좋다고 판단 되면 sending rate을 높여 공격적으로 네트워크 자원을 사용

TCP congestion control: details

rwnd 무시하고 cwnd 를 Window size W로 봄. → 망 상황에 따라 실시간으로 cwnd 조절

TCP의 혼잡제어 방법은 네트워크 혼잡에 따라 연결에 트래픽을 보내는 sending rate을 sender가 제한하도록 하는 것이다.

만약, TCP sender가 자신과 dest 간의 경로에 혼잡이 없음을 감지하면 sending rate을 높이고, 혼잡을 감지하면 sending rate을 줄인다.

• 연결로 트래픽을 보내는 sending rate을 제한하는 방법

cwnd 로 TCP sender가 네트워크로 트래픽을 전송할 수 있는 비율을 제한한다. ACK이 안 된 데이터 양(inflight byte)은 cwnd 와 rwnd 의 최소값을 초과하지 않는다.

LastByteSent - LastByteAcked ≤ min {cwnd, rwnd}

매 RTT의 시작 때, sender는 cwnd 바이트 만큼의 데이터를 전송할 수 있고, RTT가 끝나는 시점에 데이터에 대한 ACK을 수신한다. → 한 RTT마다 cwnd에 따라 Window size를 조정

sender의 sending rate = cwnd/RTT (바이트/초)

• TCP sender가 자신과 dest 사이의 경로에 혼잡이 존재하는지 감지 하는 방법

Timeout 또는 3 dup ACK 수신이 발생하면, TCP sender에 loss가 발생한 것. → 혼잡 존재 감지

TCP congestion control algorithm: AIMD

sender는 loss가 발생할 때까지 transmission rate(Window size)를 1 MSS 단위로 증가시키다, loss 감지 시 cwnd를 절반으로 줄인다.

TCP Slow Start (SS)

initial rate = 1 MSS (cwnd)로 시작해 (전송률: 1MSS/RTT) 한 세그먼트가 한 ACK을 받을 때마다 ACK당 1 MSS 씩 증가시킨다. (1→2→4→8→,,,) 언제까지? ssthresh에 도달할 때까지

loss가 생길 경우, ssthresh를 혼잡이 생긴 시점의 cwnd 값의 절반으로 정한다.

cwnd 값이 ssthresh 에 도달한다면 Slow Start를 종료하고 CA (혼잡회피모드)로 전환한다.

⇒ cwnd이 각 RTT당 1MSS씩 linear하게 증가한다.

if ( cwnd < ssthresh ) then
SS phase (double cwnd in every RTT)

else
CA phase (increment cwnd by 1 MSS in every RTT)

TCP: detecting, reacting to loss

TCP RENO

• Timeout으로 인한 loss ⇒ SS 시작 (추후 CA로 전환될 수 있음)

Timeout으로 인한 loss는 3 dup ACK보다 망 상황이 더 좋지 않다는 것이므로 SS를 시작

• 3 duplicate ACK이 온 loss ⇒ CA 시작

cwnd를 현재 cwnd값의 절반으로 줄인 후 1RTT당 1MSS씩 linear하게 증가시킨다.

TCP Tahoe

loss가 생길 경우, loss를 구별하지 않음 (3 dup ACK인지, Timeout인지)

Transmission round = RTTs

검은 선은 3 dup ACK으로 인해 loss가 감지된 것(loss가 생긴 시점 cwnd가 loss가 생긴 시점의 절반으로 조정 됨)

---

Quiz

(78) fast retx을 위해서 TCP sender는 duplicate ACK을 3개까지 기다려 본다. 1 혹은 2개가 아닌 3개까지 기다리는 이유는 무엇인가?

⇒

네트워크에서 drop되지는 않았으나, 늦게 도착하는 패킷 (delayed not lost packet)을 loss로 오판하여 불필요한 retx을 하는 것을 막기 위해서

(79) network congestion을 간단히 정의하시오.

⇒ sender host 로부터 receiver host 까지의 경로 중의 네트워크 라우터의 아웃풋 버퍼에서 발생하는 밀집도 상승 현상

많은 host들이 지나치게 많은 량의 데이터를 지나치게 빨리 전송하여, 네트워크를 구성하는 라우터의 output buffer의 밀집도가 놓아졌다는 의미

(80) 만일 TCP sender가 timeout 값을 조정하지 않는다는 가정하에, 네트워크 라우터의 output buffer 크기를 증가시킨다면 throughput은 어떻게 (증가 혹은 감소) 변하고 그 이유는 무엇인지 설명하시오.

⇒ timeout 값을 조정하지 않고 네트워크 라우터의 output buffer 크기를 증가시키면 Queueing delay가 증가하고, 불필요한 retransmission으로 인해 결과적으로 throughput이 감소할 수 있다.

throughout 이 감소하는데 그 이유는 TCP sender 가 delayed packet 가 loss 된 것으로 오판하고 retx을 하게 되므로 이미 TCP receiver 가 받은 packet들이 중간 라우터의 output buffer를 차지하는 비율이 점점 증가하게 되기 때문이다.

(81) 호스트 A에서 일정 기간 동안 5계층 응용 프로토콜이 전송하는 메시지 량이 100Mbit였다고 가정할 때 UDP를 사용하는 경우보다 TCP를 사용하는 경우 라우터로 실제 전송된 데이터량은 100Mbit를 초과할 수 있다. 그 이유는 무엇인가?

⇒ TCP는 loss 발생 시 retransmission을 지원하므로, 라우터로 실제 전송된 데이터는 애플리케이션 계층에서 보내준 데이터와 재전송되는 데이터를 포함한다.

TCP는 send buffer를 두고 네트워크에서 loss 발생시 retx을 하므로 실제 5계층에서 응용 프로토콜이 전송하고자 하는 데이터 보다 더 많은 량의 데이터를 네트워크로 전송하게 된다.

(82) 다음은 서술은 참인가? “TCP Sender가 네트워크로 전송한 데이터량이 증가하면 할 수록, TCP receiver의 throughput은 증가한다.”

⇒ F.

거짓, throughput 은 중복되어 전송된 bit들은 고려하지 않는다. 네트워크가 free한 경우에는 TCP sender가 전송한 만큼 receiver 측에서 throughput이 올라가나, 네트워크가 (라우터 output 버퍼가) 혼잡한 경우에는 네트워크로 전송한 데이터 중 불필요한(즉 TCP receiver 가 이미 받은) 데이터를 재전송하는 경우가 포함되어 있을 수 있기 때문에 TCP sender가 전송한 데이터량이 증가한다고 항상 throughput이 증가하지는 않는다.

(83) 3장 연습문제 P14번 풀기

Consider sending a large file from a host to another over a TCP connection that has no loss.
a. Suppose TCP uses AIMD for its congestion control without slow start. Assuming cwnd
increases by 1 MSS every time a batch of ACKs is received and assuming approximately
constant round-trip times, how long does it take for cwnd increase from 6 MSS to 12 MSS (assuming no loss events)?

⇒ 6RTT
b. What is the average throughput (in terms of MSS and RTT) for this connection up through time = 6 RTT?

⇒ (6+7+8+9+10+11)/6 = 51 MSS/6RTT = 8.5 MSS/RTT