Skip to content
Published on

[컴퓨터 네트워크] 15. 링크 계층: 오류 검출과 다중 접속 프로토콜

🇰🇷KO🇺🇸EN🇯🇵JA
Authors

링크 계층: 오류 검출과 다중 접속 프로토콜

링크 계층(Link Layer)은 인접한 두 노드 사이에서 프레임을 안전하게 전달하는 역할을 담당합니다. 네트워크 계층이 호스트 간 패킷 전달을 책임진다면, 링크 계층은 한 홉(hop) 단위의 통신을 담당합니다.

이 글에서는 링크 계층의 서비스, 오류 검출 기법, 그리고 공유 매체에서의 다중 접속(Multiple Access) 프로토콜을 살펴봅니다.

1. 링크 계층 서비스

1.1 기본 서비스

링크 계층이 제공하는 서비스
=============================

1. 프레이밍 (Framing)
   - 네트워크 계층 데이터그램을 프레임으로 캡슐화
   - 프레임 헤더에 MAC 주소 포함

2. 링크 접속 (Link Access)
   - 공유 매체에서의 접속 제어 (다중 접속 프로토콜)
   - MAC 주소를 사용한 프레임 전달

3. 신뢰적 전달 (Reliable Delivery)
   - 오류율이 높은 링크(무선)에서 ARQ 사용
   - 유선 링크에서는 보통 사용하지 않음

4. 오류 검출 및 정정
   - 비트 오류 검출: 패리티, CRC 등
   - 오류 정정: FEC (Forward Error Correction)

1.2 구현 위치

링크 계층은 주로 NIC(Network Interface Card) 에 구현됩니다. NIC의 하드웨어 칩이 프레이밍, CRC 계산, MAC 프로토콜 등을 처리합니다.

링크 계층 구현
================

[애플리케이션 계층]
[트랜스포트 계층]       CPU / 소프트웨어
[네트워크 계층]
-----------------------
[링크 계층]            NIC (하드웨어 + 펌웨어)
[물리 계층]

2. 오류 검출 기법

2.1 패리티 비트 (Parity Bit)

가장 단순한 오류 검출 방법으로, 데이터 비트에 패리티 비트 하나를 추가합니다.

단일 패리티 비트 (짝수 패리티)
===============================

데이터:     1011010
패리티 비트: 0  (1의 개수가 짝수가 되도록)
전송:       10110100

수신:       10110110  (5번째 비트 오류)
1의 개수:   5 (홀수) --> 오류 검출!

한계: 짝수 개의 비트가 동시에 오류나면 검출 불가

2차원 패리티: 행과 열 모두에 패리티 비트를 추가하여 단일 비트 오류를 정정할 수도 있습니다.

2차원 패리티
==============

데이터 + 행 패리티:
  1 0 1 1 | 1
  0 1 1 0 | 0
  1 1 0 1 | 1
  ----------
  0 0 0 0   (열 패리티)

오류 발생:
  1 0 1 1 | 1
  0 1 0 0 | 0  <-- 행 패리티 불일치
  1 1 0 1 | 1
  ----------
  0 0 1 0    <-- 열 패리티 불일치
        ^
  3번째 열, 2번째 행 --> 오류 위치 특정 및 정정 가능

2.2 인터넷 체크섬 (Internet Checksum)

트랜스포트 계층(TCP, UDP)에서 사용하는 간단한 오류 검출 방법입니다.

인터넷 체크섬 계산
====================

1. 데이터를 16비트 워드 단위로 분할
2. 모든 워드를 1의 보수 덧셈
3. 결과의 1의 보수를 체크섬으로 사용

예시:
  워드 1: 0110 0110 0110 0000
  워드 2: 0101 0101 0101 0101
  -------------------------
  합계:   1011 1011 1011 0101
  체크섬: 0100 0100 0100 1010  (1의 보수)

검증: 수신 측에서 체크섬 포함 모든 워드를 더하면
      결과가 1111 1111 1111 1111 이어야 함

2.3 CRC (Cyclic Redundancy Check)

CRC는 링크 계층에서 가장 널리 사용되는 강력한 오류 검출 방법입니다. 다항식 나눗셈을 기반으로 합니다.

CRC 계산 과정
===============

1. 생성 다항식 G 결정 (송신자와 수신자가 공유)
   예: G = 1001 (x^3 + 1), r = 3비트

2. 데이터 D에 r개의 0을 붙임
   D = 101110, D * 2^r = 101110 000

3. D * 2^r을 G로 XOR 나눗셈하여 나머지 R을 구함

   101110 000 / 1001
   ----------------
        101110 000
   XOR  1001
        --------
         0101 10 000
   XOR    1001
          --------
          0000 1000 0
   XOR          1001
               ------
               0001 0
   나머지 R = 011

