[컴퓨터 네트워크] Data-link layer | Frameing, Error Control methods, MAC Protocols

네트워크는 늘 당연하게 사용해왔지만, 정작 그 내부에서 어떤 일이 벌어지는지에 대해서는 깊이 생각해 본 적이 없었다. 특히 TCP/IP 5계층 모델을 공부하면서 각 계층이 독립적인 역할을 수행하면서도 유기적으로 연결된다는 점이 흥미로웠다. 그중에서도 물리 계층에서 올라온 전기 신호를 의미 있는 데이터 덩어리, 즉 프레임(frame)으로 만들고 인접한 노드까지 안전하게 전달하는 데이터 링크 계층(Data-Link Layer)의 역할에 주목하게 되었다. '어떻게 비트들의 나열이 정확한 데이터로 변환되고, 어떻게 수많은 장치가 하나의 회선을 공유하면서도 충돌을 피할 수 있을까?' 이 근본적인 질문에 대한 답을 찾기 위해 학습한 내용을 정리해보기로 했다.

1. 데이터 링크 계층의 역할 및 구조

데이터 링크 계층(Data-link Layer)은 노드 대 노드(node-to-node) 통신을 담당하는 계층이다. 인터넷은 연결 장치들에 의해 서로 연결된 네트워크들의 조합이다.

Nodes and Links

이 계층의 임무 범위(Duty scope)는 네트워크 계층으로부터 받은 데이터그램(datagram)을 경로의 다음 노드로 전달하는 것이다. 데이터 링크 계층은 데이터그램을 프레임(frame)이라고 불리는 패킷으로 캡슐화(encapsulates)한다.

경로상의 각 중간 노드(intermediate node)는 서로 다른 프로토콜과 프레임 형식을 사용하기 위해 캡슐화와 역캡슐화를 모두 수행해야 한다. 링크는 유선 LAN, 무선 LAN, 유선 WAN 또는 무선 WAN일 수 있으며, TCP/IP는 모든 표준 및 사설 프로토콜을 지원한다.

Services

링크의 두 가지 범주가 존재한다.

점대점 링크(Point-to-point link)는 두 장치에 전용으로 사용된다.
브로드캐스트 링크(Broadcast link)는 여러 쌍의 장치 간에 공유된다.

데이터 링크 계층은 두 가지 부계층으로 나뉜다.

데이터 링크 제어(DLC, Data Link Control)는 점대점 링크와 브로드캐스트 링크 모두에 공통적인 모든 문제들을 다룬다.
매체 접근 제어(MAC, Media Access Control)는 브로드캐스트 링크에 특정한 문제만을 다룬다.

Two sublayers

2. 프레이밍 (Framing)

프레이밍은 비트들을 프레임으로 묶어 각 프레임이 다른 프레임과 구별될 수 있도록 하는 과정이다. 프레이밍은 송신자 주소와 목적지 주소를 추가하여 메시지를 분리한다. 메시지가 매우 큰 프레임으로 구성되면 흐름 및 오류 제어가 매우 비효율적일 수 있으므로, 메시지는 더 작은 프레임으로 분할된다.

프레이밍 크기(Framing Size)는 두 가지 유형이 있다.

고정 크기 프레이밍(Fixed-size framing): 프레임의 경계를 정의할 필요가 없다. ATM WAN에서 셀(cells)이라는 고정 크기 프레임을 사용하는 것이 예시이다.
가변 크기 프레이밍(Variable-size framing): 한 프레임의 끝과 다음 프레임의 시작을 정의할 방법이 필요하며, LAN에서 주로 사용된다.

가변 크기 프레이밍 기법은 두 가지가 있다.

