[네트워크] 링크 계층(CRC)과 다중 접속 프로토콜

1. 링크 계층의 개요 및 역할 (Introduction & Context)

1) 기본 용어 정리 (Terminology)

• 노드 (Nodes): 네트워크에 연결되어 전송을 수행하는 호스트(PC, 노트북, 스마트폰 등)와 라우터(Routers).
• 링크 (Links): 데이터 이동 경로 상에서 서로 인접한 노드들을 물리적으로 연결하는 통신 채널.
  • 유선 링크 (Wired): 광케이블, 구리 동축 케이블 등.
  • 무선 링크 (Wireless): Wi-Fi, LTE/5G 대역 등.
  • LAN (Local Area Network): 로컬 단위로 묶인 통신망.
• 프레임 (Frame): 링크 계층의 데이터 전송 단위. 3계층의 데이터그램(Datagram)을 캡슐화하여 전송용 헤더와 트레일러를 붙인 형태.

2) 네트워크 계층 vs 링크 계층 (교통수단 비유)

교통 시스템 비유	네트워크 개념	설명
관광객 (Tourist)	데이터그램 (Datagram)	이동하는 궁극적인 목적을 가진 알맹이 데이터
개별 이동 구간 (Transport segment)	통신 링크 (Communication link)	목적지까지 가기 위해 거쳐야 하는 각 도로/경로 구간
이동 수단 (Transportation mode)	링크 계층 프로토콜 (Link-layer protocol)	WiFi, 이더넷 등 각 구간 특성에 맞는 개별 전송 규약
여행사/가이드 (Travel agent)	라우팅 알고리즘 (Routing algorithm)	전체 여정(출발지부터 목적지까지)의 최적 경로를 설정

• 핵심 메시지: 3계층(네트워크)이 출발지부터 목적지까지의 전체 경로(End-to-End)를 책임진다면, 2계층(링크)은 물리적으로 바로 맞닿아 있는 인접 노드(Hop-by-Hop)로 데이터를 안전하게 건네주는 구체적인 수송 책임을 집니다.

2. 링크 계층의 주요 서비스 및 구현

1) 제공 서비스 (Link Layer Services)

1. 프레이밍 및 링크 접근 (Framing, Link Access): 데이터그램에 헤더와 트레일러를 추가하여 프레임을 구성합니다.
   • 프레임 헤더에는 장치 고유의 물리 주소인 MAC 주소(MAC Address)가 들어갑니다. (IP 주소와 무관한 하드웨어 고유 식별자)
2. 인접 노드 간 신뢰성 전송 (Reliable Delivery):
   • 송수신 노드 간에 손실이나 오류 없이 데이터를 전달하는 기능입니다.
   • 유선 링크: 에러율이 극도로 낮으므로 불필요한 오버헤드를 막기 위해 링크 계층 수준의 신뢰성 전송을 거의 사용하지 않음 (Seldom used).
   • 무선 링크: 간섭과 신호 감쇄로 에러 발생률이 매우 높으므로, 상위 계층(TCP)까지 깨진 패킷을 보내 태평양을 왕복하는 재전송 딜레이를 유발하지 않고 링크 레벨에서 즉시 에러를 감지해 재전송(Local Recovery)함으로써 효율성을 끌어올림.
3. 흐름 제어 (Flow Control): 인접한 송신 노드가 수신 노드의 처리 속도(버퍼 크기)보다 빠르게 데이터를 들이붓지 못하도록 속도를 조절하는 페이싱(Pacing) 기능.
4. 에러 검출 및 정정 (Error Detection & Correction): 신호 감쇄나 잡음으로 발생한 비트 에러를 처리하는 기술.
5. 이중화 방식 제어 (Half-duplex / Full-duplex): * 반이중(Half-duplex): 양방향 송수신이 가능하지만 동시에 통신할 수는 없는 방식 (예: 무전기, 옛날 와이파이).
   • 전이중(Full-duplex): 충돌 없이 양방향에서 동시에 송수신이 가능한 방식 (예: 스위치 기반 이더넷).

