데이터 통신 #6

데이터 링크1

1. 개요
2. DLC - 프레임 짜기
3. DLC - 오류 제어

개요

데이터 링크층에서의 통신은 노드-대–노드간 통신이다. 인터넷에서 데이터 통신은 LAN과 WAN 같은 네트워크와 네트워크를 연결하는 라우터로 이루어진다.
이런 통신에서 일반적으로 두 종단 호스트와 라우터를 노드(node)라고 하고, 그 사이의 네트워크를 링크(link)라고 한다.

링크는 아래 2가지의 유형을 갖는다.

1. 점-대-점 링크(point to point) : 서로 연결된 2개의 장치(단말)가 전용으로 링크를 이용하는 것 ex. 가정집 전화
2. 브로드캐스트 링크(broadcast link) : 여러 장치 쌍들이 공유되는 링크 ex. 휴대폰 전화 (‘공기’라는 링크가 여러 사용자와 공유됨)

링크 계층은 기능을 이해하기 쉽도록 2가지 부계층으로 분리한다.

1. DLC(Data Link Control) : 데이터 링크 제어, 점-대-점과 브로드캐스트 링크에 관한 내용을 모두 다룸
2. MAC(Media Access Control) : 매체 접근 제어, 브로드캐스트와 관련된 특별한 사항을 다룸

DLC - 프레임 짜기

데이터 링크 제어 기능은 크게 프레임 짜기와 오류 제어가 있다.

1. Framing
   • 비트들을 프레임 안에 넣고 다른 프레임과 구분
   • 프레임 짜기를 통해 송신자와 수신자 주소를 추가해 발신지와 목적지로 가는 메시지를 분리함
     
     
2. 프레임 크기
   • 고정 길이 프레임 : 경계가 필요없음(프레임 크기를 경계로 사용하기 때문이다). ATM에서 주로 셀(cell)이라는 이름으로 사용
   • 가변 길이 프레임 : 프레임이 끝나는 곳과 다음 프레임이 시작하는 곳을 지정해야 하는 길이가 가변적인 프레임, 문자 중심 프로토콜과 비트 중심 프로토콜이 있음
     
     

3. 문자 중심 프로토콜

   

   • 데이터 : 부호화 시스템의 8비트 문자
   • 헤더 : 발신지, 목적지 주소 & 제어 정보 (k * 8비트)
   • 트레일러 : 오류 검출 및 정정 (k * 8비트)
   • Flag : 프레임과 다음 프레임을 구별하는 기준 (8비트)
   • 텍스트 교환에 유리
   • 문자열 통신에 들어가지 않는 비트를 Flag로 사용해 프레임들을 구별한다.
   • 그래프, 오디오, 영상 등이 데이터에 담기면서 Flag 패턴이 데이터 정보 자체에 들어가는 문제가 발생
     
     

4. 바이트 채우기

   

   • Flag와 동일한 비트를 가진 내용이 데이터에 들어있을 때 Flag와 내용을 구분하기 위해 사용
   • 데이터 부분에 ‘특별한 바이트’ 를 추가해 넣는 기술
   • 이런 바이트를 ‘ESC (탈출문자)’ 라고 부르며, ESC는 미리 정해진 비트 패턴을 가짐
   • 수신자는 ESC 문자를 받으면 데이터에서 그 부분을 제거하고 다음 문자를 플래그가 아닌 데이터로 인식함
   • 바이트 채우기로도 완벽하게 플래그와 데이터 오인 문제를 해결하지 못해서 비트 중심 프로토콜을 사용하는 추세
     
     

5. 비트 중심 프로토콜

   

   • 헤더와 프레임을 서로 분리하는 구분자(플래그) 사용
   • 플래그는 대부분 8비트 패턴(01111110) 사용
   • 문자 중심 프로토콜과 똑같은 문제가 발생하고, 이를 해결하기 위해 비트 채우기&빼기를 사용
     
     

6. 비트 채우기&빼기

   

   • 문자 중심 프로토콜과 다르게 플래그와 동일한 패턴을 만나면 뒤에 바이트를 추가하는 방식으로 작동하지 않는다.
   • 비트 채우기 : ‘0’ 1개와 ‘1’ 5개를 연속으로 만나면 그 다음에 무조건 비트 ‘0’을 채워넣음. 즉 011111 뒤에는 무조건 0이 온다.
   • 비트 빼기 : 수신자는 0+11111을 만나면 그 다음에 있는 0을 제거하고 데이터를 읽음.
     
     

DLC - 오류 제어

데이터에서 비트가 변경되는 오류

• 단일 비트 오류 : 데이터 단위 중 하나의 비트만 반전이 일어난 오류
• 폭주(버스트) 오류 : 데이터 단위에서 2개 이상의 연속적인 비트가 반전이 발생한 오류

1. 오류 제어의 구성
   • 중복
     
     • 오류를 검출하기 위해 데이터 이외에 ‘추가 비트’를 보낸다.
     • 추가 비트(중복 비트)는 송신자가 일정 규칙에 의해 추가하며, 수신자는 이를 통해 오류를 찾고 정정한 후 제거한다.
   • 검출
     • 오류가 생겼는지 알아내는 것
     • 오류를 수정할 수 있는지와 오류가 얼마나 발생했는지는 별개의 문제
   • 정정
     • 정확하게 어디서 몇 비트가 잘못 되었는지 알아내 수정하는 과정
