[ch3] 5-7. connection-oriented transport: TCP

TCP: Overview

• connection-oriented: message 교환 전에 송신자/수신자 사이에 연결 필요
• point-to-point: 한 연결 당, 한 명의 송신자와 수신자
• full duplex data: 한 연결에 양방향 통신 가능
• flow controlled: 송신자는 수신자가 메시지를 받을 수 없는 상태면 메시지를 보내지 않음
• pipelined: congestion control / flow control은 window size를 dynamic하게 설정할 수 있음
• reliable, in-order byte stream
  • reliable: 메시지 전송은 아예 성공하거나 아예 실패하거나 둘 중 하나
  • in-order: 송신자가 보낸 순서대로 메시지를 받음
  • byte stream
    • 메시지(data stream)을 받은 후 segment를 만들어서 데이터를 전송함
    • segment의 크기는 MSS로 제한됨
      • MSS: Maximum Segment Size

 

Many flavors of TCP

• 여러 종류의 TCP가 있는데, 대부분 congestion control algorithm에서 차이가 존재함
• 이 수업에서는 TCP (new) Reno를 다룸

 

TCP segment structure

• TCP header
  • src / dst port #
  • seq num: segment의 첫 번째 바이트의 byte stream number
  • ack num
    • 상대방으로부터 다음에 받을 것이라고 예상되는 sequence number
    • 누적 ACK 사용
  • header length
  • flag: U, A, P, R, S, F
    • A: ack # valid
    • RST, SYN, FIN: connection 생성에 사용됨 
  • receive window
    • 수신자가 받을 수 있는 bytes 수
  • checksum
  • urg data pointer
• TCP Payload 
  • application data (variable length)

 

TCP sequence numbers, ACK numbers

• full-duplex: packet은 seq #, ack #를 동시에 가지기 때문에 양방향 통신에 이용할 수 있음
• seq #는 connection 설정 단계에서 랜덤으로 설정되고, 송신자/수신자가 서로 이 정보를 교환함
  
  • 매 연결마다 같은 seq #를 사용해서 보내면 receiver가 혼동할 수 있음
• 송신자의 seq# space
  • window size = N
  • N = (전송 중이지만 ACK를 받지 않은 packet) + (전송 가능하지만 아직 보내지 않은 packet) 
  • SendBase: 아직 ACK를 받지 못한 첫번째 byte
• 수신자는 out-of-order segments를 어떻게 처리할까?
  
  • TCP에선 결정된 것이 없음. 프로그래머가 결정

 

TCP round trip time, timeout

• timeout 까지 ACK가 오지 않으면 packet loss가 일어났다고 생각하고, packet을 재전송함
• TCP가 Timeout value를 설정하는 방법
  • RTT보다 길어야 함. RTT는 queueing delay 때문에 고정된 값이 아님. timeout value를 너무 짧게 설정하면 재전송이 많이 일어나 네트워크를 혼잡하게 만들 수 있음. 그렇다고 또 너무 길면 packet loss에 느리게 대응하기 때문에 throughput이 저조해짐. 둘 다 안 좋음.
• RTT를 추정하는 방법 
  • SampleRTT
    • segment가 전송되고 ACK를 받을 때까지 측정된 시간
    • 재전송은 무시함, 하나의 패킷에 대한 RTT 당 하나의 SampleRTT 측정
    • Sample RTT는 다양하기 때문에 일반화(smoother)한 버전이 필요함
  • Exponential Weighted Moving Average (EWMA)
    • EstimatedRTT = (1-alpha) * EstimatedRTT + alpha * SampleRTT
    • 여기서 EsitmatedRTT는 과거에 측정한 값이고, SampleRTT가 가장 최근에 측정한 값임
    • 위 식을 보면 과거 측정값의 영향이 exponentially하게 감소하는 것을 볼 수 있음
    • 보통 alpha의 값으로 0.125를 사용한다고 함
• Timeout Interval
  • EstimatedRTT + "safety margin"
  • EstimatedRTT의 변동이 클수록 더 큰 safety margin이 필요함
• DevRTT
  • EstimatedRTT로부터 SampleRTT의 편차를 추정
  • DevRTT = (1-Beta) * DevRTT + Beta * |SampleRTT - EstimatedRTT|
  • Beta는 보통 0.25를 사용
• Timeout Interval
  • EstimatedRTT + 4 * DevRTT

 

TCP - reliable data transfer

• IP는 unreliable / best effort 서비스임. queue overflow, our-of-order 등 전송 중에 문제가 생길 수 있음.
• TCP는 IP 위의 계층으로, reliable data transfer를 지원함.
  • Pipelined segments, 누적 ACK, 하나의 재전송 타이머를 사용
  • timeout, 누적 ACK가 발생하면 재전송이 일어남
