Sec.4.2 Slotted Multiaccess and the Aloha System 285 n =1.This is a reasonable model for very small A.since very few collisions occur and q is typically 1.It is also reasonable for large A<1/e,since typically n is large andn. Let I,be the delay from the arrival of the h packet until the beginning of theh successful transmission.Note that if the system were first-come first-serve,II would be the queueing time of theh arrival.By the same argument as in Problem 3.32,however, the average of II,over all i is equal to the expected queueing delay 11'.Let n,be the number of backlogged packets at the instant before i's arrival;n;does not include any packet currently being successfully transmitted.but does include current unsuccessful transmissions.II;can be expressed as I,=R,+∑t+ (4.8) /-1 Ri is the residual time to the beginning of the next slot.and ((forn>0)is the subsequent interval until the next successful transmission is completed.Similarly, i.I<jmi.is the interval from the end of the (j-1)h subsequent success to the end of the jth subsequent success.After those n,successes.is the remaining interval until the beginning of the next successful transmission (i.e..the ith transmission overall). Observe that for each interval t,.the backlog is at least two.counting the new th arrival and the n,packets already backlogged.Thus,each slot is successful with probability 1/c,and the expected value of each t,is e.Next.observe that Little's formula relates the expected values of II,and n;(i.e..11,is the wait not counting the successful transmission.and n,is the number in the system not counting successful transmissions in process).Finally.the expected value of R;is 1/2 (counting time in slots).Thus,taking the expected value of Eq.(4.8)and averaging over i,we get T=1/2+λI+E{} (4.9) Now consider the system at the first slot boundary at which both the (-1) departure has occurred and the ith arrival has occurred.If the backlog is I at that point (i.e..only the ith packet is in the system),then y;is 0.Alternatively,if>1.then }=e-1.Let pn be the steady-state probability that the backlog is n at a slot boundary.Then.since a packet is always successfully transmitted if the state is I at the beginning of the slot,we see that p is the fraction of slots in which the state is I and a packet is successfully transmitted.Since A is the total fraction of slots with successful transmissions.p/A is the fraction of packets transmitted from state 1 and I-p/A is the fraction transmitted from higher-numbered states.It follows that E(=《-1A-) (4.10) Finally.we must determine p:.From the argument above.we see that A=p:+ (1-Po-p)/c.Also,state 0 can be entered at a slot boundary only if no arrivals occurred in the previous slot and the previous state was 0 or 1.Thus.po(p Solving for p gives (1-(e入-1) A=1-(e-1入-1) (4.1)
Sec. 4.2 Slotted Multiaccess and the Aloha System 285 n = I. This is a reasonable model for very small A, since very few collisions occur and (j, is typically I. It is also reasonable for large A < 1/c, since typically n is large and fz :::::; n. Let 1\'i be the delay from the arrival of the i th packet until the beginning of the ?h successful transmission, Note that if the system were first-come first-serve, H-i would be the queueing time of the i th arrival. By the same argument as in Problem 3.32, however, the average of 1\', over all i is equal to the expected queueing delay H-. Let II, be the number of backlogged packets at the instant before i's arrival; II, does not include any packet currently being successfully transmitted, but does include current unsuccessful transmissions. lri can be expressed as 1\', = Hi + L f; +.1J, }=I (4.8) Hi is the residual time to the beginning of the next slot, and II (for II, > 0) is the subsequent interval until the next successful transmission is completed. Similarly, f j . I < j :::; II i, is the interval from the end of the (j - I yh subsequent success to the end of the /h subsequent success. After those n, successes, y, is the remaining interval until the beginning of the next successful transmission (i.e., the ?h transmission overall). Observe that for each interval tJ , the backlog is at least two, counting the new i th arrival and the n i packets already backlogged. Thus, each slot is successful with probability 1/c, and the expected value of each I} is c. Next, observe that Little's formula relates the expected values of H-, and II, (i.e., H-, is the wait not counting the successful transmission, and II, is the number in the system not counting successful transmissions in process). Finally, the expected value of Hi is 1/2 (counting time in slots). Thus, taking the expected value of Eq. (4.8) and averaging over i, we get 1\' = 1/2 + Ac1\' + E{y} (4.9) (4.10) Now consider the system at the first slot boundary at which both the (i I)st departure has occurred and the ?h arrival has occurred. If the backlog is I at that point (i.e., only the i th packet is in the system), then ih is O. Alternatively, if II > I, then E' {iii} = c - I. Let]in be the steady-state probability that the backlog is n at a slot boundary. Then. since a packet is always successfully transmitted if the state is I at the beginning of the slot, we see that PI is the fraction of slots in which the state is I and a packet is successfully transmitted. Since A is the total fraction of slots with successful transmissions, PI / A is the fraction of packets transmitted from state I and I - PI / A is the fraction transmitted from higher-numbered states. It follows that {} ((-I)(A-Pl) E Ij = ------ . A Finally, we must determine PI. From the argument above. we see that A = PI + (I - Po - PI)/ c. Also, state 0 can be entered at a slot boundary only if no arrivals occurred in the previous slot and the previous state was 0 or I. Thus, Po = (Po + PI Jr· A. Solving for PI gives PI (I-AcHe A -I) I - (e I )((A - I) (4.11 )
286 Multiaccess Communication Chap.4 Combining Egs.(4.9)to (4.11)yields W= e-1/2 (e入-l)e-1) 1-e (4.12) 1-(e-I)(ex-I)] This value of W'is quite close to delay values for the pseudo-Bayesian algorithm obtained through simulation.Figure 4.6 plots E[}for this approximate model and compares it with the queueing delay for TDM with 8 and 16 nodes.It is quite surprising that the delay is so small even for arrival rates relatively close to 1/e.It appears that the assumption of immediate feedback is unnecessary for stabilization strategies of this type to be stable:the argument is that feedback delay will make the estimate n less accurate, but n/n will still stay close to I for large n. Binary exponential backoff.In the packet radio networks to be discussed in Section 4.6,and in some other multiaccess situations.the assumption of 0,1.e feedback on all slots is unrealistic.In some systems,a node receives feedback only about whether or not its own packets were successfully transmitted;it receives no feedback about slots in which it does not transmit.Such limited feedback is sufficient for slotted Aloha but is insufficient for the backlog estimation of the pseudo-Bayesian strategy.Binary exponential backoff [MeB76]is a stabilization strategy used in Ethernet that employs only this more limited form of feedback. This strategy is very simple;if a packet has been transmitted unsuccessfully i times.then the probability of transmission in successive slots is set at g-2-(or is uniformly distributed over the next 2i slots after the ith failure).When a packet initially arrives in the system,it is transmitted immediately in the next slot. 8 m■16 Figure 4.6 Comparison of expected m=8 waiting time 11'in slots.from arrival until beginning of successful transmission,for stabilized Aloha and for TDM with m =8 Stabilized Aloha and m 16.For small arrival rates.the 0.5 delay of stabilized Aloha is little more 0.2 0.4 0.6 than waiting for the next slot.whereas as the arrival rate approaches i/e.the delay Arrival Rate becomes unbounded
286 Combining Eqs. (4.9) to (4.11) yields Multiaccess Communication Chap. 4 TV = e - 1/2 _ (e.\ - I)(e - I) I-Ae A[I-(e-I)(e.\-I)] (4.12) This value of TV is quite close to delay values for the pseudo-Bayesian algorithm obtained through simulation. Figure 4.6 plots E {n-} for this approximate model and compares it with the queueing delay for TDM with 8 and 16 nodes. It is quite surprising that the delay is so small even for arrival rates relatively close to 1/e. It appears that the assumption of immediate feedback is unnecessary for stabilization strategies of this type to be stable; the argument is that feedback delay will make the estimate n less accurate, but n/n will still stay close to I for large n. Binary exponential backoff. In the packet radio networks to be discussed in Section 4.6, and in some other multiaccess situations, the assumption of 0, I,e feedback on all slots is unrealistic. In some systems, a node receives feedback only about whether or not its own packets were successfully transmitted; it receives no feedback about slots in which it does not transmit. Such limited feedback is sufficient for slotted Aloha but is insufficient for the backlog estimation of the pseudo-Bayesian strategy. Binary exponential backoff [MeB76] is a stabilization strategy used in Ethernet that employs only this more limited form of feedback. This strategy is very simple; if a packet has been transmitted unsuccessfully i times, then the probability of transmission in successive slots is set at qr = 2-i (or is uniformly distributed over the next 2i slots after the i 1h failure). When a packet initially arrives in the system, it is transmitted immediately in the next slot. 8 w 4 0.5 o 0.2 0.4 0.6 Arrival Rate Figure 4.6 Comparison of expected waiting time II' in slots. from arrival untiI beginning of successful transmission, for stabilized Aloba and for TDM with m = 8 and III = 16. For small arrival rates. the delay of stabilized Aloha is little more than waiting for the next slot. whereas as the arrival rate approaches 1/E, the delay becomes unbounded
Sec.4.2 Slotted Multiaccess and the Aloha System 287 Some rationale for this strategy can be seen by noting that when a packet first arrives (with this limited feedback),the node knows nothing of the backlog,so the immediate first transmission is reasonable.With successive collisions,any reasonable estimate of backlog would increase.motivating the decrease in the local gr.To make matters worse,however,as gr is reduced,the node gets less feedback per slot about the backlog,and thus.to play safe.it is reasonable to increase the backlog estimate by larger and larger amounts on each successive collision. Unfortunately.in the limit as the number of nodes approaches infinity,this strategy is unstable for every arrival rate A greater than 0 [Ald86].It is unknown whether or not any strategy can achieve stability with this type of limited feedback.Problem 4.10, however,develops another strategy that can be used with this limited feedback and with a finite number of nodes with unlimited buffering to achieve finite expected delay for any A less than I.Unfortunately.the price of this high throughput is inordinately large delay. 4.2.4 Unslotted Aloha Unslotted,or pure,Aloha [Abr70]was the precursor to slotted Aloha.In this strategy, each node.upon receiving a new packet.transmits it immediately rather than waiting for a slot boundary.Slots play no role in pure Aloha,so we temporarily omit the slotted system assumption.If a packet is involved in a collision,it is retransmitted after a random delay.Assume that if the transmission times for two packets overlap at all, the CRCs on those packets will fail and retransmission will be required.We assume that the receiver rebroadcasts the composite received signal (or that all nodes receive the composite signal).so that each node,after a given propagation delay,can determine whether or not its transmitted packets were correctly received.Thus,we have the same type of limited feedback discussed in the last subsection.Other types of feedback could be considered and Problem 4.11 develops some of the peculiar effects of other feedback assumptions. Figure 4.7 shows that if one packet starts transmission at time t,and all packets have unit length,then any other transmission starting between t-I and t+I will cause a collision.For simplicity,assume an infinite number of nodes (i.e.,assumption 6b)and let n be the number of backlogged nodes at a given time.For our present purposes.a node is considered backlogged from the time it has determined that its previously transmitted packet was involved in a collision until the time that it attempts retransmission.Assume that the period until attempted retransmissionr is an exponentially distributed random variable with probability density re.where r is an arbitrary parameter interpreted as a node's retransmission attempt rate.Thus,with an overall Poisson arrival rate of A to the system.the initiation times of attempted transmissions is a time-varying Poisson process of rate G()=A+n.z in which n is the backlog at a given time. Consider the sequence of successive transmission attempts on the channel.For some given i,let 7,be the duration of the interval between the initiations of the ith and (+1)th transmission attempt.The ith attempt will be successful if both 7;and T exceed I (assuming unit length packets).Given the backlog in each intertransmission
Sec. 4.2 Slotted Multiaccess and the Aloha System 287 Some rationale for this strategy can be seen by noting that when a packet first arrives (with this limited feedback), the node knows nothing of the backlog, so the immediate first transmission is reasonable. With successive collisions, any reasonable estimate of backlog would increase, motivating the decrease in the local qr' To make matters worse, however, as qr is reduced, the node gets less feedback per slot about the backlog, and thus, to play safe, it is reasonable to increase the backlog estimate by larger and larger amounts on each successive collision. Unfortunately, in the limit as the number of nodes approaches infinity, this strategy is unstable for every arrival rate), greater than 0 [Ald86]. It is unknown whether or not any strategy can achieve stability with this type of limited feedback. Problem 4.10, however, develops another strategy that can be used with this limited feedback and with a finite number of nodes with unlimited buffering to achieve finite expected delay for any), less than I. Unfortunately, the price of this high throughput is inordinately large delay. 4.2.4 Unslotted Aloha Unslotted, or pure, Aloha [Abr70] was the precursor to slotted Aloha. In this strategy, each node, upon receiving a new packet, transmits it immediately rather than waiting for a slot boundary. Slots play no role in pure Aloha, so we temporarily omit the slotted system assumption. If a packet is involved in a collision, it is retransmitted after a random delay. Assume that if the transmission times for two packets overlap at all, the CRCs on those packets will fail and retransmission will be required. We assume that the receiver rebroadcasts the composite received signal (or that all nodes receive the composite signal), so that each node, after a given propagation delay, can determine whether or not its transmitted packets were correctly received. Thus, we have the same type of limited feedback discussed in the last subsection. Other types of feedback could be considered and Problem 4.11 develops some of the peculiar effects of other feedback assumptions. Figure 4.7 shows that if one packet starts transmission at time t, and all packets have unit length, then any other transmission starting between t - I and t + I will cause a collision. For simplicity, assume an infinite number of nodes (i.e., assumption 6b) and let n be the number of backlogged nodes at a given time. For our present purposes, a node is considered backlogged from the time it has determined that its previously transmitted packet was involved in a collision until the time that it attempts retransmission. Assume that the period until attempted retransmission T is an exponentially distributed random variable with probability density ;J:(,-rr, where .J: is an arbitrary parameter interpreted as a node's retransmission attempt rate. Thus, with an overall Poisson arrival rate of ), to the system, the initiation times of attempted transmissions is a time-varying Poisson process of rate G(n) = ), + ru' in which n is the backlog at a given time. Consider the sequence of successive transmission attempts on the channel. For some given i., let Tj be the duration of the interval between the initiations of thei.1h and (i + I)lh transmission attempt. The i 1h attempt will be successful if both Tj and Tj-1 exceed I (assuming unit length packets). Given the backlog in each intertransmission
288 Multiaccess Communication Chap.4 New arrivals ☑ Retransmission Figure 4.7 Unslotted Aloha.New arrivals are transmitted immediately and unsuccessful transmissions are repeated after a random delay.Packet transmission time is one unit. and two transmissions collide if their interdeparture interval is less than one unit. interval,these intervals are independent.Thus,assuming a backlog of n for each interval, we have Pxuee e-2Gu (4.13) Since attempted transmissions occur at rate G(n).the throughput (i.e..the expected number of successful transmissions per unit time)as a function of n is throughput (n)=G(n)e-2Gn) (4.14) Figure 4.8 illustrates this result.The situation is very similar to that of slotted Aloha,except that the throughput has a maximum of 1/(2e),achieved when G(n)=1/2. The analysis above is approximate in the sense that Eg.(4.13)assumes that the backlog is the same in the intervals surrounding a given transmission attempt,whereas according to our definition of backlog.the backlog decreases by one whenever a backlogged packet initiates transmission and increases by one whenever a collided packet is detected.For small (i.e..large mean time before attempted retransmission).this effect is relatively small. It can be seen from Fig.4.8 that pure Aloha has the same type of stability problem as slotted Aloha.For the limited feedback assumed here.stability is quite difficult to achieve or analyze (as is the case with slotted Aloha).Very little is known about stabilization for pure Aloha,but if A is very small and the mean retransmission time very large.the system can be expected to run for long periods without major backlog buildup. One of the major advantages of pure Aloha is that it can be used with variable- length packets,whereas with slotted Aloha.long packets must be broken up to fit into slots and short packets must be padded out to fill up slots.This compensates for some of the inherent throughput loss of pure Aloha and gives it an advantage in simplicity.Some analysis,with simplifying assumptions,of the effect of variable-length packets appears in [Fer75]and [San80]
288 Multiaccess Communication New arrivals Chap. 4 t Retransmission Figure 4.7 Unslotted Aloha. New arrivals are transmitted immediately and unsuccessful transmissions are repeated after a random dclay. Packct transmission time is one unit, and two transmissions collidc if their interdeparture interval is less than one unit. interval, these intervals are independent. Thus, assuming a backlog of n for each interval, we have (4.13) Since attempted transmissions occur at rate G( II), the throughput (i.e .• the expected number of successful transmissions per unit time) as a function of n is throughput (n) = G(II)r-2Glnl (4.14) Figure 4.8 illustrates this result. The situation is very similar to that of slotted Aloha, except that the throughput has a maximum of 1/(2e), achieved when G(II) = 1/2. The analysis above is approximate in the sense that Eq. (4.13) assumes that the backlog is the same in the intervals surrounding a given transmission attempt, whereas according to our definition of backlog. the backlog decreases by one whenever a backlogged packet initiates transmission and increases by one whenever a collided packet is detected. For small .r (i.e .. large mean time before attempted retransmission). this effect is relatively small. It can be seen from Fig. 4.8 that pure Aloha has the same type of stability problem as slotted Aloha. For the limited feedback assumed here. stability is quite difficult to achieve or analyze (as is the case with slotted Aloha). Very little is known about stabilization for pure Aloha, but if A is very small and the mean retransmission time very large. the system can be expected to run for long periods without major backlog buildup. One of the major advantages of pure Aloha is that it can be used with variablelength packets. whereas with slotted Aloha, long packets must be broken up to fit into slots and short packets must be padded out to fill up slots. This compensates for some of the inherent throughput loss of pure Aloha and gives it an advantage in simplicity. Some analysis. with simplifying assumptions. of the etlect of variable-length packets appears in [Fer75] and [San80]
Sec.4.3 Splitting Algorithms 289 1/八2e) Drift Departures Ge-7G Arrivals Equilibrium G=A+nx G=λ G=1/2 Figure 4.8 Pure Aloha as a function of the attempted transmission rate G.Successful departures leave the system at a rate G-.and arrivals occur at a rate A.leading to a hypothesized equilibrium at the point shown. 4.3 SPLITTING ALGORITHMS We have seen that slotted Aloha requires some care for stabilization and is also essen- tially limited to throughputs of I/e.We now want to look at more sophisticated collision resolution techniques that both maintain stability without any complex estimation pro- cedures and also increase the achievable throughput.To get an intuitive idea of how this can be done,note that with relatively small attempt rates,when a collision occurs, it is most likely between only two packets.Thus,if new arrivals could be inhibited from transmission until the collision was resolved.each of the colliding packets could be independently retransmitted in the next slot with probability 1/2.This would lead to a successful transmission for one of the packets with probability 1/2.and the other could then be transmitted in the following slot.Alternatively.with probability 1/2.an- other collision or an idle slot occurs.In this case.each of the two packets would again be independently transmitted in the next slot with probability 1/2.and so forth until a successful transmission occurred,which would be followed by the transmission of the remaining packet. With the strategy above.the two packets require two slots with probability 1/2. three slots with probability 1/4.and i slots with probability 2-.The expected number of slots for sending these two packets can thus be calculated to be three,yielding a throughput of 2/3 for the period during which the collision is being resolved. There are various ways in which the nodes involved in a collision could choose whether or not to transmit in successive slots.Each node could simply flip an unbiased coin for each choice.Alternatively (in a way to be described precisely later)each node could use the arrival time of its collided packet.Finally.assuming a finite set of nodes,each with a unique identifier represented by a string of bits,a node could use the successive bits of its identity to make the successive choices.This last alterative has the
Sec. 4.3 1/(2e) Splitting Algorithms 289 AI----rl~---I----------~~------- G = A G = 1/2 Figure 4.8 Pure Aloha as ,I function of the attempted transmission rate G. Successful departures leave the system at a rate Gc- cc;. and arrivals occur at a rate )" leading to a hypothesized equilibrium at the point shown. 4.3 SPUTIING ALGORITHMS We have seen that slotted Aloha requires some care for stabilization and is also essentially limited to throughputs of 1/1'. We now want to look at more sophisticated collision resolution techniques that both maintain stability without any complex estimation procedures and also increase the achievable throughput. To get an intuitive idea of how this can be done, note that with relatively small attempt rates, when a collision occurs, it is most likely between only two packets. Thus, if new arrivals could be inhibited from transmission until the collision was resolved. each of the colliding packets could be independently retransmitted in the next slot with probability 1/2. This would lead to a successful transmission for one of the packets with probability 1/2, and the other could then be transmitted in the following slot. Alternatively. with probability 1/2. another collision or an idle slot occurs. In this case, each of the two packets would again be independently transmitted in the next slot with probability 1/2, and so forth until a successful transmission occurred, which would be followed by the transmission of the remaining packet. With the strategy above, the two packets require two slots with probability 1/2, three slots with probability 1/4, and i slots with probability 2-(1-1). The expected number of slots for sending these two packets can thus be calculated to be three, yielding a throughput of 2/3 for the period during which the collision is being resolved. There are various ways in which the nodes involved in a collision could choose whether or not to transmit in successive slots. Each node could simply flip an unbiased coin for each choice. Alternatively (in a way to be described precisely later) each node could use the arrival time of its collided packet. Finally, assuming a finite set of nodes, each with a unique identifier represented by a string of bits, a node could use the successive bits of its identity to make the successive choices. This last alternative has the