1. Introduction

Link Layer

용어

• Nodes
  • hosts and routers
• Links
  • comminacation channels that connect adjacent nodes aling communication path
  • wired links(유선 링크), wireless links(무선 링크), LANs(지역네트워크)
• (link-layer) Frame
  • unit of transmission over a link

network layer vs link layer

• 공통점: 데이터의 actual delivery
• 차이점: 범위(converge)가 다름
  • network layer converge: between source and destination
  • link layer converge: between two physicsally connected network devices

Link layer: Services

• 공통 로컬 미디어를 통한 reliable delivery of frames

1. Framing
   • 상위 계층 레이어가 미디어에 접근하는 방법
2. Media access control
   • 데이터가 어떻게 미디어에 배치되는지, 미디어로부터 데이터가 어떻게 수신되는지를 제어
3. flow control
   • 전송/수신 노드 간의 속도 조절
4. error detection
   • 신호 약화(attenuation), 노이즈로 인한 오류
   • 수신기가 오류 감지, 재전송을 위해 송신자에게 신호를 보내거나 프레임 삭제
5. error correction
   • 수신기가 재전송을 하지 않고 비트 오류를 식별하고 수정
6. half-duplex and full-duplex
   • half duplex에서는 양 끝의 노드가 동시에 전송할 수 없음

Implement

• Adaptor에서 구현
  • Adapter = network interface controller(NIC)
• 소프트웨어와 하드웨어 레이어를 연결

2. Error-Detection and Error-Correction

Error Detection

• 수신기가 received frames의 오류 여부 감지
• 데이터의 재전송이 가능한 경우 적합 (wireless applications이나 ling propagation delay에는 적합x)

Error Correction

• 오류가 발생한 경우 오류 수정
• error correction = error detection + error correction

1. Parity checks

1. single bit parity
   • 패리티 비트를 추가하여 1의 개수로 오류 검출
     • 짝수 패리티: 패리티 비트까지 추가하여 1의 개수가 짝수가 되도록
     • 홀수 패리티: 패리티 비트까지 추가하여 1의 개수가 홀수가 되도록
   • 짝수 패리티 비트를 추가하여 보냈는데(1의 개수가 무조건 짝수) 1의 개수가 홀수가 됐다면 오류가 발생함을 감지 (오류가 발생하여 2개의 비트가 바뀌는 등 짝수의 비트 오류는 검출할 수 없음)
2. Two-dimensional parity
   • 각 행과 열에 대한 parity 값이 계산된 상태
   • 오류가 발생하면 해당 비트의 행과 열에 대한 패리티에 오류가 생김
   • 수신자는 오류 발생 검출 뿐만 아니라, 열과 행의 인텍스 값을 통해 정정도 가능
   • 2개의 오류도 검출할 수 있지만 정정은 못함

2. Checksum Methods

• 전송받은 segment에서 오류를 감지하기 위해 Internet Checksum 사용
• Sender:
  • 헤더 필드를 포함하는 세그먼트 내용을 16비트 정수의 시퀀스로 취급
  • 세그먼트 내용의 덧셈(one's complement sum)
  • 송신자가 체크섬값을 UDP 체크섬 필드에 넣음
• Receiver:
  • 수신된 세그먼트의 체크섬 계산
  • 계산된 체크섬이 체크섬 필드값과 일치하는지 확인

3. CRC(Cyclic Redundancy Check)

• 순환 중복 검사
• 데이터를 변경하지 않고 적절한 방법을 사용해서 CRC 또는 FCS(frame check sequence)비트만 추가
• 오늘날 많이 사용되는 오류 감지 기술

modulo-2 arithetic(모듈로 2 연산)

• 덧셈의 올림이나 뺄셈의 빌림(carries)가 없이, 비트별로 XOR 연산

동작 과정

• T: frame to be transmitted (n bits)
• D: data to be sent(d bits)
• G: generator (r+1 bits)
• R: CRC (r bits) -> 구해야하는 것

1. 송신자는 D에 r비트의 R을 계산하여 덧붙임
2. 수신자가 d+r개의 수신 비트를 G로 나누고, 나머지가 0이 아니면 오류 발생을 감지

Calculate R

• 2^r을 곱하는 것은 비트 패턴을 r개의 위치만큼 왼쪽으로 이동하는 것
  -> D에 2^r을 곱하여 d+r 패턴을 만듦
• 모듈로 2 연산을 사용하면 d+r 비트 패턴은 G로 정확히 나누어짐

example

1. 송신자가 R 계산하고 D 뒤에 붙여서 전송
2. 수신자가 G로 나눠봄
   • 오류 없으면 0으로 나누어 떨어짐
   • 오류 있으면 나누어 떨어지지x

Polynomials

• 비트열에 적용되는 연산을 다항식 연산으로
• ex) D=110011
  -> D(X) = $1X^5+1X^4+0X^3+0X^2+1X^1+1X^0=X^5+X^4+X+1$

