데이터망 CH6. Link Layer and LAN

Link layer Terminology

Nodes

• Hosts and Routers

Links

• Communication channels that connect adjacent nodes along communication path

Frame

• Level-2 packet, Encapsulated datagram

---

Link Layer

• 데이터그램은 다른 링크를 통해 다른 링크 프로토콜로 전송된다.
  • EX. 첫번째 링크로 Wifi, 다음부터는 이더넷
• 각각의 링크 프로토콜은 다른 서비스를 제공한다.

Service

Framing - Link access

• 데이터그램을 프레임을 Encapsulate 하여 헤더와 트레일러를 덧붙힌다.
• 프레임 헤더의 MAC 주소를 통해 송신지와 목적지를 구분한다.

Reliable delivery between adjacent nodes

• 유선의 경우 에러가 거의 없다
• 무선의 경우 에러가 많이 발생한다.

Flow control

• 인접한 전송/수신 노드간의 속도 조절

Error detection

• 신호 감쇠, 노이즈 등으로 에러가 발생한다
• 수신측에서 에러를 감지해 재전송을 요청하거나 프레임을 버린다.

Error correction

• 수신측에서 재전송 없이 비트 에러를 파악 및 수정한다.

Half-duplex

• 링크 각 말단의 노드들이 동시에 전송할수 없다.
• 양방향이 아니라는 뜻
• 반대말은 Full Duplex

---

Link layer Implementation

• 모든 호스트
• Network Interface Card / Chip
  • Ethernet / Wifi Card or Chip
  • Link / Physical layer를 포함한다.
• 호스트 시스템 버스에 내장
• 하드웨어/소프트웨어/펌웨어의 조합

전송하는 쪽

• 데이터그램을 프레임으로 Encapsulate
• 에러 체크 비트 추가, Reliable data transfer, flow control

수신하는 쪽

• 에러 확인, Reliable data transter, flow control
• 데이터그램을 Extract해서 상위 레이어의 수신단에 보낸다.

---

Error detection

EDC : 에러 감지 및 수정 비트
D : 에러 체크에 의해 보호되는 데이터, 헤더 포함 가능

• 에러 감지는 100% 신뢰할수 없다.
• 몇몇 프로토콜은 가끔 에러를 지나칠수 있다.
• EDC 필드가 크면 좀더 감지와 수정을 잘 하게 된다.
  

Parity Checking

Single bit parity

• 단일 비트 에러를 감지한다.
  • 짝수 패리티 : 1의 갯수가 짝수가 되도록 한다.
  • 홀수 패리티 : 1의 갯수가 홀수가 되도록 한다.

Two-Dimensional bit parity

• 단일 비트 에러를 감지 및 수정한다.

Internet checksum

• 전송된 세그먼트의 에러 ( 비트 플립 ) 를 감지한다.

전송

• UDP 세그먼트의 내용을 16비트 정수의 나열로 간주한다.
• Checksum
  • 세그먼트 내용들의 합, 버려지는 올림수는 1의자리로 가져와 더한다.
• 체크섬 값은 UDP 체크섬 필드에 들어간다.

수신

• 수신된 세그먼트의 체크섬을 계산한다.
• 필드에 있는 체크섬과 계산된 체크섬을 비교한다
  • 다름 : 에러 발견
  • 같음 : 에러 없음 ( 에러 있을수도 있음 )

Cyclic Redundancy Check

• 강력한 에러 감지 방법
  D : 데이터 비트
  G : r+1 비트로 이루어진 비트 패턴 ( 송신자와 수신자 사이에 약속된 값 )
  R : CRC 비트

• CRC 비트를 포함한 전체 데이터를 G로 나누었을때 나머지가 없으면 에러가 없는것으로 간주한다.

구하는 방법

• 전송할 데이터를 G로 나누어 r비트의 나머지가 남도록 한다.
• 최소 r+1 bit의 에러를 검출할수 있다.

---

Multiple access link / protocol

Types of Link

Point To Point

• 이더넷 스위치와 호스트간 연결

Broadcast

• 구식 이더넷
• 케이블 망에서의 HFC 업스트림
• 와이파이, LTE, 위성통신

Multiple Access protocol

• 단일 및 공유되는 Broadcast channel을 사용한다.
• 둘 이상의 동시 전송이 노드에 의해 이루어질시, 간섭이 발생한다.
  • 둘 이상의 신호가 노드에 의해 수신될 경우 : Collision ( 충돌 )

