[컴퓨터 네트워크] Ch6. The Link Layer and LANs

호스트와 라우터 : node

node를 연결하는 것을 link라고 함 → wired, wireless

2계층에서 Packet은 frame이라고함

datagram은 다른 링크를 통해 다른 link protocol을 사용해 전달될 수 있음

→ ex) 처음엔 Wifi, 두번째는 Ethernet

각 Link protocol들은 다른 서비스를 제공함

link layer에서 하는 service

• framing, link access framing : datagram에 헤더를 붙여 encapsulate link access : shared medium인 경우 채널에 접근 헤더에 있는 MAC 주소는 source, destination을 구분해줌 (IP주소와는 다름)
  
• reliable delivery between adjacent nodes 신뢰적인 전송이란 물리적으로 옆에 있는 node까지만 신뢰적이면 된다는 의미
  
• flow control
• error detection : 에러 발견만
• error correction : 에러 발견 및 수정
• half-duplex and full-duplex : 양방향 전송 half는 한번에 한쪽만 말할 수 있는 것이고 full은 둘다 가능
  

link layer는 모든 host에 구현되어 있음 → NIC or chip에 있음

1,2 계층은 보통 같이 구현되어 있음

호스트의 시스템 버스에 붙어있음

hw, sw, firmware의 combination

sender : datagram을 frame으로 encap. 에러 체킹 비트 등등

receiver : 에러 등등 체크하고 datagram을 추출해서 위 계층으로 올림

📌 Error detection, correction

EDC : Error Detection and Correction bits

D : 에러 있는지 확인 대상이 되는 부분, 헤더 필드 포함할 수도

error detection은 100% reliable하진 않음

• 프로토콜이 어떤 에러는 감지 못할수도 (드물지만)
• EDC 필드가 더 클수록 에러 잡기 쉬워짐

1. Parity checking
   

   single bit parity : 패리티 비트를 1개만 사용

   → even parity : 1의 개수가 짝수개가 되도록 parity bit자리에 0 or 1을 넣음. ↔ odd parity

   two-dimensional bit parity : 비트에러를 탐지 및 교정할 수 있음. 그러나 가로 세로 2방향으로 틑려야하므로 드문 경우
   

2. Checksum

3. CRC : Cyclic Redundancy Check

   더 강력한 에러 탐지 방법으로 실생활에서 많이 쓰는 방식이다 → ex) 이더넷, 802.11, wifi
   

   D : 데이터들

   G : 비트 패턴 = 생성 다항식

   receiver와 sender는 G라는 패턴을 알고있고, receiver는 받아서 <D,R>을 G로 나눔 → 나머지가 0이 아니면 오류 있는 것

Sender 예시

XOR 연산을 통해서 계산 → 같으면 0, 다르면 1

G : 1001 → 생성 다항식으로 x^3 + 1을 의미함 → 이건 receiver, sender 다 알고있음

여기서 실제 데이터는 101110이고 뒤에 000은 생성자가 4자리이기에 맞춰준 것

몫은 상관 X

결과적으로 실제데이터+R 을 보냄 : 101110011

→ 받는 쪽은 받은 데이터 101110011을 공유한 다항식 G로 나누는 연산 실행하고 나머지가 0이 나오면 오류 없다고 확인

📌 multiple access protocols

link에는 2가지 타입이 있음

• point-to-point 이더넷 스위치와 host 사이의 link 나만 쓸 수 있는 것 이건 중요하지 않음
  
• broadcast (shared wire or medium) 다같이 쓰는 거 이게 중요
  

Multiple Access Protocol

하나의 공유되는 broadcast channel에서 여러 노드들이 동시에 전송 → collision 발생

어떻게 node들이 channel을 잘 공유할 수 있을지

이상적인 multiple access protocol (rate R bps라고 가정)

1. 하나의 노드만 사용한다면 rate R로 보내는 것
2. M개의 노드가 같이 사용한다면 각각 R/M rate로 전송
3. fully decentralized
   • 특별한 노드 없음
   • clock, slot의 동기화 X
4. 간단

→ 하지만 불가능

MAC protocols : taxonomy

3가지 클래스

1. channel partitioning

   채널을 더 작은 조각으로 나누어서 주는 것

   ex) TDM, FDM

2. random access

   채널을 나누지 않고 collision을 허용하는 것

   충돌이 일어났을때 회복

   ex) ALOHA, CSMA

   이더넷에서 CSMA/CD, 802.11에서 CSMA/CA 사용

3. taking turns

   노드가 돌아가면서 보내는 것, 그러나 보낼게 더 있는 노드만 지속할 수 있음

Channel partitioning MAC protocols

