패킷 pipelining (go-Back-N, selective repeat)

1. Stop and Wait

 

앞서 기본적으로 reliable한 패킷 데이터 교환을 위해서는, 우선 패킷을 보내고 그에 해당하는 ACK이 올때까지 기다리는 Stop and Wait 방식을 사용한다고 하였다.

 

하지만 이 방법은 ACK이 올때까지 송신자는 계속해서 놀고있으므로 굉장히 비효율적인 방법이다. 따라서, 한번에 하나의 패킷만 보내는 것이 아니라 여러 패킷을 pipelining 하여 처리하는 방식을 살펴볼 것이다. 대표적인 pipelining 방식으로는 GBN(Go-Back-N)과 SR(Selective Repeate) 방식이 있다.

 

 

 

2. GBN(Go-Back-N)

 

Go-Back-N 방식은 receiver 측에서 순서대로 받지 못한 패킷이 있다면 해당 패킷부터 다시 재전송 하는 방식이다.

 

1) receiver 측은 정상적으로 받지 못한 패킷이 있을경우, 해당 패킷이 올때까지 다른 패킷들을 받더라도, 받지 못한 패킷의 직전 패킷에 대한 ACK을 보낸다.

즉, ACK 사이에 갭이 있는걸 못참는 녀석이다. 이러한 성질 때문에 cumulative ACK이라고도 한다. 

 - 예를 들어 패킷 1,2,3,4,5를 전송했는데 receiver 측에서 1,2,4,5를 받았다면, receiver 측은 ACK 1,2,2,2를 보낸다.

 - sender 입장에서 ACK 1,2,3이 안오고 ACK 4만 오더라도 receiver가 패킷 1,2,3,4를 정상적으로 받았다는 것을 알 수 있다. (ACK이 오다가 손실된 경우)

 

 

2) sender는 전송한 패킷 중, ack 되지 않은 가장 최신의 패킷에 대해 타이머를 계산한다.

 - 만약 해당 타이머가 만료될 때까지 ack이 안오면, window 내의 unack된 모든 패킷을 재전송한다.

 - 만약 해당 타이머가 만료되기 전에 ack이 오면, 다음 ack 되지 않은 가장 최신의 패킷에 대해 타이머를 계산한다.

 

 

3) 구조가 간단하고 구현이 단순하며, 따로 패킷을 보관할 버퍼가 필요 없다.

 - 올바른 패킷이 오면 삼키고, 틀린 패킷이 오면 뱉는 구조이기 때문.

 

 

4) Sender의 Window Size는 사용되는 sequence number보다 무조건 작거나 같아야한다.

 - 만약 Window size가 sequence number 의 개수보다 크면, receiver가 오해할 수 있는 상황이 생긴다.

 - 예를들어 window size 가 4이고, sequence number가 0~3이라면, (window size > seq number space인 경우)

 - sender는 0, 1, 2, 3 을 한번에 보냈고, receiver는 이를 제대로 받고 ack 0 ,1, 2, 3을 보냈지만, ack들이 모두 유실된 경우를 생각해보자.

 - sender 는 ack이 하나도 안오니까 timeout 이후에 다시 0을 보낼 것이다.

 - 그러면 receiver는 재전송된 0을 재전송되었다고 생각하지 않고, 이전의 3 다음에 오는 0이라고 잘못 생각하게 된다.

 - 더 자세한 예시는, 다른분이 댓글에 적어주신 두번째 링크를 확인해보길 바란다.

 

 

말로만 해서는 이해가 잘 가지 않으므로, 아래 예시를 그림으로 살펴보자.

아래 그림은 GBN을 적용한 상태에서 Sender가 전송한 패킷2번이 중간에 소실된 상황이다. Sender는 ack1이 도착한 순간부터 패킷 2번에 대한 타이머를 계산하고, 일정시간이 지나면 타이머가 만료되면서 Sender의 Window 속에 있는 패킷들이 모두 재전송된다.

 

GBN in action1

 

 

다음으로 아래 그림은 GBN이 적용된 또다른 예시이다. 이 경우, 여러 ack이 중간에 손실되어 정상적인 ack이 하나만 도착해도 이전의 받지 못한 ack을 받은 것으로 처리하는 것을 알 수 있다. 이는 앞서 말한 cumulative ACK이기 때문에 가능하다.

 

GBN in action2

 

 

 

3. SR (Selective Repeat)

 

Selective Repeat 방식은 receiver 측에서 받은 각각의 패킷들에 대해 ACK을 보내는 방식이다.

 

1) receiver 측은 ACK이 순서대로 오든 말든, 그냥 받은 패킷에 대한 ACK을 보낸다.

 - 예를 들어 패킷 1,2,3,4,5를 전송했는데 receiver 측에서 1,2,4,5가 왔다면, receiver 측은 ACK 1,2,4,5를 보낸다.

 

2) sender는 ACK을 받지 못한 모든 패킷에 대해 타이머를 계산한다.

 - 만약 각각의 타이머가 만료될 때까지 ack이 안오면, 각각 패킷을 재전송한다.

 

3) 따로 받은 패킷을 보관할 버퍼가 필요하다.

 - 올바르지 않은 패킷이 와도 일단 저장해놓고, 나중에 부족한 부분이 채워지면 함께 삼키는 구조이기 때문.

 

4) 사용되는 sequence number는 Sender의 Window Size와 Receiver의 Widow Size 크기의 합보다 무조건 크거나 같야한다.

 - 만약 sequence number의 크기가 더 작다면, receiver가 오해할 수 있는 상황이 생긴다.

 

 

Selective Repeat 방식 역시 예를 들어 살펴보자.

아래 그림은 Sender가 보낸 패킷 중 하나가 소실된 경우이다. 각각의 패킷들이 전송되는 순간에 타이머가 가동되고, 소실된 패킷의 타이머가 만료되면 해당 패킷만 재전송 한다.

또한, 순서대로 올 경우 바로 상위 레이어로 deliver하고, 순서대로 오지 않을 경우 나머지를 버퍼에 모아뒀다가 한번에 deliver 한다.

 

SR in action

 

이 외에도 Selective Repeat 방식에서 ack이 소실되는 경우가 있는데, 이럴 경우 해당 패킷의 타이머가 만료된 후 재전송한다. receiver는 이미 받은 패킷이므로 그냥 ack만 다시 보내주는 형태로 동작한다.

 

 

오늘 배운 내용을 정리해보면,

 

1. reliable 통신에서 패킷을 더 효율적으로 송수신하기 위해 pipelining을 사용한다.

 

2. pipelining을 하는 방법으로 Go-Back-N과 Selective repeat 방식이 있다.

 

위 내용은 공부하며 정리한 것으로, 오류가 있을 수 있습니다.