[Transport Layer] TCP

 

 

Data Transfer

간단한 버전으로 TCP에 대해 설명하겠다. 

* TCP는 비교적 간단한 protocol이다. (GBN과 SN의 결합형태)

• Data received from Application Layer → encapsulate : in a segment, allocate SN, start timer, pass to the network layer
  ▷ 데이터 수신 (응용계층 → 전송계층) : 애플리케이션 계층에서 데이터를 수신하여 TCP 세그먼트로 캡슐화한다. 이 과정에서 각 세그먼트에 SN을 할당하고, 타이머를 설정한다. 이후, 캡슐화된 세그먼트를 네트워크 계층으로 전달한다.
• Timer time-out : restransmit the segment, restart timer
  ▷ 세그먼트가 전송된 후 일정 시간 내에 응답을 받지 못하면, 타이머가 타임아웃된다. 타임아웃이 발생하면 해당 세그먼트를 다시 재전송하고, 타이머를 재시작한다.
• ACK receipt : compare with "send base", update send base 
  * send base : ACK를 받지 못한 가장 오래된 byte의 순서 번호
  ▷ ACK 수신 후 처리 : 응답을 받으면 (ACK), 해당 응답을 송신한 데이터 기준값인 send base와 비교 후 업데이트한다.

TCP segment 구조 및 용어

Header field

• Source port #, Dest port # : 출발지와 목적지 포트 번호
• sequence number : byte stream number of 1st byte in the segment 순서를 확인하기 위한 세그먼트의 첫번째 바이트 번호
• acknowledge number : sequence number of next byte expected 확인 응답 필드로 다음 데이터에게 기대되는 바이트 번호
  * GBN/SR의 경우, ACK값은 해당 패킷을 잘 받았음을 의미하지만, TCP에서는 다음에 보낼 패킷의 값을 의미한다.
• header length : 4비트의 헤더길이 필드 (32비트 워드 단위로 TCP 헤더 길이 표현)
• flag : ACK, RST, SYN, FIN, PSH, URG 비트등이 포함된다
• option : 송신자와 수신자가 MSS를 협상하거나 고속 네트워크에서 사용하기 위한 window 확장 요소로 이용

Data field

애플리케이션 데이터의 일정량을 담는다.

MSS (Maximum Segment Size)

The maximum amount of data that a segment can hold

세그먼트 필드 크기의 최댓값

큰 파일 전송 시, 일반적으로 MSS 크기로 파일을 분절한다.

 

예시

0번 바이트부터 1000번 바이트까지 전송하는 과정에서 seq#92로 세그먼트를 전송한다고 가정하자.

timeout

보내는 패킷

time out이 발생하면, 보냈던 패킷을 다시 retransmit한다.

seq는 보내는 패킷의 맨 첫번째 byte 번호를 보내고, ACK는 다음에 받을 시작 byte 번호를 보낸다.

pipelining

보내는 패킷

 

TCP도 cumulative acknowledgment를 사용한다.

따라서 첫번째 segment의 timeout 전에 ACK#120을 받으면, B가 119byte까지 받은 것으로 인식함.

따라서 그 전의 92~99 패킷도 받은 것으로 인식한다.

 

Fast transmission 

TCP sender receives 3 ACK's for same data → retransmit the segment before time-out

time-out이 되기까지 기다리지 않고 sender가 다시 retransmit 할 수 있도록 하는 알고리즘

지금 seq#X를 보냈는데, 중간에 pkt이 loss되었다. 따라서 응답으로는 계속 #X를 보내달라는 ACK #X를 보낸다. 

같은 ACK가 쌓인다면 timeout 되기 전에 패킷을 재전송할 수 있다. 

 

Duplicate ACK > Fast Transmission

an ACK that acknowledges a segment for which the sender has already received an acknowledgment

이미 받은 ACK를 또 받는 상황이다.

---

TCP : GBN or  SR

TCP ACK는 누적되고 올바르게 수신되지만, 순서가 잘못된 세그먼트는 수신자가 개별적으로 ACK를 받지 않는다.

이러한 관점에서 TCP는 GBN 형태와 유사하지만, 

TCP에서는 올바르게 수신되었지만 순서가 바뀐 세그먼트들을 버퍼링한다는 차이점이 존재함

