[Network] pipelined protocol

기존 패킷을 보내는 과정은 패킷을 보내고 ACK를 받고, 패킷을 보내고 ACK를 받고 이러한 과정을 반복했다.

 

이러한 방식을 개선하기 위해서 pipelined protocol은 여러 개를 한꺼번에 보내고 여러 ACK를 한꺼번에 받는 방식을 사용한다.

 

https://en.wikipedia.org/wiki/Protocol_pipelining#/media/File:HTTP_pipelining2.svg

이러한 파이프라이닝의 형식에는 두가지가 있다.

 

go-back-N과 selective repeat이다.

 

go-back-N (GBN)

우선 N개를 보내고 ACK를 받는 방식이다.

 

노란색은 패킷을 보냈으나 아직 ACK를 받지 않은 상태이고 파란색은 아직 보내지 않은 상태이다.

 

노란색인 패킷을 in-flight 패킷이라고 한다.

 

ACK를 받게되면 노란색에서 초록색으로 바뀌고 send_base가 하나 증가한다.

 

send_base가 증가함에 따라 window size는 한 칸 옆으로 이동하게 되는 것이다.

 

sender FSM

 

receiver FSM

GBN 방식의 단점은 duplicate이다.

 

N개를 한번에 보내기 때문에 이러한 문제가 발생한다.

 

window size가 5라고 해보자.ㄷ

 

sender는 5개의 패캣을 한번에 보낼 것이다.

 

1, 2, 4, 5번 패킷은 성공적으로 보냈으나 3번 패킷에서 오류가 났다고 해보자.

 

receiver는 4, 5번을 받았음에도 계속 2번까지만 받았다고 응답을 보낼 것이다.

 

그러면 sender는 3번 패킷부터 다시 보내야하기 때문에 receiver가 다시 받은 패킷 다시 보내는 문제가 발생하게 되는 것이다.

 

이를 개선하기 위해 나온 방식이 selective repeat이다.

 

selective receive

GBN 방식과 다르게 선택적으로 받지 못한 패킷을 보내달라고 요청하는 것이다.

 

GBN 방식은 한 패킷을 받지 못하면 그 이후의 패킷도 다시 보내야하는 반면에 selective receive 방식은 받지 못한 패킷만 다시 보내달라고 요청하는 것이다.

 

sender는 패킷을 보내고 개별적으로 타이머를 시작한다.

 

window size에 포함되는 ACK를 받으면 패킷을 받았다는 표시를 하고 만약 받은 ACK가 window size 내에서 가장 작은 값이라면 window base를 그 다음 ACK를 받지 않은 sequence number로 바꾼다.

 

만약 1, 2, 3, 4 패킷을 보냈고 1, 4번 ACK를 받지 않은 상태라 하자.

 

이 상황에서 window base는 1이고 1번 ACK를 받았다면 window base를 바로 4번으로 옮기는 것이다.

 

receiver는 window size 내부에 있는 패킷을 받았다면 해당 ACK를 보내준다.

 

그리고 순서가 맞춰진 패킷들이 있으면 한 번에 application layer로 보내주고 그렇지 않다면 버퍼에 그대로 둔다.

 

순서가 맞춰진 패킷들을 application layer로 보냈다면 이제 window base를 그 다음 패킷을 받지 않은 sequence number로 바꾼다.

 

그런데 sender가 패킷을 받았는데 window size 바깥에 있는 패킷을 받았다면 어떻게 할까?

 

아래와 같이 sender의 window size 앞 두 노란색 패킷은 중간에 유실되어서 타임아웃이 발생하여 다시 패킷을 보낼 수가 있다.

이럴 경우에도 ACK를 보내줘야 한다. 참고로 receiver가 ACK를 보내주는 sequence number의 범위는 다음과 같다.

sender와 receiver를 자세히 살펴보면 그 이유를 알 수 있는데 만약 sender에서 ACK를 받지 못하는 패킷이 있다면 sender의 window base가 그 패킷의 sequence number를 지나칠 수는 없다.

 

즉 최악의 경우는 다음과 같다.

이 최악의 경우 sender와 receiver 모두 sender가 sequence number가 window base인 패킷이 응답을 받기 전까지는 다음으로 나아가지 못하게 된다.

 

그렇기 때문에 receiver가 ACK를 보내주는 sequence number의 범위가 2*N이 되는 것이다.

 

sender와 receiver는 이러한 방법을 사용하여 계속 버퍼의 공간을 유지하는 것이다.