문자 기반 프레이밍(Character-Oriented Framing): 전송될 데이터는 ASCII와 같은 코딩 시스템의 8비트 문자로 이루어져 있다. 프레임의 시작과 끝에 8비트 플래그(flag)를 추가하여 프레임을 분리한다. 데이터 섹션에 플래그와 동일한 패턴의 문자가 있을 때 이스케이프 문자(Escape character, ESC)라는 특수 바이트를 추가하는 바이트 스터핑(Byte stuffing)/언스터핑이 사용된다.
Character-Oriented Framing
비트 기반 프레이밍(Bit-Oriented Framing): 프레임의 데이터 섹션은 비트 시퀀스이다. 구분자(delimiter)로 0111110이라는 특수 8비트 패턴 플래그를 사용하여 프레임의 시작과 끝을 정의한다. 데이터 내에 0이 뒤따르는 5개의 연속된 1이 있을 때마다 추가 0을 삽입하는 비트 스터핑(Bit stuffing)/언스터핑을 통해 수신자가 0111110 패턴을 플래그로 오인하는 것을 방지한다.
Bit-Oriented Framing

3. 오류 제어 (Error Control)

오류 제어는 데이터 통신 시스템의 정확성을 보장하는 데 중요하다.

오류의 유형은 두 가지이다.

단일 비트 오류(Single-bit error): 주어진 데이터 단위의 한 비트만 변경되는 것이다.
버스트 오류(Burst error): 데이터 단위에서 2개 이상의 비트가 변경되는 것이다.

Types of Errors

오류를 감지하거나 수정하기 위해 데이터와 함께 여분성(Redundancy)을 위해 일부 추가 비트(extra bits)를 전송해야 한다.

Redundancy

블록 코딩(Block Coding)은 수신자가 유효한 코드워드 목록을 가지고 있거나 찾을 수 있으며, 원래의 코드워드가 유효하지 않은 코드워드로 변경되었을 때 오류를 감지하는 기법이다.

Block Coding Example

해밍 거리(Hamming Distance, $d(x, y)$)는 같은 크기의 두 단어에서 해당하는 비트들의 차이의 수이며, 전송 중 손상된 비트의 수이다.

Hamming Distance

최소 해밍 거리($d_{min}$)는 코드워드 쌍 간의 가장 작은 해밍 거리이다.

오류 감지: 최대 $s$ 개의 오류를 감지하려면, $d_{min} = s + 1$이어야 한다. 예를 들어, $d_{min}=2$는 단일 오류만 감지함을 보장하고, 두 개의 오류가 발생하면 감지하지 못할 수도 있다. $d_{min}=4$는 최대 세 개의 오류($s=3$) 감지를 보장한다.
Hamming Distance for Error Detection
오류 수정: 최대 $t$ 개의 오류를 수정하려면, $d_{min} = 2t + 1$이어야 한다.
Hamming Distance for Error Correction

선형 블록 코드(Linear Block Codes)는 오늘날 사용되는 거의 모든 블록 코드가 속하는 유형이다. 두 유효 코드워드의 XOR 연산 결과가 또 다른 유효 코드워드를 생성하는 특성이 있다. 선형 블록 코드의 $d_{min}$은 코드 세트 내에서 0이 아닌 코드워드에 있는 1의 최소 개수에 의해 결정된다.

Linear Block Code Example

패리티 검사 코드(Parity Check Code)는 $k$-비트 데이터워드를 $n$-비트 코드워드($n=k+1$)로 변경하며, 추가 비트인 패리티 비트(parity bit)는 코드워드 내의 1의 총 개수를 짝수로 만들기 위해 선택된다. 이 코드의 $d_{min}=2$이며, 단일 비트 오류를 감지하는 코드이다. 단순 패리티 검사 코드는 홀수 개의 오류를 감지할 수 있다. 수신 측 검사기에서 5비트 전체에 대해 모듈러 산술(% 2)을 수행하여 얻는 결과는 신드롬($s_0$)이라고 불린다.

Parity Check Code

순환 코드(Cyclic Codes)는 코드워드가 순환적으로 이동(rotated)될 때 그 결과가 또 다른 코드워드가 되는 추가 속성을 가진 특수 선형 블록 코드이다.

Cyclic Code

순환 중복 검사(CRC, Cyclic Redundancy Check)는 LAN 및 WAN과 같은 네트워크에서 사용되는 오류 감지 기법이며, 선형 및 순환 속성을 모두 가진다. 이는 이진 단어를 다항식(polynomial)으로 표현하고, 인코더와 디코더에서 나눗셈을 수행하는 과정이다.