* GBN은 전송되지 않은 패킷부터 전부 다시 재전송한다.

 

또한, TCP는 마지막으로 올바르게 수신된 순서가 맞는 세그먼트에 대해 누적 확인 응답을 하기 보다, 순서가 틀린 세그먼트에 대해 선택적 확인 응답을 한다 > 선택적 재전송과 결합시 SR 프로토콜과 비슷함

 

따라서 not send that many pkts that receiver buffer can't handle 

→ flow control(receiver buffer), congestion control(router buffer)

---

Flow Control | 흐름 제어

receive window : free buffer space a the receiver and sender maintains it

TCP는 수신 윈도우라는 변수를 유지하여 흐름제어를 제공한다.

이는 수신 측에서 가용한 버퍼 공간이 얼마나 되는지를 송신자에게 알려준다.

 

RcvBuffer

LastByteRead : 프로세스에 의해 버퍼로부터 읽힌 데이터 스트림의 마지막 바이트 번호

LastByteRcvd : ACK된 바이트로, Buffer에 저장되어있다.

rwnd : 버퍼에 남아있는 여유 공간으로 동적인 변수이다.

 

LastByteRcvd - LastByteRead ≤ RcvBuffer

rwnd = Rcvbuffer - [LastByteRcvd - LastByteRead]

 

sender은 LastByteSend와 LastByteAcked를 유지한다.

LastByteSend - LastByteAcked = sender가 이 응답에 전송 확인 응답이 안된 데이터의 양

 

LastByteSent - LastByteAcked ≤ rwnd를 보장한다.

 

rwnd = 0인 경우

수신자의 버퍼가 가득 차서 더 이상 데이터를 수신할 수 없는 상태이다. 

이런 경우 수신자는 송신자에게 rwnd=0임을 알린다.

 

만약, 수신자가 그 이후로 송신자에게 세그먼트를 보내지 않는다면, 수신자는 응답을 보낼 수 없다

따라서, sender은 reciver에게 1바이트의 세그먼트를 계속 보냄으로써 응답을 받을 수 있도록한다.

 

예시

0에서 100까지의 바이트를 가진 패킷이 있다.

LastByteRead : 60

LastByteRcvd : 80

LastByteAcked : 70

 

이때 Rcvbuffer는 80-60인, 20 이상임이 보장된다.

 

Rcvbuffer가 50byte일 때, 현재 rwnd는 50-20인 30이다.

따라서 buffer에 넣을 수 있는 최대 값은 현재 Acked된 70부터 최대 100(30바이트 만큼)이다.

 

---

 

Congestion control | 혼잡 제어

Too many sources sending too much data too fast for network to handle

네트워크에서 너무 많은 소스가 동시에 데이터를 보내는 경우, 네트워크가 이를 감당하지 못해 혼잡이 생긴다. 

 

두 가지 문제가 발생한다.

• lost pkts (buffer overflow)
• long delays

TCP congestion control algorithm

Congestion avoidence | 혼잡 회피

 

네트워크 계층은 혼잡 제어 목적을 위해 전송 계층에 어떤 직접적인 지원을 제공하지 않는다.

no info the length of congestion window size 따라서 버퍼(window)의 크기도 알 수 없다.

▷ Start small # of n, increase n until pkts lost 패킷 loss가 발생할 때까지 작은 n부터 시작하여 점점 늘린다. 

 

 

 

active increase : increase congestion window by 1MSS every RTT until loss detected
▷ loss가 없을 때, 1RTT마다 1MSS씩 congestion window를 늘린다.

 

multiplicative decrease : cut congestion window in half after

▷ loss 발생시, congestion window size를 1/2로 줄인다.

 

 

 

 

 

Fairness | 공정성

여러 사용자들이 네트워크를 공유할 때, 각 사용자들이 공정한 비율로 대역폭을 사용하는지 평가함

 

\(c\) (capacity) \( = rate1 + rate2\)

\(rate = \frac{window\ size}{RTT}\)

 

파란색은 1증가, 빨간색은 절반 감소하는 것이다. 

최대한 optimum point of operation에 수렴해야한다. 

 

Slow Start | 슬로우 스타트

