[컴퓨터 네트워크] 6장. Link Layer and Local Area Networks

해당 게시물은 김정근 교수님의 '컴퓨터 네트워크' 강의를 수강하며
학습한 내용을 개인적으로 정리한 글입니다.

---

📌 목차 - 6장. Link Layer and Local Area Networks

6-1. Introduction
6-2. Error detection, correction
6-3. Multiple access protocols
6-4. LANs

---

📌 6-1. Introduction

* Link layer: Introduction
- Hosts and Routers: nodes
- 통신 경로를 따라서 인접한 두 노드 사이에 존재하는 물리적인 통신 채널: links
- wired, wireless, LANs
- layer-2 packet: frame
- 링크 계층의 역할: 한 노드에서 물리적으로 연결된 다른 노드로의 frame 전송을 담당한다. (node to node data delivery)

* link layer: context
- 각각의 링크는 서로 다른 서비스를 담당하고 있다.

* linkt layer: services
- framing, link access: frame을 만들고 경쟁을 통해서 채널 access를 한다. 2계층의 주요 주소 "MAC"주소
- reliable delivery between adjacent nodes:무선링크에서 안정적인 전송이 사용된다.
- flow control, error detection, error correction, half-duplex and full-duplex

---

📌 6-2. Error detection, correction

* Error detection
- EDC: error detection code, 에러 검출 및 교정을 편리하게 해주는 구조적인 bits
- D: data bits

* Parity checking
- single bit parity: parity bit에 1 또는 0을 넣는다.
- Even parity: 전체 bit의  1의 개수를 짝수로 만든다.
- 받은 데이터에서 1의 개수가 홀수면 bit error가 발생했음을 알 수 있다.
- 하지만 두 개의 bit가 error난것은 알 수 없다.
- two-dimensional bit parity: 데이터를 행렬단위로 배치해서 parity bit를 각 행, 열마다 만든다.
- single bit parity 보다는 훨씬 강력하다.

* Internet checksum
- TCP, UDP에서 배웠던 방법

* Cyclic Redundancy Check (CRC)
- 가장 널리 사용되는 방법.
- D: data bits
- G: bit pattern (generator) = r+1 bit (given)
- R: generator로부터 생성된 crc 코드 = r bit
- <D,R>을 G로 나눴을 때 정확히 나눠떨어져야 한다. = no error

* CRC example
- D*2^r => r bit만큼 왼쪽으로 shift 한다.
- D*2^r (+:XOR) R = <D,R> = nG
- D*2^r = nG (+:XOR) R
- R = remainder[D*2^r/G]
- sender는 R을 구한 다음 D에다가 R을 붙여서 <D,R>을 전송한다.
- receiver는 <D,R>을 받고 G로 나눠서 나머지를 확인한다. 0 = no error, 0 != error

---

📌 6-3. Multiple access protocols

* Multiple access links, protocols
- 2계층 프로토콜의 핵심 기능 중 하나 = Multiple Access Protocol (다중 접속 프로토콜)
- two types of "links":
- point-to-point: ethernet switch, 유선
- broadcast (shared wire or medium): wifi, 무선 이동통신망

* Multiple access porotocols
- 여러개의 노드들이 하나의 broadcast 채널을 공유하는 환경에 사용된다.
- 두 개 이상의 신호가 겹쳐지는 상황(충돌)을 관리한다.
- 채널 사용권을 결정하는 알고리즘을 구현한 것이다.
- 효율적으로 채널을 나눠쓰는 방법을 구현한 것이다.
=> Medium Access Control (MAC) Protocol

* An ideal multiple access protocol
- given: 최대 스피드가 R bps 나올 때
- desiderata: m명이 각각 R/m 만큼 bandwidth를 나눠가지면 이상적인 상황이다.

* MAC protocol: taxonomy
- three broad classes
- channel partitioning: 채널을 1/n씩 정확히 조각으로 나눈다. 할당을 해도 사용을 안하면 해당 자원은 낭비가 된다.
- random access: MAC의 주류, 채널의 사용권을 끊임없이 경쟁을 통해 승리자가 갖도록 한다.
- "taking turns": 채널을 돌아가면서 사용한다.

* Channel partitioning MAC protocols
- TDMA: Time Division Multiple Access
- 전체 시간을 프레임 단위로 자르고 프레임을 슬롯 단위로 쪼갠다.
- 각 슬롯 마다 사용자를 할당한다.
- FDMA: Frequency Division Multiple Access
- 전체 Bandwidth을 사용자 수로 나눠서 각 주파수 마다 사용자를 할당한다.
- 일반적인 bursty한 데이터 트래픽하고는 잘 맞지 않는 방식이다.

* Random access protocols
- shared broadcast link, "collision"
- random access MAC protocol specifies:
- 충돌 감지하는 방법
- 충돌로부터 벗어나는 방법 (random delayed retransimission)
- 충돌이 나고 a, b 모두 충돌을 감지했을 때
- random waiting: 1~10 숫자를 임의로 고르고 해당 숫자만큼 기다렸다가 재전송한다.