Ideal multiple access protocol

• 조건 : R bps 속도의 Multiple access channel
  • 한 노드가 전송을 원할시 R의 속도로 전송
  • M개의 노드가 전송을 원할시 평균적으로 R/M의 속도로 전송
  • 완벽하게 비-중앙화
    • 전송 관리 위한 특별한 노드 없음
    • Clock / Slot을 통한 동기화 없음
  • 간단!

MAC ( Multiple Access Channel ) Protocol 분류

1. Channel Partitioning

• 채널을 작은 조각 ( 타임슬롯, 주파수, 코드 ) 로 분리한다.
• 각각의 조각을 노드가 독점적으로 사용할수 있도록 한다.

2. Random access

• 채널이 분리되지 않고, 충돌이 허용된다.
• 충돌로 부터 복구한다.

3. Taking turns

• 노드가 차례를 가져간다.
• 전송할게 많으면 턴을 오래 가져간다.

채널 분리 MAC 프로토콜 : TDMA / Time Division Multiple Access

• round 라는 시간 단위로 채널을 나눈다.
• 각 노드는 차례대로 고정된 길이의 시간 슬롯(time slot)을 획득하여 채널 접속
• 사용되지 않은 slot은 낭비된다.

채널 분리 MAC 프로토콜 : FDMA / Frequency Division Multiple Access

• 채널 스펙트럼이 여러 주파수 밴드로 분리된다.
• 각각의 노드가 고정된 주파수 밴드를 할당 받는다.
• 사용되지 않는 주파수 대역은 아무것도 하지 않는다.

랜덤 Access 프로토콜

• 2개 이상의 노드의 전송 : 충돌
• R bps의 속도로 전송 가능한 상황
• 노드간 우선순위 없음

정의하는것

• 충돌 감지
• 충돌 복구

1. Pure Aloha

• 단순하고 동기화 되어 있지 않다
• 프레임 도착시 바로 전송한다.
• 동기화가 되어있지 않아 충돌 확률이 증가한다.
• 0.18 정도의 효율성을 가진다.

2. Slotted Aloha

가정 하는것

• 모든 프레임의 사이즈가 같다
• 시간이 동일한 크기의 슬롯으로 분할된다.
• 노드는 슬롯 시작시에만 전송을 시작한다.
• 노드들은 동기화 되어 있다.
• 2개 이상의 노드가 슬롯에 전송 시작시 모든 노드가 충돌을 감지한다.

작동

• 노드가 빈 슬롯 발견시 다음 슬롯에 전송을 한다.
  • 충돌이 없을시 : 노드는 새로운 프레임을 다음 슬롯에 전송한다.
  • 충돌이 있을시 : 노드가 p의 확률로 연속된 프레임에 재전송을 시도한다.
    
  • 1, 2, 3이 초반에 충돌했지만 다음 슬롯에 아무도 확률에 걸리지 않아 아무도 전송을 하지 않은 모습이다.
  • 두번째 경우는 1과 2가 충돌해 다음 슬롯에 2가 확률에 걸려서 바로 재전송하는 모습이다.
• 장점
  • 단일 활성 노드가 연달아 채널을 사용할수 있다.
  • 상당히 탈중앙화 되어 있다.
  • 간단하다
• 단점
  • 충돌로 인해 슬롯이 낭비된다.
  • 아무도 사용하지 않는 슬롯이 생긴다.
  • 노드들의 시간이 동기화되어야 한다.
  • 충돌 감지가 어려울수 있다.

효율성

• 전송에 성공한 슬롯 / 전체 슬롯
• 대략 0.37 정도의 효율성을 가진다.

CSMA ( Carrier Sense Multiple Access )

Simple CSMA

• 전송 직전에 관찰/Listen 한다.
  • 채널이 사용되지 않는다면 : 전체 프레임을 전송한다.
  • 채널이 사용중이라면 : 전송을 늦춘다.

CSMA/CD ( CSMA With Collision Detection )

• 짧은 시간 내에 충돌이 감지된다.
• 충돌되는 전송은 바로 취소된다, 채널의 낭비가 줄어든다.
• 유선상에서는 충돌감지가 쉽고, 무선상에서는 어렵다.

CSMA의 충돌

