1. Transport-layer services
2. Multiplexing & demultiplexing
3. Connectionless transport: UDP
4. Principles of reliable data transfer
5. Connection-oriented transport: TCP
   5-1. segment structure
   5-2. reliable data transfer
   5-3. flow control
   5-4. connection management
6. Principles of congestion control
7. TCP congestion control
8. Evolution of transport layer funcitonality

Connection-oriented transport: TCP

TCP overview

• point to point
  • 단일 sender, 단일 receiver
• reliable, in-order byte stream
  • 메세지라는 경계 X. byte단위로 numbering.
• full duplex data
  • 같은 connection으로 양방향으로 통신 가능.
  • MSS : Maximum segment size
    • MTU (Maximum transmit unit) = IP header + TCP header + payload 으로 구성
    • IP header는 주로 20 ~ 60 byte, TCP header는 주로 20 ~ 40 byte
    • MSS = MTU - (IP header + TCP header)
• cumulative ACKs
• pipelining
  • TCP congestion과 flow control에 의해 윈도우 크기가 설정.
• connection-oriented
  • 데이터를 교환하기 전에 handshaking (exchange of control message)으로 sender, receiver state를 초기화한다.
• flow controlled
  • sender가 receiver를 압도하지 않게 한다.

TCP segment structure

TCP segment Header

• source port # (16 bits)
• dest port # (16 bits)
• sequence number (16 bits) : 바이트 단위로 구분되어 데이터가 bytestream내 몇 번째인지 지칭하는 번호.
• acknowledgement number (16 bits) : 다음 도착할 것으로 기대되는 바이트의 sequence number.
• header length (data ofsset, 4 bits) : TCP header 길이를 32bit 워드 단위로 표시
• flag bits (6 bits) : TCP segment 전달과 관련되어 connection을 관리하고 제어하는 flag.
  • SYN : Synchronize. 연결 설정 요청
  • ACK : Acknowledge. 확인 응답
  • FIN : Finish. 연결 종료 요청
  • PSH : Push. 즉시 전달 요청
  • URG : Urgent. 긴급 데이터 표시
  • RST : Reset. 연결 초기화
• Congestion flag (2 bits)
  • ECE : ECN Echo. (Explicit Congestion Notication)
  • CWR : Congestion Window Reduced.
• receive window (16 bits) : flow control을 위해 receiver가 수신할 것으로 기대되는 바이트 수를 표시
• checksum (16 bits)
• urgent pointer (16 bits)
• option (최대 40bits)
  TCP segment Body

위 그림에서 처럼 syn, fin, sequence number, acknowledge number, window size 등이 활용되고 있음을 알 수 있다.

TCP sequence numbers, ACKs

TCP는 신뢰성 있는 데이터 전송을 보장하기 위해 sequence number를 사용해 현재 segment의 data의 첫 byte가 byte stream에서 몇 번째에 위치하고 있는지 표시한다.

Acknowledgement도 마찬가지로 신뢰성을 보장하기 위해 sender가 보낸 segment가 receiver에서 제대로 받았음을 확인하기 위해 존재하며, receiver에서 다음에 받아야할 데이터의 sequence number를 뜻한다. TCP는 cumulative ACK 방식을 사용하여 receiver에서 ACK 번호를 보낼 때 해당 번호 이전에 존재하는 모든 데이터가 정상 수신되었음을 보장해준다.

Sender와 receiver는 각각 buffer를 가지고 있다. Sender는 buffer에 in flight 중인 segment들을 저장하고 혹시 retransmit이 필요하면 꺼내서 사용한다. Receiver는 buffer에 수신한 segment들을 저장하고 in-order가 완성되면 내보낸다.

Q. How receiver handles out-of-order segments?
A. TCP spec doesn't say. Up to implementor. (Discard or buffering)

• User types C -> seq=42 ACK=79 data='C'
  • A가 타이핑한 C는 42번째 수, 앞으로 B로부터 79번째 수를 받아야함.
• host ACKs receipt of 'C', echoes back 'C' -> seq=79 ACK=43 data='C'
  • B가 C를 정상 수신했고, 79번째 수를 보내며 43번째 수를 받아야함.

이처럼 receiver의 ack은 sender의 seq + 1의 값이고, sender의 ack은 receiver의 seq값이다.

TCP round trip time, timeout

Q. How to set TCP timeout value?

• TCP timeout은 RTT보다 길어야 하지만, RTT라는 값 자체가 일정하지 않기에 어려움이 있다.
• 만약 너무 짧게 timeout을 설정할 경우, premature timeout이 발생하며 불필요하게 retransmission들을 수행해야 한다.
• 그렇다고 너무 길게 timeout을 설정할 경우 segment loss에 대해 빠르게 대응할 수 없게 된다.

