[Network] Go-Back-N, Selective Repeat

📡 Go-Back-N (GBN)

데이터를 전송하다가 중간에 하나가 사라졌다면, 어떻게 하면 좋을까?

• 무슨 일이 생기든 신경 안 쓰고 계속 보낸다 → 신뢰성과 멀어보임
• 잃어버린 것만 다시 보낸다 → 좋은 생각이지만, 아직은 아님
• 그 이후에 보낸 것도 다 다시 보낸다 → 이 방법이 Go-Back-N이다!

Go-Back-N(GBN)은 네트워크에서 자주 쓰이는 신뢰성 있는 데이터 전송 방식 중 하나다. 간단하게 말해서, 한 가지 문제만 생겨도 다시 몽땅 보내는 스타일이다.

 

 

GBN은 한 번에 하나씩만 보내는 게 아니라, 여러 개의 패킷을 동시에 전송할 수 있다. 단, 조건이 있다. 아직 도착 확인(ACK)을 받지 못 한 패킷이 N개 이하여야 한다. 택배로 예를 들면,

• base 아직 도착 확인 안 된 맨 앞 택배
• nextseqnum 다음으로 보낼 택배의 번호

와 같이 비유할 수 있다. GBN에서는 이 두 번호 사이에 생기는 공간이 바로 윈도우$_{window}$다. 윈도우 크기는 N이고, 이 창 안에 있는 번호만 보낼 수 있다. ACK가 오면 윈도우가 “슥” 앞으로 밀린다.

 

GBN에서 윈도우는 단순히 이미 보낸 패킷만 포함하는 게 아니라 지금 보낼 수 있는 패킷까지 포함한 범위다. 윈도우는 전송 가능한 시퀀스 번호의 범위 전체를 나타내는 거지, 보낸 것만 포함된 히스토리가 아니다.

 

GBN sender

sender는 세 가지 유형의 이벤트에 응답해야 한다.

• 상위 계층에서 보낼 데이터가 오면 (rdt_send(data), FSM 12시 방향)
  • 윈도우에 여유가 있다면, 패킷을 만들어 바로 전송한다.
  • 없다면, 그냥 기다린다.
• ACK(도착 확인)가 오면 (rdt_rcv(rcvpkt) && notcorrupt(rcvpkt), FSM 6시 방향)
  • 그 ACK 번호까지 전송된 패킷은 다 도착한 걸로 처리한다.
  • 윈도우도 앞으로 당기고, 타이머도 조정한다.
• 타임아웃이 발생하면 (timeout, FSM 3시 방향)
  • 이름처럼 Go-Back한다.
  • 확인받지 못한 패킷 전부를 다시 보낸다.
  • GBN에서는 base에 해당하는 패킷 하나만 타이머를 둔다.

 

GBN receiver

receiver 동작은 하나만 받아서 생각보다 간단하다.

• 순서대로 도착한 패킷만 받아서 상위 계층에 전달하고, ACK를 보낸다.
• 순서가 어긋난 패킷은 무조건 버리고, 가장 최근에 받은 순서대로의 ACK를 다시 보낸다.

 

왜 이렇게 간단하게 끝날 수 있을까?

• 수신자는 데이터를 순서대로만 전달할 수 있다.
• 앞에 껄 안 받았는데 뒤에 껄 받으면 곤란하니까, 그냥 버리고 기다린다.
• 어차피 GBN은 다시 전부 보내준다.

 

Go-Back-N에 대해 간단하게 한 줄 요약하면, 앞에 것들 놓칠 때 뒤에 것도 다시 보내는 프로토콜이다. 빠르고 단순하지만, 재전송이 많을 수 있다는 것이 단점이다. 다음은 Selective Repeat에 대해 알아보자.

 

📡 Selective Repeat

Go-Back-N에서는 하나라도 ACK가 안 오면, 뒤에 거까지 다 다시 보냈다. 그런데 생각해보면 좀 아깝다. 패킷 3만 유실됐는데 4, 5, 6도 꼭 다시 보내야 할까?

 

