280 Multiaccess Communication Chap.4 iteratively,finding p for each successively larger n in terms of p and finally.finding o as a normalizing constant (see Problem 4.1).From this,the expected number of backlogged nodes can be found,and from Little's theorem,the average delay can be calculated. Unfortunately,this system has some very strange properties for a large number of nodes,and the steady-state results above are very misleading.To get some intuitive understanding of this.note that we would like to choose the retransmission probability gr to be moderately large,so as to avoid large delays after collisions.If the arrival rate is small and not many packets are involved in collisions,this works well and retransmissions are normally successful.On the other hand,if the system is afflicted with a run of bad luck and the number of backlogged packets n gets large enough to satisfy grn >1,then collisions occur in almost all successive slots and the system remains heavily backlogged for a long time. To understand this phenomenon quantitatively.define the drift in state n(D,)as the expected change in backlog over one slot time,starting in state n.Thus,D, is the expected number of new arrivals accepted into the system [i.e..(m-n)da]less the expected number of successful transmissions in the slot:the expected number of successful transmissions is just the probability of a successful transmission,defined as Psce.Thus. Do=(m-n)ga -Psuce (4.4) where Psucc =Qa(1.n)Q,(0.n)+Qa(0.n)Qr(1.n) (4.5) Define the attempt rate G(n)as the expected number of attempted transmissions in a slot when the system is in state n.that is. G(n)=(m-n)qa +ngr If da and gr are small.Pucc is closely approximated as the following function of the attempt rate: P.uc≈G(n)e-Gn (4.6) This approximation can be derived directly from Eq.(4.5).using the approximation (1-r)e for small a in the expressions for Q and Q,.Similarly,the probability of an idle slot is approximately e.Thus.the number of packets in a slot is well approximated as a Poisson random variable (as in the earlier intuitive analysis),but the parameter G(n)varies with the state.Figure 4.4 illustrates Egs.(4.4)and (4.6)for the case g>g(this is the only case of interest,as discussed later).The drift is the difference between the curve and the straight line.Since the drift is the expected change in state from one slot to the next,the system,although perhaps fluctuating.tends to move in the direction of the drift and consequently tends to cluster around the two stable points with rare excursions between the two. There are two important conclusions from this figure.First.the departure rate (i.e.. P)is at most I/e for large m.Second,the departure rate is almost zero for long periods whenever the system jumps to the undesirable stable point.Consider the effect of
280 Multiaccess Communication Chap. 4 iteratively, finding P" for each successively larger II in terms of Po and finally, finding Po as a nonnalizing constant (see Problem 4.1). From this, the expected number of backlogged nodes can be found, and from Little's theorem, the average delay can be calculated. Unfortunately, this system has some very strange properties for a large number of nodes, and the steady-state results above are very misleading. To get some intuitive understanding of this, note that we would like to choose the retransmission probability q, to be moderately large, so as to avoid large delays after collisions. If the arrival rate is small and not many packets are involved in collisions. this works well and retransmissions are normally successful. On the other hand, if the system is afflicted with a run of bad luck and the number of backlogged packets II gets large enough to satisfy qrn >> I, then collisions occur in almost all successive slots and the system remains heavily backlogged for a long time. To understand this phenomenon quantitatively. define the drift in state n (D,,) as the expected change in backlog over one slot time, starting in state n. Thus, D" is the expected number of new arrivals accepted into the system [i.e .. (m - lI)qo] less the expected number of successful transmissions in the slot; the expected number of successful transmissions is just the probability of a successful transmission, defined as p"U(" Thus, (4.4) where (4.5) Define the attempt rate G(n) as the expected number of attempted transmissions in a slot when the system is in state n. that is. G(n) = (m - n)qa + nq, If q" and qr are small, Pm("c is closely approximated as the following function of the attempt rate: (4.6) This approximation can be derived directly from Eq. (4.5), using the approximation (1 - .r)'1 ::::; e-ru for small x in the expressions for q" and Qr' Similarly, the probability of an idle slot is approximately C-GI"I. Thus. the number of packets in a slot is well approximated as a Poisson random variable (as in the earlier intuitive analysis), but the parameter G(n) varies with the state. Figure 4.4 illustrates Eqs. (4.4) and (4.6) for the case (], > qa (this is the only case of interest, as discussed later). The drift is the difference between the curve and the straight line. Since the drift is the expected change in state from one slot to the next, the system, although perhaps fluctuating, tends to move in the direction of the drift and consequently tends to cluster around the two stable points with rare excursions between the two. There are two important conclusions from this figure. First. the departure rate (i.e., P"m") is at most lip for large lJl. Second, the departure rate is almost zero for long periods whenever the system jumps to the undesirable stable point. Consider the effect of
Sec.4.2 Slotted Multiaccess and the Aloha System 281 Desired stable point mQ. Departure rate Ge-G Unstable equilibrium Arrival rate Undesired (m -n)q stable point n=0 G=(m-nlq。+ng, n =m G-0 G=m4 G=mq, Figure 4.4 Instability of slotted Aloha.The horizontal axis corresponds to both the state n and the attempt rate G.which are related by the linear equation G=(in-n)+ngr with >For n to the left of the unstable point.D is negative and n drifts toward the desired stable point.For n to the right of the unstable point.D is positive and n drifts toward the undesired stable point. changing q,.As g,is increased,the delay in retransmitting a collided packet decreases. but also the linear relationship between n and the attempt rate G(n)=(m-n)4 +ngr changes [i.e..G(n)increases with n faster when g,is increased].If the horizontal scale for n is held fixed in Fig.4.4.this change in attempt rate corresponds to a contraction of the horizontal G(n)scale.and thus to a horizontal contraction of the curve Ge-C.This means that the number of backlogged packets required to exceed the unstable equilibrium point decreases.Alternatively.if g,is decreased.retransmission delay increases.but it becomes more difficult to exceed the unstable equilibrium point.If qr is decreased enough (while still larger than )the curve Ge-will expand enough in Fig.4.4 that only one stable state will remain.At this stable point.and similarly when gr=go.the backlog is an appreciable fraction of m.and this means both that an appreciable number of arriving packets are discarded and that the delay is excessively large. The question of what values of gr and arrival rate lead to stable behavior,particu- larly when gr and arrival rate vary from node to node and infinite buffering is provided at each node.has received considerable theoretical attention (e.g..[Tsy85]).These the- oretical studies generally assume that nodes are considered backlogged immediately on arrival.Problem 4.8.however,illustrates that if g,is small enough for stable operation. then the delay is considerably greater than that with TDM:thus these approaches are not of great practical importance. If we replace the no-buffering assumption with the infinite-node assumption.the attempt rate G(n)becomes A+ngr and the straight line representing arrivals in Fig.4.4 becomes horizontal.In this case.the undesirable stable point disappears,and once the state of the system passes the unstable equilibrium.it tends to increase without bound.In this case.the corresponding infinite-state Markov chain has no steady-state distribution
Sec. 4.2 Slotted Multiaccess and the Aloha System Desired stable point 281 n=O G=O G=mq. G=(m-n)q.+nq, n =m G =mq, Figure 4.4 Instability of slotted Aloha. The horizontal axis corresponds to both the state n and the attempt rate G. which are related by the linear equation G = (1/7 - n)q" +nq,. with 'I, > 'I". For n to the left of the unstable point. JJ is negative and II drifts toward the desired stable point. For II to the right of the unstable point. D is positive and n drifts toward the undesired stable point. changing q,. As (j, is increased, the delay in retransmitting a collided packet decreases, but also the linear relationship between n and the attempt rate G(II) = (m - n)qll + n(j, changes [i.e .. G(n) increases with n faster when (j," is increased]. If the horizontal scale for II is held fixed in Fig. 4.4, this change in attempt rate corresponds to a contraction of the horizontal G(n) scale. and thus to a horizontal contraction of the curve Gc-G . This means that the number of backlogged packets required to exceed the unstable equilibrium point decreases. Alternatively, if q, is decreased. retransmission delay increases, but it becomes more difficult to exceed the unstable equilibrium point. If q, is decreased enough (while still larger than (jll)' the curve Ge-(; will expand enough in Fig. 4.4 that only one stable state will remain. At this stable point. and similarly when q, = q". the backlog is an appreciable fraction of m, and this means both that an appreciable number of arriving packets are discarded and that the delay is excessively large. The question of what values of (j, and arrival rate lead to stable behavior, particularly when !J, and arrival rate vary from node to node and infinite buffering is provided at each node. has received considerable theoretical attention (e.g .. [Tsy85 J). These theoretical studies generally assume that nodes are considered backlogged immediately on arrival. Problem 4.8. however, illustrates that if !J, is small enough for stable operation. then the delay is considerably greater than that with TOM: thus these approaches are not of great practical importance. If we replace the no-buffering assumption with the infinite-node assumption. the attempt rate G( n) becomes A+ ni// and the straight line representing arrivals in Fig. 4.4 becomes horizontal. In this case. the undesirable stable point disappears, and once the state of the system passes the unstable equilibrium. it tends to increase without bound. In this case, the corresponding infinite-state Markov chain has no steady-state distribution
282 Multiaccess Communication Chap.4 and the expected backlog increases without bound as the system continues to run.(See Section 3A.5 for further discussion of stability of such systems.) From a practical standpoint.if the arrival rate A is very much smaller than 1/e. and if g is moderate,then the system could be expected to remain in the desired stable state for very long periods.In the unlikely event of a move to the undesired stable point, the system could be restarted with backlogged packets lost.Rather than continuing to analyze this rather flawed system.however,we look at modifications of slotted Aloha that cure this stability issue. 4.2.3 Stabilized Slotted Aloha One simple approach to achieving stability should be almost obvious now.Psucc is approximately G(n)e.which is maximized at G(n)=1.Thus,it is desirable to change q,dynamically to maintain the attempt rate G(n)at 1.The difficulty here is that n is unknown to the nodes and can only be estimated from the feedback.There are many strategies for estimating n or the appropriate value of gr(e.g..[HaL82]and IRiv851). All of them.in essence.increase g,when an idle slot occurs and decrease gr when a collision occurs. Stability and maximum throughput.The notion of stability must be clarified somewhat before proceeding.Slotted Aloha was called unstable in the last subsection on the basis of the representation in Fig.4.4.Given the no-buffering assumption.however, the system has a well-defined steady-state behavior for all arrival rates.With the infinite- node assumption.on the other hand,there is no steady-state distribution and the expected delay grows without bound as the system continues to run.With the no-buffering as- sumption.the system discards large numbers of arriving packets and has a very large but finite delay,whereas with the infinite-node assumption,no arrivals are discarded but the delay becomes infinite. In the following.we shall use the infinite-node assumption (6b).and define a multiaccess system as stable for a given arrival rate if the expected delay per packet (either as a time average or an ensemble average in the limit of increasing time)is finite. Ordinary slotted Aloha is unstable.in this sense,for any arrival rate greater than zero. Note that if a system is stable,then for a sufficiently large but finite number of nodes m.the system (regarding each arrival as corresponding to a new virtual node)has a smaller expected delay than TDM,since the delay of TDM.for a fixed overall arrival rate,increases linearly with m. The maximum stable throughput of a multiaccess system is defined as the least upper bound of arrival rates for which the system is stable.For example.the maximum stable throughput of ordinary slotted Aloha is zero.Our purpose with these definitions is to study multiaccess algorithms that do not require knowledge of the number of nodes m and that maintain small delay (for given A)independent of i.Some discussion will be given later to modifications that make explicit use of the number of nodes. Returning to the stabilization of slotted Aloha.note that when the estimate of backlog is perfect.and G(n)is maintained at the optimal value of 1,then (according to
282 Multiaccess Communication Chap. 4 and the expected backlog increases without bound as the system continues to run. (See Section 3A.5 for further discussion of stability of such systems.) From a practical standpoint. if the arrival rate), is very much smaller than 1/e, and if (jT is moderate, then the system could be expected to remain in the desired stable state for very long periods. In the unlikely event of a move to the undesired stable point, the system could be restarted with backlogged packets lost. Rather than continuing to analyze this rather flawed system, however, we look at modifications of slotted Aloha that cure this stability issue. 4.2.3 Stabilized Slotted Aloha One simple approach to achieving stability should be almost obvious now. P,ucc is approximately G(n)e- G1Tl1 , which is maximized at G(n) = I. Thus, it is desirable to change CIT dynamically to maintain the attempt rate G( n) at 1. The difficulty here is that n is unknown to the nodes and can only be estimated from the feedback. There are many strategies for estimating n or the appropriate value of CIT (e.g., lHaL82] and lRiv85]). All of them, in essence, increase CIr when an idle slot occurs and decrease (j, when a collision occurs. Stability and maximum throughput. The notion of stability must be clarified somewhat before proceeding. Slotted Aloha was called unstable in the last subsection on the basis of the representation in Fig. 4.4. Given the no-buffering assumption, however, the system has a well-defined steady-state behavior for all arrival rates. With the infinitenode assumption, on the other hand, there is no steady-state distribution and the expected delay grows without bound as the system continues to run. With the no-buffering assumption, the system discards large numbers of arriving packets and has a very large but finite delay, whereas with the infinite-node assumption, no arrivals are discarded but the delay becomes infinite. In the following, we shall use the infinite-node assumption (6b), and define a multiaccess system as stable for a given arrival rate if the expected delay per packet (either as a time average or an ensemble average in the limit of increasing time) is finite. Ordinary slotted Aloha is unstable, in this sense, for any arrival rate greater than zero. Note that if a system is stable, then for a sufficiently large but finite number of nodes m. the system (regarding each arrival as corresponding to a new virtual node) has a smaller expected delay than TDM, since the delay of TDM, for a fixed overall arrival rate, increases linearly with m. The maximum stable throughput of a multiaccess system is defined as the least upper bound of arrival rates for which the system is stable. For example, the maximum stable throughput of ordinary slotted Aloha is zero. Our purpose with these definitions is to study multiaccess algorithms that do not require knowledge of the number of nodes m and that maintain small delay (for given ),) independent of m. Some discussion will be given later to modifications that make explicit use of the number of nodes. Returning to the stabilization of slotted Aloha. note that when the estimate of backlog is perfect. and G(n) is maintained at the optimal value of I, then (according to
Sec.4.2 Slotted Multiaccess and the Aloha System 283 the Poisson approximation)idles occur with probability 1/e0.368.successes occur with probability 1/e,and collisions occur with probability 1-2/e0.264.Thus, the rule for changing gr should allow fewer collisions than idles.The maximum stable throughput of such a system is at most 1/e.To see this,note that when the backlog is large,the Poisson approximation becomes more accurate,the success rate is then limited to 1/e,and thus the drift is positive for A>1/e.It is important to observe that this argument depends on all backlogged nodes using the same retransmission probability. We shall see in Section 4.3 that if nodes use both their own history of retransmissions and the feedback history in their decisions about transmitting.maximum stable throughputs considerably higher than I/e are possible. Pseudo-Bayesian algorithm.Rivest's pseudo-Bayesian algorithm [Riv85]is a particularly simple and effective way to stabilize Aloha.This algorithm is essentially the same as an earlier,independently derived algorithm by Mikhailov [Mik79].but Rivest's Bayesian interpretation simplifies understanding.The algorithm differs from slotted Aloha in that new arrivals are regarded as backlogged immediately on arrival. Rather than being transmitted with certainty in the next slot.they are transmitted with probability qr in the same way as packets involved in previous collisions.Thus,if there are n backlogged packets(including new arrivals)at the beginning of a slot,the attempt rate is G(n)=ngr,and the probability of a successful transmission is ng(I-g)"- For unstabilized Aloha,this modification would not make much sense,since g,has to be relatively small and new arrivals would be unnecessarily delayed.For stabilized Aloha. however,gr can be as large as I when the estimated backlog is negligible,so that new arrivals are held up only when the system is already estimated to be congested.In Problem 4.6 it is shown that this modification increases the probability of success if the backlog estimate is accurate. The algorithm operates by maintaining an estimate of the backlog n at the beginning of each slot.Each backlogged packet is then transmitted (independently)with probability g()=min{1.1/.The minimum operation limits gr to at most 1,and subject to this limitation.tries to achieve an attempt rate G=ng,of 1.For each k.the estimated backlog at the beginning of slot +1 is updated from the estimated backlog and feedback for slot k:according to the rule max{入.ik+入-1}.for idle or success nk+1= (4.7) k+(e-2).for collision The addition of A to the previous backlog accounts for new arrivals,and the max operation ensures that the estimate is never less than the contribution from new arrivals. On successful transmissions,I is subtracted from the previous backlog to account for the successful departure.Finally,subtracting I from the previous backlog on idle slots and adding (e-2)-on collisions has the effect of decreasing f when too many idles occur and increasing f when too many collisions occur.For large backlogs,if =n,each of the n backlogged packets is independently transmitted in a slot with probability g,=1/n. Thus G(n)is 1,and.by the Poisson approximation,idles occur with probability I/e and
Sec. 4.2 Slotted Multiaccess and the Aloha System 283 the Poisson approximation) idles occur with probability lie 0::::: 0.368, successes occur with probability lie, and collisions occur with probability I - 21e 0::::: 0.264. Thus, the rule for changing qr should allow fewer collisions than idles. The maximum stable throughput of such a system is at most lie. To see this, note that when the backlog is large, the Poisson approximation becomes more accurate, the success rate is then limited to lie, and thus the drift is positive for A > lie. It is important to observe that this argument depends on all backlogged nodes using the same retransmission probability. We shall see in Section 4.3 that if nodes use both their own history of retransmissions and the feedback history in their decisions about transmitting, maximum stable throughputs considerably higher than lie are possible. Pseudo-Bayesian algorithm. Rivest's pseudo-Bayesian algorithm [Riv85] is a particularly simple and effective way to stabilize Aloha. This algorithm is essentially the same as an earlier, independently derived algorithm by Mikhailov [Mik79], but Rivest's Bayesian interpretation simplifies understanding. The algorithm differs from slotted Aloha in that new arrivals are regarded as backlogged immediately on arrival. Rather than being transmitted with certainty in the next slot, they are transmitted with probability qr in the same way as packets involved in previous collisions. Thus, if there are n backlogged packets (including new arrivals) at the beginning of a slot, the attempt rate is G(n) = nqr, and the probability of a successful transmission is nqr(1 - qr),,-I. For unstabilized Aloha, this modification would not make much sense, since qr has to be relatively small and new arrivals would be unnecessarily delayed. For stabilized Aloha, however, q, can be as large as I when the estimated backlog is negligible, so that new arrivals are held up only when the system is already estimated to be congested. In Problem 4.6 it is shown that this modification increases the probability of success if the backlog estimate is accurate. The algorithm operates by maintaining an estimate n of the backlog n at the beginning of each slot. Each backlogged packet is then transmitted (independently) with probability q,(T/) = min{I. lin}. The minimum operation limits qr to at most I, and subject to this limitation, tries to achieve an attempt rate G = nq, of I. For each k, the estimated backlog at the beginning of slot k + I is updated from the estimated backlog and feedback for slot k according to the rule for idle or success (4.7) for collision The addition of A to the previous backlog accounts for new arrivals, and the max operation ensures that the estimate is never less than the contribution from new arrivals. On successful transmissions, I is subtracted from the previous backlog to account for the successful departure. Finally, subtracting I from the previous backlog on idle slots and adding (e - 2)-1 on collisions has the effect of decreasing TI when too many idles occur and increasing h when too many collisions occur. For large backlogs, if TI = n, each of the n backlogged packets is independently transmitted in a slot with probability qr = II TI. Thus G(n) is I, and. by the Poisson approximation, idles occur with probability lie and
284 Multiaccess Communication Chap.4 collisions with probability (e-2)/e.so that decreasing n by I on idles and increasing fby (e-2)on collisions maintains the balance between n and on the average. It is shown in Problem 4.9 that if the a priori probability distribution on n is Poisson with parameter>1.then given an idle or successful transmission in slot k,the probability distribution of n+is Poisson with parameter-1.Given a collision.the resulting distribution of n is not quite Poisson but is reasonably approximated as Poisson with parameter.For this reason.the algorithm is called pseudo-Bayesian. Figure 4.5 provides some heuristic understanding of why the algorithm is stable for all A<1/e.The state of the system is characterized by n and n,and the figure shows the expected drift in these variables from one slot to the next.If n and are large and equal,the expected drift of each is A-1/e,which is negative.On the other hand.if the absolute value of n-n is large,the expected drift of n is positive.but the expected reduction inIn-is considerably larger.Thus,if the system starts at some arbitrary point in the (n,)plane,n might increase on the average for a number of slots.but eventually n and will come closer together and then n will decrease on the average. In applications,the arrival rate A is typically unknown and slowly varying.Thus, the algorithm must either estimate A from the time-average rate of successful transmis- sions or set its value within the algorithm to some fixed value.It has been shown by Mikhailov (see Kel851)and Tsitsiklis [Tsi87]that if the fixed value I/e is used within the algorithm,stability is achieved for all actual A<1/e.Nothing has been proven about the behavior of the algorithm when a dynamic estimate of A is used within the algorithm. Approximate delay analysis.An exact analysis of expected delay for this algorithm.even with known A.appears to be very difficult.but it is instructive to analyze an approximate model.Assume that A is known and that the probability of successful transmission Pucc is 1/e whenever the backlog n is 2 or more,and that Psucc=I for n-分 Figure 4.5 Drift of u and u-for the pscudo-Bayesian stabilization algorithm. When the absolute value of n-is large. it approaches 0 faster than n increases
284 Multiaccess Communication Chap. 4 collisions with probability (e - 2)/e, so that decreasing il by I on idles and increasing Pi by (e 2)-1 on collisions maintains the balance between n and Pi on the average. It is shown in Problem 4.9 that if the a priori probability distribution on Ilk is Poisson with parameter Pi k -2: I, then given an idle or successful transmission in slot k, the probability distribution of nk+1 is Poisson with parameter nk + A - I. Given a collision, the resulting distribution of n k+ 1 is not quite Poisson but is reasonably approximated as Poisson with parameter F1k+ I. For this reason, the algorithm is called pseudo-Bayesian. Figure 4.5 provides some heuristic understanding of why the algorithm is stable for all A < I The state of the system is characterized by II andh, and the figure shows the expected drift in these variables from one slot to the next. If n and Pi are large and equal, the expected drift of each is A - 1/e, which is negative. On the other hand, if the absolute value of II - 71 is large, the expected drift of II is positive, but the expected reduction in In Pi I is considerably larger. Thus. if the system starts at some arbitrary point in the (n,il.) plane, n might increase on the average for a number of slots, but eventually n andil will come closer together and then II will decrease on the average. In applications, the arrival rate A is typically unknown and slowly varying. Thus, the algorithm must either estimate A from the time-average rate of successful transmissions or set its value within the algorithm to some fixed value. It has been shown by Mikhailov (see IKel85 J) and Tsitsiklis [Tsi87J that if the fixed value 1/e is used within the algorithm, stability is achieved for all actual A < 1/e. Nothing has been proven about the behavior of the algorithm when a dynamic estimate of A is used within the algorithm. Approximate delay analysis. An exact analysis of expected delay for this algorithm. even with known A, appears to be very difficult, but it is instructive to analyze an approximate model. Assume that A is known and that the probability of successful transmission ?""'C is 1/c whenever the backlog 1/ is 2 or more, and that P"".c = I for \ \ A n - n \ , 1 t , , n .... .... ..... ......... \ \ + f t + I I Figure 4.5 Drift of 1/ and 1/ - rl for the pseudo-Bayesian stabilization algorithm. When the absolute value of 1/ - " is large. it approaches 0 faster than n increases