Initially congestion window = 1MSS

initial rate = \(\frac{MSS}{RTT}\)

ex) MSS = 500bytes & RTT = 200msec > initial rate = 20kbps

 

Dobule congestion window every RTT 한번 RTT마다 cong win을 두 배씩 증가시킨다.

▷ increment Cong win for every ACK rcvd

Rate ramps up exponentially fast

 

when loss occurs :

Threshold is set to 1/2 of congwin just before loss event

임계값은 패킷 손실이 발생하기 전의 윈도우의 크기의 절반으로 설정되게 되고, 혼잡 회피 단계로 전환된다.

 

Loss event | 손실 이벤트

손실 이벤트는 두 가지 방식으로 탐지될 수 있다.

• Duplicate ACKs (중복된 ACK) : sender reduces rate (congestion window) after loss event to half its previous value
• time-out : Set congestion window = 1MSS

\(Treshold\ new = \frac{Threshold\ old}{2}\)

 

TCP는 threshold보다 낮으면 지수증가, 높으면 선형 증가한다.

 

해당 그래프를 보면, 먼저 지수증가하다가, 임계점에서부터 선형증가한다. 

만약, Duplicate ACKs를 만난다면, 현재 value의 절반부터 시작하고 임계값을 절반으로 줄인다.

임계값보다 시작 위치가 높다면, 그대로 선형 증가한다.

중간에 timeout을 만난다면 크기는 다시 1MSS로 증가하고 임계값이 절반인 40으로 줄어든다.

 

 

state	event
slow-start	ACK	cong win = congwin * 2 If congwin > threshold go to CA
CA	ACK	Congwin = Congwin + 1MSS
SS or CA	Triple duplicate ACK	Threshold = Congwin /2  Congwin = Threshold State = CA
SS or CA	Time-out	Threshold = Congwin /2 Congwin = 1MSS state = SS

 

 

delay 계산 예시 (Congwin 고려 X)

Data rate = 1Mbps
packet size = 1kbits
RTT = 10ms
File size = 10kbits

패킷 사이즈가 1kbits고, 총 file size는 10kbits이므로, 총 보내야할 패킷은 10개

transmition delay \(=\frac{L}{R} = \frac{10^3}{10^6} = 10^{-3} = 1ms\)

Transmit delay가 생기는 시간은 서버가 일을 하는 시간이다. 

RTT는 서버가 대기하는 시간이다. (idle time)

 

∴ Total Delay \(2RTT + 10 \times \frac{L}{R} + [\frac{L}{R} + RTT - \frac{L}{R}] * 9\)

10개의 transmition time이 생기고 (10개의 패킷)

그 사이의 RTT는 #of pkt-1만큼 생긴다.

 

Go-Back-5

 

 

transmition delay가 5번이 발생

\(\frac{L}{R} + RTT - 5\times \frac{L}{R}\)만큼의 시간이 idle time이 됨

 

 

∴Delay \(= 2RTT + 10 \times \frac{L}{R} + [\frac{L}{R} + RTT -5 \times \frac{L}{R}] \times 1\)

idle time 계산 법을 일반화 하면 

idle time \( = [ \frac{L}{R} + RTT - k \times \frac{L}{R}] \times \left \lceil \frac{pkt num}{k}  \right \rceil \)

 

 

delay 계산 예시 (Congwin 고려)

Fixed case 

cong win size가 고정되어 있음

R : one link between client and server with rate
s : MSS
o :File size
CongWin = w segments (Cong win size를 고정)
전체 패킷 전송 시간 : \(\frac{o}{R}\)

 

 

Case 1 : \(\frac{L}{R} \times w > RTT + \frac{L}{R}\)

w = 4라고 가정하자

현재 전체 한번에 전송하는 크기는 \(\frac{L}{R} \times w\)인데, 이게 RTT보다 크다.

네 개를 연달아 보내기 전에 첫번째 패킷에 대한 ACK가 도착했다. 

ACK를 하나 받을 때 마다 또 보낼 수 있다.

따라서, idle time 즉 서버가 대기하는 시간이 필요가 없다.

∴ delay \(= 2RTT + \frac{o}{R}\)

현재 이 경우에서는 CongWin size가 충분해서 delay 없이 보낼 수 있다.

 