그 의문에 답한 프로토콜이 바로 Selective Repeat(선택적 재전송)이다.

Selective Repeat(선택적 재전송)은 송신자와 수신자 모두가 윈도우를 가지고 있다. 그리고 각 패킷을 개별적으로 관리한다. 수신자는 순서가 뒤바뀐 패킷을 저장하고 각 패킷에 대해 개별 ACK를 전송한다. 송신자는 패킷마다 따로 타이머를 설정한다.

 

예제로 어떻게 동작하는지 살펴보자.

(윈도우 크기 = 4)

• 송신자는 패킷 0, 1, 2, 3 전송
• 수신자는 0, 1을 받고 ACK 보냄
• 2는 유실됨, 3은 먼저 도착
  • GBN이었다면 버렸겠지만, SR은 3을 버퍼에 저장하고 ACK도 보냄
• 송신자는 0, 1의 ACK를 받고 4, 5 전송
• 2가 타임아웃으로 재전송됨 → 수신자 도착
  • 이제 2, 3, 4, 5까지 차례대로 상위 계층에 전달 가능하다!

 

이처럼 순서가 뒤섞여도 무너지지 않는 구조가 Selective Repeat의 장점이다.

 

문제점

이론적으로는 완벽하지만, 시퀀스 번호가 겹치는 문제가 생길 수 있다.

 

Selective Repeat에서는 패킷마다 번호(시퀀스 번호)가 붙어 있다. 하지만 이 번호는 무한하지 않다. 예를 들어 2비트라면, 사용할 수 있는 번호는 0, 1, 2, 3으로 총 4개 뿐이다.

 

그래서 패킷을 계속 보내다 보면 번호가 다시 0으로 돌아온다. 이걸 시퀀스 번호가 순환한다고 말한다.

예를 들어,

• 시퀀스 번호가 0~3 (4개뿐)
• 윈도우 크기 = 3

라고 가정해보자.

 

수신자가 패킷 0을 받고 버퍼에 넣었는데, 그 다음에 송신자는 중간에 ACK(확인 메시지)를 못 받았다고 해보자. 0번에 대한 확인을 받지 못 했기 때문에, 새로운 0번 패킷을 다시 보낼 수 있다.

 

동시에 송신자는 계속해서 다음 패킷도 보내고 또 보내고.. 어느 순간 윈도우가 밀리면서 진짜 새로운 0번 패킷이 만들어지게 된다.

 

그렇게 되면 수신자는

 

‘지금 도착한 0번 패킷.. 예전에 저장한 0번이랑 같은 패킷인가?
아니면 새로 보낸 완전 다른 0번 패킷인가?’

 

라고 생각하게 된다. 번호는 똑같이 0이지만, 시점은 완전 다른 상황이 생겨버린다.

 

해결책

생각보다 간단하다. 시퀀스 번호의 범위가 충분히 크면 된다.

 

$$ seqnum ≥ 2 × window size $$

 

즉, 윈도우 크기가 4라면, 시퀀스 번호는 최소 8개 이상 필요하다는 것이다. 이 조건이 지켜지면 수신자는 새로운 0번을 제대로 구분할 수 있을 것이다.

 

📡 마무리

Go-Back-N은 ‘일단 쭉 보내고 안 되면 전부 다시’라면, Selective Repeat은 ‘쓸데없이 보내지 말고, 진짜 잃어버린 것만 다시’다. 둘 다 장단점이 확실하기 때문에, 어떤 걸 쓸지는 네트워크 환경과 상황에 따라 선택해야 한다.

 

특징	Go-Back-N	Selective Repeat
재전송 방식	누락된 것 이후 모두 재전송	누락된 것 하나만 재전송
수신자 처리	순서 안 맞으면 전부 폐기	순서 안 맞아도 버퍼에 저장
타이머	하나만 운용	패킷마다 따로 타이머 운영
윈도우 관리	sender만 신경 씀	sender & receiver 둘 다 윈도우 필요
복잡도	비교적 단순	구현은 더 복잡하지만 효율적

 

references

Computer Networking: A Top-Down Approach, 8th edition

COMP0414 수업 내용