• carrier sensing 에도 여전히 충돌은 발생할수 있다.
  • 두 노드간의 Propagation delay == 두 노드가 서로 전송을 시작했음을 파악하지 못함
    

두 노드가 전송을 시작하고 Propagation 되는 동안 충돌이 발생하는 예시

• 이로 인해 전체 패킷 전송 시간이 낭비된다.
• 거리 및 Propagation delay는 충돌 확률을 계산하는데 필요하다.

CSMA/CD

• CSMA/CS ( Collision Sensing ) 은 충돌로 인해 소모되는 시간을 줄여준다.
• 충돌이 발견되면 전송이 취소된다.

알고리즘

1. NIC가 네트워크로부터 데이터그램을 받아 프레임을 생성한다.
2. NIC가 채널을 확인한다.
   • 사용되지 않고 있을시 전송
   • 사용되고 있을시 기다린다.
3. 전체 프레임을 충돌 없이 전송시 성공
4. 전송하는 동안 다른 전송을 발견할시 즉각 멈추고 jam signal을 보낸다.
5. 전송을 멈추고 난 뒤 Binary backoff 에 들어간다.
   • m번째 충돌에 대해 NIC는 $0 \to 2^m-1$ 중 하나를 랜덤한 K를 선택한다, 이후 NIC는 K * 512 비트 시간만큼 기다린 후
     채널을 확인하는 동작으로 다시 이동한다.
   • 충돌이 많아질수록 backoff 가 길어진다.

Taking turn MAC protocol

• 채널 분리 / 랜덤 접속에서 장점만 빼 사용한다.

Polling

• controller 노드가 client 노드들에게 보낼 데이터가 있는지 물어보는 과정.
• 신경 써야 할 것
  • 폴링 자체의 시간 소요
  • latency: 늦어질 수 있다.
  • sing point of failure: master가 죽으면 slave들은 아무것도 못하고 계속 기다려야 된다.

Token Passing

• 토큰이 있는 노드만이 데이터 전송이 가능하다.
• 데이터를 다 보낸 노드는 다음 노드에게 토큰을 넘긴다.
  
• 신경 써야 할 것
  • 토큰 오버헤드
  • 지연시간
  • token을 가지고 있는 node가 죽으면 token이 사라져 node 전체가 기다려야 한다.

Cable access network 의 예시

FDM, TDM, 랜덤 액세스

• 다수의 다운스트림이 FDM 채널을 통해 전송된다.
  • Broadcast
  • 단일 CMTS를 통해 채널로 전송한다.
• 다수의 업스트림 채널이 전송된다.
  • 모든 사용자가 특정 업스트림 채널의 타임 슬롯을 경쟁한다.
  • TDM을 사용하는것.

DOCSIS : 케이블을 통해 전송되는 서비스 인터페이스의 설명서

• 업스트림/다운스트림 주파수 채널에 FDM 사용하기
• 업스트림에 TDM 사용하기 : 슬롯에 할당, 경쟁 수반
  • 다운스트림의 MAP 프레임이 업스트림 슬롯을 할당한다.
  • 업스트림 슬롯의 할당 요청 혹은 데이터 업로딩은 선택된 슬롯에 랜덤 액세스되어 전송된다.

---

MAC 주소

• 48비트로 이루어져 NIC ROM 에 저장되어 있거나, 소프트웨어적으로 설정 가능하다.
  • EX. 1A-2F-BB-76-09-AD
  • LAN의 인터페이스가 가지는 고유한 주소
• MAC 주소는 IEEE에 의해 할당이 관리된다.
• 앞의 24비트는 제조사를 지정하고, 이후 24비트는 자유롭게 지정된다.
• 같은 서브넷 내에서 물리적으로 연결된 인터페이스간에 frame을 전송하기 위해 지역적으로 사용한다.

---

ARP

Address resolution protocol

• IP 주소를 알고 있을때 interface의 MAC 주소를 알아내는 방법.
  • 링크 계층에서 전송시엔 Frame을 사용해 MAC주소로 보내기 때문이다.

ARP Table

• 각각의 IP node ( Host / Router ) 의 LAN이 가지고 있는 테이블
• LAN 노드를 위한 IP-MAC 주소매핑을 한다.
  • [ IP 주소 : MAX 주소 : TTL ]
• TTL : 매핑이 유지되는 기간
• arp -a 로 확인 가능하다.