CRC의 가장 핵심적인 전제는 이진 비트열(binary word)을 다항식(polynomial)으로 표현하는 것이다. 예를 들어, 10011이라는 5비트 데이터가 있다면, 각 비트를 다항식의 계수로 생각하는 방식이다.

이렇게 비트열을 다항식으로 바꾸어 생각하면, 오류 검출 문제를 정교한 대수학(algebra)의 영역으로 가져올 수 있게 된다. 이것이 CRC의 모든 마법이 시작되는 지점이라는 생각이 들었다.

CRC는 송신자와 수신자 간의 '약속된 나눗셈'을 기반으로 동작한다. 전체적인 과정은 생각보다 명료했다.

1. 생성 다항식(Generator Polynomial)의 공유

먼저 송신자와 수신자는 데이터를 나누는 데 사용할 생성 다항식(Divisor)을 미리 약속해야 한다. 어떤 생성 다항식을 사용하느냐에 따라 CRC의 오류 검출 능력이 결정되며, 통신 표준마다 특정 목적에 최적화된 다항식들이 정의되어 있다. 예를 들어, LAN 통신에는 주로 CRC-32가 사용된다.

2. 송신 측: 나머지(Remainder)를 계산하여 덧붙이기

데이터를 보내려는 송신자는 다음과 같은 과정을 거친다.

데이터 확장: 원본 데이터(Dataword) 뒤에 생성 다항식의 최고 차수만큼 0을 덧붙여 피제수(Dividend)를 만든다. 예를 들어 생성 다항식이 $x^{3} + x + 1$ (4비트)이라면 3개의 0을 덧붙인다.
나눗셈 수행: 확장된 데이터를 생성 다항식으로 나눈다. 이때의 나눗셈은 일반적인 뺄셈 대신 XOR 연산(Modulo-2)을 사용한다.
코드워드 생성: 이 나눗셈의 결과로 나온 나머지(Remainder)가 바로 CRC 값이다. 송신자는 이 CRC 값을 원본 데이터 뒤에 덧붙여 코드워드(Codeword)를 만든 후, 이를 수신자에게 전송한다.

CRC Encoder

이렇게 생성된 코드워드는 생성 다항식으로 나누었을 때 나머지가 0, 즉 완벽하게 나누어 떨어지는 특징을 갖게 된다.

3. 수신 측: 나누어 떨어지는지 확인하기

데이터를 수신한 쪽에서는 간단한 검증 절차를 진행한다.

나눗셈 수행: 수신한 전체 코드워드를 송신자와 약속했던 동일한 생성 다항식으로 나눈다.
나머지 확인:
- 나머지가 0이면 (Syndrome이 0), 전송 과정에 오류가 없다고 판단하고 데이터를 수락한다.
- 나머지가 0이 아니면, 데이터에 오류가 발생했다고 판단하고 해당 프레임을 폐기(Discard)한다.
  CRC Decoder

전송 중 단 하나의 비트라도 바뀌면, 다항식의 전체 구조가 바뀌게 되어 나눗셈의 나머지가 0이 아닐 확률이 매우 높아진다. CRC는 이러한 원리를 이용해 높은 신뢰도로 버스트 오류(Burst error)까지 검출할 수 있다.

전체 CRC 개요를 요약하면 다음과 같다.

CRC Overview

체크섬(Checksum)은 모든 길이의 메시지에 적용될 수 있는 오류 감지 기술이며, 주로 네트워크 및 전송 계층에서 사용된다. 생성기는 메시지를 $m$-비트 단위로 나누고 추가 $m$-비트 단위(체크섬)를 생성한다. 수신 측 검사기는 메시지와 전송된 체크섬의 조합으로부터 새로운 체크섬을 생성하며, 이 새로운 체크섬이 모두 0이면 메시지가 수락되고, 그렇지 않으면 메시지가 폐기된다.

4. 데이터 링크 제어 (DLC Protocols)