• 간단한 이해를 위해 누적 ACK와 flow/congestion control를 무시하고 한 송신자가 한 수신자에게 메시지를 전달한다고 가정해보자.
  • 송신자는 상위 계층으로 부터 데이터를 받는다. 그리고 segment를 만들고 seq#를 설정한다. seq #는 segment의 첫 번째 data byte의 number이다. 그리고 timer가 돌아가고 있지 않으면 timer를 시작한다. 타이머는 전송은 했지만 ack를 받지 않은 가장 오래된 segment에 대한 타이머로 생각하면 된다. timeout value는 위에서 구한 TimeOutInterval로 설정한다.
  • Timeout 발생: timeout이 발생된 segment를 재전송하고 timeout value를 두 배로 늘려서 timer를 다시 시작한다. packet loss는 보통 network가 혼잡할 때 일어난다. 이전과 같이 단순하게 재전송하면 또 timeout이 생길 것이고, 재전송으로 이어져 혼잡한 네트워크를 더 혼잡하게 만들게 된다.
  • ACK received: ACK를 아직 받지 않은 segment에 대한 ACK인 경우에는, ACK를 받았다고 sequence window를 업데이트하고, 아직 ACK를 받지 않은 segment가 있다면 타이머를 시작한다. 만약 이미 받은 ACK를 또 받은 경우는 재전송을 해야하는 상황이다.

 

TCP ACK generation

Event at receiver	TCP receiver action
예상했던 seq #의 segment를 올바른 순서로 받음. 예상했던 seq #까지의 모든 데이터들이 이미 ACK가 된 상태	delayed ACK 너무 많은 ACK를 보내는 것도 자원 낭비라고 생각해서 다음 segment가 올 때까지 500ms를 기다림. 만약 다음 segment가 오지 않는다면 ACK 전송
예상했던 seq #의 segment를 받았지만, ACK를 받지 못한 segment가 하나 있는 상태	멀쩡하게 잘 받은 것까지 나타낼 수 있는 누적 ACK를 즉시 보냄
예상했던 seq #보다 큰 segment를 받아 gap이 생긴 상태 ex) 1 2 x x 5	즉시 누적 ACK를 보냄 ex) ACK3 전송
gap을 채우는 segment가 도착했다!	즉시 누적 ACK를 보냄

 

TCP fast retransmit

• 문제: timeout이 종종 커서 재전송하기전에 오랜 시간을 기다리는 경우가 존재함
• 아이디어: duplicate ack를 통해 packet loss를 감지해보자
  •  segment가 중간에 loss되면, duplicate ACK가 생김
  • 송신자가 같은 ACK를 3번 받으면, packet loss가 발생했다고 생각하고, ACK를 받지 않은 segment 중 가장 오래된 segment 재전송하자

 

TCP flow control

• 송신자가 메시지를 너무 빠르게 보내면 buffer overflow가 생겨 packet이 drop될 수 있음
• 수신자는 수신자의 버퍼가 넘치지 않게끔 송신자를 제어함
  • 수신자는 송신자에게 보내는 세그먼트의 헤더에 'rwnd'를 포함시켜 'free buffer space'를 알림
  • rwnd는 버퍼(RcvBuffer)에 얼마나 여유 공간이 남아있는지 알려줌
  • 버퍼의 크기는 socket option을 통해 설정 가능함. 보통은 4096 bytes이고, OS가 버퍼 사이즈를 자동으로 증ㄱ마시킬 수 있음
  • 송신자는 수신자의 rwnd 값으로 unacked data의 양을 제한함으로써 수신자 버퍼에 overflow가 생기는 것을 방지할 수 있음

 

TCP connection management

• 송신자와 수신자는 통신 전에 connection establishment 단계를 거침. 이 단계에서 첫 seq #를 주고 받음
  • 2-way handshake: 송신자는 수신자가 보낸 메세지를 받았는지 확인할 수 없음
  • 3-way handshake 사용
• open a connection

Client	Server
초기 seq #인 x 를 결정하고, Server에 TCP SYN msg를 보냄 ex) SYNbit = 1, Seq#=x ------------------------------------------------>
	초기 seq #인 y를 결정하고, Client에 TCP SYNACK msg를 보냄. ex) <------------ SYNbit = 1, Seq# = y, ACKbit=1, ACKnum=x+1
SYNACK(x)를 받은 것은 Server가 실행 중이라는 것을 의미함. (establishment!) SYNACK에 대한 ACK를 보냄. 이 세그먼트는 clinet-to-server data를 포함할 수 있음 ex) ACKbit=1, ACKnum=y+1 ------------------------------------------>
	ACK(y)를 받고, client가 실행 중이라는 것을 확정지음 (establishment!)