3. Multiple Access Protocols

Multi Access problem

• 여러 노드가 단일 공유 매체에 동시에 엑서스 하려고 할 때 생기는 문제
• single shared-media technology
  • 이더넷 및 wireless LANs과 같은 기술이 사용하는 기술
  • 여러 노드가 동시에 신호를 전송하면 충돌이 발생할 수 있음
• 한 번에 한 스테이션만 데이터를 전송할 수 있도록 하는 메커니즘 필요

Classification of Multiple Access protocols (MAC)

• 네트워크에서 노드가 데이터를 전송하고 충돌을 피하며 조율하는 방식
• 채널을 공유하는 방법에 따라 노드 간 효과적인 통신을 가능하게 하는 다양한 프로토콜 존재
  • distributed algorithm으로 노드의 채널 공유 방법을 결정 (즉, 노드가 언제 전송할 수 있는지 결정)
  • 채널 공유에 대한 통신은 채널 자체를 사용해야함 (조율을 위한 별도의 채널 없음 no out-of-band channel for coordination)

1. Channel partitioning protocols
   • 채널을 더 작은 조각으로 나눔
     • 작은 조각은 time slots(TDMA), frequency(FDMA), code(CDMA)등을 의미
   • 각 조각들을 노드에 배정하여 독점적으로 사용하도록 (exclusive use)
2. Random access protocols
   • 채널을 분할하지 않고 충돌 허용
   • 충돌 복구 가능
     • CSMA/CD (Ethernet)
     • CSMA/CA (wireless LAN)
3. taking turns protocols
   • 노드가 차례를 기다림(take turns)
   • 보낼 것이 많은 노드는 더 오래 차례를 기다릴 수 있음
     • polling
     • token passing

3-1. Channel partitioning protocols

◾ TDMA (Time division multiple access)

• 일정 시간(round; frame)마다 분할하고, 각 round를 N개의 time slot으로 나눔
• N개의 노드에게 time slot을 각각 할당
  • 매 round마다 각 노드는 고정된 길이의 slot을 할당받음 (길이=packet transmission time)
• 사용되지 않는 time slot은 비활성화
  • ex) 6-sation LAN에서 1, 3, 4번 노드가 패킷을 보내려고 할 때, 2, 5, 6번 노드는 비활성화

◾ FDMA

• channel spectrum을 frequency bands으로 나눔
• R bps의 채널을 R/N의 대역폭을 갖는 다른 주파수로 나눠서 (여러 차로처럼) 각 fixed frequency band를 N개의 노드에게 각각 할당
• 사용되지 않는 주파수 대역의 transmission time은 비활성화
  • ex) 6-station LAN에서 1, 3, 4번 노드가 패킷을 보내려고 할 때, 2, 5, 6번 노드의 frequency band는 비활성화

3-2. Random access protocols

◾ ALOHA

• 확률p로 재전송 -> random

◾ Slotted ALOHA

