[네트워크] pipelined protocols(Go-Back-N, Selective Repeat)이란? | selective repeat 딜레마(dilemma)

pipelined protocols

pipelined protocols에서 pipelining은 송신자가 다수의 패킷을 한 번에 보내는 것을 말한다. 즉 ACK신호를 받을 때까지 기다리다 ACK신호를 받고 나서 다음 데이터를 보내는 stop and wait 방식과 다르게 송신자가 ACKs 신호를 받지 않아도 패킷 여러 개를 보내는 방식이다. 송신자와 수신자가 버퍼를 가져야 하며, 대표적인 두 가지 프로토콜로 Go-Back-N과 Selective Repeat이 있다. 

 

참고 : stop and wait 방식의 RDT

[네트워크] Reliable Data Transfer - rdt 1.0/2.0/2.1/2.2/3.0 | RDT란? | FSM 이란?

 

Go-Back-N (GBN)

Go-Back-N

• Go-Back-N 방식은 송신 측에서 전송할 패킷의 개수를 정한다.
• 버퍼에 그 개수만큼의 패킷을 저장하여 전송한다.
• 버퍼를 window, 버퍼의 사이즈를 window size라고 한다. 
• 버퍼의 시작점인 send_base, 다음에 보낼 패킷 번호인 next_seq_num을 가진다.
• 수신 측은 이번에 받을 패킷의 번호를 기억하고 있는다.
• 이때 수신측은 누적 ACK(Cumulative ACK)을 사용한다. 
• 각 버퍼가 전송될 때 ACK를 받지 못한 가장 오래된 패킷의 Timer를 기준으로 Timeout이 발생한다.
• Timeout 이 발생하면 window에 있는 모든 패킷을 전송한다.

이해가 쉽지 않다면 다음과 같이 동작하는 예시를 보면 이해가 빠를 것이다.

GBN in action

• window size가 4인 상황에서 GBN의 동작이다. 가장 먼저 패킷 0,1,2,3을 전송한다. 전송 도중에 패킷 2가 손실되었다.
• 수신 측은 패킷 0과 1을 잘 받았으므로 ACK 0,1을 보내고 패킷 2가 오기를 기다린다.
• 송신 측은 ACK 0을 받았으므로 send_base를 한 칸 옆으로 밀고 (send_base가 0에서 1이 됨) 패킷 4를 보낸다.
• 송신 측은 ACK 1을 받았으므로 send_base를 한 칸 옆으로 밀고 (send_base가 1에서 2가 됨) 패킷 5를 보낸다.
• 수신 측은 패킷 2를 기다렸으나 패킷 2가 오지 않고 패킷 3이 왔으므로 패킷 3을 버리고 가장 최근에 수신 성공한 패킷 1에 대한 ACK1(Culmulative ACK)을 보낸다.
• 수신 측은 패킷 2를 기다렸으나 패킷 2가 오지 않고 패킷 4가 왔으므로 패킷 4를 버리고 가장 최근에 수신 성공한 패킷 1에 대한 ACK1(Culmulative ACK)을 보낸다.
• 수신 측은 패킷 2를 기다렸으나 패킷 2가 오지 않고 패킷 5가 왔으므로 패킷 5를 버리고 가장 최근에 수신 성공한 패킷 1에 대한 ACK1(Culmulative ACK)을 보낸다.
• 송신 측은 중복된 ACK은 모두 무시한다.
• 송신 측은 pkt2를 보내고 일정 시간이 지나도 ACK이 오지 않아 Timeout이 발생한다.
• Timeout이 발생했으므로 윈도우의 모든 패킷을 전송한다. 즉, 패킷 2,3,4,5를 보낸다.  

Selective Repeat (SR)

Selective Repeat

• GBN의 비효율성을 해결하기 위한 방식이다.
• 송신측은 각 패킷마다 timer를 설정하고 timeout 된 패킷만 재전송한다. (GBN처럼 버퍼 모두를 전송하지 않음)
• 수신 측도 버퍼(window)를 가지고 있다. 
• 수신 측은 기다리던 패킷이 오면 바로 상위 계층으로 전달하고 ACK 신호를 보낸다.
• 수신 측은 기다리고 있던 패킷이 오지 않으면 일단 buffer에 넣어놓고 ACK 신호를 보낸다.
• 수신 측의 버퍼가 가득 차면(패킷이 모두 도착하면) 상위 계층으로 전달한다.
• 이외는 GBN과 비슷하다.
• GBN보다 효율적으로 보이지만 모든 패킷에 timer가 있기 때문에 overhead가 크다.

