Chapter 6. Link Layer

 

6-1. Link layer services

6-2. Multiple Access links & Multiple Access Protocols

6-3. MAC addresses and Address Resolution Protocol(ARP)

6-4. A day in the life of a web request

---

Link layer

Link layer의 용어들

 

nodes: hosts and routers

links: 근처 node들을 연결해주는 communication channels

- wired links

- wireless links

layer-2 packet: "frame"

 

Link layer: context

 

datagram은 source에서 destination까지 가는 데 다양한 link 건너감

ex. Wifi는 Ethernet switch에 연결돼 있음

=> first hop은 wifi link를, second hop은 wifi access point부터 Ethernet switch까지 ethernet link를 건너감

 

각 link protocol은 각자 다른 서비스 제공

ex. reliable data transfer

frame이 link를 거쳐 건너 왔으면 잘 건너 왔는지 receiver가 검사 => 잘 건너오지 못했다면 오류가 난 frame correction 진행

 

"transportation analogy": link layer은 transportation에 비유 가능

transportation	Link layer
tourist	datagram
transport segment	communication link
transportation mode	link-layer protocol
travel agent	routing algorithm

 

 

Link layer services

 

Framing

: datagram에 header와 trailer 붙여 frame으로 encapsulate하는 것

다른 계층의 encapsulation에서는 header만 붙임. link layer에서는 trailer&header 둘다 붙임.

물리적인 Link를 건너가기 위한 src/des의 MAC주소를 붙여줘야 한다.

- IP address: src에서 des로 가기 위해 필요한 주소

- Mac address: link 하나를 건너가기 위한 주소

 

link access

channel에 접근해야 하는데 channel은 shared medium인 경우가 많다.

link access는 channel을 접근할 때 link에 접근할 수 있게 해주는 서비스

 

reliable delivery between adjacent nodes

 

- flow control

: sending과 receiving 속도 차이 조절

- error detection

* receiver측에서 수행

* sender에게 error 복구하기 위해서 retransmit 해달라는 신호 보내거나, 조용히 drop함

* error가 없으면 수행하지 않음

- error correction

: receiver가 알아서 error correct함

* error가 발생하든 말든 모든 frame에 correction code 집어넣어 놓음

 

시간 소요: error detection > error correction (receiver가 sender에게 오류 보내고 sender가 다시 보내는 과정이 필요하기 때문)

frame size: error detection < error correction (transmit해야 하는 bit수가 더 많아지기 때문)

 

=> 이 기능들은 모든 link layer들이 하는 게 아니라 재량대로 골라서 수행

=> link layer의 error detection/correction만으로 보장 못함

=> transport layer의 end-to-end reliability 도움 필요

 

link layer의 implementation

 

- 네트워크의 모든 node에 link layer 존재

 

- link layer은 end host에 full 버전이 들어감

* network layer의 경우 end host에 간단한 버전만이 들어감.

 

- 구체적으로 "adaptor" 또는 chip에서 실행(hardware적으로 구현돼있음)

* adaptor = network interface card(NIC)

* Ethernet 또는 WiFi card/chip

=> 이 두 곳 중 하나에 link 계층과 physical 계층이 구현돼 있음

 

- host의 system bus에 부착돼 있음 => network을 통해 받은 데이터를 CPU가 처리할 수 있음

- hardware, software, firmware가 혼합적으로 활용되어 link layer 구현

 

왼쪽이 sender, 오른쪽이 receiver

 

sender측: 

- datagram을 frame으로 encapsulate

- error checking bit들 추가, reliable data transfer, flow control 등

 

receiver측: 

- error 찾거나, reliable data transfer, flow control 등

- datagram을 decapsulate해서 위 계층으로 올려보냄

 

 

link 종류

 

- Point-to-Point networks(주로 WAN - network core쪽)

: 두 host 간 연결

: p2p 네트워크 ex.

=> Dial-in

=> DSL access network

=> high-speed p2p link로 연결된 router

=> Ethernet switch와 host

: protocol ex.

=> SLIP, PPP, HDLC

 

 

- Broadcast networks(주로 LAN)

: 모든 host들이 하나의 communication channel 공유하는 네트워크

: 공유하기 때문에 비교적 느림

: 네트워크 ex.

=> old-fashioned Ethernet

=> Wireless LAN(Wi-Fi)

=> Satellite networks

=> Hybrid fiber-coaxial cable(HFC)

=> Token ring

=> FDDI

: protocol ex.

=> IEEE

 

broadcasting network, 즉 multiple access link에 대해서 좀 더 자세히 살펴보자.

 

Multiple access links
Multiple access protocols

 

 

single shared broadcast channel은..

