The Poisson process is one of the most important random processes in probability theory. It is widely used to model random "points" in time and space, such as the times of radioactive emissions, the arrival times of customers at a service center, and the positions of flaws in a piece of material. Several important probability distributions arise naturally from the Poisson process--the Poisson distribution, the exponential distribution, and the gamma distribution. The process has a beautiful mathematical structure, and is used as a foundation for building a number of other, more complicated random processes.
* This is not a class material for commercial purpose. It's free for student.*
본 포스팅은 Pure Aloha를 먼저설명하고, Slotted Aloha를 유도한다.
1. ALOHA란?
Random access method의 한 방법으로 1970년대에 제안되었으며 여전히 셀룰러 시스템에서 그 Simplicity를 장점으로 사용된다. assumption
알로하(ALOHA)는 하와이 대학에서 개발되었으며 시분할 다중접속 기술을 사용해 위성과 지구 사이의 무선 전송을 하는 프로토콜이다. 원래의 알로하에서 사용자는 언제든지 전송할 수 있지만, 다른 사용자들의 메시지는 충돌할 위험이 있다. 패킷이 준비되면 브로드캐스트되며, 만약 충돌이 일어나면 일정시간 후에 재전송된다. Slotted Aloha는 채널을 시간대별로 나누어서 충돌 위험을 줄이는 것으로, 각 사용자는 시간대의 시작에서만 전송이 가능하다.
2. Basic working
- 노드는 데이터 전송을 언제든지 할수있고 ACK를 받는다
- 만약 하나의 Frame 이상이 같은 시간에 전송된다면, 그들은 서로 간섭을 겪기때문에 충돌하거나 패킷을 잃어버린다.
(Collision or Lost)
- 만약 ACK 패킷이 지정된 시간안에 도착하지 않으면 Timeout이 발생하고 전송을 한 노도는 Backoff time만큼 기다린후
다시 전송을 시도한다.
2-2. Vulnerable period
- Frame의 길이 (전송할 패킷의 사이즈)를 L이라고 둔다면, L 길이 패킷을 전송하는 소요시간은 X = L/R (data rate)이 됨.
- consider a frame with starting transmission time to the frame will be successfully transmitted if no other frame
collides with it.
-> any transmission that begins in interval [t0, t0+X], or in the prior X seconds leads to collision
vulnerable period = [ t0 – X, t0+ X ]
위의 그림은 Unslotted Aloha의 취약구간을 보여준다. L길이 만큼의 패킷이 전송될 동안 앞뒤로 2L길이만큼 다른 노드들의 전송시도가 없어야만 성공적인 전송이 가능하다.
3. Throughput =(def. Number of packets per unit time)
1) Successful throughput : X시간(unit time) 동안의 성공적인 Frame 전송의 평균값을 의미한다.
2) G-load : X시간 동안의 평균적인 전송시도를 의미한다.
(큰 개념은 굵은 제목들만 봐도 충분히 이해가 된다. 하지만 이를 직접 Code로 구현하기 위해서는 아래의 확률과정에 대해서 충분히 이해해야 한다. G의 개념과 Qa, Qr의 개념만 안다면 코딩가능하다. 필요없는 분은 바로 3)으로 가세요)
"G" refer to the mean used in the Poisson distribution over transmission-attempts that is, on average, there are G transmission-attempts per frame-time in state n.
State (n) of system is number of backlogged nodes.
If a transmission has a collision, node becomes backlogged
– While backlogged, transmit in each slot with probability qr until successful.
Infinite nodes where each arriving packet arrives at a new node
– Equivalent to no buffering at a node (queue size = 1)
– Pessimistic assumption gives a lower bound on Aloha performance
G(n) = λ + n*Qr
( Qr : re-transmission probability of backlogged stations. )
The number of attempted packets per slot in state n is approximately a Poisson random variable of mean g(n)
– P (m attempts) = {(G(n)^k)*exp^-G(n)}/m!
– P (idle) = probability of no attempts in a slot = exp^-G(n)
– p (success) = probability of one attempt in a slot = G(n)*exp^-G(n)
: idel한 채널상태에서 혼자서 전송을 시도하는 경우 = 성공확률.
– P (collision) = P (two or more attempts) = 1 - P(idle) - P(success)
For any frame-time, the probability of there being k transmission-attempts during that frame-time is:
{(G^k)*e^(-G)} / k!
If throughput is represented by S, under all load, S = G*Ps, where Ps is the probability that the frame does not suffer collision. A frame does not have collision if no frame are send during the frame time. Thus, in t time Ps=exp^-G.
In pure Aloha, Ps=exp^(-2G), as mean number of frames generated in 2t is 2G. From the above, throughput in pure Aloha S = G*exp^-2G.
*혼잣말: G= a node transmission-attempts , k= k nodes라면.. 2)과 3)의 설명에서 G와 k의 연결고리가 없는 느낌인데..
3) Successful Probability (Ps): 성공적인 Frame전송의 확률
따라서 Successful throughput = Ps * G-load.가 된다.
if general, if frame arrivals are equally likely at any instant in time, and arrivals occur at an average rate of λ [arrivals per sec]
포아송 프로세스를 따라서 동일 프레임들K개가 T시간동안에 도착한다고 가정한다면, 위의 식으로 표현된다.
in our case, λ=G/X [arrivals per second] and T=2X, hence
그러나 앞서 이야기했듯이 Pure Aloha는 프레임길이의 2배동안 다른 노드들의 프레임전송이 없어야 충돌이 없기 때문에 전송이 성공하기 위한 조건들을 대입하면 아래와 같이 다시 쓸수가 있다.
accordingly, probability of successful transmission (no collision) is:
이를 푸아송 프로세스의 성질을 이용하여, 어떠한 전송이 없을 확률을 구하면 = 다른 노드들이 모두 전송하지 않을 확률 = 성공확률을 의미한다.
따라서 Throughput 은 평균적인 전송시도량 * 패킷전송 성공확률로 표현이 된다.
4. Slotted Aloha
Slotted Aloha는 pure Aloha보다 향상된 성능을 가지는데, 이는 충돌량이 감소했기 때문이다.
1) Assumption
- 각각의 슬롯사이즈들은 X=L/R 의 크기로 나눠어 진다. (하나의 프레임전송에 맞는 시간)
- 노드들은 전송을 슬롯의 시작부분에만 시작한다.
- 노드들은 동기화를 통해서 슬롯의 시작을 알고있다고 가정한다.
2) Operation
(1) when node has a fresh frame to send, it waits until next frame slot and transmits
(2) if there is a collision, node retransmits the frame after a backoff-time
(backoff-time = multiples of time-frames)
위의 그림을 보면 왜 Slotted Aloha가 더 좋은 성능을 가지는지 알수있다. 사실 직관적으로 2배정도의 성능을 보일것이라고 생각이 든다.
3) Throughput
packet P will be transmitted successfully if no other packet becomes available for transmission during the same time slot. Pure Aloha에서 전송시 Vulnerable period가 패킷사이즈(L)의 2배시간동안 다른 노드들의 전송이 있다면 충돌이 발생한다고 했다면, Slotted Aloha의 경우는 Packet Size의 길이만큼만 충돌이 없도록 보장이 되기에 2배의 성능을 보인다.
vulnerable period = [ t0 – X, t0 ]
따라서, Slotted ALOHA와 Pure Aloha 의 성능을 비교해보면 아래와 같다.
Slotted ALOHA의 MAX Throughput 은 G=1일때 0.36을 보인다.
따라서 실질적인 Channel capacity는 36%이다. (legend가 반대로 들어갔습니다. 붉은색 = pure, 파란색이 slotted 입니다. 참고하시길 바랍니다.)
it's a packet stuck in a buffer, unsent to the recipient because of network congestion. You probably don't see the word much in computer networking because it is used in cellular phone networks. In voice networks, where delivery is time sensitive but dropped packets can be tolerated, a backlogged packet is usually dropped.
네트워크분야에서는, 네트워크의 혼잡으로 (CSMA/CA에서 예를들면, 채널이 busy하거나, 패킷간 충돌이 발생했을때) 인하여 전송하려고 하던 패킷을 버퍼에 넣어두고 기다릴 때 전송지연되는 패킷을 말한다.
ex)
In slotted Aloha, If a transmission has a collision, the node become backlogged.
