SOME NEW APPROACHES TO RANDOM-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 accomplish unsched(cid:173)
`uled 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. collision-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 lhat are briefly discussed. Two new
`approaches to random-accessing without feedback information 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
`are generously used throughout the paper, and some speculations on
`the practicality 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
`
`general.
`
`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 multiple-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)
`seizure scheme is a token-ring in which. when the ''token" orrives 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 att~mpt 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
`relies on the access protocol to repair the damage when he encounters "bad luck",,..
`
`In some c~unication scenarios (as we shall see later), access confl1cts 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 demand that ·a sender always wait for a guarantee of e•clusive
`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
`
`

`
`J.L MOJSty
`
`light., the bold sender will be almost sure to succeed fn his gamble for access
`and can thus avoid the delay that a timid sender would incur. The primany pur(cid:173)
`pose o ( random-access f ng 1s to reduce the delay between the time that a sender
`obtains en foformatfon input and the tfme that he transmits this fnformatfon
`successfully .over the channel. Random-accessing fs a gamble, but one in .which
`the odds can be on the side of the pla}'er rather than on the std• of the "house".
`
`In Sect.ion 2 of this paper, we show why channel seizure is generally preferable
`to channel dfvhion for multiple-accessing, and we examine the role of channel
`feedback infonnation. Section 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, viz. collision resolution, and we contrast it with
`the ALOHA approach, Section S considers certain 9eneral bounds on the through(cid:173)
`put of random-access schemes. Section ·6 describes two new approaches to random-
`1ccessin9 without feedback . Some concluding remarks are given in Section 7,
`
`Z. SC»4E GENERAL MULTIPLE-ACCESS PRINCIPLES
`
`The sh•plest ~ultiple-access channel is surely the two-sender binary adder
`~ (ZSBAC) shown in fig, 1, Each lime instant •. each sender sends · a binary
`digit (0 or l) and the received ·digit is the sum (0, 1 or 2) ~f these two
`nU111bers. 1. e ••
`
`Yn • xln + Xzn
`where x1n and Xzn are the binary digits sent by senders 1 and 2, respectively,. ·
`at ttme n and Yn
`is the re"ceived dtgtt. The "wall" shown between the two se.nders
`in fig.
`signifies that ·the user on one side ts not privy to the infoM!lation
`to be sent on t he other ~ tde. a I though the two users are allowed in advance to.·
`have fo~ulated a .conmen strategy for sending this infonnation.
`
`-~~:;.· .;·7·...,._>,,
`·l"
`
`J
`
`Y,.
`
`Fic.1 : The two-sender binary adder channel (2SBAC)
`X,,. E {O,l},X2,. E {O, I}, Y .. E {O, l,2}
`
`...
`'
`
`Fig. 2 shows the pentagonal "capacity region" of the ZSSAC, i.e., the region
`of rate pairs (R1, Rz) such that Sender l can send data at the rate R1 {bits
`per channel use) and Sender 2 can send at the rate R2, both with arbitrarily
`small error probability.
`It ts easy to s~e 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) so that
`Y • x1 , and hence Sender l can directly send his "raw" i nformation· bits over
`n
`n ·
`the channel with no need for coding (R1 • l). The point (R1,R2) • (0, 1) can be
`similary achieved. By agree i ng to alternate between these two schemes for ap(cid:173)
`P~~riate periods, Senders 1 and 2 can achieve any point CR1,R2) such that
`+ Rz • 1, t.e .. at any point on the "time-sharing line" shown in ft9. 2.
`R
`1
`
`355
`--· --~-----··-~---~------------- ~·--~- · -·--······--------~---------·-··~·----...
`
`~ .. · ' ~i· lti'>!
`
`P'.
`
`. ------ ·-
`
`:
`
`' .....
`
`-. , ..
`
`Pet., Exh. 1017, p. 2
`
`

