Section 01. 프레임

01. 프레임 만들기

- 프레임(frame)

💡 프레임: 데이터 링크 계층의 데이터 단위

• 네트워크 계층(3번)에서 보낸 패킷에 데이터 링크 계층이 사용하는 헤더를 붙인 것.
• 프레임 = 패킷 + 헤더

• 2번 데이터 링크 계층: 물리 계층을 이용하여 LAN에 속해 있는 노드들에게 데이터를 전송.
• 데이터 전송 방식
  • 비동기식 전송: 예고 X
  • 동기식 전송: 예고 O → 현재 사용되는 방식

- 플래그(flag)

💡 플래그: 등기식 전송에서 데이터를 보내기 전에 통신 시작을 알리는 신호

• 시작과 끝을 알려준다

• 프리앰블(preamble) ~ 포스트앰블(postamble)

  

• 프레임 내 플래그와 같은 패턴을 가진 데이터 존재 시, 문제 발생 가능 → 그 앞에 이스케이프 문자(ESC)를 삽입하여 전송 → 프레임 안에 ‘ESC + 플래그‘ 패턴이 있을 경우, 앞에 ESC를 하나 더 붙여 전송

02. 문자 프레임과 비트 프레임

- 문자 프레임

• 문자 데이터를 아스키 코드 형태로 전송
• 프리앰블: DLE STX, 포스트앰블: DLE ETX
  • STX: 전송 텍스트 시작(Start TXt)
  • ETX: 전송 텍스트의 끝(End TXt)
• 문자 스터핑(character stuffing): 데이터에 DLE ETX가 나타나는 경우, 그 앞에 DLE를 하나 더 붙여 전송

→ 현재 거의 사용하지 않는다.

- 비트 프레임

• 대부분 사용하는 방식
• 프리앰블과 포스트앰블에 비트 패턴 사용(01111110, 1이 6번 연속, 8bit)
• 비트 스터핑(bit stuffing): 데이터에 플래그와 같은 패턴이 존재하면 연달아 나타는 1의 다섯 번째 다음에 0을 하나 삽입 (01111110 → 011111010)

Section 02. 슬라이딩 윈도우 프로토콜

01. 데이터 전송 오류

(항상 최악의 상황을 가정한다)

(1) 프레임이 전송 중간 사라지는 경우

송신 A가 보낸 프레임이 사라지는 문제

→ 송신 A는 이 상황을 모른 채 두 번째 프레임 전송

→ 수신 B 또한 이 상황을 모른 채 두 번째로 보낸 프레임을 첫 번째 프레임으로 착각하는 문제 발생

⇒ 응답 메시지(ACK)

에러가 있는 네트워크에서는 프레임을 보낸 쪽에서 제대로 받았는지 알 수 없어 문제가 발생

→ 데이터를 받았다는 신호(ACK)를 받으면 다음 프레임을 전송하자!

⇒ ACK 신호는 데이터를 수신하는 측에서 데이터가 잘 도착했다는 신호

(2) ACK가 전송 중간 사라지는 경우

수신 B가 프레임을 받은 후 보낸 ACK가 사라지는 경우

→ 송신 A는 ACK를 받지 못해 새로운 프레임을 보내지 못하고 대기한다

→ 수신 B는 ACK를 보내고 다음 프레임을 받기 위해 대기한다

→ A, B 모두 무작정 대기하는 상황

⇒ 타임아웃(timeout)

일정 시간동안 기다리는 신호가 도착하지 않으면 해당 신호(프레임, ACK)를 다시 보낸다.

(3) 전송 지연 중 타임아웃되는 경우

수신 B가 보낸 ACK 신호가 지연되어 도착하기 전에 송신 A가 타임아웃되어 동일한 프레임을 또다시 보내는 경우

→ 수신 B는 ACK를 보낸 다음으로 온 프레임이므로 이전에 받은 프레임이 아니라 서로 다른 프레임으로 착각하게 된다.

⇒ 일련번호(sequence number)

송신하는 프레임에 일련번호를 붙여 순서를 정확히 알 수 있게 됨으로써, 프레임이 사라지거나 중복되는 경우 이를 확인할 수 있다.

(3) ACK의 일련번호가 없는 경우

수신 B가 보낸 ACK가 지연 도착하여 송신 A에 타임 아웃, 0번 프레임 재전송

→ 0번 프레임 재전송 후 지연된 ACK 도착

→ 송신 A는 다시 전송한 0번 프레임의 ACK라고 판단해 1번 프레임 전송

→ 1번 프레임 전송 중 사라짐!

→ 수신 B가 두 번째 0번 프레임에 대한 ACK 도착

→ 송신 A는 1번 프레임에 대한 ACK라 착각

→ 2번 프레임 전송

⇒ 악순환 반복

⇒ 응답 메시지(ACK) 일련번호 사용

프레임과 같이 ACK 또한 일련번호를 사용한다.

