네트워크프로토콜

[네트워크프로토콜] 에러 검출 & 수정(2)

by VICENTE97P4

March 30, 2022, 2:50 p.m.

CRC(Cyclic redundancy check)

CRC는 dataword를 divisor로 나누어서 나머지를 redundancy로 씁니다.

수신측 syndrome에서는 divisor로 나누어서 나머지가 0이면 error가 없다고 판단합니다.

error가 검출되면 재전송을 요청합니다. 이는 datalink 계층의 protocol이 요청합니다.

나누는 법을 봅시다.

1001을 보낼 때 미리 정해저있는 divisor인 1011로 나눕니다.

redundancy를 3bits 추가하려고 한다면 0 3개를 1001 마지막에 붙여줍니다.

즉, 1001000을 1011로 나누면 되죠.

나누기는 각 과정에서 XOR을 하면 됩니다.

그렇게 생기는 나머지 110을 1001 뒤에 붙여서 1001110을 보내면 됩니다.

수신측에서는 밭은 codeword를 divisor로 나눕니다.

나머지가 0이면 syndrome에서 정상 전송이라 판단하고,

나머지가 있으면 error라고 판단하고, 폐기처분 후 재전송을 요청합니다.

CRC는 하드웨어 구현이 편해서 L1 / L2 계층에서 사용합니다.

XOR 회로, shift register로 구현됩니다.

CRC는 binary pattern 뿐만 아니라 polynomial(다항식) code로도 구현이 가능합니다.

나눗셈을 할 때는 redundancy 수 r만큼 x^r을 곱해줘야 합니다.

그리고 역시 XOR 연산을 하면 됩니다.

divisor를 generator라고 합니다.

syndrome에서 error가 검출되지 않는 경우도 있습니다.

바로 error가 generator에서 딱 나누어떨어지게 생기면 detection하지 못합니다.

그럼 generator를 어떻게 만들어야 할까요?

- 두 개 이상의 항과 상수항이 있어야 single bit error를 detection할 수 있습니다.

b, c는 항이 1개이고 또한 b는 상수항이 없기 때문에 a만 single bit error을 검출할 수 있습니다.

만일 두 bit가 떨어져서 error가 생기는 경우에는

- x^t + 1이 generator로 나누어떨어지면 안됩니다.

여기서 a, b, d는 x^t + 1 형태를 나눌 수 있습니다.

d의 경우는 x^32768 + 1을 나눌 수 있다고 합니다.

그래서 32768 이하 bit 떨어진 거리까지는 검출이 가능한데 그 너머로는 에러를 검출할 수 없습니다.

따라서 c만 적합합니다.(d도 사실상 사용할 수는 있습니다.)

- generator가 x+1 을 factor로 가지면 모든 홀수번째 error를 검출할 수 있습니다.

그럼 burst error는 어떻게 검출할까요?

L: burst error의 길이, r은 divisor의 차수라고 하면

- L <= r이면 burst error 감지가 가능합니다.

a는 6, b는 18, c는 32 bit 이하의 burst error를 검출할 수 있습니다.

CRC-32를 일반적으로 많이 씁니다.(LAN)

Checksum

data의 합을 구해서 error check를 합니다.

(7, 11, 12, 0, 6)을 보낼 때면 7+11+12+0+6 = 36을 뒤에 추가로 바냅니다.

(7, 11, 12, 0, 6, 36)을 보내서 수신측에서 7+11+12+0+6 = 36인지 확인해서 error 여부를 확인합니다.

그런데 실제로는 checksum으로 다 합친 결과의 음수를 보냅니다.

그러면 수신측은 그냥 싹 다 더해서 0이 나오면 되기 때문에 계산이 더욱 쉽습니다.

그러니까 (7, 11, 12, 0, 6, -36)을 보냅니다.

컴퓨터에서 2의 보수를 사용하는 이유는 HW 구현이 편리해서입니다.

sign and magnitude 방식은 Floating point에서 사용합니다.

1의 보수는 checksum에서 씁니다. 음수로 변환할 때 0과 1을 바꿔주기만 하면 됩니다.

만일 계산 중 checksum size가 넘어가면 다시 맨 뒤로 넘겨줍니다.

예를 들어 checksum size가 4bit라고 합시다. 그리고 계산 결과가 10101이 나왔다고 합시다.

그럼 맨 앞에 있는 1과 그걸 제외한 0101을 다시 더해서 0110, 그러니까 6을 checksum으로 둡니다.

더 정확하게는 6의 1의 보수인 1001, 그러니까 -6을 checksum으로 삼죠.

1의 보수의 문제점은 0을 표현하는 식이 2개라는 겁니다.

0000도 0이지만 0에다가 1의 보수를 취한 1111 또한 0입니다.

실제로 checksum은 16bit를 사용합니다.

Framing

datalink 계층의 기본 전송 단위는 frame입니다.

그런데 noise가 frame의 앞뒤로 있을 수 있습니다. 대다수의 경우 noise가 있겠죠.

통상 noise는 인식될만큼 크지 않아서 상관없지만 간혹 크기가 큰 noise는 0이나 1로 감지되기도 합니다.

그럼 수신기 입장에서는 어디서부터가 시작이고 어디까지가 끝인지 구분하기가 어렵습니다.

그래서 frame의 시작과 끝을 특수한 pattern을 가지는 flag로 구분합니다.

시작부분의 Flag를 제외하고 Header와 data들을 나누고 생긴 나머지(CRC)를 Trailer 자리에 붙입니다.

문자열 단위로 보낼 때는 기본이 byte 단위입니다.

그런데 flag 패턴이 data에 들어있으면 수신기 입장에서 또 헷갈릴 수 있습니다.

ASCII 코드는 7bit이고 특수문자는 MSB를 사용한 8bit를 사용합니다.

flag에는 통상 이 특수문자 영역이 쓰이는데,

만일 이 특수문자가 data라면 수신기 측에서 중간에 끝났다고 인식하는 대참사가 발생할 수 있습니다.

그래서 중간에 나오는 data flag는 ESC를 flag 앞에 붙입니다.

만일 ESC를 data로 보낼 때는 ESC를 한 번 더 앞에 붙여줍니다.

이렇게 sender 쪽에서는 채워준다고 해서 stuffing, receiver 쪽에서는 빼준다고 해서 unstuffing이라 합니다.

Bit oriented protocol

아까까지는 문자 단위였습니다.

그런데 요새는 bit 단위로 보냅니다.

- 동기 방식: bit 단위

- 비동기 방식: byte(문자) 단위

flag에 특정한 bit pattern을 씁니다.

이 경우에도 역시, data에 flag와 같은 패턴이 있으면 혼동됩니다.

그래서 만일 flag에 1이 연속적으로 6개가 있다고 하면,

data 부분에 1이 5개가 연속으로 있으면 무조건 0을 하나 더 넣어줍니다.

이를 bit stuffing이라 합니다.