CS/컴퓨터 네트워크

[컴퓨터 네트워크] Link Layer and LANs -1

두루두루두 2025. 6. 3. 13:45

목차

  • Introduction
  • Error detection, Correction
  • Multiple access protocols
  • LANs
    • Addressing, ARP

Link layer: introduction

링크 계층 관련 용어들:

노드 (nodes): hosts, routers, switches, WiFi APs (access points)

링크 (links or media): 통신 경로 상의 인접한 노드를 직접 연결하는 통신 채널

링크 계층 패킷: 프레임 (frame)

 

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

프레임화 (framing), 링크 접속 (link access), 인접한 노드 간의 신뢰적인 전달, 흐름 제어 (flow control), 오류 검출 (error detection), 오류 정정 (error correction), 반이중 (half-duplex) 및 전이중 (full-duplex)

 

링크 계층이 구현되는 위치

링크 계층은 네트워크 인터페이스 카드/컨트롤러 (network interface card/cotroller, NIC)로 알려진 네트워크 어댑터에 구현

하드웨어, 소프트웨어, 펌웨어 (firmware)의 조합

Interfaces communication

송신 측:
- 데이터그램을 프레임으로 캡슐화
- 오류 검사 비트, 신뢰적인 데이터 전송, 흐름 제어 등을 링크 계층 서비스 추가		 수신 측:
- 오류 검출, 신뢰적인 데이터 전송, 흐름 제어 등을 수행
- 데이터그램을 추출하여 네트워크 계층으로 전달

오류 검출 (Error detection)

EDC: 오류 검출 및 정정 (error detection and correction) 비트

D: 데이터 ([예] 데이터그램 + 프레임의 헤더)

패리티 검사 (Parity checking)

단일 패리티 비트 (single bit parity)                                      2차원 패리티 (two-dimensional bit parity) 기법

인터넷 체크섬 (Internet checksum)

Goal: 전송된 세그먼트에서 오류 ([예] 뒤바뀐 비트) 검출

sender:

  • UDP 세그먼트의 내용 (UDP 헤더 필드 및 IP 주소 포함)을 16비트 단위로 분리해서 합산
  • 체크섬 (checksum): 세그먼트 내용의 합산 결과에서 1의 보수 (one’s complement)를 취한 값
  • 계산된 체크섬 값을 UDP 체크섬 필드에 입력

receiver

  • 수신된 세그먼트의 체크섬 값을 계산
  • 계산된 체크섬 값이 체크섬 필드 값과 동일한지 확인:
    • 동일하지 않다면 → 오류 탐지
    • 동일하면 → 일단 오류는 탐지되지 않지만, 그럼에도 오류가 존재할 수 있음

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

D: 데이터 비트

G: r + 1 비트를 가지는 비트 패턴 (생성자, generator)

최상위 (가장 왼쪽) 비트는 항상 1이며, 송신 노드와 수신 노드는 생성자를 알고 있음

Goal: <D, R>이 G로 정확히 나누어지도록, r비트 길이의 CRC 'R'을 선택

  • 수신자는 G를 알고 있으므로 을 G로 나눔 → 나머지가 0이 아니면, 오류 검출
  • r + 1 비트보다 적은 수의 모든 버스트 (burst) 오류를 검출할 수 있음
  • 실제로 널리 사용되고 있음 (Ethernet, 802.11 WiFi)
  • 𝐺crc32 = 1 0000 0100 1100 0001 0001 1101 1011 0111

다중 접속 링크 (Multiple access links)와 프로토콜

두 가지 유형의 링크

  • 점대점 링크 (point-to-point link)
  • 브로드캐스트 링크 (broadcast link, shared wire or medium)

다중 접속 문제 - 다수의 송수신 노드들이 공유하는 단일 브로드캐스트 채널 접속을 조정하는 문제

두 개 이상의 노드 동시에 전송: 서로에게 간섭 (interference)을 발생시킴

  • 충돌 (collision): 수신 노드가 두 개 이상의 신호를 동시에 수신하는 경우 발생
  • 충돌 프레임은 신호를 해석할 수 없으므로, 채널 시간 (즉, 대역폭)이 낭비됨