→ 1번 ACK 도착 이전 2번 프레임을 전송하는 문제 해결

---

- 데이터 전송의 필수 요소

1. 응답 메시지(ACK) 사용
2. 타임아웃 사용
3. 프레임 일련번호 사용
4. ACK 일련번호 사용

양방향 통신이기 때문에 양쪽에서 꾸준히 데이터를 보낸다.

이때, 데이터 없이 ACK만 보내면 낭비이기 때문에 전송되는 데이터에 ACK를 함께 전송하면 네트워크가 덜 혼잡해진다.

⇒ 피기백킹(piggy-backing): 기존의 메시지에 ACK를 얹어서 보내는 방식

• 아기를 등에 업는 모양새라는 뜻이다.

02. 슬라이딩 윈도우 프로토콜

- Stop-and-Wait 방식

• 데이터를 보낸 후 멈추고(stop), ACK를 기다린다(wait)
• 느림, 에러 없는 네트워크에서 ACK를 매번 기다리는 것은 낭비 ⇒ 슬라이팅 윈도우 프로토콜 사용
  

- 슬라이딩 윈도우 프로토콜(sliding window protocol)

💡 슬라이딩 윈도우 프로토콜: ACK 없이 한꺼번에 많은 양의 데이터를 보내 전송 속도를 높이는 방법 (혹은 연속전송 프로토콜)

• 윈도우 크기(window size): 보내는 쪽과 받는 쪽에서 ACK 없이 보낼 수 있는 프레임의 개수
  • window size = 0 → 보내는 쪽에서 ACK 없이도 4개의 프레임을 연속적으로 보낼 수 있다.
• NAK(부정응답): 받지 못한 프레임에 대한 신호

- ARQ(Automatic Repeat Request)

💡 ARQ: 자동 반복 요청. 에러가 발생한 경우 재전송을 요구하는 방식

• 무잡음 채널에서의 프로토콜
  • Simplest
  • Stop-and-Wait
• 잡음이 있는 채널에서의 프로토콜
  • Stop-and-Wait ARQ
  • Go-Back-N ARQ
  • Selective Repeat ARQ
  • Adaptive ARQ

- Stop-and-Wait ARQ

• window size = 1
• 안정적, 하지만 느림

- Go-Back-N ARQ

• window size = N = 연속 전송 방식
• 오류가 난 지점부터 전송 지점까지 모두 재전송
• 1, 2, 3, 4 전송 → 2번 NACK → 2, 3, 4, 5 전송
• 단순, 프레임이 중복됨

- Selective Repeat ARQ

• window size = N = 연속 전송 방식
• 오류가 난 부분만 재전송
• 1, 2, 3, 4 전송 → 2번 NACK → 2, 4, 5, 6 전송
• 수신 B의 큰 버퍼 필요
  • 버퍼에 프레임 3 저장 후 프레임 2 도착 시 순서대로 재조합해야 한다 → 회로도 복잡
    

- Adaptive ARQ

• 전송 효율 최대화를 위해 네트워크에 따라 프레임의 길이를 동적으로 변경
• 네트워크 안정적 → 늘림, 불안정 → 줄임
• 회로 복잡 → 별로 사용 X

Section 03. 오류 처리 코드

01. 오류 처리 코드의 종류

💡 오류 처리 코드: 전달된 데이터가 원본과 다른 경우(오류)를 처리하는 코드.

• 연속 오류(burst error): 데이터가 연속적으로 변하는 오류

1. 오류 탐색 코드(Error detection code): 전달된 데이터에서 에러가 발생했을 경우를 탐지하기 위해 사용하는 코드
   1. 패리트 비트, CRC 코드, 검사합
2. 오류 보정 코드(Error correction code): 에러를 찾는 것 뿐만 아니라 원래의 값으로 보정해주는 코드
   1. 허밍 코드 → 진도 X

오류의 종류

• 단일 오류: 특정 비트의 값이 변하는 것
• 연속 오류: 데이터가 연속적으로 변하는 것

방식	종류	비고
오류 탐색 코드 (Error detection code)	패리트 비트, CRC 코드, 검사합	- 오류를 찾을 때 사용
오류 보정 코드 (Error correction code)	허밍 코드	- 오류를 찾고 워래의 값으로 보정 - 오버헤드가 크다

02. 패리티 비트(parity bit)

💡 패리티 비트는 가장 간단한 오류 탐색 코드이다.

- 원리

데이터에 추가로 1비트를 만들고, 0이나 1을 넣어 전체 1의 개수가 짝수 혹은 홀수가 되도록 만든다.

• 짝수 패리티 비트(even parity bit) / 홀수 패리티 비트(odd parity bit)

간단하다는 장점을 갖지만, 연속 에러에 취약하다.

⇒ 에러가 짝수 개 발생하면 에러를 찾지 못한다.