2) 링크 계층의 구현 위치 (Implementation)

• 구현 하드웨어: 링크 계층은 소프트웨어 중심의 상위 계층과 달리 주로 네트워크 인터페이스 카드(NIC, 랜카드) 또는 메인보드 내 통신 칩셋에 구현됩니다.
• 하이브리드 결합체: 비트를 하드웨어 신호로 쏘는 물리적 기능은 하드웨어(Hardware)가 담당.
  • 링크 접근 알고리즘과 제어 로직은 NIC의 펌웨어(Firmware)가 처리.
  • 운영체제(OS)의 커널에 탑재된 네트워크 카드 드라이버 소프트웨어가 상위 IP 계층과의 다리 역할을 수행.

3. 에러 검출 및 정정 기술 (Error Detection & Correction)

1) 기본 논리

• 송신 측은 원본 데이터 D에 특정 알고리즘을 수행하여 구한 오류 검출용 잉여 비트 EDC (Error Detection & Correction)를 덧붙여 전송합니다.
• 수신 측은 받은 데이터 D'를 기반으로 동일 알고리즘을 돌려 계산한 값과 받은 EDC'를 교차 비교합니다.
• 주의점: 에러 검출 기술은 100% 완벽할 수 없습니다. 극히 희박한 확률로 데이터는 깨졌는데 수신 알고리즘 계산 결과는 정상인 오류 필터링 실패(Missed error)가 생길 수 있습니다. (EDC 필드가 클수록 정밀도가 향상되나, 전송 오버헤드가 증가하는 트레이드오프 발생)

2) 패리티 검사 (Parity Checking)

가장 단순한 검출 기법으로, 비트 스트림 뒤에 1비트의 체크용 공간을 추가하는 방식입니다.

① 단일 비트 패리티 (Single Bit Parity)

• 짝수 패리티 (Even Parity) 기준: 데이터 비트들과 패리티 비트 내부의 1의 총 개수가 짝수가 되도록 패리티를 0 또는 1로 결정합니다.
• 예시: 데이터가 0111000110101011 일 때, 원래 1이 9개(홀수)이므로 패리티 비트를 1로 두어 짝수 개를 맞춰 보냅니다.
• 한계: 오직 1비트 에러만 감지할 수 있습니다. 만약 전송 중 절묘하게 2개의 비트가 동시에 깨지면 전체 1의 개수 짝수 성질이 깨지지 않아 에러 감지에 완전히 실패합니다.

② 2차원 비트 패리티 (Two-dimensional Bit Parity)

• 데이터를 가로 i행, 세로 j열의 매트릭스 형태로 정렬하고 가로행 끝(row parity)과 세로열 끝(column parity)에 각각 패리티 비트를 부여합니다.
• 강력한 장점: 1비트 에러에 대한 자동 정정(Correction) 가능!
  • 특정 비트가 하나 깨지면, 그 비트가 소속된 행의 패리티와 열의 패리티에 동시에 에러가 찍힙니다.
  • 가로 에러선과 세로 에러선이 만나는 교차점(Intersection)의 비트를 즉시 찾아내어 반대 값($0 \to 1$ 또는 $1 \to 0$)으로 뒤집어서 재전송 요청 없이 그 자리에서 자가 치료합니다.

3) 인터넷 체크섬 (Internet Checksum) - 비교 학습용

• 사용 레이어: 주로 3, 4계층(IP, TCP/UDP) 소프트웨어 단에서 계산합니다.
• 계산 방식: 데이터를 16비트 단위의 정수로 정렬하여 모두 더한 뒤, 캐리(자리올림)를 처리하고 1의 보수를 취해 체크섬 값을 만듭니다.
• 특징: 소프트웨어 구현이 빠르고 가벼워 CPU 부담을 덜지만, 에러 정정은 불가능하고 감지만 할 수 있습니다.

