#2 Error Detection and Correction

Network에서 Data를 전송할 때 발생할 수 있는 오류를 방지하고, data의 무결성과 신뢰성을 보장하기 위해서 Error Detection(오류 검출)과 Error Correction(오류 수정)이 필요하다.

 

예를 들어, 전송 매체에서 노이즈나 간섭이 발생할 수 있다. 광케이블에서의 비트 오류 확률은 10^(-9)정도로, 10억 bits 중 하나가 오류가 발생할 수 있음을 의미한다.

1. Error Detection(오류 검출) and Correction(오류 수정)

1.1. Error Detection과 ARQ(오류 검출과 자동 재전송 요청)

Error Detection은 오류가 발생했는지 확인하는 과정이고 ARQ(Automatic Repeat reQuest)는 오류가 검출되었을 때 data의 retransmission(재전송)을 요구하는 기법으로, Error Detection과 ARQ는 함께 처리하는 protocol이다.

 

Error Detection은 오류를 감지하는데 집중하며 parity bit(패리티 비트), CRC와 같은 기법으로 데이터를 확인한다.

 

ARQ는 오류가 발생하면 packet을 retransmission하는 방식으로, data 전송의 신뢰성을 높인다.

1.2. Error Correction이란?

Error Correction은 data를 확인하여 감지된 오류를 바로 수정하는 과정을 의미한다. Error Correction은 data를 다시 보내는 것이 비용이 많이 들거나 시간이 오래 걸리는 상황에서 사용된다.

 

retransmission cost가 너무 비싼 경우의 대표적인 예시로는 화성 탐사선과 지구 간의 통신이 있다. 지구에서 화성으로 data를 보낼 때, 신호가 도달하는 데만 몇 분에서 수십 분이 걸릴 수 있다.

 

이때 오류가 발생하면 retransmission을 요청하고 다시 data를 받는 데 시간이 많이 걸리므로 error detection 후 retansmission을 하는 대신 error correction 방식을 사용하는 것이 훨씬 효율적이다.

2. Error Detection은 어디 계층에서 일어나나?

Error Detection 여러 계층에서 메커니즘을 사용할 수 있지만, 주로 Data-Link Layer에서 발생한다.

2.1. Data-link Layer에서의 error detection

Data-link Layer는 물리적인 전송에서 발생할 수 있는 error를 검출하기 위한 역할을 수행한다. 이 Layer에서 error detection은 data frame이 전송될 때 이루어지며 이를 통해 data의 무결성을 확한다.

 

실제적인 구현으로 NIC(Network Interface Controller)의 controller에서 CRC 메커니즘 등을 사용하여 error를 검출한다.

2.2. RDT(Reliable Data Transfer) 보장

RDT는 데이터 전송의 신뢰성을 보장하기 위한 protocol로, 오류 검출, ACK/NAK, retransmission 등의 메커니즘을 통해 데이터의 무결성을 유지합니다.

 

이를 통해 네트워크에서의 데이터 통신이 보다 안전하고 신뢰성 있게 이루어질 수 있습니다.

3. Error Detection에 사용되는 Redundancy(중복성)

Data 전송 과정에서 Error가 발생할 수 있기 때문에 이를 감지하고 수정하기 위해 추가 정보를 삽입하는 방식이다.

 

Redundancy의 비트 수가 많아질수록 오류 검출 향상에 유용하지만 메모리 대역폭 소모, 처리 시간 증가, 복잡성, 성능 저하 등의 단점 또한 존재한다.

3.1. parity check (패리티 검사)

Parity Check은 데이터의 무결성을 보장하기 위해 비트의 개수를 이용하여 오류를 확인한다.

- Even parity concept (짝수 패리티)

데이터 비트의 1의 개수가 짝수가 되도록 추가 비트를 설정한다. 예를 들어, 데이터 비트가 1011이라면, 1의 개수가 3개이므로 짝수를 맞추기 위해 추가 비트로 1을 추가하여 10111로 만든다.

 

구현이 매우 간단하고, 별도의 복잡한 연산 없이도 오류를 검출할 수 있다. 하지만 두 개 이상의 비트가 오류가 발생한 경우 오류를 감지할 수 없다. 예를 들어, 데이터가 1011에서 1000로 변경되면 패리티는 여전히 맞기 때문에 오류를 감지하지 못한다.

3.4. CRC(Cyclic Redundancy Check)

3.4.1. CRC란?

CRC는 데이터 전송 중 오류를 검출하기 위해 사용되는 오류 검출 메커니즘이다. CRC는 특정 다항식을 사용하여 데이터 블록의 나머지를 계산하고, 이를 CRC 값으로 추가하여 오류 검출을 수행한다.

3.4.2. CRC 계산 과정 예시

• CRC 값은 divisor보다 한 칸 적어야 함
• Sender에서 data를 divisor로 xor을 통해 나눌 때 0은 divisor의 한 칸보다 작아야 함
• Receiver는 divisor로 나누면 0이 나와야 함

3.4.3. Standard polynomials

Standard Polynomials는 CRC에서 오류 검출을 위해 널리 사용되는 polynomials(다항식)을 의미한다. 이러한 다항식에서 최고 차항은 항상 존재해야 하며, 이를 통해 CRC 비트의 길이가 데이터와 함께 효과적으로 오류를 검출할 수 있다.

 

다항식의 최고 차항이 2의 거듭제곱 형태일 떄, 이 다항식은 divisor로 사용할 수 있으며 이 경우 CRC 비트의 길이가 2의 거듭제곱 형태로 나타난다.