Datalink Layer - Multiple Access

AI 네트워킹 중간범위 — 노션 강의 노트를 옵시디언용으로 정리한 노트.

데이터 링크 계층의 구조

데이터 링크 계층(Data Link Layer)은 기능 중심으로 두 개의 서브레이어로 나뉜다.
상위 — Data Link Control (데이터 링크 제어): 흐름 제어(flow control), 오류 제어(error control), 프레임 관리.
하위 — Multiple Access / MAC (다중 접근 제어): 여러 노드가 공유 매체를 어떻게 공유할지결정.

Multiple Access Protocol (다중 접근 프로토콜)

여러 노드(스테이션)가 하나의 링크(멀티포인트/브로드캐스트 링크)를 공유할 때, 동시에 데이터를 보내면 **충돌(collision)**이 발생한다.
“누가 언제 보낼지”를 조정하기 위해 사용하는 것이 Multiple Access Protocol이다.

세 가지 분류

Multiple Access Protocol
 ├─ Random Access     (경쟁 기반)
 ├─ Controlled Access (제어 기반)
 └─ Channelization    (자원 분할)

구분	방식	충돌	특징
Random Access	경쟁	발생	단순, 현실적
Controlled Access	순서 제어	없음	오버헤드 존재
Channelization	자원 분할	없음	고정 할당

Random Access (경쟁 기반)

동작: 각 노드가 독립적으로 판단해 전송 → 충돌 발생 시 재전송.
이유: 현실 트래픽은 예측 불가(burst, 랜덤) → 그래서 가장 많이 쓰이고 다뤄진다. 중앙 제어 없이 유연하게 동작.
특징: 충돌을 본질적으로 제거할 수는 없고 확률적으로 줄인다.
예: ALOHA(아무 때나 보냄), CSMA(듣고 보냄), CSMA/CD(충돌 감지), CSMA/CA(충돌 회피).

Controlled Access (제어 기반)

동작: 누가 보낼지 미리 정해진다. → 충돌을 아예 없애기 위함.
방법: Reservation(미리 예약), Polling(중앙이 순서 지정), Token Passing(토큰 가진 노드만 전송).
Trade-off: 충돌 없음 / 대기 시간·관리 오버헤드.

Channelization (자원 분할)

동작: 링크를 물리적으로 나눈다. → 충돌을 구조적으로 제거.
방법: FDMA(주파수 분할), TDMA(시간 분할), CDMA(코드 분할).
Trade-off: 충돌 없음 / 자원 낭비(idle slot, unused band) 가능.

Random Access

경쟁(contention) 기반 접근. 모든 스테이션이 동등한 권한을 가지며, 어떤 스테이션도 다른 스테이션을 제어하지 않는다.
하나 이상의 스테이션이 동시에 전송하면 **접근 충돌(access collision)**이 발생, 프레임이 손상될 수 있다.
Station = 네트워크에 연결된 통신 주체(노드), 데이터 전송 단위.

Random Access Protocol이 풀어야 할 4가지 문제

(When) 언제 보낼지
(Busy) 매체가 바쁠 때 무엇을 할지
(Result) 전송의 성공/실패를 어떻게 판단할지
(Collision) 충돌 시 어떻게 처리할지

→ ALOHA, CSMA, CSMA/CD, CSMA/CA는 이 네 문제에 대한 각기 다른 해답이다.

ALOHA 프로토콜

1970년대 초 하와이 대학교에서 개발된 가장 초기의 랜덤 접근 방식.
중앙에 Base Station(기지국, 중앙 제어기, 1-hop)이 존재하며 모든 노드가 같은 채널을 공유. 항상 Station → Base Station → Station으로 동작.
업/다운 링크 주파수를 분리(예: 업로드 407 MHz, 다운로드 413 MHz). 모든 업로드 채널이 같은 주파수(407 MHz)이므로 동시에 보내면 충돌 가능.
동작: ① 데이터 생성 → ② listen 없이 즉시 전송 → ③ Base station 수신 → ④ 다른 노드로 전달.
핵심: 그냥 보내고, 충돌 나면 다시 보내는 가장 원시적인 랜덤 접근.

Pure ALOHA (순수 알로하)

전송할 프레임이 생기면 즉시 전송. 단일 채널 공유 → 충돌 발생 → 실패 시 재전송.
프레임이 일부만 겹쳐도 전체 프레임이 손상된다.

ALOHA 동작 규칙 (플로우차트)

변수: K = 시도 횟수, Tp = 최대 전파 지연, Tfr = 프레임 전송 평균 시간, TB = 백오프 시간, R = 랜덤 값.