2. 부호화
   • 실제 데이터에서 ‘어떤 관계’ 를 이용해 중복 비트를 만들고 제거하는 것
   • ‘블록 부호화’ 와 ‘컨볼루션 부호화’ 가 있음 ( 블록 부호화만 다룬다 )

3. 블록 부호화

   

   • 메시지를 먼저 ‘k비트의 블록’ 으로 나눈다. 이것을 ‘데이터 워드’라고 한다.
   • 각 블록에 r비트의 중복 비트를 추가한다. 총 길이는 n = k + r 이 된다.
   • 이렇게 만들어진 n비트를 ‘코드 워드’ 라고 한다.
   • 데이터워드는 k비트를 사용하므로 총 2^k의 데이터 워드를 만들 수 있다.
   • 코드워드는 n비트를 사용하므로 총 2^n의 코드 워드를 만들 수 있다.
   • 동일한 데이터워드는 동일한 코드 워드로 부호화 된다. ( 일대일 대응 )
   • 따라서 2^n – 2^k 개의 코드 워드는 만들어 질 수 없다.
   • 만들어 질 수 없는 코드 워드를 받은 수신자는 ‘오류’ 라고 판단한다.
   • 수신자는 유효 코드워드(만들어질 수 있는 코드워드)에서는 데이터를 추출하고 유효하지 않은 코드워드는 버린다.
   • 어떤 데이터워드가 오류로 인해 잘못된 코드워드로 변경되었는데, 잘못 변경된 코드워드 또한 유효 코드워드라면, 수신자는 오류를 발견할 수 없다.
     
     
4. 해밍 거리
   • 두 개의 같은 크기의 코드 워드 간에 차이가 나는 비트의 개수
   • 차이가 나는 비트의 수는 두 코드 워드를 XOR 연산해서 나오는 1의 개수로 확인
   • 최소 해밍 거리 : 모든 코드워드 쌍들을 XOR 연산해서 나온 해밍거리 중 최소값, 최소 해밍 거리 = 최대 오류 검출 가능 수 + 1 의 관계를 갖는다.
     
     
5. 선형 블록 코드
   • 두 개의 유효한 코드워드에 대해 XOR 연산을 하면 다른 유효 코드워드를 생성하는 코드
     
     

6. 패리티 검사 코드

   

   • K 비트 데이터워드에 한 비트를 추가해 N = K + 1 비트 코드워드를 만드는 것
   • 추가되는 비트를 포함해서 전체 코드워드의 1의 개수는 짝수개가 되어야 함
   • 최소 해밍 거리는 2 이다.
   • 단일 비트 오류 검출 코드
   • 1의 개수가 짝수개가 아니면 오류가 발생한 것
   • 신드롬(Syndorme) : 코드워드 checker에서 만든 비트, 1의 개수가 짝수개면 0, 홀수개면 1을 생성한다.
   • 신드롬이 0이면 데이터 워드가 만들어지고 1이면 코드 워드가 오류가 발생했다고 판단해서 버려진다.(1의 개수가 짝수여야 하므로)
     
     
7. 순환 코드
   • 선형 블록 코드의 성질과 순환성 성질을 모두 만족하는 코드워드
   • 순환성 : 코드워드를 한 칸씩 왼쪽으로 밀어서 얻는 코드가 다시 코드워드가 되는 구조
   • 밀린 비트는 사라지는 것이 아니라 오른쪽 끝으로 붙음
     
     

8. 순환 중복 검사(CRC : cyclic redundancy check)

   

   • 순환 코드의 성질을 이용한 오류 검출
   • Sender(송신자)는 데이터 워드에 부호기(Generator)를 이용해 코드워드를 생성한다
   • Receiver(수신자)는 코드워드를 받으면 복호기(Checker)를 이용해 데이터 워드를 추출한다.
     
     

9. 순환 중복 검사(CRC : cyclic redundancy check) - 부호기

   

   • 먼저 데이터워드 끝에 추가적으로 0비트를 채운다. 이 때 0비트의 개수는 부호기의 Divisor에 따라 미리 결정되있는 값이다.
   • 부호기에 미리 정해진 Divisor로 코드워드를 나눈다. 이 때 나눗셈은 XOR 연산으로 진행된다.
   • XOR 연산을 한 결과에 맨 앞자리가 0인 경우 다음 XOR 연산은 ‘0000’ 으로 진행
   • 최종적으로 남은 나머지가 데이터 워드에 붙여져서 코드워드가 생성됨
     
     

10. 순환 중복 검사(CRC : cyclic redundancy check) - 복호기

    

    • 나머지를 데이터워드에 붙였기 때문에 복호기에서 부호기의 Divisor로 다시 나눠주면 나눠 떨어져야 함(나눗셈의 특성)
    • 따라서 신드롬이 0 이면 데이터코드를 추출하고, 0이 아니면 버려짐(잘못된 코드워드임)
    • a의 경우 신드롬이 0이므로 올바른 코드워드이고, b는 신드롬이 0이 아니므로 오류가 발생한 코드워드로 판단해 버려짐
      
      
11. 순환 코드의 장점
    • 단일 비트, 두 비트, 홀수 비트, 폭주 오류 검사에 우수한 성능
    • 구현이 쉽고, 속도가 빠름 ( XOR 연산은 비트 연산이라 속도가 매우 빠르다 )
    • 위 장점에 따라 LAN,WAN 등 많은 네트워크에서 사용되는 오류 제어 방법임.
    • 검사합 : 모든 길이의 메시지에 적용할 수 있는 오류 검출 방법