3.3 TCP Flow Control & 3-way handshake

TCP seq. numbers, ACKs

TCP가 in-order, no-loss delivery를 제공하기 위해 보내는 msg를 byte단위로 관리하기 위한 field ⇒ byte-oriented delivery

sender의 send buffer

모두 application에서 생성되어 transport layer로 내려온 data들

bar 하나가 numbering 된 하나의 byte를 나타냄

왼쪽에서부터 초록색은 ACK을 받은 byte들,

노란색은 보낸 후 아직 ACK을 받지 못한 byte들 ⇒ inflight byte

→ inflight byte들은 NW router buffer, receiver buffer에 영향

→ window size W가 buffer의 상태에 따라 보내는 양(노란색) 조절

= congestion (NW router buffer) & flow control (receiver buffer)

sender는 receiver가 잘 받지 못 했다면 retransmit하려고 keep하고 있다가, ACK을 받으면 drop

SendBase: 아직 ACK 받지 못 한 첫번째 byte를 가리키고 있음 (노란 첫번째)

NextSequenceNumber: 다음에 붙여야 할 Sequence number (파란 첫번째)

sequence number

• byte stream “number” of first byte in segment’s data

acknowledgements

• seq # of next byte expected from other side
• cumulative ACK

how receiver handles out-of-order segments ?

data들은 separate되어 packet 단위로 전송 되기 때문에 out-of-order 될 수 있다. 순서에 맞지 않게 늦게 도착하거나 중간에 loss될 수 있다.

1-2-4 순서로 받았다면 application layer에 3을 올려줄 수 없음. 4번은 ?

drop or keep (구현하기 나름)

sequence number와 ack의 밀접한 관계

• 첫 번째 세그먼트는 클라이언트에서 서버로 송신된다. 이 세그먼트는 데이터 필드 안에 문자 'C'를 포함한다. 이 첫번째 세그먼트는 SequenceNumber 안에 42를 갖는다. 또한 클라이언트가 아직 서버로부터 어떠한 데이터도 수신하지 못했으므로, ACK 필드는 79의 임의의 최초 SequenceNumber 로 초기화 한다.
• 두 번째 세그먼트는 서버에서 클라이언트로 송신된다. 이것은 수신하는 서버에게 데이터에 대한 ACK을 제공한다. ACK 필드에 43을 넣음으로써, 서버는 클라이언트에게 바이트 42를 성공적으로 수신했고, 앞으로 바이트 43을 기다린다는 것을 말해준다. 또한 문자 'C'를 반대로 반향 되도록 한다. 그러므로 데이터 필드에 'C'의 ASCII 표현을 갖는다. 이 두 번째 세그먼트는 이 TCP연결의 서버/클라이언트 데이터 흐름의 최초 SequenceNumber 인 79를 갖는다. ACK이 세그먼트 안에서 전달 되는 것이다. (piggy-backed)
• 세 번째 세그먼트는 클라이언트에서 서버로 송신된다. 목적은 서버로부터 수신한 데이터를 ACK하는 것이다. 이 세그먼트는 빈 데이터 필드를 가진다. 즉, ACK은 어떤 클라이언트/서버 데이터와 함께 피기백 되지 않는다. 세그먼트는 ACK 필드 안에 80을 갖는다. 왜냐하면 클라이언트가 SequenceNumber 79의 바이트를 통해 바이트의 스트림을 수신했기 때문이다. 그리고 이제 80으로 시작하는 바이트를 기다린다.

data 'C'는 42번째 byte, ACK이 79이니 flag =1 인 것, 78번째 byte까지 잘 받았고 79번째 byte부터 받으면 됨

Host B는 Host A의 ACK을 받고 78까지 잘 받았다니 79번째 byte부터 보내줌

• 42번째 ACK까지 잘 받았으니 43번째 ACK을 보내주면 된다

⇒ 클라이언트/서버에 대한 ACK은 서버와 클라이언트 간에서 데이터를 운반하는 세그먼트 안에서 전달 된다 (= piggy back)

TCP round trip time, timeout

TCP는 손실된 세그먼트를 발견하기 위해 타임아웃/재전송을 이용한다.

언제까지 상대방의 ACK을 기다려야 할까? 제한 시간을 줘야 함

how to set TCP timeout value?

• if too short: premature timeout, unnecessary retransmit delayed pkt
• if too long: slow reaction to segment loss → high latency

⇒ long timeout (longer than RTT) + fast retx before timeout

how to estimate RTT?

SampleRTT: 세그먼트가 송신된 시간 (IP로 넘겨진 시간)으로부터 ACK이 도착한 시간

time from segment transmission until ACK receipt (ignore retransmissions)

