United States Patent [19]
`Koopman
`
`111111111111111111111111111111111111111111111111111111111111111111111111111
`US005436901A
`[11] Patent Number:·
`(45] Date of Patent:
`
`5,436,901
`Jul. 25, 1995
`
`[75]
`
`[54] SYNCHRONOUS TIME DIVISION
`MULTIPLEXING USING JAM-BASED
`FRAME SYNCHRONIZATION
`Inventor: Philip J. Koopman, Hebron, Conn.
`[73] Assignee: Otis Elevator Company, Farmington,
`Conn.
`[21] Appl. No.: 202,870
`[22] Filed:
`Feb. 25, 1994
`
`Related U.S. Application Data
`[63] Continuation of Ser. No. 992,879, Dec. 21, 1992, aban(cid:173)
`doned.
`
`Int. Cl.6 ••••.••••••••••••••••••••.••••••••••••.•.••••.•• H04J 3/06
`[51]
`[52] u.s. Cl .................................. 370/85.1; 370/100.1
`[58] Field of Search ............... 370/100.1, 105.4, 105.5,
`370/85.1, 85.2, 85.3, 85.5, 95.1, 95.2, 95.3, 103,
`85.9, 85.11; 375/107, 111
`References Cited
`U.S. PATENT DOCUMENTS
`4,438,520 3/1984 Saltzer .............................. 370/110.1
`4,603,418 7/1986 Townsend .......................... 370/95.3
`4,606,022 8/1986 Suzuki et al ....................... 370/85.1
`4,631,721 12/1986 Ono et al ........................... 370/85.9
`
`[56]
`
`4,646,291 2/1987 Pemtz et al ........................ 370/85.9
`4,674,084 6/1987 Suzuki et al ..................... 370/100.1
`4,901,348 2/1990 Nichols et al ...................... 370/85.2
`4,907,222 3/1990 Slavik ............................... 370/100.1
`4,987,571 1/1991 Haymond et al .................. 370/85.2
`5,189,670 2/1993 Inglis ································ 370/100.1
`Primary Examiner-Douglas W. Olms
`Assistant Examiner-Chau T. Nguyen
`
`ABSTRACT
`[57]
`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 mamnilm
`network propagation delay). If a transceiver detects a
`jamming pattern, it inhibits its own transmissions and
`waits for the end of the jamming pattern. If multiple
`transceivers begin jamming within a propagation delay
`of each other (within the network vulnerable time),
`their jamming transmissions will not destructively inter(cid:173)
`fere with each other. When jamming ceases, all trans(cid:173)
`ceivers begin a time slice progression. Thus, the end of
`the jamming period when all transceivers have finished
`jamming serves as a network-wide synchronization for
`the start of an implicit token time slice progression.
`
`2 Claims, 17 Drawing Sheets
`
`TRANSAIITTER RESET
`POwER TURNED ON
`
`ftNf ERROR
`OR
`'TRANS!.IITTER CONFUSED"
`
`RESYNCHRONIZE - WAIT FOR:
`
`BUS JAU
`om: clEO
`
`FSO FOR SYNCHRONOUS llloiE DMSJON J.IULllPLEXING PROTOCOL
`(SYNCHRONOUS TDJ.I).
`
`Exhibit 1322 Page 01 of 32
`
`

`
`U.S. Patent
`
`July 25, 1995
`
`Sheet 1 of 17
`
`5,436,901
`
`COMMUNICATIONS MEDIUM
`"
`"'
`1
`I
`TRANSMITTER
`TRANSMITTER
`&
`&
`RECEIVER
`RECENER
`
`I
`l
`
`A
`
`I
`TRANSMITTER
`&
`RECEIVER
`
`A PLURALilY OF ·TRANSMITTERS AND RECEIVERS COUPLED
`TO A COMMAN COMMUNICATIONS MEDIUM.
`FIG.1
`
`OPERATION
`BEFORE
`SYNCHRONIZATION
`
`D u~ ETECTED
`
`8
`
`
`TRANS MITIER
`GENERATE
`NEEDS TO
`NIZATION
`SYNCHRO
`EVENT
`
`JAM
`THE BUS
`JAM PER IOD
`
`ED ELAPS
`
`WArT FOR
`ALL JAMMERS
`TO FINISH
`
`JAMMING
`CEASES
`
`SYNCHRONIZATION
`ACHIEVED
`
`OPERATION
`AFTER
`SYNCHRONIZATION
`
`FSD FOR SYNCHRONIZATION OF MULTIPLE TRANSMITTERS.
`FIG.2
`
`Exhibit 1322 Page 02 of 32
`
`

