지난 시간 배운 내용

***sequence number 와 acknowledgement number 가 중요!***

TCP 세그먼트 헤더에서 reliable data transfer을 위해 가장 중요한 필드 두 가지는 sequence number 와 acknowledgement number.

TCP는 full duplex (양 쪽의 end host가 동시에 보내면서 받을 수 있음.)

어쩔 땐 내가 sender고 receiver. sender 입장에선 sender buffer를 가져 잃어버리면 다시 retransmission, receiver 입장에선 응용이 읽는 속도를 몰라 hold 해줘야 하므로 receiver buffer를 가짐 ⇒ 모든 endbuffer를 두 개 가짐

둘다 사용해서 full duplex(양쪽에서 보내고 받는 걸-bidirection 동시에) 가능

sequence number : 세그먼트에 있는 첫번째 byte의 번호

보낼 때 사용. 첫번째 보내는 byte에 numbering된 숫자가 몇 번이야.

acknowledgement number : sender로부터 기대하는 다음 바이트의 SequenceNumber

piggy back 하는 상황이라고 가정하면 전에 받았던 data에 대한 ACK을 줌. 상대방이 잘 받은 데이터의 다음 데이터 번호를 줌. ⇒ TCP는 cumulative ACK & in-order delivery이기 때문에 다음 거를 가리 키는게 acknowledgement number 이고, 받을 시 flag=1 일 때만 읽음

acknowledgement number

receiver가 write하는 field. 받아서 application layer에 올려줘야 하는 다음 byte #

: Next byte # that it wants to receive for in-order delivery

Ex. 호스트 A가 호스트 B로부터 0~535 바이트를 포함하는 세그먼트와 900~1000 바이트를 포함하는 또 다른 세그먼트를 수신할 경우, B에 대한 A의 ACK 번호는 536을 가진다. TCP는 스트림에서 첫 번째 잃어버린 바이트까지의 바이트들까지만 확인 응답 ⇒ cumulative ack

순서가 틀리게 도착한 세그먼트(900~1000)는 어떻게 하는가?

TCP RFC는 여기에 어떤 규칙도 부여하지 않았고, 이는 개발자의 몫

(1) 수신자가 순서가 틀린 세그먼트를 즉시 버리거나 (2) 보유하고, 빈 공간에 잃어버린 데이터를 채우기 위해 기다린다.

---

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

     ⇒ to the oldest unacked byte =SendBase

• retransmissions triggered by: 둘 다 사용

  Sender TCP가 retransmission을 결정하는 두 가지 방법

  1. timeout events

  2. triple duplicate acks (3 dup ACK)

     = fast retransmission before timeout 
     
     timeout이 발생하기 이전에 rtx를 결정하는 방법

     ⇒ TCP는 timeout 값은 넉넉히 설정하고 pipelining과 cumulative ack을 이용해 timeout 전에 loss를 유추하는 이중 방법을 사용하도록 설계됨

• 어떻게 fast retransmission이 가능?

  pipelined segments: ACK을 받지 않은 상태에서 일련의 데이터 전송

  cumulative acks: 앞의 ACK이 loss 되어도 그 다음 ACK만 잘 가면 ok

TCP sender events:

timer로 retransmission 하는 방법

1. data received from app