전송할 프레임이 있으면 시작, K = 0.
프레임 전송.
2 × Tp(왕복 = 최대 전파 시간의 2배)만큼 ACK 대기(타임아웃).
시간 내 ACK 수신 → 성공(종료). 아니면 실패(5번).
ACK 없음 → 실패, K = K + 1.
K > Kmax 이면 abort(중단), 아니면 7번.
0 ~ 2^K − 1 사이의 랜덤 값 R 선택.
**TB = R × Tp (또는 R × Tfr)**만큼 대기 — 이진 지수 백오프(binary exponential backoff).
다시 프레임 전송.

Tp(최대 전파 시간) = 거리 / 전파 속도.

취약 시간 (vulnerable time)과 처리량

순수 ALOHA 취약 시간 = 2 × Tfr— 전송 시작 후 2 × Tfr 안에 다른 프레임이 시작하면 충돌.
처리량: S = G × e^(−2G), 최대 Smax = 0.184 (G = 0.5).
G = 단위 시간당 전송 시도 수(트래픽 강도), S = 실제 성공 전송 수.
S는 취약 구간 동안 다른 프레임이 0개 발생할 확률(포아송 분포 기반).

Slotted ALOHA (슬롯 알로하)

시간을 Tfr 길이의 슬롯으로 나누고, 각 스테이션은 반드시 슬롯 시작 시점에서만전송.
취약 시간이 2 × Tfr → Tfr로 줄어든다.
처리량: S = G × e^(−G), 최대 Smax = 0.368 (G = 1).

CSMA (Carrier Sense Multiple Access)

원칙: “sense before transmit” / “listen before talk”— 보내기 전에 채널을 감지.
충돌 가능성을 줄이지만 완전히 제거하진 못한다: 전파 지연(propagation delay) 때문에, 다른 스테이션의 첫 비트가 아직 도달하지 않아 매체를 비었다고 오판할 수 있다.
CSMA 취약 시간 = Tp(전파 지연)— 신호가 모든 노드에 도달하기 전까지는 다른 노드가 채널을 비었다고 착각할 수 있다.

Persistence Methods (지속성 전략)

채널이 바쁠 때 “어떻게 기다리고 다시 시도할지” 결정하는 전략. 세 가지가 있다.

방식	행동	특징
1-persistent	idle 되는 순간 즉시 전송(확률 1)	빠르지만 충돌 많음
non-persistent	busy면 랜덤 시간 대기 후 다시 감지	충돌 적지만 지연 증가
p-persistent	idle 시 확률 p로 전송, q=1−p로 다음 슬롯까지 대기	중간 타협(슬롯 기반 시스템에서 사용)

1-persistent: idle 되는 순간 여러 노드가 동시에 시도 → 충돌이 많다.
non-persistent: 충돌은 줄지만 불필요한 대기가 생길 수 있다.
p-persistent: 충돌과 지연 사이의 타협.

CSMA/CD (Collision Detection)

CSMA에 충돌 처리 절차를 추가. 전송 후에도 매체를 모니터링하여 충돌을 감지하면 즉시 중단하고 랜덤 backoff 후 재전송.

채널 감지(idle이면 전송).
전송하면서 계속 신호 감지.
비정상 신호 감지 → 충돌 판단.
즉시 전송 중단(abort).
랜덤 backoff 후 재전송.

충돌 감지 방법: 정상 신호는 일정한 전압/파형. 충돌 시 신호 에너지가 비정상적으로 커지므로(이상 파형) 이를 충돌로 판단.

최소 프레임 크기: Tfr ≥ 2Tp

CSMA/CD가 동작하려면 프레임 전송 시간 Tfr이 최대 전파 지연 Tp의 최소 2배이상이어야 한다(2Tp = 왕복 지연).
이유: 프레임이 너무 짧으면 충돌 신호가 송신자에게 돌아오기 전에 전송이 끝나, 충돌을 감지하지 못한다.
→ 프레임은 최소한 충돌이 돌아올 때까지계속 전송 중이어야 한다.

CSMA/CA (Collision Avoidance)

무선 네트워크용. 무선에서는 충돌 감지(CD)가 어렵기 때문에 충돌을 회피한다.
동작: ① 채널 감지 → ② idle 발견 → ③ IFS만큼 대기 → ④ 랜덤 backoff(contention window) → ⑤ 카운트다운 → ⑥ 0 되면 전송 → ⑦ ACK 대기.

세 가지 충돌 회피 전략

IFS (Inter Frame Space): idle을 발견해도 바로 보내지 않고 잠시 대기.

IFS가 짧을수록 먼저 보내므로 우선순위가 높다→ IFS로 우선순위를 정의할 수 있다.

Contention Window: 랜덤 슬롯 중 하나를 선택해 backoff.

채널이 busy해지면 타이머를 다시 시작하지 않고 멈췄다가, idle이 되면 이어서카운트다운한다. (매번 다시 시작하면 starvation 발생.)

ACK: 충돌 감지가 어려우니, 성공 여부는 ACK 응답으로 확인.