두 가지 주요 DLC 프로토콜이 있다.

HDLC(High-Level Data-Link Control): 많은 LAN 프로토콜의 기반이며, 점대점 및 다중점 링크를 통한 통신을 위한 비트 지향 프로토콜이다. NRM(Normal Response Mode)과 ABM(Asynchronous Balanced Mode)이 포함된다.
PPP(Point-to-Point Protocol): HDLC에서 파생되었으며, 점대점 링크에 사용된다.

HDLC 프레임은 세 가지 유형이 있다.

I-프레임(Information frames): 사용자 데이터와 사용자 데이터와 관련된 제어 정보(piggybacking)를 전송한다.
S-프레임(Supervisory frames): 제어 정보를 전송한다.
U-프레임(Unnumbered frames): 시스템 관리를 위해 예약되어 있다.

HDLC frames

5. 매체 접근 제어 (MAC Protocols)

매체 접근 프로토콜은 와이어나 공기와 같은 공유 매체를 다른 사용자와 공유할 때, 이 공유 과정을 관리하고 데이터 전송을 수행하기 위해 필요하다.

Media Access Protocols

랜덤 액세스(Random Access) 방식에서는 어떤 스테이션도 다른 스테이션보다 우위에 있지 않으며, 제어권이 할당되지 않는다(동등지위). 데이터를 보낼 스테이션은 프로토콜이 정의한 절차를 사용하여 전송 여부를 결정하며, 이는 매체의 상태(유휴 또는 사용 중)에 따라 달라진다. 둘 이상의 스테이션이 전송을 시도하면 충돌(Collision)이 발생하고 프레임이 파괴되거나 수정된다.

Pure ALOHA는 가장 초기의 랜덤 액세스 방식이다 (1970년대 하와이 대학교에서 개발되었다). 각 스테이션은 데이터가 있을 때마다 프레임을 보내지만, 단일 채널을 공유하면 충돌이 발생할 가능성이 있다. 프레임의 한 비트라도 다른 프레임과 채널에서 겹치면 둘 다 파괴되며, 충돌로 손실된 프레임은 재전송되어야 한다.

Pure ALOHA

취약 시간(Vulnerable time): 충돌 가능성이 있는 시간의 길이를 의미하며, Pure ALOHA의 경우 프레임 전송 시간($T_{fr}$)의 2배($2 \times T_{fr}$)이다.
처리량(Throughput, $S$): 성공적으로 전송된 프레임의 평균 개수이며, $S = G \times e^{-2G}$이다. 최대 처리량 $S_{max}$는 $G = 1/2$일 때 약 $0.184$이다.

Slotted ALOHA는 Pure ALOHA의 변형이며, 취약 시간은 $T_{fr}$이다. 처리량은 $S = G \times e^{-G}$이며, 최대 처리량 $S_{max}$는 $G = 1$일 때 약 $0.368$이다.

Slotted ALOHA

CSMA(Carrier Sense Multiple Access)는 충돌 가능성을 최소화하고 성능을 높이기 위해 전송 전에 매체를 먼저 청취하는 방식이다. 전파 지연(propagation delay) 때문에 충돌 가능성을 완전히 제거할 수는 없다.

CSMA

CSMA의 취약 시간은 전파 시간($T_p$)이다.
지속성 방법(Persistence methods)은 채널이 사용 중일 때 스테이션이 취해야 할 행동을 정의한다.

1-지속형(1-persistent): 스테이션이 라인이 유휴 상태임을 발견한 후, 확률 1로 즉시 프레임을 전송한다 (이더넷에서 사용된다).
비지속형(Nonpersistent): 라인이 유휴 상태이면 즉시 전송하고, 유휴 상태가 아니면 무작위 시간 동안 기다린 후 다시 라인을 감지한다.
p-지속형(p-persistent): 라인이 유휴 상태임을 발견한 후, 확률 $p$로 프레임을 전송하거나, 확률 $q = 1-p$로 다음 시간 슬롯의 시작까지 기다렸다가 라인을 다시 확인한다.