• create segment with seq # ← NextSequenceNumber

  : 이 번호로 receiver 측에서 loss가 생겼는지 판단 (by gap)

  ( seq#의 byte부터 MaxSegmentSize byte까지의 data 전송됨 )

  NextSequenceNumber = NextSequenceNumber + MSS

  MSS: 최대 세그먼트 크기 Maximum segment Size

  → 송신 호스트에 의해 전송될 수 있는 가장 큰 프레임 길이 (MTU: Maximum Transmission Unit) 에 의해 결정

• 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

---

Quiz

(71) T/F

(a) Sender TCP 가 segment를 보내놓고 retx 시점을 결정하기 위해 사용하는 타이머의 timeout 값은 네트워크의 실제 RTT 값을 사용한다.

⇒ T. 실제 RTT값을 측정해 timeout 값을 조정함

(b) Sender TCP의 타이머는 가장 최근에 보낸 segment의 첫번째 바이트를 가리키고 있다.

⇒ F. 가장 마지막으로 ACK을 받은 segment의 다음 segment (첫번째 inflight segment)

가장 오래전에 보낸 segment의 첫번째 바이트. 즉, Sendbase에 타이머가 달려있다.

(c) Sender TCP가 3 Dup ACK으로 loss를 판단한 경우가 timeout으로 loss를 판단한 경우 보다 네트워크 상황이 더 나쁘다.

⇒ F. 반대, timeout으로 loss를 판단한 경우가 네트워크 상황이 더 나쁘다.

(d) 버퍼는 크기가 아무리 작아도 버퍼 입력율 보다 출력율이 작다면 overflow가 발생하지 않는다.

⇒ F. 버퍼 입력율보다 출력율이 작으면 overflow가 발생할 수 있다.

버퍼는 크기에 상관 없이 출력율이 입력율보다 항상 크면 오버플로우X

(e) TCP 가 connection을 맺을 때마다 sequence number 는 항상 초기값 0으로 시작한다.

⇒ F.

(72) 다음 빈칸을 send 혹은 receive 중 하나를 넣으시오.

TCP가 사용하는 ( send ) buffer는 수신 TCP가 순서에 맞게 segment들을 받았는지 확인될 때까지 보낸 segment를 저장하고 있다가 필요시 재전송을 위해 필요하며, ( receive ) buffer 는 sender TCP가 data를 보내는 속도와 상위 어플리케이션이 그 data를 가져가는 속도의 차이를 보완하기 위해 사용된다.

(73) 두 호스트 P와 Q가 통신하고 있다. 호스트 P가 ACK-bit가 1인 TCP 세그먼트 받았을 때, acknowledgement number 필드에 적힌 값이 1150이였다. 이 1150번은 무슨 의미인가?

⇒ receiver는 sender로부터 SequenceNumber가 1149번인 세그먼트까지 받았고, 1150번인 세그먼트를 기다리고 있다.

(74) 슬라이드 #30에서와 같이 호스트 B가 79번째 byte로 시작하는 segment를 보내면서 동시에 ACK number = 43을 함께 보내는 방식을 뭐라고 하는가?

⇒ Piggyback

(75) TCP sender가 timeout 값을 지나치게 작게 잡으면 (premature timeout) 어떤 현상이 일어나는가?

⇒ ACK이 도착하기 전 timeout이 발생해 retransmission을 하게 된다.

네트워크 지연에 의해 수신측에 늦게 도착하는 패킷 (delayed packet)을 loss로 오판하게 되어 불필요한 재전송이 일어나게 되는데, 네트워크 자원을 낭비하게 된다.

(76) TCP sender가 timeout 값을 지나치게 길게 잡으면 (slow reaction) 어떤 현상이 일어나는가?

⇒ segment 혹은 ACK이 손실 될 경우 retransmission까지 많은 시간이 소요된다.

패킷 loss 감지 및 필수적인 재전송이 늦게 일어나게 되므로, 결과적으로 상위 5계층 응용이 느끼는 서비스 품질 (latency)이 나빠지게 된다.

(77) 슬라이드 37번에서 정의한 SendBase와 NextSeqNum를 사용한다고 가정한다. 현재 SendBase = 800이고 NextSeqNum가 1150 일 때, 수신한 TCP segment의 ACK#가 1050이고 5계층에서 200 바이트가 전송되기 위해 내려왔다고 가정하면 SendBase와 NextSeqNum는 어떤 값으로 update 되는가? (MSS는 100이라고 가정함)

⇒ SendBase: 1050, NextSeqNum: 1250

Sendbase가 800, NextSeqNum이 1150이므로 window size는 최소한 1150-800=350보다 클 것이다. ACK# 1050이 도착해 SendBase가 1050으로 이동하므로 1050+350=1400번까지는 전송이 가능하므로 pipelining을 통해 연속으로 두 segment를 보내면 NextSeqNum은 1150+200=1350

만약, 5계층에서 내려온 데이터가 110 바이트라면?

이때는 우선 100 바이트 segment를 전송하고 남은 10바이트는 (OS에 따라 구현이 다르나) 대부분의 TCP는 바로 전송하지 않고 버퍼에 저장해서 다음 내려오는 응용 메시지 (outgoing data)와 함께 MSS를 채워서 보냅니다. 그러나 언제까지나 기다릴 수는 없으므로 타이머를 사용해서 일정기간 동안 더 이상의 응용 데이터가 내려오지 않으면 버퍼에 남은 데이터를 전송하게 됩니다.

여기서 타이머는?

만일 SendBase=890이고 NextseqNum=1150일 때는 timer가 890byte에 걸려 있었는데, ACK#=1050을 받고 나서는 timer가 1050 byte를 가리키고 re-start하게 됩니다.

그 다음 110 바이트가 5계층에서 내려왔고, MSS가 100이므로 한 segment를 전송하게 되어, NextSeqNum는 1150+100=1250으로 바뀝니다. 이때 timer는 5계층에서 응용 데이터가 내려온 것 과는 아무런 상관없이 1050byte에서 re-start 한 후 계속 흘러가고 있습니다.

(타이머는 SendBase)