Pipelined Protocol

Pipelined protocol이란 sender 가 여러개의 패킷을 한번에 보내는 것을 말한다. 

두가지 종류가 있는데 이는 Go-Back-N 과 Selective Repeat 방식이 있다. 

 

Go-Back-N

• Sender 는 N unakced 패킷을 가질 수 있다.
• Receiver는 cumulative(누적) ack만 보낸다
  • 받은 데이터에 gap 이있을시 보내지 않음
• Sender는 가장 오래된 unacked 패킷에 대한 타이머가 있고 timeout시 모든 unacked 패킷을 보낸다

Go-back-N

• 버퍼를 window라 칭하고, 버퍼의 크기를 window size라 칭한다.
• 버퍼의 시작점: send base
• 다음 패킷 번호: next_seq_num

다음은 Go-Back-N 의 FSM이다.

Sender

Receiver

GBN 동작과정

• Window size는 4라고 가정, 패킷을 순차적으로 보내는데, 2번 패킷이 유실되었다
• Sender는 window size 만큼의 패킷을 보내고 대기한다.
• Receiver는 0,1번 패킷에 대한 ack를 보내지만 유실된 2번 패킷에 대한 ack는 보내지 않는다.
• Sender는 ACK 0, 1 을 받았으므로 send_base를 옆으로 밀고 패킷4,5 를 보낸다
• 하지만 receiver는 2번 패킷을 받지 않았으므로 마지막으로 성공적으로 받은 패킷인 1번 패킷에 대해 ACK를 보낸다
  • 4번 5번 패킷은 버린다
• Sender는 중복된 ACK 이므로 무시한다.
• Timeout 이발생했으므로 sender는 2번 패킷부터 순차적으로 다시 보낸다. 

Selective Repeat

• Sender는 N unacked 패킷을 가질 수 있다
• Receiver는 각 패킷에 대하여 individual ack을 보낸다
• Sender는 각 unacked 패킷에 대한 타이머가 있고 timeout 시 unacked 인 패킷만 다시 보낸다

Selective Repeat 동작과정

• GBN은 좋으나 비 효율적
• Selective Repeat은 모든 패킷이 아닌 ACK 받지 못한 패킷에 대해서만 재전송을 한다.
• 수신측도 버퍼가 있으며 모든 패킷에 대해 timer가 존재
  • Overhead 가 크다.

• GBN과 같은 상황.
• Sender는 윈도우 크기인 4만큼 패킷을 보내고 기다린다.
• Receiver는 0번, 1번 패킷이 올바르게 왔으므로 ACK0,1을 보낸다
• 2번 패킷이 오지 않았지만 sender가 이후 보낸 3번 4번 5번 패킷에 대해서 ack를 보낸다.
  • 하지만 2번 패킷이 오지 않았으므로  sender는 send base를 더이상 밀지 않는다.
  • 이때, 3번,4번,5번은 전달이 아닌 버퍼에 저장
• sender측 2번 패킷에 대한 timeout이 발생, 재전송
• Receiver는 2번 패킷을 받고 버퍼에 있는 모든 패킷(3,4,5)를 상위 계층으로 보낸다.
• ACK 2 가 도착한 뒤 sender는 send_base를 밀기 시작

Selective repeat 방식의 문제점은 모든 ACK 가 손실되었을 때 발생한다. 

다음 상황을 보자.

Selective Repeat 문제점

• Sender 가 0,1,2 패킷을 보냈고 receiver는 패킷을 정상적으로 받고 ACK 0,1,2 를 보내지만 모든 ACK 패킷이 유실되었다. 
  • 이때 rcv_base는 한칸씩 밀리게 된다.
• sender는 패킷0에 대해 ACK를 받지 못했으니 재전송하지만 receiver는 다음에 올 0번 패킷과 이전의 0번 패킷을 구분하지 못한다. 그렇기에 중복된 데이터가 발생한다.
• 그렇다면 해결 방법은?
  • window size < sequence num / 2
  •  

Selective Repeat 문제점 해결