7. 오류 검출

오류검출

• 데이터 링크 층의 중요한 기능이다.
• 오류검출까지는 하드웨어가 처리할 수 있다.
• 오류 복구/처리/재전송은 소프트웨어가 처리한다.

오류 검출 코드 (Error Detecting Code) : EDC

• 데이터 영역 안에 오류가 있는지 없는지 알아내기 위한 부가 데이터 (overhead)
  • 수신자가 알아내야 하므로 비용 없이는 할 수 없는 작업이다.
• Ex. parity (맨 끝의 parity bit)
• 크기 면에서 EDC는 data보다 작아야 한다. 오류가 없는 경우 EDC는 단순 overhead가 되기 때문에 작아야 의미가 있다.
• 효율 면에서 오류 검출율이 높아야 한다. EDC가 너무 작으면 검출율이 낮아진다.
• 비용 면에서 f() 연산에서 시간이 적게 소모되어야 한다. 고속 통신에서 병목 지점이 될 수도 있기 때문이다.
• 조건
  1. 부하는 작아야 한다.
  2. 오류 검출율이 높아야 한다.
  3. f 연산에 시간이 적게 들어야 한다.

• 송신자는 data로부터 f()를 이용하여 EDC를 생성한다.
• 수신자는 받은 data를 f()를 이용하여 EDC를 생성하고, 받은 EDC와 대조한다.
  • data, EDC 모두 제대로 온다는 보장은 없다.

오류 검출율

• EDC가 완벽하게 오류를 검출할 수 있을까?
• 검출에 실패하면 시스템 integrity를 상실하게 된다.
• 매우 높은 오류 검출율과 함께 계층마다 오류를 여러 번 체크하는 중복 오류 검사가 필요하다.
  • 송신자가 보낸 EDC, data로 테스트하지만, f(data’) == EDC 라고 해서 통신이 잘 되었는지는 알 수 없다.

2차원 패리티 (Two-Dimensional Parity)

• 1bit 오류라고 가정하면 오류 위치 식별이 가능하고, 수정도 가능하다.
• size가 작고, f()의 비용도 작지만 검출율이 떨어질 수 있다. → EDC로 사용하기는 부적합하다.

인터넷 체크섬 알고리즘(Internet Checksum Algorithm)

• IP Protocol에서 사용한다.
• 아이디어 : 메시지를 16bit 정수의 연속으로 간주하고, 각 정수들을 16-bit 1의 보수 연산을 사용하여 모두 더한다. 모두 더한 값의 1의 보수를 얻어내면 해당 16-bit 숫자가 checksum이 된다.
• size도 작고 f() 계산속도도 빠르지만 검출율이 낮다. 똑같은 자리에서 에러가 발생하게 되면 sum은 같으므로 오류 검출이 실패할 수 있다.
• 약하지만 하위계층에서 bit 오류를 이미 검출했을 것이므로 해당 계층에서는 약한 알고리즘을 써도 된다.

순회 중복 검사 (Cyclic Redundancy Check: CRC)

• 2계층 오류는 거의 대부분 CRC를 사용한다.
• 더하기 보다 복잡한 나누기를 사용하고, 나머지를 오류 검출 코드로 사용한다.
• C를 잘 잡으면 오류 확률을 크게 낮출 수 있다.
• 조건
  • 젯수로 사용될 송수신 사이에 약속된 비트 패턴 : C (n+1 bit)
  • 보낼 메시지 : M
  • 오류 검출을 위해 추가되는 정보 : F (n bit, EDC)
• 송신쪽
  • (M || F) % C == 0이 되도록 F를 생성한다. ( ||은 concatenation)
  • 수신자에게 (M || F)를 전송한다.
• 수신쪽
  • 수신된 메시지 전체를 C로 나누어서
    • 나누어 떨어지지 않으면 오류 발생
    • 나누어 떨어지면 오류가 없는 것으로 간주

CRC의 개념적 이해

• NIC으로 HW 구현 가능. C는 NIC에 존재한다.
• 다항식 연산 (XOR 연산)을 사용한다.

CRC의 성능

• 오류 검출율 매우 높음
  • 비트 패턴 C의 선택이 좌우한다.
  • 수학적 분석에 의해 C를 잘 잡으면, 검출율이 매우 높아진다.
  • 32 비트 (4byte) 코드 사용하면 1500 byte 이상의 데이터에 대해서도 99.99…의 검출율을 갖는다.
• 연산 속도
  • 하드웨어로도 연산 가능한 XOR 연산이라 매우 빠르다.
  • 연산 속도는 전송 속도보다 빨라야 한다.
  • 가능하면 네트워크 카드 내에서 하드웨어로
• 빠른 연산과 ㄴ분석을 위해 다항식 연산 (XOR)을 사용한다.
• 표준화된 C를 사용 → CRC Code

순회 중복 검사 : 송신자 세부사항

CRC 코드

• F가 길면 overhead가 높아지지만 검출율도 같이 높아진다.
• 1로 끝나고 1로 시작하는 C가 검출율이 높다.

CRC의 하드웨어 구현 (참조)

• 1-bit Latch와 XOR gate를 비트패턴 C에 따라 조합
  • 즉, |C| - 1 길이 shift-register의 비트 사이에 XOR을 비치한다.
  • 모든 비트 통과 후, Latch에 남아있는 결과가 CRC 비트
• frame format에서 CRC의 위치는 data 뒤에 존재한다.
  • CRC가 하드웨어로 빠르게 계산될 수 있다고 하더라도 전송 전에 CRC를 계산하게 되면 소요시간이 존재하게 된다.
  • CRC는 의미적으로는 헤더의 일부지만, CRC가 뒤에 존재하면 회로를 병렬적으로 구성 가능하기 때문에 CRC의 전송 시간이 없는 것이 된다.

CRC 정리

• 정의 : 전송되어지는 데이터의 오류 여부를 확인하기 위해 부가되어 보내지는 오류 검출 코드
  • 송신자가 계산에서 생성 및 추가하고, 수신자가 확인한다.
• 사용하는 이유 : 오류 검출율이 매우 높고, 하드웨어 구현이 가능해서 거의 모든 링크 전송에서 사용된다.
  • 이더넷/무선랜 어댑터에서 CRC-32를 사용하고, 99.999%의 검출율을 갖는다.
• XOR-나누기 연산에 기초
• 프레임 전체가 약속된 젯수에 나누어 떨어지도록 CRC 값을 만들어서 데이터 뒤에 붙여 전송한다.
• 수신자는 프레임을 약속된 젯수로 나누어서 나머지가 0이 아니면 오류로 판단한다.
• 나머지가 0이 아니면 오류가 아니라고 간주한다.