Reliable data transfer - TCP

Mechanism of reliable data transfer

reliable transfer를 위해 ack. mechanism 사용이 반드시 필요한데,

이러한 ack. mechanism 사용을 위해서는

sequence number 사용이 필요하고,

 

ack. mechanism을 사용하면서 bandwidth 활용을 높이기 위해서는

window를 활용한 pipelining 을 해야 한다.

 

 

checksum

• detect bit error

 

acknowledgement (ACK)

• 잘 받았다고 sender에게 알림
• sender는 다음 segment를 보내면 됨
• 방식
  • individual : receiver가 받은 각 packet에 대해서 ack를 일일이 보냄
  • cumulative : n번까지 라고 퉁쳐서 ack 하나 보냄

negative acknowledgement

• 문제 있다고 sender에게 알림
• 전송한 segment를 다시 보냄 (re-transmit)
• acknowledgement 와 같이 안 씀

 

timer

• loss인 경우 segment에 문제가 있는지조차 탐색 불가능
• 이 때 timeout을 알림
• 복제본이 여러 개 들어올 수도 있다는 문제가 있음
• 잘 가고 있었는데 loss아닌가 싶어서 섣불리 timeout이라고 말하는 문제가 있음
• ACK의 loss에 대해 처리할 수 없음
• retransmit을 요구할 시점과 다시 받아야할 packet을 알림

 

sequence number

• 복제복은 중복하여 받는 것을 방지하기 위해
• 방금 온 sequence number는 0이고 새로 온 packet의 number가 1이라면 새 거 구나 하고 받음
• 만약 두 개가 서로 같다면 복제본임을 reciever가 알아채고 drop
• 특히 window로 여러 개를 보내면
  • 0,1이 아닌 window 크기만큼 넘버링
  • 그래서 받은 packet 속 sequence number에 gap이 존재하면 loss를 의심할 수도 있음

pipelining & window

• 아래의 pipelining에 필요
• stop and wait는 너무 오래 걸림ㅠ
• sender가 한 번 보낼 수 있는 packet의 수

 

 

Propagation Delay and Throughput

stop-and-wait

1. 하나 보내고 기다리고 를 반복 
   1. throughput = 1 packet / RTT
2. d_trans << d_prop 이어서 throughput이 엄청 낮아짐
   1. d_trans : transmission time
   2. d_prop : propagation time

 

pipelining

1. ACK을 받지 않아도 한 번에 쭉 보냄
   1. throughput = 5 packet / RTT
2. throughput은 증가하지만 data 양을 조절하여 보내야
3. receiver의 buffer overflow와 network의 congestion control을 방지
4. 이를 제한하기 위한 packet 개수를 window로 제한

 

 

Propagation time이  transmission time보다 길면,

stop and wait에서 비효율적 (throughput 낮아짐)

 

이 때는 ACK을 받지 않는 Pipelining을 해서 throughput을 향상시킬 수 있다

한 번에 보내는 packet의 수는 window 크기보다 적음

 

 

 

---

 

Connection-oriented transport TCP

transport protocol

 

 

point to point

• one sender, one receiver

reliable, in-order byte stream

• TCP는 message boundaries를 인식하지 않고 전송
• sender의 send buffer에 application layer에서 내려보낸 data 저장
• buffer 속에 일정 사이즈 만큼 잘라서 전송
• 즉 실제 데이터 크기 대로 보내는 것이 아님
  • UDP가 TCP보다 어떤 데이터가 segment에 담겨졌는지, 언제 보냈는지 컨트롤하기 쉬움.
  • TCP로는 byte-flow 방식이라 byte 단위로 끊어서 보냄. 그래서 segment에 하나의 메시지를 더 짧게 혹은 더 길게 담아서 보내기 때문. 반면에 UDP는 application이 주는 대로 무조건 하나의 segment에 담아서 전송. 그 메시지는 UDP segment의 payload에 모두 담음. 그렇기에 UDP를 이용하면 하나의 segment에 어떤 데이터를 담았는지 application에서 통제하기 용이함 

