[네트워크] ALOHA protocol

데이터 링크 레이어의 Medium Access Control 중, Random Access protocol의 한 종류인 ALOHA에 대해 알아보자.

Random access protocol이란, 무작위성을 이용해 충돌을 방지하는 medium access control 방법이다.
ALOHA 프로토콜은 Random access protocol의 한 종류이다.

ALOHA

전송할 데이터가 생기면 곧바로 전송한다.
충돌이 발생하면, 랜덤한 시간 동안 기다렸다가 재전송한다.

Pure ALOHA

• 송신자는 전송할 프레임이 있다면 즉시 전송한다.

• 수신자가 프레임을 수신했다면, ACK를 전송한다.

• ACK가 timeout period 안에 도착하지 않았다면, 송신자는 랜덤한 시간동안 대기한 후 재전송한다.

• 두 프레임이 동시에 링크 위에 존재한다면, 충돌이 발생한다.

• timeout period = RTT + margin
• RTT (Round Trip Time) = (transmission time of frame & ACK) + (propagation time of frame & ACK) + (processing time)

• Time slot = transmission time $\text{T}_{\text{fr}}$ + propagation time $\text{T}_{\text{p}}$
• R (Random number) = $\text{rand}(0, 2^\text{k}-1)$
• k는 타임아웃이 발생할 때마다 1씩 증가한다.

• 타임아웃 안에 ACK가 도착하지 않으면, sender는 k를 1 증가시키고 T*R만큼의 시간을 기다리는 후 프레임을 재전송한다.

Vulnerable time

• 한 프레임이 전송되고 있을 때, 다른 프레임이 전송될 경우 충돌이 발생하는 기간을 말한다. (이 기간동안 조용해야 충돌이 발생하지 않는다)
• ALOHA의 vulnerable time : $2 \times \text{T}_\text{fr}$

Poisson distribution:

$\displaystyle p(k) = \frac{e^{-\lambda}\lambda^k}{k!}$

$G$: 한 $T_{fr}$ (transmission time) 동안 평균적으로 전송되는 프레임의 수

Vulnerable time $2\times T_{fr}$ 동안 평균적으로 전송되는 프레임의 수 = 2G

vulnerable time동안 아무도 전송하지 않을 확률:

$\displaystyle p(0) = \frac{e^{-2G}\lambda^0}{0!}=e^{-2G}$

Throughput $S$: 전체 프레임 중 성공적으로 전송되는 프레임의 비율

$S = G \times e ^{-2G}$

---

pure ALOHA 네트워크가 200-bit 프레임을 200kbps 채널에 전송한다.
시스템이 1초에 500프레임을 생성할 때, 몇 개의 프레임이 성공적으로 전송되는가?

$T_{fr}$ = (# bits) / (bandwidth(bps)) = 200 / 200k = 1/10^3 = 1ms

vulnerable time = 2ms

G = ($T_{fr}$=1ms 동안 전송되는 프레임 수) = 0.5

$S = 0.5 \times e^{-1} = 0.184$

1초에 $500 \times 0.184 = 92$개의 프레임이 성공적으로 전송된다.

---

Slotted Aloha

Vulnerable time: $T_{fr}$

Throughput
$S = G \times e ^{-G}$