[Transport Layer 01] Pipelining, Go-Back-N, Selective repeat

rdt 2.0, 2.1, 2.2, 3.0 을 배웠다. 

rdt의 stop and wait protocol의 경우 매우 비효율적이다. 

미국의 동부 끝과 서부 끝에서 패킷을 주고받는다고 생각해볼때 하나의 패킷을 보내고, ACK가 올때까지 기다려야한다.

다시 말해 물리적인 거리가 매우 긴 곳에서 stop and wait protocol을 이용해서 패킷을 주고받으면 propagation delay가 매우 클 것이기에 RTT가 길어져서 오랜 시간을 기다려야할것이다. 따라서 최악의 performance를 가질 것이다. 

Pipelining

그러면 데이터 패킷을 하나 보내놓고 기다리지 않고 데이터 패킷을 여러 개 보내놓고 기다리면 좀 낫지 않을까?

utilization을 구해서 비교해보자. 

왼쪽이 파이프라인을 적용하지 않은 rdt 3.0, 오른쪽이 파이프라인을 적용한 rdt 3.0

파이프라인이 적용되지 않는 utilization과 파이프라인이 적용된 utilization은 다음과 같이 나타낼 수 있다. 

파이프라인이 적용되지 않는 utilization

 

파이프라인이 적용된 utilization

 

pipelining을 n개 적용할 수록 utilization은 n배가 증가한다. 물론 여전히 만족스럽지 못한 수치이다. 매우 낮은 utilization이므로 3,000개, 혹은 30,000개가 적용되어야한다. 실제로 TCP는 receiver의 buffer를 overflow시키지 않는 범위 내에서 sender가 segment 여러개를 연이어 보낼 수 있다. 

 

Go-Back-N

TCP를 설명하기 위한 개념이다. sender는 다수의 파이프라인된 패킷을 보내야하기때문에 window를 가진다. window는 버퍼와 비슷하게 패킷들을 저장하는 저장공간이다. 굳이 버퍼라는 말을 쓰지 않은 이유는 고정되어있는 버퍼와 달리 window는 sliding되어 움직이기 때문이다. sender는 ACK를 받지 않은 상황에서 n개의 패킷을 보낼 수 있도록 하는 window를 사용한다. ACK가 도착한 패킷은 sender 입장에서 잊어버려도 되기때문에 slide한다. (sender와 마찬가지로 receiver도 도착한 packet을 저장하기 위한 window가 필요하다.)

 

sender window

N개의 window size를 가지는 window의 모습이다. window에 속하는 가장 왼쪽에 위치한 send_base는 sender가 packet을 보냈지만 ACK를 받지 않는 제일 처음으로 보낸 패킷이다. 그리고 nextseqnum 은 sender가 아직 보내지않았지만 보내려하는 또는 application에서 요청을 하지 않아 비어있는 공간의 시작점이다. 

그리고 맨 왼쪽에 있는 초록색 패킷들은 sender가 receiver에게 전송을 하고, ACK도 정상적으로 받은 패킷들이다. 

 

Go-Back-N에서는 ACK의 개수를 줄이기 위해서 누적된 ACK를 보낸다. 다시 말해 receiver입장에서 seq numb이 1, 2, 3, 4, 5인 패킷들을 받았으면 ACK5 하나만을 보낸다.

그리고 타이머는 내가 보낸 ACK를 받지 않은 packet중에서 가장 오래된 timer를 기준으로 timeout을 결정한다. timeout이 n 패킷에 대해서 났으면 n이상인 패킷들을 재전송한다.

 

receiver 의 sliding window

recieve 입장에서의 sliding window를 보자. receive는 앞서 말했다싶이 누적된 ACK를 보내서 지금까지 순서대로 올바르게 받은 패킷 중 가장 높은 seq numb의 패킷 번호를 보낸다. 따라서 계속 loss가 발생한 경우 중복된 ACK를 보낼 수 있다. 

receiver 입장에서는 오직 rcv_base만 기억할 필요가 있다. rcv_base는 receiver가 받지 않은 seq_numb가 가장 작은 패킷이다. 이에 대한 패킷이 왔는지 안왔는지를 파악하는 것이 주 목적이기 때문이다. 

 

out of order는 순서에 어긋난 패킷을 말하는데 이를 버릴지 저장할지는 구현에 따라 달라진다. 두가지 경우가 있을 수 있겠는데 out of order이더라도 일단 저장하는 경우가 있을 수 있겠고, 그냥 순서에 어긋나므로 버리는 경우가 있을 수 있겠다. 

 