1. TDMA : time division multiple access

   돌아가면서 채널을 사용

   각 station은 차례마다 고정된 크기의 slot을 할당 받게됨

   사용하지 않은 슬롯은 빈공간으로 남음

   

   6-station LAN에서 1,3,4만 보낼게 있고 2,5,6은 보낼게 없는 상황

   → 다른 사람이 보낼 수 있는데 안쓰고 있는거니까 공간 낭비
   

2. FDMA : frequency division multiple access

   채널을 주파수로 나눔

   각 station은 고정된 주파수를 할당받음

   TDMA와 동일하게 사용하지 않은 주파수는 빈공간

   guard band : 주파수 사이에 있는 간섭을 막기위한 약간의 공간

   

   여기서도 1,3,4만 사용중

---

Random access protocols

하나의 노드가 보낼 패킷이 있으면 full channel을 사용. 노드간에 우선순위 없음

두개 이상의 노드가 전송할때는 collision 발생

random access MAC protocol은

• 어떻게 collision을 탐지할것인지
• 어떻게 recover할건지

종류는 아래와 같은 것들이 있음

• ALOHA, slotted ALOHA
• CSMA, CSMA/CD, CSMA/CA

1. Slotted ALOHA

   가정

   • 모든 frame의 사이즈가 같다
   • time을 동일한 사이즈로 나눔
   • 노드들은 slot이 시작할 때만 전송을 할 수 있음
   • 노드들은 synchronized됨 : 시작점, 속도 동일하게 맞춤
   • 2개 이상의 노드가 같은 slot을 사용하게되면 모든 노드들은 collision을 탐지

   작동 방식은 노드가 새로운 프레임을 받게되면, 다음 slot에다가 전송하려고함

   • 이때 collisiion이 없다면 → 그냥 보내면 됨
   • collision이 있다면 → 충돌한 노드들 각각 랜덤한 시간 후에 다시 전송

   

   1,2,3 충돌 남 → 각자 랜덤한 시간 기다린 후에 재전송

   장점

   • 하나만 보내는 상황이라면 fully하게 사용가능
   • 분산성이 높음
   • 간단함

   단점

   • 충돌로 인한 slot 낭비
   • 빈 slot도 존재
   • 노드들은 패킷 전송에 걸리는 시간보다 더 빨리 충돌 감지 가능
   • clock 동기화로 인한 낭비

   최대 효율성이 37%정도로 좋은 편은 아님

2. Pure ALOHA

   

   슬롯을 사용하지 않는 ALOHA → 더 간단하고, 동기화 필요없음

   다른 것들을 신경쓰지 않고 그냥 프레임을 버리는데 collision이 조금이라도 일어난 경우에는 다 버려짐

   최대 효율성 18%로 더 안좋다

3. CSMA

   : Carrier Sense Multiple Access

   전송전에 먼저 확인을해서

   • 채널이 비었다면 : 전체 프레임 전송
   • 채널이 비어있지 않다면 : 전송 연기

   다른 것들을 방해하지 말자!

   그렇지만 여기서도 collision 발생가능 → 방금 막 시작한 두개의 노드끼리는 서로 모를 가능성이 높음

   collision 발생시에도 그냥 끝까지 전송해서 모든 패킷이 버려짐

   CSMA/CD

   : CSMA + collision detection

   충돌을 아주 짧은 시간내에 감지

   collision이 발생하면 바로 멈추고 회선 비운다음에 다시 시작 → 데이터를 많이 버리지 않을 수 있음

   collision detection은 무선에서는 사용하기 힘들다

   ALOHA보다 효율성도 좋고, 간단하고 싸고 분산됨

   • 보내고자 하는 데이터가 적을 때 좋은 방법 → 낭비가 없으므로
   • 보내고자 하는 데이터가 많으면 충돌 및 재전송이 많이 일어나서 차라리 ALOHA가 나을수도

   이더넷 CSMA/CD 알고리즘

   1. NIC는 network layer에서 datagram받아서 frame 생성

   2. NIC은 채널을 확인하고 비었으면 보내고, 아니면 기다림

   3. 만약 충돌없이 모든 프레임 전송완료 했다면 성공적으로 끝남

   4. 만약 보내는 중에 충돌을 감지하면 : abort (중지), send jam signal (다른 채널들에게 알림)

   5. 중지한 후에 NIC은 binary (exponential) backoff

      m번째 재전송이면 0~2^m-1 범위내에서 랜덤하게 선택하여 그 시간만큼 기다리고 다시 2번 step으로 감

      충돌이 많을수록 기다리는 시간을 늘려가 선택폭을 늘림

      빠른 재전송 + 대역폭 낭비를 줄임

   ---

Taking turns MAC protocol

channel partitioning MAC protocol : 채널을 효율적이고 공평하게 공유함

→ low load인 상황에서는 비효율적 : 1개의 노드만 있어도 1/N 대역폭을 할당받게됨