A가 B에게 데이터그램을 보내고 싶을때

1. B의 MAC 주소가 A의 ARP table에 존재하지 않는다.
2. A는 B의 IP 주소를 포함한 ARP query packet을 broadcast한다.
   • 자신의 IP/MAC 주소, 찾고자 하는 MAC 주소 포함.
3. 같은 LAN에 존재하는 모든 node들은 ARP query를 받는다.
4. ARP packet을 받은 B는 자신의 MAC 주소를 가지고 응답한다.
   (이때 A의 IP 주소, MAC 주소를 알기 때문에 unicast를 이용하여 A에게만 전송한다)
5. A는 자신의 ARP table에 B의 MAC 주소를 저장 후 그를 통해 전송한다.

A가 First hop router R을 거쳐 B로 데이터그램을 보내고 싶을때

• A는 B의 IP를 알고 있다.
• A는 R의 IP와 MAC 주소를 알고 있다.

1. A는 Subnet-Mask를 가지고 B가 다른 LAN에 존재하는 것을 인지한다.
   • IP 의 Network ID 가 다른것으로 확인할수 있을것이다.
2. A에서 frame에 B의 IP 주소와 R의 MAC주소를 넣어서 R에게 보낸다.
3. R에서 frame을 까본 후, 목적지가 B임을 확인하고 이를 B로 Forwading한다.
   (router도 ARP table이 존재해 목적지 IP 주소를 보고 MAC 주소를 넣어서 packet을 전송한다)
4. 목적지 B에서 Frame을 받는다.

---

Ethernet

시장지배적 유선 LAN 기술

Physical topology of Ethernet

Bus

• 한쪽에서 사용하게 되면 다른 쪽에서는 사용하지 못하며 이로 인해 충돌이 발생할 수 있다.

Switched ( Star Topology )

• 중간에 layer-2 스위치가 위치한다.
• 서로가 분리된 link를 이용하고 이를 통해 충돌을 막을 수 있다.

이더넷 프레임 구조

• IP 데이터그램을 Encapsulate 한다.
  

• Preamble : 수신자와 송신자간 동기화를 위해 사용한다. - 10101011

• Addresses : MAC 주소, 올바른 MAC 주소로 받아 Network layer로 데이터를 올려준다.

• Type : 상위 레이어 프로토콜에 대한 설명

  • Demux 에 사용한다.

• CRC : 수신자에 대한 CRC 검사

  • 에러 검출시 프레임을 버린다.

이더넷의 특징

Connectionless

• 송수신 간에 Handshaking 과정이 없다.

Unreliable

• 받아오는 NIC에서 송신측 NIC에 ACK나 NAK를 보내지 않는다.
  • 송신측에서 TCP의 rdt같은것을 쓰지 않는 이상 버려진 프레임은 복구될수 없다.

Ethernet Multiple Access Protocol

• Unslotted CSMA/CD with Binary Backoff ( $0$ ~ $2^m - 1$ ) 를 사용한다.

---

802.3 이더넷 기준

• 이더넷의 표준은 다양함.
• 프레임 포맷과 MAC 프로토콜은 같다
• 속도 / 물리적 매체에 따라 갈린다.

---

Ethernet switch

• Link layer device
  • 이더넷의 프레임을 저장/전달 한다. ( 버퍼를 가진다 )
  • 들어오는 프레임의 MAC 주소를 확인 후
    선택적으로 1개 혹은 2개 이상의 출력 링크를 통해 프레임을 전송한다.
  • switch는 point - to - point 통신을 하기 때문에 충돌이 생기지 않지만 CSMA/CD를 그대로 사용한다.

동시전송

• Host는 스위치와 직결 연결되어 있다.
• 각각의 입력 링크에 이더넷 프로토콜이 사용된다. >> 각각의 연결이 따로 충돌 도메인을 가진다.
• A'-A 와 B'-B 연결은 충돌 없이 가능하다
  
• A-A' 와 C-A' 연결은 충돌이 일어난다
  

스위치가 작동하는 방식

• 각각의 스위치는 Host의 MAC 주소, Host와 연결된 Interface, Time stamp 를 엔트리로 가지는
  스위치 테이블을 내장하고 있다
  • 라우팅 테이블과 유사하다.

self-learning : Switch table을 채워 나가는 과정

