[네트워크] ARQ: Stop-and-wait, Go-back-N, Selective repeat

전송계층(Transport Layer)에서 세그먼트*를 전송할 때, 조금 더 신뢰성 있는 통신, 즉 Reliable Data Transfer를 위해 다양한 방식의 프로토콜을 사용한다. 물론 TCP를 쓸 때는 TCP가 그 자체로 이미 신뢰성 있는 프로토콜이기 때문에 별도의 프로토콜을 더하지 않아도 되지만, UDP 등의 신뢰성이 떨어지는 녀석들을 활용하기 위해서는 더 높은 신뢰도를 위해 추가적인 프로토콜들을 더해주어야 한다. 이러한 프로토콜들을 Automatic Repeat reQuest, 줄여서 ARQ라고 부른다. ARQ는 전송되는 데이터의 정확성과 순서를 보장하는 역할을 한다. 물론 Noisy channel에서만 ARQ를 쓰고, Noiseless channel에서는 non-ARQ를 쓰는데, 여기선 ARQ에 대해서만 다룬다.

 

* 네트워크 계층마다 데이터를 부르는 이름이 모두 다르다:

  물리 계층 - 비트, (데이터) 링크 계층 - 프레임, 네트워크 계층 - 패킷, 전송 계층 - 세그먼트, 응용 계층 - 데이터

  근데 전송 계층에서도 프레임 혹은 패킷이라는 용어를 쓰기도 하던데, 이 부분은 좀 더 알아봐야겠다.

 

ARQ 1: Stop-and-wait

작동 원리

1. 단일 패킷 전송: 송신자가 하나의 패킷을 수신자에게 전송.
2. 수신 확인 대기: 송신자는 해당 패킷에 대한 수신자의 확인 응답(ACK)을 기다림.
3. ACK 수신:
   • 성공적 수신: 수신자가 패킷을 올바르게 받으면, ACK를 송신자에게 보냄. 송신자는 다음 패킷을 보낼 수 있음.
   • 수신 실패: 패킷이 손상되었거나 분실된 경우, 수신자는 응답을 보내지 않거나 음의 응답(NAK, Negative Acknowledgement)을 보냄. 이 경우, 송신자는 같은 패킷을 다시 전송.
4. 타임아웃: 송신자는 타임아웃을 설정하여 ACK 응답을 일정 시간 내에 받지 못하면 패킷을 재전송.

특징 및 한계

• 간단함: 구현이 매우 간단하고, 데이터를 순차적으로 처리해서 패킷 순서 문제 발생하지 않음.
• 효율성: 한 번에 하나의 패킷만을 처리해서, 네트워크의 활용도 낮음. 대역폭이 클 경우, 효율성 크게 떨어질 수 있음.
• 지연 시간: 각 패킷의 확인 응답을 받기 전까지 다음 패킷을 전송할 수 없어, RTT(Round-Trip Time)만큼의 지연 발생.

https://www.youtube.com/watch?v=YdkksvhkQGQ

 

한 마디로, sender입장에서, 패킷 하나 보내놓고 그에 대해 ACK 돌아올 때까지 기다렸다가 돌아오면 그 다음 패킷 보내는 방식(a). 만약 지정해둔 시간 안에 안 오면(b -  전송 자체가 안 되었거나, c - ACK가 안 왔거나) 다시 한 번 보내는 방식. (d)는 프로토콜 자체를 잘못 짠 거다. 응당 걸려야 하는 RTT 고려 안하고 너무 짧은 timeout 설정이므로.

결론적으로, 한번에 하나씩 밖에 못 보내니까 비효율적임.

 

한번에 하나씩이 아닌 여러개 씩 보낼 수 있는 방법이 나옴: 바로 protocol pipeline을 쓰는 것. 데이터를 담을 윈도우라는 구조를 만들고, 그 크기를 설정하고, ACK를 받은 녀석에 한해서만 윈도우에서 제거하고 그 다음 녀석으로 넘어가는 방식.

 

ARQ 2: Sliding Window1: Go-back-N

