:
`
`United States Patent £191
`Koopman et al.
`
`lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll
`5,450,404
`Sep. 12, 1995
`
`US005450404A
`[11] Patent Number:
`[45] Date of Patent:
`
`[54) EXPLICIT AND IMPLICIT TOKEN MEDIA
`ACCESS PROTOCOL WITII MULTI-LEVEL
`BUS ARBITRATION
`Inventors: Philip J. Koopman, Hebron; David C.
`Brajczewski, Vernon, both of Conn.
`
`[75]
`
`[73] Assignee: Otis Elevator Company, Farmington,
`Conn.
`[21] Appl. No.: 992,878
`[22] Filed:
`Dec. 21, 1992
`Int. 0.6 ............................................... H04L 5/22
`(51]
`(52] u.s. a .................................... 370/85.2; 370/95.3
`[58] Field of Search ................. 370/110.1, 100.1, 58.1,
`370/85.1, 85.2-85.4, 85.5, 85.6, 95.3, 94.1, 85.7'
`103, 95.1; 375/107; 340/825.5, 825.06
`References Cited
`U.S. PATENT DOCUMENTS
`4,054, 753 10/1977 Kaul et al .......................... 370/95.3
`4,438,520 3/1984 Saltzer .................................... 375/4
`4,570,257 2/1986 Olson et al . ........................ 370/85.6
`4,594,706 6/1986 Kobayashi ......................... 370/95.3
`4,709,364 11/1987 Hasegawa et al .................. 370/85.1
`
`[56]
`
`4,763,321 8/1988 Calvignac et al .................. 370/85.1
`4,815,110 3/1989 Benson eta! ....................... 370/103
`4,970,720 9/1990 Esaki .................................. 370/85.2
`
`OTHER PUBLICATIONS
`Werner Bux, "Token-Ring Local Area Networks and
`Their Performance" Feb. 1989, Proceeding of the
`IEEE, vol. 77, No. 2.
`
`Primary Examiner-Benedict V. Safourek
`Assistant Examiner-Chan T. Nguyen
`
`ABSTRACT
`(57]
`Primary implicit token slots (that is, token slots follow(cid:173)
`ing a message or jam used to restart network activity)
`are assigned to multiple transceivers. When a trans(cid:173)
`ceiver assigned to a shared slot has data to transmit, it
`emits a jamming signal instead of a message in its token
`slot. This jamming signal serves as a synchronization for
`a second implicit token slot progression in which only
`transceivers sharing the primary level implicit token
`slot participate.
`
`5 Claims, 10 Drawing Sheets
`
`TRANSMITTER RESET OR
`POWER 1URNE0 ON
`
`ANY ERROR OR
`• T!WISIIITTER CONFUSED"
`
`I
`RESYNCHRONIZE -WNT FOR:
`
`D~ OR
`
`BUS JAM '
`DETECTED
`
`SHORT BUS
`J ...
`DETECTED
`
`SHORT
`JMI
`DETECTEO
`
`NOT THE
`BUS MASTUl
`
`BUS
`OWNERSHIP
`MESSAGE
`omcrro
`
`EXHIBIT \? >)\
`DATE lr I) ~Sc:
`REPORTER C' i.-6:-C
`Planet DepCI5. LLC
`
`Exhibit 1321 Page 01 of 25
`
`

`
`U.S. Patent
`
`Sep. 12, 1995
`
`Sheet 1 of 10
`
`5,450,404
`
`fig.t
`
`~
`~
`
`A
`
`l
`
`COMMUNICATIONS MEDIUM
`I
`I
`
`1\
`
`l
`
`.
`
`II l
`
`TRANSMITTER
`AND
`RECEIVER
`
`TRANSMITTER
`AND
`RECEIVER
`
`TRANSMITTER
`AND
`RECEIVER
`
`fig.2
`
`OPERATION
`BEFORE
`SYNCHRONIZATION
`
`JAM
`BUS
`
`DETE CTED
`
`T RANSMITTER
`NEEDS
`TO GENERATE
`HRONIZATION
`SYNC
`EVENT
`
`I JAM THE BUS I
`
`ERIOD
`JAM P
`
`ELAP SED
`
`WAIT FOR ALL
`JAMMERS TO FINISH
`
`JAMMING
`CEASES
`
`SYNCHRONIZATION
`ACHIEVED
`
`OPERATION AFTER
`SCNCHRONIZATION
`
`Exhibit 1321 Page 02 of 25
`
`

`
`U.S. Patent
`
`Sep. 12, 1995
`
`Sheet 2 of 10
`
`5,450,404
`
`fig.3
`
`TRANSMITIER RESET
`POWER TURNED ON
`
`t
`
`ANY ERROR OR
`,.TRANSMITIER CONFUSED ..
`
`RESYNCHRONIZE-WAIT FOR:
`
`'
`
`JAM
`DETECTED
`
`BUS JAM
`DETECTED
`
`BUS IDLE FOR
`OR N SLICE TIMES
`+
`FRAME GAP
`
`N SLICE TIMES
`+
`FRAME GAP
`IDLE ELAPSED
`,....-.L.----...1..-..,.
`
`I JAM THE BUS I
`
`I
`JAM PERIOD
`ELAPSED
`
`WAIT FOR ALL
`JAMMERS TO FINISH
`
`JAMMING
`CEASES
`
`FRAME
`GAP
`FRAME GAP
`TIME ELAPSED
`'
`
`WAIT FOR
`Mth SLICE
`M TIME SLICE
`ELAPSED
`
`TRANSMIT
`BUS JAM
`MESSAGE 11-----~
`DETECTED
`
`TRANSMISSION
`TIME SLICE
`ELAPSED
`
`WAIT FOR
`REST OF 1 - - - - -_ J
`SLICES
`
`ANOTHER
`N-M-1 SLICES
`ELAPSED
`
`Exhibit 1321 Page 03 of 25
`
`

