Wireless Communications II Lecture 2 Notes PDF

Wireless Communications II - Fall 2024 - Lecture 2 In the last Lecture Pure ALOHA: Transmit at will and repeat iff no acknowledgement returns. The load of independent users is Poisson....

Wireless Communications II - Fall 2024 - Lecture 2 In the last Lecture Pure ALOHA: Transmit at will and repeat iff no acknowledgement returns. The load of independent users is Poisson. The packet inter-arrival time is Exponential. The distribution of packets (in time) is Uniform (Homework). Throughput < 20% (Assumptions: asymptotic users, ergodic load without backlogging) Asymptotic Aggregate Throughput of ALOHA 0.2 0.18 0.16 0.14 Aggregate Throughput: ρ(L) 0.12 0.1 0.08 0.06 0.04 0.02 0 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 Average Load: L Figure 1: Asymptotic aggregate throughput of ALOHA as a function of the average packet load. 1  Maximally Entropic Distributions: With limited support and no prior information is Uniform. With real support and first and second moments is Gaussian. With positive real support and first moments is Exponential (Homework). 2 Slotted ALOHA The protocol is the same as ALOHA, but users are synchronized. In a slotted system all packets have the same length, so that time can be counted by integer numbers. Asymptotic Aggregate Throughput: The immediate consequence of user synchronization, a.k.a. slotting, is that packets are only sub- ject to collision within the slot. In other words, the vulnerable time is equal to the packet duration, i.e. λ0 = λ. Thus Pr{Packet is collision-free} = P (0; λ) = e−λ (1) It follows straightforwardly that the asymptotic aggregate throughput of Slotted ALOHA is ρ(L) = Le−L (2) Consequently, the optimum load and its corresponding maximum throughput are 1 L∗ = 1 =⇒ ρ(L∗ ) = ≈ 0.3679 (3) e Synchronizing users results in a (possible) 2-fold throughput gain. Asymptotic Aggregate Throughputs of Slotted and Pure ALOHA 0.4 Asynchronous ALOHA Slotted ALOHA 0.35 0.3 Aggregate Throughput: ρ(L) 0.25 0.2 0.15 0.1 0.05 0 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 Average Load: L Figure 2: Asymptotic aggregate throughputs of pure and slotted ALOHA as a function of the average load. 3  Limitation of Asymptotic Analysis: The consequence of the asymptotic assumption on the accuracy of the analysis above should not be ignored and can be illustrated by plots of the individual throughput, which from equation ρ(L) = L × Pr{Packet is collision-free} = Le−L (4) is found to be ρ(p; N ) = pe−N p (5) Figure 3 shows a plot of the individual throughput, scaled by the number of users, as a function of the packet transmission probability p. It can be seen that according to the asymptotic result, the efficiency of the ALOHA MAC with a single user, i.e., N = 1, is still 1/e, which is obviously inconsistent. Scaled Individual Throughput of Slotted ALOHA 0.4 0.35 0.3 Individual Throughput: ρ(p; N ) 0.25 0.2 0.15 0.1 N =1 0.05 N =2 N =5 N = 10 0 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Transmission Probability: p Figure 3: Scaled individual throughput of slotted ALOHA as a function of the packet transmission probability. Limitation of Ignoring Backlogging Besides the aforementioned asymptotic limitation (which is hard to improve upon), the throughput result so far lacks in accuracy as it ignores the fact that collided packets are subsequently retransmitted, which implies that the transmission probability is not independent from the throughput. In order to incorporate backlogging into the analysis, we require a new tool: Queueing Theory 4  Markov Chains and Basic Queueing Theory The process of “servicing” packets with random arrivals that converge onto a single server exemplified in the Slotted ALOHA scheme is only an example of the problems studied by Queueing Theory, and the Markov Chain is one of its fundamental models. Figure 4: Illustration of the Markov Chain model of the backlogging process associated with the Slotted ALOHA scheme. Let us introduce some basic concepts, notations and classic results of Queueing Theory. – Kendall’s Notation and Terminology: The standard notation to describe a queue is as follows A/B/c/K (6) where: A denotes the distribution of the arrival (load) process. The most common/basic cases are ∗ A = M : Used in reference to a Markov process, with load following a Poisson distribution. ∗ A = M X : Used in reference to a batch Markov process, with load arrives simultaneously following a Poisson dis- tribution. ∗ A = G: Used in reference to processes with load following a General (arbitrary) distribution. 5  B denotes the distribution of the inter-arrival (service time) process. The most common/basic cases are ∗ B = M : Used in reference to Markov process, with time following an Exponential distribution. ∗ B = G: Used in reference to processes with time following a General (arbitrary) distribution. ∗ B = D: Used in reference to processes with Deterministic times. c is a constant denoting the number of servers. K is a constant denoting the queue capacity. The constant K is often omitted if K = ∞. Example: The throughput of Slotted ALOHA is modeled by M X /M/1 – Fundamental Performance Parameters: ∗ Average Waiting Time (sojourn): Time it takes since someone enters the queue, until it leaves. ∗ Expected Queue Length: Number of users (“customers”) in the system in steady state. ∗ Average Idle Time: Fraction of time the server is free, i.e. number users = 0. Notice that the values of these metrics depend not only on transition probabilities, but also on the initial state. Figure 5: Illustration of the Markov Chain model of a simple “birth-death” process. 6 – Little’s Theorem: Consider the G/G/1 queue as the one depicted in figure 5, with average arrival rate λ and average departure µ. Let k denote the number of users in the queue in steady state, and pk be denote the probability that there are k users in the system at steady state. Then, the expected queue length is ∞ X K= k · pk (7) k=0 Finally, let S denote the average sojourn time a user spends in the queue. Then, Little’s Theorem states that: K = λS (8) Finding the average length K and the average sojourn S of a queue is often referred to as “solving the queue.” In this regard, Little’s Theorem ensures that two alternative ways to solve the queue exist. Example: Consider the process illustrated in figure 6 below, in which the Y - axis shows the number of users in the queue, the X-axis represents time, and the index of different users is shown within circles. The average queue length K and average sojourn time S are given by 1 K = [(t2 − t1 ) + 2(t3 − t2 ) + (t4 − t3 ) + 2(t5 − t4 ) + 3(t6 − t5 ) + T 1 +2(t7 − t6 ) + (T − t7 )] = [T − t1 − t2 + t3 − t4 − t5 + t6 + t7 ] T 1 S = [(t3 − t1 ) + (t6 − t2 ) + (t7 − t4 ) + (T − t5 )] = N 1 [T − t1 − t2 + t3 − t4 − t5 + t6 + t7 ] N where N = 4. From the above it is found that N K= S = λS (9) T where λ = N/T is, as predicted by Little’s Theorem, the average rate of arrival of the system. 7 Figure 6: Illustration of the Markov Chain model of the backlogging process associated with the Slotted ALOHA scheme. Backlogged Analysis: – Backlogged Nodes: It is assumed that each of the backlogged nodes attempts re- transmission at each slot with probability pb. Notation: pb = probability of that a node is “busy” Notice that pb is a design parameter! – Group of Backlogged Nodes: Let B be the number of backlogged nodes at the beginning of a slot. The probability that i out of the B backlogged nodes simultaneously and independently attempt retransmission is gov- erned by the Binomial distribution   B Pb (i; B) = (1 − pb )B−i pib (10) i – Non-backlogged Nodes: We assume that a total of N nodes are in the system. Each of the N − B non-backlogged nodes have empty buffers, but may still transmit a new packet with a probability pe , which in turn depends on the probability of arrival of packets at each node. Assuming the arrival rate of the system is λ, the probability of no arrival at a single node is e−λ/N , such that the probability that at least one new packet arrives at a given node is pe = 1 − e−λ/N (11) Notation: pe = probability that a node transmits a new packet. 8 – Group of Non-backlogged Nodes: Analogously to Pb , the probability that i out of N − B non- backlogged nodes transmit is given by   N −B Pe (i; B) = (1 − pe )N −B−i pie (12) i – Queue Dynamics: At each slot, the number of backlogged nodes may (see Figure 4) a) Decrease by 1 if a backlogged node gets a packet across, which occurs with probability Only 1 backlogged node transmits z }| { Pk→k−1 = Pe (0; k) · Pb (1; k) (13) | {z } No “empty” node transmits b) Remain the same if only one empty node transmits while none of the backlogged nodes do, or no empty node transmits and more then 1 backlogged nodes do No new packet is generated and, no backlogged packet is transmitted or gets across z }| { Pk→k = Pe (1; k) · Pb (0; k) + Pe (0; k) · [1−Pb (1; k)] | {z } New packet is generated and gets across c) Is increased by 1 if a single empty node transmits, but any of the backlogged nodes also do Any backlogged node transmits z }| { Pk→k+1 = Pe (1; k) · [1 − Pb (0; k)] (14) | {z } One “empty” node transmits d) Is increased by i if a number i > 2 of empty nodes transmit Pk→k+i = Pe (i; k) (15) | {z } A number i > 2 of “empty” nodes transmit The aforementioned probabilities can be understood as transition probabilities of an infinite state machine (or chain), whose states are the number of backlogged nodes. Notice that in such a chain, the probability of transitioning to another state is independent on previous transitions/states. Probability chains with such “memoryless” characteristic are known as Markov Chains. 9  – Stead-state Probabilities pk : Recall that in order to compute the average number of backlogged users in steady state as per equation (7), the probabilities pk that the steady-state queue has length k are required. Two general relations for the probabilities pk are: ∗ The sum of all steady state probabilities is unitary N X pk = 1 (16) k=0 ∗ The chance of a given steady-state equals the sum of all state transitions, times the corresponding previous states ∞ X pk = pi · Pi→k (17) i=0 For an M K /M/1 queue, calculating pk can be a formidable chal- lenge. Specifically, equation (17) becomes hard to solve1 , due to its asymptotic nature. Fortunately, in the case in question, the maximum state-decrease is unitary such that equation (17) reduces to k+1 X pk = pi · Pi→k (18) i=0 From equation (18) it follows that k X pk = pk+1 · Pk+1→k + pi · Pi→k i=0 k X pk+1 · Pk+1→k = pk − pi · Pi→k i=0 k−1 X pk − pk · Pk→k − pi · Pi→k i=0 k−1 X pk · (1 − Pk→k ) − pi · Pi→k i=0 k−1 " # 1 X pk+1 = · pk · (1 − Pk→k ) − pi · Pi→k , ∀k0 1−x which is also tight for small x, yielding Ps ≈ [(N − k) · pe + k · pb ] e−Rk = Rk · e−Rk , (pe , pb )  1. (25) The average throughput of Slotted ALOHA is, even with a finite number of nodes, in fact well approximated by a Poisson random variable, but with a variable rate. 12  Stability Conditions: In order to interpret the above result in terms of stability, consider the plots shown in figure 7. In this figure, the drift is given by the distance between the straight (blue) line and the (black) curve. It can be seen that when the queue has a small number of backlogged nodes (k < 2) the drift is positive, leading to an increase in back- logging. Likewise, if the load is anywhere between 2 and 12, the drift is negative, indicating a high likelihood that those additional back- logged nodes will be served. The point around k = 2 is, therefore, a stable throughput point. If, however, a load higher then k = 12 accumulates, the resulting positive drift will push the network to an undesired equilibrium point, where the average queue length is k = 21 and the aggregate throughput is of nearly 0.05 packets per slot. Notice that the point in the vicinity of k = 12 is an unstable equilibrium point! Notice also that the distance between the stable throughput and the unstable equilibrium points imply possibly large delays in re-establishing equilibrium after an off-balance event. Aggregate Throughput and Drift of Slotted ALOHA 0.4 Aggregate Throughput 0.35 Drif+Throughput 0.3 Throughput: Ps 0.25 0.2 Desirable Stability Point Undesirable Stability Point 0.15 0.1 Unstable Equilibrium Point 0.05 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 Load: k Figure 7: Superposed plots of the aggregate throughput Ps and drift of Slotted ALOHA, as a function of the load k. The drift Dk is the difference between the blue line and the black curve. The results are calculated with the parameters: N = 25, pe = 0.015 and pb = 0.2. 13  Consider now a variation of this plot with pb = 0.3, shown in figure 8. It can be seen that the drift delay is reduced, at the expense, however of less stability. Aggregate Throughput and Drift of Slotted ALOHA 0.4 Aggregate Throughput 0.35 Drif+Throughput 0.3 Throughput: Ps 0.25 0.2 0.15 0.1 0.05 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 Load: k Figure 8: Superposed plots of the aggregate throughput Ps and drift of Slotted ALOHA, as a function of the load k. The drift Dk is the difference between the blue line and the black curve. The results are calculated with the parameters: N = 25, pe = 0.015 and pb = 0.3. Finally, consider what occurs if the probability of new arrivals pe is only slightly higher then that assumed in figure 7, as illustrated in figure 9. In this case, it is found that the network cannot achieve any desirable stable throughput! Aggregate Throughput and Drift of Slotted ALOHA 0.4 Aggregate Throughput 0.35 Drif+Throughput 0.3 Throughput: Ps 0.25 0.2 0.15 0.1 0.05 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 Load: k Figure 9: Superposed plots of the aggregate throughput Ps and drift of Slotted ALOHA, as a function of the load k. The drift Dk is the difference between the blue line and the black curve. The results are calculated with the parameters: N = 25, pe = 0.0175 and pb = 0.2. 14  Recommended Reading - Bertsekas and Gallager : Chapter 4 (Section 4.2 ∼ 4.2.4) - Gross et al. : Chapter 1 (Sections 1.1 ∼ 1.9) References L. G. Roberts, “ALOHA packet system with and without slots and cap- ture,” Telenet Communications Corporation, Tech. Rep., 1972. D. Bertsekas and R. Gallager, Data Networks. Prentice Hall, 1992. Avalilable at: http://web.mit.edu/dimitrib/www/datanets.html. D. Gross, J. F. Shortle, J. M. Thompson, and C. M. Harris, Fundamen- tals of Queueing Theory. Wiley, 2008. 15