`
`U.S. Patent
`
`July 25, 1995
`
`Sheet 2 of 17
`
`5,436,901
`
`ANY ERROR
`OR
`TRANSMITIER RESEr
`"TRANSMITIER CONFUSED•
`POWER TURNED ON
`t
`•
`RESYNCHRONIZE - WAIT FOR:
`
`JAM
`DETECTED
`
`•
`
`BUS IDLE FOR
`OR N SUCE TIMES
`+
`FRAME GAP
`N SLICE TIMES
`+
`FRAME GAP
`IDLE ELAPSED
`JAM
`THE BUS
`
`BUS JAM
`DffiCTED
`
`JAM PERIOD
`ELAPSED
`
`WAIT FOR
`Ali JAMMERS
`TO FINISH
`JAMMING
`CEASES
`,---1....---.
`FRAME
`GAP
`
`FRAME GAP
`TIME ELAPSED
`,--.--1....---,
`WAIT FOR
`Mth SLICE
`
`M TIME
`SLICES ELAPSED
`r--__._-_,
`TRANSMIT
`MESSAGE
`
`BUS JAM
`DETECTED
`
`TRANSMISSION
`TIME SLICE
`ELAPSED
`
`WAIT FOR
`REST OF
`ANOTHER
`SUCES
`N-M-1 SLICES
`I
`ELAPSED
`FSD FOR SYNCHRONOUS TIME DMSION MULTIPLEXING PROTOCOL
`(SYNCHRONOUS IDM).
`F1G.3
`
`Exhibit 1322 Page 03 of 32
`
`

