[Network] Link layer, error detection (parity, CRC)

link layer service

link layer에서는 다음과 같은 서비스들을 제공한다.

 

framing, link access

1. 데이터그램에 header, trailer를 붙여서 프레임으로 만든다.
2. header에 MAC 주소를 사용하여 source, destination을 식별한다.

reliable delivery between adjacent nodes

1. low bit-error link (fiber, twisted pair) : 에러 비율이 낮다.
2. wireless link : 에러 비율이 높다.

이 외에도 flow control, error detection, error correction, half-duplex, full-duplex와 같은 서비스들을 제공한다.

 

link layer가 동작하는 위치

https://electronicspost.com/where-is-link-layer-implemented/

 

link layer가 동작하는 위치는 Network Interface Card(NIC, adaptor) 아니면 칩셋이다.

 

호스트의 시스템 버스에 존재하며 하드웨어의 성격도 가지고 소프트웨어의 성격도 가지는 펌웨어(firmware)이다.

 

이러한 adaptor끼리 통신하는 과정은 다음과 같다.

보내는 측에서는 데이터 그램을 encapsulate를 해서 frame으로 만들어 보낸다.

 

물리적인 경로를 사용해서 보내고 받는 측에서는 frame을 벗겨서 데이터 그램으로 만들어 다음 계층(network layer)으로 보낸다.

 

error detection

 

데이터그램을 frame을 만들 때 EDC가 추가된다.

 

EDC는 Error Detection and Correction bits이다.

 

기존 데이터그램 데이터에 EDC를 붙여서 보내게 되면 수신 측에서는 이 EDC를 확인하고 에러를 감지할 수 있다.

 

single bit parity 

 

가장 단순한 방식은 데이터 비트 중 1 비트의 개수를 세는 것이다.

 

1 비트의 개수가 짝수면 parity bit를 0으로, 홀수면 parity bit를 1로 설정한다.

 

수신 측에서는 데이터의 1비트 개수와 parity bit를 비교해서 에러를 감지할 수 있다.

 

그런데 만약 에러가 난 비트가 2개라면 짝수, 홀수 여부는 바뀌지 않기 때문에 감지할 수 없게 된다.

 

two-dimensional bit paritys

 

single bit parity의 단점을 보완한 방식으로 2차원 행렬을 만들어서 각각의 행과 열에 대한 parity bit를 만드는 것이다.

 

어느 비트가 에러 났는지 알 수 있기 때문에 error correction 또한 가능하다.

 

single bit parity의 단점은 보완했지만 이 역시 완벽하지는 않다.

 

Cyclic Rebundancy Check (CRC)

 

대부분의 장비에서 사용되고 있는 error check 방식이다.

 

데이터그램에 해당하는 data bits와 r개의 CRC bits가 사용된다.

 

또한 CRC 방식에서는 generator라는 것이 존재한다.

 

CRC bit의 개수가 r개라고 한다면 generator의 비트 개수는 r+1개가 된다.

 

위의 예시에서 CRC bit의 개수가 3개이기 때문에 generator 비트 개수는 4개가 된다.

 

data bits가 101110이고 generator bits가 1001이라고 가정하자.

 

CRC bits는 data bits를 generator bits로 나눈 나머지이다.

 

그런데 일반적으로 우리가 하는 나눗셈과는 달리 XOR 연산을 사용한다.

 

data bits가 101110이고 generator bits가 1001일 때 CRC bits는 011이 되는데 이를 구하는 과정은 다음과 같다.

 

1. 우선 data bits의 뒤에 ( generator bits의 개수 -1 )만큼 0을 붙여준다.

2. 나눗셈을 시작하는데 일반적인 뺄셈을 하는 것이 아닌 XOR 연산을 한다.

만약 일반적인 나눗셈과 똑같이 한다면 1011에서 1001을 빼는 식으로 가겠지만 그게 아니라 XOR 연산을 한다.

 

참고로 나눗셈을 당하는 대상의 첫 비트가 1이어야한다.

 

이 다음은 나눗셈을 당하는 대상 비트(주황색 비트)가 0이다.

이럴 땐 0비트를 넣어주고 XOR 연산을 한다. 

나눗셈 당하는 대상의 첫 비트가 1이기 때문에 이어서 진행한다.

이제 이 과정을 계속 반복하면 

나머지가 011이 되고 이것이 곧 CRC bits가 된다.

 

이제 데이터를 보낼 때 아래와 같이 CRC bits를 추가해서 보내는 것이다.

수신 측에서는 data bits와 CRC bits를 합친 수를 다시 generator로 나눈다. (generator는 수신 측과 송신 측이 같은 것을 사용한다.)

즉 1 0 1 1 1 0 0 1 1 을 1 0 0 1로 나누는 것이다. (물론 정확히는 XOR 연산)

 

만약 0이 나온다면 에러가 없는 것이고 0이라면 에러가 발생한 것으로 생각한다.