• UDP는 application message의 boundary를 인식하고 전송하는데 반해
• TCP는 application이 내려보내는 데이터를 byte stream으로 보고 전송한다.

connection-oriented

• handshaking 먼저 필수

full duplex data

• 두 지점 사이 맺어진 connection을 바탕으로 양방향 데이터 교환 
• TCP connection이 맺어 지면 이는 양방향 transmission이 이루어지는 bidirectional connection

MSS

• maximum segment size
• TCP segment는 특정 물리적 링크로 실어서 보냄
• rkr link의 frame(data unit)에 실을 수 있는 최대 크기에 맞추어 보내야 함

flow controlled

• receiver에 넘치지 않도록 하기 위해

congestion controlled

• network에 넘치지 않기 위해

pipelined

• TCP congestion 과 flow control을 위해 window 크기 정함
• TCP의 transmission window 크기는
• 시간이 감에 따라 receiving buffer에 가용 양과 네트워크 상태에 따라 변할 수 있는
• 가변적 크기의 window이다.

 

---

TCP - 1. segment structure

모든 TCP segment는 4byte의 5개의 필드를 고정으로 가지고 있음

demux mux에 필요한 정보인 source, dest port

reliable 을 위한 sequence number

자신이 상대로부터 받은 것에 대해 ack 정보를 acknowledgement number에 실음

• ACK # valid
• 내가 보내는 데이터에 n번까지 잘 받았다고 여기에 실음

!! 주의

• sequence number와 ack number는 byte 단위로! segment (X)
• ack number 와 receive window는
• 내가 보내는 데이터의 정보가 아닌
• 상대방이 나에게 보낼 데이터에 대한 정보를 실어서 보내는 것

 

sequence number는 

• payload에 실려있는 첫번째 byte가 byte stream에서 몇 번째 byte에 해당하는지 적어줌
  • 어디서부터 시작하는 segment인지 알 수 있도록,
  • 즉 그 packet이 몇 번째 순서에 놓인 packet인지 알 수 있도록

 

 

receive window

• # byte rcvr will
• ack num 이후로 얼마나 받을 수 있는지 알림
• flow control을 위해 사용

The size of the TCP rwnd changes by receiving buffer ...

The TCP segment has a field in its header for rwnd.

 

 

RSF, SYN, FIN

• 이 3가지를 이용해 connection setup / teardown / command

URG : urgent flag (data) -> 현재 사용 X 

•  긴급 데이터 포함 여부 알림
• urg data pointer에 payload에서 어느 위치에 그 데이터가 등장하는 표기

PSH : push data now  -> 현재 사용 X 

• segment를 받는 즉시 receiver buffer를 flash해서 바로 배달해달라고 요청
• 

 

 

 

Internet checksum

• UDP와 마찬가지
• The size of the TCP rwnd never changes throughout the duration of the connection.

  

 

그 다음으로 option 필드는 길이가 저마다 다른 필드가 들어옴

option 필드의 길이 표시는 head len에서

 

 

 

TCP sequence number , ACKs

sequence number

• segment의 first byte의 byte stream number

acknowledgement

• 다음 byte의 sequence number
• cumulative ACK (n번)

out of order segment를 받은 경우

• TCP에서 어떻게 할 지 정하지 않았기에 implementor에게 그 일을 넘김
• 그래서 TCP 마다 keep할 수도, drop할 수도
  • 둘다 옳은 TCP
  • keep일 경우 생략된 부분을 받자마자 application layer로 올릴 수 있지만
  •  drop인 경우에는 시간이 조금 더 걸림

 

- 초록색 : 보냈고, 그에 대한 ACK도 받음

- 노란색 : 보냈는데 아직 ACK은 받지 못함

• 여기에서 가장 앞서 있는 쪽이 바로 acknowledgement number

- 파란색 :  application layer에서 내려오지 못해서 보내지 못함

• 여기에서 가장 앞서 있는 쪽이 바로 sequence number

- 회색 : window에서 벗어난 부분이기에 아직 sequence number 부여 X

 

 

 

ex) telnet scenario

인터넷을 통해 원격 host에 접속하는 것