• 모든 프레임이 동일한 사이즈
• 시간은 동일한 크기의 slots(1프레임 전송 시간)으로 나눠짐
• 노드는 slot이 시작할 때만 전송을 시작하고, 동기화(shychronized)되어있음
• 한 슬롯에서 2개 이상의 노드가 전송하는 경우 충돌 감지
• 노드가 새로운 frame을 얻었을 때
  • 충돌 없으면: 노드는 새로운 프레임을 다음 slot으로 보낼 수 있음
  • 충돌 있으면: 노드는 성공할 때까지 다음 slot에서 확률 p로 프레임을 재전송
• 장점
  • single active node는 채널의 최대 속도로 지속적으로 전송할 수 있음
  • highly decentralized (높은 분산): 노드의 슬롯만 동기화되면 됨, 노드가 충돌을 감지하고 언제 재전송할지 각자 결정하므로 분산
  • 단순
• 단점
  • collisions, wasting slots
  • nodes may be able to detect collision in less than time to transmit packet
  • clock synchoronization

◾ Pure ALOHA

• unslotted: slot 개념이 없다
  • 간단하고, 동기화 없음
• 프레임이 처음 도착하면 즉시 전송
• 충돌 확률 증가: t0에서 전송된 프레임은 [t0-1, t0+1] 범위에서 전송된 프레임과 충돌하므로
• 충돌이 발생하면 확률 p로 즉시 재전송
  • 즉시 재전송하지 않는 경우, 노드는 프레임 전송 시간동안 기다림
  • 기다리고 나서 확률 p로 재전송 또는 1-p로 다른 프레임 시간동안 기다림

Pure vs Slotted

• 같은 원린데 slot을 나눠서 시간 관리를 하느냐 마느냐 차이
• 다른 노드가 전송하고 있건 말건 일단 보냄
  -> 충돌 생기고 비효율적
  -> sol: CSMA

◾ CSMA/CD

• Carrier sense multiple access/Collision Detection
• 노드는 다른 노드가 프레임을 보내고 있는지 감지하고(Carrier sense), 보내고 있지 않을 때(idle) 프레임을 전송
• 다른 노드가 방해 프레임을 전송하고 있음을 검출하면, 자신의 전송을 중단하고 랜덤 시간동안 기다린 후 idle 상태인지 확인하고 전송하는 것 반복 (Collision detection)
• ACK를 사용하며, ACK를 못받으면 충돌이 발생한 것으로 가정하고 재전송

CSMA approaches

• non-persistent CSMA
  • 캐리어를 감지한 후, 랜덤 시간동안 기다렸다가 다시 캐리어를 감지하고 전송
• 1-persistent CSMA
  • 캐리어가 감지되면, idle 상태를 감지할 때까지 기다렸다가 즉시 전송
• p-persistent CSMA
  • idle일 때 확률p로 전송
  • 캐리어를 감지하면, idel 상태를 감지할 때까지 기다렸다가 확률p로 전송
  • 1-p확률로 one time slot만큼 딜레이

CD가 없을 때

1. t0에 노드B가 다른 노드들이 아무도 전송하고 있지 않아서 채널이 비어있는 것으로 감지
2. 노드B는 전송을 시작하고, 전송한 비트들은 양방향으로 전송
3. t1에 노드D가 전송할 프레임이 생겼는데, 노드B의 비트가 아직 D에 도달하지 못해서 D는 t1일 때 채널이 비어있는 것으로 감지
4. D가 전송을 시작하면, B의 비트와 D의 비트가 collision

CD가 있을 때 ⭐

• 충돌을 감지하고 즉시 전송 취소

