United States Patent [19J
`Koopman et al.
`
`11111111111111111111111111111111111111111111111 IIIII IIIII 111111 11111111 1111
`US005535212A
`[11] Patent Number:
`[45] Date of Patent:
`
`5,535,212
`Jul. 9, 1996
`
`[54]
`
`IMPLICIT TOKEN MEDIA ACCESS
`PROTOCOL WITHOUT COLLISION
`DETECTION
`
`[75]
`
`Inventors: Philip J, Koopman, Hebron; David C.
`Brajczewski, Vernon, both of Conn.
`
`[73] Assignee: Otis Elevator Company, Farmington,
`Conn.
`
`[21] Appl. No.: 189,944
`
`[22] Filed:
`
`Jan. 31, 1994
`
`Related U.S. Application Data
`
`[63] Continuation of Ser. No. 992,877, Dec. 21, 1992, aban(cid:173)
`doned.
`Int. Cl.6
`.. ............................... . H04L 5/22; H04J 3/06
`U.S. Cl. ...................... 370/85.6; 370/95.3; 370/100.1
`Field of Search .................................. 370/85.1, 85.2,
`370/85.3, 85.4, 85.6, 85.7, 95.3, 13, 95.3,
`95.1, 100.1, 825.5, 825.51; 375/362, 356
`
`[51]
`[52]
`[58]
`
`[56]
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,330,857
`4,379,294
`4,438,520
`4,603,418
`4,606,022
`4,628,311
`
`5/1982 Alvarez, ill et al. .................. 370/95.3
`4/1983 Sutherland et al .................. 340/825.5
`3/1984 Saltzer ................................. 370/100.1
`611986 Townsend .............................. 370/95.3
`8/1986 Suzuki et al ......................... 3701100.1
`12/1986 Milling ................................ 340/825.5
`
`4,719,620
`4,763,325
`4,907,222
`4,980,886
`5,012,469
`5,070,501
`5,153,578
`5,161,151
`5,189,670
`
`111988 Machino et al ...................... 370/100.1
`8/1988 Wolfe et al ............................ 370/95.3
`3/1990 Slavik .................................. 370/100.1
`12/1990 Bernstein ............................... 370/95.3
`4/1991 Sardana .................................. 370/95.3
`12/1991 Shimizu ................................. 370/85.4
`10/1992 Izawa et al ............................ 370/94.2
`1111992 Kimura et al ............................. 370/13
`2/1993 Inglis ................................... 370/100.1
`
`OTHER PUBLICATIONS
`
`Werner Bux, "Token-Ring Local-Area Networks and Their
`Performance" Feb. 1989, Proceeding of The IEEE, vol. 77,
`No.2.
`Primary Examiner-Wellington Chin
`Assistant Examiner-Chau T. Nguyen
`ABSTRACT
`
`[57]
`
`lf 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 propaga(cid:173)
`tion delay). If a transceiver detects a jamming pattern, it
`inhibits its own transmissions and waits for the next slot
`progression. If multiple transceivers begin jamming within
`a propagation delay of each other (within the network
`vulnerable time), their jamming transmissions will not
`destructively interfere with each other. When jamming
`ceases, all transceivers begin a slot 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 slot progression.
`
`7 Claims, 10 Drawing Sheets
`
`TRANS~ITIER RESET OR
`POWER TURNED ON
`
`I
`
`ANY ERROR OR
`"TRANSMJTIER CONFUSED'
`
`I
`
`RESYNCHRONILE -WAIT FOR:
`
`JAM
`DSTECTED
`
`OR
`
`BUS IDLE FOR
`MAXIMUM
`IDLE PERIOD
`
`B
`US JAM
`0 m:c~to
`
`LE FOR
`BUS 10
`MUM
`MAXI
`IDLE P
`ERIOD
`
`I JAM 1Ho Bus 1
`
`JAM PE RIOD
`ED
`ELAPS
`
`I
`
`l
`
`WAIT FOR ALL
`JAMMERS TO FINISH
`JAMMING I
`CEASES i
`~
`~
`FRAME CAP
`TIME ElAP>'li'O
`
`BUS
`OWNERSHIP
`MESSAGE ,---
`OETEClEO
`
`--,
`
`Exhibit 1323 Page 01 of 23
`
`

