`Koopman et al.
`
`Ulllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll
`US005450404A
`5,450,404
`[11] Patent Number:
`[45) Date of Patent:
`Sep. 12, 1995
`
`[54] EXPLICIT AND IMPLICIT TOKEN MEDIA
`ACCESS PROTOCOL WITH 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
`Dec. 21, 1992
`[22] Filed:
`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 a!. ......................... 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 eta!. ................. 370/85.1
`
`[56)
`
`4,763,321 8/1988 Calvignac eta! .................. 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-Chau T. Nguyen
`
`(57]
`ABSTRACT
`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 Oaims, 10 Drawing Sheets
`
`TRANSMITTER RESET OR
`POWER nJRNEtl ON
`
`ANY ERROR OR
`"TRANS\IrrTER CONFUSED"
`
`I
`
`RESYNCHRONIZE-WAIT i'OR'
`
`D~ OR
`
`SHORT BUS
`JAM
`DETECTED
`
`SHORT
`JAM
`CETEcrnl
`
`NOT THE
`BUS MASTER
`
`BUS
`OWNERSHIP
`MESSAGE
`DETECTED
`
`Exhibit 1233 Page 01 of 25
`
`
`
`U.S. Patent
`
`Sep. 12, 1995
`
`Sheet 1 of 10
`
`5,450,404
`
`fig. I
`
`'
`
`~
`
`h
`
`l
`
`COMMUNICATIONS MEDIUM
`1
`I
`
`TRANSMITIER
`AND
`RECEIVER
`
`TRANSMITIER
`AND
`RECEIVER
`
`1\
`
`J
`
`1\
`
`TRANSMITIER
`AND
`RECEIVER
`
`fig.2
`
`OPERATION
`BEFORE
`SYNCHRONIZATION
`
`BUS
`JAM
`
`DETE CTED
`
`T RANSMITIER
`TO GENERATE
`NEEDS
`
`SYNC HRONIZATION
`EVENT
`
`1 JAM THE susJ
`
`JAM P ERIOD
`
`ELAP SED
`
`WAIT FOR ALL
`JAMMERS TO FINISH
`
`JAMMING
`CEASES
`
`SYNCHRONIZATION
`ACHIEVED
`
`OPERATION AFTER
`SCNCHRONIZATION
`
`Exhibit 1233 Page 02 of 25
`
`
`
`U.S. Patent
`
`Sep. 12, 1995
`
`Sheet 2 of 10
`
`5,450,404
`
`fig.3
`
`TRANSMITIER RESET
`POWER TURNED ON
`
`ANY ERROR OR
`"TRANSMITIER CONFUSED"
`~
`RESYNCHRONIZE-WAIT FOR:
`
`t
`
`JAM
`DETECTED
`
`IDLE FOR
`BUS
`OR N SLICE TIMES
`+
`FRAME GAP
`
`BUS JAM
`DETECTED
`
`N SLICE TIMES
`+
`FRAME GAP
`IDLE ELAPSED
`.---.1...-----L---,
`
`I JAM THE BUS I
`
`I
`JAM PERIOD
`ELAPSED
`
`WPJT FOR ALL
`JAMMERS TO FINISH
`
`JAMMING
`CEASES
`
`I FRAME
`
`GAP
`FRAME GAP
`TIME ELAPSED
`
`WPJT FOR
`Mth SLICE
`M TIME SLICE
`ELAPSED
`
`TRANSMIT I
`BUS JAM
`MESSAGE 11----~
`DETECTED
`
`TRANSMISSION
`TIME SLICE
`ELAPSED
`
`WAIT FOR
`REST OF 1 - - - - - - l
`SLICES
`
`ANOTHER
`N-M-1 SLICES
`ELAPSED
`
`Exhibit 1233 Page 03 of 25
`
`
`
`U.S. Patent
`
`Sep. 12, 1995
`
`Sheet 3 of 10
`
`5,450,404
`
`fig.4
`TRANSMITIER RESET OR
`POWER TURNED ON
`
`ANY ERROR OR
`"TRANSMITIER CONFUSED"
`
`+
`'
`RESYNCHRONIZE-WAIT FOR:
`
`JAM
`DETECTED OR
`
`BUS IDLE FOR
`MAXIMUM
`IDLE PERIOD
`
`BUS JAM
`DETECTED
`
`BUS IDLE FOR
`MAXIMUM
`IDLE PERIOD
`
`I JAM THE BUS 1
`
`JAM PERIOD
`ELAPSED
`
`WAIT FOR ALL
`JAMMERS TO FINISH
`
`JAMMING
`CEASES
`
`IFRAME I
`
`GAP
`FRAME GAP
`TIME ELAPSED
`
`BUS
`OWNERSHIP
`MESSAGE .------,.
`
`I WAIT FOR 1 DETECTED NOT THE
`
`~------~ BUS
`Mth SLOT I
`MASTER
`M SLOT
`ELAPSED
`
`TRANSMIT BUS
`ONERSHIP
`MESSAGE
`
`TRANSMITIER
`IS BUS
`MASTER
`
`Exhibit 1233 Page 04 of 25
`
`
`
`U.S. Patent
`
`Sep. 12, 1995
`
`Sheet 4 of 10
`
`5,450,404
`
`fig.S
`
`TRANSMilTER RESET OR
`POWER TURNED ON
`
`ANY ERROR OR
`"TRANSMilTER CONFUSED"
`
`t
`
`RESYNCHRONIZE-WAIT FOR:
`
`'
`
`BUS JAM
`
`NODE
`ADMISSION
`PERMilTED
`
`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
`
`l WAIT FOR l DETECTED
`
`. Mth SLOT I
`M SLOT
`ELAPSED
`
`,____._ __
`NOT THE
`BUS
`MASTER
`
`RECEIVED
`TOKEN
`
`TRANSMIT BUS
`ONERSHIP
`MESSAGE
`
`l PASS I
`
`TOKEN
`
`TRANSMIT
`MESSAGES
`
`DONE
`TRANSMilTING
`
`Exhibit 1233 Page 05 of 25
`
`
`
`U.S. Patent
`
`Sep. 12, 1995
`
`Sheet 5 of 10
`
`5,450,404
`
`fig.6
`ANY ERROR OR
`TRANSMmER RESET
`"TRANSMITTER CONFUSED"
`POWER TURNED ON
`~
`~
`RESYNCHRONIZE -WAIT FOR:
`
`JAM
`DETECTED
`
`OR
`
`BUS IDLE FOR
`N SLOT TIMES
`+
`FRAME GAP
`
`BUS JAM
`DETECTED
`
`N SLOT TIMES
`+
`FRAME GAP
`IDLE ELAPSED
`
`~
`l
`I BUS IDLE
`
`fl------,
`
`._____
`
`BUS JAM
`DETECTED
`
`WAIT FOR ALL
`JAMMERS TO FINISH I
`JAMMING
`CEASES
`
`TRAFFIC READY
`TO SEND
`
`l JAM THE BUS j
`
`JAM PERIOD
`ELAPSED
`
`MESSAGE
`DETECTED
`
`lFRAME
`
`GAP
`FRAME GAP
`TIME ELAPSED
`
`WArr FOR
`Mth SLOT
`M SLOT
`ELAPSED
`
`MESSAGES
`READY
`TRANSMIT?
`
`N
`MESSAGE r-----''---...
`.....------..~~----.. DETECTED WAIT FOR
`!BUS BUSY:
`REST OF
`SLOTS
`
`TRANSMISSION
`COMPLETED
`
`Y -
`
`TRANSMIT
`'-M-ES_S_A_G_Es___, TRANSMISSION
`COMPLETED
`
`Exhibit 1233 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"
`
`t
`
`RESYNCHRONIZE-WAIT FOR:
`
`JAM
`DETECTED
`
`OR
`
`BUS IDLE FOR
`MAXIMUM
`IDLE PERIOD
`
`BUS JAM
`DETECTED
`
`BUS IDLE FOR
`MAXIMUM
`IDLE PERIOD
`
`SHORT BUS
`JAM
`DETECTED
`
`SHORT
`JAM
`DETECTED
`
`NOT THE
`BUS MASTER
`
`BUS
`OWNERSHIP
`MESSAGE
`DETECTED
`
`JAM PERIOD
`ElAPSED
`
`SECONDARY
`FRAME GAP
`FRAME GAP
`TIME ELAPSED
`
`TRANSMIT BUS
`OWNERSHIP
`MESSAGES
`
`TRANSMISSION
`COMPLffiD
`
`TRANSMITTER
`IS BUS MASTER
`
`Exhibit 1233 Page 07 of 25
`
`
`
`U.S. Patent
`
`Sep. 12, 1995
`
`Sheet 7 of 10
`
`5,450,404
`
`TRANSMITIER RESET OR
`POWER TURNED ON
`
`ANY ERROR OR
`"TRANSMITIER CONFUSED"
`
`•
`
`RESYNCHRONIZE-WAIT FOR:
`
`t
`
`fig.B
`
`JAM
`DETECTED
`
`OR
`
`BUS IDLE FOR
`L SLOT TIMES +
`FRAME GAP
`
`SH
`ORT
`JAM
`DETE
`CTED
`
`BUS JAM
`DETECTED
`
`L SLOT TIMES +
`FRAME GAP
`IDLE ELAPSED
`
`t TRANSMISSION
`I BUS IDLE~ COMPLETED J BUS BUSY I
`
`BUS JAM
`DETECTED
`
`I WAIT FOR ALL
`JAMMERS TO FINISH I
`JAMMING
`CEASES
`
`~~~EJ
`
`TRAFFIC
`READY
`TO SEND
`IJAM THE susJ
`JAM PERIOD
`ELAPSED
`
`MESSAGE
`DETECTED
`
`FRAME GAP
`TIME ELAPSED
`
`Gth SLOTJ
`G SLOT
`ELAPSED
`
`SHORT
`JAM
`
`I
`
`I WAIT FOR I DETECTED WAIT FOR L
`I
`I OTHERS~
`JAM THE BUS I
`
`y
`
`MESSAGE
`READY TO
`TRANSMIT ?
`N
`
`I WAIT FOR j
`
`Gth SLOT
`SHORT
`JAM
`DETECTED
`
`(GROUP)
`
`I SECONDARY I
`
`FRAME GAP
`FRAME GAP
`TIME ELAPSED
`
`TRANSMISSION
`I
`COMPLETED
`I WAIT FOR I
`J TRANSMIT~
`Hth SLOT j H SLOTS ) MESSAGE
`ELAPSED
`
`Exhibit 1233 Page 08 of 25
`
`
`
`U.S. Patent
`
`Sep. 12, 1995
`
`Sheet 8 of 10
`
`5,450,404
`
`fig.9
`
`TRANSMITTER RESET
`POWER TURNED ON
`
`ANY ERROR 'OR
`"TRANSMITTER CONFUSED"
`
`RESYNCHRONIZE-WAIT FOR:
`
`'
`
`t
`
`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
`
`l
`I BUS IDLE I
`I.___, TRAFFIC
`READY
`TO SEND
`
`.JAM THE BUS I
`
`JAM PERIOD
`ELAPSED
`
`BUS JAM
`DETECTED
`
`I WAIT FOR ALL
`
`JAMMERS TO FlNISH
`
`JAMMING
`CEASES
`
`TRANSMISSION
`....-BU-S--'-8-USY---.... COMPLETED
`
`1,
`
`I FRAME L....._ _ __ _ __,
`I GAP J TRANSMISSION
`FRAME GAP
`COMPLETED
`TIME ELAPSED
`
`MESSAGE
`DETECTED
`
`WAIT FOR
`Mth SLOT
`M SLOTS
`ELAPSED
`
`MESSAGE
`READY TO
`TRANSMIT ?
`N
`
`Y _j TRANSMIT
`l MESSAGE
`
`MESSAGE
`WAIT FOR
`DETECTED
`~-----------1 REST OF
`SLOTS
`
`ANOTHER I
`N-M SLOTS
`ELAPSED L-----------~
`
`Exhibit 1233 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
`"TRANSMITTER CONFUSED"
`
`fig. 10
`
`RESYNCHRONIZE-WA!T FOR:
`
`JAM
`DITECTED
`MESSAGE OR
`DETECTED
`
`BUS IDLE FOR
`N+Q SLOT TIMES +
`FRAME GAP
`
`MESSAGE
`DETECTED
`
`BUS JAM
`DETECTED
`
`BUS JAM
`DITECTED
`
`I WAIT FOR ALL
`
`JAMMERS TO FINISH
`
`N+Q SLOT TIMES +
`FRAME GAP
`IDLE ELAPSED
`t
`l BUS IDLE I
`I
`TRAFFIC READY
`__j TO SEND
`JAM THE BUS I
`JAM PERIOD!
`ELAPSED j
`
`I
`
`JAMMING
`CEASES
`TRANSMISSION
`-BUS--L-B-USY----.J COMPLETED J~ME(~--------------------,
`I GAP J TRANSMISSION
`FRAME GAP
`COMPLETED
`TIME ELAPSED
`
`PRIORITY
`MESSAGE TO
`TRANSMIT ?
`
`y
`
`P SLOTS
`.---W-AI_T_F_O_R...,( ELAPSED
`TRANSMIT
`It------<- I.D. AND
`Pth SLOT
`MESSAGE
`
`1.
`
`N
`WAIT FOR
`MESSAGE
`.._D_ITE_ CTE_ D_--l REST OF
`SLOTS
`Q SLOTS
`ELAPr-S_ED~---.
`MESSAGE
`~..:::.D.;;;;.ITE;.;;;..;;..CTE.;..;;;.;;..D __ --1 WAIT FOR
`Rth SLOT
`R SLOTS
`ELAPSED
`MESSAGE
`READY TO
`TRANSMIT ?
`N
`WAIT FOR
`DETECTED
`ANOTHER
`L - - - - -- ---1 REST OF
`...__s_LOr-T_s ...... N-R SLOTS
`I MESSAGE
`-
`I
`ELAPSED
`J DETECTED
`
`'
`
`I MESSAGE
`
`y
`
`Exhibit 1233 Page 10 of 25
`
`
`
`U.S. Patent
`
`Sep. 12, 1995
`
`Sheet 10 of 10
`
`5,450,404
`
`TRANSMITIER RESET OR
`POWER TURNED ON
`
`fi g.11
`
`t
`
`ANY ERROR OR
`"TRANSMITIER CONFUSED"
`
`RESYNCHRONIZE-WAIT FOR:
`
`'
`
`SHORT
`JAM
`DETECTED
`
`JAM
`DETECTED
`MESSAGE OR
`DETECTED
`
`BUS JAM
`DETECTED
`
`MESSAGE
`DETECTED
`
`BUS IDLE FOR
`W SLOT TIMES +
`FRAME GAP
`W SLOT TIMES +
`FRAME GAP
`IDLE ELAPSED
`
`BUS JAM ,.--1
`DETECTED
`
`•
`I BUS IDLE I
`~TRAFFIC READY
`TO SEND
`JAM THE BUS I
`
`JAM PERIODJ
`ELAPSED
`
`I WAIT FOR ALL
`JAMMERS TO FINISH I
`JAMMING
`CEASES
`TRANSMISSION
`
`II BUS BUSY I COMPLETED J FRAME I
`I TRANSMISSION
`COMPLETED
`
`I
`
`I GAP
`FRAME GAP
`TlME ELAPSED
`
`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
`
`P SLOTS
`y WAIT FOR 1 ELAPSED
`Pth SLOT I
`I
`
`TRANSMIT
`I.D. AND
`MESSAGE
`
`JAM THE
`_I
`! BUS (GROUP)
`
`FRAME GAP
`
`t
`I SECONDARY J
`FRAME GAP J
`MESSAGE )r- TIME ELAPSED
`r i WAIT FOR I
`Zth SLOT I Zth SLOT
`ELAPSED
`ANY SIGNAL
`DETECTED
`
`y WAIT FOR I
`
`MESSAGE I
`
`READY TO
`TRANSMIT ?
`
`yN
`WAIT FOR
`REST OF
`SLOTS
`I
`
`ANOTHER
`J-Y SLOTS
`ELAPSED
`
`Exhibit 1233 Page 11 of 25
`
`
`
`1
`
`5,450,404
`
`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.
`
`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
`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
`time slots grows large because slot widths must account
`for oscillator drift. Integration of building-wide sensors
`and actuators (such as hall call buttons at each landing)
`and other building services make a capability to expand
`the number of transceivers to a large number highly
`desirable.
`B. FURTHER REVIEW OF PRIOR ART
`1. SYNCHRONOUS TDM PROTOCOLS
`In many commuuications systems there is a need to
`occasionally 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/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 points. How(cid:173)
`ever, some protocols, notably synchronous Time Divi-·
`sion Multiplexing (synchronous TDM) protocols, are
`implemented such that the transceiver finite 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-
`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 resynchroni-
`
`10
`
`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 are
`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 token message. Im(cid:173)
`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 50
`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-
`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-
`
`65
`
`Exhibit 1233 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
`TDM, 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 TDM). 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
`TDM 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 TDM 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 TDM 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 TDM 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- so
`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 ss
`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)
`miJIIications 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 has 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-
`·
`vvork.
`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 1233 Page 13 of 25
`
`
`
`5,450,404
`
`15
`
`25
`
`35
`
`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 nwnber 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(cid:173)
`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 DATAC system chip set
`from National Semiconductor uses this approach for a
`synchronous TOM 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
`
`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(cid:173)
`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 practical limi(cid:173)
`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(cid:173)
`ous protocols: (a) single point of failure and (b) need for
`collision detection.
`
`DISCLOSURE OF THE INVENTION
`A ftrst 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~g. 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 ftrst predicate that the present
`invention provides a means for synchronization of a
`
`Exhibit 1233 Page 14 of 25
`
`
`
`5,450,404
`
`30
`
`7
`plurality of transceivers on a shared communications
`medium using a "jamming" signal, thereby eliminating
`requirements to use collision detection or a centralized
`bus master. As a consequence of the second predicate,
`one way to use such a synchronization technique is to 5
`let the jam signal serve as a unique time point from
`which to start an implicit token slot progression.
`According to the present invention, a collision, multi(cid:173)
`ple signals transmitting onto an idle bus, is assumed and
`access to an idle bus begins with a jam pattern, the end 10
`of which all transceivers synchrOI\ize to.
`The invention is further explained. When the commu(cid:173)
`nications medium is busy, implicit token slots follow the
`end of each message. If a slot progression completes
`with no messages being sent, the communication me- 15
`dium is allowed to go idle.
`If a transceiver has a message to send during an idle
`medium condition, it transmits a jam pattern onto the
`medium for a predetermined time (based on maximum
`network propagation delay). If a transceiver detects a 20
`jamming pattern, it inhibits its own transmissions and
`waits for the next slot progression. If multiple transceiv(cid:173)
`ers begin jamming within a propagat