두 개 이상의 node들이 동시에 transmission을 할 때 충돌이 발생할 수 있다.

=> multiple access protocol을 통해 해결

 

- node들이 channel을 어떻게 공유할 건지 distributed algorithm을 통해 정의

ex. 다음에 누가 channel을 공유할 건지 결정

 

- control하기 위해서도 shared channel 사용

사용자 데이터를 전송하는 channel과 분리된 다른 channel(out-of-band channel) 필요

But,, 대부분의 경우 out-of-band channel이 없음 => 사용자 데이터 전송 channel 써야 함 => 낭비 ㅜㅜ

 

channel partitioning

- time(TDMA): channel을 time slot으로 나눠 여러 사용자에게 사용 시간을 지정해줌

- frequency(FDMA): frequency별로 다른 사용자들이 동시에 사용하도록 함

- code(CDMA): channel로 내보내는 code를 달리해 

=> 각각 time slot을 나눠 synchronize하는 데, 사용자 간 겹치지 않게 frequency band 나누는 데, coding을 하는 데에 overhead가 존재

 

(+) load가 많을 때 channel을 효율적으로 공유

(-) load가 적을 때는 비효율적 (보낼 게 없는 상태임에도 나눠져 있음. 사용할 게 없는 사용자한테도 할당되기 때문)

 

 

random access

: 보낼 데이터 있는 사용자가 dynamic하게 channel을 잡아 사용

- ALOHA(satellite에서 사용)

- CSMA(WiFi, Ethernet에서 사용): 다른 사람이 channel을 사용하고 있는지 먼저 확인 => 채널이 조용해지면 자신의 데이터 실음

* But,, 채널이 조용해질 때 다수의 사람이 access할 수 있음(충돌) => CD & CA 사용

- Collision Detection(CD): collision 발생 여지 남겨 놓고 발생하면 collision된 애들끼리 서로 누가 먼저 보낼 건지 정해줌

- Collision Avoidance(CA): 아예 collision 발생하지 않게 control signal 사용

 

(+) load가 적을 때 하나의 node가 channel을 독점해 사용 가능하기 때문에 효율적

(-) load가 많을 때는 충돌

 

taking turns

: 순서로 돌아가면서 함

: Polling, Token passing, Bluetooth, FDDI, Token Ring 등

 

=> channel partitioning과 random access의 장점만 가져옴

 

- polling

* intelligency 많이 가지고 있는 master, dumb한 slave 사이에서 주로 사용됨

* master가 slave들 polling(보낼 것 있는지 물어봄)

=> 보낼 것이 있다면 보내지만, 보낼 것 없으면 polling 대답하지 않고, 그러면 다음 slave로 순서 넘어감

 

(-) polling overhead: polling을 하기 위해서도 shared medium 필요하기 때문

(-) latency: 전 순서의 slave가 보낼 데이터가 없어도 순서를 기다려야 하므로

(-) single point of failure(master): master에 문제가 생기면 아무 작업도 일어나지 못함

 

그렇지만,, 단순히 polling하는 것일 뿐 자원을 완전히 독점하는 것이 아니기 때문에 partitioning보다는 overhead 적음

- token passing

: device들이 모두 동등하게 intelligent한 관계

보낼 token이 없다면 다음으로 token 패스해줌

 

(-) token overhead

(-) latency: 보낼 것이 있어도 token 오기를 기다렸다가 순서가 되면 보낼 수 있으므로

(-) single point of failure(token): token에 문제가 생기면 아무 작업도 일어나지 못함

 

 

IEEE 802 standards

 

Network Implement Card(NIC)에 implement 되어 있음

 

link 계층은 세 서브계층으로 나뉨

 

- Logical Link Control(LLC)

: 실제 link가 뭐건 간에 공통적으로 존재

 

- 802.1 MAC Bridging

: LLC와 아래 서로 다른 medium들 연결

 

- MAC sub layer

* 802.3: Ethernet (CSMA CD 사용)

* 802.11: WLAN (CSMA CA 사용)

=> medium access control(CSMA CD/CA)은 다 제각각 다르지만

한 link 건너왔을 때 flow control/error control은 다 같이 해줌

 

MAC address(LAN address)

 

 

IPv4 address

- 32-bit짜리

- network-layer address

- layer-3(network layer)의 forwarding을 위해 사용

 

MAC address

- 48-bit짜리 => 2^48가지 MAC주소 존재 가능

- NIC ROM에 영구적으로 실림

* 지금까지 사용했던 주소 사용하면 안 됨 => IEEE가 제조해 NIC ROM에 실어놓음

* IEEE는 LAN protocol, LAN(MAC) address space 등 모두 관리

- link 하나에서 물리적으로 frame을 실어나르기 위한 것