여러 개의 에러를 찾기 위해 패리티 비트를 수직과 수평으로 배열하는 방법

→ 마찬가지로 짝수 개의 에러에 취약

⇒ 보통, 패리티 비트는 추가되는 1비트 당 1개의 에러를 찾을 수 있다.

03. CRC (Cyclical Redundancy Check, 순환 중복 검사) 코드

💡 CRC 코드는 가장 많이 사용되는 에러 검출 코드.

• 적은 오버헤드로 많은 에러를 찾을 수 있는 장점 때문.

- 원리

1. 보내려는 쪽과 받으려는 쪽에서 똑같은 ‘CRC 코드 값’을 알고 있다.
2. 보내는 쪽에서 데이터를 CRC 코드 값으로 나누었을 때 0이 되는 숫자를 추가하여 보낸다.
3. CRC 코드가 9이고, 보내야할 데이터가 12일 때, 보내려는 데이터는 120 ~ 129 사이의 값이다. 이때, 9로 나눴을 때 나머지가 0인 숫자는 126이기 때문에 126을 전송한다. (126 % 9 = 0)
4. CRC 코드가 9인 경우, 9로 나누어 나머지가 0이 아닌 모든 수가 에러임으로 찾을 수 있는 에러의 개수는 8개가 된다. (120 ~ 129 중 126만 정상)

- 찾을 수 있는 에러의 개수

8비트를 추가할 경우, 패리티 비트는 8개 오류를 찾을 수 있다.

→ 하지만, CRC 코드가 8비트일 때 찾을 수 있는 에러의 개수는 $2^8-1$인 255개가 된다.

같은 맥락으로) 16비트를 추가할 경우, 패리티 비트는 16개 오류를 찾을 수 있다.

→ CRC 코드는 $2^{16}-1$인 65,535개 오류를 찾을 수 있다.

CRC 코드 값은 표준으로 정해져 있다. (CRC-16, CRC-32, CRC-64)

• CRC-32 → 이더넷 헤더, 동영상 포맷인 MPEG-2, PKZIP과 같은 압축 파일, PNG 헤더에 사용

- CRC 자세히 알기(2진수, 나눗셈 연산)

• 2진수에서 CRC 코드 계산 원리
• CRC 코드가 n이면 추가하는 비트는 n-1이다. (딱 떨어지게 해주기 위함)

1. 보내려는 데이터가 1100, CRC 코드 값은 1001로 가정
   1. 실제로 CRC는 수백 메가비트에서 발생할 수 있는 오류를 32비트(CRC-32)로 처리할 수 있다. (더욱 방대하다)

2. 나머지를 붙여서 보내는 만큼 비트 0을 추가한 후 나눗셈을 진행한다.

   1. 1100 + 000 / 1001

   2. CRC에서의 나눗셈은 정확하게는 모듈러(modular) 2 연산(XOR 연산)

      → 같으면 0, 다르면 1

3. 추가 비트만큼의 나머지를 보내려는 데이터(1100)에 붙여서 보낸다.
4. 수신 측에서는 전송된 1100101을 CRC 코드 값인 1001로 나눈다
5. 이때 나머지가 000이 나오면 전송된 데이터에 에러가 없다고 본다. (정상)

추가 예시)

1. CRC 기법의 코드워드 계산 과정 (발신 측)
   

2. CRC 기법의 에러 검증 과정 (수신 측)
   

- CRC 종류에 따른 비트 패턴

CRC 코드 값은 표준으로 정해져 있다.

대표적인 CRC 코드 값

• 다항식 표현: 비트 패턴에서 해당 비트열이 1인 다항식만 표시하는 방법
  • 긴 비트열을 짧게 표현 가능

CRC-16는 17개, CRC-32는 33개.

• 2진수에서 나머지의 크기는 CRC 코드의 크기보다 1 비트 작다.
• 따라서 17자리, 33자리 비트 패턴 사용
• CRC-16의 경우, 나머지는 16비트. CRC-32는 나머지가 32비트

04. 검사합(checksum)

💡 CRC와 유사하지만, 보다 간단한 에러 탐색 방법

- 원리

1. 보내려는 데이터를 일정 크기로 자르고, 더해 에러 탐색 코드를 만든다.

   → 변형되어 우연히 값이 같아진 경우는 찾을 수 없다. ⇒ CRC보다 찾을 수 있는 에러양이 적다.

2. 이때 더한 뒤 1의 보수를 취해 붙인다.

3. 데이터를 수신한 뒤, 모든 비트를 더하고 보수를 취했을 때 최종 결과가 모두 0이 나오면 정상 수신된 것이다.
   

*참고

• 에러 제어
  • 에러 검출: 패리티 검사, CRC, 검사합
  • 에러 복구: Stop-and-Wait ARQ, Go-back N ARQ, SR ARQ
  • 에러 정정: 해밍 코드
• 흐름 제어
  • Sliding Window: window size 조절로 전송 속도 제어