06 Link Layer and LANs

1. Link Layer 개요

Link layer는 인접한 node 간에 datagram을 전달하는 역할을 한다. “Link”는 통신 경로를 따라 인접 node를 연결하는 통신 채널이다.

1.1 Link Layer 서비스

서비스	설명
Framing	Network layer datagram을 frame으로 encapsulate. Header, trailer 추가
Link access	공유 매체의 경우 채널 접근을 조율하는 MAC(Medium Access Control) protocol
Reliable delivery	인접 node 간 신뢰성 있는 전달. 오류율 높은 link(wireless)에서 주로 사용. 오류율 낮은 link(fiber)에서는 드물게 사용
Error detection	전기 신호 감쇠나 noise에 의한 bit error 검출. Receiver가 오류 발견 시 재전송 요청 또는 폐기
Error correction	재전송 없이 receiver가 직접 bit error를 수정

1.2 Link Layer의 구현 위치

Link layer는 모든 host에서 NIC(Network Interface Card) 또는 칩에 구현된다:

NIC: Ethernet card, WiFi card, 또는 칩셋에 통합
NIC는 link layer와 physical layer를 구현
NIC는 host의 system bus에 연결
Hardware(NIC) + software(driver) + firmware의 조합

2. Error Detection과 Correction

전송 중 bit error가 발생할 수 있으므로, 이를 검출(detection)하고 수정(correction)하는 메커니즘이 필요하다. Sender가 data bits $D$ 에 error detection/correction bits(EDC)를 추가하여 전송한다.

2.1 Parity Checking

Single bit parity: Data bits의 1의 개수가 짝수(even parity) 또는 홀수(odd parity)가 되도록 1 bit를 추가한다. 단일 bit error를 검출할 수 있지만, 짝수 개의 bit error는 검출하지 못한다.

Two-dimensional bit parity: Data bits를 2차원 행렬로 배열하고, 각 행과 열에 parity bit를 추가한다. 단일 bit error를 검출하고 수정할 수 있으며, 2 bit error도 검출할 수 있다(수정은 불가).

2.2 Internet Checksum

UDP, TCP에서 사용하는 checksum:

Data를 16-bit integer의 sequence로 취급
모든 16-bit integer를 더함 (1’s complement sum)
합의 1’s complement를 checksum으로 사용
Receiver가 같은 계산을 하여 결과가 0이면 error 없음

2.3 CRC (Cyclic Redundancy Check)

Link layer에서 가장 강력한 error detection 방식이다. 실무에서 널리 사용된다.

원리:

$D$ : Data bits (주어진 data)
$G$ : Generator bit pattern ( $r + 1$ bits). Sender와 receiver가 합의
$R$ : CRC bits ( $r$ bits). $D$ 에 추가하여 전송
목표: $< D, R >$ (즉 $D \cdot 2^{r} XOR R$ )이 $G$ 로 정확히 나누어지도록 $R$ 을 결정

계산: $R = remainder of \frac{D \cdot 2 ^{r}}{G}$ (modulo-2 arithmetic, XOR 사용)

CRC는 $r + 1$ bits 이하의 burst error를 100% 검출할 수 있다. Ethernet, WiFi, ATM 등에서 사용된다.

3. Multiple Access Protocol

단일 공유 broadcast 채널에서 여러 node가 동시에 전송하면 collision(충돌)이 발생한다. Multiple access protocol은 node가 채널을 공유하는 방식을 결정하는 distributed algorithm이다.

Link의 두 유형:

Point-to-point: Ethernet switch-host 간 전용 link, PPP 등
Broadcast (shared medium): 구형 Ethernet(shared bus), WiFi, upstream HFC, 4G/5G

이상적인 multiple access protocol의 요건 (채널 rate $R$ bps):

하나의 node만 전송 시 → rate $R$ 로 전송 가능
$M$ 개 node가 전송 시 → 각각 평균 $R / M$ 의 rate
완전 분산: 조율을 위한 특별한 node나 clock 동기화가 불필요
단순