`
`U.S. Patent
`
`Jul. 9, 1996
`
`Sheet 1 of 10
`
`5,535,212
`
`fig. 1
`'
`
`~ I
`
`TRANSMITIER
`AND
`RECEIVER
`
`COMMUNICATIONS MEDIUM
`7
`
`1\ I
`
`TRANSMITIER
`AND
`RECEIVER
`
`1
`
`TRANSMITTER
`AND
`RECEIVER
`
`fig.2
`
`OPERATION
`BEFORE
`SYNCHRONIZATION
`
`JAM
`BUS
`
`DETE CTED
`
`T RANSMITIER
`NEEDS TO GENERATE
`HRONIZATION
`SYNC
`EVENT
`
`I JAM THE BUS 1
`
`ERIOD
`JAM P
`
`ELAP SED
`
`WAIT FOR ALL
`JAMMERS TO FINISH
`
`JAMMING
`CEASES
`
`SYNCHRONIZATION
`ACHIEVED
`
`OPERATION AFTER
`SCNCHRONIZATION
`
`Exhibit 1323 Page 02 of 23
`
`

`
`U.S. Patent
`
`Jul. 9, 1996
`
`Sheet 2 of 10
`
`5,535,212
`
`fig.3
`
`TRANSMITIER RESET
`POWER TURNED ON
`~
`RESYNCHRONIZE -WAIT FOR:
`
`ANY ERROR OR
`"TRANSMITIER CONFUSED"
`
`'
`
`JAM
`DETECTED
`
`BUS JAM
`DETECTED
`
`-
`
`IDLE FOR
`BUS
`OR N SLICE TIMES
`+
`FRAME GAP
`
`N SLICE TIMES
`+
`FRAME GAP
`IDLE ELAPSED
`.----..__----1---,
`
`I JAM THE BUS I
`
`I
`JAM PERIOD
`ELAPSED
`
`WAIT FOR ALL
`JAMMERS TO FINISH
`
`L
`~------..
`
`JAMMING
`CEASES
`
`I FRAME
`l GAP
`FRAME GAP
`TIME ELAPSED
`
`WAIT FOR
`Mth SLICE
`M TIME SLICE
`ELAPSED
`
`TRANSMIT
`BUS JAM
`MESSAGE 11-----~
`DETECTED
`
`TRANSMISSION
`TIME SLICE
`ELAPSED
`
`WAIT FOR
`REST OF
`SLICES
`
`ANOTHER
`N-M-1 SLICES
`ELAPSED
`
`Exhibit 1323 Page 03 of 23
`
`

