네트워크: Link layer 정리 (Multiple Access Protocol, LAN, ARP)

먼저 Link layer에 대해 대략적으로 알아보자. 

 

- Link layer에서는 wired link, wireless link, LAN을 다룬다. 

- layer 2에서는 layer3의 datagram을 encapsulation하여 frame이라는 단위의 패킷을 다룬다. 

- 이더넷, frame rely, 802.11 등의 프로토콜을 사용한다. 

 

 

< Link layer service > 

 

1) framing, link access

 

- framing: 네트워크 레이어에서 내려온 datagram은 앞 쪽에 header,

  뒤쪽에 trailer가 붙으면서 frame으로 캡슐화된다. 

- link access: source와 destination을 확인하기 위해 frame header에서 MAC  address를 사용한다.

 

 

2) reliable delivery between adjacent nodes

 

- 유선의 경우에는 거의 에러가 없다 (fiber, some twisted pair들은 신뢰적이다.)

- 무선의 경우, 높은 비율로 에러가 발생한다.  

 

 

이외에도 flow control, error detection, error correction, half-duplex and full-duplex등의 서비스가 Link layer service가 있다.

 

 

 

 

< Where is the link layer implemented? >

 

- 모든 호스트에는 Link layer가 있으며 이는 어댑터 형식으로 구성되어 있다. 

통상 이를 NIC(Network Interface Card)라 한다. 

 

ubuntu에서도 ip a를 통해 network interface를 확인할 수 있다.

 

 

 

 

< Error detection, correction >

 

link layer에서는 신뢰적인 통신을 위해 다음과 같은 과정들이 수행된다. 

 

 

1. Error detection

 

- error를 detection 하기 위해서 보내려는 datagram의 뒷부분에

EDC(Error detection and correction bits)를 추가한다.

 

 

- EDC를 크게 하면 할수록 error detection은 올라가지만 너무 커지면 overhead된다

​

 

원래 데이터 d bits에 EDC를 덧붙혀서 receiver에게 전송한다. 

 

bit-error prone link로 전송한 후, D'의 모든 값들에 error가 없는지 체크한다. 

(하지만 프로토콜이 에러를 놓칠 가능성을 갖고 있기 때문에 100%를 신뢰할 수 없다. )

 

 

 

2. Parity checking

 

1) single bit parity : burst bit error(error가 두 군데 이상 발생하는 것)는 발견하기 어렵다.

 

2) two-dimensional bit parity : error correction이 가능 (burst bit error는 발견하기 어려움)

 

- data bit를 일정한 개수로 나눈 뒤 2차원으로 만들고 각각의 parity bit를 계산한다.

- parity bit를 확인하는 parity bit의 parity bit까지 있어 parity bit가 error가 발생해도 correction가능하다.

 

그외에도 checksum같은 단순한 error detection이 있다. 

 

 

 

 

< Multiple access protocols > 

 

link에 다수의 단말들이 물려있을 때 어떻게 접속할까?

 

 여러개의 단말들이 몰려 있을 때는 broadcast 기반의 통신을 하는데 

이더넷이라는 shared wire를 이용하거나 무선인 경우 WiFi를 통해 다수의 user들이 통신한다.

 

이 때, 동시에 같은 리소스를 써서 둘 이상이 접속하게 되면 

충돌이 발생하는데 이를 어떻게 할 것인가를 정하는게 multiple access protocol이다. 

 

즉, 여러 노드로부터 동시에 transmission이 올때 충돌이 발생할 수 있으므로

이러한 충돌을 대비하고 대역을 효율적으로 사용하기 위해사용하는 것이 Multiple access protocol을 사용한다.

 

 

1. 이상적인 Multiple access protocol이란?

 

Rbps의 rate를 가진 broadcast channel이라고 가정할때 다음 조건을 만족해야한다. 

 

1) 한 노드가 전송을 원할때 R rate로 보낼 수 있어야 한다. 

2) M개의 노드로 보낸다면 평균적으로 R/M rate로 보낸다. 

3) 전송율을 조절하는 노드가 없다.(master가 없다) 

4) 단순했으면 좋겠다. 

 

 

 

2. MAC protocols: taxonomy

 

MAC 프로토콜은 channel partitioning, random access, taking turns 방식으로 나뉘어 사용된다. 

 

 

1) channel partitioning

 

- channel을 작은 조각(time slots, frequency, code)으로 나누어 collision을 막는 것

