1. ALOHA Protocol이란?
ALOHA는 Additive Links On-line Hawaii Area의 준말입니다.
1970년대 하와이 대학교에서 개발한 컴퓨터 네트워킹 시스템입니다.
여러 섬에 분산된 컴퓨터 간 무선 통신으로 데이터를 교환할 때 사용하는 프로토콜입니다.
이때 확률과 통계를 이용해서 ALOHA Protocol의 성능을 측정해보겠습니다.
2. ALOHA Protocol의 원리
기존의 복잡한 통신 시스템에 비해 다른 기본적인 가정이 있습니다.
- 시간이 정해져 있지 않음
- 패킷은 즉시 도착한다
- 별도의 채널이나 동일한 채널에서 ACK를 기다림 (정상 도착했다는 신호)
- 만약 충돌이 일어나면 Time-Out 혹은 NAK 신호를 받음
- 충돌이 일어난다면 재전송
단순한 구조입니다. 패킷이 생성되면 즉시 보내고, 만약 수신 측에서 제대로 받았다는 신호를 보내면 그대로 끝
제대로 받았다는 신호가 오지 않았다면 다시 재전송하는 시스템입니다.
매우 간단하지만, 유저가 증가할수록 충돌도 증가해서 낮은 채널 통신량을 가집니다.
이때 Vulnerable Period(v_p), 취약 구간이 있는데,
취약 구간은 특정 패킷이 성공적으로 보내기 위해서 다른 패킷의 시작이 들어오면 안 되는 구간이 됩니다.
예를 들어 하나의 패킷 전송 타임이 T라고 가정한다면, 특정 패킷이 전송되기 이전의 T구간과 패킷이 전송되는 T 구간은 다른 패킷이 생성되면 안 됩니다.
만약 다른 패킷이 생성된다면 충돌이 발생합니다.
따라서 Vulnerable period는 2T가 됩니다.
3. ALOHA의 Performance
- \(\lambda\)는 패킷이 생성되는 평균 개수입니다.
- 이때 패킷은 Poisson process에 의해 도착합니다.
- 이때 새롭게 생성(\(\lambda\))되거나 재전송(\(\alpha\)) 되는 패킷은 G이고, 이 값은 \(\lambda\)보다 크거나 같습니다.
- S : Average number of successful transmissions
- 성공적으로 전송되는 패킷의 평균 개수
- G : Average number of packet transmissions attempted
- 평균적으로 시도되는 패킷 전송 횟수 (이때 본 유저 말고 나머지 유저의 패킷 전송 횟수이다)
- G/T > 1 : More than one packet/slot may attempt a transmission -> 전송 실패
- G/T < 1 : SOme slots are idle
- \(\gamma\) : probability of successful transmission
- 통신 성공의 확률
- 이 확률은 velnerable period 2T 동안 no additional packets are generated 될 확률과 같다.
즉 S = \(\gamma\)G와 같습니다.
따라서 k개의 패킷이 시간 t동안 시도하는 확률 (성공 확률 아님)을 Poisson distribution을 통해 나타내면,
P[k packets in time t] = \(\frac{(\lambda t)^k}{k!}e^{-(\lambda t)} = \frac{(Gt / T)^k}{k!}e^{-(Gt/T)}\)이 됩니다.
(참고로 G/T는 채널에 평균적으로 시도하는 패킷 개수)
또한 성공적으로 전송할 확률은 vulnerable period 2T동안 아무런 패킷이 생성되지 않을 확률과 같으니, 다음과 같습니다.
\(\gamma\) = P[no packet during 2T] = \(\frac{(Gt/T)^k}{k!}e^{-(G/T)t}, t = 2T, k = 0\Rightarrow e^{-2G}\)
따라서 S = \(\gamma\)G = \(Ge^{-2G}\)와 같습니다.
(Average number of attempts per slot(G) * Probability of successful transmission (\(\gamma\)))
따라서 Maximum Throughput (T 시간 동안 패킷을 평균적으로 G번 시도할 때, 성공 통신량)은 아래와 같습니다.
\(\frac{\mathrm{d} S}{\mathrm{d} G}= e^{-2G}-2Ge^{-2G} = 0 \Rightarrow G = \frac{1}{2} \Rightarrow S_{max}=\frac{1}{2e}=0.184\)
즉 본유저를 제외하고 나머지 유저들이 0.5개의 패킷을 보내야 최대 통신량에 도달하는데, 최대 통신량 또한 0.184밖에 되지 않습니다.
즉 나머지 0.816 시간은 허비한다는 뜻입니다.
또한 이후에는 쭉 떨어지는 모습을 볼 수 있는데, 사실 0.5라는 수준을 넘어서면 다시 회복이 불가능합니다.
왜냐하면 이후에는 새롭게 생성 + 재전송 시도가 너무 많아서 다시 call back 하기가 힘들어지죠
따라서 기존의 ALOHA Protocol이 너무 성능이 안 좋아서 나온 것이 바로 Slotted ALOHA Protocol입니다.
아무튼 여기서 ALOHA Protocol의 전송 시간에 대해서 알아보겠습니다.
4. Delay of ALOHA
(이때 일반화를 위해 T가 없는 식으로 표현합니다. T에 대해 표현하려면 모든 수식에 T를 곱하면 됩니다.)
기본적인 식은 (Average number of retransmissions)*(Time between retransmission packets) + (Time to success to transmission), (평균 재전송 횟수) * (재전송까지의 딜레이) + (성공할 때의 시간)이 됩니다.
먼저 평균 재전송 횟수를 구해봅시다!
4.1 Average number of retransmissions
혹시 geometric distribution 기억하시나요?
매 도전마다 성공 확률이 있고, n번째에 성공할 확률을 나타내는 확률 분포입니다.
이때 n번째 시도에 전송에 성공한다고 가정한다면, n - 1번까지는 모두 전송에 실패하고, n번째에만 전송에 성공해야 합니다.
n번째 전송에 성공할 확률을 \((P_s)_n\)이라고 가정합시다.
따라서 \((P_s)_n = (1 - \gamma)^{n- 1} * \gamma\)이 됩니다.
이때 평균 전송 횟수를 계산합시다.
시도는 한 번부터 무한대까지 할 수 있으므로, 식을 세워보면,
\(E[N] = \sum_{n = 1}^{\infty} n(1-\gamma)^{n-1} * \gamma = \frac{1}{\gamma} = e^{2G}\)이 나옵니다.
참고로 \(\gamma\)는 우리가 위에서 \(e^{-2G}\)라고 구해놨었습니다.
자 우리는 성공할 때까지의 평균 전송 횟수에 대해 구했습니다.
이제 평균 재전송 횟수에 대해 알아야 하는데, 평균 전송 횟수에 1을 빼면 아주 간단하게 구할 수 있죠?
마지막 시도가 전송된 거니까요....
따라서 Average number of retransmissons \(E[N_r]=E[N]=e^{2G} - 1\) 이 됩니다!
그럼 이제 한 번 재전송할 때 걸리는 시간에 대해 알아봅시다.
4.2 Time between retransmisson packets
우선 정상적으로 패킷이 송수신될 때의 시간을 계산합니다.
패킷이 생성 및 송신 -> 패킷이 수신 -> ACK 신호 생성 및 송신-> ACK 신호 수신
이때 패킷이 송신되는 시간을 \(\alpha\)라 하고, ACK가 생성되는 시간을 \(\beta\)라고 합시다.
패킷을 송신한 측은 T + 2\(\alpha\)T + \(\beta\)T 동안 기다려야 ACK 신호를 정상적으로 수신할 수 있습니다.
이때 \(\alpha\)가 두 개인 이유는 패킷이 이동하는 시간 + ACK가 이동하는 시간입니다.
하지만 이제 여기서 패킷이 정상적으로 수신되지 않거나, ACK 신호를 수신하지 못할 때의 시간을 봅시다.
어찌 됐던 패킷을 송신하는 쪽은 다시 보내야 합니다.
이때 위의 시간을 기다렸음에도 불구하고 ACK 신호를 받지 못했다면 재전송해야 합니다.
얼마큼 기다려야 할까요?
두 개의 패킷이 충돌돼서 재전송해야 하는 상황이라 가정합니다.
이때 바로 재전송하는 상황이라면 또 충돌합니다.
따라서 T의 배수 시간만큼 랜덤으로 기다려서 재전송해야 합니다.
그러므로 랜덤으로 기다리는 시간을 E [B]라고 합시다.
따라서 E [R] (패킷을 재전송하기 위한 시간) = \(1 + 2\alpha + \beta\) + E[B]입니다.
(T는 normalized하기 위해 없앴음)
이때 랜덤으로 기다리는 시간의 평균을 구해봅시다.
back-off라고 하며, 0~k-1까지 랜덤 하게 정한 후, (0 ~ k - 1)T만큼 기다립니다.
\(E[B] = \sum_{i = 0}^{K-1}i * \frac{1}{K} = \frac{K(K-1)}{2}*\frac{1}{K} = \frac{K-1}{2}\)이 됩니다.
4.3 Conclusion
위에서 기본 식을 다시 가져오겠습니다.
기본적인 식은 (Average number of retransmissions)*(Time between retransmission packets) + (Time to success to transmission), (평균 재전송 횟수) * (재전송까지의 딜레이) + (성공할 때의 시간)이 됩니다.
ALOHA Protocol의 평균 전송 시간을 E[D]라 합시다.
즉, E[D] = E[\(N_r\)] * E[R] * 1 + \(\alpha\)이 됩니다. (1 + \(alpha\)는 성공할 때의 시간)
우리가 다 위에서 구한 식이죠?
\(E[D] = (e^{2G} - 1)(1 + 2\alpha + \beta + \frac{K-1}{2}) + 1 + \alpha\)이 됩니다.
결론은 ALOHA에서 성공 확률은 Poisson Distribution에 의하여 \(\gamma = e^{-2G}\)가 되고, 이를 이용하여 한 번 전송할 때 걸리는 Delay time은 위의 E[D]와 같습니다.
감사합니다.
지적 환영합니다.