[네트워크] GBN(Go-back-N), SR(Selective Repeat) - Pipelined Protocols

Pipelined Protocols

앞서 서술하였듯이, RDT 2.1 모델부터는 송신자가 하나의 packet을 보내고나면 수신자의 응답을 기다리는 "Stop and Wait" 방식을 사용한다고 하였다.

https://oneonlee.tistory.com/m/111

[네트워크] Reliable Data Transfer의 원리와 RDT 모델 알고리즘

 

하지만 이 방법은 ACK가 올 때까지 송신자가 계속해서 놀고 있기 때문에 굉장히 비효율적인 방법이다.

 

따라서, 한번에 하나의 패킷만 보내는 것이 아니라 여러 패킷을 pipelining하여 처리하는 방식을 살펴볼 것이다.

© All material copyright 1996-2012 J.F Kurose and K.W. Ross, All Rights Reserved

대표적인 Pipelined Protocol으로는 GBN(Go-Back-N)과 SR(Selective Repeate) 방식이 있다.

 

GBN(Go-back-N)

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

• (1) 수신자 측은 정상적으로 받지 못한 패킷이 있을 경우, 해당 패킷이 올 때까지 다른 패킷들을 받더라도, 받지 못한 패킷의 직전 패킷에 대한 ACK를 보낸다.
  • 수신자는 받은 ACK의 순서가 뒤섞이는 것을 허용하지 않는다.
    • 이러한 성질 때문에 cumulative ACK(연속적인 ACK)이라고도 한다.
  • 예를 들어 패킷 1,2,3,4,5를 전송했는데, 수신자 측에서 1,2,4,5를 받았다면, 수신자 측은 ACK 1,2,2,2를 보낸다.
    • 송신자 입장에서 ACK 1,2,3이 안오고 ACK 4만 오더라도 수신자가 패킷 1,2,3,4를 정상적으로 받았다는 것을 알 수 있다. (ACK가 오다가 손실된 경우)
• (2) 송신자는 전송한 패킷 중, ACK 되지 않은 가장 최신의 패킷에 대해 하나의 타이머를 계산한다.
  • 만약 해당 타이머가 만료될 때까지 ACK가 오지 않으면, window 내의 unack된 모든 패킷을 재전송한다.
  • 만약 해당 타이머가 만료되기 전에 ACK가 온다면, 다음 ACK 되지 않은 가장 최신의 패킷에 대해 타이머를 계산한다.
• (3) 구조가 간단하고 구현이 단순하며, 따로 패킷을 보관할 버퍼가 필요 없다.
  • 올바른 패킷이 오면 삼키고, 틀린 패킷이 오면 뱉는 구조이기 때문이다.
• (4) 송신자의 Window Size는 사용되는 sequence number보다 무조건 커야한다.
  • N = (2^k)-1
  • 만약 Window size가 같거나 작으면, 수신자가 오해할 수 있는 상황이 생긴다. (ACK가 모두 소실된 경우)

SR(Selective Repeat)

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

• (1) 송신자 측은 ACK가 순서대로 오든 말든, 그냥 받은 패킷에 대한 ACK을 보낸다.
  • 예를 들어 패킷 1,2,3,4,5를 전송했는데 송신자 측에서 1,2,4,5가 왔다면, 송신자 측은 ACK 1,2,4,5를 보낸다.
• (2) 송신자는 ACK을 받지 못한 모든 패킷에 대해 타이머를 각각 계산한다.
  • 만약 각각의 타이머가 만료될 때까지 ACK가 안오면, 각각 패킷을 재전송한다.
• (3) 따로 받은 패킷을 보관할 버퍼가 필요하다.
  • 올바르지 않은 패킷이 와도 일단 저장해놓고, 나중에 부족한 부분이 채워지면 함께 삼키는 구조이기 때문이다.
• (4) 사용되는 sequence number는 송신자의 Window Size와 송신자의 Widow Size 크기의 합보다 무조건 크거나 같야한다.
  • Max allowable window size N을 (2^k)-1이 아니라, (2^k)/2 = 2^(k-1)로 해야 한다. (half the seq# space)
  • 만약 sequence number의 크기가 더 작다면, 송신자가 오해할 수 있는 상황이 생긴다.

---

시각화 자료

• YouTube - "Go back N sliding window Protocol by Khurram Tanvir"

• YouTube - "Go Back N demonstration"

• YouTube - "Selective Repeat sliding Window Protocol by Khurram Tanvir"

---

참고 자료

1. Computer Networking: A Top Down Approach 6th edition - Jim Kurose, Keith Ross Addison-Wesley March 2012
2. https://ddongwon.tistory.com/m/81
3. https://m.blog.naver.com/mayooyos/220987008864