Multiple access links, protocols

links에는 두 가지 타입이 존재한다.
point-to-point와 broadcast(shared wire or medium)이 있다.

위와 같은 구조는 모두 한 링크를 여러 장치가 공유해서 사용하고 있다.
이 때, 한 링크에 여러 신호를 동시에 전송하게 되면 신호 간에 간섭이 발생하게 된다. 이를 collision 이라고 한다.

Multiple access protocol은 노드가 채널을 어떻게 나눠서 가질지 결정하는 방법이다. 즉, 언제 노드가 전송할 지 결정하는 알고리즘이다.

MAC(Multiple Access Channel) protocol

MAC 프로토콜은 공유 채널에 다수의 사용자가 접속할 수 있도록 하는 프로토콜이다.

세 가지의 방법이 있는데 다음과 같다.

Channel Partitioning

채널을 여러 개의 조각으로 나누는 것을 의미하고, 한 사용자에게 각 조각을 할당하여 사용할 수 있게 한다.
나누느 기준은 여러 개가 있지만 보통은 TDMA와 FDMA가 있다.

TDMA

TDMA는 Time Division Mulitple Access의 약자로 말 그대로 시간을 나누는 것이다.
각 노드별로 채널을 사용할 수 있는 시간을 할당해주는 방식을 의미한다.

각 노드는 본인의 차례에 보낼 데이터가 없을 수도 있다. 그런데 그 때 본인의 시간대라면 비효율이 발생할 수 있다.

위의 그림은 6개의 노드가 존재할 때 전체 채널을 6분할하여 분배한 것이고, 6개의 노드 중 1, 3, 4 노드만 활성화되어 전체 시간의 절반만 사용되고 있다.

FDMA

FDMA는 Frequency Division Multiple Access의 약자로 주파수를 나누는 방식이다.
주파수 대역을 나누면 동시에 여러 노드가 채널을 사용해도 간섭이 발생하지 않는다.

존재하는 노드의 개수만큼 주파수 대역을 나누어 각 노드에게 할당해 주면, 각 노드는 할당받은 주파수 대역을 언제든지 사용할 수 있다.

TDMA와 마찬가지로, 다른 노드가 채널을 사용하고 있지 않을 때에도 한 노드가 추가적인 주파수 대역을 할당받을 수 없으므로 성능적 측면에서 비효율이 발생한다.

Random Access Protocol

모든 노드가 동등하며, 각 노드들 간의 우선순위 등이 정의되어 있지 않아 어떤 노드가 언제 신호를 보내는지 알 수 없다. 만약 둘 이상의 사용자가 서로 겹치게 되면 collision이 발생한다.

collision이 발생할 수 밖에 없는 방식이니만큼 collision을 탐지하고 이를 recover하는 과정이 중요하다. 이 과정은 프로토콜마다 다르게 구현된다.

Slotted ALOHA

나중에 나올 Pure ALOHA 방식을 time slot 단위로 나누는 정책을 도입함으로써 개선한 방식이다.

• 시간을 동일한 time slot 으로 나눈다.
• 노드들은 slot 단위로만 신호를 보내려고 시도한다.
• 노드들은 동기화되어 slot의 시작점을 알고 있다.
• 둘 이상의 노드가 같은 slot에 신호를 보내면, 모든 노드는 collision을 감지한다.
• 만약 collision이 발생하였다면, 성공할 때까지 재전송한다.

아까 Slotted ALOHA는 Pure ALOHA 방식을 개선한 방식이라고 했는데, 두 배 가량 개선한 37%의 efficiency를 가진다.

Pure ALOHA

• 전송할 프레임이 생기면 바로 전송한다.
• 다른 프레임과 겹치게 되면 collision이 발생한다.

위 그림에서 t0에 보내진 노란색 프레임은 초록색, 보라색 프레임과 겹쳐 collision이 발생했다.

다른 노드 간의 동기화 작업이나 기다리는 과정 등이 없기 때문에 당연히 collision 발생 빈도가 높고, 그만큼 버려지는 시간이 길어지기 때문에 성능이 좋지 않다.

Pure ALOHA 방식은 18%의 efficiency를 가진다고 알려져 있다.

CSMA

CSMA는 carrier-sense multiple access의 약자이다.
근거리 전산망에서 지국이 데이터의 전송시기를 결정하는 방법의 하나이다.
전송을 하기 전에 지국은 반송신호의 유무 확인을 통해 네트워크의 상태를 점검한다.

내가 데이터를 보내기 전에 채널 상에 데이터를 보내고 있는 노드가 있는지 확인 후 보낸다.
채널 상에 나타나는 신호를 carrier 라고 하고 이를 통해 채널 상에 신호가 존재하는지를 감지하는 것을 carrier sense 라고 한다.

CSMA는 collision의 가능성을 줄일 수는 있지만, 완전히 방지할 수는 없다.

CSMA/CD

CSMA with Collision Detection이다.

채널 상에 collision이 발생하는지 탐지한 이후 resolution 작업을 수행하는 방식이다.

프레임을 전송 함과 동시에 두 개의 다른 포트를 이용하여 충돌이 발생하는지 감시한다. 프레임이 목적지에 도착할 시간 이전에 다른 프레임과 비트가 발견되면 충돌이 일어난 것으로 판단한다. 만약 collision이 발생했다면 회선 모두에 jam signal을 보내어 충돌 사실을 알린다. 그리고 binary exponential backoff 과정을 수행한다.

binary exponential backoff란 m번째 충돌 때 {0, 1, 2, ..., 2^m - 1} 숫자 중 하나 K를 선택하여 K*512 bit time 만큼 기다렸다가 다시 transmission을 시작하는 방법이다.
충돌이 많이 발생할수록 backoff interval이 길어지지만 그만큼 충돌이 발생할 확률이 줄어든다.

CSMA/CD의 기본 아이디어는 지국이 충돌을 감지하기 위해서는 신호를 전송하는 동시에 신호를 받을 필요가 있다는 것이다.

충돌이 없으면 지국은 자신이 보낸 신호만을 받게 된다. 하지만 충돌이 생기면 지국은 자신의 신호와 다른 지국이 보낸 신호인 두 개의 신호를 받게 된다.

"Taking turns" MAC protocols

일정한 규칙을 가지고 차례를 지정하여 채널을 이용한다.

polling

마스터 노드와 슬레이브 노드가 있으며 마스터 노드가 순서를 지정해준다.

구현이 간단하고 충돌이 발생하지 않으며 낭비가 되는 채널이 없다는 장점이 있다.
그러나 순서를 지정하는 알고리즘의 오버헤드가 발생하고, 마스터 노드가 다운되면 전체 시스템이 다운되는 문제점이 존재한다.

Token passing

각 노드들이 토큰을 서로 주고 받는다. 현재 토큰을 가지고 있는 노드가 데이터를 전송할 수 있다.

토큰을 관리함에 있어 고려할 사항이 많아 구현이 어렵고, 내가 데이터를 보내야 함에도 다른 노드들을 거쳐 토큰이 다시 나에게 돌아올 때까지 기다려야 하는 latency가 발생한다는 점이 있다.