[Data Communication] 에러 제어와 ARQ

 

 

 

디지털 데이터 전송 중 노이즈 등으로 비트가 변하는 오류가 발생할 수 있다. 

 

Parity Bit 

데이터에 패리티 비트를 1비트 추가해서 전체 1의 개수를 짝수나 홀수로 맞춘다. 

단일 비트 오류는 검출할 수 있지만, 오류 수정은 안되고 짝수 개의 비트 오류는 검출할 수 없다. 

 

Checksum

데이터 블럭의 합을 사용해 오류를 검출한다.

데이터를 여러 블럭으로 나눠 합계를 계산하고, 이 합의 보수를 체크섬으로 전송한다. 

수신 측은 받은 데이터 + 체크섬이 0이 되는지 확인하는 방식이다. 

빠르지만 역시 오류 수정은 불가능함

 

CRC (Cyclic Redundancy Check)

다항식 데이터를 이진 다항식으로 바라보고 미리 정해진 Generator Polynominal으로 연산.

나머지(R)가 CRC 코드이고, 수신 측에서도 같은 방식으로 나눠서 나머지가 0인지 확인하는 방식이다. 

오류를 정확하게 검출할 수 있지만 오류 수정은 불가능함 

 

Hamming Code 

데이터에 여러 패리티 비트를 추가하고, 특정 비트 오류가 발생하면 어디가 틀렸는지도 알아낸다. 

Hamming(7, 4) -> 4비트 데이터 + 3비트 패리티로 구성. 수신 후 XOR 연산으로 오류 위치 판별하고 비트 반전으로 복구.

1비트 오류는 수정할 수 있고 2비트 오류는 검출만 가능.

 

코드워드는 데이터비트 + 패리티비트로 구성된다.  

 

 

 

 

해밍 거리를 사용하면 최소 해밍 거리 - 1 개 만큼의 비트 오류를 탐지할 수 있다. 

 

 

 

 

IP 헤더, TCP 헤더, UDP 헤더에 오류 탐지를 위한 비트가 들어있다. 

 

대부분의 경우.. 수신자는 오류를 탐지할 수만 있고 복구는 불가능하다.

그러니 오류 탐지 후 오류 데이터를 재전송해달라고 요청해야 하는데, 이걸 ARQ (Automatic Repeat Request) 라고 부른다.

 

Parity / Checksum / CRC 등 오류 체크 로직은 추가적인 비트를 사용하는데 이 추가 비트는 전체 데이터의 크기에 비해 매우 작고 효율적이다. 

1500바이트 짜리 패킷을 보낼 때도 오류 체크에 사용되는 비트는 정해져있다.

 

Parity Bit는 추가 비트를 1비트만 사용해 전송 단위마다 붙인다. (비효율적이라 거의 사용하지 않음)

Checksum은 IPv4 TCP UDP의 헤더에 16비트를 추가한다. 

CRC는 Ethernet 등에서 프레임 전체에 16 / 32 / 64 고정 비트를 추가한다.

 

그냥 단순한 합산으로 구하는게 아니고, 위에 언급한 로직 기반으로 정교한 수학적 연산을 수행해 적은 비트를 사용해도 큰 데이터에 대한 오류를 효과적으로 검증할 수 있다. 

 

 

 

 

---

 

 

 

 

데이터 링크 계층은 물리 계층의 불안정한 전송을 보완해 논리적으로 오류 없는 프레임 단위의 전송을 보장한다.

 

흐름제어 - 송신자가 너무 빠르게 보내면 수신자가 처리할 수 없다.

에러제어 - 전송 중 손상되거나 유실된 프레임을 검출하고 재전송한다. 

 

Automatic Repeat reQuest 는 에러가 발생했을 때 자동으로 재전송을 요청하는 방식으로, 수신자가 데이터 프레임에서 오류를 감지하면 송신자에게 재전송 요청을 보내고 송신자는 해당 프레임을 다시 전송한다. 

 

CRC, Checksum 같은 오류 탐지 매커니즘을 사용해서 데이터의 오류를 검출할 수 있음이 전제되어야 하고, 응답이 제대로 도착한 경우 수신자는 송신자에게 Acknowledgement 응답을 보내고 오류가 있는 경우 Negative ACK를 보낸다. 

 

ARQ는 2계층과 4계층에서 사용된다.