`
`U.S. Patent
`
`Jul. 9, 1996
`
`Sheet 3 of 10
`
`5,535,212
`
`fig.4
`TRANSMITIER 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
`
`I JAM THE BUS
`JAM PERIOD
`ELAPSED
`
`WAIT FOR ALL
`JAMMERS TO FINISH
`
`JAMMING
`CEASES
`
`FRAME I
`
`GAP
`\
`FRAME GAP
`TIME ELAPSED
`
`BUS
`OWNERSHIP
`MESSAGE . - -----..
`NOT THE
`BUS
`MASTER
`
`I WAIT FOR I DETECTED
`
`1 - - - -------.l
`
`Mth SLOT I
`M SLOT
`ELAPSED
`
`TRANSMIT BUS
`ONERSHIP
`MESSAGE
`
`TRANSMITIER
`IS BUS
`MASTER
`
`Exhibit 1323 Page 04 of 23
`
`

`
`U.S. Patent
`
`Jul. 9, 1996
`
`Sheet 4 of 10
`
`5,535,212
`
`fig.S
`
`TRANSMITTER RESET OR
`POWER TURNED ON
`~
`RESYNCHRONIZE-WAIT FOR:
`
`t
`
`ANY ERROR OR
`"TRANSMITTER CONFUSED"
`
`BUS JAM
`
`NODE
`ADMISSION
`PERMITTED
`
`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
`, - - - - lL - - - . .
`NOT THE
`DETECTED
`! WAIT FOR (
`1------~ BUS 1------.
`Mth SLOT I
`MASTER
`M SLOT
`ELAPSED
`
`RECEIVED
`TOKEN
`
`TRANSMIT BUS
`ONERSHIP
`MESSAGE
`
`I PASS I
`
`TOKEN
`
`TRANSMIT
`MESSAGES
`
`DONE
`TRANSMITTING
`
`Exhibit 1323 Page 05 of 23
`
`

`
`U.S. Patent
`
`Jul. 9, 1996
`
`Sheet 5 of 10
`
`5,535,212
`
`fig.6
`TRANSMITIER RESET
`POWER TURNED ON
`
`ANY ERROR OR
`"TRANSMITIER CONFUSED"
`
`~
`
`RESYNCHRONIZE -WAIT FOR:
`
`'
`
`JAM
`DETECTED
`
`OR
`
`IDLE FOR
`BUS
`N SLOT TIMES
`+
`FRAME GAP
`
`BUS JAM
`DEfECTED
`
`N SLOT TIMES
`+
`FRAME GAP
`IDLE ELAPSED
`
`I BUS IDLE
`
`~t---,
`TRAFFIC READY
`TO SEND
`
`BUS JAM
`DETECTED
`
`WAIT FOR ALL
`JAMMERS TO FINISH
`
`JAMMING
`CEASES
`
`l JAM THE BUS I
`
`J
`
`JAM PERIOD
`ELAPSED
`
`FRAME
`GAP
`FRAME GAP
`TIME ELAPSED
`'
`
`MESSAGE
`DETECTED
`WAIT FOR
`r - - - - -- -l Mth SLOT
`
`M SLOT
`ELAPSED
`
`MESSAGES
`READY
`TRANSMIT?
`
`y
`
`N
`MESSAGE ..-------''--------.
`,.---'----..DETECTED WAIT FOR
`REST OF
`SLOTS
`
`I BUS BUSY:
`
`TRANSMISSION
`COMPLETED
`
`TRANSMIT
`._M_Es_s_A_GE_s.....,. TRANSMISSION
`COMPLETED
`
`Exhibit 1323 Page 06 of 23
`
`

`
`U.S. Patent
`
`Jul. 9, 1996
`
`Sheet 6 of 10
`
`5,535,212
`
`fig.7
`
`TRANSMilTER RESET OR
`POWER TURNED ON
`
`ANY ERROR OR
`"TRANSMilTER CONFUSED"
`
`RESYNCHRONIZE-WAIT FOR:
`
`'
`
`BUS IDLE FOR
`MAXIMUM
`IDLE PERIOD
`
`IDLE FOR
`BUS
`MAXIMUM
`IDLE PERIOD
`
`SHORT BUS
`JAM
`DETECTED
`
`SHORT
`JAM
`DETECTED
`
`NOT THE
`BUS MASTER
`
`BUS
`OWNERSHIP
`MESSAGE
`DETECTED
`
`JAM
`DETECTED
`
`OR
`
`BUS JAM
`DETECTED
`
`JAMMING
`CEASES
`
`JAM PERIOD
`ELAPSED
`
`SECONDARY
`FRAME GAP
`FRAME GAP
`TIME ELAPSED
`
`TRANSMIT BUS
`OWNERSHIP
`MESSAGES
`
`TRANSMISSION
`COMPLETED
`
`TRANSMilTER
`IS BUS MASTER
`
`Exhibit 1323 Page 07 of 23
`
`