Case 2 : \( \frac {L}{R} \times w < RTT + \frac{L}{R} \)

이런 경우에는 idle time이 생긴다

idle time \( = \frac{L}{R}  + RTT - \frac{L}{R} \times w\)

∴ delay \(= 2RTT + \frac{o}{R} + [ RTT + \frac{L}{R} - \frac{L}{R} \times w] \times (k -1)\)

w는 window size

k 는 총 window 수

 

Case 1 + Case 2

∴ total delay \( = 2RTT + \frac{o}{R} + (k-1) \times [RTT+\frac{L}{R} - \frac{L}{R} \times w]^+\)

 

Dynamic window

window grows according to slow-start rule

 

w : congestion window size

k : # of congestion windows (segments)

pktnum : \(\frac{o}{s}\)

 

*w가 fixed 일 때 \(k \times w \geq pktnum\) 이였다. pktnum도 고정이다.

이때 w가 변수이다. 

\(w_1 = 1\), \(w_2 = 2\) , \(w_3 = 4 \) ..로 지수 형태로 늘어나고, 이는 즉 \(w_i = 2^{i-1}\)이라는 듯이다

\(k \times w \)였는데, 이를 윈도우 개수 k개에 \(w_i\)를 k만큼 곱해주면

\(2^0 + 2^1 + ... 2^{k-1} \geq pktnum\)으로 볼 수 있다

\(\frac{1\times (2^k-1)}{2-1} = 2^k -1 \geq pktnum\)

∴ \(k \geq log_2(pktnum+1)\)

k는 정수이므로 \(k = \lceil log_2(pktnum+1) \rceil \)으로 볼 수 있다. 

 

단, 이 다이나믹의 경우는 cong win size가 k-1까지 threshold 에 도달하지 않는다고 본다.

즉, 계속 slow start 구간이다.

 

∴ delay \(= \sum_{i=1}^{k-1} [\frac{L}{R} + RTT - 2^{i-1} \times \frac{L}{R}]^+ + 2RTT + \frac{o}{R}\)

 

현재 \(k_1, k_2 ...\) 까지 모두 텀이 있는데, 텀이 0인것들도 있을 수 있다. 이를 없애줄 것이다.

해당 식을 더 간단한 형태로 바꿀 수 있다.

 

Q : # of time server would stall (idle 상태가 되는 횟수)

idle 상태가 된다는 것은 idle time이 존재해야하고, 즉, 첫번째 패킷을 보내 ACK 돌아오는 시간이 congestion window 보다 커야함

\(\frac{L}{R} + RTT \geq 2^{k-1} \times \frac{L}{R}\)

* 현재 window size가 \(2^{k-1}\)이다. 

\( Q = max(k) = \lfloor log2(1+\frac{RTT}{L/R}) \rfloor + 1\)

 

실제 파일 size인 o에 대한 고려가 없기 때문에 Q가 현재 window size -1 보다 큰 상황이 생길 수 있다. 

window의 개수가 10개인데 idle 타임이 12개가 될 수 없다. 무조건 9개 이하로 존재해야함

 

actual # of the server stalls is P = min {Q, k - 1}

즉 , delay는 +기호를 없애고 \(2RTT + \frac{o}{R} + sum_{i=1}^{p}[\frac{L}{R} + RTT - 2^{i-1} \times \frac{L}{R}\)

∴ delay\( = 2RTT + \frac{o}{R} + P\times [RTT + \frac{L}{R}] -(2^p-1) \times \frac{L}{R}\)

 

 

예시

o/s = 30 (총 30개의 패킷으로 구성)

k = window의 개수

 

k = min { 1 + 2 + 4 + 8 + 16 ≥ 30이므로 \(2^k-1\)이 30보다 커야하므로 k = 5이다. 

 

1    2    4    8    16이 존재한다.

idle  idle  idle  x   

 

ACK를 받아야 다음 전송을 할 수 있으므로 윈도우들 사이에 ACK가 4번 발생할 수 있다.

Q = 3이라고 가정하자 idle 이 마지막에서 발생하지 않았다. 

P = min(3,4) = 3

 

Q를 다시 가정해보자

Q = 8이므로 P = min (8,4) = 4