`
`U.S. Patent
`
`July 25, 1995
`
`Sheet 3 of 17
`
`5,436,901
`
`TRANSMITTER RESET OR
`POWER TURNED ON
`
`ANY ERROR
`OR
`"TRANSMITIER CONFUSED•
`
`RESYNCHRONIZE - WAIT FOR:
`
`JAM
`DETECTED
`
`OR
`
`BUS IDLE FOR
`MAXIMUM
`IDLE
`PERIOD
`
`BUS IDLE FOR MAXIMUM
`IDLE PERIOD
`
`BUS JAM
`DEfECl'ED
`
`JAM PERIOD
`EIPPSED
`
`WNT FOR
`ALL JAMMERS
`TO FINISH
`JAMMING
`CEASES
`
`FRAME
`GAP
`
`~........1--._,
`
`FRAME GAP
`TIME ELAPSED
`WAIT FOR
`Uth SLOT
`M SLOTS
`ELAPSED
`TRANSMIT BUS
`OWNERSHIP
`M
`
`TRANSMITIER
`IS BUS
`MAS R
`
`BUS
`OWNERSHIP
`MESSAGE
`DEfECTED
`
`NOT THE
`BUS
`M R
`
`FSD FOR BUS MASTER ARBITRATION.
`FIG.4
`
`Exhibit 1322 Page 04 of 32
`
`

`
`U.S. Patent
`
`July 25, 1995
`
`Sheet 4 of 17
`
`5,436,901
`
`TRANSMITTER RESET OR
`POWER TURNED ON
`
`ANY ERROR
`OR
`"TRANSMITTER CONFUSED"
`
`RESYNCHRONIZE - WAJT FOR:
`
`NODE
`ADMISSION OR
`PERM !TIED
`
`BUS JAM
`DETECTED
`
`BUS IDLE FOR
`MAXIMUM
`IDLE
`PERIOD
`NODE ADMISSION PERIOD
`OR
`BUS IDLE FOR MAXIMUM
`...-__,_-__,IDLE PERIOD
`JAM
`THE BUS
`
`JAM PERIOD
`ELAPSED
`
`WAIT FOR
`ALL JAMMERS
`TO FINISH
`JAMMING
`CEASES
`....-----'------.
`FRAME
`GAP
`
`FRAME GAP
`TIME ELAPSED
`r - - - ' - - - ,
`WAJT FOR
`Mth SLOT
`M SLOTS
`ELAPSED
`TRANSMIT BUS
`OWNERSHIP
`M
`
`BUS
`OWNERSHIP
`MESSAGE
`DffiCTED
`
`FSD FOR EXPUCIT TOKEN BUS PROTOCOL.
`· AG.5
`
`Exhibit 1322 Page 05 of 32
`
`

`
`U.S. Patent
`
`July 25, 1995
`
`Sheet 5 of 17
`
`5,436,901
`
`TRANSMITTER RESET
`POWER TURNED ON
`
`ANY ERROR
`OR
`"TRANSMITIER CONFUSED.
`
`RESYNCHRONIZE - WAIT FOR:
`
`JAM
`DffiCTED
`
`BUS IDLE FOR
`OR N SLOT TIMES
`+
`FRAME GAP
`N SLOT TIMES
`+
`FRAME GAP
`IDLE ELAPSED
`
`BUS JAM
`DETECltD
`
`BUS JAM
`DETECTED
`WAIT FOR
`ALL JAMMERS
`TO FINISH
`JAMMING
`CEASES
`
`FRAME
`GAP
`
`FRAME GAP
`TIME ELAPSED
`,----..1----.
`WAIT FOR
`t.fth SLOT
`
`FRAME
`GAP
`
`JAM PERIOD
`ELAPSED
`
`TRANSMISSION
`COMPLETED
`
`>YE_S_~ TRANSMIT
`MESSAGE
`
`BUS BUSY ~~-=-~
`
`TRANSMISSION .____ _______________ ___.
`COMPLETED
`FSD FOR RESERVATION CSMA PROTOCOL WITH PER-MESSAGE RESTART.
`AG.6
`
`Exhibit 1322 Page 06 of 32
`
`

`
`U.S. Patent
`
`July 25, 1995
`
`Sheet 6 of 17
`
`5,436,901
`
`TRANS~ITIER RESET OR
`POWER TURNED ON
`
`ANY ERROR
`OR
`"TRANSMfiTER CONFUSED"
`
`RESYNCHRONIZE - WAIT FOR:
`
`JAM
`DETECTED
`
`OR
`
`BUS IDLE FOR
`MAXIMUM
`IDLE
`PERIOD
`BUS IDLE FOR
`MAXIMUM
`IDLE PERIOD
`
`JAM
`THE BUS
`
`BUS JAM
`DITECTED
`
`JAM PERIOD
`ELAPSED
`
`WAIT FOR
`ALL JAM~ERS
`TO FINISH
`JA~MING
`CEASES
`
`FRAME
`GAP
`
`FRAME GAP
`TIME ELAPSED
`
`FIG.7A
`
`SHORT
`BUS JAM
`DETECTED
`
`Exhibit 1322 Page 07 of 32
`
`

