GO-Back-N & Selective Repeat

1. GO-Back-N

• 패킷에 오류 또는 손실이 발생했을 때, 해당 패킷부터 모든 패킷을 재전송하는 방식을 가진 ARQ 형태의 프로토콜
  → ARQ (자동 반복 요청): 통신에서 발생하는 오류를 감지하고 복구하여 신뢰성을 제공해주기 위해 패킷 전송 중에 재전송을 요청하는 기술 및 프로토콜
  

  1. sender는 ACK를 받지 않은 상태로 동시에 최대로 보낼 수 있는 패킷의 수인 window size를 설정
  2. sender는 send_base 및 nextseqnum 설정
     → send_base: 송신자가 이미 보냈지만 아직 ACK를 받지 못한 가장 첫번째 패킷의 시퀀스 번호
     → nextseqnum: 송신자가 현재 전송할 수 있는 다음 패킷의 시퀀스 번호
  3. 수신자는 패킷들을 연속해서 받고, 각각의 패킷을 받을 때마다 sequence number를 확인하고 ACK를 전송
     → N번까지 잘받았다 → Culmulative Ack
     → 패킷이 유실되어 sequence number에 빈틈이 생기면, 빈틈이 생기기전 정상적으로 받은 가장 마지막 패킷 번호를 ACK에 담아 보낸다.
     → 수신자는 정상적으로 받은 마지막 패킷 sequence number를 rcv_base에 기록한다.
     → Go-Back-N 방식에서는 수신자가 버퍼를 가지고 있지 않는다.
  4. 송신자는 보낸 패킷의 ACK가 정상적으로 왔다면, 패킷 처리 후 window를 오른쪽으로 한 칸 sliding 한다.

• 예시
  

  1. window size: 4
  2. sender: 0, 1, 2, 3번 패킷을 한꺼번에 전송
     → 2번 패킷 loss
  3. receiver는 패킷들을 받고 0, 1번 패킷에 대해서는 ACK
     → rcv_base에 1 저장
  4. rcv_base + 1 = 2가 아닌 3번을 수신했음으로 packet loss 감지 & ACK(1)를 보낸다.
  5. sender는 ACK(0)과 ACK(1) 을 받고 중복된 ACK가 아니라면, 해당 번호의 패킷을 완료처리 & sliding window를 진행한다.
     → 4번 패킷 & 5번 패킷 전송
  6. 이후 다시 ACK(1)이 들어오게 되면 중복된 ACK를 감지하고 window를 sliding하지 않고 무시한다.
  7. ACK를 받지 못한 2번 패킷에 대해 timeout이 발생하면 2번 패킷부터 모든 패킷을 재전송한다.

• 장점: 손실된 데이터부터는 모두 송신측으로부터 재전송되므로 receiver는 해당 데이터들을 버퍼링 할 필요가 없다.

• 2번만 재전송할 수는 없을까? → Selective Repeat

---

2. Selective Repeat

• 정상적으로 도착한 패킷이더라도 손실 패킷 이후 모든 패킷들을 재전송해야 하기 때문에 비효율적일 수 있다.
  이를 개선하여 Selective Repeat 방식이 등장했다.

• Selective Repeat (SR): 자동 반복 요청(ARQ) 프로토콜의 한 형태로, 수신자가 수신한 각각의 패킷에 대해 개별적인 확인 응답(Individual Acknowledge)을 보내는 방식
  

  1. sender는 window size 설정
  2. window size 내에 들어있는 패킷들을 전부 송신 후 ACK을 기다림
     → 각각의 패킷에 대해 타이머를 가지고 있어 time-out을 활용해 재전송 한다.
  3. Selective repeat 방식에서는 수신자가 버퍼를 가지고 있다.
     • 수신 패킷 처리: 수신자는 들어오는 패킷의 시퀀스 번호를 확인하여 rcv_base에 저장된 시퀀스 번호와 어긋난다면 패킷들을 임시로 버퍼에 저장해 둔다
     • 순서에 맞는 패킷 도착 & ACK 전송: 이후에 순서에 맞는 패킷이 도착하면, 수신자는 버퍼에 저장된 패킷들을 모아 상위 계층으로 전달한다.
     • 윈도우 슬라이딩: ACK 전송 횟수만큼 송신자의 윈도우가 슬라이딩된다.
  4. 특정 패킷에 대해 ACK가 들어오면 그 패킷을 완료 기록
     → 송신자가 보낸 패킷들 중 아직 ACK되지 않은 패킷들 중 가장 번호가 작은 패킷이 ACK되면 window를 sliding

• 예시
  

  1. 송신자는 아직 2번 패킷에 대해 ACK가 오지 않았기 때문에, ACK3에 대해 완료 처리를 하지만 window는 이동시키지 않는다.
  2. 수신자의 경우 3, 4, 5번 패킷에 대해서 ACK를 보내지만, 상위 레이어에 deliver 하지는 않는다.
  3. 2번 패킷이 들어와 순서대로 패킷이 나열되었을 때, 버퍼에 저장한 패킷들과 상위 레이어로 한꺼번에 보내며 ACK들도 송신자에게 한꺼번에 보낸다.
  4. ACK2가 송신자에게 도착하면 2번 패킷을 완료처리 & window를 한 칸 sliding한다.
     → 6번 패킷 전송

• 문제점

  • ACK전송이 모두 실패하여, 0 데이터를 receiver는 현재 윈도우 내의 데이터로 인지할 수 있다.
    
    
    
  • 해결 방법: window size는 사용하는 sequence number 갯수의 반 이하여야 한다.
    → Sequence numbmer 4개 사용 & 윈도우 크기가 2: 시퀀스 넘버 0과 1을 가진 패킷을 전송한 후에 수신자는 시퀀스 넘버 2와 3을 가진 패킷을 받을 준비를 한다.
    즉, ACK가 유실되어 수신자가 0번 또는 1번 패킷을 수신 받더라도 수신자는 현재 윈도우 내의 데이터로 오인할 가능성이 줄어든다.