CSMA/CD (CSMA with Collision Detection)는 스테이션이 프레임을 보낸 후 전송이 성공했는지 확인하기 위해 매체를 모니터링하는 방식이다. 충돌이 발생하면 프레임은 다시 전송된다.

CSMA collision

최소 프레임 크기: 충돌 감지 및 전송 중단을 위해 프레임 전송 시간($T_{fr}$)은 최대 전파 시간($T_p$)의 최소 두 배 이상이어야 한다($T_{fr} \ge 2T_p$). 표준 이더넷의 최소 프레임 크기는 512비트(64바이트)이다.

CSMA/CD

제어 접근(Controlled Access) 방식에서는 스테이션들이 서로 협의하여 전송할 권한이 있는 스테이션을 찾으며, 스테이션은 다른 스테이션의 승인을 받기 전에는 전송할 수 없다.

예약(Reservation): 스테이션은 데이터를 보내기 전에 예약을 해야 하며, 시스템에 $N$ 개의 스테이션이 있다면 예약 프레임에는 정확히 $N$ 개의 예약 미니슬롯이 있다.
Reservation
폴링(Polling): 하나의 장치가 주 스테이션(primary station)으로, 다른 장치들이 보조 스테이션(secondary stations)으로 지정된 토폴로지에서 작동한다(-> Bluetooth에 활용). 주 장치는 데이터를 보낼 때 'Select'를 사용하고, 보조 장치로부터 전송을 요청할 때 'Poll'을 사용한다.
Polling
토큰 전달(Token Passing): 네트워크의 스테이션들이 논리적 링(logical ring)으로 조직되며, 토큰(token)이라는 특수 패킷이 링을 순환하며, 토큰을 소유한 스테이션이 채널에 접근할 권한을 얻는다(마치 수건돌리기를 하듯, 토큰을 주고 받음).
Token Passing

6. 링크 계층 주소 지정 (Link-Layer Addressing)

연결 없는 인터넷워크에서 IP 주소와 달리, 정확한 지점을 정의하는 링크 계층 주소(Link address), 즉 물리적 주소(physical address) 또는 MAC 주소가 필요하다.

Link-Layer Addressing

세 가지 유형의 주소가 있다.

유니캐스트 주소(Unicast Address): 일대일 통신이며, 유니캐스트 목적지 주소를 가진 프레임은 링크 내의 단 하나의 개체만을 대상으로 한다. 이더넷 유니캐스트 주소는 48비트(6바이트)이며, 12개의 16진수로 표현되고, 두 번째 숫자는 짝수여야 한다 (예: A2:34:45:11:92:F1).
멀티캐스트 주소(Multicast Address): 일대다 통신이며, 관할권은 링크 내부(local)이다. 이더넷 멀티캐스트 주소는 48비트이며, 두 번째 숫자는 홀수여야 한다 (예: A3:34:45:11:92:F1).
브로드캐스트 주소(Broadcast Address): 일대다(One-to-All) 통신이며, 목적지 브로드캐스트 주소를 가진 프레임은 링크 내의 모든 개체로 전송된다. 이더넷 브로드캐스트 주소는 48비트가 모두 1로 설정된다 (FF:FF:FF:FF:FF:FF).

여기서 문득 이런 의문이 들 수 있다. 내 컴퓨터가 같은 네트워크에 있는 다른 컴퓨터로 데이터를 보낼 때, IP 주소만 아는 상태에서 어떻게 그 컴퓨터의 랜카드(MAC 주소)를 정확히 찾아내는 걸까? 논리적 주소와 물리적 주소 사이의 간극을 메워주는 연결고리가 반드시 필요하다는 생각이 들었고, 그 해답이 바로 주소 결정 프로토콜(ARP, Address Resolution Protocol)에 있었다.

상황 설정: 커피숍의 당신과 친구 '민준'

당신(PC 'A')이 하나의 와이파이(Wi-Fi)에 연결된 커피숍(로컬 네트워크, LAN)에 있다고 상상해 보자. 당신은 친구 '민준'(PC 'B')에게 쪽지를 전달하고 싶다.