random access MAC protocols : low load에서 효율임. 노드가 1개만 있을때 fully하게 사용가능

→ high load인 상황에서 비효율적 : 충돌 많이 일어나서

taking turns는 이것들의 장점만 가져온 것

polling

master 노드가 다른 노드들에게 보낼 거 있냐고 물어보면서 돌아가는 방식

주로 dumb한 디바이스에서 사용됨

문제점

• polling overhead : 물어보는데 걸리는 시간
• latency : 내 차례 올 때까지 대기
• single point of failure(master) : 마스터가 죽으면 통신 불가

token passing

token이 계속 node에서 node로 이동되면서 돌아감. 이때 필요한 애가 가져가서 데이터 보냄

문제점

• 토큰 오버헤드
• latency
• single point of failure(token)

---

Cable access network : FDM, TDM and random access

downstream은 집쪽으로 내려오는 것 의미 → downstream이 upstream보다 많으므로 주로 FDM 사용하고 대역폭이 큼.

upstream은 집에서 올라가는 것 → multiple access해야돼서 충돌이 생길 수 있음

DOCSIS : data over cable service interface specification

• downstream시에는 주로 FDM
• upstream 시에는 random access + TDM(할당해주는것) 섞어서

📌 LANs : addressing, ARP, Ethernet, switches, VLANs

MAC address

IP 주소 : 32 비트, network-layer에서의 주소, forwarding에 사용

ex) 128.119.40.136

MAC (or LAN or physicial or Ethernet) 주소 : 물리적으로 연결된 interface간에 사용(같은 서브넷, 같은 IP 주소 내부)

48비트

ex) 1A-2F-BB-76-09-AD

LAN의 각 interface

• 48비트의 unique한 MAC 주소를 가짐
• 지역적으로 unique한 IP주소를 가짐 (밖에서 봤을땐 하나의 IP 주소)

MAC주소는 IEEE에 의해 할당됨

MAC주소 : 주민 등록 번호 → portable : 이동해도 변하지 않음

IP주소 : 집 주소 → not portable : 이동하면 변함

ARP : Address Resoulutionm Protocol

Q. 인터페이스들은 서로의 MAC주소를 어떻게 알 수 있을까

→ ARP table : LAN안에 존재하는 각 노드들은 테이블을 가지고 있음

• IP/MAC 주소는 매핑되어 있음 <IP 주소; MAC 주소; TTL>

A가 B에게 datagram을 보내려고하는 상황

→ B의 MAC주소가 A의 ARP 테이블에 존재하지 않으므로, ARP를 사용하여 B의 맥 주소를 찾아야하는 상황 (IP주소는 알음)

A가 B의 IP주소를 포함한 ARP 쿼리를 broadcast

LAN에 있는 모든 노드들이 쿼리를 받음

B는 A의 쿼리를 받고 자신의 MAC주소를 포함한 응답을 보냄

A는 B의 응답을 받고 자신의 ARP 테이블에 올림

---

Routing to another subnet : addressing

다른 서브넷 간에 전송이 일어나는 경우

A에서 R 라우터를 통해 B로 보냄

가정

• A가 B의 IP 주소 알음
• A가 first hop router인 R의 IP 주소 알음 → 자기 IP 주소 받을 때 받음
• A가 R의 MAC주소 알음 → 모르면 ARP 돌리면 됨

3계층 : A의 목적지 B → end to end

2계층 : A의 목적지 R → node to node

A는 3계층에서 source A, dest B인 IP 데이터 그램 생성

2계층에서는 dest MAC을 R로 설정

A → R로 데이터 전송

R에서 프레임 받아서 3계층은 그대로 두고 MAC주소를 바꿈 : MAC source R, MAC dest B

B가 전송받음 : IP주소를 확인하고 올려보냄

---

Ethernet

유선 LAN 기술 중 가장 많이 사용하는 것

간단하고 저렴함

속도가 다양하다

물리적 형태

bus : 90년대 많이 사용 → 모든 노드에서 동일하게 충돌일어날 수 있음

switched : 최근 많이 사용 → 중앙에 2계층의 스위치 존재 : 기능은 하지만 없는 것 처럼 존재

각 노드에서 switch까지는 자신만 쓰는 길이므로 충돌 X

Ethernet frame structure

이더넷 프레임에서 IP정보 encapsulate됨 → data 부분에

CRC가 중요 : 에러 관련

preamble : receiver, sender clock 속도를 동기화하는데 사용됨

address : 6바이트의 source, dest의 MAC 주소

type : 상위 계층 프로토콜 알려줌

Ethernet : unreliable, connectionless

connectionless : sender와 receiver사이에 handshaking 없음

