데이터 통신

[Data Communication] 재전송 기반의 오류제어 및 흐름제어 (ARQ)

짱일모 2023. 5. 24. 00:12

저번 포스팅에서 오류 탐지 및 오류 복구를 위한 여러가지 방법에 대해 알아보았습니다. 오류 복구를 위한 방법으로는 오류 복구에 필요한 데이터를 미리 실어 보내는 방법을 다루었습니다.

 

이번 시간에는 재전송을 기반으로하는 오류제어 및 흐름제어 방법인 Automatic Repeat Request (ARQ) 방법에 대해 알아보겠습니다.

 

 

데이터 링크 계층에서의 흐름제어/오류제어

컴퓨터마다 데이터를 주고 받는 성능 혹은 네트워크 환경이 다르기 때문에 이를 조율할 수 있는 "흐름 제어" 방법이 필요합니다.

 

흐름 제어 방법은 다음과 같습니다.

  • Stop n Wait : 한 번에 하나씩만 전송.
  • Sliding Window : 한 번에 여러개 전송. 

오류제어 방법으로는 Automatic Repeat Request (ARQ) 방법을 사용합니다. 즉, 오류가 발생하면 재전송을 요청하여 오류를 해결합니다.

 

예를 들어, STOP N WAIT ARQ (흐름제어 + 오류제어) 방법의 경우 송신자가 0번 패킷을 전송합니다. 수신자가 0번 패킷을 잘 받았을 경우 "1번 패킷을 주세요" 라고 요청을 합니다. 0번 패킷을 잘 받지 못했을 경우, "0번 패킷을 주세요" 라고 요청을 합니다.

 

만약 "n번 패킷을 주세요" 라는 메세지가 전송 중에 오류가 발생하면, 송신자 측에서는 일정 시간이 지났는데도 불구하고 수신자로부터 메세지가 오지 않으면 데이터 전송에 오류가 발생한 것으로 간주하고 재전송을 수행합니다.

 

이를 결합한 흐름제어 / 오류제어 방법은 다음과 같습니다.

 

  • Stop N Wait ARQ
  • Go-Back N ARQ
  • Selective Repeat ARQ

 

 

STOP N WAIT ARQ

Stop N Wait ARQ 의 정상동작 Flow

 

Stop N Wait ARQ 방식으로 흐름제어/오류제어를 수행하기 위해서는 다음과 같은 요소가 필요합니다.

 

  • Sequence Number : 패킷의 식별자
  • ACK : 정상 패킷에 대한 수신자가 송신자로 보내는 응답. 이것이 전송 중 손실이 일어나면 Timeout 발생
  • Timeout (Timer) : 송신자가 수신자에게 패킷을 전송할 때 카운트 다운하는 값. Timeout 발생 시 재전송 수행. 이 때 Timeout 값은 RTT (Round Trip time) 을 고려하여 지정

 

Stop N Wait ARQ Architecture 1
Stop N Wait ARQ Architecture 2

 

송신자는 수신자로부터 적절한 ACK 신호를 받지 않으면 Timeout 이 발생하여 재전송을 수행합니다. 수신자는 받고자하는 패킷이 들어왔는지 확인합니다. 이것이 Stop N Wait ARQ 의 전부입니다.

 

그러나 Stop N Wait ARQ 는 문제점이 있습니다. 속도가 매우 느립니다.

 

1Gbps 대역폭을 지원하는 채널, 15ms 의 Propagation Delay 가 존재하는 네트워크 환경에서 패킷 하나에 8000bits 을 담아 전송하는 예시를 살펴봅시다. 

 

Transmisson Delay = 8000bits / 1Gbps = 8microseconds 가 되고, Utilization of Sender 를 총 전송 시간 중 실제 데이터를 보내는 시간의 비율로 정의하면 Utilization of Sender 는 다음과 같이 계산됩니다.

 

U.sender = Transmission Delay / (Rount-trip time + Transmission Delay) = 0.00027 입니다.

 

즉, 1Gbps 의 대역폭을 약 3/10000 밖에 이용하지 못하게 됩니다.

 

이를 해결하기 위해 한 번에 보낼 수 있는 패킷의 양을 늘린 방법이 Go-Back N ARQ 입니다.

 

 

Go-Back N ARQ

Go-Back N ARQ 방식은, Stop N Wait ARQ 에서 Sliding Window 라는 개념을 도입하여 한 번에 보낼 수 있는 패킷의 양을 1개 이상으로 만든 방법입니다.

 

먼저 패킷에 를 m개의 비트를 이용하여 Sequential Number 를 부여합니다.

 

그리고 송신자는 수신자의 ACK 신호를 받지 않더라도 Sliding Window 크기만큼의 패킷을 보낼 수 있습니다. 즉, 한 번에 보낼 수 있는 패킷의 양이 많아졌습니다. 그리고 ACK 신호를 받지 못한 Sequential Number 의 패킷 타이머를 유지합니다. Timeout 이 발생하면 해당 패킷부터 이후 패킷까지 재전송을 수행합니다.

 

수신자는 패킷을 받을 때마다, ACK 을 보냅니다. 

 

Go-Back N ARQ
Go-Back N ARQ Architecture 1

 

하지만, Go-Back N ARQ 를 사용할 때 Sliding Window 의 크기를 적절하게 (max: 2^m - 1) 잡아주어야합니다. 그렇지 않으면 오류가 발생할 여지가 있습니다.

 

Go-Back N ARQ Architecture 2

 

만약 위 그림에서와 같이 Sliding Window 의 크기가 2^m 과 같아지는 순간, 송신자가 보내는 Packet 이 잘못 전송된지 모르고 수신자가 패킷의 Seq Number 가 같단 이유만으로 데이터를 Accept 할 가능성이 발생하기 때문입니다.

 

여기서 의문점이 생깁니다! Sequence Number 의 크기를 결정하는 m 값을 무한히 키우면 이런 일이 없지 않냐?

하지만, 이 m 값은 송신자와 수신자 간의 프로토콜로써, 반드시 정해진 값이 있다고 합니다.

 

Selective Repeat ARQ

Selective Repeat ARQ 는 Go-Back N ARQ 방식을 개선한 것으로, 미수신된 패킷만을 재전송하는 방법입니다. (Go-Back N ARQ 는 미수신된 패킷부터 연속된 패킷을 모두 재전송하였습니다.)

 

이 때 Selective Repeat ARQ 에서 수신자는 미수신된 패킷이 있고 그 다음 Seq Num 패킷이 들어오더라도 이를 Accpet 할 수 있습니다. 한마디로, 수신자의 Sliding Window 크기가 (2^m-1) 입니다.

 

 

 

Selective Repeat ARQ

 

Selective Repeat ARQ 도 Go-Back N ARQ 와 마찬가지로 오류 발생을 방지하기 위한 제약 조건이 존재합니다. Selective Repeat ARQ 의 Sliding Window 크기는 2^m-1 보다 작아야합니다.

Selective Repeat ARQ 2

 

 

정리

데이터 링크 계층에서는 IEEE 802.11 무선랜에서 ARQ 방식을 사용합니다. (이더넷은 ARQ 가 아닙니다.)

또, Transport 계층의 TCP 에서 Go-Back N ARQ 방식과 Selective Repeat ARQ 방식을 혼합한 방식의 흐름제어/오류제어 방법을 사용합니다.