keyboard - > CPU -> screen 과정에서,

host A는 keyboard, screen만, host B는 CPU만 이용

• echo back된 C를 화면에 띄움
• 꼭 잘 받았다고 ACK 보내기

• seq 42는 이번에 보내는 문자 C가 자기 byte stream에서 42번째임을 의미
• ack 79는 a가 b에게 79번째 byte를 받고 싶다고 알림
• 그래서 seq 79로 보내고 ack은 43을 기대한다고 알림

 

 

 

P5. Host A and B are communicating over a TCP connection, and Host B has already received from A all bytes up through byte 126. Suppose Host A then sends two segments to Host B back-to-back. The first and second segments contain 80 and 40 bytes of data, respectively. In the first segment, the sequence number is 127, the source port number is 302, and the destination port number is 80. Host B sends and acknowledgement whenever it receives a segment from Host A.

 

a.      In the second segment sent from Host A to B, what are the sequence number, source port number, and destination port number?

In the second segment from Host A to B, the sequence number is __126+80+1___, source port number is _302___ and destination port number is _80__.

b.     If the first segment arrives before the second segment, in the acknowledgment of the first arriving segment, what is the acknowledgment number, the source port number, and the destination port number?

If the first segment arrives before the second, in the acknowledgement of the first arriving segment, the acknowledgement number is __126+80+1__, the source port number is _80___ and the destination port number is __302__.

c.      If the second segment arrives before the first segment, in the acknowledgment of the first arriving segment, what is the acknowledgment number?

If the second segment arrives before the first segment, in the acknowledgement of the first arriving segment, the acknowledgement number is __127___, indicating that it is still waiting for bytes __127___ and onwards.

 

d.     Suppose the two segments sent by A, arrive in order at B. The first acknowledgment is lost and the second acknowledgement arrives after the first timeout interval. Draw a timing diagram, showing these segments and all other segments and acknowledgments sent. (Assume there is no additional packet loss.) For each segment in your figure, provide the sequence number and the number of bytes of data; for each acknowledgment that you add, provide the acknowledgment number.

---

TCP round trip time, timeout

TCP의 timeout 값 설정 방법?

ack을 받아야하는 시점에 오지 않을 때 쓰기에,  RTT 보다 길어야 함

• 그런데 RTT가 변동이 크다는 단점
• too short : premature timeout -> 불필요한 재전송
• too long : loss에 대한 대처가 늦어짐

 

RTT를 평가하는 방법?

 

sampleRTT : 

• segment를 내보낸 이후로 ACK을 받기까지 걸린 시간을 알아두고 이를 기반으로 측정
• retransmission에 대한 시간은 고려하지 않음
  • retrans의 ACK인지 original의 ACK인지 분별하기 어려워서
• sampleRTT도 다양하기에 완화된 기준으로 정함
  • 여러 개에 대한 평균으로 계산
  • 굉장히 들쭉날쭉한 sampleRTT

 

EstimatedRTT : 

• sample이 오래될 수록 (1-a) 를 곱해줌
• -> 이후에 sample의 영향을 줄여서 기하급수적으로 변동성을 낮춤

• alpha 설정은 경험을 기반하여 설정

•  

  

 

TCP는 error control을 위해

round trip time estimation이 필요한데,

이를 위해 sample RTT의 exponential weighted moving average를 사용한다.

 

즉, RTT estimation에

각 RTT sample의 기여 정도는

시간이 감에 따라 exponential하게 감소하게 된다.

 

 

 

timeout interval : EstimatedRTT + safety_margin

• sampleRTT가 갑자기 크게 뛰어버리면 그것을 조금 따라가기에
• 이에 대한 보완으로 safety_margin을 덧셈
• 변동이 클수록 safety도 크게!

SampleRTT Deviation from EstimatedRTT

• sample과 estimated의 차이를 B만큼 반영
• 이전 step devRTT를 (1-B)만큼 반영
• devRTT가 클수록 safety margin을 크게 줌
• B는 경험을 통해 설정

결론

 

 

 