`
`U.S. Patent
`
`Jul. 9, 1996
`
`Sheet 7 of 10
`
`5,535,212
`
`TRANSMITIER RESET OR
`POWER TURNED ON
`
`J
`
`ANY ERROR OR
`~TRANSMITIER CONFUSED"
`
`RESYNCHRONIZE-WAIT FOR:
`
`fig.B
`
`JAM
`DETECTED
`
`OR
`
`IDLE FOR
`BUS
`L SLOT TIMES +
`FRAME GAP
`
`SHORT
`JAM
`DETECTED
`
`BUS JAM
`DETECTED
`
`L SLOT TIMES +
`FRAME GAP
`IDLE ELAPSED
`
`BUS JAM
`DEfECTED
`
`TRANSMISSION
`COMPLETED ~.--B-U_S_BU_S_Y--.1
`
`I BUS IDLE~
`l
`TRAFFIC
`READY
`TO SEND
`
`JAM THE BUS I
`
`JAM PERIOD
`ELAPSED
`
`JAMMERS TO FINISH
`
`I WAIT FOR ALL
`!FRAME I
`
`JAMMING
`CEASES
`
`GAP
`FRAME GAP
`TIME ELAPSED
`
`SHORT
`JAM
`
`I WAtT FOR LDETECTED
`Gth SLOT I
`G SLOT
`ELAPSED
`
`MESSAGE
`DETECTED
`
`JwArr FOR •1
`I OTHERS
`
`MESSAGE
`READY TO
`TRANSMIT ?
`N
`
`y
`
`JAM THE BUSJ
`(GROUP)
`
`FRAME GAP
`FRAME GAP
`TIME ELAPSED
`
`I SECONDARY I
`I
`I WAIT FOR I
`Hth SLOT I H SLOTS I MESSAGE
`ELAPSED
`
`TRANSMISSION
`COMPLETED
`
`I TRANSMIT l-
`
`I WAIT FOR I
`
`Gth SLOT
`SHORT
`JAM
`DETECTED
`
`Exhibit 1323 Page 08 of 23
`
`

