SOME NEW APPROACHES TO RANro-1-ACCESS COMMUNICATIONS
`
`J~mes l. MASSEY
`
`Institute for Signal and Information Processing
`Swiss Federal Institute of Technology
`809Z Zurich, Switzerland
`
`Random-accessing is defined as any technique to accomp 1i sh unsched-
`u 1 ed seizure of a many-user communications channel; its purpose 1s
`to reduce transmission delay below what can be achieved by sched(cid:173)
`uled-accessing or by channel division. Some general principles re-.
`garding channel division, channel seizure, and the effect of feedback
`are formulated. The "classical" approach to random-accessing, 1.e.,
`ALOHA-like techniques. is seen to be subject to instability. A newer:
`approach. coll is ion-resolution al?orithms (CRA's), is shown to avoid
`this problem. The analysis of CRA s has led to bounds on the perform(cid:173)
`ance of any random-access system that are briefly discussed. Two new
`approaches to random-accessing without feedback informal ion are de(cid:173)
`scribed, viz .. protocol sequences for the M-user collision channel
`and coding for the M-active-out-of-T-user collision channel. E•amples
`He generously used throughout the paper, and some speculations on
`the pr act ica 1 i ty of the new approaches are offered.
`
`1.
`
`I N 1 RODUC T I ON
`
`Befo.re describing "new approaches to random-access communications", we should
`make clear what we mean by "random-accessing" and what we see as its main pur(cid:173)
`pose. To do this. we must first say a few words about "multiple-accessing" in
`
`genera 1.
`
`A multiple-access technique is any technique that permits two or more senders
`to operate on a single commun1cat1ons channel. Time-division multiple-accessing
`(TOMA). frequency-division mult1ple-access1ng (FOMA) and code-division multiple(cid:173)
`accessing(COMA) are wel 1-known mull 1ple-access schemes of the channel-division
`type: i.e .• they divide the single channel into many "smaller" channels. one
`for each sender. This division may be fixed, or it may be adjusted from time to
`time to correspond to the changing needs of the senders as in so-called "demand
`assignment" schemes. A second class of multiple-access schemes is that of what
`we shall call the channel-seizure type. ~n this type of multiple-accessing, a
`single sender can use the full (time and frequency) resources of the channel
`for himself alone on some sort of temporary basis. An example of a channel(cid:173)
`se1zure scheme H a token-ring in which. when the "token" arrives at a sender's
`station on the ring. that sender can remove the token, send his own message as
`if he were the only sender on the ring. and then reinsert the token.
`A random-access technique can be defined as a multiple-accessing scheme of the
`channel-seizure type ( i) in which it can happen that two or more senders may
`simultaneously alt.empt to seize the channel, and (ii) which provides in some
`way for the recovery from such "access conflicts", In a random-access system, a
`sender generally "takes a chance" when he attempts to seize the channel, and he
`re lies on the access protocol to repair the damage when he encounters "bad luck",,..·
`
`In some c~unication scenarios (as we sha 11 see later), access conflicts can(cid:173)
`not be avoided. More often, however, it is a matter of choice whether or not to
`allow access conflicts and hence whether or not to use random-accessing. The
`
`obvious question is: why should anyone choose to allow such an obviously bad
`thin9 as access conflicts? The answer can be put as a second question: why
`should anyone delll<1nd that ·a sender always wait for a guarantee of e•clus1ve
`access before he attempts to seize the channel? When traffic on the channel is
`
`l ...
`
`Reprinted with permission from Perfonnance '87, pp. 551-569, 1988.
`
`354
`
`Pet., Exh. 1017, p. 1
`
`