Suppose that the five measured SampleRTT values (see Section 3.5.3) are 106ms, 120ms, 140ms, 90ms, and 115ms. Compute the EstimatedRTT after each of these SampleRTT values is obtained, using a value of α = 0.125 and assuming that the value of EstimatedRTT was 100ms just before the first of these five samples were obtained. Compute also the DevRTT after each sample is obtained, assuming a value of β = 0.25 and assuming the value of DevRTT was 5ms just before the first of these five samples was obtained. Last, compute the TCP TimeoutInterval after each of these samples is obtained.

 

-> 첫번째 SampleRTT = 106ms를 얻고난 후

 EstimatedRTT = 0.875 * 100 + 0.125*106 = 100.75ms

DevRTT = 0.75 * 5 + 0.25 * |106 - 100.75|  = 5.06ms

TimeoutInterval = 100.75ms + 4*5.06ms = 120.99ms

 

-> 두번째 SampleRTT = 120ms 를 얻고난 후

After obtaining second SampleRTT = 120ms:

After obtaining third SampleRTT = 140ms:

After obtaining fourth SampleRTT = 90ms:

After obtaining fifth SampleRTT = 115ms:

---

TCP - 2. reliable data transfer

TCP 는 reliable을 실현하기 위해

 

• pipelined segment
• cumulative acks
• single retransmission timer per connection
  • when retransmission?
    • timeout events
    • duplicate acks - 단순한 TCP sender는 이걸 하지 않음 
      • flow control, congestion control도 안 함
    • TCP가 retransmission을 하게 만드는 event는 timer expiration과 triple dup. ack. 받게되는 경우
    
    

TCP sender events

data rcvd from application layer

• 새 segment를 생성하여 sequence number부여 -
  • first data byte로 지정
• timer를 connection 당 한 개만 사용
  • 내보냈지만 ack을 받지 못한 것 중 가장 오래 전에 것에 대해 timer 작동 (for oldest segment)
  • expiration interval : TimeOutInterval

 

 

timeout

• retransmit segment caused timeout 
• 타이머를 다시 시작

 

ack rcvd from network layer

• ack된 segment를 update
• 타이머를 다시 시작
• oldest segment가 그 다음으로 변경됨

 

 

 

TCP sender (simplified)

TCP는

retransmission timer를 각 connection 별로 1개씩 두고 

unacked segment 중

oldest segment에 대해 이 timer를 적용한다.

 

TCP sender 측에서 발생할수 있는 event는

•  application 계층으로부터 data를 받거나, 
• network 계층으로부터 ack.을 받거나, 
• timer가 expire되는 세 가지 종류가 있다.

 

 

1. TCP sender 상태가 처음 초기화되었을 때

1. NextSeqNum : 다음에 새롭게 생성할 segment의 sequence num (파랑 맨앞)
2. SendBase : 다음에 ack 받기를 기대하는 최소 segment  (노랑 맨앞)
3. 초기에는 둘 다 InitialSeqNum으로 초기화

 

2. application으로부터 data 받음

1. 새로운 segment 생성하여 그 sequnce number에 NextSeqNum 써 줌
2. 다음 NextSeqNum  = NextSeqNum  + length(data)
3. 새로 만든 segment은 IP로 내려보냄
4. 타이머가 실행 중이지 않았다면, 지금 보내는 것이 oldest segment가 되므로 타이머를 실행

 

3. 타임아웃 발생

1. 해당 segment 재전송 with smallest seq #
2. 타이머 재시작

 

4. ACK을 받으면

1. ACK 필드에 있는 값으로 SendBase 지정
2. ACK 필드값이 y라면
3. if (y == SendBase )
   1. 복제본이 왔다는 의미라서
   2. 이미 왔던 ack을 또 받은 것이기에
   3. SendBase 를 update 할 필요 없음
4. if (y > SendBase )
   1. 뒤쪽으로 SendBase 를 옮김
   2. 즉 ,SendBase를 y로 지정
   3. 초록색이 늘어남
   4. 가장 최근에 받은 cumulative ACK byte로 업데이트
   5. 아직 노란색 파트가 남아있다면, ACK을 받지 못한 segment가 남아있기에 타이머를 재시작
   6. 노란색 파트가 남지 않았다면 inflight 상태 없으니 타이머 종료

      

 

