United States Patent (19)
`Tobagi et al.
`
`54 LOCAL AREA COMMUNICATION
`NETWORK UTILIZING AROUND ROBIN
`ACCESS SCHEME WITH IMPROVED
`CHANNEL UTILIZATION
`75) Inventors: Fouad A. Tobagi, Los Altos, Calif.;
`Luigi Fratta, Segrate; Flaminio
`Borgonovo, Cantt, both of Italy
`73 Assignee: Stanford University, Palo Alto, Calif.
`21 Appl. No.: 294,745
`22 Filed:
`Aug. 20, 1981
`51) Int. Cl. ................................................ HO4J 6/00
`52 U.S. C. ........................................ 370/85; 370/93;
`370/94
`58) Field of Search ....................... 370/85, 94, 93, 95,
`370/86, 87, 88,89; 340/825.05, 825.5
`References Cited
`U.S. PATENT DOCUMENTS
`3,732,374 5/1973 Rocher et al. ........................ 370/85
`3,940,561 2/1976 Heinze et al. ......................... 370/85
`4,210,780 7/1980 Hopkins et al. ....................... 370/85
`4,241,330 12/1980 Hery et al. .......
`... 340/825.05
`4,292,623 9/1981 Eswaran et al. ...................... 370/85
`Primary Examiner-Douglas W. Olms
`Attorney, Agent, or Firm-Flehr, Hohbach, Test,
`Albritton & Herbert
`57
`ABSTRACT
`Disclosed is a local area communication network based
`
`56)
`
`11) Patent Number:
`45) Date of Patent:
`
`4,503,533
`Mar. 5, 1985
`
`upon a broadcast communication system comprising an
`inbound channel and an outbound channel, a plurality
`of stations connected to both the inbound and the out
`bound channels, transmitting on the outbound channel
`which utilizes an access protocol where the the access
`protocol used by the stations connected to the bus is a
`distributed algorithm and is based upon a conflict-free
`round robin (RR) access scheme. The time required to
`switch from one active user to the next in a round is
`minimized (on the order of carrier detection time, and is
`independent of the end-to-end network propagation
`delay. This improvement is particularly significant
`when the channel data rate is so high, or the end-to-end
`propagation delay is so large, or the packet size is so
`small as to render the end-to-end propagation delay a
`significant fraction of, or larger than, the transmission
`time of a packet. Moreover, some features of the present
`invention make it particularly suitable for voice applica
`tions. In view of integrating voice and data, a voice/-
`data protocol is described which allows it to meet the
`bandwidth requirement and maximum packet delay
`constraint for voice communication at all times, while
`guaranteeing a minimum bandwidth requirement for
`data traffic. The voice/data protocol constitutes a
`highly adaptive allocation scheme of channel band
`width, which allows data users to steal the bandwidth
`unused by the voice application.
`
`66 Claims, 20 Drawing Figures
`
`
`
`OUBOUND CHANNEL
`
`NBOUND
`CHANNEL
`
`IPR2020-00038
`MM EX1020, Page 1
`
`

`

`U.S. Patent Mar. 5, 1985
`
`Sheet 1 of 14
`
`4,503,533
`
`CSMA - CD
`- - - - RR
`= O L SEC/km
`
`O
`
`
`
`IPR2020-00038
`MM EX1020, Page 2
`
`

`