SampleRTT는 어떤 시점에서 전송되었지만 현재까지 ACK이 없는 세그먼트 중 하나에 대해서만 측정되며, 재전송한 세그먼트에 대해선 계산하지 않는다.

불규칙적인 SampleRTT를 통해 RTT를 다음과 같이 추정한다.

**EstimatedRTT = (1-a)*EstimatedRTT + a*SampleRTT**

누적되며 EstimatedRTT(과거의 값)의 영향이 exponential 하게 줄어듦

→ 오래된 값일수록 영향 적어짐

• timeout interval: EstimatedRTT + "safety margin"
  • large variation in EstimatedRTT → large safety margin
• estimate SampleRTT deviation from EstimatedRTT:

---

TCP reliable data transfer

• TCP creates rdt service on top of IP’s unreliable service
  1. pipelined segments
  2. cumulative acks
  3. single retransmission timer per connection
  4. ⇒ to the oldest unacked byte =SendBase
• retransmissions triggered by: 둘 다 사용
  1. timeout events
  2. triple duplicate acks (3 dup ACK)= fast retransmission before timeout timeout이 발생하기 이전에 rtx를 결정하는 방법⇒ TCP는 timeout 값은 넉넉히 설정하고 pipelining과 cumulative ack을 이용해 timeout 전에 loss를 유추하는 이중 방법을 사용하도록 설계됨
• Sender TCP가 retransmission을 결정하는 두 가지 방법
• 어떻게 fast retransmission이 가능?cumulative acks: 앞의 ACK이 loss 되어도 그 다음 ACK만 잘 가면 ok
• pipelined segments: ACK을 받지 않은 상태에서 일련의 데이터 전송

TCP sender events:

timer로 retransmission 하는 방법

1. data received from app

• create segment with seq # ← NextSequenceNumber( seq#의 byte부터 MaxSegmentSize byte까지의 data 전송됨 )MSS: 최대 세그먼트 크기 Maximum segment Size
• → 송신 호스트에 의해 전송될 수 있는 가장 큰 프레임 길이 (MTU: Maximum Transmission Unit) 에 의해 결정
• NextSequenceNumber = NextSequenceNumber + MSS
• : 이 번호로 receiver 측에서 loss가 생겼는지 판단 (by gap)
• seq # is byte-stream number of first data byte in segment
• start timer if not already running=no inflight byte=no cracked byte
  • think of timer as for oldest unacked segment
  • expiration interval: TimeOutInterval
  • 설정한 timeout에 도달하면 곧바로 타이머가 가리키는 byte(SendBase)부터 MSS만큼 segment에 실어서 전송

2. timeout

• retransmit segment that caused timeout
• restart timer

3. ack received

ack # sent by receiver (y : SendBase 다음부터 첫번째 파란색 사이의 값)

(원래 y는 SendBase에 있었음)

• if ack acknowl edges previously unacked segments
  • update what is known to be ACKed
  • start timer if there are still unacked segments

TCP: retransmission scenarios

lost ACK scenario

SequenceNumber가 92인 byte를 보낸 후 (여태까지의 ACK 모두 받았다고 가정)

SendBase: (oldest unacked byte) 92

NextSequenceNumber: 100 (92+8byte)

ACK이 loss

SendBase를 가리키던 Timer가 expired → 다시 92번부터 전송

(receiver는 duplicated 되었으니 버릴 것)

: B로부터 A의 ACK (100)이 손실되면, 타임아웃이 일어나고, 호스트 A는 동일한 세그먼트를 B에게 재전송, 호스트 B는 재전송 세그먼트를 수신했을 때, 세그먼트가 포함한 SequenceNumber를 통해 이미 수신된 데이터라는 것을 알 수 있고, 재송신 된 바이트를 버릴 것

premature timeout

SequenceNumber가 100인 byte 보낸 후 (여태까지의 ACK 모두 받았다고 가정)

SendBase: (oldest unacked byte) 92

NextSequenceNumber: 120 (100+20byte)

Timeout expired

같은 data들이 또 전송 (receiver는 duplicated 되었으니 버릴 것)

SequenceNumber가 92인 byte를 다시 보낸 후

120인 ACK이 옴 (cumulative ACK: 정상적으로 120번까지 in-order로 받음)

: SequenceNumber 92와 100짜리 두 세그먼트 모두 호스트 B에 무사히 도착하면, B는 각각의 세그먼트에 대해 2개의 개별적인 ACK을 전송. 첫번째 ACK은 100, 두번째 ACK은 120을 가진다. 만약 호스트 A에서 첫 번째 세그먼트의 타임아웃 전에 ACK을 수신하지 못 한다면, 호스트 A는 92번 세그먼트를 재전송하고 타이머를 다시 시작한다. 새로운 타임아웃 이전에 두 번째 세그먼트에 대한 ACK이 도착하면 두 번째 세그먼트는 재전송 되지 않는다.