unreliable : ACK, NAK안보냄 → 에러 체킹은 하지만 재전송 안함

CSMA/CD with binary backoff 사용

802.3 Ethernet standards

이더넷 다양하게 존재함

MAC protocol and frame format은 동일

속도가 다 다르다

fiber, cable 사용

---

Switch

스위치는 2계층 장비

• 이더넷 프레임 받아서 저장, forward
• MAC주소를 보고 selectively forwarding : 하나 이상의 Outgoing link로 보냄 → CSMA/CD 사용
  

transparent : host는 switch의 존재를 알 수 없음

plug-and-play, self-learning : 별도의 세팅 필요없고 연결만 알아서 작동

호스트는 스위치에게 직접적이고 dedicated하게 연결되어 있음

스위치는 패킷을 버퍼에 저장

이더넷 프로토콜은 각 incoming link에서 사용됨 : no collision, full duplex

위 그림에서 A → A’ , B → B’가 동시에 일어나도 충돌일어나지 않음

그러나 A → A’, C → A’ 이런식으로 목적지가 동일한 경우에는 동시에 보낼 수 없음 → 스위치가 알아서 시간차를 줌

Q. 위 그림에서 스위치가 A’에 가려면 4번 인터페이스를 통해야한다는 것을 어떻게 알까?

→ 각 스위치는 switch table이라는 것을 가짐 : 호스트의 MAC 주소, 인터페이스 번호, time stamp를 알고있음

→ Switch는 self-learning으로 이러한 정보들을 알게됨

스위치는 어떤 인터페이스를 통해서 어떤 host에게 갈 수 있는지 learn → 프레임을 받았을 때 테이블에 기록

위 그림에서 A에서 A’로 전송(MAC 주소를 통해서)

→ 이를 통해 A’ 테이블에는 A에 관한 정보가 채워짐

스위치에 프레임이 들어오면

1. 보낸 host의 incoming link와 MAC주소를 기록

2. MAC 주소를 통해 스위치 테이블에서 찾아봄

3. if 목적지의 entry를 찾았다면 {목적지가 같은 링크에 있으면 frame을 끊고 아니면 forwarding}

   else : flood → 다 뿌려줌

Example

A에서 A’로 보내려고 하는 상황인데 스위치에서 주소를 모르면 → B,C,A’,B’,C’에게 다 뿌림

이런 과정을 통해 A’에 대한 정보를 알게됨

→ 나중에 A’로 갈 때는 4번 링크로만 보내면됨

switch가 몇개가 있던간에 각자 알아서 self learning함

C → I로 send, responds 과정 → self learning

1. C → S1 스위치로 MAC 주소가 I인 프레임을 보냄
2. S1은 비어있다가 지금 C(host), 3(interface)에 관한 정보를 기록
3. S1에 I에 관한 정보가 없으므로 연결된 모든 host에게 C,I에 관한 정보를 flood
4. S4는 비어있다가 C,0 기록하고 I모르므로 S2, S3에게 flood
5. S2, S3도 비어있다가 C,0 기록
6. S3는 I에게 frame을 보내주고 I,3을 테이블에 기록
7. I에서 다시 C로 가야하므로 C,0을 보고 0번을 따라서 S4로 감
8. S4에서는 I,2를 기록하고 C로 보냄

Switches vs routers

둘다 store-and-forward

• routers : network layer 기기
• switch : link layer 기기

둘다 forwarding table을 가짐

• routers : routing 알고리즘, IP주소를 통해 테이블 계산
• switch : flooding, self-learning, MAC주소를 통해 테이블을 Learn

---

LANs : Local Area Network

Virtual LANs : 물리적으로 호스트를 옮겨도 논리적으로는 옮기지 않은 것으로 하고 싶을 때 사용

원래 CS에 있던 컴퓨터가 물리적으로 EE로 옮겨갔지만, 논리적으로는 CS에 있는 것 처럼 보이게함

switch는 물리적으로 하나의 LAN 인프라를 통해 여러 virtual LANs를 구성가능

Port-based VLANs

스위치의 포트번호를 통해 그룹을 나눔 → 논리적으로 아예 분리된 것 처럼 보이게 된다

• traffic isolation : 위에서 1-8번 포트 영역 까지가 서로 flood 하는 영역
• dynamic memership
• forwarding between VLANs : VLAN들 사이에서는 라우터를 통해서 통신하게됨

여러개의 스위치에서 VLANs spanning

trunk port : 앞의 스위치의 16번과 뒤의 스위치의 1번을 연결한 포트

물리적으로 독립된 여러 스위치들을 같은 VLAN 영역으로 묶어주는 역할

802.1Q VLAN frame format

이더넷 프레임보다 좀 더 추가적인 필드가 필요하다

source address와 type사이에 이것저것 추가적인 사항 필요