- non-hierarchical 

* IP 주소는 hierarchical

- 고유한 주소이기 때문에 위치에 따라 MAC주소가 바뀌지 않음

* IP주소는 위치에 따라 dynamic하게 주소 번호가 바뀜(현실의 주소라고 생각하면 됨)

- hexadecimal 형태로 표현됨. ex. IA-2F-BB-76-09-AD

- broadcast MAC addr => FF-FF-FF-FF-FF-FF-FF

* broadcast주소 사용하면 모든 host에게 전달 가능

 

ARP(Address Resolution Protocol)

 

IP header에는 IP src/des address가 붙어있음

IP주소가 MAC주소로 바뀜

그렇다면, IP주소에 해당하는 MAC주소가 무엇인지 어떻게 알 수 있을까?

 

LAN을 통해 목적지로 가기 위해서는 MAC주소를 알아야 하는데, network 계층에서 내려온 주소는 목적지의 IP주소다.

 

network 계층에서는 목적지 IP주소를 보고 outgoing interface 결정(routing)

그후 link 계층은 outgoing interface에서 다음 hop으로 보내기 위해 MAC 주소를 적어야 함

=> 이때"ARP" protocol 사용

 

ARP란

 

"plug-and-play" 방식 사용

- network 관리자의 간섭 없이, node가 알아서 필요할 때 동작

- src의 outgoing interface에서 des의 interface로 보내고 싶지만 MAC주소를 모를 경우, ARP 저절로 실행

 

 

ARP table

 

: 같은 LAN에 물려있는 node들의 IP주소와 MAC주소 매핑 정보

형식: <IP address; MAC address; TTL>

 

ARP table에서 MAC주소 찾을 수 없다면 ARP protocol 동작

=> 해당 매핑 정보 ARP table에 저장해둠(또 사용될 가능성이 크기 때문)

=> but, 영구적으로 저장해두는 것은 아님. 보통 20분만 저장해둠.(TTL)

* 20분동안 또 사용되지 않으면 table에서 해당 정보 제외 => 이것을 "soft state로 유지한다"고 함

 

ARP protocol 사용 양상

 

A가 B에게 전해줄 datagram 있다고 할 때

B의 MAC address가 A의 table에 없다면, A는 ARP query를 수행해 B의 MAC주소를 찾는다.

 

1. B의 IP주소를 담은 ARP query를 broadcast함

- destination MAC address = FF-FF-FF-FF-FF-FF

=> LAN에 속한 모든 node들은 ARP query를 받음

=> A의 table에서, target IP주소=B인 node만 응답

ARP query

 

- Source hardware address: A의 MAC주소

- Source protocol address: A의 IP주소

- Target hardware address: 모름

- Target protocol address: B의 IP주소

 

2. B가 ARP packet 받으면, A에게 B의 MAC주소가 담긴 ARP 응답

 

ARP response

- Target IP address: 137.196.7.14 => B의 IP address

- Target MAC address: 58-23-D7-FA-20-B0 => B의 MAC address

- sent to 71-65-F7-2B-08-53 => A의 MAC address

 

 

3. A는 B의 응답을 받고 local ARP table에 B의 entry 추가해둠

형식: <IP address; MAC address; TTL>

- IP addr: B의 IP address

- MAC addr: B의 MAC address

-  TTL

 

 

Addressing: routing to another LAN

 

<A가 R을 경유해 B로 가고 싶을 때>

IP address&mac address: 특정 interface에 할당되는 주소

 

- A가 B의 IP주소 알고 있음(B의 host name 알기 때문에 DNS를 통해 IP주소도 알 수 있음)

- A가 first hop router인 R의 IP주소 알고 있음(DHCP를 통해, 또는 직접 setup 가능)

* R에 연결된 interface의 MAC주소인 "E6-E9-00-I7-BB-4B" 알려줌

- A가 R의 MAC주소도 알고 있음(ARP를 통해)

 

구체적으로 살펴보자.

<A에서>

 

A의 IP계층에서는 

- IP src: A의 IP주소

- IP des: B의 IP주소

 

A의 link계층에서는 여기에 src/des의 MAC주소를 덧붙인다.

- MAC src: A의 MAC주소

- MAC des: R의 MAC주소

 

<R에서>

 

R의 IP계층에서는

- IP src: A의 IP주소

- IP des: B의 IP주소

=> A에 있을 때와 같음

 

R의 link계층에서는 MAC주소를 덧붙인다. 누구의 MAC주소인지를 잘 봐야 한다.

- MAC src: R의 MAC주소

- MAC des: B의 MAC주소

 

<B에서>

decapsulate해서 IP계층으로 올라감