receiver sliding window의 경우 transport layer 의 윗 단계인 application layer가 data를 읽어가지 않는 경우 멈춘다. 이는 data를 저장할 수 있는 공간은 한정되어있고 application layer단에서 문제가 있어 읽어가지 못하고 있는 상황에서 한정된 양이상의 패킷을 저장해버리면 넘치게 되어 loss가 발생되는 것을 막기위한 flow control과도 관련이 있는 동작이다. 

 

아무튼 out of order를 저장하던 버리던간에 receiver입장에서 rcv_base가 계속 안와서 n번째 seq numb인 패킷에 timeout이 발생한 경우 n부터 모든 데이터 패킷을 재전송한다. 

 

그러면 어떻게 action이 이루어지는 지  살펴보자.

 

pkt을 0번부터 잘 보내다가 pkt2가 loss된 모양이다. pkt0에 대한 ACK가 날아올때까지 sender의 window는 움직이지 않는다. 

그리고 receiver의 window를 보면 pkt2가 loss된 이후로 ack를 ack1만 계속 보내고 있는 모습을 볼 수 있다. 앞서 말했던 중복된 ACK가 발생하는 경우이다. 이런 중복된 ACK의 경우 sender입장에서는 무시한다. 

pkt2에 대한 timeout이 발생하였고 다시 pkt2부터 이후 패킷들을 보내는 모습을 볼 수 있다. 

 

Selective Search

Go-Back-N의 경우 n번째 packet이 유실되어 timeout이 발생한 경우 n번째 이상의 패킷들을 재전송하였다. 그런데 그럴 필요가 없겠다는게 바로 Selective Search이다. Go-Back-N방법과 Selective Search 방법이 적절하게 혼합되어서 TCP에서 사용되고 있다. receiver는 모든 잘 도착한 패킷에 대해 개별적으로 인지한다. 따라서 모든 패킷에 대한 타이머가 개별적으로 운용되어야한다. 

sender window에는 다양한 패킷들이 있는데 receiver에게 보냈지만 ACK를 받지 않은 패킷들은 또다시 재전송할 수 있는 패킷들이므로 저장되어있으며 receiver에게 정상적으로 도착했고 ACK를 받았더라도 앞에 ACK를 받지 못한 보내진 패킷들이 있으면 window가 slide가 안된다.

sender입장에서 window

따라서 send_base는 보냈지만 ACK를 받지 못한 seq_numb가 가장 작은 패킷을 의미하고, nexseqnum은 사용가능하지만 보내지지는 않은 패킷들의 첫번째를 의미한다. 더 구체적으로 이야기해보자면 상위 application에서 아직 주지 않아 비어있는 공간이거나 상위 application에서 이미 데이터를 주어서 보낼 준비가 되어있는 패킷들의 공간일 것이다. 

 

Go-Back-N과 다른 것 중 하나가 n번쨰 패킷이 타임아웃이 난 경우 n번째 패킷만 재전송하고 타이머를 재시작한다. 

또한 sender window에서 받은 ACK(n)은 Go-Back-N과 달리 n번째 패킷만 잘 받았다는 의미이다. ACK를 받지 못했던 send_base가 ACK를 받은 경우, 그 다음으로 위치한 ACK를 받지못한 패킷까지 window가 sliding된다. 

 

receiver window의 경우 두가지 위치에 패킷이 위치할 수 있겠는데

rcv_base와 rcv_base + N-1사이에 위치하는 패킷n이 있을 경우, 패킷을 전달받으면 ACK(n)을 보내고, out of order의 패킷인 경우 buffer에 저장하며, in order의 패킷인 경우에 application측에 전달하고 window를 slide한다. 

rcv_base - N과 rcvbase - 1에 위치한 패킷 n이 있을 경우, ACK(N)을 전송한다. 이렇게 전송하는 ACK는 sliding window밖이라는 점에서 이미 이전에도 데이터가 정상적으로 도착했지만 ACK가 유실된 경우의 패킷일 것이므로 ACK를 제대로 전송해주어야한다. 

나머지의 경우에는 ACK번호가 corrupt된 상황일것이므로 무시한다. 

 

Selective repeat 를 동작할때 만약 window size < seq numb인 상황이라면 다음과 같은 문제가 발생한다. 

pkt0은 잘 전송되었으나 ACK(0)이 유실된 경우 sender입장에서는 window가 slide가 안되고, 0 패킷을 재전송해야하는데, receiver에서 0 패킷을 재전송받으면 이전의 0번 패킷이 아닌 새로운 0번 패킷이라고 착각하게 되어 구분할 수 없는 딜레마가 생기게된다. 

 

따라서 sender가 보낸 패킷이 receiver에게 전부 보냈지만 ACK가 다 이상전송되었을때를 커버하려면 

# of seq number >= 2* window size 를 만족해야한다.