1. 프레임들은 NIC를 보낼 준비를 하고 있음
2. NIC가 채널이 idle임을 감지하면 프레임을 전송하기 시작하고, 채널이 바쁘면 NIC는 채널이 idle이 될 때까지 기다린 뒤 보냄
3. 전송중일 때는 NIC가 collision을 모니터링
4. 충돌이 없으면 NIC는 프레임 전송을 완료하고 1번으로 돌아가고, 충돌이 감지되면 NIC는 전송을 취소하고 short JAM 신호를 보냄
5. 전송 취소 후, adaptor는 랜덤 시간만큼 기다리고 2번으로 돌아감(랜덤이 아닌 고정시간이라면 동시에 프레임을 전송했을 때 똑같은 시간을기다린 후 전송하므로 계속 충돌하니까)

• JAM 신호를 받으면 모든 스테이션은 전송을 중단하고, 각각 다른 프레임을 전송하기 전에 랜덤시간동안 대기

Binary exponential backoff

• 랜덤 시간 결정 알고리즘
• n번 충돌 후, NIC는 {$2^0, 2^1, ... , 2^{n-1}$}에서 하나를 랜덤 선택
  • 충돌을 많이 할수록 랜덤 딜레이 시간이 길어지 확률이 큼
• 16번 충돌한 뒤에는 포기하고 에러냄

4. Switched Local Area Networks

4-1. ARP (Address Resolution Protocol)

MAC address

• IP address
  • 32bit(4byte), layer 3 address for routing and forwarding
  • IANA에서 관리
• MAC address
  • 48bit(6byte) physically burned in NIC ROM
  • IEEE에서 관리
• LAN의 각 인터페이스는 IP address와 MAC address를 가짐

Address Resolution problem

• 네트워크 계층 주소와 링크 계층 주소 사이에 변환을 해주는 프로토콜
  • 네트워크 계층의 datagram의 헤더에는 IP address 포함, 링크 계층의 frame의 헤더에는 MAC address 포함
  • datagram이 링크 계층의 frame으로 encapsulation될 때, IP주소는 링크 계층에서 사용되지 않음
  • 이때, ARP 프로토콜이 IP주소와 MAC주소 사이 변환

ARP Operation

• LAN매체에 프레임을 배치하기 위해 대상 MAC 주소를 알아야 함

1. 호스트 A가 C에게 프레임을 전달하려고 함
   • 호스트 A는 C의 IP 주소밖에 모른다면?
2. ARP Request
   • 호스트 A는 호스트 C의 IP주소가 포함된 ARP 요청 메시지를 해당 네트워크의 모든 호스트에게 broadcast
3. ARP Reply
   • 호스트 C는 ARP 응답 메세지로 자신의 MAC 주소를 포함하여 응답
   • 호스트 B와 D는 나중을 위해 호스트 A의 IP/MAC주소를 ARP 테이블에 저장

ARP message format

Proxy ARP

• 라우터는 broadcast된 ARP 요청 메세지를 차단하므로
• Proxy ARP가 라우터가 로컬 네트워크 외부의 원격 호스트에 응답할 수 있도록 해줌

4-2. Ethernet

• 인터넷이 글로벌 네트워킹이면, 이더넷은 근거리 네트워킹

Topology

• bus topology
  • 모든 노드가 동일한 충돌 도메인에 속함 (서로 충돌 가능)
  • 90년대 중반..
• star topology
  • 중앙에서 스위치 활성화
  • 각 spoke는 (별도의) 이더넷 프로토콜을 실행 (노드 간 충돌 없음)

frame structure

features

• connectionless
  • 송/수신 NIC간의 핸드 셰이킹 없음
• unrealiable
  • 수신 NIC는 송신 NIC에게 ACK 보내지 않음
  • 데이터가 드롭된 프레임에 대한 재전송은 초기 송신자가 더 높은 계층의 신뢰성있는 데이터 전송(TCP)를 사용하는 경우에만 복구
    (그렇지 않으면 손실)
• ethernet's MAC protocol
  • unslotted CSMA/CD 사용 (with exponential binary backoff)

FIY: IEEE 802 Standards

• IEEE 802 standards
• Ethernets frame format
• Ethernet LAN Naming
• Type of Ethernet

4-3. Link-Layer Switches

LAN Devices

