Multiple access protocols

Multiple Access Protocols

- 때는 바야흐로 무선 인터넷의 시대, 개나 소나 NIC를 들고 다니는 시대가 되었다. 그러나 꿈만 같은 무선 인터넷에도 희대의 문제가 있었으니, 바로 한 Channel에 여러대의 디바이스가 접근해야 하는 경우가 생긴 것이다.

- 두개나 그 이상의 노드에서 동시에 전송하게 되면 이는 Collision이라고 칭해진다.

- 이에 노드들이 어떻게 채널들을 북치고 장구치게 분배할지 결정할 필요가 생겼고, 분산적으로 작동하는 알고리즘인 MAP가 탄생하게 되었다. (다만 채널을 나누는 통신은 그 채널 자체에서 해결해야만 한다.)

 

MAC Protocol에는 Channel Partitioning, Random access, Taking turns가 존재한다.

- Channel Partitioning 방식의 경우 TDMA, FDMA 방식이 존재한다. 이중 TDMA는 시간을 슬롯으로 쪼개서 패킷을 보낼 때 뺑뺑이(?)를 돌리는 방식이다.

- 다만 Collision의 발생 우려가 있다.

- FDMA 방식은 채널을 주파수 대역으로 나눠서 각각의 밴드를 분배하는 방식으로 사용된다. 특징적으로는 Collision이 발생할 일이 존재하지 않으나, Burst한 트래픽이 몰려온다면 감당하기 힘들어 질 수 있다.

 

- Random Access Protocols은 한마디로 요약하자면, 진짜로 확률적인 개념으로 특정 패킷을 보낼 지 말지 결정하는 (Random) 모시깽이인 셈이다. 아래 ALOHA/slooted ALOHA의 예시를 들어 이해해 보자.

 

- Slotted ALOHA의 가정 및 작동 방식은 아래와 같다.

- 먼저 모든 프레임은 같은 크기를 가지고 있다고 가정하고, 시간은 일정한 슬롯으로 쪼개진다. 각각의 노드들은 동기화 되어 있다고 할때, 만약 Collision이 없으면 노드는 다음 프레임을 다음 차례의 슬롯에 던진다. 하지만 Collision이 존재하게 된다면 node는 p의 확률로 다음 프레임을 다음 차례의 슬롯에 던진다.

- 이는 싱글 노드가 채널의 가용대역을 모두 사용해서 전송할 수 있고, 간단하다는 장점이 존재하나 그림에서 볼 수 있듯이 idle slot과 collision으로 인한 wasting slot으로 인한 낭비가 존재한다. 더불어 clock 동기화를 해야하며, 노드가 delay로 인해 collision을 감지하지 못하고 그냥 던져버리는 경우가 발생할 수 있다. (후술할 CDMA에서도 같은 문제가 있음)

 

- 문득 보면 비효율적인 방식이라고 생각 될 수 있지만, 최대 효율이 37%정도 되는 녀석이다. Pure ALOHA의 18%에 비하면 상당히 양호한 수치라고 할 수 있다.

 

Pure ALOHA는 Synchronization 그딴거 없다!

- 그 다음으로 등장하는 것은 CSMA. 뭔가 복잡해 보이지만, 사실 슬라이드에서도 써져 있듯이 만약 Device가 채널이 바쁜 것을 감지하면 패킷을 보내지 않고 아니면 그냥 던져버리는 단순한 방식이다. 

- 다만 문제는 CSMA가 작동하기 뭐 한 상황이 발생하는데, Propagation Delay로 인해서 채널이 텅 빈줄 알고 패킷을 보내버렸다가 Collision이 발생하는 경우가 아주아주아주아주아주 심하게 발생한다. 

 

- 이에 CSMA/CD가 탄생하였으니, 쉽게 말해서 패킷을 던지다가 Collision이 일어난 것 같다 싶으면 Collision을 일으킨 Device가 패킷 전송을 멈추는 것이다. 이 얼마나 아름다운 방식인가? (다만 Wireless에서는 Collision Detection이 상당히 어려운 일이고, 이에 Wireless 환경을 위한 CSMA/CA라는 방식이 존재하며 차후 다룰 예정이다.)

- 그래서 정리하자면, CSMA/CD의 알고리즘은 다음과 같다.

- 먼저 NIC가 채널을 감지했을때 텅 비었다 싶으면(느끼기에) 프레임 전송을 시작한다. 이때 전송중 만약 NIC가 Collision을 감지하게 된다면, Abort 하게 된다. 그리고 나서는 Binary Backoff 시간을 가지게 된다. (Binary Backoff Interval: 0, 1, 2, ... 2^m 중 숫자를 하나 골라서 K*512 bit의 시간 만큼 기다리는것) 그리고는 Collision이 사라지면 다시 NIC가 채널의 유휴 유무를 판단하게 된다. (만약 Collision이 계속 발생한다면 Backoff Interval이 늘어난다.)

 

 

- 마지막으로 살펴 볼 것은 Taking Turns 방식이다. 이를 비유적으로 설명하자면은, 통신계의 통표 폐식 방식이라고 하면 철덕들은 한번에 알아들을 수 있을 것이다. 아래 2가지 방식을 살펴보면서 이해해 보자.

 

- Polling 방식의 Taking Turns MAC Protocol은 다음과 같이 동작한다. 중앙에 Controller가 하나 있고, 그 Controller가 어떤 Node가 해당 차례에 데이터를 보낼지 결정한다. (그래서 대게 "멍청한" 디바이스들의 모임에서 쓰인다.)

- 다만 이경우 컨트롤러가 사망하면 다같이 사망하는 문제점 (Single Point of Failure)가 존재하며 컨트롤 시간으로 인한 래이턴시의 존재 또한 문제가 된다.

 

- Token Passing 방식의 Taking Turns Protocol은 진짜 말그대로 통표 폐식 방식이다. 토큰을 만든 다음에 해당 토큰을 가진 Client만이 패킷을 보낼 수 있고, 보내고 나면 순서에 따라서 토큰을 다른 클라이언트에 던지게 된다.

- 물론 token 사망에 따른 sigle point of failure의 위험성은 여전히 존재한다.

 

그리고 위에서 배운 것들은 현재 이렇게 쓰이고 있다.

 

 

---

Ref : Computer Networking - A top down approach