이상적인 다중 접속 프로토콜

조건: R bps 전송률을 갖는 다중 접속 브로드캐스트 채널

이상적인 동작:

  • ① 단 하나의 노드만 전송할 데이터가 있다면, 그 노드는 R bps 처리율을 획득
  • ② M개의 노드가 전송할 데이터가 있으면, 각 노드는 평균적으로 R/M bps의 처리율을 획득
  • ③ 완전히 분산되어 있음 • 전송을 조정하는 특수 노드 (마스터 노드) 없음 • 클럭 (clock), 슬롯 (slot)의 동기화가 필요 없음
  • ④ 단순해야 됨

MAC 프로토콜의 분류

채널 분할 (channel partitioning) 프로토콜

  • 채널을 더 작은 ‘조각’으로 분할 (time slots, frequency, code)
  • 노드는 자신에게 할당된 조각을 독점적으로 사용

랜덤 접속 (random access) 프로토콜

  • 채널이 분할되지 않음
  • 충돌 발생을 허용하고, 충돌 발생하면 랜덤 지연 시간 후 재전송

순번 (taking turns) 프로토콜

  • 노드는 순번대로 전송 기회를 획득하며, 보낼 데이터가 많은 노드는 자신의 순번에서 오랫동안 전송할 수 있음

채널 분할 프로토콜: TDMA

시분할 다중 접속 (time division multiple access, TDMA)

  • 라운드 (round)로 채널 접근
  • 각 노드는 각 라운드에서 고정 길이의 시간 슬롯 (time-slot)을 획득
  • 충돌이 발생하지 않고, 공정함
  • 사용하지 않는 슬롯은 유휴 (idle) 상태가 됨: 즉, 낭비됨

채널 분할 프로토콜: FDMA

주파수 분할 다중 접속 (frequency division multiple access, FDMA)

  • 채널 스펙트럼 (channel spectrum)을 주파수 대역 (frequency band)으로 분할
  • 각 노드에 고정 주파수 대역이 할당됨
  • TDMA와 장/단점이 비슷함

랜덤 접속 프로토콜

  • 노드에 전송할 패킷이 있다면
    • 채널의 최대 전송률인 R bps로 패킷을 전송
    • 노드 간의 사전 조정 동작이 없음
  • 두 개 이상의 노드가 동시에 전송: ‘충돌’ 발생 → 채널 시간 낭비
  • 랜덤 접속 프로토콜의 종류:
    • ALOHA, slotted ALOHA
    • CSMA, CSMA/CD, CSMA/CA

Slotted ALOHA (additive links online Hawaii area)

가정:
모든 프레임의 길이 (즉, 전송 시간)는 동일함: L bit

시간은 동일한 크기의 슬롯 (한 프레임의 전송 시간)으로 분할됨

노드는 슬롯의 시작점에서만 프레임을 전송하기 시작함

노드 간의 슬롯 시작 시간이 동기화 됨

한 슬롯에서 2개 이상의 프레임이 충돌하면, 모든 노드는 그 슬롯이 끝나기 전에 충돌 발생을 검출함		 동작:
노드가 새 프레임을 획득하면 다음 슬롯에서 전송

- 충돌이 없다면: 전송 성공! 노드는 다음 슬롯에서 새로운 프레임을 전송할 수 있음

- 충돌이 발생하면: 전송 실패! 노드는 성공할 때까지 다음 슬롯들에서 p의 확률로 해당 프레임을 재전송

장점:
▪ 단일 활성 노드 (전송할 패킷을 가진 노드)는 채널의 최대 속도로 프레임을 전송할 수 있음

▪ 고도화된 분산: 각 노드가 충돌을 감지하고, 언제 재전송할지 각자 결정

▪ 간단한 동작		 단점:
▪ 활성 노드가 많이 있으면, 충돌로 슬롯 시간이 낭비됨

▪ 확률적인 재전송으로 일부 슬롯이 유휴가 되어 낭비됨

▪ 노드 간의 슬롯 시작 시간 동기화가 필요

순수 알로하 (Pure ALOHA)

슬롯이 없는 알로하: 더 단순하고, 동기화되지 않음