• Repeatures, hubs -> physical layer
• Switches, bridges -> data link layer
• Routers -> network layer

Ethernet Switches

• 이더넷 프레임을 저장(store)하고 전송(forward)하는 link layer device
  • 수신된 프레임의 MAC 주소를 기반으로 동작
  • 선택적으로 프레임을 하나 이상의 출력 링크로 전송
• 호스트는 스위치의 존재를 알 수 없음
• plug and play, self learning

Self-Forwarding and filtering

• self learning을 통한 switch table
  • 스위치는 어떤 호스트가 어떤 인터페이스를 통해 목적지에 도달할 수 있는지를 학습 (source의 MAC addresses 사용)
• self forwarding
  1. 처음에 비어있는 스위치 테이블
  2. 호스트A가 목적지 A'에게 프레임 전송
  3. 스위치는 모든 다른 인터페이스들에게 해당 프레임 전송
  4. 스위치는 source MAC 주소를 확인하여 해당 호스트와 인터페이스 정보를 스위치 테이블에 기록
• self filtering
  1. 호스트 A'가 목적지 A에게 프레임 전송
  2. 스위치는 스위치 테이블을 보고 프레임을 전송할 인터페이스를 찾음
  3. 스위치는 해당 인터페이스를 통해 프레임을 A에게 전송
  4. 스위치는 MAC 주소를 기반으로 A'의 인터페이브 정보도 테이블에 기록
• 모든 entry가 테이블에 기록됨
• 스위치는 이 테이블 정보를 사용하여 simultaneous transmissions (동시 전송)을 가능하게 함

Switched LANs, STP

• 스위치들은 서로 연결될 수 있음
• STP(Spaning Tree Protocol)
  • 네트워크에서 모든 목적지 간에 하나의 논리적 경로만 존재하도록 보장
  • multiple broadcast storms, loop, duplicate frames 방지

Switches vs Routers

• store and forward (저장 및 전달 기능)
  • router: network layer에서
  • switch: link layer에서
• forwarding tables
  • router: 라우팅 알고리즘과 IP주소 사용
  • switch: flodding, self-learing, MAC 주소 사용
• Broad cast
  • router: block broadcast
  • switches: pass broadcast

4-4. VLANs (Virtual Lans)

• 일반적인 LAN
  • 라우터의 인터페이스 중 하나가 서브넷(LAN) 형성
  • single broadcast domain (그룹 트래픽을 단일 스위치 내로 격리)
  • 모든 link layer broadcast traffic은 전체 LAN을 건너야한다는 단점

• "CS유저가 사무실을 옮겼지만 CS LAN 도메인을 연결하고싶다"

Virtual LAN (가상 LAN)

• 라우터가 아닌 스위치에 의해 지원되는 logical subnet(LAN)
• VLAN 내에서 exclusive(독점적인) broadcast domain

1. SC 호스트가 broadcast 전송
2. 스위치가 SC-VLAN으로만 전송
3. SC-VLAN에 있는 호스트만 broadcast를 받을 수 있다
4. 라우터는 broadcast를 막음

VLAN 없으면
VLAN 있으면

Port-based VLANs

• 스위치 포트는 VLAN 세그먼트로 그룹화 (스위치 소프트웨어에 의해)
• 스위치 하드웨어는 동일한 VLAN에 속하는 포트 간에만 프레임 전달(여러개의 그룹을 한 스위치로 구성하게 됨)

trunk port

• 스위치마다 하나의 trunk port를 가진 경우 다른 VLAN과의 간편 연결 가능

• 여러 스위치에 걸친 VLAN

1. Port-based VLAN
   • 각 VLAN 연결에 대해 스위치 간 케이블 필요
2. VLAN trunking
   • 각 스위치의 특수 포트(trunk port)가 두 VLAN 스위치를 상호 연결 -> 더 간편!

802.1Q VLAN

• IEEE가 VLAN truck를 통과하는 프레임에 대해 정의
• VLAN 태그가 추가됨