4) 순환 중복 검사 (CRC, Cyclic Redundancy Check)

현대 유선 이더넷과 802.11 Wi-Fi 표준에서 사용하는 극도로 강력한 다항식 기반 에러 감지 방식입니다.

① 수학적 원리 및 수식

• 주어진 값: 원본 데이터 D (이진수), 미리 약속한 생성 다항식 패턴 G (r+1 비트 크기).
• 목표: 데이터 D의 뒤에 r비트 크기의 나머지 값 R을 붙인 전체 프레임 < D,R >이 G로 나누어떨어지게 만드는 것 (Modulo-2 연산 기반).

< D,R > = D * 2^r  XOR  R

② Modulo-2 산술 규칙 (핵심)

• Modulo-2 연산은 덧셈과 뺄셈을 내림(Borrow)이나 올림(Carry) 없이 오직 XOR(배타적 논리합)로만 연산합니다.
• 즉, 두 비트가 같으면 0, 다르면 1이 됩니다. (예: 1 XOR 1 = 0, 1 XOR 0 = 1, 0 XOR 0 = 0)

③ 연산 예시 및 가이드 (D = 101110, G = 1001, r = 3)

1. G가 4비트(r+1)이므로, r=3입니다.
2. 데이터 D 뒤에 r=3개만큼 0을 붙여 자릿수를 늘립니다: D * 2^r = 101110000
3. 이 값을 G=1001로 Modulo-2 나누기 연산을 수행합니다.

            1 0 1 0 1 1  <-- 몫 (중요하지 않음)
       ----------------
1 0 0 1 | 1 0 1 1 1 0 0 0 0
          1 0 0 1
          -------
          0 0 1 0 1  <-- 1-1=0, 0-0=0, 1-0=1, 1-1=0 (XOR 연산 수행)
            0 0 0 0  <-- 앞자리가 0이므로 0000으로 연산
            -------
              1 0 1 0
              1 0 0 1
              -------
              0 0 1 1 0
                0 0 0 0
                -------
                1 1 0 0
                1 0 0 1
                -------
                0 1 0 1 0
                  1 0 0 1
                  -------
                  0 0 1 1  <-- 최종 나머지 3자리 (R = 011)

• 결과 나머지 (R): 011
• 최종 송신 데이터 (< D,R >): 원래 데이터 뒤에 R을 붙인 101110011
• 감지 방식: 수신 측은 101110011을 그대로 받아 G=1001로 나누었을 때 나머지가 정확히 000이 나오면 정상 수신으로 인정하고, 이외의 값이 나오면 오류 감지(Error Detected)로 취급해 드롭합니다. (에러 위치 특정 및 정정은 불가능)

4. 다중 접속 프로토콜 (Multiple Access Protocols)

하나의 브로드캐스트 전송 매체(Shared line, Wireless air 등)를 여러 노드가 공유할 때, 신호가 겹쳐서 데이터가 폭파되는 충돌(Collision)을 통제하기 위해 설계된 분산 약속 시스템입니다.

1) 이상적인 다중 접근 프로토콜의 4가지 요구조건 (Desiderata)

총 대역폭 속도가 R bps인 채널 환경에서 바라는 이상향:

1. Full Rate 보장: 통신하는 노드가 단 1개뿐일 때는 그 노드가 최대 전송 속도 R을 통째로 누릴 수 있어야 함.
2. Fair Share 공평성: 통신하는 노드가 M개로 늘어나면, 각 노드는 평균적으로 공평하게 R/M의 안정적인 속도를 가질 수 있어야 함.
3. 완전한 분산 제어 (Fully Decentralized): 전체 조율을 지휘하는 값비싼 중앙 통제 서버가 없어야 하며, 모든 노드 간의 클록(시간대) 동기화 요구가 없어야 함.
4. 단순함 (Simple): 구조와 하드웨어 연산 비용이 단순해야 함.

2) MAC 프로토콜 3대 카테고리 (Taxonomy)

5. 핵심 프로토콜 상세 동작 메커니즘