`U.S. Patent Mar. 5, 1985
`U.S. Patent Mar.5,1985
`
`Sheet 2 of 14
` Sheet20f14
`
`4,503,533
`
`
`
`4,503,533
` PASSIVE
`
`CY IRECTIONAL[
`
`3 | COUPLER | 23
`
`F. G. - 2E
`
`IPR2020-00038
`MM EX1020, Page 3
`
`IPR2020-00038
`MM EX1020, Page 3
`
`

`

`U.S. Patent Mar. 5, 1985
`
`Sheet 3 of 14 4,503,533
`
`PASS VE
`DIRECTIONAL
`
`(D)
`
`
`
`
`
`
`
`
`
`IPR2020-00038
`MM EX1020, Page 4
`
`

`

`U.S. Patent Mar. 5, 1985
`
`Sheet 4 of 14
`
`4,503,533
`
`OUTBOUND CHANNEL
`
`NBOUND
`CHANNEL
`
`
`
`
`
`O
`
`OUTBOUND
`CHANNE
`
`IPR2020-00038
`MM EX1020, Page 5
`
`

`

`Sheet 5 of 14
`
`4,503,533
`
`
`
`(NI) LOG(N!). LOE(NI) LOG
`
`
`
`
`
`U.S. Patent Mar. 5, 1985
`
`
`
`-|||||||||?ITW?vgl.
`
`IPR2020-00038
`MM EX1020, Page 6
`
`

`

`int
`(NI)LO(NI)Loa(NI)LOSMYOMLINNOILVLS'
`
`SWIL
`
`SWiL
`
`SWIL
`
`
`
`LIWSNVYL
`
`(dvi
`
`(4N0‘9
`
`(NI‘H)9
`
`NITNIVEL
`
`U.S. Patent Mar. 5, 1985
`U.S. Patent Mar. 5, 1985
`
`Sheet 6 of 14
`Sheet 6 of 14
`
`4,503,533
`4,503,533
`
`W
`
`BW ||
`
`
`
`
`
`‘LuVLS-d109¥SNINVLY3S0NnSG‘>|4fNOILVLSLVGSANSSEOSVSLN3JAZONYSTVNOIS
`
`
`
`GANIWYsl30S3WO934d
`
`aqvagAGV3Y
`
`IPR2020-00038
`MM EX1020, Page 7
`
`IPR2020-00038
`MM EX1020, Page 7
`
`

`

`U.S. Patent Mar. 5, 1985
`
`Sheet 7 of 14
`
`4,503,533
`
`STATION
`DEAD
`
`
`
`NO
`WAT FOR FIRST OF FOLLOW ING
`EVENTS: BOT (N) OR
`TIME-OUTtt + (
`)
`TME-OUTt - t
`INTATE Tx OF PILOT
`
`WAT FOR BOT (N)
`
`STOP TRANS MISSION OF PILOT
`
`EOC (OUT),
`
`WAT FOR FIRST OF FOLLOWING
`EVENTS: EOT (N) OR EOC(OUT)
`
`TRANSMT LOCOMOTIVE
`
`
`
`
`
`
`
`
`
`
`NTATE TRANSMISSION OF TU
`
`
`
`WAIT td SECONDS
`
`
`
`
`
`
`
`ABORT
`TRANSMSSION
`
`COMPLETE TRANSMISSION OF TU
`FG.- 6 FLOW CHART FOR THE ACCESS PROTOCOL
`
`IPR2020-00038
`MM EX1020, Page 8
`
`

`

`U.S. Patent Mar. 5, 1985
`
`Sheet 8 of 14
`
`4,503,533
`
`NLJOXLJLVILINI
`(Pi)LNO-AWILGNV
`
`‘3A1LOWO907
`:0=(XH)ELGNV
`AAILOWOD01
`dOx1dOLls
`
`4OXLdOLS
`
`
`
`
`
`(Pt)LNO-SWIL
`
`1=(X"H)GLGNV.
`
`ANV3ALLOWOD07JO*L
`
`
`
`ALVILINI:(NI)LOS
`
`
`
`(Py)LNO-AWIL
`
`(PyLNO-SWILr=(N1'H)NIVSL
`
`
`
`anv3AIIV
`
`3wooadOLLSAND3Y
`JAA3wooadOLLS3NO3YL
`
`
`
`-O=(NIF)NIVYLGNV
`
`O=(LNO'H)2GNV
`
`
`
`(Pi)LNO-3WIL
`
`
`
`nljoxlALVILINI
`
`GNV(LNO)303
`
`s}=(X5)GL
`
`NLJOXLLYOSV
`
`}=(LNO'H)9GNV
`(Pl)NO-aWIL
`
`
`
`(Py)LNO-3WILGNV(NI)LOG
`
`S13A31Y3SHOIHLOMNd40XLdOls
`
`
`
`
`
`3HLONILNAWAIdW!ANIHOVWALVLSSLINIS
`AJILON:XL9:(NI)LO
`
`"JOIOLOYdSSAIOV2-Ol4
`
`
`\LOnidJOXLJLVILINI
`
`(P4497+2)
`
`
`
` LNO-AWIL6(Py497.4a)1NO-FWILSLVELINI
`
`IPR2020-00038
`MM EX1020, Page 9
`
`IPR2020-00038
`MM EX1020, Page 9
`
`
`
`

`

`U.S. Patent Mar. 5, 1985
`
`Sheet 9 of 14 4,503,533
`
`SATON
`DEAD
`
`DECODING UNSUCCESSFUL
`
`
`
`WAT FOR BOT (N)
`
`WAT FOR FIRST OF FOLLOWING
`EVENTS: BOT (N) OR
`TIME-OUT (t + c + td)
`
`TIME-OUT (C++ td)
`
`NTATE TRANSMSS ON
`OF P LOT
`
`WAT FOR BOT (N)
`
`STOP TRANSMSSION OF POT
`
`SET C = t +to+ td
`
`
`
`
`
`RECEIVE AND DECODE
`TRAN-TYPE INDICATOR
`DECODNG
`SUCCESSFUL
`
`
`
`
`
`
`
`
`
`Fl G -8 FOW CHART FOR THE IN TAZATION PORTION
`g
`OF THE VOCEADATA ALGOR THM.
`
`IPR2020-00038
`MM EX1020, Page 10
`
`

`

`U.S. Patent Mar. 5, 1985
`
`Sheet 10 of 14 4,503,533
`
`
`
`
`
`
`
`
`
`
`
`
`
`WAT FOR FIRST OF FOLLOWING
`EVENTS: EOT (N) OR EOC (OUT)
`
`COMMUNCATE () AND C
`TO HGHER LEVELS
`
`STATE (b)=ACT VE
`
`COMPLEMENT b AND RESET C
`
`TRANSMT TRAIN INDICATOR
`
`
`
`
`
`
`
`STATE(0)=ACTIVE
`AND TB (t,b)=
`AND C L (8)
`N ?
`
`NITATE TRANS MSS ON OF TU
`
`
`
`WAT td SECONDS
`
`c(tOUT)=O
`AND C L(t)
`
`
`
`
`
`
`
`
`
`ABORT
`TRANSMISSION
`
`
`
`
`
`WAIT FOR FIRST OF FOLLOW ING
`EVENTS: CTX OR C=L(0)
`
`STATE (0) = DORMANT
`FLOW CHART FOR THE PORTION OF THE VOICE/DATA
`ALGORTHM EXECUTED BY A STATION IN THE ALIVE STATE
`FG. - 9
`
`IPR2020-00038
`MM EX1020, Page 11
`
`

`

`U.S. Patent Mar. 5, 1985
`
`Sheet 11 of 14 4,503,533
`
`REQUEST TO BECOME
`ALVE AND
`TRAIN (t, IN) =
`
`REQUEST TO BECOME
`ALVE AND
`TRAN (t, N)= O:
`NTATE TIME-OUT (
`
`C
`c
`
`--
`
`
`
`d'Eot(N): NTATE
`TIME-OUT (t" to +2td)
`
`UNABLE TO DECODE
`(AND TRAIN (t, N) = 1)
`
`BOT (N): SET C-t+ t +td
`AND NITATE RECEP
`T ON AND DECODING OF T
`
`TIME-OUT (t+ 2)
`NTATE Tx OF POT
`
`(05)
`
`
`
`DECODED
`AND (i) = O
`
`BOT (N):
`STOP Tx OF PLOT
`SET = O AND C=O
`
`
`
`T DECODED
`AND (i) =
`
`(A15
`
`F G e O FNTE STATE MACHINE MPLEMENTNG THE
`O
`NT ALIZATION PORTION OF THE VOCE/DATA
`ALGOR THM,
`
`IPR2020-00038
`MM EX1020, Page 12
`
`

`

`
`
`
`
`
`
`
`
`"SALLOW=(1)SLVLS“(1)Y>9IGNV(P4)LNO-3SAIL
`
`
`
`(Pi)LNO-SWILGNVIL4OXLSLVILINI{130XLLYORV
`
`£@LNSW3T1dWNOO‘O=913S:}=(1N0‘H)9
`
`
`
`
`
`
`VLVG/39I0AJHL40NOILYOd3HLONILNSWIIdWISNIHOVWSLVLSSLINIG
`“ZLVLSSAINVSHLNIWHLIYOOTV||-"9|4NOILVLSVAGd3.LND3X3
`
`
`
`
`
`
`
`
`O=(LNO'H)2GNV
`
`
`
`(A)LNO-AWIL
`
`U.S. Patent Mar. 5, 1985
`
`Sheet 12 of 14 4,503,533
`
`‘S13A31Y3HOIHOLD
`
`
`
`
`
`
`
`GNV©LINSNVYL:(NI)LOS(Py)1NO-aWILGNV
`
`:((1)129.YO
`
`
`
`Nl40x%LLYOSV
`
`
`ANVWY0dGNVPyINO-JWILinywuod
`
`
`=(1)31VLS(P)LNO-3NIVW
`ALJOXL1YOaVNL4OXLLYOay
`
`(1)129(n>ONV(LNO'}PONY:(O)1=9
`JALLOV=tteGNY:((ov50NOI=tiNo'n)
`
`X19-(0)aLvis
`AALLOV=(0}asONYNLJOXL3LVILINII=
`(P))LNO-3WILONV
`
`(LNO)903ONYi)LNO-S3WIL
`
`O=(LNO‘Ndf}-{0)1>9ONY
`
`AL40XLSLVILINI
`
`eirfdavisany
`
`
`
`“ATAeoanoramtonyDUBESN
`
`
`
`
`
`(Pl)LNO-SAIL
`
`
`
`
`
`(LNYWHOG=(1)3LVLSYO
`
`O=(1'})G1)ONYXLO
`
`O=(LNO'H)DGNV
`
`
`PanoaAGoieGRY“SAI“(0)U>9JIp‘ST3A31LDV=(0)BLVLS
`(Pt)LNO-SWILGNV9LINSNVYL:(NI)LOS
`YSHOIHOLOD
`
`
`
`
`
`
`
`(LNVWHOd=(0)SiVLSYO
`
`O=(O'HGL)GNVXL
`
`IPR2020-00038
`MM EX1020, Page 13
`
`IPR2020-00038
`MM EX1020, Page 13
`
`
`
`

`

`U.S. Patent Mar. 5, 1985
`
`Sheet 13 of 14 4,503,533
`
`2
`3O
`2O
`2 - U-H
`
`d
`
`-
`
`ce
`H
`O
`
`23
`
`RT APS
`2.
`
`32
`
`
`
`Tx 8 Rx
`FUNCT ONS
`
`FG.-2
`
`IPR2020-00038
`MM EX1020, Page 14
`
`

`

`Sheet 14 of 14 4,503,533
`U.S. Patent Mar. 5, 1985
`3O
`1 A
`NBOUND CHANNEL
`2O
`OT
`TY
`
`2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Nan
`
`TERMINATOR
`
`O
`
`OO
`TRANSMTTER
`L CONTROL
`H 32
`TRANSMTTER
`CONTROL
`
`
`
`
`
`
`
`PHASE t
`ENCODER
`3O
`
`TRANSMITTER
`SHIFT REGISTER
`
`w
`
`y N.
`
`O
`
`2
`
`
`
`E CE VER
`R
`FT
`REGISTER
`SH
`
`ADDRESS E.
`FLTER
`ty
`
`--m-
`
`NPUT
`BUFFER
`
`USNG DEVICE
`
`FIG. - 3
`
`IPR2020-00038
`MM EX1020, Page 15
`
`

`

`1.
`
`LOCAL AREA COMMUNICATION NETWORK
`UTILIZING AROUND ROBIN ACCESS SCHEME
`WITH IMPROVED CHANNEL UTLIZATION
`
`10
`
`15
`
`BACKGROUND OF THE INVENTION
`The present invention relates to a local area commu
`nication network.
`A great deal of discussion can be seen in the recent
`literature regarding local networks and their applicabil
`ity to many of today's local area communication needs.
`These needs have primarily consisted of data communi
`cation applications such as computer-to-computer data
`traffic, terminal-to-terminal data traffic, and the like.
`More recently, a new line of thought has been apparent.
`It is the desire to integrate voice communication on
`local data networks. The reason for this is threefold: (i)
`voice is an office communication application just as
`computer data, facsimile, etc.; (ii) recent advances in
`vocoder technology have shown that digitized speech
`20
`constitutes a digital communication application which is
`within the capabilities of local area data networks; and
`(iii) today's local network architectures, especially the
`broadcast bus type, offer very elegant solutions to the
`local communications problems, from both the point of
`25
`view of flexibility in satisfying growth and variability in
`the environment.
`While existing solutions are elegant, they are not
`without their limitations in performance. Some of these
`limitations arise as the characteristics of the environ
`30
`ment and data traffic requirements being supported by
`these solutions deviate from those assumed in the origi
`nal design. Examples of such characteristics are: Packet
`length distribution, packet generation pattern, channel
`data rate, delay requirements and geographical area to
`be spanned.
`One prior art approach is a bidirectional broadcast
`system (BBS) architecture based on a carrier sense mul
`tiple access (CSMA) mechanism as exemplified by the
`so-called ETHERNET. Another prior art approach is a
`unidirectional broadcast system (UBS) architecture
`with a round-robin access scheme.
`A problem with a CSMA bidirectional broadcast
`system is that it can be shown that the effort required to
`achieve higher channel bandwidths with the hope of 45
`achieving a network throughput proportional to the
`channel speed is unfortunately rewarded only by a mar
`ginal improvement.
`The limitation with unidirectional broadcast systems
`operating with the existing round-robin scheme is that
`the maximum throughput for such a system exhibits
`similar performances as for a CSMA bidirectional
`broadcast system, and as such both approaches suffer of
`an overhead per packet transmission.
`There is a need therefore for an improved local area
`55
`communication network which overcomes the prob
`lems of prior art systems. In view of the above back
`ground, it is an objective of the present invention to
`provide an improved local area communication net
`work.
`60
`
`4,503,533
`2
`not require signal propagation to be unidirectional, and
`still utilizes a round-robin access protocol. In either
`case, the present invention, however, is performance
`wise more efficient than existing schemes and over
`comes many of the limitations. Moreover, the present
`invention can be shown to be particularly suitable for
`the integration of voice and data applications having a
`simple voice/data protocol which allows the network
`to meet bandwidth requirements and maximum packet
`delay constraints for voice communication at all times,
`all guaranteeing a minimum bandwidth requirement for
`data traffic.
`These requirements are satisfied by blocking requests
`for voice communication which exceed a maximum
`allowable number, where this maximum number is
`given as a function of the vocoder's rate and a minimum
`data bandwidth requirement, and is easily enforceable
`in practice.
`In accordance with the foregoing summary, the pres
`ent invention achieves the objective of providing an
`improved local area communication network.
`Other objects and features of the present invention
`will become apparent from the following detailed de
`scription when taken in conjunction with the accompa
`nying drawings.
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 depicts a representation of maximum through
`put of prior art local area communication networks.
`FIGS. 2A-2G depict channel taps which could be
`utilized with the present invention.
`FIGS. 3A and 3B depict examples of block diagrams
`of a local area communication network topology ac
`cording to the present invention.
`FIGS. 4 and 5 depict timing diagrams for illustrating
`the operation of the present invention.
`FIG. 6 depicts a flow chart illustrating the sequence
`of operations for the access protocol according to the
`present invention.
`FIG. 7 depicts a finite state machine implementing
`the access protocol according to the present invention.
`FIG. 8 depicts a flow chart for the initialization por
`tion of the voice/data algorithm according to the pres
`ent invention.
`FIG, 9 depicts a flow chart for the main portion of
`the voice/data algorithm executed by a station in the
`local network.
`FIG. 10 depicts a finite state machine implementing
`the initialization portion of the voice/data algorithm.
`FIG. 11 depicts a finite state machine implementing
`the main portion of the voice/data algorithm executed
`by a station in the network.
`FIG. 12 depicts a block diagram of a station accord
`ing to the present invention.
`FIG. 13 depicts a more detailed diagram of a station
`according to the present invention.
`DETALED DESCRIPTION OF THE
`DRAWINGS
`In the bidirectional broadcast system (BBS) architec
`ture, all devices share a single communication medium,
`typically a coaxial cable, to which they are connected
`via passive taps. When transmitted by a device, signals
`propagate in both directions, thus reaching all other
`devices. The device interface is such that it recognizes
`and accepts messages addressed to it.
`
`35
`
`50
`
`SUMMARY OF THE INVENTION
`The present invention relates to a local area commu
`nication network.
`In one embodiment, the present invention is based
`65
`upon a unidirectional broadcast system and utilizes an
`access protocol based uon a round robin access proto
`col. In another embodiment, the present invention does
`
`IPR2020-00038
`MM EX1020, Page 16
`
`

`

`10
`
`T. e.
`S =
`Tge 8 -- (1 - es - ge8)T -- 1
`
`(1)
`
`where g is the rate at which stations become ready
`during a slot of size T, T is again the transmission time
`of a packet and T is the time needed to detect a colli
`sion and stop transmitting. Both T and Te are measured
`in units of slots. Setting Teto its minimum value (Te=2),
`S is maximized, as T changes, for a value of g practi
`cally constant and equal to 0.65. The maximum
`throughput (or channel capacity) Smax is therefore
`given by
`
`30
`
`4,503,533
`4.
`3
`thus is considered as the benchmark for CSMA
`The difficulty in controlling access to the channel by
`schemes. The results are derived from a worse case
`users who can only communicate via the channel itself
`analysis in which the vulnerable period of a packet is
`has given rise to what is known as random access tech
`always considered equal to its maximum. Although it is
`niques. The best known such schemes are ALOHA and
`possible to predict better performance if one took into
`Carrier Sense Multiple Access (CSMA). In the
`account the fact that the vulnerable period of a trans
`ALOHA scheme, users transmit any time they desire.
`When conflicts (consisting of overlapping packet trans
`mission is variable, the result would become dependent
`on the particular environment (namely, the geographi
`mission) occur, the conflicting users schedule retrans
`mission of their packets to some later time, incurring a
`cal distribution of devices) and the particular traffic
`random rescheduling delay. In CSMA, the risk of a
`pattern (i.e., the source-destination traffic distribution),
`collision is decreased by having users sense the channel
`and would be rather difficult to evaluate. In order to
`prior to transmission. If the channel is sensed busy, then
`study the limitations of the scheme considered and in an
`attempt to keep the results as general as possible, a
`transmission is inhibited. There are several CSMA pro
`trocols. In the so-called nonpersistent CSMA, a user
`worse case analysis is undertaken throughout the paper
`which finds the channel bus simply schedules the re
`15
`for all schemes considered.
`transmission of the packet to some later time. In the
`It has been shown that the throughput of the slotted
`p-persistent CSMA, a user which finds the channel busy
`nonpersistent CSMA-CD scheme is given by
`monitors the channel, waits until the channel goes idle,
`and then performs the "p-process' which consists of
`transmitting the packet with probability p, and waiting
`20
`the maximum end-to-end propagation delay with proba
`bility 1-p; at this point in time, it senses the channel and
`again if the channel is sensed idle, it repeats the p-proc
`ess, othewise it repeats the entire procedure.
`Given the physical characteristics of digital transmis
`25
`sion, on coaxial cables, in addition to sensing carrier it is
`possible for transceivers to detect interference among
`several of their colliding packets. This gives rise to a
`variation of CSMA which is referred to as Carrier
`Sense Multiple Access with Collision Detection
`(CSMA-CD). In the so-called Ethernet network, users
`employ th p-persistent CSMA-CD protocol along with
`a scheduling procedure, called the binary exponential
`back-off; it consists of having the colliding users incur a
`random delay whose mean is doubled each time a colli
`35
`sion is incurred.
`The performance of a bidirectional broadcast system
`is heavily dependent on the particular access method
`used, and is characterized by two main measures: chan
`nel capacity and throughput-delay tradeoff. For a given
`access mode, channel capacity is defined as the maxi
`mun throughput that the network is able to support.
`The throughput-delay measure is the relationship which
`exists between packet delay and channel throughput. It
`should be clear that, due to collisions and retransmis
`sions, channel capacity is always below the available
`channel bandwidth, and that throughput and delay have
`to be traded off; the larger the throughput is, the larger
`is the packet-delay.
`Let W, denote the channel bandwidth (in bits/-
`seconds), d the length of the cable between the extreme
`users, and B the number of bits per packet (assuming
`fixed size packets). Let r denote the end-to-end delay
`defined as the time from the starting of a transmission to
`the starting of reception between the extreme users, and
`55
`T denote the transmission time of a packet; i.e.,
`T=B/W. In all CSMA protocols, given that a transmis
`sion is initiated on an empty channel, it is clear that it
`takes at most T sec. for the packet transmission to reach
`all devices; beyond this time the channel is guaranteed
`to be sensed busy for as long as data transmission is in
`progress. A collision can occur only if another transmis
`sion is initiated before the current one is sensed. Thus,
`the first T sec. of a packet transmission represents its
`(maximum) vulnerable period and plays a key role in
`determining the performance of CSMA protocols.
`Among all protocols previously mentioned, the p-per
`sistent CSMA-CD provides the best performance, and
`
`Using estimates for the various delays through interface
`components and for the propagation delay in coaxial
`cables as given in the Ethernet Specifications, one finds
`that a rough estimate for T is 10 microseconds for each
`km of cable (assuming one repeater for each 500 m of
`cable), and thus the product T W is equal to 10 bits for
`each MBPS bandwidth and each km of cable.
`In FIG. 1 Smax is plotted as a function of W for vari
`ous values of the ratio d/B, where d is in kilometers and
`B in kilobits. Consider for example B= 1 KB and d = 1
`Kim. While with W = MBPS one can achieve a
`throughput of 0.96 MBPS, with W = 10 MBPS, Sna is
`equal to 7.26 MBPS, and when W = 20 MBPS then
`Smax= 11.4 MBPS. If packets are shorter, say 250 bits,
`then with W = 1 MBPS S=0.87 MBPS; with W = 10
`MBPS, Smax is only 4 MBPS. The effort required to
`push the technology to higher channel bandwidth with
`the hope to achieve a network throughput proportional
`to the channel speed is unfortunately rewarded only by
`a marginal improvement. The need to seek better solu
`tions is thus clear.
`Just as with BBS, a unidirectional broadcast system
`(UBS) consists of a single bus to which all users are
`connected. Transmitting taps, however, are such that
`the transmitted signals are forced to propagate in only
`one direction, attenuating heavily the signals in the
`opposite direction. Broadcast communication is then
`achieved by various means, such as folding the cable, or
`repeating all signals on a separate channel (or fre
`quency) in the reverse direction, so that signals trans
`mitted by any user reach all other users on the reverse
`path. Thus the system may be considered as consisting
`
`T
`Smax = T 376 =
`1
`
`1.
`3.76
`--
`
`TV
`(3
`
`(2)
`
`45
`
`50
`
`60
`
`65
`
`IPR2020-00038
`MM EX1020, Page 17
`
`

`

`4,503,533
`6
`5
`users have had their chance. In the present algorithm,
`of two channels: the outbound channel which all users
`access in order to transmit, and the inbound channel
`while no user transmits more than once within each
`which users access in order to read the transmitted
`"round', the order of transmission within the round
`information. In addition to the transmitting capability
`may vary depending on the instants at which messages
`on the outbound channel, users can sense activity on
`arrive. For example, assume that user S1just completed
`that channel in a way similar to that required in other
`transmission of its message. Assume also that at this time
`channel sensing systems such as CSMA. In a UBS this
`S2 does not have a message ready and therefore S3,
`capability results in an interesting feature. Assume users
`assumed ready, transmits next. While S3 is transmitting,
`are numbered sequentially S1, S2, S3, etc., and user S1
`a message arrives at S2, and consequently when S3 is
`is defined as the "farthest', i.e., possessing the longest
`finished, S2 transmits next. The order of transmission in
`round trip delay between its transmitting tap and its
`this case is S1, S3, S2 while if all had a ready meassage
`receiving tap. Because of the undirectional signalling
`at the beginning of the round the order would have
`property, S2 is able to sense signals generated by S1 on
`been S1, S2, S3.
`both the inbound and outbound channels whereas the
`From the above algorithm, it is clear that all transmis
`opposite does not hold; that is, S1 can sense signals
`sions are conflict free. The time separating two consec
`generated by S2 only on the inbound channel. This
`utive packet transmissions depends on the relative posi
`asymmetry is utilized in establishing the ordering re
`tion of the devices transmitting them. The best case is
`quired for a round-robin (RR) scheme, which is now
`observed when the successive transmitting users are
`described.
`among the highest indices. In this case neglecting the
`In the RR algorithm, a user is considered to be in one
`20
`transmission time of a burst as well as the delay incurred
`of three states. It is in the IDLE state if it does not have
`between the two taps (on the inbound and outbound
`any message awaiting transmission. A non-idle user,
`channels) of the subscriber with the highest index, it can
`called a ready user, assumes for fairness purposes one of
`be seen that the time separating two consecutive trans
`two states: ACTIVE if it has not transmitted its message
`missions can be as low as 2t sec., i.e., the longest round
`in the current round, or DORMANT if it did transmit
`25
`trip delay. The worst case is observed when the two
`in the round and is waiting for the completion of the
`successively transmitting users are with the lowest indi
`round. In order to achieve fair scheduling, DOR
`ces. In that case the gap is about 4T sec. Note also that
`MANT users defer to all other ACTIVE users. Conse
`due to the transmission of bursts when not all users are
`quently, it is apparent that no user will transmit its sec
`in the DORMANT state, the inbound channel is never
`ond message before other ready users have had a
`30
`idle for a period longer than 2T sec. The channel idle
`chance to transmit their first ones. Eventually all ready
`time will exceed 2r sec., if either all users are DOR
`users will have transmitted their message (i.e., they all
`MANT or all users are IDLE. Thus it can be seen that
`become DORMANT); this constitutes the end of a
`the gap between two rounds in the former case is be
`round; at this time all users reset their state to ACTIVE
`tween 4T and 6t.
`and a new round starts,
`35
`To study the channel capacity of a UBS employing
`While each user distinguishes between its DOR
`the RR algorithm, assume that M users are always
`MANT and ACTIVE states, arbitration among active
`ready to transmit (i.e., we assume heavy traffic condi
`users must be provided by additional means. To that
`tions). In this case the maximum throughput is given by
`end each ACTIVE user transmits a short burst of un
`modulated carrier after the end of the previous message
`has been detected on the inbound channel, thus indicat
`ing its ACTIVEness and at the same time senses the
`outbound channel. All but one ACTIVE user will sense
`the outbound channel busy (due to transmission from
`users with a lower index) thus singling out the next user
`45
`to transmit. If a given user senses the outbound channel
`busy, then there exists at least one ready user "ahead' of
`it which generated that signal; a user will always defer
`its transmission in favor of those "ahead' of it.
`Initially all users reset their state, meaning that all
`50
`ready users are ACTIVE. An ACTIVE user will oper
`ate as follows:
`1. Wait until the next end-of-carrier (EOC) is detected
`on the inbound channel.
`2. Transmit a short burst of unmodulated carrier and
`listen to the outbound channel for one round trip
`delay.
`3. If during that period the outbound channel is sensed
`idle, the user transmits its message and switches to the
`DORMANT state. Otherwise, the user repeats the
`algorithm.
`A DORMANT user becomes ACTIVE if the in
`bound channel is sensed idle for one round trip delay or
`longer and then performs the above steps.
`In other round-robin disciplines, each user, in a pre
`65
`scribed order, is given a chance to transmit; it transmits
`if it has a message ready and declines if it has not. This
`user will not be given a second chance before all other
`
`Note: The upper bound on channel capacity can be
`achieved if, following the transmission of the burst, a
`device waits a period of time shorter than 2t, namely 27
`minus the propagation time between its tap on the out
`bound channel and its tap on the inbound channel. The
`drawback of such a mode of operation, however, is that
`this parameter has to be tuned according to the position
`of the device on the cable.
`In FIG. 1, the lower bound on Sna for the RR algo
`rithm is plotted. Both RR and CSMA-CD exhibit simi
`lar performance and both suffer of an overhead per
`packet transmission which is dependent on the ratio
`
`10
`
`15
`
`55
`
`60
`
`- (3)
`-za M. -s Saas - a
`M(T + 4 + 6
`max
`M(T + 2 + 4t
`The lower bound is also expressed as
`
`Smax =
`
`B
`B -- 4t -- 9.
`
`(4)
`
`If M is not too small, then one can neglect 6 W/M and
`get
`
`--
`Smax =
`W
`X 4 g
`
`(5)
`
`IPR2020-00038
`MM EX1020, Page 18
`
`

`

`4,503,533
`8
`7
`detect presence of the unit, and then to synchronize
`W/B. The removal of such a dependent will provide the
`with bit and packet boundaries.
`ultimate performance, which is an objective of the pres
`ent invention and which will be described hereinbelow.
`C. Bus Transceivers
`As with the UBS architecture, the present invention
`For every station in the system, the transmitting de
`is based upon a broadcast communication system com
`5
`prising an outbound channel and an inbound channel, a
`vice is connected to the outbound channel while the
`plurality of stations connected to both the outbound and
`receiving device is connected to the inbound channel. It
`is noteworthy that, regardless of what type the trans
`inbound channels, transmitting on the outbound chan
`nel and receiving on the inbound channel. The commu
`mitters are (unidirectional or bidirectional), given the
`nication medium constituting the outbound and inbound
`kind of topologies under consideration for the invention
`10
`channels may be a twisted pair, a coaxial cable, an opti
`and given the way the outbound and inbound channels
`cal fiber, or a wave guide. The channel access protocol
`are connected, signals propogate on the inbound chan
`for transmission on the outbound channel is based upon
`nels always in the same direction.
`the round-robinscheme described for the UBS architec
`One of the basic features required for the round-robin
`ture with the advantage of utilizing the channel band
`algorithm and the access protocol of the invention is the
`15
`width more efficiently than the RR algorithm even
`ability for each station to sense, on the outbound chan
`when packet transmission times are short and cable
`nel, the carrier due to transmissions by stations on the
`distances are long.
`upstream side of its transmitter; (i.e., those stations
`In one embodiment, transmitters on the outbound
`whose transmit taps on the outbound channel are more
`channel may be of the undirectional type rendering the
`20
`distant from the inbound channel than the transmitter of
`invention a UBS; in another embodiment, signal propa
`the station in question.)
`gation on the outbound channel is not required to be
`Restricting again the discussion to the unidirectional
`undirectional, and thus bidirectional transmitters may
`case, note that there are several ways for achieving the
`be utilized. As it is easier and simpler to present the
`necessary functions on a coaxial cable or twisted pair.
`concepts underlying the invention when unidirectional
`25
`Described herein are feasible alternatives disregarding
`ity of signal propagation is guaranteed than when trans
`any consideration of complexity, cost, or implementa
`mitters are bidirectional. The preferred embodiment is
`tion preference. One way of achieving unidirectionality
`considered at first to be a UBS architecture and defer to
`of transmission is to use such means as unidirectional
`a later section discussion of the case where the con
`amplifiers between every two consecutive transmit taps
`straint of unidirectionality is relaxed.
`30
`The gist is basically the following. Consider the UBS
`on the outbound channel. In this case the transmit taps
`architecture, contrary to a RR algorithm where the
`can be "passive' T-connectors (such as those used in
`time reference used in determining the right of way is
`ETHERNET) and therefore do not require splicing of
`the end-of-carrier on the inbound channel (EOC(IND),
`the cable for installation; the unidirectional means how
`in the access protocol of the present invention the time
`ever do require splicing of the cable and are active
`elements. To achieve sensing of carrier signals gener
`reference used is the end-of-carrier on the outbound
`channel (EOC(OUT)). The mechanism used in deter
`ated by stations on the upstream side of a tap 33, one of
`mining the access right to users in a given round is thus
`two options exist: (i) provide an additional (passive) tap
`made independent of the propagation delay t, thus
`31 on the upstream side of the amplifier 29 which is on
`decreasing the gaps between consecutive transmissions
`the upstream side of the tap 33 (as shown in FIG. 2A),
`to values on the same order of magnitude as the time
`or (ii) operate with a single tap 33, but provide means 27
`n