`
`Ra"'lom·Atcm Con1111unlrotlo11J
`
`R 2 (bita/u1e)
`
`Fis.2 : Capacity Region o{ the 2SBAC of Fig.l
`
`It 1s almost as easy to see how the point (Rl'Rz) • (1, 1/2) on the capaclty(cid:173)
`re91on boundary can be approached. St!nder 1 transmits his raw 1nfof'lllat1on b1ts
`(R 1 • 1). This causes the channel seen by Sender 2 to be lhtt shown in fig. J,
`because. for Instance. if Sender Z should send a l then wtlh probabiltty 1/2
`Sender 1 will also send a 1 and 2 wiH be received, whfle wfth probability 1/2
`Sender l wll l send a 0 and 1 w;l 1 be received. But t.he channe 1 of f tg. 3 ts ·lhe
`fam;l1ar bin.ary erasure channel (1n which a rec~ived 1 ts the "erasure symbol")
`with erasure probability 6 • 1/2 and capacity C • 1-6 • 1/Z, Thus, Shannon's
`noisy coding theorem ensures the eAist.ence of a coding scheme that will 1ll0w
`Sender Z to send information at. a rate Rz arbitrarily close to 1/2 with arbi(cid:173)
`trarl ly small error probability. After the receiver has decoded Sender 2's
`codeword. he can subtract it from the received sequence to obtain the uncoded
`sequence that was transmitted by Sender 1. The price of maktng R2 closer lo the
`capacity 1/2 is an Increasingly longer codeword length or, equivalently, a
`) •
`,R
`longer d~lay in recovering the infonaatlon al the receiver .• The paint. (R
`1
`2
`(1/Z, 1) can, of course, be siniihrly approached. By a~propriately alt.ernat.1.ng
`between coding schemes, any point (R1,Rz) on the capacity-region boundary line
`3/Z between the points (1, 1/2) and (1/2, 1) can be approached. ·
`R1 + R2
`
`Y,.
`
`1~2
`~ 0
`
`1/2
`
`0
`
`fig.3 : The binary erasure channel seen by Sender 2 when Stndtr I
`S<:"tHls r«nnom binar.v digits OVC'f th<:> 2SRAC or Fig.l.
`
`Perhaps the but interpretation of the "wall" shown 1n Fig. 1 1s es a prohib1t1011
`against seizure of the channel by a single sender. If a single sender iS· allowed
`to control both x1n and Xzn•
`then he can by choosing (Xin•Xzn) lo be (0,0),(0, 1)
`or (1. 1) cau~e Yn to be 0, 1 or Z, respectively, i.e., he can create ·a noiseless
`3 (bits per use). By alternating appropriatel~
`ternary channel with capacity log2
`between such seizures, two senders could achieve any point on the "seizure line"
`shown tn Fig. Z that lies strictly outside the (seizure-prohibited) capacity
`. region.
`
`L_'
`
`356
`-· .. ·-·---·-· - .. . ..... , _____ ·····---·-- ---~----·- · -···-·-·· ....... .. . _. ·---------------- -·---.. -------~-...... .
`
`Pet., Exh. 1017, p. 3
`
`

`
`l; ,
`
`J.L Mass~y
`
`Suppose now that there 1s a feedback channel from the receiver to the two send(cid:173)
`el"S. tn Hg. 1 so that each sender learns the value of Yn tnrnediately after x1n
`end Xzn have been sent. The point (R1,R2) • (1, 1/2) can now be achieved with
`the greatest of ease. Sender 1 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 hts tnfonnation
`bits repeatedly until 1t 1s received "unerased", f,e., unttl Yn • 0 when this
`tnfol"lll~tton btl 1s a 0 or until Yn • 2 when this tnfonnat1on bft is a l. Because
`the el"4sure probabt l1ty 6 1s 1/2, Sender 2 wi 11 be sending tnfonnat ton at the
`rate R2 • 1-6 • 1/2 bits/use. Moreover, the average dehy between ftnt tl"4ns(cid:173)
`•fsston end successful transmfsston ts only 2-1 • l ttme tnstant. Something even
`more remnkable, however, results from the availability of feedback (as was
`first shown by Gaarder and Wolf [1]): points outside the capacity region of
`fig. 2 can be achieved! Thts was qutte surprising when first discovered because
`tt had long been knovn that feedback could not increase the capacity of a stngle(cid:173)
`sender Met110ryless channel. The actual capacity ·region of the 2SBAC with feedback
`was only recently detel"lllined by Wille111s [2}: it differs froa the capacity region
`without f.eedback. shovn in fig. 2. tn that the boundary line between the points
`(l. 1/2) and (1/2. 1) is bowed slightly outward (but sttll well away from the
`"seizure line"}.
`
`The stmple ZSBAC of ftg. 2 ts a rtch source of lessons about multiple-accessing.
`With its help, we have been able to illustrate all of tl-e following general
`principles of aulttple•eccess c011111unicettons:
`(1) Channel seizure, when possible, ts the most effective way to utilize a
`8ultiple-access channel.
`(2) When channel seizure ts prohibited, time-sharing (or other types of channel
`diviston) generally is still sub-opttmum in the sense that tt cannot be used
`to achieve all -points in the capacity region.
`(3) feedback, when available, can be exploited to reduce the coding delay and
`complexity required to achieve a given transmission rate.
`(4) When channel seizure ts 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 all 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 illustrate the ALOHA approach,
`we now describe the ALOHA system, including the modification of "time slotting"
`that was introduced by Roberts [4].
`
`Suppose that a 11 data to be sent 1 s in the form of "packets", a 11 of which have
`the same length (measured in transmission time on the seized channel) that we
`take lo be the untt.o! 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
`
`

`
`Random-Acau Communlcatl-Oru
`
`only by beginning transmission at a slot boundary. Thus, transmitted packets
`from two senders w1ll etther overlap completely at the receiver or not at all,
`
`The channel model postulated by Abramson was that. when 2 or more transmitted
`packets overlap at the receiver, then they mutua 1 ly destroy one another, but
`otherwise packets are rec·etved. error-free. Moreover, there is feedback from the
`recetver at the end of each slot so that all users learn whether or not a co111-
`ston occurred (collision/no-collision binary feedback).
`
`The 1nformat1on-9eneratton model postulated by Abramson was that of a very
`large number (essentially Infinite) of identical sources, each with an asso(cid:173)
`ctated sender, such that the number of new fnformat ion packets generated during
`any slot Is a Poisson random vartable wtth mean l (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 necess1ty, lln fact. the original operational ALOHA system had a very
`small number of transmitters so that random-accessing was a matter of choice,
`made by Abramson and his colleagues for the e•press purpose of reducing access
`delay. j
`
`The r·andoin-access protoco.1 devised by Abramson was ingeniously simplJt: A new
`packet must be transmitted in the slot irrtnediately following that tn which it
`was generated. When a collision occurs.each "colliding" sender must retransmit
`In a randomly-selected later slot. Each such sender, of course, independently
`makes lhts random selection of retransmission delay.
`
`Abramson's analysis of the ALOHA system was equally ingenious, if not rf9orous.
`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 frOfn slot to slot and independent of the new-packet ge(cid:173)
`n.eralion process, with a mean of lr (packets/slot). Because the sum of independ(cid:173)
`ent Poisson random variables is again Pofsson, this implies that the fotal
`number of packets n·ansmftted in an)'-slot Is also a Poi sion random variable with
`mean lt • A + Ar. Because the throughput t of successful packets at the recefver
`ls the fraction of slots in which exactly one packet is transmitted, it follows
`that t
`fs just the probabilfty that a Poisson random variable with mean "t takes
`on the value 1, i. e. ,
`
`(I)
`
`Equation (1), which is the so-called throughput equation for slotted-ALOHA, is
`shown graphically in fiq. 4, It is easy to check from (l) that t 1s maximized
`when At • l (packet/slot), which seems qufte natural, and that thts maximum ts
`
`t
`
`- e-I c:r . 36B (packets/slot),
`
`max
`which .seems quite fundamental. It h corrrnon to say th6t e-I is the "cep4city of
`the slotted-ALOHA channel", but, as we shall see, this descriptfon h
`ll'islead1ng.
`
`The reader may (and should) be disturbed by the fact that the new-packet arr1val
`rate A appears nowhere in the throughput equation (I), To bring~ Into the plc(cid:173)
`ture, one must invoke the equilf!tt:ium hypothesis whtch states that packets are
`enterfng and leaving the system 11t the same rate, i.e .•
`
`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 < e- 1 as
`shown in Fig. 4. If equilibrium prevails. then the traffic rate At will be Atl
`as shown 1n fig. 4 •• Thi_s 1s of course an "average" rate and, over any f1Xed
`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·-Jittle
`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) is 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-policy 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.t1fldom·Accas Communications
`
`1nvarlebly appear to have been purged of any anomalies, If indeed any occurred • .
`.
`I
`In fact, there 1s usually very little tnfonnetton provJded wtth such simulations
`about what total time period was simulated, whether time-out provistons were
`included. etc •• so that it ts generally very difficult to detenntne the real
`meaning of the simulated performance results that are presented.
`
`4. COLLISION-RESOLUTION ALGORITHMS
`
`Concer.n over the 1nslabl hty of most ALOHA-11ke protocols led SOl!le researchers
`to search for random-access schemes that were provably stable. The breakthrough :
`In these efforts vas made In 1977 by J, CapelanaHs {6), then an K. l. T-. doctoral.
`student working with Prof. R. Gallager, and 1ndependently achieved shortly ther~­
`after by two Soviet researchers, 8. Tsybakov and V. K1k~a1lov (7J. The essence
`of thetr contrlbu~lons was t~e "collis1on-resolul1on approach" lo randll'ft-access(cid:173)
`ing, which we now consider.
`
`as that for
`the same
`The channel rnodel assu~d for collision resolution 1s
`slotted-ALOHA. na~ly a lime-slotted collision-type channel with seine fonn.of
`feedback lo the senders at the end of each slot. Wt, wtl 1 assume the Hiiie M.nary
`(collision/no-collision) feedback as for slotted-Aloha (as Capetanalr.ts also
`assu~d; Tsybalr.ov and Mtlr.haHov considered te1'nar:y (colHs'\on/success/idl~)
`r'eedbad:J. The tnfonnation-generat1on 1110del fs the same · IS for slotted-ALOHA.
`I.e .• essenltelly-infinilely many identical sources, each v1th an associated
`sender, such that the number of new packets 9enerated 1n each slot is an Inde(cid:173)
`pendent Poisson random variable with mean l.
`
`A collision-resolution algorithm can be defined as a random-access protocol such ·
`that. whenever a collision occurs, then at some later lime (provided A is not
`too large) all senders will simultaneously learn from the feedback information
`that all packets involved in that collhion have nov been successfully trans(cid:173)
`mitted. The cru• of collision resolution ts the e~plottat'\on of the feedback
`information to control the "random" retransmission process 1n such • w~y that
`chaotic retransmission can never occur. Because there .ts no upper bound on the
`number. of packets that initially collide, 1t was not at all obvious that collt-
`s ion-reso lutton al gor I thm.s u i sled-before-.th~ first.. such algorithms were pre(cid:173)
`sented by Capetanab s and by Tsybakov and H11r.ha11.ov.
`
`As an example of a collision-resolution algorithm, we now describe the b~nary
`staclt algorithm, which is essentially Capetanaka' binary "tree algor;t,hm".
`but we prefer the terminology "staclr. algorithm" introduced by hybalr.ov and
`H1khailov. The terminology "binary" stems fr()(ll the fact that every st"der is
`assu111ed to have a fa'ir "Mnary coin"(wtth "O" on one side and "1" on the olhe~) ·
`Yhich he flips whenever his packet Is fnvolved in a collision. The term !'~tack"
`comes from the fact that one can conveniently visualize the operation of the
`algorithm in terms of the conceptual stack shown in Fig. 5.
`
`Suppos·e at the outset. that the stac\:. ts empty, 1.e •• that S "0. Suppose also
`that the access gate is opened and some number X of senders then enter the
`"current send\ng bo~". which is just the conceptual locat1on of all senders vho
`will send pac~ets in the current slot. Perhops X • Z or X • 0 or even X •
`6 x lOZJ: for the moment, we assume only that X?. Z so that a collision ("C")
`occurs In this slot. Then these colliding senders f11p their binary coins,
`th:Se l)ho flip "O" re<11a i n in the "current send1ng box" (i.e •• they again trans(cid:173)
`mit in the next slot) while those vho flip "t" art pushed down (conceptu~,1~1)
`
`L.'
`
`360
`
`Pet., Exh. 1017, p. 7
`
`

`
`J.L /tltWtY
`
`into level 1 of the stack, The slack size ts now S • 1. The general rule is: if
`"C", the_ll S .. S • 1. One sees that. now about X/Z of the ortg1nal X colliding
`senders vtll remain tn the "current sending box" wh11e about X/Z w111 be pushed
`down into the stack. for the -nl, we asst.let the bloclttd-access protocol,
`which states that the "access gate• is c~osed at the tn1t1~t colttston and
`reaatns closed unt11 all senders l~arn that the original X colltdtng pack,ts
`have all been successfully transMitted. The sa111e process of stack growth and
`conc0111itant "thinning out" of the "current sending box" continues until the
`feedback "no-coll is ton" ("NC") occurs, which means that either 1 sender or none
`had been in the "current sending bot". This ts the signal for the slack to be
`pushed upward one level so that senders who were i~ 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 ts: tf "HC" and S > 0, then S + S - 1. After s09e tt11e,
`because the 1bove process wtll "thin out" crowded levels tn the stack, the stack
`size will again reach S • O. If now no collision occurs, this 111tans that 111 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 is: if "kC" and
`S • 0, .. then the co 11 is ton is resolved.,
`
`"C" and "O"
`
`CURRENT
`
`SENDING BOX
`
`i - - - - - i ACCESS
`GATE
`
`World of
`Senders
`
`"C" and "l"
`
`"NC"
`
`Levd l
`
`Level 2
`
`CONCEPTUAL
`'STACK
`-
`
`~"C"
`L.::__:j-- "NC"
`
`Level S
`
`STACK SIZE COUNTER
`
`Fig.5 : Conceptual diagram of the "bin•ry •t•d •'1t>tit~m" __ . .
`for collision resolution.
`
`The binary stack algorithm is clearly simple to implement. When involved 1n a
`collision, a sende.- need only generate 11 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 in
`the stack (H he were a party to the collision) while the other
`keeps track
`of the stack size S so that he knows when the collision has been resolved. The
`big question of course is: how effective is this random-access protocol?
`
`Perhaps the main theoretical advantage of the collision-resolution 1pproach
`over the ALOHA approach to random-:-accessing
`i~ that the former lends itself to
`precise (and reasonably simple) analysis 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(YIX •NJ, the average number of slots needed to resolve a
`terest' is LN
`collision of N transmitters. We see that Lo• L1• 1 as then there is no, initial
`
`!.. ••
`
`361
`
`Pet., Exh. 1017, p. 8
`
`

`
`,,tun' Communlcotlom
`
`1
`1
`.
`L2 • l + ~ (L0 + t 2) + ~ (L 1 + t 1>
`as, after the ;nitial tollision, w1th .probab1lily 1/2 the two senders v11 .1 flip
`the same binciry number leaving no one 1n the "current sending bo1t" ·and both
`in level 1 (or v1ce verso), while wtth probabtltt~ 1/2 they will flip different
`binary numbers leaving l sender 1n the "current sending bo1t" ond 1 se,nder 1n
`level l of the stack, Solving for lz gives
`t 2 • s
`slots required on the average to resolve a collision of Z packets, It ~s easy
`to write the general recursion for LN end to show that the solution satisfies
`lN
`l
`2.8810< "ll + N < 2.8867. N ~ 4:
`the tnterested reader Is referred to (8) for details of this argument~ The con(cid:173)
`clusion to be drawn frOftl (Z) ts quite refllarkable: whenever the initial collision
`h moderately large, then just about 2,89 sloh will be required to "service"
`eoch of the packets lnvolved in this initial collision. This means that the
`algorithm will be stable (the "server" will not drop flopelessly behind in ser(cid:173)
`ving customers) provided only that
`
`(2)
`
`l. ~ rim ::r .346 (packets/slot)
`
`whereas it w\11 be unstable ff
`1
`~ ~ 2:88iQ
`
`:: .347 (pockets/slot).
`
`Thus, the maximum stable throughput of the b.inory shd algorithm with bloded(cid:173)
`access is J.ust ~bout .346 packets/slot. Moreover, this stability holds not only
`for the anumed P~i sson arrival protess. but .. for ..,1rtua Hy any arrive l process
`that can be characterized by an average arrival rate .\ (packets/slot). Thts
`robustness (or, eQuivalenlly, Insensitivity to the statistics of the arrival
`process) h, or should be, an attractive pr.actical feature of many colltston-
`.. re.so lu~_ion a ~gorithms.
`
`To eomine the role placed by the "blochd~acce$s protocol" 1n the o6ove analysis, - ..
`we first observe that the binary stack al9or1thnl never makes any assumption in
`advance about the occupanty of the "current sending bo•" or any of the S stack
`.
`n
`levels. There could just as well be none or . 6 x 10
`senders in any of these
`loca(ions as hr as the binary stack algorithm 1s concerned, Thh meoM that
`there is no reason to block new senders frona entering the "current sending bo•"
`at any time. The free-access protocol leaves the •actess 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 become "ac~" in the transmitting
`process. Intuition su99uls that free-access should also give a better through(cid:173)
`put· than blod:ed-access. Unfortunately, free-access aho com~11cates .. the analysts.
`but Mathys and flajolet have shown that the binary slatk algoritlva with free(cid:173)
`access has a maJ<imum stable throughput of.\• .360 (packets/slot) •. Hore sur(cid:173)
`prisingly, they showed aho that the ternary stack algorithm (in which\enders
`flip a fair three-sided coin after a colltsion, movtng into levels 1 or Z if
`..... . t~ey flip "1" or "2" while S ts increased by Z) with free-access has an even
`larger mu imuin stab le throughput of I
`
`.\ • ,401 (pockets/slot).
`
`Pet., Exh. 1017, p. 9
`
`

`
`J.L J.l4UtY
`
`(Because this MIKi~ 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 algorithll with free-access
`has a better delay vs. throughput characteristic than does etther the binary
`stack 1l90rtlt• or the usual ALOHA 1l90rttt. (when analyzed ass1.111tng optt•htic(cid:173)
`ally that the ~utltbrt1111 hypothesis holds. (9)
`
`Many other collision-resolution algorithms have been proposed that have maximum
`stable throughputs exceeding .401 (packets/slot) -- the current record for binary
`(collision/no-collision) feedback ts ,4493 packets/slot {\OJ. However, the
`ternary stack 1l90rttti. with free-access appears to us to be the best practical
`chot.ce by virtue of th st111pl1ctty. its robustness and its relatively Mgh
`iaax'iinun1_ stable throughput. [t also seems to us to be a
`better practical
`choice than any ALOHA-like algorithm for randOl'l-access'ing 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 110re deeply into the 111athe111atics needed for a
`precise analysts of colltston-resolutton algorittv.s will find the recent book
`{11) by Hofrt to be a useful source of information.
`
`S. UPPER BOUNDS Off KAXIMUH STABLE THROUGHPUT
`
`Our discussion of colltston-resolutton algoritllllls .ay have raised the question
`tn the reader's mind: what is the capacity of the collision channel with feed(cid:173)
`back or, equivalently. what ts the largest possible maximum stable 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 (collision/no-collision) feedback. Sonie ingenious and complex arguments
`·have been used-to obtain upper bounds on the max1mum stable throughput. Rather
`than describing the best bound, we illustrate the general idea by descri~1ng
`a very simple bound due to Kelly [12].
`
`Kelly's ·bound actually applies only to elgorlthms (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 inrnediately following that in which it was generated. Suppose such
`an algorithm is operating stably for Polsson new arrivals with a mean of A
`(packels/s lot). Let pr be the fr act ion of slots in which at least one packet
`1s retransmitted. 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 packet (i'.e., the throughput t)
`satisfies
`
`T ~ Ae-A(l-pr)+ pre-A
`
`with equality when at most 1 packet is retransmitted in any slot (i.e., per(cid:173)
`fect scheduling of retransmissions). But stability implies t • A and thus ·
`-A
`-A
`A~ Ae . (1-pr) +pr
`
`(3)
`
`if the system is stable. It is readily checked that the choice pr• 1 maximizes
`A for which (3) can be satisfied. Thus
`
`( 4)
`
`is required for stability. The largest ~satisfying (4) is Kelly's bound on
`
`363
`
`Pet., Exh. 1017, p. 10
`
`

`
`Random-Accm Communications
`
`~aximum stable throughput, namely
`
`>.max~ • 5671 packets/slot,
`
`"' (S)
`
`that holds for any random-access al9or1thm with inmediate-first-transmtssion.
`In fact, our argument has never used the assumption of binary (collision/no~
`collision) feedback so that Kelly's bound (S) applies to any rand0111-access
`algorithm with inmediate-first-transmission on the collision channel with any
`kind of feedback.