`
`l.L Mauty
`
`light, the bold sender will be almost sure to succeed 1n his gamble for access
`and can thus avoid the delay that a timid sender would incur, The prlmany pur(cid:173)
`pose of rand0111-accessing 1s to reduce the delay between the time that a sender
`obtains an ·information input and the time that he transmits this informat1o11
`successfully over the channel. Random-accessing ts a gamble, but one tn .which
`the odds can be on the side of the player rather than on the side of the "house".
`
`In Section 2 of this paper, we show why channel seizure h generally preferable
`to channel division for multiple-accessing, and we examine the role of channel
`feedback infonnat ion. Sect ion 3 describes the ALOHA approach to random-accessing
`and points out its virtues and defects. In Section 4, we describe one new ap(cid:173)
`proach to random-accessing, v1z. collision resolution, and we contrast it with
`the ALOHA approach, Sect ion 5 considers certa 1 n genera 1 bounds on the through(cid:173)
`put of rand0111-accen schemes. Sect Ion .6 describes two new approaches to random(cid:173)
`accessing without feedback. Some concluding remarks are given in Section 7.
`
`Z. stf4E GENERAL MULTIPLE-ACCESS PRINCIPLES
`
`The si1111>lest multiple-acceu channel is surely the two-sender binary adder
`channel (ZSBAC) shown In Fig. 1, Each time instant •. each sender sends· a binary
`digit (0 or 1) and the received digit is the sum (0, l or 2) of these two
`nUfllbers, i.e ••
`
`Yn • .xln + Xzn
`where x111 and lzn are the binary digits sent by senders l and 2. respectively, . ·
`h
`at time n and Y
`the re'ceived digit. The "wall" shown between the two se.nders
`11
`in fig. 1 signifies that the user on one side is not privy to the information
`to be sent on the other ~Ide, a 1 though the two users are a 1 lowed in advance to
`have formulated a .conmon strategy for sending this infonnation •
`
`)1----
`. . . $#~;;,;$
`.: ____ ~
`
`.l.'.2n
`
`Fic.1 : The lwo·scndcr binary adder channel (2SBAC)
`X 1,. E (O, l},X2 .. E {O, l}, Y,. E {O, l, 2}
`
`fig. Z shows the pentagonal "capacity region" of the 2S8AC, i.e., the region
`of rate pairs (R1, R2 ) such that Sender l can send data at the rate R1 (bits
`per channel use) and Sender Z can send at the rate R2, both with arbitrarily
`sma 11 error probabi 1 i ty.
`It is easy to ste how the point (R 1,R2 )' • (1,0) on the capacity-region boundary
`can be achieved. Sender Z simply always sends O's (and thus R2 • 0) ~o that
`Yn • Xln' and hence Sender l can directly send his "raw" information· bits over
`the channel with no need for coding (R1 • l). The point (R1,R2) • (0, l) can be
`similary achieved. By agreeing to alternate between these two schemes for ap(cid:173)
`p~priate periods, Senders l and Z can achieve any point (R1,R2 ) such that
`+ Rz • 1, i.e., at any point on the "time-sharing line" shown in ftg. z.
`R
`1
`
`I.. ,
`
`355
`
`Pet., Exh. 1017, p. 2
`
`