- 각 node에게 slots을 할당시켜서 배타적으로 사용할 수 있게 한다. 

- 사용하는 노드가 많으면 효율이 높아진다.

​

 

1 - 1) TDMA : time division multiple access

- time으로 channel을 나눈다. 

- 각 node는 전송할 packet이 있으면 자신에게 할당된 time slots 동안 packet bit를 전송한다.

- 사용되지 않는 슬롯들이 생기면 효율성이 떨어진다. 

 

 

 

 

1- 2) FDMA : frequency division multiple access

 

- frequency대역으로 channel을 나누는 것

- 각 station은 fixed frequecny band가 할당 

- 각 노드들은 해당 대역으로 통신을 하게 된다. 

- 사용되지 않는 대역들이 생기면 효율성이 떨어진다.

 

 

 

2) random access

 

- channel을 나누지 않으며 node가 packet bit를 전송할때 collision을 허용한다.

- collision을 허용하기 때문에 이를 어떻게 감지하고 복구할지가 관건이다.

- 사용하는 노드가 적으면 효율이 높아진다.

- 낭비없이 전체 full channel을 사용할 수 있다는 장점이 있다. 

 

 

 

2-1) Pure (unslotted) ALOHA

 

- unslotted ALOHA가 slotted ALOHA 보다 먼저 개발된 모델 

- node들이 보내야 하는 slot이 나눠져 있지 않다.

(각 노드가 보낼 수 있는 시간이 정해져 있지 않다)

- frame이 도착하면 즉시 보낸다. 

- 약간의 충돌이 생겨도 그 packet을 전부 재전송해야 한다.

- pure (unslotted) ALOHA의 효율은 최대 18%

 

 

 

 

 

​

2-2) Slotted ALOHA

 

unslotted ALOHA는 조금이라도 겹치면 충돌이 생긴다. 이를 보완한 것이 Slotted ALOHA

 

< assumptions >

 

- 모든 frame의 크기를 동일하게 하고 time slots을 균등하게 나눈다.

- node들은 보내려고 하는 시간을 미리 정해놓는다. 

- 2개 이상의 node가 해당 슬롯에서 통신하면, 다른 모든 node들은 충돌을 감지한다..

 

<operation>

 

- time slot이 시작할때 전송 

- node가 아무도 안 보낸다고 판단된다면 다음 slot에서 새로운 frame을 전송한다.

- 충돌이 있다면 node는 성공할 때까지 확률적으로 시간을 계산후, 다음 slot에 frame을 재전송

(충돌이 일어난 node들은 random 하게 쉬게 된다.)

 

 

 

장점

 

- 노드 하나만 사용한다면 최고 속도로 packet bit를 전송한다.

- decentralized되었기 때문에 구현이 단순하다.

 

 

단점

 

- 충돌이 발생하거나 낭비되는 슬롯이 발생한다.

- node들의 시간이 동기화되어야 한다.

(노드들의 시간이 전부 같게 하는 것은 어려움)

- slotted ALOHA의 효율은 최대 37%

​

 

 

2-3) CSMA (carrier sense multiple access)

 

- listen before transmit 방식으로 동작

- 다른 node에서 packet bit를 전송하고 있는지 확인 후에 전송.

- 만약 channel이 busy면 일정시간 딜레이 한후 전송 

- 하지만 CSMA도 충돌이 여전히 발생한다.

(미묘하지만 data가 propagation되면서 시간이 겹칠 수 있다)

 

다음은 패킷 전송 후, propagation이 겹치는 경우 

 

 

 

 

2-4) CSMA/CD(Collision detection)

 

- CSMA와 동일한 방식으로 collision이 발생하면 짧은 시간안에packet bit 전송을 양쪽에서 멈춘다. 

- 짧은 시간안에 collision을 감지함으로써 channel의 시간 낭비를 줄일 수 있다.

- CSMA/CD : 충돌이 발생하면 중단 요청 신호를 보낸다.

 

 

Collision detection

 

- Wired LANs: 측정하기는 쉽다. (보낸 신호와 받은 신호를 비교)

- Wireless LANs: 무선의 경우가 사용하기 어렵다. 

 

 

 

 

2- 5). Ethernet CSMA/CD Algorithm

 

1. NIC는 네트워크 계층으로부터 datagram을 받고, frame으로 만든다.

2. NIC은 channel이 idle하다고 할때 전송하고, busy하다면 channel이 idle하다고 할때까지 전송