cumulative ACK

because of cumulative ACK, unnecessary retransmission is avoided

100인 ACK은 loss 되었지만, 120인 ACK을 받음으로써 여태까지의 data가 모두 잘 도착했다는 것을 알 수 있음 ⇒ SendBase를 120

기존의 NextSequenceNumber가 120이었음 ⇒ inflight byte가 없다는 소리

: 호스트 A가 2개의 세그먼트를 전송했을 때 첫 번째 세그먼트에 대한 ACK이 네트워크에서 분실 되었지만, 첫 번째 세그먼트의 타임아웃 전에 호스트 A가 두 번째 세그먼트에 대한 ACK (120)을 수신하면, 호스트 A는 호스트 B가 119바이트까지 모든 데이터를 수신했다는 것을 알게되므로, 두 세그먼트 중 어느 것도 재전송하지 않는다.

TCP ACK generation: at receiver

TCP 수신자의 ACK 생성 정책

TCP 수신자가 기다리는 다음 것보다 더 큰 SequenceNumber를 가진 세그먼트를 받았을 때, TCP 수신자는 gap(손실된 세그먼트)를 찾아낸다. TCP는 부정 확인 응답은 사용하지 않으므로, 수신자는 송신자에게 부정 확인 응답은 보낼 수 없으나, 수신자는 마지막으로 수신된 바이트를 갖는 데이터에 대해 다시 ACK (중복 ACK을 생성함)을 생성해 보낸다.

만약 sender가 많은 양의 segment를 연속적으로 보내는 경우 하나의 세그먼트가 손실된다면, TCP는 연속적인 중복 ACK을 보낼 수 있다. 만약 TCP sender가 같은 데이터에 대해 3개의 중복 ACK을 수신한다면, 이것은 ACK된 세그먼트의 다음 3개의 세그먼트들이 분실 되었음을 의미한다.

3개의 중복 ACK을 수신하는 경우 TCP는 세그먼트의 타이머가 만료되기 이전에 손실 세그먼트를 빠르게 재전송하는 fast retransmit을 한다.

case 1.

이벤트) 기다리는 SequenceNumber를 가진 세그먼트의 도착, 모든 데이터들은 이미 확인 응답 됨

receiver) 또 다른 세그먼트의 도착을 위해 500ms까지 기다린다. 만약 다음 세그먼트가 이 기간에 도착하지 않으면, ACK을 보낸다.

case 2.

이벤트) 기다리는 SequenceNumber를 가진 세그먼트의 도착. ACK 전송을 기다리는 다른 하나의 순서에 맞는 세그먼트

receiver) 즉시 2개의 순서가 맞는 세그먼트들을 ACK하기 위해, 하나의 누적된 ACK을 보낸다.

case 3.

이벤트) 기다리는 것보다 높은 SequenceNumber를 가진 순서가 틀린 세그먼트의 도착 → GAP이 발견됨

receiver) 즉시 SequenceNumber가 다음의 기다리는 바이트 (GAP의 최솟값)를 나타내는 중복 ACK을 보낸다.

case 4.

이벤트) 수신 데이터에서 GAP을 부분적으로 또는 모두 채우는 세그먼트의 도착.

receiver) 즉시 ACK. 단, 그 세그먼트가 GAP의 최솟값에서 시작한다고 가정

TCP fast retransmit이 가능한 이유

1. long timeout
2. TCP pipelining (sliding window)
3. in-order delivery
4. cumulative ACK

⇒ TCP sender는 3 ACKs for same data(3 duplicated ACK)를 받으면 unacked segment 중 최소 SequenceNumber를 가진 세그먼트를 재전송 한다.

왜 3개까지 기다릴까?

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

---

TCP flow control

flow control: receiver controls sender, so sender won’t overflow receiver’s buffer by transmitting too much, too fast

receiver의 send buffer 오버플로우를 방지 하기 위한 flow control

애플리케이션이 버퍼에서 데이터를 읽어 가는 속도와 sender가 전송하는 속도를 같게 한다. (애플리케이션이 읽는 속도보다 sender가 전송하는 속도가 더 큰 경우 receiver의 buffer에서 오버플로우 발생 가능)

⇒ flow control: 버퍼 잔여량 알려줘서 sender의 sending rate을 control (rwnd 필드에 버퍼의 잔여량을 넣어줌)

lastByteRead lastByteRcvd 의 차이로 가용한 버퍼 사이즈를 알 수 있음 → rwnd 필드에 → sending rate (inflight) 조절

3-way handshake

each knowing the other willing