`
`u~s. Patent
`
`July 25, 1995
`
`Sheet 7 of 17
`
`5,436,901
`
`SHORT
`JAM
`.----WA-IT..~....F_O_R--, DETECTED
`Gth SLOT
`
`NOT THE
`BUS
`MASTER
`
`BUS
`OWNERSHIP
`MESSAGE
`DETECTED
`
`G SLOTS
`ELAPSED
`JAM
`THE BUS
`(GROUP)
`JAM PERIOD
`ELAPSED
`SECONDARY
`FRAME
`GAP
`
`~-.I..--,
`
`FRAME GAP
`TIME ELAPSED
`..--------,
`WAIT FOR
`Hth SLOT
`
`H SLOTS
`ELAPSED
`TRANSMIT BUS
`OWNERSHIP
`MESSAGE
`TRANSMISSION
`COMPLETED
`r------L--,
`TRANSMITTER
`IS BUS
`MASTER
`
`FSD FOR MULTI-LEVEL BUS MASTER ARBITRATION.
`FIG.78
`
`FIG.
`7A
`
`FIG.
`78
`FIG.Z
`
`Exhibit 1322 Page 08 of 32
`
`

`
`FIG.BA
`
`CEASES
`JAMMING
`
`ALL JAMMERS
`
`TO FINISH
`
`WAIT FOR
`
`JAM PERIOD
`
`ELAPSED
`
`GAP
`FRAME
`
`TO SEND
`READY
`TRAFFIC
`
`BUS IDLE
`
`DETECTED
`SHORT JAM
`
`COMPLETED ~--~
`TRANSMISSION
`
`,--_....L-~
`
`IDLE ELAPSED
`FRAME GAP
`
`L SLOT TIMES
`
`+
`
`L SLOT TIMES
`BUS IDLE FOR
`
`FRAME GAP
`
`+
`
`OR
`
`DETECTED
`
`JAM
`
`RESYNCHRONIZE -WAIT FOR:
`
`"TRANSMITIER CONFUSEDN
`
`ANY ERROR
`
`OR
`
`TRANSMITIER RESET OR
`
`POWER TURNED ON
`
`Exhibit 1322 Page 09 of 32
`
`

`
`FSD FOR RCSMA PROTOCOL WITH MULTI-LEVEL ARBITRATION & PER-MESSAGE RESTART.
`
`AG.8B
`
`MESSAGE
`1-------..t TRANSMIT
`
`ElAPSED
`H SLOTS
`
`Hth SLOT
`WAIT FOR
`
`COMPLETED
`TRANSMISSION
`
`,------1---1
`
`TIME ElAPSED
`FRAME GAP
`
`SECONDARY
`
`GAP
`FRAME
`
`SLOTS
`REST OF
`WAIT FOR
`
`FIG.8
`
`88
`FIG.
`BA
`FIG.
`
`e •
`
`•
`00
`
`OTHERS
`
`FOR
`WAIT
`
`DEfECTED
`MESSAGE
`
`TIME ELAPSED
`FRAME GAP
`
`GAP
`FRAME
`
`Exhibit 1322 Page 10 of 32
`
`

`
`F!G.9A
`
`CEASES
`JAMMING
`
`ALL JAMMERS
`
`TO FINISH
`
`WAIT FOR
`
`JAM PERIOD
`
`ELAPSED
`
`THE BUS
`
`JAM
`
`TO SEND
`READY
`TRAFFIC
`
`BUS IDLE
`
`..---L----11....-,
`
`IDLE ELAPSED
`FRAME GAP
`
`N SLOT TIMES
`
`+
`
`OR N SLOT TIMES
`BUS IDLE FOR
`
`FRAME GAP
`
`+
`
`DETECTED
`
`JAM
`
`RESYNCHRONIZE -WAIT FOR:
`
`"TRANSMITTER CONFUSED•
`
`ANY ERROR
`
`OR
`
`POWER TURNED ON
`TRANSMITTER RESET
`
`Exhibit 1322 Page 11 of 32
`
`

`
`FSD FOR RCSMA PROTOCOL THAT AVOIDS PROTOCOL RESTARTS DURING HEAVY LOADS.
`
`FIG.98
`
`N...:.M SLOTS
`ANOTHER
`
`ELAPSED
`
`SLOTS
`REST OF
`WAIT FOR
`
`DETECTED
`MESSAGE
`
`FIG.9
`98
`FIG.
`9A
`FIG.
`
`~;..::.._--~ MESSAGE
`TRANSMIT
`
`YES
`
`COMPLETED
`TRANSMISSION
`
`ELAPSED
`M SLOTS
`
`Mth SLOT
`WAIT FOR
`
`.--F-RAM~E--.
`
`GAP
`
`BUS BUSY t--------+i
`
`COMPLETED
`TRANSMISSION
`
`Exhibit 1322 Page 12 of 32
`
`

`
`fiG. lOA
`
`JAM PERIOD
`
`ELAPSED
`
`THE BUS
`
`JAM
`
`TO SEND
`READY
`TRAFFIC
`
`CEASES
`JAMMING
`
`ALL JAMMERS
`
`TO FINISH
`
`WAIT FOR
`
`N+Q SLOT TIMES
`
`IDLE ElAPSED
`FRAME GAP
`
`+
`
`N+Q SLOT TIMES
`BUS IDLE FOR
`
`FRAME GAP
`
`+
`
`DETECTED
`MESSAGE OR
`DETECTED
`
`JAM
`
`•
`rJl
`0 •
`
`RESYNCHRONIZE -WAIT FOR:
`
`"TRANSMITTER CONFUSED"
`
`ANY ERROR
`
`OR
`
`POWER TURNED ON
`TRANSMITTER RESET
`
`Exhibit 1322 Page 13 of 32
`
`