CSMA/CA 플로우차트

채널 확인 → 2. idle 발견 → 3. IFS 대기 → 4. 여전히 idle이면 → 5. 랜덤 R 선택(0 ~ 2^K − 1) → 6. R만큼 카운트다운 → 7. 0 되면 전송 → 8. ACK 대기 → 9. 실패 시 K++ → 10. K > 15 면 Abort, 아니면 재시작.

아이디어: 각 노드의 랜덤 넘버가 서로 다를 확률이 높을수록 충돌이 줄어든다. → 랜덤 넘버 선정 시 기존 데이터를 기반으로 AI로 설정할 수도 있다.

Channelization

링크의 가용 대역폭을 시간 / 주파수 / 코드기준으로 나누어 여러 스테이션이 공유하는 다중 접근 방식. 충돌을 구조적으로 제거.

FDMA (Frequency Division Multiple Access)

하나의 큰 채널을 여러 주파수 대역으로 분할 → 각 노드는 자기 주파수만 사용.
주파수 간 간섭을 막기 위해 대역 사이에 Guard Band(보호 대역, gap)를 둔다.
FDMA는 데이터 링크 계층 개념, FDM은 물리 계층(1계층) 기술— FDMA는 물리 계층에서 FDM을 사용한다.
장점: 충돌 없음, 동시 전송 가능, 지연 거의 없음. / 단점: 대역폭 낭비(guard band), 미사용 시에도 자리 유지, 유연성 낮음.

TDMA (Time Division Multiple Access)

전체 대역폭은 하나의 채널. 이 채널을 시간 슬롯으로 나눠 각 노드가 자기 시간에만 전송.
타임슬롯을 잘게 잘라 번갈아 전송.

CDMA (Code Division Multiple Access)

FDMA와 달리 하나의 채널이 전체 대역폭을 사용하고, TDMA와 달리 시간 분할 없이모든 스테이션이 동시에전송.
아무것도 나누지 않고 **코드(code)**로 구분: 각 노드의 데이터를 서로 다른 코드로 변환 → 신호를 합쳐서 전송 → 수신자는 자기 코드로만 추출.
코드가 서로 **직교(orthogonal)**하므로 겹친 신호에서 분리 가능. → “같은 시간, 같은 주파수에서 코드로 구분하여 동시 전송”.

CDMA 코드(칩 시퀀스, chips)와 직교성

코드 = +1 / −1 로 이루어진 벡터(칩 시퀀스). 예(Walsh):
C1 = [+1 +1 +1 +1], C2 = [+1 −1 +1 −1], C3 = [+1 +1 −1 −1], C4 = [+1 −1 −1 +1]
직교 시퀀스의 성질:

동일한 두 시퀀스의 내적: A · A = N(스테이션 수, 예: C1 × C1 = 4).
서로 다른 두 시퀀스의 내적: A · B = 0(서로 간섭 안 함).
A · (−A) = −N.

공통 채널 = d1·c1 + d2·c2 + d3·c3 + d4·c4.
전체 신호에 내 코드를 곱하면내 데이터만 남고 남의 데이터는 0이 된다. 예: (Σ dᵢcᵢ) × c1 = 4 × d1.

데이터 표현 (인코딩)

비트 0 → −1, 비트 1 → +1, 무음(idle) → 0.
흐름: 비트 → (+1/−1/0) 변환 → 코드 곱함 → 전부 더함 → 채널로 전송.

예시 (4 노드, N=4)

노드1: bit 0 → −1, c1=[+1 +1 +1 +1] → d1·c1 = [−1 −1 −1 −1]
노드2: bit 0 → −1, c2=[+1 −1 +1 −1] → d2·c2 = [−1 +1 −1 +1]
노드3: idle → 0, c3=[+1 +1 −1 −1] → d3·c3 = [ 0 0 0 0]
노드4: bit 1 → +1, c4=[+1 −1 −1 +1] → d4·c4 = [+1 −1 −1 +1]
채널 합 벡터:

 [-1 -1 -1 -1]
+[-1 +1 -1 +1]
+[ 0  0  0  0]
+[+1 -1 -1 +1]
----------------
 [-1 -1 -3 +1]

수신: (채널 신호) × (내 코드) → 전부 더함 → N으로 나눔→ 비트 변환.

Walsh table (코드 생성)

Walsh 테이블의 행 하나 = 하나의 코드(chip sequence). 시퀀스 개수는 N = 2^m(m = 확장 횟수).

W(2N) = [ W(N)   W(N)
          W(N)  -W(N) ]

W1 = [ +1 ]
W2 = [ +1  +1
       +1  -1 ]
W4 = [ +1 +1 +1 +1
       +1 -1 +1 -1
       +1 +1 -1 -1
       +1 -1 -1 +1 ]