4. 전송 비트: D와 R을 연결 = 101110 011

5. 수신 측: 수신 비트를 G로 나누어 나머지 = 0이면 오류 없음

2.4 CRC의 오류 검출 능력

CRC의 강력한 검출 능력
========================

r비트 CRC로 검출 가능한 오류:
  - 모든 단일 비트 오류
  - 모든 2비트 오류 (적절한 G 선택 시)
  - 홀수 개의 비트 오류 (G가 x+1을 인수로 포함 시)
  - r비트 이하의 연속 오류 (burst error)

표준 CRC 다항식:
  CRC-8:  x^8 + x^2 + x + 1
  CRC-16: x^16 + x^15 + x^2 + 1
  CRC-32: 이더넷, WiFi, ZIP 등에서 사용
          32비트 나머지로 매우 강력한 검출

3. 다중 접속 프로토콜

여러 노드가 하나의 공유 브로드캐스트 링크를 사용할 때, 동시 전송으로 인한 충돌(collision)을 해결해야 합니다.

3.1 분류

다중 접속 프로토콜 분류
=========================

1. 채널 분할 (Channel Partitioning)
   - TDMA, FDMA, CDMA
   - 충돌 없지만 비효율적

2. 랜덤 접속 (Random Access)
   - ALOHA, Slotted ALOHA, CSMA, CSMA/CD
   - 충돌 허용, 감지/복구 메커니즘

3. 순번 방식 (Taking-Turns)
   - 폴링, 토큰 패싱
   - 중간 타협점

4. 채널 분할 프로토콜

4.1 TDMA (Time Division Multiple Access)

시간을 고정 크기의 슬롯으로 나누고, 각 노드에 전용 슬롯을 할당합니다.

TDMA 동작
==========

시간 프레임:
  [슬롯1][슬롯2][슬롯3][슬롯4][슬롯1][슬롯2][슬롯3][슬롯4]
   노드A  노드B  노드C  노드D  노드A  노드B  노드C  노드D

장점: 충돌 없음
단점: 노드 A만 데이터가 있어도 자기 슬롯에서만 전송 가능
  --> 채널 대역폭의 1/N만 사용 가능 (낭비)

4.2 FDMA (Frequency Division Multiple Access)

주파수 대역을 나누어 각 노드에 전용 주파수를 할당합니다.

FDMA 동작
==========

주파수
  ^
  |  [노드 D 대역]
  |  [노드 C 대역]
  |  [노드 B 대역]
  |  [노드 A 대역]
  +--------------------> 시간

TDMA와 동일한 장단점
  - 충돌 없지만 대역폭 낭비

5. 랜덤 접속 프로토콜

5.1 ALOHA

하와이 대학에서 개발된 최초의 랜덤 접속 프로토콜입니다.

Pure ALOHA
===========

동작:
  1. 전송할 프레임이 있으면 즉시 전송
  2. 충돌 발생 시 확률 p로 즉시 재전송, (1-p)로 대기

시간:
  [A 전송]
      [B 전송]  <-- A와 겹침, 충돌!
                    [A 재전송]
                         [C 전송]  <-- 충돌 없음

최대 효율: 1/(2e) = 약 18%
  (채널 용량의 18%만 실제 전송에 사용)

5.2 Slotted ALOHA

시간을 슬롯으로 나누고, 슬롯 시작 시점에만 전송을 허용하여 충돌 가능 구간을 줄입니다.

Slotted ALOHA
===============

시간 슬롯:
  | 슬롯 1  | 슬롯 2  | 슬롯 3  | 슬롯 4  | 슬롯 5  |
  |  A 전송 | A+B 충돌| B 전송  |         | C 전송  |
  |  성공   |  실패   |  성공   |  비어있음|  성공   |

최대 효율: 1/e = 약 37%
  (Pure ALOHA의 2배)

가정:
  - 모든 프레임이 같은 크기
  - 시간이 슬롯으로 동기화
  - 슬롯 시작 시점에만 전송 시작

5.3 CSMA (Carrier Sense Multiple Access)

전송 전에 채널을 청취(carrier sense)하여, 다른 노드가 전송 중이면 대기합니다.

CSMA 동작
==========

1. 채널 감지 (Listen before talk)
   - 채널이 비어있으면 --> 전송
   - 채널이 사용 중이면 --> 대기

2. 그래도 충돌이 발생하는 이유: 전파 지연!

시간
  |
  | A가 전송 시작
  |   [A의 신호가 B에 도달하는 중...]
  |   B가 채널을 감지: "비어있네!" --> B도 전송 시작
  |      [충돌 발생!]
  v

전파 지연이 클수록 충돌 확률 증가