Q. How to estimate RTT?

• SampleRTT : segment transmission부터 ACK을 받을 때까지 측정된 시간.
  • 이때, retransmission은 무시한다.
• SampleRTT 값은 매번 바뀌기 때문에, 더 부드럽게 추정하기 위해 여러 번의 최근 측정 값들의 평균을 구해야 한다.
• 또한, 자체 값에도 오류가 있을 수 있어 margin을 더해준다.
  • 이 margin은 underline network가 불안정할수록 커진다.

Bonus : RTT measurement

한 번에 하나의 segment만 주고받을 수도 있고, 여러 segment를 pipelining을 통해 주고받을 수도 있다. 그러나 이런 상황에 관계 없이 timer가 1개 뿐이기에 한 번에 RTT를 하나씩만 측정이 가능하다.

그래서, 두 번째 예시의 경우 1번 seg 전송 때 부터 시작된 timer가 2번까지 ack이 되고 나서 끝이나고, 두 번째 4번째 seg 전송 때 부터 시작된 timer가 3번째 ack이 들어오자마자 끝이난다. 즉, pipelining으로 인해 값 간의 격차가 커진다.

그래서 sampleRTT를 기록하면 굉장히 뒤죽박죽인 값이 나오게 된다. 이를 완화시키고자 EstimatedRTT를 도입해 부드럽게 만든 것을 볼 수 있다.

EstimatedRTT = (1 - $\alpha$) X EstimatedRTT + $\alpha$ X SampleRTT

• Exponential Weighted Moving Average (EWMA) 알고리즘을 적용한 것.

  • 최근의 RTT 측정값에 더 많은 가중치를 부여하고, 오래된 값에 덜 가중치를 부여해 계산하는 원리
  • typical value : $\alpha$ = 0.125

• timeout interval은 EstimatedRTT에 safety margin을 더한 개념이다.

  • ERTT에서 vairation이 클수록 더 큰 safety margin을 필요로 한다.
  • 그래서 margin을 deviation 값으로 구한다.

TimeoutInterval = EstimatedRTT + 4 X DevRTT

• DevRTT도 EstimatedRTT로 부터 얻은 SampleRTT deviation에 EWMA 알고리즘을 적용한 것이다.
  • typical value : $\Beta$ = 0.25

DevRTT = (1 - $\Beta$) X DevRTT + $\Beta$ X |SampleRTT - EstimatedRTT|

TCP Sender

• Event : data received from application
  • Segment를 sequence number를 이용해 만든다.
  • Sequence number는 segment 상의 첫 data byte가 byte stream 내에서 어디에 존재하는지 알려준다.
  • 만약 실행되고 있지 않다면, retransmission을 파악하기 위해 timer를 시작한다.
    • timer는 가장 오래된 unACKed segment를 위해 필요하다.
    • expiration interval: TimeOutInterval
• Event : timeout
  • timeout을 일으키게 만든 segment를 retransmit
  • timer 재시작
• Event : ACK received
  • 수신한 ACK은 처음 받은 것일 수도, duplicate일수도 있다.
  • 만약 ACK이 이전의 unACKed segment들을 acknowledge하게 된다면,
    • ACK된 것들 목록을 업데이트하고
    • 만약 남아있는 unACKed segment가 있다면 timer를 시작한다.

Bonus : Exponential backoff

Exponential backoff는 congestion control 매커니즘으로, congestion을 줄이고 network congestion collapse를 막기 위해 사용된다.

라우터나 스위치와 같은 네트워크 장치가 전송할 패킷을 처리할 속도보다 빨리 패킷을 받으면 혼잡해질 수 있습니다. 혼잡 붕괴를 방지하기 위해 장치는 패킷을 삭제하고 송신자에게 전송 속도를 줄이도록 신호를 보낼 것입니다. 이에 따라 송신자는 전송 속도를 줄이고 전송한 각 패킷에 대한 확인(ACK)을 수신 대기합니다.

송신자가 패킷에 대한 ACK를 수신하지 못하면 혼잡 때문에 패킷이 손실되었다고 가정하고 일정 시간 동안 기다린 후 패킷을 재전송합니다. 다시 전송한 패킷이 손실된 경우, 송신자는 패킷을 다시 전송하기 전에 대기 시간을 더 늘립니다. 이 대기 시간을 "백오프 시간"이라고 합니다.

지수 백오프는 패킷이 손실될 때마다 백오프 시간을 지수적으로 증가시켜 가면서 작동합니다. 예를 들어, 송신자는 1초의 백오프 시간으로 시작하고 패킷이 손실되면 백오프 시간을 2초, 4초, 8초 등으로 지수적으로 증가시킵니다. 이 과정을 반복하여 패킷이 성공적으로 전송될 때까지 계속됩니다.