동기화하지 않았으므로 충돌 확률이 증가

  • 𝑡0 에서 보낸 프레임이 [𝑡0 − 1, 𝑡0 + 1]에서 보낸 다른 프레임과 충돌

반송파 감지 다중 접속 (Carrir Sense Multiple Access, CSMA)


CSMA: 전송하기 전에 채널 상태를 확인

  • 만약 채널이 유휴 (idle)하면: 전체 프레임을 전송
  • 만약 채널이 신호가 감지 (busy)되면: 전송을 지연

CSMA/CD: CSMA with Collision Detection

  • 송신 노드는 프레임을 전송하면서 동시에 채널을 들음
  • 충돌이 검출되면, 충돌이 발생한 프레임 전송을 즉시 중단시켜 낭비되는 채널 시간을 감소
  • 반송파 감지 (carrier sensing): 유선에서는 쉽지만, 무선에서는 어려움

CSMA

 

 

CSMA를 활용해도 충돌은 여전히 발생할 수 있음

  • 전파 지연으로 두 노드가 서로의 방금 시작된 프레임 전송을 감지 못할 수 있음

충돌 (collision): 전체 패킷 전송 시간이 낭비됨

  • 충돌 확률은 거리 및 전파 지연에 영향을 받음
  • 채널 전파 지연이 CSMA의 성능을 결정하는데 중요한 역할

 

CSMA/CD는 충돌로 낭비되는 시간을 줄임

  • 충돌이 검출되면 즉시 전송을 중단함
  • 유선은 충돌 검출이 쉬움: 자신의 송신 신호의 세기와 채널에서 수신되는 신호의 세기를 비교
  • 무선은 충돌 검출이 매우 어려움: 자신의 송신 신호의 세기에 비해 수신 신호의 세기를 너무 약함
  • 충돌이 발생한 프레임 전송을 중단하고 jam 신호를 브로드캐스트하여 다른 노드들에게 충돌이 발생했다고 알림
  • 이더넷 (Ethernet)에서 CSMA/CD 방식 사용

Ethernet CSMA/CD 알고리즘

① NIC는 네트워크 계층에서 데이터그램을 전달받고 프레임을 생성함

② NIC는 현재 채널에서 반송파가 감지되는지 확인

  • 채널이 유휴 (idle) 상태이면: 프레임 전송 시작
  • 채널에서 반송파가 감지 (busy)되면: 채널이 유휴 할 때까지 대기후, 전송 시작

③ 프레임을 전송하는 동안 NIC는 채널에서 다른 신호의 에너지가 검출되는지 감시

④ 충돌없이 전체 프레임을 전송하면, 프레임 전송이 완료됨!

⑤ NIC가 전송 중 다른 전송을 감지하면 (즉, 충돌이 발생하면), 즉시 전송을 중단하고 jam 신호를 전송

⑥ 중단 후 NIC는 이진 지수적 백오프 (binary exponential backoff) 알고리즘을 활용하여 대기 시간을 임의로 결정하여 대기하고,      ②로 복귀

순번 (Taking turns) MAC 프로토콜

채널 분할 MAC 프로토콜:

  • 부하가 많은 네트워크에서 효율적, 공정하게 채널을 공유
  • 부하가 낮은 네트워크에서 비효율적, 채널 접속 지연 발생, 활성 노드가 1개만 있으면 1/N 대역폭만 활용 가능

랜덤 접속 MAC 프로토콜:

  • 부하가 낮은 네트워크에서 효율적, 단일 노드가 채널의 대역폭을 완전히 활용할 수 있음
  • 네트워크의 부하가 많아지면, 활성 노드가 많아지면서 충돌 오버헤드가 증가

순번 MAC 프로토콜:

  • 부하가 많든 적든 어느 정도 효율적으로 동작 가능
  • 제어 오버헤드 및 단일 장애점 발생: 특정 노드의 오류가 전체 시스템을 정지시킬 수 있음

순번 프로토콜

폴링 (Polling) 프로토콜

  • 마스터 노드는 각 클라이언트 노드에게 순서대로 (라운드 로빈 방식) 전송 기회를 제공
  • 전송 기회를 받은 클라이언트 노드는 전송할 패킷이 있다면 패킷 전송을 요청/시작
  • 블루투스는 폴링 방식으로 동작
  • 단점:
    • 폴링 지연 발생
    • 마스터 노드에서 장애가 발생하면 전체 채널 전송 동작이 멈춤  