TCP : retransmission scenarios

 

상황 1 - loss ACK -  ACK을 받지 못한 경우 timeout 기간까지 기다리다 안 오면 신호를 다시 보냄	상황 2 - premature timeout - loss가 아닌 아직 도착하지 못했는데 오해한 거라면 똑같은 요청이 두 번 오면 무시하고 최근 보낸 ACK으로 다시 보냄 TCP sender 측의 timer expiration이 premature한 것이어도  불필요한 duplicate data transmission을 하는것 이외에는  문제가 발생하지 않는다.
상황 3 - cumulative ACK timeout 전에 마지막에 보낸 segment의 ACK을 받으면 괜찮다고 넘어감

 

 

---

TCP ACK generation

ACK은 다음으로 무엇을 받아야하는지 알리는 신호가 됨

 

 

TCP에서 sender가 보낸 data segment 중 

하나에 대한 ack.이 loss된 경우 

 

해당 segment가 current window의 마지막 segment인 경우였다면 

불필요한 data duplicate, data transmission이 발생할 수 있지만, 

 

그렇지 않은 경우는 

TCP의 cumulative ack. 덕분에 

불필요한 duplicate retransmission 없이 진행될 수 있다.

 

arrival 방식	receiver에서는	그에 따라 TCP receiver의 반응은
in-order segment	받고자 한 sequence num이 도착했고  이전까지에 대한  ACK을 모두 보냈을 때	500ms 동안 ACK을 안 보내고 기다림 이유: ACK만을 보내기 위해 TCP를 쓰기엔 TCP segment 하나에 TCP header에 20Byte, IP 계층에서 IP header 20Byte가 붙게 되어 overhead가 커져서 별로 기다리면서 그동안 receiver에서 sender 측으로 보낼 data가 생길 때까지 기다려서 piggyback 아니면 다른 ACK이 올 수 있으니 cumulative ACK으로 모아서 보내려고
	ACK을 안 보내고 기다린, pending 상태인 ACK이 있다면	cumulative ACK을 즉시 수행
out-of-order segment	이후의 segment가 들어온다면	다시 현재에 필요한 것에 대한 ACK을 보냄 (duplicate ACK)
partially of completely fills gap	예상 못한 seq num가 들어온 다음 제 순서에 올 segment가 왔다면	그 gap의 가장 앞 부분이 정확하게 맞다면, ACK을 즉시 보냄 1,2 번이 완벽히 오면 괜찮은데 2번만 오면 이 상황이 아님

 

 

TCP는 일반적으로 control overhead를 최소화 하기 위해 

ack.을 piggy backing하는데, 

 

내보내야 하는 ack.을 piggy backing할 수 있는 data segment가 없고, 

현재  ack. transmission을 미루고 있는 received pending segment가 없는 상태라면

 

일단 500ms 동안은 ack. 전송을 delay 시켜본다.

 

 

 

TCP receiver가 received segment에 대해

즉시로 ack.을 내보내는 경우는

• 현재 ack.을 delay하고 있는 segment가 있는 상태에서 그 다음 in order segment가 들어온 경우
• out of order segment 가 들어온 경우, 
• gap이 있을 때 gap의 맨 앞부분부터 일부 혹은 전부를 채워주는 segment가 들어온 경우

 

 

 

TCP fast retransmit

timeout은 상당히 길게 잡기

• 이것만으로 error 잡기는 loss 알아내기 어려움
• duplicate ack을 받았을 때도 loss를 의미하는 방법을 추가 
  • TCP sender가 pipelined transmission을 하기에
  • 여러 segment를 확인하지 않고
  • back-to-back으로 보내기 때문에 일어남 
  • loss가 발생하면 sender는 여러 개의 duplicate ACK을  받게 됨

  • 

 

• TCP fast retransmit
  • 같은 데이터에 대해 3개의 ACK을 받으면
  • 이건 완전 소실이라고 생각하고
  • timeout 전이라도 바로 다시 보냄