3. NIC가 또 다른 transmission 감지 없이 전체의 frame을 다 보냈다면 성공!

4. 만약 NIC가 다른 transmission을 감지 했다면 전송을 중단하고 jam signal을 보낸다. 

5. 중지 이후,  NIC는 binary backoff 상태로 들어간다. 

 

 

※ binary backoff

n 번 충돌이 발생했다면 {0, 1, 2, . . . , 2^(n - 1)} 중 하나(K)를 선택해

 Kx512bit time만큼 랜덤하게 쉰다.

(충돌로부터 회복하는 과정으로 충돌이 많이 발생하면 할수록 오래 기다려야 한다)

​

 

 

3) Taking turns

 

- 차례가 되면 보내고 보낸 후 다음 차례에게 턴을 넘겨준다. 

(channel partitioning, random access의 장점을 조합한 것)

 

 

polling

 

master 노드가 slave 노드들에게 보낼 데이터가 있는지 물어보는 과정.

master nodes invites slave nodes to to transmit in turn.

polling

 

※ polling에 대한 concern

- pollling overhead: 반복해서 물어보게되고

- latency: 늦어질 수 있다. 

- sing point of failure: master가 죽으면 slave들은 아무것도 못하고 계속 기다려야 된다.

 

 

 

token passing

 

- token이 있는 node만 data 전송이 가능하다..

- data를 다 보낸 node는 다음 node에게 토큰을 넘겨준다. 

 

※ token passing에 대한 concern

- token overhead

- latency

- token을 가지고 있는 node가 죽으면 token이 사라져 node 전체가 기다려야 한다.

 

​

​

​

< LANS >

 

- link layer에서는 LAN, physical, Ethernet등의 방법으로 통신하며 이 때 MAC 주소를 이용한다.  

- MAC 주소는 physically-connected한 인터페이스(NIC)에서 frame을 얻을 때 사용되는 주소 

- MAC 주소는 48-bit의 크기를 갖고, 네트워크 장비의 고유번호로써 사용된다. 

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

- MAC 주소는 IEEE에 의해 할당된다. 

 

​

1. ARP : address resolution protocol

 

- 상대방의 IP주소는 아는데 MAC 주소는 모를때 사용한다.

(링크 계층에서 보낼 때는 Frame을 사용하므로 MAC 주소가 필요하다.)

- IP 주소를 실제 LAN에서 MAC 주소로 변환해 주는 protocol

- network layer protocol 

 

 

- 각 host는 ARP table을 갖는다.

- ARP table : IP 주소와 그 IP 주소에 해당하는 MAC 주소가 있다.

 

 

 

1) ARP protocol(same LAN)

 

A는 B에게 datagram을 보내고 싶다. 하지만 A는 B의 MAC 주소를 모른다. 

 

1. B의 MAC 주소가 A의 ARP table에 존재하지 않는다.

2. A는 B의 IP 주소를 포함한 ARP query packet을 broadcast한다.

3. 같은 LAN에 존재하는 모든 node들은 ARP query를 받는다.

4. 모든 node는 자신과 상관 있는 IP 주소만을 채택하고 나머지는 discard한다.

5. ARP packet을 받은 B는 자신의 MAC 주소를 가지고 응답한다.

(이때 A의 IP 주소, MAC 주소를 알기 때문에 unicast를 이용하여 A에게만 전송한다)

6. A는 자신의 ARP table에 B의 MAC 주소를 저장한다.

​

ARP는 위와  같이 plug-and-play 방식으로 ARP table을 관리자의 도움 없이 만든다.  

 

 

 

2) ARP protocol(another LAN)

 

A는 다른 LAN에 있는 B에게 R을 거쳐 datagram을 보내고 싶다. 

이 때, 다음 상황을 가정한다.

- A는 B의 IP를 알고 있다.

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

 

 

1. A는 Subnet-Mask를 가지고 B가 다른 LAN에 존재하는 것을 인지한다.

2. A에서 frame에 B의 IP 주소와 R의 MAC주소를 넣어서 R에게 보낸다.

3. R에서 frame을 까본 후, 목적지가 B임을 확인하고 이를 B로 Forwading한다.

(router도 ARP table이 존재해 목적지 IP 주소를 보고 MAC 주소를 넣어서 packet을 전송한다)

4. 목적지 B에서 Frame을 받는다. 

 

​

 

 

 

 

2. Ethernet

 

- 사무실이나 가정에서 사용되는 LAN 중 가장 많이 활용되는 기술 규격이다.