* Random access protocols ex.
- ALOHA, slotted ALOHA
- CSMA, CSMA/CD, CSMA/CA

* Slotted ALOHA
- 충돌이 발생하면 충돌이 발생한 그 다음 슬롯부터 확률 p(randomization)로 재전송을 시도한다.
- X->geometric
- 장점
- 간단하다.
- "Robust" 하다: 분산형이므로 시스템이 절대 죽지 않는다. (highly decentralized)
- 단점
- 슬롯을 낭비한다. (collision, idle)
- 충돌을 감지해도 해당 슬롯이 끝날 때까지 계속 데이터 전송을 한다.
- efficiency
- max efficiency = 1/e = .37 // 나머지 확률은 충돌 or IDLE 상태

* Pure ALOHA
- time을 슬롯 단위로 나누지 않는다.
- 단순하다.
- Slotted ALOHA 대비 충돌 확률이 늘어난다.
- 전송시각이 t라면 [t - n, t + n] 사이에 다른 곳에서는 아예 전송을 하면 안된다.
- efficieny
- max efficiency = .18 // 나머지 확률은 충돌 or IDLE 상태

* CSMA (Carrier Sense Multiple Access)
- carrier sense -> channel sensing: difs 시간동안 현재 채널이 누군가에 의해 사용되고 있는지 확인하는 것
- idle: 전송 바로 시작
- busy: 전송이 끝날 때까지 대기
- CSMA/CD (collision detection): Ethernet (유선랜)
- CSMA/CA (collision avoidance): WIFI (무선랜)

* CSMA: collision
- carrier sensing을 해도 충돌이 발생할 수 있다.
- 다른 한 곳에서 전송을 시작해도 멀리있는 곳에서는 도착 이전에 idle로 뜨기 때문에 이 곳에서 전송을 시작하면 결국 충돌이 일어난다.

* CSMA/CD
- 충돌을 감지하면 전송을 중단한다.

* ethernet CSMA/CD algorithm
- 유선랜의 de Facto standard인 ethernet이 사용하는 알고리즘이다.
1. NIC receives datagram from network layer, creates frame
2. If NIC sense channel:
- idle: start frame transmission.
- busy: wait until channel idle, than transmit
3. If NIC transmits entire frame without collision, NIC is done with frame
4. If NIC detects another transmission while sending: abort, send jam signal
5. After aborting, NIC enters binary exponential backoff(random waiting time을 발생시킨다.)
- 해당 충돌이 m번째 충돌일 때, K: {0, 1, 2, .., 2^m-1} 사이에서 숫자를 고른다.
- K * 512 bit times을 기다린다.
- ex. ethernet R = 100 Mbps, 1 bit time = 10^-8 sec.
- m이 커질수록 다시 충돌할 확률이 작아진다.
- efficiency
- prop delay가 크면 효율이 떨어진다.
- trans delay가 크면 효율이 좋아진다.

* "Taking turns" MAC protocol
- polling: master node "invites" other slave nodes // 블루투스
- concerns: polling overhead, latency, single point of failure (master)
- token passing: token을 돌려가면서 token을 가진 노드만 데이터 전송을 하도록 한다.
- concerns: token overhead, latency, single point of failure (token)

---

📌 6-4. LANs

* MAC addresses
- 32-bit IP address: network-layer address for interface // 128.119.40.136 => 집주소 느낌
- 48-bit MAC address: LAN, physical, ethernet // 1A-2F-BB-76-09-AD => 주민번호 느낌

* ARP: address resolution protocol
- ARP table: <IP address, MAC address, TTL>

* ARP protocol in action
1. A broadcast ARP query (+target IP address)
2. B replies to A with ARP response (+ MAC address)
3. A receives B's reply, add B entry

* Routing to another subnet: addressing
- target IP address가 다른 subnet에 있는 경우, broadcast가 아닌 라우터의 MAC address로 query를 보낸다.

* Ethernet
- 유선 LAN(Local Area Network)
- 장점: simple, cheap

* Ethernet: physical topology
- bus: shared broadcast channel, coaxial cable
- star(switched): prevails today

* Ethernet frame structure
- preamble, address, type, CRC

* Ethernet: unreliable, connetionless
- connectionless
- unreliable
- ethernet's MAC protocol: CSMA/CD with binary backoff

* Ethernet switch
- store, forward Ethernet frames
- transparent: host는 switch의 존재를 몰라도 된다.
- plug-and-play, self-learning: switches do not need to be configured

* Switch: multiple simultaneous transmissions
- no collision, full duplex

* Switch forwarding table (2계층)
- IP forwarding table (3계층)과 다르다.
- MAC address of host, interface to reach host, time stamp
- self-learning: 들어오는 데이터를 자동으로 테이블의 정보로 기록한다.
1. record incoming link, MAC address of sending host
2. index switch table using MAC destination address
3. entry found for destination
- 찾지 못했을 때: flooding  - 모두에게 뿌린다.

* Interconnecting switches
- self-learning 방식이랑 똑같다.

---