마찬가지로 예시를 들어 이해해보자.

SR in action

• window size가 4인 상황에서 SR의 동작이다. 가장 먼저 패킷 0,1,2,3을 보낸다. 전송 도중 패킷 2가 손실되었다.
• 수신 측은 패킷 0과 1을 잘 받았으므로 ACK 0,1을 보내고 패킷 0과 1을 상위계층에 전달한 다음 패킷 2가 오기를 기다린다.
• 송신 측은 ACK 0을 받았으므로 send_base를 한 칸 옆으로 밀고 (send_base가 0에서 1이 됨) 패킷 4를 보낸다.
• 송신 측은 ACK 1을 받았으므로 send_base를 한 칸 옆으로 밀고 (send_base가 1에서 2가 됨) 패킷 5를 보낸다.
• 수신 측은 패킷 2를 기다렸으나 패킷 2가 오지 않고 패킷 3이 왔으므로 패킷 3을 버퍼에 넣어놓고 ACK 3을 보낸다.
• 수신 측은 패킷 2를 기다렸으나 패킷 2가 오지 않고 패킷 4가 왔으므로 패킷 4를 버퍼에 넣어놓고 ACK 4를 보낸다.
• 수신 측은 패킷 2를 기다렸으나 패킷 2가 오지 않고 패킷 5가 왔으므로 패킷 5를 버퍼에 넣어놓고 ACK 5를 보낸다.
• 송신 측은 ack3,4,5는 기록(mark)만 하고 send_base(pkt2)에 대한 ACK이 오지 않았으므로 send_base를 밀지는 않는다.
• pkt2에 대한 timer가 timeout이 됐으므로 패킷2를 다시 보낸다. 
• 수신 측은  패킷2를 받고, 버퍼에 있는 패킷까지 포함해 패킷 2,3,4,5를 상위계층에 보낸 다음 ACK2를 보낸다.
• 이후 ACK2가 송신 측에 도착하면 ACK 3,4,5는 mark 해두었기 때문에 send_base가 2에서 6이 된다. 

 

Selective Repeat Dilemma(SR 딜레마)

SR은 GBN에 비해 매우 효율적으로 보인다. 하지만 SR은 큰 딜레마를 가지고 있다.

우선 window size가 3이고 sequence number는 0,1,2,3 이라고 하자. 또한 수신 측과 송신 측이 서로를 볼 수 없다고 가정하자. 위의 SR 동작에서 보이진 않았지만, 수신 측도 기다리던 패킷을 받으면 window 에서 rcv_base를 옆으로 한 칸 씩 밀게 된다. 즉, 위 그림과 같은 상황에서는 아무 문제가 발생하지 않는다.

 

하지만 위와 같이 ACK 0,1,2가 모두 손실된다면 문제가 발생한다.

수신 측은 패킷 0,1,2를 제대로 받았으므로 ACK 0,1,2를 보내고 rcv_base를 한 칸씩 밀어 rcv_base는 3이 될 것이다.

송신 측은 패킷 0,1,2를 보내고 ACK 신호가 오지 않으므로 timeout되고 패킷 0을 다시 보낼 것이다.

문제는 수신 측의 window 안에 0이 들어 있다는 것이다.

수신 측은 송신측의 상황을 모르기 때문에 이번에 들어온 패킷0가 올바른 패킷으로 판단하고 패킷 0을 버퍼에 넣을 것이다.

하지만 이번에 들어온 패킷 0는 이미 예전에 받은 패킷0와 똑같은, 즉 중복된 패킷을 받게 되는 문제가 발생한다.

 

해결방법은 무엇일까? 그것은 바로 다음과 같다.

SR은 window size가 sequence number의 개수의 절반보다 이하여야한다. 
window size <= (sequence number)/2

예를 들어 위의 같은 상황에서 window size를 2로 줄이면 문제가 해결된다. 

 

---