• close a connection

Client	Server
clientSocket.close() 메세지를 이제 안보내지만, 받을 수는 있음 ex) FINbit=1, seq=x ---------------------------------------------------->
	메세지를 아직 보낼 수 있음 ex) <------- ACKbit=1, ACKnum=x+1
서버가 닫히는 것을 기다림
...
	서버가 이제 socket을 닫겠다고 client에게 알려줌 이제 서버는 데이터를 안보낼꺼다! ex) <-------- FINbit=1, seq=y
FIN msg에 대한 ACK를 보냄 segment의 lifetime의 두 배 동안 기다리고 닫음. FIN msg에 대한 ACK 메세지가 제대로 갔는지 모르기 때문임 ex) ACKbit=1, ACKnum=y+1 --------------------------------------->
	ACK msg가 도착하면 닫음

 

TCP congestion control

• Congestion: 너무 많은 소스가 네트워크가 다루기에 너무 빠르게 많은 데이터를 보내서 생김
• flow control과는 다름
  
  • flow control은 송신자가 수신자가 감당할 수 없을 만큼 빠르게 데이터를 보내지 않도록 제어하는 것이고, congestion control은 송신자들이 네트워크가 감당할 수 없을만큼 많은 데이터를 빠르게 보내지 않도록 제어하는 것
• 증상으로는 buffer overflow로 인한 packet loss와, buffer에서의 queueing delay가 있음
• congestion의 원인과 cost
  • Ideal case
    • 가정1. sender가 router의 buffer에 free space가 얼마나 있는지 알고 있음
    • 가정2. packet loss가 생긴 것을 sender가 안다. packet이 loss 되었을 때만 재전송을 함
  • Realistic case (cause)
    
    • 송신자는 packet loss를 감지하기 위해 timeout을 사용함. timeout이 일찍 일어나면, 수신자가 패킷을 잘 받았어도 다시 보내기 때문에 duplicate들이 발생하게 됨. 
  • cost: 불필요한 재전송. link가 같은 pkt을 여러번 옮기는 상황이 존재함
    • 문제가 없던 상위 link의 bandwidth에 낭비가 발생
    • ACK/timeout을 기다리는데 시간 낭비 발생
• 그래서 congestion control 어케함?
  
  • congestion이 있을 때는 전송 속도를 줄이고, congestion이 없으면 전송 속도를 올린다
  • 1. 전송 속도를 어떻게 제어할까?
  • 2. congestion control를 어떻게 감지할까?
  • 3. 전송 속도를 언제, 얼마나 높이고, 낮추어야 하는가?
• In TCP Reno,
  • Key states & mechanisms 
    • slow start
    • congestion control - "AIMD: Additive Increase Multiplicative Decrease"
    • fast recovery
  • Key parameters
    • congestion window: cwnd
    • slow-start threshold: ssthresh
    • MSS, RTT
  • Key events
    • ACK received: good
    • timeout: very bad
    • 3 duplicate ACK received: bad

 

TCP Congestion Window

• (가장 최근에 보낸 byte - 가장 최근에 받은 byte) < cwnd
• cwnd는 dynamic함
• TCP 전송률 = cwnd/RTT bytes/sec

 

TCP Slow Start

• slowstart: 연결을 시작할 때, 첫번째 loss가 생길 때 까지 전송 속도를 exponential하게 증가시킴
  • 초기 cwnd = 1 MSS
  • 매 RTT 마다, 즉 ACK를 받을 때마다 2배씩 증가시킴
• timeout: slow start와 유사하게 돌아옴
  • 네트워크가 ACK도 못보낼 최악의 상황이라는거임
  • cwnd를 1로 설정함
  • ssthresh에 도달 할 때까지 window를 exponential하게 늘림
• 3 dup ack: congestion avoidance 단계로 감
  • 네트워크에 여유가 있는 상태임
  • cwnd를 절반으로 줄이고, linear하게 증가시킴

 

TCP congestion avoidance: AIMD

• additive increase: loss가 발생할 때까지 매 RTT마다 cwnd를 1 MSS씩 증가시킴
• multiplicative decrease: loss 발생 후 cwnd를 절반으로 줄임 (ssthresh가 cwnd의 1/2로 설정됨)

 

TCP throughput

• TCP의 평균 throughput?
  • slow start, +3 무시
  • W: loss가 일어나는 곳의 window size
    • 평균 window size는 3/4W
    • 평균 throughput: 3/4 * W/RTT bytes/sec

 

TCP Fairness

• bandwidth가 R인 bottleneck를 공유하는 K개의 TCP sessions은 각각 평균 속도가 R/K이어야 함
• 왜?
  •