3.1 MAC Protocol 분류

분류	설명	예시
Channel Partitioning	채널을 작은 “조각”(time slot, frequency, code)으로 나누어 각 node에 배정	TDMA, FDMA, CDMA
Random Access	채널을 분할하지 않고, collision을 허용하되 복구	ALOHA, Slotted ALOHA, CSMA, CSMA/CD, CSMA/CA
Taking Turns	Node가 순서대로 전송하되, 보낼 데이터가 많은 node가 더 긴 차례를 가짐	Polling, Token passing

3.2 Channel Partitioning

TDMA (Time Division Multiple Access)

시간을 고정 길이 slot으로 나누고, 각 node에 전용 slot을 배정
장점: Collision 없음. 단점: 사용하지 않는 slot은 낭비

FDMA (Frequency Division Multiple Access)

채널 주파수 대역을 분할하고, 각 node에 고정 대역을 배정
장점: 동시 전송 가능. 단점: 사용하지 않는 대역 낭비

3.3 Random Access Protocol

전송할 packet이 있으면 전체 channel rate $R$ 로 즉시 전송한다. 사전 node 간 조율이 없다. Collision이 발생하면 이를 검출하고 복구한다.

Slotted ALOHA

모든 frame이 동일 크기이고, 시간이 동일 크기 slot으로 분할됨 (slot = 1 frame 전송 시간)
Node는 slot 시작 시점에만 전송 시작
Collision 발생 시: 다음 slot에서 확률 $p$ 로 재전송

효율: $N$ 개 node가 확률 $p$ 로 전송할 때, 성공 확률 = $Np (1 - p)^{N - 1}$ . $N \to \infty$ 에서 최대 효율 = $1/ e \approx 0.37$ (37%)

Pure ALOHA (Unslotted)

Slot 동기화 없이 데이터가 있으면 즉시 전송
Collision 확률이 더 높음
최대 효율: $1/ (2 e) \approx 0.18$ (Slotted ALOHA의 절반)

CSMA (Carrier Sense Multiple Access)

“Listen before transmit” - 전송 전에 채널이 사용 중인지 감지한다:

Channel idle: 전체 frame 전송
Channel busy: 전송을 보류(defer)

그러나 CSMA에서도 collision이 발생할 수 있다. Propagation delay 때문에 두 node가 상대방의 전송을 듣지 못하고 동시에 전송을 시작할 수 있기 때문이다. Collision 발생 시 전체 packet 전송 시간이 낭비된다.

CSMA/CD (Collision Detection)

CSMA에 collision detection을 추가한다:

전송 중에 collision을 감지하면 즉시 전송을 중단(abort), 채널 낭비를 줄임
유선 LAN(Ethernet)에서 쉽게 구현 가능. 무선에서는 어려움

Ethernet CSMA/CD 알고리즘:

NIC가 network layer에서 datagram을 받아 frame을 생성
Channel sensing: idle이면 전송 시작, busy이면 idle이 될 때까지 대기
전체 frame이 collision 없이 전송되면 완료
전송 중 다른 전송을 감지하면(collision): 전송을 중단하고 jam signal 전송
Binary (Exponential) Backoff: $m$ 번째 collision 후, $K$ 를 ${0, 1, 2, ..., 2^{m} - 1}$ 에서 랜덤 선택. $K \times 512$ bit times 대기 후 Step 2로 복귀
- Collision이 반복될수록 backoff 범위가 넓어져, 더 오래 기다릴 확률이 높아짐

3.4 Taking Turns

Polling

Master node가 각 node를 순서대로 초대(poll)하여 전송하게 함
단점: Polling overhead, single point of failure (master 장애 시 전체 마비)

Token Passing

제어 token이 node 간 순서대로 순환
Token을 가진 node만 전송 가능. 전송이 끝나면 token을 다음 node에 전달
단점: Token overhead, single point of failure (token 분실 시), latency

4. LAN (Local Area Network)

