//--------------------------------------------------
4.1 introduction.
different types of networks.
//--------------------------------------------------
4.2 slotted multiaccess and the aloha system.
Idealized slotted multiaccess model assumptions:
1. slotted system
2. Poisson arrival
3. collision or perfect reception.
4. 0, 1, e immediate feedback.
5. retransmission of collisions.
6a. no buffering, lower bound for delay, no queuing time.
6b. infinite nodes. gives upper bound for delay, because packets were in the same queue can interfere with each other, causing collision.
Slotted aloha with 6a assumption.
m nodes, n backlogged,
$q_a$ arrival transmission probability for each unbacklogged node.
$q_r$ retransmission probability for each backlogged node.
using drift method:
$$
D_n = (m-n) q_a - P_{success} \\
P_{success} \approx G(n) e^{G(n)} \\
G(n) = (m-n) q_a + n q_r
$$
$$
D_n = (m-n) q_a - P_{success} \\
P_{success} \approx G(n) e^{G(n)} \\
G(n) = (m-n) q_a + n q_r
$$
using the approximation $(1-x)^y \approx e^{-xy}$ when x is small.
G(n) is the attempted transmission in one slot, when there is n backlogged nodes.
The only case of interest is $q_r > q_a$. When $q_r$ is small enough for stability, it can be shown that the delay exceeds TDM.
assume the attempted transmissions in one slot is Poisson(G(n)),
The optimal throughput is obtained at $G(n) = 1 \rightarrow P_{success} = 1/e$, $P_{idle} = P(Poisson(G(n)) = 0) = e^{-G(n) } = 1/e$,
therefore $P(collision ) = 1- 2/e$
instead of 6a, for 6b, $G(n) = \lambda + n q_r$, the arrive straight line becomes horizontal $\lambda$
meaning:
$$
D_n = \lambda - P_{success}
$$
the undesirable stable point disappeared, but once n passes the unstable equilibrium, n tends to increase without bound, thus the throughput becomes 0.
Define statbility:
infinite node(6b), the system is stable for a given arrival rate if the expected delay is finite.
aloha is unstable.
G(n) is the attempted transmission in one slot, when there is n backlogged nodes.
The only case of interest is $q_r > q_a$. When $q_r$ is small enough for stability, it can be shown that the delay exceeds TDM.
assume the attempted transmissions in one slot is Poisson(G(n)),
The optimal throughput is obtained at $G(n) = 1 \rightarrow P_{success} = 1/e$, $P_{idle} = P(Poisson(G(n)) = 0) = e^{-G(n) } = 1/e$,
therefore $P(collision ) = 1- 2/e$
instead of 6a, for 6b, $G(n) = \lambda + n q_r$, the arrive straight line becomes horizontal $\lambda$
meaning:
$$
D_n = \lambda - P_{success}
$$
the undesirable stable point disappeared, but once n passes the unstable equilibrium, n tends to increase without bound, thus the throughput becomes 0.
Define statbility:
infinite node(6b), the system is stable for a given arrival rate if the expected delay is finite.
aloha is unstable.
//--------------------------------------------------
4.3 splitting algorithm
resolve the collision before move on, fully exploit the feedback information.
example:
2 node collision, CRP = E[Geo(1/2)] + 1 = 3.
two improvement:
1. automatically split after (e,0,), avoid a w.p.1 collision.
2. discard the R half after (e,e,).
Proof: after the first e, split to $l,r$.
$$
P(r | l>1, l+r >1) = P(r | l>1) = P(r)
$$
which is the same as the untested.
FCFS splitting algorithm.
resolve the collision before move on, fully exploit the feedback information.
example:
2 node collision, CRP = E[Geo(1/2)] + 1 = 3.
two improvement:
1. automatically split after (e,0,), avoid a w.p.1 collision.
2. discard the R half after (e,e,).
Proof: after the first e, split to $l,r$.
$$
P(r | l>1, l+r >1) = P(r | l>1) = P(r)
$$
which is the same as the untested.
FCFS splitting algorithm.
//--------------------------------------------------end
No comments:
Post a Comment