5.4 CSMA/CD (CSMA with Collision Detection)

충돌을 감지하면 즉시 전송을 중단하여 채널 낭비를 줄입니다. 이더넷에서 사용하는 방식입니다.

CSMA/CD 동작 과정
====================

1. NIC가 프레임을 수신하면 채널 감지
2. 채널이 비어있으면 전송 시작
3. 전송 중 충돌 감지:
   a. 전송 즉시 중단
   b. 잼(Jam) 신호 전송 (48비트)
   c. 이진 지수 백오프 (Binary Exponential Backoff)

이진 지수 백오프:
  n번째 충돌 후, 0 ~ (2^n - 1) 중 랜덤 선택하여 대기

  1번째 충돌: 0 또는 1 중 선택
  2번째 충돌: 0, 1, 2, 3 중 선택
  3번째 충돌: 0 ~ 7 중 선택
  ...
  10번째 충돌: 0 ~ 1023 중 선택 (최대 10까지)

5.5 CSMA/CD 효율

CSMA/CD 효율 공식
====================

효율 = 1 / (1 + 5 * d_prop / d_trans)

d_prop:  최대 전파 지연 (두 노드 간 최대 거리)
d_trans: 최대 크기 프레임의 전송 시간

특성:
  - d_prop -> 0 이면 효율 -> 1 (이상적)
  - d_trans -> 무한대 이면 효율 -> 1
  - 큰 프레임, 짧은 거리에서 효율적

6. 순번 방식 (Taking-Turns) 프로토콜

6.1 폴링 (Polling)

마스터 노드가 각 슬레이브 노드를 순서대로 지정하여 전송 기회를 부여합니다.

폴링 프로토콜
===============

[마스터]
    |
    |--> "노드 A, 전송하세요" --> [노드 A] 전송
    |
    |--> "노드 B, 전송하세요" --> [노드 B] 전송 (데이터 없음, 패스)
    |
    |--> "노드 C, 전송하세요" --> [노드 C] 전송
    |
    |--> 다시 노드 A부터...

단점:
  - 폴링 오버헤드 (폴링 메시지)
  - 폴링 지연 (순서를 기다림)
  - 마스터 노드 고장 시 전체 네트워크 마비 (단일 장애 지점)

6.2 토큰 패싱 (Token Passing)

특수한 토큰 프레임이 노드 사이를 순환하며, 토큰을 가진 노드만 전송할 수 있습니다.

토큰 패싱 프로토콜
====================

   [A] --> [B] --> [C] --> [D]
    ^                       |
    |_______________________|
         (토큰 순환)

동작:
  1. 토큰이 A에 도착
  2. A에 데이터가 있으면: 데이터 전송 후 토큰을 B로 전달
  3. A에 데이터가 없으면: 토큰을 바로 B로 전달
  4. 반복

장점: 공정성 보장, 충돌 없음
단점:
  - 토큰 오버헤드
  - 토큰 분실 시 복구 필요
  - 한 노드 고장 시 네트워크 장애

7. 다중 접속 프로토콜 비교

프로토콜 비교 요약
====================

프로토콜    | 효율      | 지연   | 공정성 | 복잡도
-----------+----------+--------+--------+--------
TDMA       | 낮음(1/N) | 보장   | 공정   | 단순
FDMA       | 낮음(1/N) | 보장   | 공정   | 단순
Pure ALOHA | 18%      | 가변   | 공정   | 단순
Slotted ALOHA | 37%  | 가변   | 공정   | 단순
CSMA/CD    | 높음     | 가변   | 공정   | 중간
폴링       | 높음     | 폴링지연| 가변  | 중간
토큰       | 높음     | 토큰지연| 공정  | 높음

8. 정리

개념핵심 내용
패리티 비트가장 단순한 오류 검출, 짝수 오류 미검출
CRC다항식 나눗셈 기반, 강력한 burst 오류 검출
CSMA/CD감지 후 전송, 충돌 시 즉시 중단 + 백오프
Slotted ALOHA슬롯 동기화로 효율 37%
이진 지수 백오프충돌 반복 시 대기 범위 2배씩 증가
폴링마스터가 순서 지정, 단일 장애 지점 위험
토큰 패싱토큰 보유 노드만 전송, 공정하지만 오버헤드

다음 글에서는 링크 계층의 대표적 구현인 이더넷, 링크 계층 스위치, 그리고 VLAN을 살펴보겠습니다.

참고 자료

  • James F. Kurose, Keith W. Ross, "Computer Networking: A Top-Down Approach", 6th Edition, Chapter 5
  • IEEE 802.3 - Ethernet Standard
  • Andrew S. Tanenbaum, "Computer Networks", 5th Edition, Chapter 4
Discuss on Twitter • View on GitHub