`
`U.S. Patent
`
`Sep. 12, 1995
`
`Sheet 3 of 10
`
`5,450,404
`
`fig.4
`TRANSMilTER RESET OR
`POWER TURNED ON
`
`ANY ERROR OR
`"TRANSMilTER CONFUSED"
`
`RESYNCHRONIZE-WAJT FOR:
`
`'
`
`t
`
`JAM
`DETECTED OR
`
`BUS IDLE FOR
`MAXIMUM
`IDLE PERIOD
`
`BUS JAM
`DETECTED
`
`BUS IDLE FOR
`MAXIMUM
`IDLE PERIOD
`
`I JAM THE BUS I
`
`JAM PERIOD
`ELAPSED
`
`WAIT FOR ALL
`JAMMERS TO FINISH
`
`BUS
`OWNERSHIP
`MESSAGE r-----.
`NOT THE
`DETECTED
`BUS
`MASTER
`
`JAMMING
`CEASES
`
`IFRAME I
`
`GAP
`FRAME GAP
`TIME ELAPSED
`
`I WAIT FOR I
`Mth SLOT I
`M SLOT
`ELAPSED
`
`TRANSMIT BUS
`ONERSHIP
`MESSAGE
`
`TRANSMITTER
`IS BUS
`MASTER
`
`Exhibit 1321 Page 04 of 25
`
`

`
`U.S. Patent
`
`Sep. 12, 1995
`
`Sheet 4 of 10
`
`5,450,404
`
`fig.5
`
`TRANSMITIER RESET OR
`POWER TURNED ON
`
`ANY ERROR OR
`"TRANSMITIER CONFUSED"
`
`RESYNCHRONIZE -WAIT FOR:
`
`'
`
`t
`
`BUS JAM
`
`NODE
`ADMISSION
`PERMflTED
`
`BUS JAM
`DETECTED
`
`-
`
`OR
`
`BUS IDLE FOR
`MAXIMUM
`IDLE PERIOD
`
`NODE ADMISSION PERIOD
`OR BUS IDLE FOR
`MAXIMUM IDLE PERIOD
`
`JAM THE BUS I
`
`JAM PERIOD
`ELAPSED
`
`WAIT FOR ALL
`JAMMERS TO FINISH
`
`JAMMING
`CEASES
`
`FRAME
`GAP
`\
`FRAME GAP
`TIME ELAPSED
`
`BUS
`OWNERSHIP
`MESSAGE
`
`I WPJT FOR I DETECTED
`
`. Mth SLOT I
`, M SLOT
`ELAPSED
`
`.-------'----.
`NOT THE
`BUS
`MASTER
`
`RECEIVED
`TOKEN
`
`TRANSMIT BUS
`ONERSHIP
`MESSAGE
`
`I PASS I
`
`TOKEN
`
`TRANSMIT
`MESSAGES
`
`DONE
`TRANSMITTING
`
`Exhibit 1321 Page 05 of 25
`
`

`
`U.S. Patent
`
`Sep. 12, 1995
`
`Sheet 5 of 10
`
`5,450,404
`
`fig.6
`TRANSMmER RESET
`POWER TURNED ON
`
`ANY ERROR OR
`"TRANSMITTER CONFUSED"
`
`RESYNCHRONIZE-WAIT FOR:
`
`'
`
`t
`
`JAM
`DETECTED
`
`OR
`
`BUS IDLE FOR
`N SLOT TIMES
`+
`FRAME GAP
`
`BUS JAM
`DETECTED
`
`N SLOT TIMES
`+
`FRAME GAP
`IDLE ELAPSED
`
`I BUS IDLE
`
`BUS JAM
`DETECTED
`
`WAIT FOR ALL
`JAMMERS TO FINISH
`
`JAMMING
`CEASES
`
`~t--­
`TRAFFIC READY
`TO SEND
`[JAM THE BUS j
`
`JAM PERIOD
`ELAPSED
`
`!FRAME
`
`GAP
`FRAME GAP
`TIME ELAPSED
`
`MESSAGE
`DETECTED
`WAIT FOR
`. - - - - - - -I Mth SLOT
`
`M SLOT
`ELAPSED
`
`MESSAGES
`READY
`TRANSMIT?
`
`y
`
`N
`MESSAGE ,.-----l~-o---.
`...-----'--- DETECTED WAIT FOR
`!sus BUSY:
`REST OF
`SLOTS
`
`TRANSMISSION
`COMPLETED
`
`TRANSMIT
`~._M_Es_s_A_G_Es_. TRANSMISSION
`COMPLETED
`
`Exhibit 1321 Page 06 of 25
`
`

`
`U.S. Patent
`
`Sep. 12, 1995
`
`Sheet 6 of 10
`
`5,450,404
`
`fig.7
`
`TRANSMITTER RESET OR
`POWER TURNED ON
`
`ANY ERROR OR
`"TRANSMITIER CONFUSED"
`
`RESYNCHRONIZE-WAIT FOR:
`
`'
`
`BUS IDLE FOR
`MAXIMUM
`IDLE PERIOD
`
`BUS IDLE FOR
`MAXIMUM
`IDLE PERIOD
`
`SHORT BUS
`JAM
`DETECTED
`
`SHORT
`JAM
`DETECTED
`
`NOT THE
`BUS MASTER
`
`BUS
`OWNERSHIP
`MESSAGE
`DETECTED
`
`JAM
`DETECTED
`
`OR
`
`BUS JAM
`DETECTED
`
`JAMMING
`CEASES
`
`JAM PERIOD
`ElAPSED
`
`SECONDARY
`FRAME GAP
`FRAME GAP
`TIME ELAPSED
`
`TRANSMIT BUS
`OWNERSHIP
`MESSAGES
`
`TRANSMISSION
`COMPLETED
`
`TRANSMITTER
`IS BUS MASTER
`
`Exhibit 1321 Page 07 of 25
`
`

`
`U.S. Patent
`
`Sep. 12, 1995
`
`Sheet 7 of 10
`
`5,450,404
`
`TRANSMmER RESET OR
`POWER TURNED ON
`
`ANY ERROR OR
`•TRANSMITIER CONFUSED•
`~
`RESYNCHRONIZE-WAIT FOR:
`
`•
`
`jig.B
`
`JAM
`DETECTED
`
`BUS IDLE FOR
`OR L SLOT TIMES +
`FRAME GAP
`L SLOT TlMES +
`FRAME GAP
`IDLE ELAPSED
`
`BUS JAM
`DETECTED
`
`ORT
`SH
`JAM
`
`CTED DETE
`
`t TRANSMISSION
`I BUS IDLE!
`COMPLETED L BUS BUSY j
`~1fl
`
`READY
`TO SEND
`
`JAM THE BUS I
`
`BUS JAM
`DETECTED
`
`I WAIT FOR ALL
`I
`JAMMERS TO FINISH I
`JAMMING
`CEASES
`
`JAM PERIOD!
`ElAPSED
`
`MESSAGE
`DETECTED
`
`SHORT
`JAM
`
`JWAIT FORi
`I OTHERS
`
`I ~JEl
`FRAME cJAP
`TlME ELAPSED
`I WAIT FOR I DETECTED
`Gth SLOT I
`G SLOT
`ELAPSED
`JAM THE BUS I
`
`y
`
`MESSAGE
`READY TO
`TRANSMIT ?
`N
`
`(GROUP)
`
`FRAME GAP
`FRAME GAP
`TlME ELAPSED
`
`I SECONDARY I
`
`TRANSMISSION
`COMPLETED
`
`.I TRANSMIT l-
`
`I
`I WAIT FOR I
`Hth SLOT J H SLOTS l MESSAGE
`ELAPSED
`
`I WAIT FOR I
`
`Gth SLOT
`SHORT
`JAM
`DETECTED
`
`Exhibit 1321 Page 08 of 25
`
`

`
`U.S. Patent
`
`Sep. 12, 1995
`
`Sheet 8 of 10
`
`5,450,404
`
`fig.9
`
`ANY ERROR OR
`TRANSMITTER RESET
`"TRANSMITIER CONFUSED"
`POWER TURNED ON
`~
`~
`RESYNCHRONIZE-WAIT FOR:
`
`BUS JAM
`
`MESSAGE
`DETECTED
`
`BUS IDLE FOR
`OR N SLOT TIMES +
`FRAME GAP
`N SLOT TIMES +
`FRAME GAP
`IDLE ELAPSED
`
`BUS JAM
`DETECTED
`
`MESSAGE
`DETECTED
`
`BUS JAM
`DETECTED
`
`I BUS IDLE J
`
`[......___, TRAFFIC
`READY
`TO SEND
`
`,.JAM THE BUS I
`
`JAM PERIOD
`ELAPSED
`
`I WAA FOR ALL
`
`JAMMERS TO FINISH I
`JAMMING
`CEASES
`
`TRANSMISSION
`COMPLETED
`
`I,.....B_U_S__._BU-SY----..1
`
`1
`
`J FRAME(.,_. ____
`--,
`·1 GAP
`I TRANSMISSION
`FRAME GAP
`COMPLETED
`TIME ELAPSED
`
`MESSAGE
`DETECTED
`
`WAIT FOR
`Mth SLOT
`M SLOTS
`ELAPSED
`
`MESSAGE
`READY TO
`TRANSMIT ?
`N
`
`y
`
`TRANSMIT
`MESSAGE
`
`MESSAGE
`WAIT FOR
`DETECTED
`' - - - - - - - - - - - - l REST OF
`SLOTS
`ANOTHER
`N-M SLOTS
`ELAPSED ~-------------~
`
`Exhibit 1321 Page 09 of 25
`
`

`
`U.S. Patent
`
`Sep. 12, 1995
`
`Sheet 9 of 10
`
`5,450,404
`
`TRANSMITIER RESET
`POWER TURNED ON
`
`ANY ERROR OR
`MTRANSMITTER CONFUSED•
`
`fig . f 0
`
`RESYNCHRONIZE-WAIT FOR:
`
`JAM
`DETECTED
`MESSAGE OR
`DETECTED
`
`BUS IDLE FOR
`N+Q SLOT TIMES +
`FRAME GAP
`
`MESSAGE
`DETECTED
`
`BUS JAM
`DETECTED
`
`N+Q SLOT TIMES +
`FRAME GAP
`IDLE ELAPSED
`f
`I BUS IDLE-I
`DETECTED ~ TRAme READY
`BUS JAM
`•
`TO SEND
`
`I WAIT FOR ALL
`
`JAMMERS TO FINISH
`
`JAM THE BUS I
`JAM PERID OT
`ELAPSED I
`
`I
`
`JAMMING
`CEASES
`TRANSMISSION
`r~BUS-_.._B_USY~1 COMPLETED I~MEI~------------------~
`l GAP
`I TRANSMISSION
`FRAME GM'
`COMPLETED
`TIME ELAPSED
`
`PRIORITY
`MESSAGE TO
`TRANSMIT ?
`
`y
`
`P SLOTS
`TRANSMIT
`.--W-AI_T_F_O_R...,.I ELAPSED
`Pth SLOT 11-----tiOOol I.D. AND
`MESSAGE
`
`N
`WAIT FOR
`MESSAGE
`._D_ETE_ CTE_ D_---1 REST OF
`SLOTS
`Q SLOTS
`ELAPrS=;ED::.......J---.
`MESSAGE
`~..::D..=ffi.:-=.:::C..:...:TE=D:___----" WAIT FOR
`Rth SLOT
`R SLOTS
`ELAPSED
`MESSAGE
`READY TO
`TRANSMIT ?
`N
`MESSAGE
`WAIT FOR
`DETECTED
`ANOTHER
`L-- -- - ---1 REST OF
`.__SL""''O~T_s ...... N-R SLOTS
`I
`ELAPSED
`
`y
`
`MESSAGE
`DETECTED
`
`Exhibit 1321 Page 10 of 25
`
`

`
`U.S. Patent
`
`Sep. 12t 1995
`
`Sheet 10 of 10
`
`5,450,404
`
`TRANSMITIER RESET OR
`POWER TURNED ON
`~
`RESYNCHRONIZE-WAIT FOR:
`
`ANY ERROR OR
`~TRANSMITTER CONFUSED"
`
`'
`
`fi g. 11
`
`SHORT
`JAM
`DETECTED
`
`JAM
`DEfECTED
`MESSAGE OR
`DETECTED
`
`BUS JAM
`DETECTED
`
`MESSAGE
`DETECTED
`
`BUS JAM ----'
`DETECTED
`
`BUS IDLE FOR
`W SLOT TIMES +
`FRAME GAP
`W SLOT TlMES +
`FRAME GAP
`IDLE ELAPSED
`t
`I BUS IDLE I
`~TRAFFIC READY
`TO SEND
`JAM THE BUS I
`JAM PERIOD~
`ELAPSED
`
`I WAIT FOR ALL
`JAMMERS TO FINISH I
`JAMMING
`CEASES
`TRANSMISSION
`II BUS BUSY I COMPLETED J FRAME I
`I GAP
`I TRANSMISSION
`COMPLETED
`FRAME GAP
`TIME ELAPSED
`
`I
`
`MESSAGE I
`
`--1 WAfT FOR L
`I
`
`yN
`WAIT FOR
`REST OF
`SLOTS
`I
`
`ANOTHER
`J-Y SLOTS
`ELAPSED
`
`P SLOTS
`y WAIT FOR I ELAPSED
`Pth SLOT I
`
`I
`
`TRANSMIT
`I.D. AND
`MESSAGE
`
`PRIORITY
`MESSAGE TO
`TRANSMIT ?
`
`-
`MESSAGE
`DETECTED
`ANY SIGNAL
`. DETECTED
`
`N
`WAIT FOR
`ALL FIXED
`SLOTS
`0 SLOTS
`Am SIGNAL ELAPSED
`DETECTED
`WAIT FOR
`Yth SLOT
`Y SLOTS
`ELAPSED
`
`READY TO
`TRANSMIT ?
`
`_I
`JAM THE
`I BUS (GROUP)
`I SECONDARY I
`•
`MESSAGE y TIME ElAPSED
`
`FRAME GAP
`FRAME GAP)~
`~ WAIT FOR I
`Zth SLOT I Zth SLOT
`ELAPSED
`ANY SIGNAL
`DETECTED
`
`Exhibit 1321 Page 11 of 25
`
`

`
`EXPLICIT AND IMPLICIT TOKEN MEDIA
`ACCESS PROTOCOL WITH MULTI-LEVEL BUS
`ARBITRATION
`
`TECHNICAL FIELD
`This invention relates to computer communication
`protocols, and in particular, to a Reservation Carrier
`Sense Multiple Access (RCSMA) media access scheme.
`
`BACKGROUND OF THE INVENTION
`If multiple transceivers attempt to use a medium si(cid:173)
`multaneously, the transmissions collide, resulting in
`garbled messages and potentially lost data. Media Ac(cid:173)
`cess Control (MAC) protocols are used to arbitrate 15
`which transceiver has possession of a medium at any
`given time. Arbitration is the process by which one of
`multiple peer transceivers desiring access to the bus
`obtains it. The subset of MAC protocols of interest is
`those protocols used to implement Local Area Net- 20
`works (LANs) using a shared transmission medium.
`The terms "explicit token" and "implicit token" are
`used herein. Explicit tokens are actual messages that arc
`passed from transceiver to transceiver as control of the
`medium is passed. Ownership of the token grants sole 25
`right to transmit. Token ownership is relinquished to
`another transceiver by sending a tokc!n message. Im·
`plicit tokens are time slots which, if used grant exclu(cid:173)
`sive access to the medium. They are implicit because no
`real token message exists. Rather, each implicit token 30
`time slot period on the communications medium carries
`with it the meaning of a token-to-transceiver assign(cid:173)
`ment.
`A. MEDIA ACCESS CONTROL PROTOCOL SE(cid:173)
`LECTION
`1. EXEMPLARY ELEVATOR SYSTEM
`In the communication protocol selection process, a
`number of factors should be considered. An exemplary
`application to illustrate some of these factors is an eleva(cid:173)
`tor system which uses twisted-pair wires as a shared 40
`communications medium.
`Of further interest are LANs that apply to embedded
`and real time control applications that require predict(cid:173)
`able and/or deterministic system response.
`2. FACTORS TO BE CONSIDERED IN MEDIA 45
`ACCESS PROTOCOL SELECTION IN LIGHT OF
`PRIOR ART
`First, collision detection circuits are impracticable in
`some elevator communications systems. Analog colli(cid:173)
`sion detection techniques rely on approximately equal so
`signal strengths from colliding transmitted signals.
`However, in a large building, signals over twisted pair
`wires are severely attenuated over 2000 feet, so signal
`strengths from some transceiver pairs are very unequal.
`Second, real time response requirements of elevator 55
`systems, for purposes of safety and control loop stabil(cid:173)
`ity, require both predictable and bounded message
`transmission delays. In some protocols, such as
`CSMA/CD, there is no guarantee that any particular
`message will be delivered within a bounded time inter- 60
`vaL
`Third, many protocols do not allow for deterministic
`prioritization of network access as required by elevator
`control loops and safety schemes. CSMA/CD, for ex(cid:173)
`ample, provides no guarantees for priority service.
`Fourth, some protocols (e.g., CSMA/CD) make inef(cid:173)
`ficient use of network bandwidth under heavy loading
`conditions. Existing elevator systems often have slow-
`
`1
`
`5,450,404
`
`10
`
`2
`speed low-grade wire that must be efficiently used to
`avoid the expense of installing newer, higher-speed
`media.
`Fifth, some protocols, such as explicit-token based
`5 protocols, are vulnerable to system failures if the token
`is lost or duplicated and are slow to recover from such
`failures. Elevator control requires quick recovery from
`a network protocol failure in order to maintain positive
`control over moving machinery.
`Sixth, it is desirable that broadcast messages be used
`in such a way as to eliminate the need for acknowledg(cid:173)
`ments because multiple acknowledgment messages take
`up bandwidth. Therefore, lack of acknowledgment is
`not available as an indirect means for detecting colli(cid:173)
`sions.
`Seventh, elevators must be able to function in the face
`of failures, and so must not have the single-point failure
`vulnerability inherent in a central communications me(cid:173)
`dium master.
`Eighth, some protocols support only a limited num(cid:173)
`ber of transceivers. For example, implicit token proto(cid:173)
`cols become inefficient as the number of implicit token
`lime slots grows large because slot widths must account
`for oscillator drift. Integration of building-wide sensors
`and actuatots (sut;h as hall call buttons at each landing)
`and other building services make a capability to expand
`lhe number of transceivers to a large number highly
`desirable.
`B. FURTHER REVIEW OF PRIOR ART
`I. SYNCHRONOUS TDM PROTOCOLS
`In many communications systems there is a need to
`occasic·nally resynchronize all transceivers to a com(cid:173)
`mon point in time. One reason synchronization is
`35 needed is that the local clock for each transceiver (usu(cid:173)
`ally based on a crystal oscillator or resistor I capacitor
`oscillator circuit) runs at a slightly different speed from
`local clocks at other transceivers. Factors contributing
`to this clock drift include component manufacturing
`variations, aging effects, and temperature variations.
`Another reason for resynchronization is so that a
`newly activated transceiver (or one recovering from an
`error state) can join into a. communication protocol
`currently active among other transceivers using the
`communication medium even in the absence of message
`transmissions.
`Communication protocols in which the absence of
`continual messages implies a bus idle state can use the
`messages themselves as resynchronization poinrs. How(cid:173)
`ever, some protocols, notably synchronous Time Divi-·
`sion Multiplexing (syncbronou.s TDM) protocols, are
`implemented such that tbe transceiver fmite state ma(cid:173)
`chine is in a state other than BUS IDLE for long peri(cid:173)
`ods of time, even though no messages are being sent.
`These protocols, including synchronous TDM, usually
`use explicit resynchronization signals to limit the accu-
`mulated clock drift over time between different trans(cid:173)
`ceivers.
`There is a maximum clock drift that can be tolerated
`while still maintaining synchronized transmission and
`reception within a protocol. For example, if two trans(cid:173)
`ceivers are to take turns transmitting based on time
`alone (as opposed to detection of other transmissions), a
`pad time must be allowed between consecutive trans-
`65 missions to allow for clock drift. Accumulated clock
`drift must be kept smaller than this pad time for collision
`avoidance and, therefore, correct operation. A good
`way of accomplishing this is to schedule a resyncbroni-
`
`Exhibit 1321 Page 12 of 25
`
`

`
`5,450,404
`
`3
`zation just before the accumulated clock drift goes out
`of tolerance. One way to do this is to perform resyn(cid:173)
`chronization at fixed intervals (based on worst case
`clock drift design analysis) regardless of the protocol in
`use.
`If the protocol is fixed-length time-slice synchronous
`TOM, a resynchronization is performed at the start of
`each transmission frame, using a frame sync signal.
`Perhaps the most straightforward communication
`scheme is synchronous Time Division Multiplexing 10
`(synchronous TOM). In the traditional master/slave
`implementation, a single transceiver is designated as the
`bus master. This bus master queries each transceiver in
`tum, allowing each transceiver to transmit a message
`when queried. This system has high overhead because 15
`of the query messages and responses that must be gener(cid:173)
`ated even when the responding transceiver has no use(cid:173)
`ful messages to send. This system also has the obvious
`reliability problem of a single master.
`Still more sophisticated versions of synchronous 20
`TOM are possible. For example, a single bus master
`may simply transmit a frame synchronization message
`("frame sync"), allowing all other transceivers to mea(cid:173)
`sure a unique time delay from that frame sync. Com(cid:173)
`monly, synchronous TOM protocols employ a single 25
`designated bus master transceiver to issue the frame
`sync signal. This has obvious limitations in terms of
`reliability and designation of the common bus master.
`Each transceiver then may transmit during its own
`window of time ("time slice") after the frame sync. In 30
`even more sophisticated versions, other transceivers
`sense whether there is activity on the bus, and cut short
`unused time slices.
`All synchronous TOM protocols have a problem in
`determining which transceiver is the bus master. Either 35
`it must be predesignated, or arbitration among trans(cid:173)
`ceivers must be performed to designate a master at
`system initialization. Synchronous TOM protocols
`make no provision for priority messages on a global
`basis; the highest priority message in each transceiver's 40
`outgoing queue must wait for that transceiver's time
`slice.
`2. EXPLICIT TOKEN PROTOCOLS
`As mentioned previously, an explicit token is a mes(cid:173)
`sage that is passed from transceiver/receiver to trans- 45
`ceiver/ receiver as control of the medium is passed. In
`explicit token protocols known to the art, the initial
`token holder is either designated as a predetermined
`transceiver on the network (leading to reliability prob(cid:173)
`lems if that predetermined transceiver becomes non- 50
`functional) or is determined via a potentially lengthy
`arbitration method involving collision detection.
`3. CONTENTION-BASED AND COLLISION(cid:173)
`A VOIDANCE PROTOCOLS
`Contention-based protocols are protocols in which 55
`multiple transceivers contend for access to the commu(cid:173)
`nications medium asynchronously.
`A simple media access protocol for LANs is Carrier
`Sense Multiple Access (CSMA), where "Carrier Sense"
`refers to the ability of a transceiver to detect data being 60
`asserted on the communication medium. When a trans(cid:173)
`ceiver has an outgoing message, it first performs carrier
`sensing to see if the medium is busy. If the medium is
`idle, it then transmits a message. Receipt acknowledg(cid:173)
`ments are required, because there is a possibility of two 65
`transceivers beginning transmission nearly simulta(cid:173)
`neously (within a propagation delay along the commu(cid:173)
`nications medium, known as the vulnerable period)
`
`4
`with a resultant collision and loss of data. This method
`has poor performance at high load and has poor real(cid:173)
`time performance characteristics.
`An improvement over CSMA is Carrier Sense Multi-
`5 pie Access with Collision Detection (CSMA/CD).
`When two transceivers begin transmission onto the
`medium within the vulnerable period a collision detec(cid:173)
`tion circuit is able to detect the resultant collisions, and
`truncate the transmission of data from both transceiv-
`ers.
`Collision avoidance CSMA protocols (CSMA/CD)
`use time slots after each collision and transmission to
`reduce the change of subsequent collisions.
`One variation of CSMA/CD that is suited to embed(cid:173)
`ded and real time control communications is Reserva(cid:173)
`tion Carrier Sense Multiple Access
`(RCSMA).
`RCSMA is an implicit token system in which there is a
`sequence of time slots after each transmitted message.
`In RCSMA, one time slot is assigned to each trans(cid:173)
`ceiver. If any transceiver has a message to send, it waits
`for its slot (measured as a unique time delay for each
`transceiver from the end of the previous message).
`When a transceiver's time slot is elapsing on the com(cid:173)
`munications medium, the transceiver can start transmit(cid:173)
`ting a message with a guarantee that it is the sole active
`transceiver (because of the one-to-one mapping of slots
`to transceivers). If a transceiver bas no message to send,
`it remains idle and its time slot elapses, allowing the next
`transceiver's time slot to start. The slots are referred to
`as implicit tokens, because asserting data during a slot is
`functionally equivalent to acquiring a token for medium
`access. Elaborations upon RCSMA known in the art
`include assigning slots in different groupings to imple(cid:173)
`ment priority levels and implementing a "slot rotation"
`in which the position of slot changes based on the last
`transceiver active in order to implement fair access to
`the medium.
`RCSMA schemes require either implementation of
`collision detection or have slow restarts from protocol
`errors. Also, RCSMA suffers from a limitation in the
`number of transceivers supported in that as the number
`of transceivers grows the number of implicit token slots
`becomes too large to be practical.
`C. RESTARTING THE PROTOCOL FROM AN
`IDLE MEDIUM
`Part of selecting a media access protocol is selecting
`a protocol for restarting the protocol on an idle net-
`work.
`·
`In RCSMA, implicit token slots begin to elapse at the
`end of a transmitted message. However, a problem
`arises when there is no message to be sent, allowing all
`slots to elapse unused. The question is, how is a new slot
`progression initiated in the absence of a message? There
`are four strategies known to the art.
`D. NETWORK RESTART
`I. NETWORK RESTART WITH ARBITRA(cid:173)
`TION
`The NETWORK RESTART WITH ARBITRA(cid:173)
`TION technique for RCSMA is taught by Kiesel and
`Kuehn, IEEE Journal on Selected Areas in Communica(cid:173)
`tions, Vol. SAC-1, No. 5, November 1983, pages
`869-876. We shall refer to this method as the Reserva(cid:173)
`tion Carrier Sense Multiple Access/Collision Detection
`(RCSMA/CD) scheme.
`If the network is idle when a transceiver acquires a
`message to send, the transceiver begins transmitting
`data immediately as in CSMA/CD. Implicit token slots
`begin after each message. If there is a collision, the
`
`Exhibit 1321 Page 13 of 25
`
`

`
`5,450,404
`
`6
`sions repeat indefinitely without frame synchronization
`while the network remains idle.
`The mastership is "distributed" among all transceiv(cid:173)
`ers. There are several problems with using this scheme
`for the exemplary elevator communications application:
`(a) the time bases must be very stable over periods of
`time when the network is idle. In the DATAC
`application this problem is controlled by using
`expensive redundant oscillators;
`(b) a transceiver that has lost track of the protocol
`state through some transient error or reset cannot
`immediately access the network while the network
`is idle, because there are no transmissions on the
`network to indicate where, in the time slot progres(cid:173)
`sion, other transceivers are located;
`(c) system power-on and reset problems remain be-
`cause the initial active transceiver must be chosen.
`DATAC uses an unspecified method of collision
`detection for system initialization; and
`(d) this method does not overcome the practicallimi-
`tation on the number of slots and therefore the
`number of transceivers on the network.
`Our new protocols are well suited to embedded real
`time control and avoid the key disadvantages of previ-
`25 ous protocols: (a) single point of failure and (b) need for
`collision detection.
`
`15
`
`5
`transceivers cease transmitting, and treat the collision
`event as equivalent to the end of a message. Thus, a slot
`progression begins after a collision as if a message had
`just been issued. This technique addresses the problem
`of what to do when there is no network traffic by sim- 5
`ply letting the medium go idle and providing for a quick
`restarting capability.
`Collision detection is required for implementation,
`and this method does not overcome the practical limita(cid:173)
`tion on the number of slots and therefore the number of 10
`transceivers on the network. There is a practical limit
`on the number of slots because beyond a certain number
`of transceivers, the clocks of transceivers at opposite
`ends of the medium may be so out of sync that they
`transmit in the same slot.
`2. SINGLE MASTER
`A SINGLE MASTER can be used to restart token
`flow periodically. One way this can be done is for a
`master to emit frame synchronization signals that start a
`progression of implicit token slots. If all slots have 20
`elapsed without a transmission on the communications
`medium, the master generates a new frame synchroniza-
`tion signal to start a new slot progression. By relying on
`a single master, there is always a source of periodic
`restarts (frame synchronization signals).
`Problems with using a single master approach are
`that:
`(a) the single master represents a single point of fail(cid:173)
`ure vulnerability within the system,
`(b) the master is an extra component separate from 30
`the other nodes that must be separately designed
`and fabricated, and
`(c) this method does not overcome the practical limi(cid:173)
`tation on the number of slots and therefore the
`number of transceivers on the network.
`3. ROTATING MASTER
`A ROTATING MASTER is taught in "Demand
`Assignment Multiple Access Schemes in Broadcast Bus
`Local Area Network", IEEE Transactions on Comput(cid:173)
`ers, Volume C-33, No. 12, December 1984, Pages 40
`1130-1159), by Michael Fine and Fouad Tobogi. This
`method prevents the bus from going idle by continually
`issuing dummy messages.
`However, there are shortcomings in the rotating
`master approach that make it inappropriate for the ex- 45
`emplary elevator application, including the following:
`(a) the rotating master still represents a subtle, single
`point of failure vulnerability. If the current master
`should fail, it will not issue a dummy message and
`the network will go idle; and
`(b) this method does not overcome the practical limi(cid:173)
`tation on the number of slots and therefore the
`number of transceivers on the network.
`4. STABLE TIME BASE
`Another approach to implementing RCSMA is for 55
`the system to use stable time bases, also known as DIS(cid:173)
`TRIBUTED MASTERS, to avoid the need for a cen(cid:173)
`tral or rotating master. The DA T AC system chip set
`from National Semiconductor uses this approach for a
`synchronous TDM implementation. In this scheme, 60
`each transceiver uses a stable time base that does not
`skew significantly over periods when the network goes
`idle (the stable time base is implemented in the DATAC
`chip set by having two cross-checked oscillators instead
`of only one). After each message, a slot progression is 65
`initiated. Whenever the slot progression is completed
`with no network activity, a new slot progression is
`automatically initiated. In other words, slot progres-
`
`50
`
`35
`
`DISCLOSURE OF THE INVENTION
`A first object of the present invention is a media
`access protocol with deterministic (i.e., repeatable),
`predictable, and bounded response times for routine and
`priority messages; highly efficient use of available com(cid:173)
`munications media bandwidth; and fast initialization
`and recovery from transient and permanent transceiver
`failures without any need for collision detection or bit
`dominance.
`A second object of the present invention is an implicit
`token media access protocol that supports a plurality of
`transceivers assigned to individual token slots without
`requiring collision detection. This objective is in sup(cid:173)
`port of multiple transceivers at the same priority level
`within a slot progression. A consequence of this slot(cid:173)
`sharing capability is a significant increase in the number
`of transceivers which can be supported.
`·
`The present invention is predicated on the observa(cid:173)
`tion that some communication protocols involve colli(cid:173)
`sion detection by collision detection circuitry followed
`by transmission of a predetermined, nondestructively
`interfe~ng, jam signal. This use of a jam signal enhances
`collision detection among a plurality of transceivers
`because transmission of the jam signal informs all trans(cid:173)
`ceivers that a collision has occurred.
`The present invention is further predicated on the
`observation that synchronization of a plurality of trans(cid:173)
`ceivers is required to start a sequence of events within a
`communications protocol for shared medium access.
`One way to accomplish this is to have each transceiver
`desiring to initiate the sequence of events assert a mes(cid:173)
`sage onto the communications medium. The problem
`with this method as currently practiced in the art is that
`collisions will take place if two transceivers assert such
`initiation messages within the "vulnerable time" (re(cid:173)
`lated to signal propagation delay) of the network. Said
`collisions corrupt data being sent and fail to establish
`unique ownership of the communications medium; fur(cid:173)
`thermore, detecting such collisions is undesirable.
`It follows from the first predicate that the present
`invention provides a means for synchronization of a
`
`Exhibit 1321 Page 14 of 25
`
`

`
`5,450,404
`
`BEST MODE FOR CARRYING OUT THE
`INVENTION
`Co-pending applications Ser. No. (Attorney Docket
`No. OT-1451) entitled "Implicit Token Media Access
`Protocol Without Collision Detection" and Serial No.
`(Attorney Docket No. OT-1746) entitled "Synchronous
`Time Division Multiplexing Using Jam-based Frame
`Synchronization" are hereby incorporated by refer(cid:173)
`ence. An exemplary means for transmitting and receiv(cid:173)
`ing is shown therein.
`
`7
`8
`plurality of transceivers on a shared communications
`BRIEF DESCRIPTION OF THE DRAWINGS
`medium using a ''jamming" signal, thereby eliminating
`FIG. 1 is a block diagram of a plurality of tran-
`requirements to use collision detection or a centralized
`sceiver/receiver nodes coupled to a shared communica-
`bus master. As a consequence of the second predicate,
`one way to use such a synchronization technique is to 5 tion medimn;
`let the jam signal serve as a unique time point from
`FIG. 2 is a finite state diagram for synchronizing a
`which to start an implicit token slot progression.
`plurality of transceivers;
`FIG. 3 is a finite state diagram for implementing
`According to the present invention, a collision, multi-
`pie signals transmittin