`
`U.S. Patent
`
`Jul. 9, 1996
`
`Sheet 8 of 10
`
`5,535,212
`
`fig.9
`
`TRANSMITTER RESET
`POWER TURNED ON
`
`.
`
`RESYNCHRONIZE-WAIT FOR:
`
`ANY ERROR OR
`"TRANSMITTER CONFUSED"
`
`'
`
`BUS JAM
`
`MESSAGE
`DETECTED
`
`BUS IDLE FOR
`OR N SLOT TIMES +
`FRAME GAP
`
`MESSAGE
`DETECTED
`
`BUS JAM
`DEfECTED
`
`BUS JAM
`DETECTED
`
`N SLOT TIMES +
`FRAME GAP
`IDLE ELAPSED
`
`I BUS IDLE I
`1~..------, TRAFFIC
`READY
`TO SEND
`
`I JAM THE BUS I
`
`JAM PERIOD
`ELAPSED
`
`\
`
`WAIT FOR ALL
`JAMMERS TO FINISH I
`JAMMING
`CEASES
`
`TRANSMISSION
`r-IB_U_S~BU_S_Y--..j COMPLETED
`
`I FRAME ~ ..... - - - - - - ,
`1 GAP J
`TRANSMISSION
`COMPLETED
`FRAME GAP
`TIME ELAPSED
`
`MESSAGE
`._D_Er_E_C_TE_D __ ----l WAIT FOR
`Mth SLOT
`M SLOTS
`ELAPSED
`
`MESSAGE
`READY TO
`TRANSMIT ?
`N
`
`Y
`
`I TRANSMIT
`I MESSAGE
`
`MESSAGE
`DETECTED
`
`WAIT FOR
`REST OF
`SLOTS
`ANOTHER
`N-M SLOTS
`ELAPSED
`
`' - - - - - - --
`
`- - - - - - - - '
`
`Exhibit 1323 Page 09 of 23
`
`

`
`U.S. Patent
`
`Jul. 9, 1996
`
`Sheet 9 of 10
`
`5,535,212
`
`TRANSMITIER RESET
`POWER TURNED ON
`
`ANY ERROR OR
`"TRANSMITTER CONFUSED"
`
`fig. 10
`
`RESYNCHRONIZE-WAIT FOR:
`
`JAM
`DETECTED
`MESSAGE OR
`DETECTED
`
`IDLE FOR
`BUS
`N+Q SLOT TIMES +
`FRAME GAP
`
`MESSAGE
`DETECTED
`
`BUS JAM
`DETECTED
`
`N+Q SLOT TIMES +
`FRAME GAP
`IDLE ELAPSED
`
`l BUS IDLE _I
`~ TRAFFIC READY
`TO SEND
`~
`JAM THE BUS I
`JAM PERIOD!
`ELAPSED j
`
`BUS JAM
`DETECTED
`
`I WAIT FOR ALL
`
`JAMMERS TO FINISH
`
`JAMMING
`CEASES
`TRANSMISSION
`I FRAME lt---- - - - - - - -- - - . ,
`r -1 - - ' - -8-U ~. COMPLETED
`I GAP
`I TRANSMISSION
`'-BT"u_s,--r-s..,y-1
`FRAME GAP
`COMPLETED
`TIME ELAPSED
`
`PRIORITY
`MESSAGE TO
`TRANSMIT ?
`
`y
`
`N
`
`P SLOTS
`,.--WA_I_T _F_O_R--..1 ELAPSED
`Pth SLOT I
`
`TRANSMIT
`I.D. AND
`MESSAGE
`
`MESSAGE
`DETECTED
`
`MESSAGE
`DETECTED
`
`MESSAGE
`DETECTED
`
`WAIT FOR
`REST OF
`SLOTS
`Q SLOTS
`ELAPSED
`MESSAGE
`.-----''--...
`..::;D..:::ET.c...:E.c...:C'-'-T=ED=------1 WAIT FOR
`Rth SLOT
`R SLOTS
`ELAPSED
`MESSAGE
`READY TO
`TRANSMIT ?
`tN
`WAIT FOR
`ANOTHER
`REST OF
`'---SL..,o_T_s_ N-R SLOTS
`ELAPSED
`1
`
`y
`
`Exhibit 1323 Page 10 of 23
`
`

`
`U.S. Patent
`
`Jul. 9, 1996
`
`Sheet 10 of 10
`
`5,535,212
`
`TRANSMITIER RESET OR
`POWER TURNED ON
`
`fig . 11
`
`t
`
`ANY ERROR OR
`"TRANSMilTER CONFUSED"
`
`t
`
`RESYNCHRONIZE -WAIT FOR:
`
`SHORT
`JAM
`DETECTED
`
`JAM
`DETECTED
`
`MESSAGE
`DETECTED
`
`OR
`
`BUS IDLE FOR
`W SLOT TIMES +
`FRAME GAP
`
`BUS JAM
`DETECTED
`
`MESSAGE
`DETECTED
`
`BUS JAM
`DETECTED
`
`I WAIT FOR ALL
`
`JAMMERS TO FINISH
`
`W SLOT TIMES +
`FRAME GAP
`IDLE ELAPSED
`t
`I BUS IDLE l
`~TRAFFIC READY
`TO SEND
`JAM THE sus)
`JAM PERIOD~
`ELAPSED
`
`JAMMING
`CEASES
`TRANSMISSION
`BUSY 1 COMPLETED
`I
`
`I FRAME I
`l GAP r TRANSMISSION
`
`II BUS
`
`FRAME GAP
`TIME ELAPSED
`
`PRIORITY
`MESSAGE TO
`TRANSMIT ?
`
`N
`
`'MESSAGE
`DETECTED
`ANY SIGNAL
`DETECTED
`
`WAIT FOR
`ALL FIXED
`SLOTS
`0 SLOTS
`ANY SIGNAL ELAPSED
`DETECTED
`WAIT FOR
`Yth SLOT
`Y SLOTS
`ELAPSED
`MESSAGE
`READY TO
`TRANSMIT ?
`N
`
`WAIT FOR I
`MESSAGE I
`t
`
`WAIT FOR
`REST OF
`SLOTS
`r
`
`COMPLETED
`
`P SLOTS
`y WAIT FOR 1 ELAPSED
`Pth SLOT I
`I
`
`TRANSMIT
`I.D. AND
`MESSAGE
`
`I
`JAM THE ~
`- ~BUS (GROUP)
`
`t
`I SECONDARYl
`
`FRAME GAP
`FRAME GAP,!
`y TIME ELAPSED
`riWAIT FORl
`Zth SLOT f Zth SLOT
`ELAPSED
`ANY SIGNAL
`DETECTED
`
`ANOTHER
`J-Y SLOTS
`ELAPSED
`
`Exhibit 1323 Page 11 of 23
`
`

`
`5,535,212
`
`1
`IMPLICIT TOKEN MEDIA ACCESS
`PROTOCOL WITHOUT COLLISION
`DETECTION
`
`This is a Continuation of application Ser. No. 07/992, 5
`877, filed Dec. 12, 1992, abandoned.
`
`TECHNICAL FIELD
`This invention relates to computer communication pro- 10
`tocols, and in particular, to a Reservation Carrier Sense
`Multiple Access (RCSMA) media access scheme.
`
`BACKGROUND OF THE INVENTION
`
`2
`Fourth, some protocols (e.g., CSMA/CD) make inefficient
`use of network bandwidth under heavy loading conditions.
`Existing elevator systems often have slow-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 pro(cid:173)
`tocols, 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 acknowledgments
`because multiple acknowledgment messages take up band-
`15 width. Therefore, lack of acknowledgment is not available
`as an indirect means for detecting collisions.
`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 medium
`20 master.
`Eighth, some protocols support only a limited number of
`transceivers. For example, implicit token protocols 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
`ball 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
`I. SYNCHRONOUS TDM PROTOCOLS
`In many communications systems there is a need to
`occasionally resynchronize all transceivers to a common
`point in time. One reason synchronization is needed is that
`the local clock for each transceiver (usually based on a
`crystal oscillator or resistor/capacitor oscillaLor 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 con-
`tinual messages implies a bus idle state can use the messages
`themselves as resynchronization points. However, some
`protocols, notably synchronous Time Division Multiplexing
`(synchronous TDM) protocols, are implemented such that
`the transceiver finite state machine is in a state other than
`BUS IDLE for long periods of time, even though no
`messages are being sent. These protocols, including syn(cid:173)
`chronous TDM, usually use explicit resynchronization sig(cid:173)
`nals to limit the accumulated clock drift over time between
`55 different transceivers.
`There is a maximum clock drift that can be tolerated while
`still maintaining synchronized transmission and reception
`within a protocol. For example, if two transceivers are to
`take turns transmitting based on time alone (as opposed to
`detection of other transmissions), a pad time must be
`allowed between consecutive transmissions 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
`65 schedule a resynchronization just before the accumulated
`clock drift goes out of tolerance. One way to do this is to
`perform resynchronization at fixed intervals (based on worst
`
`50
`
`25
`
`If multiple transceivers attempt to use a medium simul(cid:173)
`taneously, the transmissions collide, resulting in garbled
`messages and potentially lost data. Media Access Control
`(MAC) protocols are used to arbitrate 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
`Networks (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 right to transmit.
`Token ownership is relinquished to another transceiver by 30
`sending a token message. Implicit tokens are time slots
`which, if used, grant exclusive access to the medium. They
`are implicit because no real token message exists. Rather,
`each time slot period of time on the communications
`medium carries with it the meaning of a token-to-transceiver 35
`assignment.
`A. MEDIA ACCESS CONTROL PROTOCOL SELEC-
`TION
`1. EXEMPLARY ELEVATOR SYSTEM
`In the communication protocol selection process, a num- 40
`ber of factors should be considered. An exemplary applica(cid:173)
`tion to illustrate some of these factors is an elevator system
`which uses twisted-pair wires as a shared communications
`medium.
`Of further interest are LANs that apply to embedded and 45
`real time control applications that require predictable and/or
`deterministic system response.
`2. FACTORS TO BE CONSIDERED IN MEDIA
`ACCESS PROTOCOL SELECTION IN LIGHT OF PRIOR
`ART
`First, collision detection circuits are impracticable in
`some elevator communications systems. Analog collision
`detection techniques rely on approximately equal signal
`strengths from colliding transmitted signals. However, in a
`large building, signals over twisted pair wires are severe! y
`attenuated over 2000 feet, so signal strengths from some
`transceiver pairs are very unequal.
`Second, real time response requirements of elevator sys(cid:173)
`tems, for purposes of safety and control loop stability,
`require both predictable and bounded message transmission 60
`delays. In some protocols, such as CSMA/CD, there is no
`guarantee that any particular message will be delivered
`within a bounded time interval.
`Third, many protocols do not allow for deterministic
`prioritization of network access as required by elevator
`control loops and safety schemes. CSMA/CD, for example,
`provides no guarantees for priority service.
`
`Exhibit 1323 Page 12 of 23
`
`

`
`5,535,212
`
`5
`
`3
`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 (synchronous
`TDM). In the traditional master/slave implementation, a
`single transceiver is designated as the bus master. This bus
`master queries each transceiver in turn, allowing each trans- 10
`ceiver to transmit a message when queried. This system has
`high overhead because of the query messages and responses
`that must be generated even when the responding transceiver
`has no useful messages to send. This system also has the
`obvious reliability problem of a single master.
`Still more sophisticated versions of synchronous TDM are
`possible. For example, a single bus master may simply
`transmit a frame synchronization message ("frame sync"),
`allowing all other transceivers to measure a unique time
`delay from that frame sync. Commonly, synchronous TDM 20
`protocols employ a single 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 even 25
`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 deter(cid:173)
`mining which transceiver is the bus master. Either it must be
`predesignated, or arbitration among transceivers 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 outgoing queue must wait for that trans(cid:173)
`ceiver's time slice.
`2. EXPLICIT TOKEN PROTOCOLS
`As mentioned previously, an explicit token is a message
`that is passed from transccivcrlrcceiver to transceiver/re(cid:173)
`ceiver as control of the medium is passed. In explicit token
`protocols known to the art, the initial token bolder is either
`designated as a predetermined transceiver on the network
`(leading to reliability problems if that predetermined trans(cid:173)
`ceiver becomes non-functional) or is determined via a
`potentially lengthy arbitration method involving collision 45
`detection.
`3. CONTENTION-BASED AND COLLISION-AVOID(cid:173)
`ANCE PROTOCOLS
`Contention-based protocols are protocols in which mul(cid:173)
`tiple transceivers contend for access to the communications
`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 asserted on
`the communication medium. When a transceiver 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 acknowledgments are required, because
`there is a possibility of two transceivers beginning trans(cid:173)
`mission nearly simultaneously (within a propagation delay
`along the communications medium, known as the vulnerable
`period) with a resultant collision and loss of data. This
`method has poor performance at high load and has poor
`real-time performance characteristics.
`An improvement over CSMA is Carrier Sense Multiple
`Access with Collision Detection (CSMA/CD). When two
`transceivers begin transmission onto the medium within the
`
`4
`vulnerable period a collision detection circuit is able to
`detect the resultant collisions, and truncate the transmission
`of data from both transceivers.
`Collision avoidance CSMA protocols (CSMA/CA) use
`Lime slots after each collision and transmission to reduce the
`change of subsequent collisions.
`One variation of CSMA/CA that is suited to embedded
`and real time control communications is Reservation 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 transceiver. If any transceiver has a mes(cid:173)
`sage to send, it waits for its slot (measured as a unique time
`delay for each transceiver from the end of the previous
`15 message). When a transceiver's time slot is elapsing on the
`communications 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 implement 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 colli-
`30 sian 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.
`35 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 network.
`In RCSMA, implicit token slots begin to elapse at the end
`40 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
`1. NETWORK RESTART WITH ARBITRATION
`The NETWORK RESTART WITH ARBITRATION
`technique for RCSMA is taught by Kiesel and Kuehn, IEEE
`Journal on Selected Areas in Communications, Vol. SAC-1,
`50 No.5, November 1983, pages 869-876. We shall refer to this
`method as the Reservation 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 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 simply 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 limitation 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
`
`55
`
`60
`
`65
`
`Exhibit 1323 Page 13 of 23
`
`

`
`5,535,212
`
`6
`(c) system power-on and reset problems remain because
`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 limitation
`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 previous proto(cid:173)
`cols: (a) single point of failure and (b) need for collision
`detection.
`
`DISCLOSURE OF THE Ji'IVENTION
`
`15
`
`20
`
`25
`
`5
`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 5
`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 synchronization signal to start a new
`slot progression. By relying on a single master, there is 10
`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 failure
`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 practical limitation
`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 Computers, Volume C-33 ,
`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 exemplary
`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 limitation
`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 DISTRIB(cid:173)
`UTED MASTERS, to avoid the need for a central or rotating
`master. The DATAC system chip set from National Semi(cid:173)
`conductor uses this approach for a synchronous TDM imple(cid:173)
`mentation. 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 DATAC chip set by having two cross-checked oscil(cid:173)
`lators instead of only one). After each message, a slot
`progression is initiated. Whenever the slot progression is
`completed with no network activity, a new slot progression
`is automatically initiated. In other words, slot progressions
`repeat indefinitely without frame synchronization while the
`network remains idle.
`The mastership is "distributed" among all transceivers.
`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 redun(cid:173)
`dant oscillators;
`(b) a transceiver that has lost track of the protocol state
`through some transient error or reset cannot immedi(cid:173)
`ately access the network while the network is idle,
`because there are no transmissions on the network to 65
`indicate where, in the time slot progression, other
`transceivers are located;
`
`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 mes(cid:173)
`sages; highly efficient use of available communications
`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 support of
`multiple transceivers at the same priority level within a slot
`progression. A consequence of this slot-sharing capability is
`a significant increase in the number of transceivers wlllch
`can be supported.
`The present invention is predicated on the observation
`that some communication protocols involve collision detec(cid:173)
`tion by collision detection circuitry followed by transmis(cid:173)
`sion 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 transceivers that a collision has
`occurred.
`The present invention is further predicated on the obser(cid:173)
`vation that synchronization of a plurality of transceivers is
`40 required to start a sequence of events within a communica(cid:173)
`tions protocol for shared medium access. One way to
`accomplish this is to have each transceiver desiring to
`initiate the sequence of events assert a message onto the
`communications medium. The problem with this method as
`45 currently practiced in the art is that collisions will take place
`if two transceivers assert such initiation messages within the
`"vulnerable time" (related to signal propagation delay) of
`the network. Said collisions corrupt data being sent and fail
`to establish unique ownership of the communications
`50 medium; furthermore, detecting such collisions is undesir(cid:173)
`able.
`It follows from the first predicate that the present inven(cid:173)
`tion provides a means for synchronization of a 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 conse(cid:173)
`quence of the second predicate, one way to use such a
`synchronization technique is to let the jam signal serve as a
`60 unique time point from which to start an implicit token slot
`progression.
`According to the present invention, a collision, multiple
`signals transmitting onto an idle bus, is assumed and access
`to an idle