이러한 메커니즘은 네트워크 혼잡이 감지될 때 패킷 전송 속도를 줄여 혼잡을 예방하는 데 도움이 됩니다. 백오프 시간을 지수적으로 증가시킴으로써 제어된 방식으로 네트워크 혼잡 붕괴를 방지하는 데도 도움이 됩니다.

TCP Receiver : ACK generation

• 첫 번째는 In-Sequence Segment Arrival 이벤트.

  • 기대하는 sequence number와 일치하는 segment를 수신한 경우. Acknowledgement number를 설정해함.
  • 그러나, 이전에 수신한 segment들에 대한 ack가 이미 전송되었으므로, delayed ACK을 수행한다.
  • Delayed ACK은 500ms 시간 동안 추가적인 segment를 수신하는지 확인하고, 수신되지 않으면 이전에 처리한 segment에 대해 ack를 전송한다.
  • 이 방법을 통해 가능한 여러 segment를 수신한 후 한 번에 ACK를 전송하기에 TCP traffic을 줄일 수 있다.

• 두 번째도 In-Sequence Segment Arrival 이벤트.

  • 이번엔 기대하는 seq #와 일치하는 segment를 수신하였으나, 또 다른 in-order segment의 ACK이 보류되고 있는 상태이다.
  • 그래서 하나의 cumulative ACK을 전송해서 두 개의 in-sequence segement를 모두 acking하게 된다.

• 세 번째는 Out-of-Order Segment Arrival 이벤트.

  • 이번엔 기대하는 seq #보다 높은 seq #를 가진 out-of-order segment가 도착하면서 이전에 수신한 segment와 gap이 발생하였다는 것이다.
  • 그래서 receiver는 duplicate ACK을 전송하며 다음에 기대하는 seq #가 무엇인지 알려준다.
  • 이를 통해 sender가 receiver가 어떤 데이터가 필요로 한지를 알게 된다.

• 네 번째도 Out-of-Order Segment Arrival 이벤트.

  • 이는 out-of-order segment로 인해gap이 발생해 있는 상황에서, 이 gap을 채워줄 수 있는 segment를 수신한 것이다.
  • 만약 도착한 segment가 gap의 낮은 부분에서 시작한다면, receiver는 바로 ACK을 전송해 gap을 채워준다.
  • 그러나 만약 gap의 높은 부분에서 시작한다면, 3번째 경우처럼 duplicate ACK을 전송해 다음에 기대하는 sequence number를 알려줘야 한다.

+) RFC 문서 내용
Specifically, an ACK should be generated for at least every second full-sized segment, and must be generated within 500ms of the arrival of the first unacknowledged packet.

TCP 송신자가 full-sized segment를 전송할 때마다 적어도 두 번째 전송된 Segment마다 ACK를 보내야 한다는 의미입니다. 이는 TCP 송신자가 데이터 전송의 효율성을 높이기 위해 가능한 많은 데이터를 전송할 수 있도록 하기 위한 조치입니다.
TCP 송신자가 ACK를 보내지 않은 첫 번째 패킷이 도착한 후 500ms 이내에 ACK를 보내야 한다는 것을 의미합니다. 이는 TCP 통신에서 패킷 손실을 탐지하고 재전송을 수행하기 위한 Timeout과 관련된 사항입니다. 만약 Timeout이 발생하면, 송신자는 재전송을 시작하여 데이터 전송의 완료를 보장합니다. 이러한 방식으로 TCP는 안정적이고 신뢰성 높은 데이터 전송을 지원합니다.

TCP : retransmission scenarios

• lost ACK scenario
  • A가 segment를 보낸 후, B가 ACK을 보내다가 lost되었다.
  • A가 timeout이 되며 해당 segment를 재전송하였다.
• premature timeout
  • A가 두 개의 segment를 보낸 후 B가 모두 ACK을 보냈는데, 도착하기 전에 A에서 timeout이 발생하였다.
  • A는 첫 segment부터 다시 retransmit하는데, 이미 ack되어 있기 때문에 cumulative ACK을 보낸다.
• cumulative ACK covers for earlier lost ACK
  • A가 두 개의 segment를 보냈는데, 첫 번째 segment가 ACK되는 도중에 lost되고 두 번째만 전달되었다.
  • 이때, 다시 retransmission 없이 120 ACK이 100부분도 커버하기 때문에 정상 수신되었음을 확인하고 다음으로 넘어간다.

TCP fast retransmit

