Link Layer

링크 계층은 물리적으로 인접한 노드 간의 데이터그램의 전송을 책임진다. 링크 계층에서 주고 받는 패킷의 단위는 frame이다. 링크 계층은 인접한 노드들 간의 신뢰성 있는 연결을 제공한다.

Error detection

네트워크 계층에서 보내는 Datagram에 EDC (Error Detection and Correction bits) 라는 추가 정보를 만들어서 보낸다.

이 EDC를 가지고 오류를 감지해 낼 수 있다.

Parity checking

가장 단순하게 오류를 감지하는 방법은 패리티 체크 방식이고, 이는 데이터의 끝에 패리티 비트(parity bit)를 추가하는 방식이다.

패리티 비트를 추가하면 비트의 1의 개수를 짝수개로 만든다.

패리티 체크 방법에는 두 가지 방법이 있다.
single bit parity, two-dimensional bit parity

Single bit parity

1비트의 패리티 비트를 사용하는 방법이다.
전체 데이터 비트의 1 개수를 확인 후, 0 또는 1을 추가하여 전체 1의 개수를 짝수 개로 만든다.

만약 전송하는 과정에서 비트가 변해서 홀수 개가 되었다면 오류가 발생한 것이라고 판정할 수 있다.

그러나 이 방식의 문제는 어느 비트가 바뀌었는지 알 수 없다는 점이다.
또한 짝수 개의 비트가 바뀌는 오류가 발생했다면 이 방법으로는 오류를 감지할 수 없다.

two-dimensional bit parity

각 row, column 별로 각각 parity bit를 붙여서 오류를 검증하낟.

이 방식은 single bit error에서 어느 비트가 바뀌었는지도 알 수 있다.
만약 2행과 2열이 동시에 패리티 에러가 발생하면 2행 2열에 해당하는 비트가 반전되어 있다는 뜻이다.

그러나 같은 행/열에 여러 에러가 발생하면 에러 감지를 할 수 없다.

Cyclic Redundancy Check (CRC)

원래 데이터의 값에 따라 CRC 값을 계산하여 데이터에 붙여 전송하고, 데이터 전송이 끝난 후 받은 데이터의 값으로 다시 CRC 값을 계산한다. 두 값을 비교했을 때 두 값이 다르면 데이터에 오류가 발생했다는 것을 알 수 있다.

R은 CRC 비트의 길이이다. 길면 길수록 오류 검증 성능이 강력하다. D가 보내야 하는 원본 데이터이고 위 그림의 경우에는 101110이다. G는 송수신자 모두 알고 있는, 사전에 정의된 값이고 원본 데이터를 나눗셈 할 때 사용된다. CRC 값보다 1비트 만큼 길다.

먼저 원본 데이터에 2^r을 곱하여 r비트만큼 공간을 마련해준다. 그리고 G로 XOR 연산을 반복하여 수행한다. 그러면 더이상 연산을 할 수 없는 나머지가 발생할 것이다. (물론 나머지가 없을 수도 있음) 여기서 발생한 나머지 (위 그림에서는 011)이 CRC 값이다. 나머지만큼 원본 데이터에 2^r을 곱한 수에다가 더해주면 나머지가 없어진다.

그리고 CRC 값을 원본 데이터 앞에 붙인 값인 101110011 을 보낸다. 즉 나머지가 0이 되게끔 하여 보낸다. 수신자는 받은 데이터와 1001을 가지고 XOR 연산(나누기)을 수행한다. 결과가 다르면 에러가 발생했음을 알 수 있다.