아는 것: 친구의 이름은 '민준'이라는 사실을 안다. ➡️ 이것이 바로 IP 주소다. 논리적이고 사람이 기억하기 쉬운 주소 체계다.
모르는 것: '민준'의 얼굴과 지금 어디에 앉아 있는지는 모른다. ➡️ 이것이 바로 MAC 주소다. 실제 장비를 가리키는 고유한 물리적 식별자다.

1단계: "민준"을 찾습니다 (ARP Request 📣 Broadcast)

'민준'의 얼굴과 자리를 모르니 쪽지를 바로 전달할 방법이 없다. 그래서 당신은 자리에서 일어나 커피숍에 있는 모든 사람이 들을 수 있도록 큰 소리로 외친다.

"혹시 '민준'씨 계신가요? 계시면 저 좀 봐주세요!"

이것이 바로 ARP 요청(Request) 브로드캐스트(Broadcast)다. 같은 네트워크에 연결된 모든 장치에게 "이 IP 주소(민준)를 가진 사람은 누구인가요?"라고 질문을 던지는 과정이다. 이 외침은 특정 대상을 정하지 않고 모두에게 전달된다.

2단계: "네, 저 여기 있어요!" (ARP Reply 🙋‍♂️ Unicast)

이 외침을 들은 커피숍의 다른 손님들은 자신의 이름이 '민준'이 아니므로 그냥 무시한다.

오직 진짜 '민준'만이 당신의 외침에 반응한다. '민준'은 손을 들고 다른 사람에게는 들리지 않게, 당신에게만 직접 "네, 저 여기 있어요!"라고 대답한다.

이것이 ARP 응답(Reply) 유니캐스트(Unicast)다. 브로드캐스트 요청을 보낸 'A'에게만 "그 IP 주소는 바로 나고, 내 MAC 주소(얼굴과 자리)는 이것입니다"라고 1:1로 응답하는 과정이다.

3단계: 얼굴과 자리를 기억해두기 (ARP Cache 📝)

이제 당신은 '민준'의 얼굴과 자리를 명확히 알게 되었다. 이 정보는 꽤 유용하므로, 당신은 이 사실을 수첩에 잠시 적어둔다.

이것이 바로 ARP 캐시(Cache)다. 운영체제는 이렇게 확인된 IP-MAC 주소 매핑 정보를 'ARP 캐시'라는 테이블에 일정 시간 동안 저장해 둔다. 다음에 또 '민준'에게 쪽지를 보낼 일이 생기면, 굳이 커피숍 전체에 소리칠 필요 없이 수첩을 보고 바로 '민준'의 자리로 찾아가 쪽지를 건넬 수 있다. 통신 효율이 훨씬 높아지는 셈이다.

ARP protocol

정리하며

데이터 링크 계층은 눈에 보이지 않는 비트의 흐름을 '프레임'이라는 의미 있는 단위로 만들고, 오류를 제어하며, 공유된 매체 위에서 질서를 유지하는 중요한 역할을 담당하고 있었다. 특히 CSMA/CD 방식이 왜 최소 프레임 크기를 필요로 하는지, 그리고 IP 주소와 MAC 주소가 어떻게 ARP를 통해 협력하는지를 이해하게 된 것이 가장 큰 수확이었다. 단순한 개념 암기를 넘어 '왜 이렇게 설계되었을까?'라는 질문을 던지며 원리를 파고드는 과정이 컴퓨터 과학의 진정한 재미라는 생각이 들었다. 다음에는 네트워크 계층으로 올라가, 이 프레임들이 어떻게 경로를 찾아 목적지까지 찾아가는지 탐구해볼 계획이다.

추천글

[컴퓨터 네트워크] 데이터 통신의 기본 요소와 TCP/IP 5계층

[컴퓨터 네트워크] Physical Layer | 비트(Bit)가 아날로그 신호(Signal)로 변환되는 원리

[컴퓨터 네트워크] Physical Layer | 데이터 전송 속도의 한계, 아날로그의 디지털화 & 디지털의 아날로그화