작동 원리

1. 다중 패킷 전송: 송신자는 윈도우(window) 크기만큼 여러 패킷을 연속적으로 전송 가능. 윈도우 크기는 송신자가 ACK 없이 전송할 수 있는 패킷의 최대 수.
2. 수신 확인 대기: 송신자는 전송한 패킷 각각에 대해 수신자로부터의 확인 응답(ACK)을 기다림.
3. ACK 수신:
   • 성공적 수신: 수신자가 패킷을 올바르게 받으면 해당 패킷의 ACK를 송신자에게 보냄.
   • 수신 실패: 특정 패킷에 대한 ACK을 받지 못하면, 송신자는 해당 패킷과 그 이후에 전송된 모든 패킷을 재전송.
4. 슬라이딩 윈도우: 송신자는 받은 ACK에 따라 윈도우를 슬라이드하며 계속해서 새로운 패킷을 전송.

특징 및 한계

• 효율성: 윈도우를 활용하여 여러 패킷을 연속적으로 보낼 수 있어 네트워크 활용도 향상. 대역폭이 클 경우에 효율적으로 작동.
• 재전송 오버헤드: 잘못된 패킷 하나 때문에 여러 패킷을 재전송해야 하기 때문에, 패킷 손실이 빈번하게 발생하는 환경에서는 비효율적일 수 있음.
• 복잡한 윈도우 관리: 윈도우 크기와 슬라이딩 메커니즘이 네트워크 상황에 따라 적절히 조정되어야 하므로 구현이 복잡할 수 있음.

  

  https://www.youtube.com/watch?v=QD3oCelHJ20

앞의 Stop and wait 보다는, 당연히, 파이프라이닝을 썼기 때문에 한번에 여러 개를 보낼 수 있으므로 효율적이지만, 만약 문제가 생겼을 때, 예를 들어 그림처럼 2번이 문제가 생겼다 하면, 그 에러를 인식하기 전에 보내진 3,4,5 는 모두 receiver 입장에서 폐기처분하기 때문에, 그 부분이 비효율적이다. 그래서 나온 게 Selective repeat.

 

 

ARQ 3: Sliding Window2: Selective Repeat

작동 원리

1. 다중 패킷 전송: 송신자는 윈도우 크기에 따라 여러 패킷을 연속적으로 전송 가능.
2. 개별 ACK 처리: 각 패킷에 대해 독립적으로 수신 확인(ACK)을 기다림.
3. 선택적 재전송:
   • 성공적 수신: 각 패킷에 대한 ACK을 받으면 해당 패킷은 성공적으로 전송된 것으로 처리.
   • 수신 실패: 오류가 발생한 패킷만 재전송. 이는 네트워크 자원을 효율적으로 사용하게 함.
4. 슬라이딩 윈도우: ACK을 기반으로 윈도우를 슬라이드하며 패킷 전송 계속.

특징 및 한계

• 효율성 향상: 오류가 발생한 패킷만을 재전송하여 네트워크 자원을 보다 효율적으로 사용.
• 복잡한 구현: 패킷의 순서와 버퍼 관리가 더 복잡해짐. 각 패킷의 독립적인 처리 필요로 하여 구현 난이도 상승.
• 고성능 환경 요구: 정확한 패킷 추적과 빠른 반응 속도가 필요하여 고성능의 시스템에서 더욱 효과적.

https://www.youtube.com/watch?v=WfIhQ3o2xow

 

Selective repeat은 문제가 난 패킷만을 다시 전송하기 때문에, 전송 시의 효율도 잡고, 에러 핸들링 또한 효율적이라 가장 좋은 프로토콜이라고 할 수 있음. 물론 구현하는 데에 힘이 소요된다는 단점이 있기는 함.

Selective repeat의 경우에도 sliding window는 무조건 연속적인 번호로 구성되어야 함. 다만 리시버 입장에서 순서를 따르느라고 에러가 났을 때 기존의 잘 받은 것들을 폐기처분하는 일은 안 해도 된다는 것.