cyj893

저장소

컴퓨터 네트워크 - Link 계층: Error Detection & Correction

2 분 소요


K-MOOC에서 부산대학교 유영환 교수님의 “컴퓨터 네트워킹” 강의를 수강하며 적은 노트


링크 레이어: 물리적으로 연결되어 있는 두 개의 노드 사이에서 프레임 전달

  • 노드: 네트워크의 호스트나 라우터 등
  • 링크(미디어): 서로 이웃한 두 개의 노드를 직접 연결해 주는 물리적인 연결(physically adjacent)
  • 프레임: layer-2 packet, 링크 레이어에 생성되는 패킷. 즉 데이터그램을 품고 있음
    • 트랜스포트 레이어(4계층): 세그먼트
    • 네트워크 레이어(3계층): 데이터그램
  • 비트 에러 핸들링, 패킷 충돌 핸들링

링크 레이어의 서비스

  • Framing: 위의 계층에 있는 데이터그램을 전달받아 앞의 헤더와 뒤의 트레일러를 붙여 프레임(frame)을 만드는 것
  • 채널: 하나의 호스트와 다른 호스트들이 서로 다 대 다 연결을 하면 채널을 공유하게 되므로, 이 순서를 정해주는 channel access를 제공
    • MAC address: 각 기계마다 부여받은 주소
  • flow control
    • TCP의 flow control: source 노드와 destination 노드 사이에 전송 속도를 조절. 두 노드는 여러 개의 연결이 있을 수 있음, 직접적인 연결 아님
    • 링크 레이어에서의 flow control: 물리적으로 연결된 두 노드가 너무 빠르게 보내지 않도록 조절
  • error detection: 비트 에러 검사 후 처리
    • 채택한 기술에 따라 감지 또는 감지 후 복구도 가능
  • sending: framing, error control을 위한 부가 정보, flow control 정보
  • receiving: error check, flow control 정보, 데이터그램을 뽑아내 상위 계층에 전달



Error Detection & Correction

Redundancy: 그냥 원본 데이터만 보내면 에러가 발생했는지 알 수 없으므로, 부가적인 정보를 추가하는 것. 여러 에러 디텍션에서 공통적인 부분

parity

  • parity checking: 1의 개수가 홀수 또는 짝수가 되게 한 비트를 더 붙임. odd parity, even parity
    • 데이터 길이와 상관없이 1 bit 추가, 오버헤드 적음
    • 1 bit 에러 감지
  • 2차원 bit parity: 데이터를 행렬로 표현해 row parity, column parity를 구함
    • 1 bit 에러 감지, 수정

CRC(Cyclic Redundancy Check)

  • 송신자와 수신자가 코드 G를 약속
  • CRC의 길이는 r, G의 길이는 r+1
  • 데이터를 G로 나누었을 때(XOR) 딱 나누어 떨어지도록 R을 붙임
  • 필요에 따라서 길이는 짧거나 길게 가능
  • 에러 감지

FEC(Forward error correction): 수신자가 에러 코렉션

  • 코드워드(codeword): 원래 데이터 k bit에 redundant한 데이터를 붙여, 송신자가 실제로 보내는 n bit
  • redundancy: (n-k)/k
  • code rate: k/n. code rate이 작을수록 redundant 데이터가 많고 에러 수정 가능성은 커짐
  • hamming code: 어떤 데이터 블록 단위로 코드워드로 대체되어 전송

    • ex) 2 bit 전송

      00 00000
      01 00111
      10 11001
      11 11110
      • 00100 수신: 코드워드에 없음. 00000였을 확률이 가장 높으므로 이것으로 고침
      • 물론 틀리게 수정할 수도 있지만, 네트워크 계층에서 checksum으로 에러 감지
      • 네트워크에서도 감지 못했다면 트랜스포트 계층에서 TCP checksum, UDP checksum
  • hamming distance: 두 코드워드 사이 비트 차이
    • 5 bit 코드워드를 만들 경우, 2^5=32가지 중 네 개의 코드워드 사이의 해밍 디스턴스가 가장 먼 것들 4개를 선정
    • 각 4개의 코드워드들의 minimum distance = 3
      • 1 비트 에러는 수정 가능
      • 2 비트 에러는 디텍션 가능
      • 3 비트 에러는 감지 불가
  • convolutional code: 이전의 히스토리가 현재 비트를 코드워드로 변경하는데 영향
    • 음성 전화 등은 연속적으로 데이터가 들어오기 때문에 해밍 코드처럼 비트를 나누거나 모아서 코드워드로 전송하기 힘듦
    • 한 비트를 두 비트로 만들어 전송, 즉 code rate = 1/2
    • ex) 01101
      • 0: 레지스터 000 -> 00(000과 순서대로 XOR, 00과 순서대로 XOR)
      • 1: 레지스터 000 -> 11(000과 순서대로 XOR, 00과 순서대로 XOR)
      • 1: 레지스터 100 -> 01(100과 순서대로 XOR, 00과 순서대로 XOR)
      • 0: 레지스터 110 -> 01(110과 순서대로 XOR, 10과 순서대로 XOR)
      • 1: 레지스터 011 -> 11(011과 순서대로 XOR, 11과 순서대로 XOR)
    • 따라서 같은 비트가 들어가도 다른 코드 생성
    • 에러를 감지 및 수정 기능 강함


댓글남기기

참고