1) 채널 분할 방식: TDMA (Time Division Multiple Access)

• 동작: 시간을 주기적인 '라운드'로 쪼개고, 각 라운드 내에 노드별로 전용 고정 시간 슬롯(Fixed-length slot)을 지정합니다.
• 장단점: * 장점: 자기 지정 시간대에는 혼자만 말하므로 충돌이 절대 안 남. * 단점: 나 혼자 전송 중이어도 내 할당 슬롯 외에는 쓰지 못하고 노는 슬롯들(Idle slots)을 보며 낭비해야 하므로 최대 속도(R$) 활용에 실패함.

2) 랜덤 접속 방식: CSMA (Carrier Sense Multiple Access)

• 개념: "말하기 전에 조용히 귀 기울여 들어보고(Carrier Sensing) 들어가자."
  • Idle 상태 감지 시: 전체 프레임 즉시 전송 시작.
  • Busy 상태 감지 시: 끼어들지 않고 전송을 연기(Defer)한 후 대기.

💡 귀를 기울이는데도 충돌이 발생하는 이유: 전파 지연 (Propagation Delay)

• 신호가 전선이나 무선 공간을 지나 반대쪽 끝 노드까지 전달되는 데는 미세한 전파 물리적 지연 시차(t_prop)가 걸립니다.
• 왼쪽 끝 노드가 t_0에 전송을 시작했으나 이 신호가 오른쪽 끝 노드에 닿기 직전 시점인 t_1에 오른쪽 끝 노드가 채널을 들어보면 조용한 것으로 인식(Idle 착각)합니다.
• 결국 오른쪽 노드도 데이터를 동시에 쏘아 보내며 선로 중간에서 신호가 겹치는 충돌이 발생합니다.
• 일반 CSMA의 비효율: 충돌을 감지하지 못해 데이터가 이미 도중에 다 뭉개졌음에도 불구하고 패킷이 끝날 때까지 꿋꿋이 붙잡고 전송을 진행하므로 심각한 채널 대역폭 낭비가 발생합니다.

3) 랜덤 접속 방식: CSMA/CD (Collision Detection)

• 원리: 데이터를 송신하면서 동시에 귀를 계속 열어두어 전송 중 충돌 발생 여부를 상시 감시하는 유선 이더넷의 표준 방식.
• 작동 규칙:
  1. 데이터를 보내다가 전압 등의 변화로 충돌을 감지하면 즉시 전송을 중단(Abort)하여 채널 낭비를 차단합니다.
  2. 수신 노드 및 전체 네트워크 노드들에게 충돌이 났음을 확산 전파하기 위한 경고용 잼 신호(Jam Signal)를 보냅니다.
  3. 재전송 타이밍이 겹치지 않도록 이진 지수 백오프(Binary Exponential Backoff) 알고리즘 영역으로 들어갑니다.

💡 이진 지수 백오프 (Binary Exponential Backoff)

• m번째 연쇄 충돌 발생 시, 노드는 다음 범위의 정수 집합에서 무작위로 K를 하나 뽑습니다.
• 대기 시간은 K * 512 비트 시간만큼 기다립니다.
• Q. 왜 최댓값(2^m-1)을 안 쓰고 0부터 전체 범위 중 무작위(Random)로 뽑나요?
  • A: 연쇄 충돌이 났을 때 두 노드가 똑같이 최댓값을 고르면, 대기가 끝나는 시점이 마이크로초 단위까지 완벽하게 동일해져서 재전송하는 순간 100% 또 부딪치기 때문입니다. 무작위 K 선택을 통해 서로 대기하는 시간 차이를 벌려놓아(타이밍 엇갈림) 먼저 대기를 끝낸 녀석이 채널을 점유하고 나가도록 유도하는 것이 이 알고리즘의 본질입니다.
  • 충돌 횟수(m)가 거듭될수록 뽑기 집합의 크기를 지수적(2^m)으로 확장하여 동시 다발적 접속 시 번호가 겹칠 충돌 확률을 무력화시킵니다.