토큰 전달 (token passing) 프로토콜

한 노드에서 다음 노드로 순차적으로 제어 토큰을 전달

  • 토큰을 가진 활성 노드는 패킷을 최대 개수까지 전송하고 다음 노드로 전달
  • 토큰을 수신한 노드가 전송할 패킷이 없다면 즉시 다음 노드로 전달

마스터 노드가 없는 분산 방식이며 효율성이 높음

단점: 토큰 오버헤드, 토큰 지연 및 단일 장애점 (토큰을 가진 노드)

 

다중 접속 프로토콜 요약

채널 분할: 시간, 주파수 또는 코드 별로 분할

  • 시간 분할, 주파수 대역 분할, 코드 분할

랜덤 접속 (동적인)

  • ALOHA, Slotted-ALOHA, CSMA, CSMA/CD
  • 이더넷은 CSMA/CD 사용
  • 와이파이 (Wi-Fi, IEEE 802.11)은 CSMA/CA 사용

순번

  • 중앙 컨트롤러 (마스터 노드)에서 폴링, 토큰 전달
  • Bluetooth, 토큰 링 (token ring), FDDI

MAC 주소

32-bit (or 128-bits) IP 주소

  • 인터페이스의 네트워크 계층 주소
  • 네트워크 계층에서 데이터그램을 전달하기 위해 사용
  • [예] 128.119.40.136

MAC (medium access control) 주소 또는 랜 (Local Area Network, LAN) 주소, 물리적 (physical) 주소, 이더넷 (Ethernet) 주소

  • 인터페이스에서 물리적으로 연결된 다른 인터페이스로 프레임을 전달하기 위해 ‘로컬’ (일반적으로 동일한 서브넷)에서 사용되는 주소
  • MAC 주소 (48비트)는 NIC의 ROM에 영구적으로 기록되며, 최신 NIC는 소프트웨어로 MAC 주소를 변경할 수 있음

 

 

근거리 네트워크 (LAN)에서 각 인터페이스 :

‘로컬’에서 유일한 32비트 IP 주소를 사용

유일한 48비트 MAC 주소를 사용

 

 

 

주소 결정 프로토콜 (Address Resolution Protocol, ARP)

Q. IP 주소는 알지만, MAC 주소는 모르면, 어떻게 MAC 주소를 알 수 있을까?

A. ARP를 통해 확인 IP 주소를 바탕으로 MAC 주소를 알 수 있음

  • LAN의 각 노드 (호스트, 라우터)에 ARP 테이블이 존재 (plug-and-play)
    • IP 주소와 MAC 주소 간의 매핑 정보를 포함

다른 서브넷으로 라우팅: 주소 지정

[예] 라우터 R을 통해 A에서 '다른 서브넷'에 있는 B로 데이터그램을 전송

  • A는 B의 IP 주소를 알고 있음
  • A는 첫 홉 (first-hop) 라우터인 R의 IP 주소를 알고 있음 (DHCP)
  • A는 라우터 R의 MAC 주소를 알고 있음 (ARP)

  • A에서 출발지 IP 주소를 A, 목적지 IP 주소를 B로 설정한 데이터그램을 생성
  • A는 해당 데이터그램을 캡슐화해서 프레임을 생성
    • R의 MAC주소는 프레임의 목적지 MAC 주소로 설정

  • 프레임은 A에서 R로 전송
  • R에서 프레임 수신하면, 데이터그램을 추출하여 네트워크 계층으로 전달
  • R은 출력 인터페이스를 결정하고, 출발지 IP 주소를 A, 목적지 IP 주소를 B로 설정한 데이터그램을 링크 계층으로 전달
  • R은 해당 데이터그램을 캡슐화해서 프레임을 생성
    • 출발지 MAC 주소: R의 MAC 주소
    • 목적지 MAC 주소: B의 MAC 주소
  • B는 프레임을 수신하고, 데이터그램을 추출하여 네트워크 계층을 전달