• 스위치가 어떤 interface로 나가야 특정 호스트에 도달할수 있을지를 배워 나가는 과정
• 프레임이 도착하면 스위치는 보낸이의 위치를 학습한다.
• 보낸쪽의 맥주소와 interface 쌍을 스위치 테이블에 저장한다.

비어있는 switch table

A가 프레임을 보내고 난 이후의 switch table

• A의 맥 주소와 A에 도달하기 위한 interface가 저장되어있다.

프레임 전달 방법

1. 스위치가 프레임을 받았을 때, 어떤 인터페이스로 왔는지, 어떤 맥주소에서 왔는지 스위치 테이블에 기록한다.
2. 프레임을 받았는데 들어온 인터페이스 목적지가 송신지와 동일하다면 프레임을 버린다.
3. 그렇지 않다면 table entry에 기록된 인터페이스로 보낸다.
4. 만약 entry가 비어 있다면 flooding 시킨다.
   • 받은 interface를 제외한 모든 interface에 보낸다.

---

스위치 상호연결

• self-learning 스위치를 상호 연결할수 있다.
  

---

스위치 vs 라우터

• 둘다 Store / Forward 한다.
• 둘다 포워딩 테이블을 가진다.

라우터

• Network-layer device
• 라우팅 알고리즘을 통해 테이블을 계산
• IP 주소 사용

스위치

• Link-layer device
• self-learning 통해서 테이블 학습
• MAC 주소 사용

---

VLAN

• LAN의 크기가 너무 커지면
  • 모든 layer-2 broadcast traffic이 전체 랜을 지나쳐야 한다.
  • 효율, 안전, 개인정보 이슈가 생긴다.

• CS에 있는 사람이 EE로 이동할 시, 물리적으로는 EE 스위치에 있으나 논리적으로는 CS 스위치에 계속 유지하고 싶을수 있다.

• VLAN을 지원하는 스위치는 단일 LAN 구성에서 여러 VLAN 을 구성할수 있다.

Port based VLAN

• 스위치의 포트를 그룹으로 나누어 여러개의 가상 스위치처럼 작동하게 한다.
  

Traffic isolation

• 1~8번 포트에서 출발한 프레임은 1~8번 포트로만 전달될수 있다.

Dynamic membership

• VLAN 사이에서 포트들은 동적으로 할당될수 있다.

Forwarding between

• 스위치간 통신은 여타 다른 분리된 스위치와 같이 다른 스위치를 거쳐 연결된다.

Trunk port

• 하나의 포트에 여러 VLAN 트래픽이 통과하는것을 의미한다.
• 전송과 동시에 VLAN ID 정보 또한 전송이 된다.
• 802.1q 프로토콜을 통해 추가적인 헤더를 추가 혹은 제거한다.

---

MPLS

Multi Protocol Label Switching

• 라벨 스위칭 라우터로도 불린다.
• 라벨값만을 이용해 패킷을 outgoing interface 로 forwarding 한다.
• MPLS 포워딩은 IP 포워딩 테이블과는 분리된다.

목표

• MPLS가 가능한 라우터끼리 빠른 IP 포워딩
• 고정된 길이의 label을 사용한다.

원리

• 고정된 길이의 ID를 통해 빠르게 lookup 한다.
  • Longest prefix match 보다 빠르다.
• IP 데이터그램은 IP 주소를 유지한다.

유연성

• MPLS 포워딩의 결정은 IP를 이용한 결과와 다를수 있다.
• 같은 송-수신에 대해 다른 경로를 사용할수 있다. ( 트래픽 에지니어링 )
• link fail 발생시 빠르게 경로를 수정할수 있다 ( 미리 백업 경로를 계산해둠 )

• IP 라우팅의 경우 목적지 주소에만 의존해 경로를 결정한다.

• IP/MPLS 라우터는 송신지와 수신지의 정보를 이용해 경로를 결정할수 있다.
• Generalized forwarding 과 유사하다.
• 경로 재계산이 빠르다
  • 연결 실패시 백업 라우트를 미리 계산해 둔다.

MPLS signaling

• 기존 OSPF 에서 확장된것
  • 링크 상태 정보를 MPLS 가능한 라우터끼리 flooding 한다.
• 엔트리 MPLS 라우터가 RSVP-TE Signaling protocol을 통해 다른 라우터의 포워딩을 설정한다.