`
`FIG.lOB·
`
`MESSAGE
`I.D. &
`TRANSMIT
`
`"'1----..L...---. P SLOTS .----~---.
`
`ElAPSED
`
`Pth SLOT
`WAIT FOR
`
`EIJ\PSED
`Q SLOTS
`
`ALL FIXED
`WAIT FOR
`
`SLOTS
`
`DETECTED
`MESSAGE
`
`COMPLETED
`TRANSMISSION
`
`TIME ELAPSED
`FRAME GAP
`
`GAP
`
`--'
`
`-
`
`-
`
`BUS BUSY 1----
`
`.----F-RA...._M_E--.
`
`COMPLETED
`TRANSMISSION
`
`Exhibit 1322 Page 14 of 32
`
`

`
`"""' -l
`0 .....
`"""' ~
`""
`til =- ('!)
`
`(I)
`
`•
`00
`~ •
`
`FSD FOR RCSMA PROTOCOL WITH BOTH FIXED PRIORilY AND ROTATING SLOTS.
`
`FIG.lOC
`
`SLOTS
`REST OF
`WAIT FOR
`
`NO
`
`N-R SLOTS
`ANOTHER
`
`ELAPSED
`
`DETECTED
`MESSAGE
`
`Rth SLOT
`DETECTED WAIT FOR
`MESSAGE
`
`FIG.lO
`
`lOG
`FIG.
`108
`FIG.
`lOA
`FIG.
`
`Exhibit 1322 Page 15 of 32
`
`

`
`fiG.JlA
`
`FIG.ll
`11 c
`FIG.
`11B
`FIG.
`11A
`FIG.
`
`CEASES
`JAMMING
`
`All JAMMERS
`
`TO FINISH
`
`WAIT FOR
`
`JAM PERIOD
`
`ELAPSED
`
`THE BUS
`
`JAM
`
`TO SEND
`READY
`TRAFFIC
`
`W SLOT TIMES
`
`IDLE ELAPSED
`FRAME GAP
`
`+
`
`OR W SLOT TIMES
`BUS IDLE FOR
`
`FIV\ME GAP
`
`+
`
`DETECTED
`MESSAGE
`
`DETECTED
`
`JAM
`
`RESYNCHRONIZE -WAIT FOR:
`
`"TRANSMITIER CONFUSED"
`
`ANY ERROR
`
`OR
`
`TRANSMITIER RESET OR
`
`POWER TURNED ON
`
`Exhibit 1322 Page 16 of 32
`
`

`
`ELAPSED
`p SLOTS
`
`DETACHED
`ANY SIGNAL
`
`ELAPSED
`Q SLOTS
`
`ALL FIXED
`WAIT FOR
`
`SLOTS
`
`DETACHED
`ANY SIGNAL
`
`DETECTED
`MESSAGE
`
`YES
`
`TIME ElAPSED
`FRAME GAP
`
`COMPLETED
`TRANSMISSION ---L..--,
`
`GAP
`FRAME
`
`e •
`
`•
`rLl
`
`Exhibit 1322 Page 17 of 32
`
`

`
`FSD FOR RCSMA PROTOCOL WITH fiXED PRIORITY AND MULTI-LEVEL, ROTATING SLOTS.
`
`FIG.llC
`
`TRANSMIT
`
`MESSAGE
`I.D. &
`
`COMPLETED
`TRANSMISSION
`
`ELAPSED
`L-----------t---A-N-Y -S-IG-NA-L~_Zth_SL_o_T _. Z SLOTS
`
`DETECTED
`
`WAIT FOR
`
`TIME ELAPSED
`FRAME GAP
`
`SECONDARY
`
`GAP
`FRAME
`
`ELAPSED
`J-Y SLOTS
`ANOTHER
`
`DETECTED ~-~--...... ......
`ANY SIGNAL
`
`SLOTS
`REST Of
`WAIT FOR
`
`NO
`
`YES
`
`ELAPSED
`Y SLOTS
`
`Yth SLOT
`WAIT FOR
`
`Exhibit 1322 Page 18 of 32
`
`