2계층에서 사용될 때는 직접 연결된 두 노드 간의 신뢰성을 보장할 때 사용되고, 4계층에서 사용될 때는 인터넷을 통해 멀리 떨어진 두 호스트 간의 통신을 보장할 때 사용된다. (TCP)

3계층의 주요 역할은 라우팅과 전달이지 신뢰성 있는 전송이 아니기에 3계층에서는 ARQ가 사용되지 않는다. 

 

 

 

 

 

 

Stop-and-Wait ARQ는 가장 기본적인 ARQ 방식으로 하나의 프레임을 전송한 후 해당 프레임에 대한 ACK를 받을 때 까지 송신을 멈추는 방식이다. (완전 블로킹 모델)

 

A와 B가 통신하는 예시를 살펴보면, A가 프레임 0을 전송하면 B는 프레임 0을 수신한 후 ACK 0으로 프레임 0을 잘 받았다고 A에게 응답한다. 이후 A는 0을 보냈으니 이번에는 1을 보내고, B는 1을 수신하고 ACK 1을 응답한다. 

 

여기서 시퀀스 번호를 1비트만 사용하는데, 어차피 송신자는 항상 하나의 프레임만 보내고 수신자도 하나의 프레임만 기다리기에 동시에 처리되는 프레임은 1개 뿐이니 1비트만으로 충분하다. 

 

왕복지연시간을 고려해서 Timeout 값을 설정해야 한다. (2*RTT) Timeout 됐다면 패킷이 손실됐다고 판단한다. 

 

동작은 하지만.. 성능이 좋지는 않다.

전송 속도 - 1Gbps / 전파지연시간 - 15ms / 패킷 크기 - 8000 bits 라고 할 때.. 

패킷 하나를 보내는 데 걸리는 시간은 0.008ms, 송신 측 링크 사용률은 0.0266% 정도가 나온다. 

즉, 나머지 99.97%는 ACK를 기다리느라 놀고 있다는 것.. (Blocking + 동기)

 

매우 비효율적인 Throughput을 보여주니... 한 번에 여러 개를 보내는 ARQ 방식을 사용한다. 

 

 

 

 

 

 

Go-back-N ARQ 방식에서는 송신자가 ACK를 수신받지 않은 N개의 패킷을 전송한다. (부분 블로킹 모델)

수신자는 누적 ACK를 전송하고, 가장 오래된 ACK 미수신 타이머를 제거한다. 

 

한 번에 여러 프레임을 전송하고, 수신자가 오류 감지 시 해당 프레임 이후부터 전부 재전송하는 ARQ 방식으로 Stop-and-Wait ARQ 방식보다 훨씬 빠르다. 

 

송신자 측은 최대 N개의 프레임까지 ACK 없이 연속으로 전송할 수 있고, 수신자 측은 ACK 번호가 순차적이지 않으면 버린다. 

각 프레임이 붙은 고유 번호는 모듈로 방식으로 순환되고, 수신자는 해당 번호를 기반으로 ACK를 전송한다. (Non-Blocking + 동기)

 

윈도우 크기가 N이면 N개의 프레임을 한 번에 보낼 수 있다는거지 하나의 프레임은 수천 바이트일 수 있다.

중복된 프레임을 구분하려면 유효한 번호가 겹치는걸 방지해야 하니.. 시퀀스 번호 크기 >= N+1 로 설정된다.

 

0 1 2 3 프레임을 보냈지만 2에서 손실이 발생한 경우 ACK 1까지만 보낼 수 있으니 2 3 은 모두 재전송 해야 한다. 

 

 

 

 

 

 

 

Selective Repeat ARQ는 ARQ 중에서 가장 발전된 방식으로 한 번에 여러 프레임을 보내면서도 오류난 프레임만 골라서 재전송한다.

수신자는 순서가 틀리더라도 일단 저장하고, 송신자는 필요한 프레임만 다시 전송한다. (논블로킹 모델)

 

0 1 2 3 을 보낼 때 2가 손실나더라도 일단 3까지 송신한다. 이후 ACK 0 1 3 을 보내고, ACK 2가 도착하지 않았으니 2번 프레임만 다시 보내는 방식으로 작동한다. (Non-Blocking + 비동기)

 

모든 프레임을 일단 다 저장하기에 시퀀스 번호가 너무 빠르게 사용된다면 해당 프레임이 예전 프레임인지 새로운 프레임인지 헷갈릴 수 있어 시퀀스 번호를 좀 더 넓게 사용해야 한다. (시퀀스 번호 크기 >= 2N)