만약 sender가 같은 데이터에 대해 3개의 ACK을 추가적으로 수신하면 (three duplicate ACKs), unACKed된 segment들 중에 가장 작은 seq#를 가지는 것을 resend한다. 마치 해당 segment를 lost된 것처럼 처리해서 timeout이 발생할때까지 기다리지 않게 한다. (이 방식이 fast retransmit)

이 그림에서처럼 도중에 2번째 segment가 lost되며, ACK 100이 수신된 후 추가로 3개가 더 들어왔다. A 입장에선 timeout이 아직 되진 않았지만, fast retransmit에 의해 2번 segment가 lost라고 추측해 retransmit한다.

TCP flow control

Application은 TCP socket buffer에서 데이터를 제거하고, network layer는 IP datagram payload를 전달한다. 만약 네트워크 레이어가 데이터를 전달하는 속도가 어플리케이션에서 빼가는 속도보다 빠르면 buffer overflow가 발생하게 된다.

이를 방지 하기 위해 TCP segment의 header에 포함된 receive window 정보를 이용해 receiver가 수용가능한 byte 수를 파악해 flow control을 수행하게 된다. Receiver가 sender를 control하여 sender가 너무 많이 전송해서 receiver의 buffer를 overflow하게 되지 않도록 방지한다.

• TCP header에 있는 rwnd field를 이용해 receiver의 free buffer space를 알린다.
  • RcvBuffer 크기는 socket의 옵션에 의해 결정된다. (디폴트 4096 bytes)
  • 많은 os는 RcvBuffer를 자동으로 최적화한다.
• sender는 rwnd에 따라 in-flight 중인 unACKed segment 수를 조절한다.
• 이를 통해 receive buffer가 voerflow하지 않음을 보장한다.

+) Q. Window size는 주로 64K, 어떨 때는 128K도 가진다. 근데 receive window는 16bit밖에 안되는데 이게 어떻게 가능할까?
A. Option field에는 window scale factor가 존재하며, 이를 multiply하여 표현 가능 범위 이상의 크기를 가질 수 있게 된 것.

TCP connection management

TCP는 데이터를 교환하기 전에 sender와 receiver 사이에 connection을 만드는 "handshake" 과정이 존재한다. 이때 서로가 connection을 만들기를 원해야 하며, 시작하는 sequence #와 같은 connection parameter에 합의를 봐야 한다.

+) HW 2 부분을 통해 TCP connection 과정에서 header 파악 부분 연습.

+) 합의가 있다는 부분에서 알 수 있듯이, sender와 receiver는 저마다 sequence number를 가지고 있다.

TCP 3-way handshake

3-way handshake는 3번의 communicate로 connection이 setup된다는 것.

먼저, server에서 socket을 만들고 client로부터 connection request를 오기를 listen하며 기다린다 (LISTEN).

다음, client에서 socket을 만들며(LISTEN), 서버의 주소와 포트를 입력해 connect를 시도한다. (SYNSENT) 이때, synbit=1 표시로 synchronization 과정임을 알리고, seq #도 알린다.

이제 server에서 해당 request를 받으며 (SYN RCVD) 자신이 사용할 seq #도 정하고, SYN과 ACK 표시로 성공적으로 수신했음을 알린다.

Client는 해당 response를 받아 서버의 존재를 확인하고, SYNACK를 정상적으로 받았음을 알리는 ACK을 보낸다.(ESTAB)

마지막으로 server도 해당 ACK을 받아 클라이언트의 존재를 확인하고 connection을 종료한다. (ESTAB)

Closing a TCP connection

• Client와 server는 각각 자신의 connection 부분을 닫을 수 있다.
  • TCP segment를 FIN bit=1과 함께 보내면 된다.
  • 이를 Active close라고 하며, 상대방에게 "더 이상 데이터를 보내지 않을 것이며, 내가 받은 모든 데이터를 이미 처리했다는 것을 알린다"는 의미를 가진다.
• FIN을 수신할 경우 ACK으로 반응하며,
  • 이는 "나도 더 이상 데이터를 보내지 않을 것이며, 네가 보낸 모든 데이터를 받았다는 것을 확인했다"는 것을 의미
  • FIN을 받으면 상대 측에선 ACK을 보내며 동시에 FIN도 보낼 수 있다.
  • 상대방에서도 더 이상 보낼 데이터가 없다면, 마찬가지로 "FIN" 세그먼트를 보내고, 이를 받은 측에서는 "ACK" 세그먼트를 보내며 연결을 종료. 이를 "Passive close"라고 한다.
  • 이를 통해 두 호스트가 동시에 FIN을 교환해 종료할 수 있게 되며 불필요한 대기시간을 줄인다.