`
`SYNCHRONOUS TIME DMSION
`MULTIPLEXING USING JAM-BASED FRAME
`SYNCHRONIZATION
`
`This is a File Wrapper Continuation of application
`Ser. No. 7/992,879, filed Dec. 21, 1992, abandoned.
`
`30
`
`1
`
`5,436,901
`
`TECHNICAL FIELD
`This invention relates to computer communication 10
`protocols, and in particular, to a synchronous time divi(cid:173)
`sion multiplexing media access sclieme.
`
`2
`Fourth, some protocols (e.g., CSMA/CD) make inef(cid:173)
`ficient use of network bandwidth under heavy loading
`cnnditions. Existing elevator systems often have slow(cid:173)
`speed low-grade wire that must be efficiently used to
`5 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
`BACKGROUND OF THE INVENTION
`in such a way as to eliminate the need for acknowledg(cid:173)
`ments because multiple acknowledgment messages take
`If multiple transceivers attempt to use a medium si- 15
`up bandwidth. Therefore, lack of acknowledgment is
`multaneously, the transmissions collide, resulting in
`not available as an indirect means for detecting colli(cid:173)
`garbled messages and potentially lost data. Media Ac(cid:173)
`sions.
`cess Control (MAC) protocols are used to arbitrate
`Seventh, elevators must be able to function in the face
`which transceiver has possession of a medium at any
`of failures, and so must not have the single-point failure
`given time. Arbitration is the process by which one of 20
`vulnerability inherent in a central communications me(cid:173)
`multiple peer transceivers desiring access to the bus
`dium master.
`obtains it. The subset of MAC protocols of interest is
`Eighth, some protocols support only a limited num(cid:173)
`those protocols used to implement Local Area Net(cid:173)
`ber of transceivers. For example, implicit token proto(cid:173)
`works (LANs) using a shared transmission medium.
`cols become inefficient as the number of implicit token
`The terms "explicit token" and "implicit token" are 25
`time slots grows large because slot widths must account
`used herein. Explicit tokens are actual messages that are
`for oscillator drift. Integration of building-wide sensors
`passed from transceiver to transceiver as control of the
`and actuators (such as hall call buttons at each landing)
`medium is passed. Ownership of the token grants sole
`and other building services make a capability to expand
`right to transmit. Token ownership is relinquished to
`the number of transceivers to a large number highly
`another transceiver by sending a token message. Im(cid:173)
`desirable.
`plicit tokens are time slots which, if used, grant exclu(cid:173)
`B. FURTHER REVIEW OF PRIOR ART
`sive access to the medium. They are implicit because no
`1. SYNCHRONOUS IDM PROTOCOLS
`real token message exists. Rather, each time slot period
`In many communications systems there is a need to
`of time on the communications medium carries with it 35
`occasionally resynchronize all transceivers to a com(cid:173)
`the meaning of a token-to-transceiver assignment.
`mon point in time. One reason synchronization is
`A. MEDIA ACCESS CONTROL PROTOCOL SE(cid:173)
`needed is that the local clock for each transceiver (usu(cid:173)
`LECTION
`ally based on a crystal oscillater or resistor/ capacitor
`1. EXEMPLARY ELEVATOR SYSTEM
`oscillator circuit) runs at a slightly dilferent speed from
`In the communication protocol selection process, a 40 local clocks at other transceivers. Factors contributing
`to. this clock drift include component manufacturing
`number of factors should be considered. An exemplary
`application to illustrate some of these factors is an eleva-
`variations, aging effects, and temperature variations.
`Another reason for resynchronization is so that a
`tor system which uses twisted-pair wires as a shared
`communications medium.
`newly activated transceiver (or one recovering from an
`Of further interest are LANs that apply to embedded 45 error state) can join into a communication protocol
`and real time control applications that require predict-
`currently active among other transceivers using the
`able and/or deterministic system response.
`co=unication medium even in the absence of message
`2. FACTORS TO BE CONSIDERED IN MEDIA
`transmissions.
`ACCESS PROTOCOL SELECTION IN LIGHT OF
`Communication protocols in which the absence of
`PRIOR ART
`so continual messages implies a bus idle state can use the
`First, collision detection circuits are impracticable in
`messages themselves as resynchronization points. How-
`some elevator communications systems. Analog colli-
`ever, some protocols, notably synchronous Time Divi-
`sion detection techniques rely on approximately equal
`sion Multiplexing (synchronous TDM) protocols, are
`implemented such that the transceiver finite state rna-
`signal strengths from colliding transmitted signals.
`However, in a large building, signals over twisted pair 55 chine is in a state other than BUS IDLE for long peri-
`ods of time, even though no messages are being sent.
`wires are severely attenuated over 2000 feet, so signal
`strengths from some transceiver pairs are very unequal.
`These protocols, including synchronous TDM, usually
`Second, real time response requirements of elevator
`use explicit resynchronization signals to limit the accu-
`systems, for purposes of safety and control loop stabil-
`mulated clock drift over time between different trans-
`ity, require both predictable and bounded message 60 ceivers.
`There is a maximum clock drift that can be tolerated
`transmission delays.
`In some protocols, such as
`CSMA/CD, there is no guacailtee that any particular
`while still maintaining synchronized transmission and
`reception within a protocol. For example, if two trans-
`message will be delivered within a bounded time inter-
`val.
`ceivers are to take turns transmitting based on time
`Third, many protocols do not allow for deterministic 65 alone (as opposed to detection of other transmissions), a
`pad time must be allowed between consecutive trans-
`prioritization of network access as required by elevator
`control loops and safety schemes. CSMA/CD, for ex-
`missions to allow for clock drift. Accumulated clock
`ample, provides no guarantees for priority service.
`drift must be kept smaller than this pad time for collision
`
`Exhibit 1322 Page 19 of 32
`
`

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