`
`R 2 (bita/u1e)
`
`Fis.2 : Capacity Region o{ the 2SBAC of Fig.l
`
`It Is almost as easy to see how the point (Rl'Rz) • (1, 1/Z) on the capacity(cid:173)
`region boundary can be approached. ~nder 1 transmits hh raw 1nfomat1on bits
`(R 1 • 1). This causes the channel sun by Sender Z to be thlt shown in fig. 3,
`because, for instance, if Sender Z should send a 1 then with probability 1/Z
`Sender 1 will also send a 1 and Z wiH be received, whfle wfth probability 1/Z
`Sender l wtl 1 send a 0 and 1 w;l 1 be received. But the channe 1 of f 19, 3 h
`·the
`familiar bin.ary erasure channel (in which a rec~ived 1 1s the "erasure symbol")
`with erasure probability 6 • 1/2 and capacity C • 1-6 • 1/Z, Thus, Shannon's
`noisy coding theorem ensures the existence of a coding scheme that will 11l0w
`Sender Z to send information at a rate Rz arbitrarily close to l/Z with arbi(cid:173)
`trarily sma 11 error probabi 11 ty, After the receiver has decoded Sender Z' s
`codeword, he can subtract it from the received sequence to obtain the uncoded
`sequence that was transmitted by Sender 1, The price of making Rz closer to the
`capacity 1/2 is an increasingly longer codeword length or, equivalently, a
`longer delay in recovering the infon11at1on at the receiver, The pc1nt (R
`,R
`) •
`1
`2
`{1/2, l) can, of course, be si111ilarly approached. By appropriately alternat1.ng
`between coding schemes, any point (Rl'Rz) on the capacity-reg1on boundary 11ne
`R1 + R2 • 3/2 between the points (1, 1/Z) end (1/2, l) can be approached.·
`
`1/2
`
`X2n
`
`1/2
`
`Y,.
`
`2 ·~
`
`0
`
`1/2
`
`0
`
`Fig.3 : The binary erasure channel seen by Sender 2 when Sender I
`Sf't1<ls r«n<lom binary <ligits OVC'r lhf' 2SRAC or Fig.1.
`
`Perhaps the best interpretation of the "wall" shown in Fig. l h as a prohibition
`against seizure of the channel by a single sender. If a single sender iS· allowed
`to control both x1n and x2n' then he can by choosing (XJn•Xzn) to be (0,0),(0, l)
`or (1, 1) cause Yn to be 0, 1 or 2, respectively, i.e .. he can create ·a noiseless
`ternary channel with capacity 1og
`3 (bits per use). By alternating appropr1atel~
`2
`between such seizures, two senders c:ould ac:hieve any point on the "sehure line"
`shown ~n Fig. Z that lies strictly outside the (seizure-prohibited) capacity
`. region.
`
`356
`
`Pet., Exh. 1017, p. 3
`
`

`
`~:
`
`J; ,
`
`J.L Mass~y
`
`Suppose now that there fs a feedback channel from the receiver to the two send(cid:173)
`en in Hg. 1 so that each sender learns the value of Yn 1nrnediately after x1n
`end Xzn have been sent.. The point. (R1,R2) • (1, 1/2) can now be achieved with
`the greatest of ease. Sender l still sends his raw Information bits (R1 • 1)
`so that Sender 2 still sees the binary erasure channel of ftg, 3, Sender 2,· how(cid:173)
`ever, can now (because of the feedback of Yn) simply send each of his 1nfonnation
`bih repeatedly until 1t 1s received "unerased", f,e., unttl Yn • 0 when this
`1nfon11~tton bit 1s a 0 or until Yn • 2 when this information bft is a l. Because
`the el"4sure probabi l1ty 6 is 1/2, Sender 2 wi 11 be sending tnfonnat ion at the
`rate R
`• 1-6 • 1/2 bits/use. Moreover, the average dehy between fint tl"4ns(cid:173)
`2
`•isston end successful tnnsrnfsston is only 2-1 • 1 time tnstent. Something even
`more remarkable, however, results from the 1vaf11b1l1ty of feedback (as was
`first shown by Gaarder end Wolf [l]): points outside the capacity region of
`fig. 2 can be achieved! This was quite surprising when first discovered because
`it had long been knovn that feedback could not Increase the capacity of a single(cid:173)
`sender Met110ryless channel. The actual capacity ·region of the 2SBAC with feedback
`was only recently detel"llllned by Wllle111s [2}: it differs froa the capacity region
`without f.eedback. shown in fig. 2. in that the boundary line between the points
`(1. 1/2) and (1/2. 1) is bowed slightly outward (but still well away from the
`"seizure line").
`
`The simple ZSBAC of fig. 2 ts a rich source of lessons about multiple-accessing.
`With its help, we have been able to illustrate all of tl-e following general
`principles of 111ultiple•access c011111unicat1ons:
`(1) Channel seizure, when possible, is the most effective way to utilize a
`,.u 1tip1 e-eccess channe 1.
`(2) When channel seizure 1s prohibited, time-sharing (or other types of channel
`division) generally is still sub-optimum in the sense that ft cannot be used
`to achieve all -points in the capacity region.
`(3) Feedback, when available, can be exploited lo reduce the coding delay and
`complexity required to achieve a given transmission rate.
`(4) When channel seizure is prohibited, feedback can also enlarge the capacity
`region.
`The first -~f these pr-inciples supports the-way that:computer-eommuni-cations .is
`carried ~ut tod~y. Virtually al\ newer local area networks (LAN's) operate on a
`channel seizure basis, sometimes ·with deterministic access (as in a token ring)
`and sometimes with random access (as in Ethernet). The third principle suggests
`that feedback will play an especially crucial role in random-accessing, because
`some kind of "coding" is absolutely necessary to overcome the losses due to
`access conflicts.
`
`3. THE ALOHA APPROACH TO RANC>a-4-ACCESSING
`
`. The ALOHA system, devised by Abramson {3] and his colleagues at the University
`
`of Hawaii, was the first random-access system: its approach underlies most
`present-day random-ac;cess systems, e.g. Ethernet. To i \ lustrate the ALOHA approach,
`we now describe the ALOHA system, including the modification of "time slotting"
`that was introduced by Roberts [ 4].
`
`Suppose that all data to be sent is in the form of "packets", all of which have
`the same length (measured in trllnsmission time on the seized channel) that we
`take to be the un.tt. o_f time. We define the time interval (n-1) ~ t < n to be
`the n-th channel "slot". "Time-slotting" means that senders can transmit packets
`
`357
`
`Pet., Exh. 1017, p. 4
`
`

`
`Rondom·Aec~u Communications
`
`only by beginning transmission at a slot boundary. Thus, transmitted packets
`from two senders w1ll either overlap completely at the receiver or not at all,
`
`The channel model postulated by Abramson was that. when Z or more transmitted
`packets overlap at the rece1ver, then they mutually destroy one another, but
`otherwise packets are received error-free. Moreover, there 1s feedback from the
`receiver at the end of each slot so that all users learn whether or not a col11-
`s1on occurred (collision/no-collision binary feedback).
`
`The Information-generation model postulated by Abramson was that of a very
`large number (essentially Infinite) of identical sources, each with an asso(cid:173)
`ciated sender, such that the number of new fnformatfon packets generated during
`any slot Is a Poisson random variable with mean ~ (packets/slot), independent
`of previously generated packets. The essentially Infinite number of senders
`means that access conflicts cannot be entirely avoided, i.e., random-accessing
`becomes a necessity. lln fact, the original operational ALOHA system had a very
`small number of transmitters so that random-accessing was a matter of choice,
`madt by Abramson and his colltegues for the e•press purpose of reducing access
`delay. I
`
`The r·andom-access protocol devised by Abramson was ingeniously simpl!i; A new
`packet must be transmitted in the slot irr111ediately following that in which it
`was generated. When a collision occurs.each "colliding" s·ender must retransmit
`1n a randomly-selected later slot. Each such sender, of course, independently
`makes this random selection of retransmission delay.
`
`Abramson's analysis of the ALOHA system was equally ingenious, if not rigorous.
`He postulated that the retransmission policy could be shaped in such a way that
`the number of retransmitted packets in any slot would also be a Poisson random
`variable. independent from slot to slot and independent of the new-packet ge(cid:173)
`n.eration process. with a mean of Ar (packets/slot). Because the sum of independ(cid:173)
`ent Poisson random variables is again Poisson, this implies that the fot11l
`number of p11dets transmffted in ani- slot f s al so a Poisson random voriab le with
`me11n >.t • >. + >.r. Because the throughput T of successful packets at the receiver
`Is the fract1on of slots in which exactly one packet is transmi tt~. it follows
`that t 1S just the probabi 1 ity that a Poisson rand0111 variable with mean >. t taltes
`on the value l, i.e.,
`
`(I)
`
`Equation (1), which 1S the so-called throughput equation for slotted-ALOHA,
`Is
`shown graphic11l ly in fig. 4, It is easy to check from (I) that t 1s maximized
`when >.t • 1 (packet/slot). which seems quite natural, and that this m11ximum Is
`
`t
`
`• e-l.,,. .36B (packets/slot),
`
`max
`which seems quite fundamental. lt is coll'rnOn to say that ,-l is the "capacity of
`the slotted-ALOHA channel", but, as we shall see, this de\cription is mtsleadtng.
`
`The reader may (and should) be disturbed by the fact that the new-packet arrival
`rate A appears nowhere in the throughput equation (I), To bring~ Into the pic(cid:173)
`ture, one must invoke the egui 1 lbteium hypothesis which states that packets are
`11nter1ng and leaving the system at the same rate, i.e ..
`
`.>..
`t •
`[ .. _.
`
`Pet., Exh. 1017, p. 5
`
`

`
`J.L. Ma.u~y
`
`Fic.4: Graphical depiction of the throughput equa.lion for slotted-ALOHA.·
`
`~.
`
`This seems similar to the constancy assumption for the retransmission rate, but
`in fact neither assumption implies the other.The equilibrium hypothesis is real(cid:173)
`ly an expression of the hope that the ALOHA system is stable,. i.e., that the
`queue of packets awaiting retransmission is not steadily growing at a positive
`rate A-t (packets/slot). Such a positive growth rate is not inconsistent with
`a constant retransmission rate if the retransmission delay is chosen randomly
`in a way to.depend on'how many times the given packet has been previously trans(cid:173)
`mitted unsuccessfully. The equilibrium hypothesis should in fact be called the
`stability hypothesis for ALOHA.
`
`It is easy to argue from Fig. 4 that the ALOHA system cannot be stable for a
`retransmission policy that does not take into account the number of previous un(cid:173)
`successful transmissions. Suppose that the arrival rate A satisfies A < ,-l as
`shown in Fig. 4. If equilibrium prevails. then the traffic rate At will be Atl
`i!i. of course an "average" rate and, over any fhed
`as shown 1n fig. 4 •• Thi_s
`length interva 1. the actual ra!-e wt 11 fluctuate about this mean. If the actua 1
`traffic rate moves a little above Atl' the actual throughput in-creases a·Httle
`above A. Thus, packets leave the system faster than they arrive, which causes
`the_actual traffic rate to move back down to Atl' Hence, the point (t,At) •
`(A,Atl) ts a conditionally stable point. t.e •• it is stable under small flue~ ..
`tuations. But if a large fluctuation causes the actual traffic rate to move to
`the right of Atl in Fig. 4, then the actual throughput decreases below A. Thus,
`packets leave at a slower rate than they enter, which causes a further increase
`in the actual traffic rate, a further decrease in actual throughput. etc. The
`system never returns to the point (A,At 1). but rather drifts relentlessly to(cid:173)
`ward the catastrophic "unconditionally stable" point (t,\) .. (0,..,). The~
`mum stable throughput of a fixed-pol icy ALOHA system is O.
`
`The virtue of the ALOHA approach 1s its simplicity, its Achilles' heel is its
`instability. In fact, it is possible to devise retransmission policies that
`stabilize an, ALOHA system, cf. [5], but the protocol then loses its simplicity.
`Most practical" ALOHA-type random-access systems appear fn fact to be unstable.
`These systems incorporate some kind of time-out feature that switches the system
`to a~~~n-random type of acc~ssing to clear away the backlog of traffic when the
`channel ~s jammed wfth collisions, then switches back again to the basic ALOHA
`protocol. Again this means some loss of simplicity in the access protocol, as
`well as some performance anomalies. Published simulations of ALOHA-type systems
`
`Pet., Exh. 1017, p. 6
`
`

`
`R.afldom·Accas Communications
`
`1nvariably appear to have been purged of any anomalies, tf tndeed eny occurred • .
`.
`.
`I
`In fact, there is usually very little tnformatton provJded wtth such stmulaltons
`about what total time period was s1rnulated, whether time-out 11rovistons were
`included. etc •• so that H h genera\\y very difficult. to detenntne the reel
`mun1ng of the simulated performance results that are presented.
`
`4, COLLISION-RESOLUTION ALGORITHMS
`
`Concern over the lnstabt lily of most ALOHA-11ke protocols led s~ researchers
`to search for random-access schemes that were provably stable, The breakthrough:
`1n these efforts was made 1n 1977 by J, Capetanaltis (6), then an K, l, T. doctoral
`student working with Prof. R. Gallager. and independently achieved sho~tly ther~­
`afler by two Soviet researchers, 8. Tsybaltov and V. Mik~a1lov (7}. The essence
`of their contribut.tons was tile "collis1on-resolut1on approach" to rand0111-11ccen-
`1n9, which we now consider.
`
`.s that for
`the same
`The channel model anumed for collision resolution 1s
`slotted-ALOHA, namely a time-slotted colltston-type channel wtth sQl'le fona.of
`feedback to the senders at the end or each slot. We., wtl l auume the sa111e b.1.nary
`(colltsion/no-collision) feedback es for slotted-Aloha (as Capetanalr.is also
`assumed: Tsybaltov and Hllthailov considered tetnary (co\ltston/sucun/idl~)
`r·eedback]. The information-generation model 1s the ume ·U for slotted-ALOHA,
`i.e .. euenlially-infinttely many identical sources. each v1th an usociated
`sender, such thal the number of new packets generated in each slot is en inde(cid:173)
`pendent Poisson random variable with mean ~.
`
`A collision-resolution algorithm can be defined as 1 random-access protocol such·
`the.t. whenever e. collision occurs, then at some later time (provided A ts not
`too large) all senders will simultaneously learn from the feedback information
`that all packets 1nvolved in that collision have now been successfully trans(cid:173)
`mitted. The cru• of collision resolution is the uploitatton of the feedbaclt
`information to control the "random" retransmission process 1n such a w':y that
`chaotic retransmission can never occur. Because there 1s no upper bound on the
`number _ of packets that initially coll1de, 1t was not at all obvious that co11t(cid:173)
`sion-resolullon al9orltlims otsted-before.-.the Hrs~ such al.9ortthms were pre(cid:173)
`sented by Capetanak; s and by Tsybaltov and H11tha11.ov.
`
`As an example of a collision-resolulton algorithm, we now describe the b.inary
`stack algorithm. which is enentially Capetanaltts' binary "tree a19orHhm".
`but we prefer the terminology "staclr. algorithm" introduced by Tsybaltov and
`H1khailov. The tenninolOi,ly "binary" stems frcxn the fact that every st"der is
`11ssu111ed to have a fa\r "t>inary cotn"(with "O" on one side and "1" on lht olhe~)
`Yhich he flips whenever his packet ts tnvolved in a co11tston. The term "~lack"
`comes from the fact that ont can conventently visualize the operation of the
`a 19ori th"' in ter"'s of the conceptua 1 stack shown in Ftg. S.
`
`Suppost at the outset that the st.ad. ts empty, i.e •• that S "0. Suppose also
`that the access gate is opened and some number X of senders then enter the
`"current send\n9 bo•"· which ts just the conceptual location of all senders who
`Yi l 1 send pac~ets in the current slot. Perhaps X • Z or X • 0 or oen X •
`6 ,. 1023:
`for the moment, we assume only that X?. Z so that a collision ("C")
`occurs in this slot. Then these colliding senders flip their binary coins,
`th:Se •ho flip "O" ret11ai" in the "current. sending box" (1.e., they ' again lrans-
`111it in the ne•t slot) while those who flip "1" are pushed dO'lln (conceptua.J~y)
`
`L.'
`
`360
`
`Pet., Exh. 1017, p. 7
`
`

`
`J.L /tltWtY
`
`into level 1 of the stack, The stack size ts now S • 1. The general rule is: ;f
`"C", theJI S .. S • 1. One seu that. now about X/Z of the ortg1na l X co 11 tding
`senders vtll reinatn tn the "current sending box" wh11e about X/Z w111 be pushed
`down into the st.eek. for the -nl, we asst.let the bloclttd-access protocol,
`which states that the "access gate• ts c~osed at the tniti~t colttston and
`reaatns closed until all senders ll!arn that the original X colltdtng paclt!ts
`have all been successfully transMitted. The sa111e process of stack growth and
`conc0111itent "thinning out" of the "current sending box" continues until the
`feedback "no-coll is ton" ("NC") occurs, which means that et ther 1 sender or none
`had been in the .. current sending bot". This ts the s igna 1 for the stack to be
`pushed upward one level so that senders who were ;~ level 1 of the conceptual
`stack are now again in the "current sending box" and the stack stze ts reduced
`by 1. The general rule 1$: 1f "HC" and S > 0, then S + S - 1. After sel9e t.h1e,
`because the above process wt11 "thin out" crowded levels tn the stack, the stack
`she wtll again reach S .. O. If now no collision occurs, this 111tans that all of
`the original X senders 1111st have successfully sent their packets. (If a colli(cid:173)
`sion occurs. the previous process continues.) The general rule ts: if "kC" and
`S • 0, .. then the collision is resolved.,
`
`"C" and "O"
`
`CURRENT
`
`SENDING BOX
`
`i - - - - - i ACCESS
`GATE
`
`World of
`Senders
`
`"C" and "l"
`
`"NC"
`
`CONCEPTUAL
`'STACK
`-
`
`Levd l
`
`Level 2
`
`Level S
`
`~"C"
`L.::_:j--"NC"
`
`STACK SIZE COUNTER
`
`Fig.5 : Conceptual diagram of the "bin•ry •t•d •l11>tit~m" ___ _
`for collision resolution.
`
`The binary stack algorithm is clearly simple lo implement. When involved 1n a
`collision, a sende.- need only generah a binary random variable ("O" or "1"}
`so a minimum of retransmission "randomization" is required. His only other re(cid:173)
`quirements are to maintain two counters, one of which gives his own position tn
`the stack (if he were e party to the collision) while the other
`keeps track
`of the stack stze S so that he knows when the collision has been resolved. The
`big question of course ts: how effective is this random-access protocol?
`
`Perhaps the main theoretical advantage of the collision-resolution approach
`over the ALOHA approach to random-:-accessing
`i~ that the former lends itself to
`precise (and reasonably simple) analysts as we now demonstrate for the binary
`stack algorithm with blocked-access. Letting Y be the number of slots needed to
`resolve the original collision of X senders, then the quantity of principal in(cid:173)
`.. E (YI X • NJ, the average number of s 1 ots needed to reso 1 ve a
`te;'eSt' is LN
`collision of N transmitters. We see that Lo• L1• 1 as then there is no initial
`
`!.. ••
`
`361
`
`Pet., Exh. 1017, p. 8
`
`

`
`-Arras Communlcotlo111
`
`collhion. w, see furth'r that
`1
`1
`.
`t 2 • l +~Clo+ L2> • 1 (L 1.+ t 1>
`as. after the initial tolHsion, w1th .probabtlity 1/2 the two senders w11.1 fltp
`the same b1nary numb'r leaving no one in the "current sending box" ·and both
`1n level 1 (or vice verso), while with probability 1/2 they will fltp different
`binary numberr. leaving 1 r.'nd'r in the "current sending box" and 1 se,nder tn
`level 1 of the stacli:. Solving for L
`2 gives
`t 2 • s
`~lots required on the average lo resolve a collision of Z packets, It ~s easy
`lo write the general r,cursion for LN end to show that the solutton sat1sftes
`LN
`1
`Z.8810< N + R < 2.8867,
`
`N?:. 4:
`
`(2)
`
`the interested reader is referred to (8) for details of thts argu111ent~ The con(cid:173)
`clusion lo be drawn from (2) 1s quite remarkable: whenever the tntttal co111ston
`is moderately large, then just about 2.89 slots wtll be requtred to "service"
`each of the packets involved in this 1nittal collision. Thts means that the
`algorithm ,.n1 be stable (the "serv,r" will not drop flopelessly behind in ser(cid:173)
`ving customers) provid'd only that
`
`l. ~ dm 1:1
`
`.346 (packets/slot)
`
`whereas it will be unstable if
`1
`~ 2.8iITO
`
`:: .347 (packets/slot).
`
`Thus, the maximum stable throughput of the b~nary stack algorithlll with blocked(cid:173)
`access is just ~bout .346 packets/slot. Moreover, thts stablltt.y holds not only
`for the assumed P~ l sson arrive l process, but .Jor ~trtua lly any arrival process
`that con be characterized by an average arrival rate .1. (packe.ts/slot). This
`robustness (or, equivalently, insensitivity to the statistics of the arrival
`process) is, or should be, en attractive practical feature of 11111ny col11sion-
`_reso l_u~.ion algorithms.
`
`To uamine the role placed by the "blocked"."acceis protocol" 1n . ihe aliove analysts,
`we first obs,rve that the binary steck al9or1thnl never makes any assumption in
`advance ebout the occupancy of the "current sending box" or any of the S stack
`levels. There could Just as well be none or 6 1t 1023 sender-s tn any of these
`loca(ions as far as the binary slack algor1thln ts concerned. This means that
`there is no reason to block new senders frOlll entering the "current sending box''
`at any time. The free-access protocol leaves the "access gate" of Fig, 5 open
`at all times. Free-access has the practical advantage that senders need to
`monitor the channel feedback only after they becOllle "act-+tt" in the trensmilting
`process. Intuition suggests that free-access should also give a better· through(cid:173)
`put· than blocl:.ed-access. Unfortunately, free-access also com~Hcates .. the analysts,
`but Mathys and Flajolet have shown that the binary stack algoritlva with free(cid:173)
`access · has a maximum stable throughput of .1. • .360 (packets/slot),. Hore sur(cid:173)
`prisingly, they showed a ho that the ternery stack algorithm (in which ; s~nders
`flip a fair three-sided coin after a collision, moving into levels 1 or 2 1f
`. t~ey flip "1" or "Z" "hile S ts increased by 2) wfth free-access has an even
`larger mu imum st.ab le throughput of I
`
`" • .401 (packets/slot).
`
`Pet., Exh. 1017, p. 9
`
`

`
`J.L J.l4UtY
`
`(Because this Miili- stable throughput exceeds e-l tt:: .368, we see that it is
`tndefensible to call e-1 the "capacity of the slotted-ALOHA channel".) Hathys
`and Flajolet also s~ that this ternary stack algorHhll wtth free-access
`has a better delay vs. throughput characteristic than does etther the binary
`staclr. 1l90rilt• or the usual ALOHA 1l90ritt. (when analyze.d ass1.111ing opti•htic(cid:173)
`ally that the ~uiltbri1111 hypothesis holds. (9)
`
`Many other collision-resolution algorithms have been proposed that have ma11.tmum
`stable throughputs e11.ceeding .401 (packets/slot) -- the current record for binary
`(col1ision/no-co11ision) feedback is ,4493 packets/slot {\OJ. However, the
`ternary stack 1 l90ritt. with free-access appears to us to be the best pract ica 1
`cho1.ce by virtue of th sil1plicity. its robustness and its relatively Mgh
`iaaxiinun1_ stable throughput. [t also seems to us to be a
`better practical
`choice than any ALOHA-like algorithm for randOl'l-accessing on the collision
`channel with feedback, and we wonder why algorithms of the latter type are still
`being proposed for new randon1-access systems.
`
`The reader interested in delving llOre deeply into the 111atheaiatics needed for a
`precise analysts of collision-resolution algorit!Vlls will find the recent book
`(11) by Hofri to be a useful source of information.
`
`S. UPPER BOUNDS Off KAXIMUH STABLE THROUGHPUT
`
`Our discussion of collision-resolution algoritlllls 111y have raised the question
`1n the reader's mind: what h
`the capacity of the collision channel with feed(cid:173)
`back or, equivalently. what ts the largest possible maximum $table throughput
`that can be. achieved for Poisson arrivals? It is known that the answer depends
`in general on the kind of feedback available so we continue to consider only
`binary (coll is ion/no-co 1 tis ion) feedback. SOl!le ingenious and comp lex arguments
`·have been used-to obtain upper bounds on the mu1mum stable throughput. Rather
`than describing the best bound, 'We illustrate the genera 1 idea by descri~1n9
`a very simple bound due to Kelly [12].
`
`Kelly's ·bound actually applies only to elgonthms (such as the ALOHA algorithm
`or any collision-resolution algorithm with free-access) with the immediate(cid:173)
`firsf-trarismfS.sion property that'"a newly-gener-ated packet must be tr4ns111itted
`in the slot imediately following that in which it was generated. Suppose such
`an algorithm iS operating stably for Poason new arrivals with a mean of J..
`(packets/slot). Let pr be the fraction of slots in which at least one packet
`1s retrans111itted. Then, because the number of new senders in any slot is inde(cid:173)
`pendent of the number of retransmitted packets in that slot, it follows that
`the fraction of slots with exactly one paclcet (i'.e., the throughput t)
`satisfies
`
`T ~ Ae-).(1-p )+ p e-).
`r
`r
`with equa 1 ity when at most 1 paclcet is retransmitted in any slot (i.e., per(cid:173)
`fect scheduling of retransmissions). But stability implies t
`.\ and thus ·
`.\~ .\e-).(1-p) + p -.\
`·
`r
`r
`if the system is stable. It is read11y checked that the choice pr • 1 maximizes
`A for which (3) can be satisfied. Thus
`
`(3)
`
`•
`
`1; ,equired for stability. The largest ~satisfying (4) is Kelly's bound on
`
`( 4)
`
`363
`
`Pet., Exh. 1017, p. 10
`
`

`
`Random-Accm Communications
`
`11aximum stable throughput, namely
`
`>.max~ • 5671 packets/slot,
`
`'"'' (S)
`
`that holds for any random-accus al9or1thm with inmediate-first-transmtssion.
`In fact, our argument has never used the assumption of binary (co 1l is ion/no.,..
`collision) feedback so that Kelly's bound (S) applies to any random-access
`algorithm with i11111ediate-first-transmission on the collision channel with any
`kind of feedback.
`
`By usin9 simHar but much more intricate arguments, Tsybakov and Likhanov (13)
`have recently proved that, for any random-access algorithm, the 1111x i