4.1 MAC Address (Physical Address)

네트워크 interface를 식별하는 두 가지 주소 체계:

	IP Address	MAC Address
크기	32 bits (IPv4)	48 bits
용도	Network layer forwarding (source → destination)	Link layer, 같은 subnet 내 frame 전달
관리	Subnet에 의존 (hierarchical)	NIC ROM에 고정 (flat)
Portability	이동 불가 (subnet에 종속)	이동 가능 (LAN을 바꿔도 MAC 유지)
관리 기관	ICANN	IEEE
표기	Dotted decimal (128.119.40.136)	Hexadecimal (1A-2F-BB-76-09-AD)
비유	우편 주소 (위치 기반)	주민등록번호 (신원 기반)

Broadcast MAC address: FF-FF-FF-FF-FF-FF - LAN 내 모든 node에 frame을 전송

4.2 ARP (Address Resolution Protocol)

IP address만 알고 있을 때, 같은 LAN에 있는 destination의 MAC address를 어떻게 알아낼 것인가? 이것이 ARP의 역할이다.

각 IP node(host, router)는 ARP table을 유지한다:

ARP Table Entry	설명
IP address	대상 node의 IP 주소
MAC address	대상 node의 MAC 주소
TTL	이 매핑이 만료되는 시간 (보통 20분)

ARP 동작 (A가 B의 MAC address를 알고 싶을 때):

A가 B의 IP address를 담은 ARP query를 LAN에 broadcast (dest MAC = FF-FF-FF-FF-FF-FF)
LAN의 모든 node가 ARP query를 수신
B만이 자신의 IP address임을 인식하고, A에게 ARP reply로 자신의 MAC address를 응답 (unicast)
A가 B의 (IP, MAC) 매핑을 ARP table에 저장 (TTL 이후 만료)

ARP는 “plug-and-play” 프로토콜이다 - 관리자 개입 없이 자동으로 동작한다.

4.3 다른 Subnet으로의 Routing: IP와 MAC Address의 역할

Host A(111.111.111.111)가 다른 subnet의 Host B(222.222.222.222)에 datagram을 보내는 과정:

핵심 원리: IP address는 end-to-end로 유지되지만, MAC address는 hop-by-hop으로 바뀐다.

A가 IP datagram 생성: src IP = A, dest IP = B
A가 link-layer frame 생성: src MAC = A의 MAC, dest MAC = R(router)의 MAC (B가 아님!)
- A는 B가 다른 subnet에 있음을 알고, default gateway R의 MAC address를 사용 (ARP로 획득)
Frame이 R에 도착, R이 frame에서 datagram을 추출
R이 forwarding table로 outgoing interface를 결정
R이 새 frame 생성: src MAC = R의 outgoing interface MAC, dest MAC = B의 MAC (ARP로 획득)
- IP datagram은 변경 없이 유지 (src IP = A, dest IP = B)
Frame이 B에 도착, B가 datagram을 추출하여 IP layer로 전달

4.4 Ethernet

Ethernet은 가장 널리 사용되는 유선 LAN 기술이다.

Ethernet Frame 구조:

Field	크기	설명
Preamble	8 bytes	7 bytes의 `10101010` + 1 byte의 `10101011`. Clock 동기화에 사용
Dest Address	6 bytes	Destination MAC address. `FF-FF-FF-FF-FF-FF`이면 broadcast
Source Address	6 bytes	Source MAC address
Type	2 bytes	상위 layer protocol 표시 (주로 IP: 0x0800, ARP: 0x0806)
Data (Payload)	46-1500 bytes	IP datagram 등. 최소 46 bytes(미달 시 padding)
CRC	4 bytes	Error detection. 오류 시 frame drop

Ethernet의 특성:

Connectionless: Handshaking 없이 전송
Unreliable: 수신 NIC가 ACK/NAK를 보내지 않음. Dropped frame은 상위 layer(TCP 등)에서 복구
CSMA/CD with binary backoff 사용 (traditional Ethernet)

Ethernet 표준