- unreliable, connectionless 하다. (CSMA/CD방식을 사용한다)

- 초창기 Ethernet은 bus 구조(=Dummy Hub)를 사용했다. 

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

- 현재는 Ethernet은 star 구조를 사용한다.

스위치를 사용함으로써 서로 분리된 link를 이용하고 이를 통해 충돌을 막을 수 있다.

 

 

 

 

Ethernet frame structure

​

adapter는 IP datagram을 Ethernet frame을 이용하여 encapsulate한다.

ethernet frame

- preamble은 상대와 비트 동기화를 위해 사용된다. 

- MAC source, destination address를 사용한다.

adapter가 받은 frame의 destination이 동일하거나 broadcast address라면 데이터를 

네트워크 계층으로 보내며 그렇지 않으면 버린다. 

- type: 상위 계층의 프로토콜

 

 

 

 

3. Ethernet switch

 

- link 계층의 디바이스 

- mac address에서 기반해서 이더넷 프레임을 store하고 forward한다.

- buffer가 있어 frame을 먼저 저장을 하고 해당 link로 전달한다.

- switch는 point - to - point 통신을 하기 때문에 충돌이 생기지 않지만 CSMA/CD를 그대로 사용

- link switch는 host는 switch의 존재를 모른다.

(단지 한 host에서 다른 host로 frame을 전달하는 역할을 한다)

- ARP가 동작할 때 plug-and-play, self-learning을 통해서 동작

- 각각의 link path들이 독립적으로 구성 중간에서 서로에게 영향을 주지 않도록 switch가 연결되어 있다.

- network 관리자가 switch를 바꿀 때마다 table을 바꾸어줄 필요 없이 self-learning을 통해서 한다.

​

 

스위치는 호스트에서 호스트로 가는 스위치 테이블을 갖고 있는데

이 테이블은 switch의 self-learning을 통해 만들어진다. 

 

스위치는 어떤 호스트가 어떤 인터페이스로 나가야 하는지 learn한다.

ex) A가 스위치로 데이터를 보냄으로써 1번 인터페이스에 있음을 알게 된다. 

 

 

 

 

- 스위치가 프레임을 받았을 때, 어떤 인터페이스로 왔는지, 어떤 맥주소에서 왔는지 스위치 테이블에 기록한다.

- 프레임을 받았는데 들어온 인터페이스 목적지가 A라면 당연히 다시 A에게 보내지 않고 드랍한다.

- 그렇지 않다면 table entry에 기록된 인터페이스로 보낸다.

- 만약 entry가 비어 있다면 flooding 시킨다.

 

 

 

 

 

 

< Multiprotocol label switching (MPLS) >

 

- 초기 목표: IP 주소 대신 고정된 길이의 label value을 이용해서 고속의 IP forwarding을 하기 위함.

(IP longest prefix matching을 이용하면 오래 걸리므로 )

- 고정된 길이의 identifier를 사용해서 fast lookup

- VC를 사용해서 들어오면 어느 인터페이스로 보낼지 결정한다.

- IP datagram은 여전히 IP주소를 가지고 있다.

 

 

 

 

< MPLS capable routers >

 

- a.k.a label-switched router

- label에 기반해서 스위칭을 해준다. (기존의 IP longest prefix matching보다 빠르다.)

- flexibility: MPLS forwarding은 IP의 forwarding과는 다를 수 있다. 

- 소스 목적지와 주소를 이용해서 같은 목적지라도 다르게 route 시킬 수 있다. 

(IP routing의 경우에는 목적지 경로만으로 정해진 경로를 이동)

ex) traffic engineering이 가능해진다. 

 

 

기존의 IP routing

IP routing

 

 

MLPS header를 이용한 routing 

MPLS routing

 

 

MPLS forwarding table 

 

MPLS는 다음과 같은 방식으로 self-learning한다.

 

 

- 호스트 A와 연결되어 있는 라우터의 경우, 0번 인터페이스로 나가야 A에 도착한다.

  이 정보를 이용하여 label = 6으로 들어온다면 0번 인터페이스로 내보내는 규칙을 만든다.   

- 주위 노드들에게 이러한 정보를 보내준다.

- R3에서 호스트 A에게 보내는 룰을 만들고 싶다.

1번 인터페이스로 나가면 A로 갈 수 있고, label=6 을 가지고 가야 처리해주므로

이때 R3로 들어온 in label이 10면 6으로 바꾸어서 보낸다.