💡 CSMA/CD 효율성 공식 (Efficiency)

• 효율성이 1(100%)로 수렴하는 극한 환경:
  • t_prop = 0 일 때: 노드 간 거리가 매우 가까워 전파 시차가 없으므로 눈치싸움 실패로 인한 충돌 자체가 원천 제거되어 성능 극대화.
  • t_trans = infty 일 때: 전송 데이터(프레임 크기)가 매우 길면 초기 극초반의 위험 구간만 충돌 없이 넘기면 채널을 독점하여 계속 밀어 넣을 수 있어 효율성 극대화.

4) 랜덤 접속 방식: CSMA/CA (Collision Avoidance)

• 사용 환경: 무선 와이파이(Wi-Fi, 802.11) 대역. 무선 특성상 자기 송신 출력이 수신 신호를 압도하므로 물리적으로 충돌 감지(CD)를 사용할 수 없어 탄생한 충돌 회피(Avoidance)형 규약.
• 주요 타임라인 변수:
  • DIFS (Distributed Inter-Frame Space): 데이터를 전송하기 전, 채널이 완전히 비어 있는지 눈치를 보며 강제 대기해야 하는 긴 안심 기준 시간.
  • SIFS (Short Inter-Frame Space): 데이터 수신 직후 수신 확인 신호인 ACK를 쏘기 전 잠깐 숨을 고르는 가장 짧은 간격 시간. (SIFS가 DIFS보다 압도적으로 짧기 때문에 다른 컴퓨터가 끼어들 틈을 주지 않고 수신 측이 즉시 안전하게 ACK 신호를 날릴 수 있도록 권한을 보장함.)
  • ACK (Acknowledgement): 무선은 충돌 감지가 불가능하므로, 수신 측이 정상 수신 시 무조건 ACK를 송신 측에 답장해 줌으로써 배달 신뢰성을 보장함. ACK를 못 받으면 무조건 에러(충돌)로 치부하고 처음부터 백오프 대기 후 다시 전송.

5) 차례 돌리기 방식 (Taking Turns)

• 등장 배경: * 채널 분할은 저부하(Low load) 시 노는 자원이 많아 성능 낭비가 심함.
  • 랜덤 접속은 고부하(High load) 시 충돌로 인한 성능 붕괴가 심함.
  • 목표: "사람이 적을 땐 혼자 다 쓰고, 사람 많을 땐 순서를 강제하자!"

① 폴링 (Polling)

• 원리: 하나의 마스터(Master) 노드가 슬레이브(Slaves)들에게 순서대로 "너 보낼 거 있어?" 라고 물어보는 poll 신호를 던지며 제어.
• 한계: * 수시로 물어보고 대답하는 과정에서 대역폭을 소모하는 폴링 오버헤드(Polling overhead) 발생.
  • 차례가 올 때까지의 무조건적인 대기 딜레이(Latency) 발생.
  • 마스터가 고장 나면 전체 통신이 단번에 마비되는 단일 장애점(SPOF, Single Point of Failure) 리스크 존재.

② 토큰 패싱 (Token Passing)

• 원리: 중앙 제어 노드 없이, 권한 상징 프레임인 토큰(Token)을 링 형태로 구성된 노드들끼리 순서대로 이웃에 순차 전달.
• 동작: 토큰을 획득한 노드만 데이터 전송 권한을 얻으며, 다 보내면 토큰을 이웃에게 릴레이 토스. 보낼 게 없는 노드는 토큰을 받는 즉시 지체 없이 다음 노드로 릴레이.
• 한계:
  • 아무도 보낼 데이터가 없어도 토큰이 계속 돌아야 하는 토큰 오버헤드 존재.
  • 중간 통신 잡음으로 토큰 자체가 깨지거나(토큰 분실), 특정 장비가 토큰을 먹은 채 먹통이 되면 복잡한 복구 알고리즘이 개입해야 함.