Link Layer

미노·2025년 6월 12일

Computer Network

목록 보기
17/23

Link layer : introduction

  • node : host and routers
  • link : 노드들을 연결하는 통신채널
    • Wire : 대부분
    • Wireless
    • LANs (Local Area Network)
  • frame : link layer의 pkt 단위
  • Link layer는 인접한 노드에 link를 따라 물리적인 frame 전송을 책임진다.

Link layer : services

  • framing, link access
    • framing : datagram (Network layer)에 header + trailer를 붙여 frame으로 만드는 과정
    • channel access : 통신라인에 어떻게 접근할 것인가를 정의
    • MAC address : (Medium Access Control) : IP address와는 다른 source, destination 식별주소
  • error detection, correction : receiver는 bit error를 탐지해 재전송없이 정정
  • half-duplex, full-duplex

  • NIC(Network Interface Card), chip에서 link layer가 구현됨
    • Ethernet, WiFi card or chip

Interfaces communicating

  • Sending side :
    • Encapsulates datagram in frame
    • add error checking bits, reliable data, transfer, flow control, etc
      • Frame뒤 extra bits를 더함
  • receiving side :
    • Frame뒤 extra bits를 통해 error detection
    • header를 제거한 후 datagram을 윗계층으로 올림

Error detection

  • EDC (Error Detection and Correction bits) : D를 인자로 받아서 EDC를 생성 후 frame뒤에 붙임
  • EDC가 길어질수록 탐지 및 정정이 더 용이함
  • Error detection은 100% 신뢰할 수 없음

Parity checking

  • data bits에서 1의 개수를 짝수로 맞춤

  • single bit parity

    • 가장 간단하고 구현하기 쉬움
    • 어떤 비트에서 에러가 발생한건지 알 수 없음

  • two-dimensional bit parity

    • single bit error를 detection, correction할 수 있음
    • 어떤 비트에서 에러가 발생한지 알 수 있음

CRC (Cyclic Redundancy Check)

  • 앞의 방식보다 훨씬 더 powerful한 error detection coding(EDC를 만드는 작업)
  • D를 Pattern G로 나눈 나머지인 R을 EDC로 사용

CRC (Cyclic Redundancy Check): example

  • XOR연산을 통해 나머지 R을 구함
  • D의 크기가 가변적이어도 C, EDC의 크기는 정해져있음.

Multiple access protocol

  • collision : 하나의 통신채널에 둘 이상의 호스트들이 동시에 사용하려고 할 때 발생하는 충돌
  • collision을 방지하기 위해 TDMA, FDMA, etc

Channel partitioning MAC protocols: TDMA

  • TDMA : Time Division Multiple Access
  • 한 채널의 시간을 나누어서 슬롯마다 호스트들이 사용할 수 있음

Channel partitioning MAC protocols : FDMA

  • FDMA : Frequency Division Multiple Access
  • 채널의 주파수를 나누어 각 주파수별로 사용

Random access protocols

  • 언제 노드가 데이터를 보낼지 모름
  • 둘이상의 노드가 데이터를 보낼 때 collision 발생
  • random access MAC protocol은 정의
    • How to detect collisions
    • how to recover from collisions
  • ALOHA, slotted ALOHA, CSMA, CSMA/CD, CSMA/CA

slotted ALOHA

  • 가정상황
    • 모든 frame의 크기는 동일
    • TDMA 방식 사용
    • 똑같은 크기의 slot, 하나의 slot에 하나의 frame
    • 둘 이상의 노드가 같은 slot에 frame을 보내면 collision
    • 모든 노드는 collision detection
    • frame을 보낼지말지는 확률에 맡김
  • 간단하고 구현이 쉬움
  • 낭비하는 slot이 생김, sync가 맞아야함, collision 발생 증가

slotted ALOHA : efficiency

  • 하나의 노드의 성공확률 : p(1−p)N−1p(1-p)^{N-1}
  • 전체 노드들의 성공확률 : Np(1−p)N−1Np(1-p)^{N-1}
  • max efficiency :  1e=.37\ {1\over e} = .37