`
`5
`data immediately as in CSMA/CD. Implicit token slots
`begin after each message. If there is a collision, the
`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(cid:173)
`ply letting the medium go idle and providing for a quick
`restarting capability.
`Collision detection is required for implementation, 10
`and this method does not overcome the practical limita(cid:173)
`tion on the number of slots and therefore the number of
`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 15
`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 20
`master to emit frame synchronization signals that start a
`progression of implicit token slots. If all slots have
`elapsed without a transmission on the communications
`medium, the master generates a new frame synchroniza(cid:173)
`tion sigDa! to start a new slot progression. By relying on 25
`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- 30
`ure vulnerability within the system,
`(b) the master is an extra component separate from
`the other nodes that must be separately designed and
`fabricated, and
`(c) this method does not overcome the practicallimi- 35
`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 40
`Local Area Network", IEEE Transactions on Comput(cid:173)
`ers, Volume C33, No. 12, December 1984, Pages
`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(cid:173)
`emplary elevator application, including the following:
`(a) the rotating master still represents a subtle, single
`point of failure vulnerability. If the current master 50
`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
`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 60
`from National Semiconductor uses this approach for a
`synchronous TDM implementation. In this scheme,
`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 DA T AC 65
`chip set by having two cross-checked oscillators instead
`of only one). After each message, a slot progression is
`initiated. Whenever the slot progression is completed
`
`45
`
`55
`
`5,436,901
`
`6
`with no network activity, a new slot progression is
`automatically initiated. In other words, slot progres(cid:173)
`sions repeat indefinitely without frame synchronization
`while the network remains idle.
`The mastership is "distributed" among all transceiv·
`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 DAT AC applica(cid:173)
`tion this problem is controlled by using expensive re(cid:173)
`dundant oscillators;
`(b) a transceiver that has lost track of the protocol
`state through some transient error or reset cannot im(cid:173)
`mediately access the network while the network is idle,
`because there are no transmissions on the network to
`indicate where, in the time slot progression, other trans(cid:173)
`ceivers are located;
`(c) system power-<>n and reset problems remain be(cid:173)
`cause the initial active transceiver must be chosen.
`DATAC uses an unspecified method of collision detec(cid:173)
`tion 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 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
`interfering, 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.
`
`Exhibit 1322 Page 21 of 32
`
`

`
`5,436,901
`
`8
`(e) larger numbers of transceivers allowed than with
`other implicit token systems without long slot progres(cid:173)
`sions by using multi-level slot progressions.
`
`7
`It follows from the first predicate that the present
`invention provides a means for synchronization of a
`plw:ality of transceivers on a shnred communications
`medium using a "jamming'' signal, thereby eliminating
`BRIEF DESCRIPTION OF TilE DRAWINGS
`requirements to use collision detection or a centralized 5
`FIG. 1 is a block diagram of a plurality of tran-
`bus master. As a consequence of the second predicate,
`one way to use such a synchronization technique is to
`sceiver/receiver nodes coupled to a shared communica-
`let the jam signal serve as a unique time point from
`tion medium;
`FIG. 2 is a finite state diagram for synchronizing a
`which to start an implicit token slot progression.
`According to the present invention, a collision, multi- 10 plurality of transceivers;
`pie signals transmitting onto an idle bus, is assumed and
`FIG. 3 is a finite state diagram for implementing