IEEE 802.3 Ethernet standard로 정의되며, link layer와 physical layer를 모두 다룬다:

100BASE-TX: 100 Mbps, twisted pair (copper)
100BASE-FX: 100 Mbps, fiber
1000BASE-LX: 1 Gbps, fiber (long distance)
10GBASE-T: 10 Gbps, twisted pair
40GBASE-T: 40 Gbps, twisted pair

4.5 Ethernet Switch

Switch는 link layer device로, Ethernet frame을 store-and-forward하며 MAC address를 사용하여 incoming frame을 적절한 outgoing link로 전달한다.

특성:

Transparent: Host는 switch의 존재를 인식하지 못함
Self-learning: Switch가 스스로 forwarding table을 구성 (plug-and-play, 설정 불필요)

Self-Learning

Switch는 어떤 host에 어떤 interface를 통해 도달할 수 있는지를 학습한다:

Frame이 도착하면 source MAC address를 기록하고, 해당 frame이 들어온 interface와 매핑
해당 (MAC, interface) 매핑을 switch table에 저장 (TTL 이후 만료)

Forwarding

Frame이 switch에 도착했을 때:

Destination MAC이 table에 있으면 → 해당 interface로 forward (self-loop이면 drop)
Table에 없으면 → 도착한 interface를 제외한 모든 interface로 flood

Switch vs Router

비교 항목	Switch	Router
Layer	Link layer (Layer 2)	Network layer (Layer 3)
주소	MAC address	IP address
Table	Self-learning (plug-and-play)	Routing algorithm으로 구성
Broadcast	Broadcast storm 가능	Broadcast domain 분리
Topology	Spanning tree로 loop 방지	임의 topology 가능

4.6 VLAN (Virtual Local Area Network)

물리적 LAN 인프라를 논리적으로 분할하여, 여러 개의 가상 LAN을 구성하는 기술이다.

VLAN의 필요성:

단일 broadcast domain이 너무 크면 효율 저하 (모든 layer 2 broadcast가 전체 LAN에 전파)
부서 이동 시 물리적 재배선 대신 software 설정만으로 LAN을 재구성하고 싶음

Port-based VLAN: Switch의 port를 VLAN 그룹으로 분류. 같은 VLAN의 port만 같은 broadcast domain을 형성.

VLAN 간 통신은 router를 통해서만 가능하다 (Layer 3 routing).

802.1Q VLAN frame: VLAN 간 frame을 전달하기 위해 Ethernet frame에 4-byte VLAN tag를 추가한다. Tag에는 12-bit VLAN ID가 포함되어, 어느 VLAN에 속하는 frame인지 식별한다.

5. Chapter 6 정리

주제	핵심 내용
Link Layer 서비스	Framing, link access (MAC), reliable delivery, error detection/correction
Error Detection	Parity (single/2D), Internet Checksum, CRC (modulo-2, 가장 강력)
Multiple Access	Channel partitioning (TDMA, FDMA), Random access (ALOHA, CSMA, CSMA/CD), Taking turns (polling, token)
Slotted ALOHA	최대 효율 37%. Pure ALOHA는 18%
CSMA/CD	Listen before transmit + collision detection + binary exponential backoff. Ethernet에서 사용
MAC Address	48-bit, flat, NIC ROM에 기록. IEEE 관리. Broadcast: FF-FF-FF-FF-FF-FF
ARP	IP → MAC 변환. Broadcast query + unicast reply. Plug-and-play. TTL 20분
Subnet 간 Routing	IP address는 end-to-end 유지. MAC address는 hop-by-hop 변경
Ethernet	Frame: Preamble + Dest/Src MAC + Type + Data + CRC. Connectionless, unreliable. CSMA/CD
Switch	Layer 2, MAC 기반 forwarding. Self-learning, plug-and-play. Transparent
VLAN	물리적 LAN을 논리적으로 분할. Port-based. 802.1Q tag (12-bit VLAN ID)

탐색기

회고

일상

정원