⇒ 최대 37%의 efficiency

CSMA (Carrier Sense Multiple Access)

  • carrier : Data를 운반하는 signal
  • simple CSMA : Listen and Talk
    • idle : frame 전송 가능
    • busy : channel 사용 중
  • 위의 그림에서 t0에 idle이니 h1이 carrier를 보냄, prop delay때문에 퍼져나감 → t1에 h4가 carrier를 보냄 → collision 발생
  • CSMA/CD (Collision Detection) : collision 발생 시 전송을 중단, 이미 data가 깨진 상태
  • CSMA/CA (Collision Avoidance): collision 발생할 거 같으면 전송을 중단, data 보호 가능

Summary of MAC Protocol

  • Link에 N개의 장치들이 pkt을 보낼 때 충돌이 발생, 이 충돌을 어떻게 해결할 것인지를 정의
    • Channel partitioning : TDMA, FDMA
    • Random access : slotted ALOHA, CSMA, CSMA/CD, CSMA/CA, etc
  • MAC(Medium Access Control) address :
    • 유동적으로 값이 바뀌는 IP address와 달리 값이 바뀌지 않음
    • unique 48bits / 6Bytes
    • 16진수로 표현 / 1A-2F-BB-76-09-AD

Ethernet

  • 가장 보편적으로 쓰이는 인터넷 프로토콜
  • simpler, cheap → 인프라 조성
    • single chip : chip 하나로 Ethernet protocol 지원

Ethernet : physical topology

  • bus :

    • node를 쉽게 붙였다 뗄 수 있음

    • 모든 node가 bus의 내용을 확인할 수 있음

  • switched :

    • switch와 port가 연결되어 있음

    • 서로의 port의 내용을 확인할 수 없음

    • port의 수가 제한적임

Ethernet frame structure

  • preamble : frame의 시작부분을 나타냄, synchronize를 위해 사용
  • dest, source address : MAC address가 들어감 / 48bits
  • data : Network layer로 부터 내려온 Datagram이 들어감
  • CRC : Error detection, correction을 위한 추가 비트

Ethernet : unreliable, connectionless

  • connectionless : no handshaking
  • unreliable : ACK, NAK를 보내지 않음
  • MAC Protocol : unslotted CSMA/CD

802.3 Ethernet standards : link & physical layers

Ethernet switch

  • Link layer’s device

Switch : Multiple simultaneous transmission

  • switch는 MAC address를 확인 후 frame을 fowarding
  • switching : A-A’, B-B’으로 frame을 collision 없이 forwarding
  • switching table을 통해 forward

Switch forwarding table

  • routing table처럼 어떤 port로 frame forwarding을 해야하는지 정해져있는 table
  • 우리는 장치를 바꿔도 따로 switch 설정을 하지 않음. 이는 switch가 독자적으로 table을 수정하고 있어서임

Switch : self-learning

  • MAC address를 지속적으로 업데이트
  • 위의 그림처럼 A-A’으로 frame forwarding을 했다면, A의 MAC addr, interface, TTL을 table에 저장
  • flood : dest를 모른다면 모든 host들에게 다 뿌림, 이때 모든 host의 정보를 table에 저장

Small institutional network

  • 외부 network에서 router를 통해 전송 → switch를 통해 각각의 다른 switch로 전송 → 각각의 host로 전송

Switches VS Routers

  • Store and forward
    • routers : Network layer devices
    • switches : Link layer devices
  • have forwarding tables
    • routers : routing algorithm을 사용한 table, IP address
    • switches : self-learning, flood를 사용한 table, MAC address
  • L2 switch : general switches
  • L3 switch : 기능을 추가하여 router로도 사용, 자동차에서 사용
profile
미노
이전 포스트

Network Layer

다음 포스트

What is mobility?

0개의 댓글