[네트워크] 5. Link layer - Link layer services / ARP / MAC protocols

Reference - Computer Networking: a Top Down Approach

 

 

Link layer는 물리적으로 연결된 두 디바이스 사이의 네트워크를 관리한다. 인접한 node로 패킷을 안전하게 전달할 책임을 가진다.

 

Link(Data-link) layer services

 

- Terminology

hosts and routers : nodes

communication path : links (wired / wirelss / LAN)

link layer packet : frame

 

Link layer를 비유하자면 서울에서 도쿄로 여행을 간다고 할 때 탑승객을 datagram, 이동경로가 communication link, 교통수단은 link layer protocol, 여행 에이전트가 routing algorithm이라 생각하면 편하다.

 

- Link layer services

1. framing : 데이터그램을 링크상으로 전송하기 전에 link layer frame에 캡슐화한다.

2. link access : medium access control이 링크상으로 프레임을 전송하는 규칙을 명시한다.

3. reliabble delivery between adjacent nodes : TCP와 마찬가지지만, 오류가 발생한 link에서 정정

4. flow control 

5. error detection / error correction

6. half-duplex and full-duplex : datagram을 보내고나서 받거나, 보내면서 동시에 받거나

 

- Link layer address (MAC address)

subnet의 각 host와 router는 subnet에서의 주소를 구체화하기 위해 link layer address가 필요하다.

즉, 라우터가 IP 주소는 알지만 subnet을 모를 때, 이를 찾기위해 한 subnet 안에서 사용하는게 MAC(Media Access Control) address이며 그 방법이 address resolution이다. MAC address는 48bit의 [제조사 identifer 6자리 : random number 6자리]의 형태로 되어있다. (ex. [00:01:AB:01:02:03])

 

Address Resolution Protocol (ARP)

 

네트워크 계층의 주소 IP와 링크 계층의 주소 MAC을 변환해주는 프로토콜이 Address Resolution Protocol다.

라우터는 목적지 host의 IP 주소는 알지만 subnet안의 subnet 주소는 모른다. 이를 알아내기 위해, ARP request message를 subnet의 모든 host에게 보낸다. 이때 특정 IP address의 host가 response를 하면, 라우터는 IP 패킷을 destination host에게 보내게 된다.

 

link layer는 network interface controller(NIC)라 불리는 네트워크 어댑터에 구현된다.

 

MAC Protocols

link에는 두가지 유형이 있다. point to point와 broadcast다.

point to point는 unicast(= 하나의 송신자가 하나의 수신자로 전송, MAC address를 기반으로 IP주소를 목적지로 함)로, ethernet switch와 host사이를 연결한다. wired link로, collision이 거의 없다.

broadcast(=local LAN에 붙어있는 모든 단말에 전송)는 와이파이와 같은 무선망에서 사용한다.

이때 broadcast link를 쓰면, 동시에 여러 개의 transmission을 받게 되어 interference가 생긴다.

이때 collision이 발생하며, collision이 발생하면 프레임은 소실된다.

이러한 interference를 없애는 게 Multiple Access Protocol이다. 각 node가 언제 transmit할 수 있는지 등을 결정한다.

 

MAC protocol은 3가지 broad classes로 분류할 수 있다.

 

- channel partitioning (ex. 셀룰러)

- random access (ex. Wifi)

- taking turns (차례로 transmission -> 효율 안좋음)

 

Channel partitioning MAC protocol은 channel을 작게 나누어 collision을 막는 방법으로, TDMA / FDMA / CDMA 가 대표적이다. 위 각각은 Multiple Access를 Time Division할지, Frequency Division할지, Code Divisioln할지 나눈다.

FDMA는 가용 주파수 대역을 여러개로 나누어 할당하는데, 이때 인접 채널 간 간섭이 발생할 수 있으므로 Guard band를 통해 이를 방지하지만, 이때문에 주파수 대역을 효율적으로 쓰기 힘들어진다. (1세대)

TDMA는 동일한 주파수 대역폭에서 시간축을 여러 구간으로 나누고 사용자가 자기에게 할당된 시간을 다른 사용자와 겹치지 않게 사용하는 방법이다. (2세대)

CDMA는 사용자가 각자 고유의 확산 부호를 할당받아 신호를 전송하면 해당 부호를 알고있는 수신기만 신호를 복원할 수 있는 방식이다. (3세대)

추가로 OFDMA는 4세대 이동통신 기술로, 주파수의 직교성을 활용하여 간섭을 없앴다.

 

 

channel partitioning의 경우 사용하는 노드가 많으면 효율이 올라간다.

 

