United States Patent [19]
`Koopman
`
`11111111111111 1111111111111111111111111111111111111111111111111111111111111
`US005436901A
`[11] Patent Number:
`[45] Date of Patent:
`
`5,436,901
`Jul. 25, 1995
`
`[54] SYNCHRONOUS TIME DMSION
`MULTIPLEXING USING JAM-BASED
`FRAME SYNCHRONIZATION
`Inventor: Philip J. Koopman, Hebron, Conn.
`
`[75]
`
`[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. Q,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
`
`[56]
`
`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
`
`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
`
`ABSTRACf
`[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 maximum
`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
`
`TRANSI.IrrTER RESET
`POWER TURNED ON
`
`Nff ERROR
`OR
`"1RAN$MI1TER CONFUSED"
`
`RESYNCHRONIZE - WMT FOR:
`BUS IDLE FOR
`OR N SUCE 11MES
`+
`FRAI.IE GAP
`
`JN.j
`Drn:C!El
`
`BUS JAM
`DffiClED
`
`FSD FOR SYNCHRONOUS 11t.IE DMSION t.IUL11PLEXING PROTOCOL
`(SYNCHRONOUS TOM).
`
`Exhibit 1224 Page 01 of 32
`
`

`

`U.S. Patent
`
`July 25, 1995
`
`Sheet 1 of 17
`
`5,436,901
`
`COMMUNICATIONS MEDIUM
`,
`,
`I
`r
`TRANSMITTER
`TRANSMITTER
`&
`&
`RECENER
`RECENER
`
`J_
`I
`
`"
`
`r
`TRANSMITTER
`&
`RECEIVER
`
`A PLURALITY OF TRANSMITTERS AND RECEIVERS COUPLED
`TO A COMMAN COMMUNICATIONS MEDIUM.
`FIG.1
`
`OPERATION
`BEFORE
`SYNCHRONIZATION
`
`TRANSMITTER
`NEEDS TO GENERATE
`SYNCHRONIZATION
`EVENT
`
`JAM
`THE BUS
`JAM PERIOD
`ELAPSED
`
`WAIT FOR
`ALL JAMMERS
`TO FINISH
`
`JAMMING
`CEASES
`
`SYNCHRONIZATION
`ACHIEVED
`
`OPERATION
`AFTER
`SYNCHRONIZATION
`
`FSD FOR SYNCHRONIZATION OF MULTIPLE TRANSMITTERS.
`FIG.2
`
`Exhibit 1224 Page 02 of 32
`
`

`

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

`

`U.S. Patent
`
`July 25, 1995
`
`Sheet 3 of 17
`
`5,436,901
`
`TRANSMITTER RESET OR
`POWER TURNED ON
`t
`RESYNCHRONIZE - WAIT FOR:
`
`-.
`
`ANY ERROR
`OR
`"TRANSMITIER CONFUSED•
`
`JAM
`DITECTED
`
`OR
`
`IDLE FOR
`BUS
`MAXIMUM
`IDLE
`PERIOD
`
`BUS IDLE FOR MAXIMUM
`IDLE PERIOD
`
`BUS JAM
`omcTED
`
`JAM
`THE BUS
`
`JAM PERIOD
`ELAPSED
`
`WAIT FOR
`All JAMMERS
`TO FINISH
`JAMMING
`CEASES r -............. ____
`FRAME
`GAP
`
`FRAME GAP
`TIME ELAPSED
`.----L---..
`WAIT FOR
`Mth SLOT
`M SLOTS
`ELAPSED
`TRANSMIT BUS
`OWNERSHIP
`MESSAGE
`
`TRANSMilTER
`IS BUS
`MASTER
`
`BUS
`OWNERSHIP
`MESSAGE
`DITECTED
`
`NOT THE
`BUS
`MASTER
`
`FSD FOR BUS MASTER ARBITRATION.
`FIG.4
`
`Exhibit 1224 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
`"TRANSMITIER CONFUSED•
`
`RESYNCHRONIZE - WAlT FOR:
`
`NODE
`ADMISSION OR
`PERMITIED
`
`BUS IDLE FOR
`MAXIMUM
`IDLE
`PERIOD
`NODE ADMISSION PERIOD
`OR
`BUS IDLE FOR MAXIMUM
`~~-__,IDLE PERIOD
`JAM
`THE BUS
`
`BUS JAM
`DETECTED
`
`JAM PERIOD
`ELAPSED
`
`WAIT FOR
`ALL JAMMERS
`TO FINISH
`JAMMING
`CEASES
`
`,..........-~---.
`
`FRAME
`GAP
`
`FRAME GAP
`TIME ELAPSED
`, - - - -1 - - - ,
`WAIT FOR
`Mth SLOT
`M SLOTS
`ELAPSED
`TRANSMIT BUS
`OWNERSHIP
`u
`
`BUS
`OWNERSHIP
`MESSAGE
`DffiCTED
`
`DONE
`TRANSMITTING
`
`FSD FOR EXPUCIT TOKEN BUS PROTOCOL.
`FIG.5
`
`Exhibit 1224 Page 05 of 32
`
`

`

`U.S. Patent
`
`July 25, 1995
`
`Sheet 5 of 17
`
`5,436,901
`
`TRANSMmER RESET
`POWER TURNED ON
`
`ANY ERROR
`OR
`"TRANSMITTER CONFUSED•
`
`RESYNCHRONIZE - WAIT FOR:
`
`JAM
`DffiCTED
`
`BUS IDLE FOR
`OR N SLOT TIMES
`+
`FRAME GAP
`N SLOT TIMES
`+
`FRAME GAP
`IDLE ELAPSED
`
`BUS JAM
`DITECTED
`
`BUS JAM
`DffiCTED
`WAlT FOR
`ALL JAMMERS
`TO FINISH
`JAMMING
`CEASES
`
`FRAME
`GAP
`
`FRAME GAP
`TIME ELAPSED
`..-----1...--
`WAIT FOR
`Mth SLOT
`
`FRAME
`GAP
`
`JAM PERIOD
`ELAPSED
`
`TRANSMISSION
`COMPLETED
`
`~YE:..::.S-~ TRANSMIT
`MESSAGE
`
`..-----1 MESSAGE.--__._ __
`BUS BUSY
`DETECTED
`
`TRANSMISSION L...----------------__.j
`COMPLETED
`FSD FOR RESERVATION CSMA PROTOCOL WITH PER-MESSAGE RESTART.
`AG.6
`
`Exhibit 1224 Page 06 of 32
`
`

`

`U.S. Patent
`
`July 25, 1995
`
`Sheet 6 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
`
`JAM
`THE BUS
`
`BUS JAM
`DffiCTED
`
`JAM PERIOD
`ELAPSED
`
`WAIT FOR
`ALL JAMMERS
`TO FINISH
`JAMMING
`CEASES
`
`FRAME
`GAP
`
`FRAME GAP
`TJME ElAPSED
`
`F1G.7A
`
`SHORT
`BUS JAM
`DETECTED
`
`Exhibit 1224 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
`
`FRAME GAP
`TIME ELAPSED
`
`WAIT FOR
`Hth SLOT
`
`H SLOTS
`ELAPSED
`TRANSMIT BUS
`OWNERSHIP
`MESSAGE
`TRANSMISSION
`COMPLETED
`TRANSMilTER
`IS BUS
`MASTER
`
`FSD FOR MULTI-LEVEL BUS MASTER ARBITRATION.
`FIG.78
`
`FIG.
`7A
`
`FIG.
`78
`FJG.Z
`
`Exhibit 1224 Page 08 of 32
`
`

`

`FIG.BA
`
`tt> -00
`
`til =- tt>
`
`'"""
`-...l
`0 ...,
`
`'""" ~ (II
`
`~(II
`~
`
`~
`
`~
`
`e •
`
`•
`00
`
`CEASES
`JAMMING
`
`ALL JAMMERS
`
`TO FINISH
`
`WAIT FOR
`
`JAM PERIOD
`
`ELAPSED
`
`GAP
`FRAME
`
`DETECTED
`SHORT JAM
`
`BUS BUSY
`
`TO SEND
`READY
`TRAFFIC
`
`BUS IDLE
`
`COMPLETED
`TRANSMISSION
`
`...-----L---1
`
`IDLE ELAPSED
`FRAME GAP
`
`L SLOT TIMES
`
`+
`
`L SLOT TIMES
`BUS IDLE FOR
`
`FRAME GAP
`
`+
`
`OR
`
`DETECTED
`
`JAM
`
`RESYNCHRONIZE -WAIT FOR:
`
`,.TRANSMITTER CONFUSED ..
`
`ANY ERROR
`
`OR
`
`TRANSMITTER RESET OR
`
`POWER TURNED ON
`
`Exhibit 1224 Page 09 of 32
`
`

`

`FSD FOR RCSMA PROTOCOL WITH MULTI-LEVEL ARBITRATION & PER-MESSAGE RESTART.
`
`BG.BB
`
`MESSAGE
`1-------+4 TRANSMIT
`
`ELAPSED
`H SLOTS
`
`Hth SLOT
`WAIT FOR
`
`COMPLETED
`TRANSMISSION
`
`.-----L---1
`
`TIME ELAPSED
`FRAME GAP
`
`SECONDARY
`
`GAP
`FRAME
`
`SLOTS
`REST OF
`WAIT FOR
`
`FIG.B
`
`88
`FIG.
`8A
`FIG.
`
`~ e.
`
`OJ
`~
`......
`~OJ
`N
`""d
`
`~ a n> = ~
`
`•
`00
`~ •
`
`OTHERS
`
`FOR
`WAIT
`
`DETECTED
`MESSAGE
`
`Gth SLOT
`WAIT FOR
`
`TIME ELAPSED
`FRAME GAP
`
`GAP
`FRAME
`
`Exhibit 1224 Page 10 of 32
`
`

`

`EfG.9A
`
`JAM PERIOD
`
`ElAPSED
`
`THE BUS
`
`JAM
`
`TO SEND
`READY
`TRAFFIC
`
`CEASES
`JAMMING
`
`ALL JAMMERS
`
`TO FINISH
`
`WAIT FOR
`
`DETECTED
`BUS JAM
`
`...---~---.......
`
`BUS IDLE
`
`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 1224 Page 11 of 32
`
`

`

`c:: .
`
`•
`00.
`
`FSD FOR RCSMA PROTOCOL THAT AVOIDS PROTOCOL RESTARTS DURING HEAVY LOADS.
`
`EIG.98
`
`N-M SLOTS
`ANOTHER
`
`ELAPSED
`
`SLOTS
`REST OF
`WAIT FOR
`
`DETECTED
`MESSAGE
`
`FIG.9
`9B
`FIG.
`9A
`FIG.
`
`~=--~~ MESSAGE
`TRANSMIT
`
`YES
`
`COMPLETED
`TRANSMISSION
`
`ELAPSED
`M SLOTS
`
`Mth SLOT
`WAIT FOR
`
`TIME ELAPSED
`FRAME GAP
`
`r---F-RA...._M_E_
`
`GAP
`
`BUS BUSY ._ ___ __..,.
`
`COMPLETED
`TRANSMISSION
`
`Exhibit 1224 Page 12 of 32
`
`

`

`FIG. lOA
`
`rJ.J. •
`e •
`
`CEASES
`JAMMING
`
`ALL JAMMERS
`
`TO FINISH
`
`WAIT FOR
`
`JAM PERIOD
`
`ELAPSED
`
`THE BUS
`
`JAM
`
`TO SEND
`READY
`TRAFFIC
`
`BUS IDLE
`
`..--------L----1~
`
`N+O SLOT TIMES
`
`IDLE ELAPSED
`FRAME GAP
`
`+
`
`FRAME GAP
`
`NtQ SLOT TIMES
`BUS IDLE FOR
`
`t
`
`DETECTED
`MESSAGE OR
`DETECTED
`
`JAM
`
`RESYNCHRONIZE -WAIT FOR:
`
`"TRANSMITTER CONFUSED"
`
`ANY ERROR
`
`OR
`
`POWER TURNED ON
`TRANSMITTER RESET
`
`Exhibit 1224 Page 13 of 32
`
`

`

`FIG. lOB·
`
`e • rJ1
`
`•
`
`'r---L.----.. P SLOTS ,.-~-__,
`
`MESSAGE
`1.0. &
`TRANSMIT
`
`ELAPSED
`
`Pth SLOT
`WAIT FOR
`
`COMPLETED
`TRANSMISSION
`
`ELAPSED
`Q SLOTS
`
`ALL FIXED
`WAIT FOR
`
`SLOTS
`
`DETECTED
`MESSAGE
`
`TIME ELAPSED
`FRAME GAP
`
`.---F-RA~M-E----,
`
`COMPLETED
`TRANSMISSION
`
`BUS BUSY t-------~ GAP
`
`Exhibit 1224 Page 14 of 32
`
`

`

`-.l
`~
`"'+>
`0
`.J:o.
`~
`
`00 =- nl sa.
`
`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.l 0
`
`10C
`FIG.
`108
`FIG.
`10A
`FIG.
`
`Exhibit 1224 Page 15 of 32
`
`

`

`fiG.llA
`
`~ • 00.
`
`•
`
`FIG.11
`11C
`FIG.
`11 B
`FIG.
`11A
`FIG.
`
`CEASES
`JAMMING
`
`ALL JAMMERS
`
`TO FINISH
`
`WAIT FOR
`
`JAM PERIOD
`
`ELAPSED
`
`THE BUS
`
`JAM
`
`TO SEND
`READY
`TRAFFIC
`
`BUS IDLE
`
`.-------L..----11~
`
`W SLOT TIMES
`
`IDLE ELAPSED
`FRAME GAP
`
`+
`
`OR W SLOT TIMES
`BUS IDLE FOR
`
`FRAME GAP
`
`+
`
`DETECTED
`MESSAGE
`
`DETECTED
`SHORT JAM
`
`RESYNCHRONIZE -WAIT FOR:
`
`DETECTED
`
`JAM
`
`"TRANSMITIER CONFUSED"
`
`ANY ERROR
`
`OR
`
`TRANSMITIER RESET OR
`
`POWER TURNED ON
`
`Exhibit 1224 Page 16 of 32
`
`

`

`FIG.ll B
`
`ELAPSED
`p SLOTS
`
`DETACHED
`ANY SIGNAL
`
`ELAPSED
`Q SLOTS
`
`Pth SLOT
`WAIT FOR
`
`DETECTED
`MESSAGE
`
`YES
`
`TIME ELAPSED
`FRAME GAP
`
`COMPLETED
`TRANSMISSION _ ____._-:-::----,
`
`GAP
`FRAME
`
`BUS BUSY
`
`00 .
`d
`
`Exhibit 1224 Page 17 of 32
`
`

`

`-....l
`....
`0 ......
`-....l
`....
`~ .....
`~
`1:1"'
`00
`
`<.II
`~
`....
`~ .$-
`
`~<.II
`~
`
`•
`00.
`~ •
`
`FSD FOR RCSMA PROTOCOL WITH FIXED PRIORITY AND MULTI-LEVEL, ROTATING SLOTS.
`
`FIG.llC
`
`MESSAGE
`I.D. &
`TRANSMIT
`
`ElAPSED
`Z SLOTS
`
`Zth SLOT
`WAIT FOR
`
`DETECTED
`ANY SIGNAL
`
`TIME ElAPSED
`FRAME GAP
`
`SECONDARY
`
`GAP
`FRAME
`
`COMPLETED
`TRANSMISSION
`
`YES
`
`ElAPSED
`J-Y SLOTS
`ANOTHER
`
`SLOTS
`REST OF
`WAIT FOR
`
`NO
`
`Yth SLOT
`WAIT FOR
`
`DETECTED
`ANY SIGNAL
`
`Exhibit 1224 Page 18 of 32
`
`

`

`SYNCHRONOUS TIME DIVISION
`MULTIPLEXING USING JAM-BASED FRAME
`SYNCHRONIZATION
`
`This is a File Wrapper Continuation of application
`Ser. No. 7/992,879, ffied 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 scheme.
`
`2
`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(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
`I. SYNCHRONOUS 1DM 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 assigmnent.
`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 different 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.
`communication 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
`50 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 calli-
`ever, some protocols, notably synchronous Time Divi-
`sion detection techniques rely on approximately equal
`sion Multiplexing (synchronous 1DM) protocols, are
`signal strengths from colliding transmitted signals.
`implemented such that the transceiver finite state rna-
`However, in a large building, signals over twisted pair 55 chine is in a state other than BUS IDLE for long peri-
`wires are severely attenuated over 2000 feet, so signal
`ods of time, even though no messages are being sent.
`strengths from some transceiver pairs are very unequal.
`These protocols, including synchronous 1DM, 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.
`In some protocols, such as
`There is a maximum clock drift that can be tolerated
`transmission delays.
`CSMA/CD, there is no guarantee 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
`prioritization of network access as required by elevator
`pad time must be allowed between consecutive trans-
`control loops and safety schemes. CSMA/CD, for e:x-
`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 1224 Page 19 of 32
`
`

`

`5,436,901
`
`3
`4
`neously (within a propagation delay along the commu-
`avoidance and, therefore, correct operation. A good
`nications medium, known as the vulnerable period)
`way of accomplishing this is to schedule a resynchroni-
`zation just before the accumulated clock drift goes out
`with a resultant collision and loss of data. This method
`has poor performance at high load and has poor real-
`of tolerance. One way to do this is to perform resyn-
`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-
`use.
`pie Access with Collision Detection (CSMA/CD).
`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-
`each transmission frame, using a frame sync signal.
`10 tion circuit is able to detect the resultant collisions, and
`Perhaps the most straightforward communication
`truncate the transmission of data from both transceiv-
`scheme is synchronous Time Division Multiplexing
`ers.
`(synchronous TDM). In the 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. This bus master queries each transceiver in 15 reduce the change of subsequent collisions.
`tum, allowing each transceiver to transmit a message
`One variation of CSMA/CA that is suited to embed-
`when queried. This system has high overhead because
`ded and real time control communications is Reserva-
`of the query messages and responses that must be gener-
`tion Carrier Sense Multiple Access
`(RCSMA).
`ated even when the responding transceiver has no use-
`RCSMA is an implicit token system in which there is a
`fu1 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.
`Still more sophisticated versions of synchronous
`ceiver. If any transceiver has a message to send, it waits
`TDM are possible. For example, a single bus master
`for its slot (measured as a unique time delay for each
`may simply transmit a frame synchronization message
`transceiver from 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-
`manly, synchronous TDM protocols employ a single
`ring a message with a guarantee that it is the sole active
`designated bus master transceiver to issue the frame
`transceiver (because of the one-tO-<>ne mapping of slots
`to transceivers). If a transceiver has no message to send,
`sync signal. This has obvious limitations in terms of
`reliability and designation of the common bus master. 30 it remains idle and its time slot elapses, allowing the next
`Each transceiver then may transmit during its own
`transceiver's time slot to start. The slots are referred to
`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
`sense whether there is activity on the bus, and cut short
`access. Elaborations upon RCSMA known in the art
`unused time slices.
`35 include assigning slots in different groupings to imple-
`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 the 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
`outgoing queue must wait for that transceiver's time
`number of transceivers supported in that as the number
`slice.
`of transceivers grows the number of implicit token slots
`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-
`lems if that predetermined transceiver becomes non-
`end of a transmitted message. However, a problem
`functional) or is determined via a potentially lengthy
`arises when there is no message to be sent, allowing all
`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?_
`A VOIDANCE PROTOCOLS
`There are four strategies known to the art.
`Contention-based protocols are protocols in which
`D. NETWORK RESTART
`multiple transceivers contend for access to the commu-
`1. NETWORK RESTART WITH ARBITRA-
`nications medium asynchronously.
`TION
`A simple media access protocol for LANs is Carrier 60
`The NETWORK RESTART WITH ARBITRA-
`Sense Multiple Access (CSMA), where "Carrier Sense"
`TION technique for RCSMA is taught by Kiesel and
`refers to the ability of a transceiver to detect data being
`Kuehn, IEEE Journal on Selected Areas in Communica-
`asserted on the communication medium. When a traus-
`tions, Vol. SAC-I, No. 5, November 1983, pages
`869-876. We shall refer to this method as the Reserva-
`ceiver has an outgoing message, it first performs carrier
`sensing to see if the medium is busy. If the medium is 65 tion Carrier Sense Multiple Access/Collision Detection
`idle, it then transmits a message. Receipt acknowledg-
`(RCSMA/CD) scheme.
`If the network is idle when a transceiver acquires a
`ments are required, because there is a possibility of two
`transceivers beginning trausmission nearly simulta-
`message to send, the transceiver begins trausmitting
`
`Exhibit 1224 Page 20 of 32
`
`

`

`5
`data immediately as in CSMA/CD. Implicit token slots
`begin after e2eh 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 5
`just been issued. This teChnique addresses the problem
`of what to do when there is no netwo.rk 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 signal 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 Tran.sactions on Comput(cid:173)
`ers. Volume C-33, No. 12, December 1984, Pages
`ll3D-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 DAT AC 65
`chip set by having two cross-checked oscillators instead
`of only one). After e2eh 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(cid:173)
`ers. There are several problems with using this scheme
`for the exemplary elevator commun.ications 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-on and reset problems remain be(cid:173)
`cause the initial active transceiver must be chosen.
`DAT AC 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 1224 Page 21 of 32
`
`

`

`5,436,901
`
`8
`(e) larger numbers of transceivers allowed than with
`other implicit token systeiDS without long slot progres(cid:173)
`sions by using multi-level slot progressions.
`
`20
`
`7
`It follows from the first predicate that the present
`invention provides a means for synchronization of a
`plurality of transceivers on a shared communications
`medium using a "jamming" signal, thereby eliminating
`BRIEF DESCRIPTION OF THE ORA WINGS
`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 tec