Link Layer: introdution
- Link : 통신경로를 따라 인접 node를 연결 시키는 채널(유/무선, LANs)
- data(layer-2 packet) : Frame, datagram을 캡슐화(frame을 링크를 통해 인접한 노드로 전송되는데 사용)
- datagram은 다른 link protocol로 다른 Link로 전송될 수도 있음(예를 들어 Wifi -> Ethernet)
- 각각의 link protocol은 다른 서비스를 제공
Services
- framing, link access
- framing: datagram에 헤더와 트레일러를 붙여서 캡슐화 하여 프레임화 시키는 것
- MAC address : IP와 다르게 물리적 주소를 활용하여 목적지와 출발지를 구분
-
error detection
신호 간섭이나 잡음으로 인해 에러 발생 가능,
수신측은 이 에러를 감지해서 재 수신하거나 drop frame -
error correction
수신측이 bit 에러를 재송신 없이 고치고 확인하는 것 -
half-duplex and full-duplex
Error detection, correction
Error Detection
Redundancy, bit error 등을 감지, 헤더필드를 활용하여 에러를 감지함
Parity checking
데이터 비트와 parity 비트에 속한 1이 짝수인가 홀수 인가로 판단
even,odd 두가지 방법 존재
- odd parity check : 01111100 같은 경우 앞에 7자리 비트는 데이터 비트, 마지막 0은 패리티 비트,
1의 개수가 6개로 짝수이므로 error 발생 감지 가능
Cyclic Redundancy Check(CRC)
데이터 비트와 제너레이터(비트 패턴)을 활용
110100 = (X^5) (X^4) (X^2) 와 같은 형식으로 표현
- CRC error detection rule
송신측은 항상 연산된 P(X)를 수신측으로 보냄
수신측, P(X) + E(X)를 받음
E(X) -> 데이터가 전송되면서 만들어진 에러를 다항식으로 표현한 것(E(X) = 0 은 에러 없음)
=> (P(X) + E(X)) % G(X) = 0 이면 에러가 발생하지 않은 것,
(P(X) + E(X)) % G(X) > 0 이면 에러가 발생한 것
Multiple Access Protocols
두가지 타입의 link가 존재
- point-to-point: 이더넷, 스위치, 호스트 사이의 링크
- broadcast : traditional Ethernet, upstream HFC, Wireless LAN
ex. MAC(Medium Access Control) 프로토콜
메체 공유시 전송을 공평하고 효율적으로 중재
- Collision: 한곳에 서로 다른 데이터 두개가 동시에 오게 되는 것 => 이것을 최소화 시키는 것이 필요
Ideal multiple Access Protocol
BroadCast channel of rate R bps 라고 치면,
하나의 노드만 해당 채널 사용시 R bps를 다 사용함,
N개의 노드가 나누어서 사용시 R/N bps 로 사용
=> 항상 분산된 제어 알고리즘을 사용해야함(하나의 노드가 전체 전송을 제어하게 되면 Collision 위험 증가)
MAC Protocols : a Texonomy
-
Channel Partitioning => 채널을 작게 나누어서 사용(시간, 주파수, 코드 등등), 그 채널 조각은 한 노드 전용으로 사용 ex. FDMA(Frequency), TDMA(Time), CDMA(Code)
-
Random Access => 채널 분류 없이, collision 허용하고, 이를 회복하는 방향
-
Controlled-access protocols => 문명 겜 처럼 턴제, 한 턴을 길게 가져가서 더 많은 양을 보낼 수도 잇음
Channel Partitioining
- TDMA: 각각의 노드들은 매 라운드 마다 고정된 길이 slot(=time length, pkt trans time)를 할당
-> 사용하지 않은 slot은 낭비(1,3,4 station 이외 슬롯을 낭비함)
- FDMA : 각각의 노드들은 주파수를 나누어 갖고, 보내고 싶을때 보낼 수 있음
(이것도 사용하지 않은 주파수는 낭비)
-> 이를 해결해보자!
다중화 방식(Multiple Access)
OFDM 처럼 주파수 채널 사이 간격을 줄여서 주파수 효율을 향상
- CDMA : Code Division Mulitiple ACCESS
Random Access Protocols
노드가 자신이 보낼 Pkt를 갖고 있는 경우 사용가능한 모든 R bps를 사용하여 보냄
사전 조율 X -> 두개 이상의 노드에서 보내면 collision.
이를 회복하는 방식이 중요
- Slotted ALOHA
모든 프레임은 같은사이즈, 슬롯 역시 같은 사이즈(단위시간당 1frame)
노드들 간에 서로 동기화 필수
프레임을 slot 시작할때만 송신 가능 -> 두개 이상의 프레임이 한 slot에 들어오면 collision 감지
사진처럼 하나의 노드에서 한 프레임만 보내야 성공 나머지는 비거나 Collision
-
Pure ALOHA
슬롯으로 분류도 안되어있고, 동기화도 안되어있음
송신측이 Collision 감지, 발생시 랜덤하게 기다리다가 재전송 => 가챠 시스템(확률이 구데기)
-
CSMA(Carrier sense multiple access)
carrier sense를 통해서 collision 감소 시키는 방식
- Carrier sense :채널이 현재 idle 상태인지(쉬는 상태), busy 상태인지 확인
다른 곳에서 데이터 보내면 보내지 않음
Taking Turns
채널 분리는 빠르지만 낭비가 많고, 랜덤 엑세스는 낭비는 적지만 성능이 구데기,
턴제는 이 두가지 방식의 장점만 취하려는 시도에서 탄생
- Token Passing: 순서대로 토큰을 다음 노드로 넘기면서, 토큰을 잡은 노드가 데이터를 보낼 수 있도록 하는 방식
토큰을 전달하는데 overhead 발생가능성이 있고, 잃어버리거나 경로가 끊기면 다음 노드는 토큰을 못받는 경우가 있음
-> 일정시간 동안 토큰이 안오면 토큰을 만들어서 보냄
- polling: 중앙제어 컨트롤러가 보낼 노드를 초청하는 방식
블루투스가 이 방식을 활용!