Random access MAC protocol은 완전히 decentralized 되어 있으며, collision을 허용한다. 사용할 주파수를 얻기위한 눈치게임과 같다고 보면된다. 노드는 항상 채널의 최대 전송률로 프레임을 전송하고, collision이 생기면 각 node는 즉시 재전송하지 않고 collision이 없을때까지 random한 시간을 대기한 후 frame을 재전송한다.

Random access에는 pure ALOHA, slotted ALOHA, CSMA/CD, CSMA/CA 등이 있다.

pure ALOHA는 보내고 싶을 때 언제든지 보내는 방법이다. 당연히 collision이 자주 발생하고, throghput을 수학적으로 분석하면 최대 효율이 0.18임을 알 수 있다. collision이 발생하면 random한 시간동안 back-off(대기)한 후 retransmission한다.

slotted ALOHA는 시간을 slot으로 나눠 message를 time slot이 시작할때만 보낼 수 있게 했다. throughput을 수학적으로 분석하면 최대 효율이 0.36임을 알 수 있다.

 

CSMA/CD는 Carrier Sense Multiple Access with Collision Detection의 약자로, message를 보내기 전에 먼저 다른 node를 listen한 뒤 channel이 idle되면 보내는 방법이다. 이를 listen-before-talk이라 하며, wired link에서 사용된다.

이때 두개 이상의 channel이 sensing중이면 당연히 collision이 발생한다. collision이 발생할때마다 backoff를 두배씩 늘려 collision을 최소화하는데, 이를 binary exponential backoff라 한다.

collision을 방지하기 위한 3가지 방법이 있다.

- 1-persistent : channel이 idle되자마자 보낸다. - 단말이 2개 이상이면 collision이 발생하므로 쓰지 않는다.

- p-persistent : channel이 idle되면 p의 확률로 보낸다. 이때 propagation delay (tau) 동안 기다린 후 다시 시도한다.

- Non-persistent : random waiting 시간동안 대기한 후 sensing해서 channel이 idle하면 보내고, 아니면 다시 대기를 반복한다.

 

CSMA/CD에서 throughput을 올리려면, propagation delay(tau)가 transmission delay(m)보다 작아야 한다.

propagation delay는 패킷이 전송 시작할때부터 노드에 도착할때까지 걸리는 시간, transmission delay는 packet length에 비례하여 라우터가 패킷을 처음부터 끝까지 밀어내는데 걸리는 시간이다.

t<<m일 때 throughput 효율을 올릴 수 있다.(=비어있는 채널이 없도록 할 수 있다)

이때 worst case에서, propagation delay(tau)가 A가 전송을 시작한 후 B가 이를 sensing하기 직전에 데이터를 전송한다면, A는 또 propagation delay를 거친 이후에 collision을 알아차리게 된다. 

 

따라서 transmission delay와 propagation delay를 고려하면, delay는 아래와 같다.

 

이때 throughput을 최대화하기 위해, transmission time이 propagation delay보다 훨씬 커야 한다는 수식을 도출할 수 있다.

 

CSMA/CA는 Carrier Sense Multiple Access with Collision Avoidance의 약자다. wireless link에서 사용한다.

CSMA/CD가 아닌 CA를 사용하는 이유는 무선은 안테나의 특성상 데이터를 보내는 동시에 받을 수 없고, 전파의 strength가 원 겉넓이인 4pi*r^2에 반비례하기 때문에 거리가 멀어질수록 세기가 급속도로 줄고, 따라서 먼거리의 노드는 detection이 불가능하기 때문에 Collision Avoidance 방식을 사용한다.

CA는 random backoff 방식을 사용한다. 물론 불행하게도 두 노드가 같은 random을 가지면 collision이 발생하겠지만, random의 범위를 넓혀가는 방식으로 collision을 해결한다. CA에서 collision은 detection되지 않는다.

CA의 또다른 개념으로, collision avoidance를 위해 Interframe spacing을 사용하는데, 이는 급하게 보내야될 패킷(ex. ACK)을 위한 Short IFS와 일반적인 데이터용 DCF IFS를 나누어 중요한 패킷은 먼저 보낼 수 있도록 하는 것이다.

Backoff time은 contention window * slot time으로 정해지는데, [0, CW[i]-1]중 random하게 정해진다.

각 slot은 일반적으로 9us라고 하며, CW는 CWmin(e.g., 16)으로 시작해서 collision이 발생할때마다 최대 CWmax까지 double된다. packet이 성공적으로 전송되면 CW는 CWmin으로 reset된다.

CSMA/CA의 전체 과정은 아래와 같다.

 

 

Random access의 경우 사용하는 노드가 많을수록 효율이 떨어진다.