CA1236541A - Communications method - Google Patents

Abstract

ABSTRACT

The present disclosure relates to a communications method for communicating data over a data channel that comprises two unidirectional communication lines. A protocol which is a set of predetermined control characters is used by the com-munications method and the protocol is used for transferring data between communicating devices. The communications method combines acknowledgments which are control characters of the protocol transmitted in between messages, piggy-backing which is the combining of control characters of the protocol and data messages, and hold-offs with long time outs which cause the devices to enter a standby idle mode waiting for a responsive control character of the protocol. The communications system and method combines these features so as to permit improved efficient flow control of data information between the com-municating devices.

Description

1'~36S41'

- 2 - 4157-15~D

This invention is a divisional of Canadian application Serial No. 467,293 filed November 8, 1984 by Tandem Computer Incorporated.
The present invention relates to a communications system and method both of which use a pair of communications devices for communicating messages across a data channel.
A protocol which aids the transfer of data is intended to be used to effect delivery to a communicating device that may be executing higher level application programs. The messages trans-ferred between the communication devices include protocol control codes of the protocol and data. The protocol should be transparent to the higher level application programs which rely on the protocol and the communications devices so that unnecessary and excessive communication responsibilities are not that of the higher level application programs. Consequently, many application programs in~
clude their own high level protocol programs to effect the proper compilation of multiple messages transferred over the data channel.
The data portion of the message includes the higher level protocols and therefore is not a part of the protocol that is used to effect delivery between the communication devices.
The two communications devices which transmit data to each other must account for the nature of their communications channel. Many useful communications channels are error prone, that is,information can be lost or corrupted in the process of data transfer from one device to the other. Other useful quali~
ties of the data channels, such as their extreme speed or their relative inexpensiveness, may prompt the system designer ' ~

~3~S41

-3- 4157-158~

to use them anyway and to provide a mechanism which allows the communicating devices to transfer their data even when the data channel is error prone.
A proper solution to using an error-prone data channel is to provide a protocol for transferring the information within flow restrictions detecting errors and providing recovery from the errors. There are many such protocols used in the art. The protocols are tailored to a specific set of problems and to a specific data channel.
The degree of error to which the data channel is prone affects the efficiency and effectiveness of the protocol. Most protocols are concerned with data channels that are fairly likely to lose messages or to corrupt data in transit. Efficient use of the high speed capability of the data channel is important because the transfer rate affects the efficiency of a computer system.
Flow control is re~uired during data transfers between communicating devices. Data is lost if the amount of transferred data exceeds the capacity o~ the receiving communications device thereby degrading the effective transfer rate. Most protocols for high speed data channels assume a predetermined memory capacity.
Acknowled~ments are those protocol control codes that are used to signal a transmittiny device that the receiving device has received a message. These acknowledgment protocol control codes are well known in the art.

~;Z36S~

-4- 4157-15~B

Each particular control code, e.y., acknowledgment, has a specific meaning. Because a control code can have dif-ferent meanings depending upon the state of the communicating devices, a single meaning control code is inefficient. Multiple meaning control codes can have multiple purposes so as to reduce the number of communications required.
Piggy-backing, which is the combining of protocol control codes and data transferred in a single message, is well known in the art. The use of acknowledgment control codes in combination with data in a message, that is, the data and control codes are piggy-backed, has been used to avoid the transmission of a message merely to effectuate flow control.
To avoid memory capacity over-flow of a receiving device, flow control is necessary. The data flow to a receiving device must be at a rate such that the receiving memory capacity does not overflow and lose data. The use of separa-te acknow-ledgment protocol control codes within a message containing only the control code has been used in the prior art to effect flow control. The use o e acknowledgment messages without data for the sole purpose of flow control disadvantageously decreases the efficiency of the communicating devices over the data channel because two acknowledgments may be required. One acknowledges receipt of data and a second signals the ability to receive another message. These two messages can be replaced with a single message. This single message has both meanings.

~23659~

-5- ~157-15~D

Other types of communicating devices have used hold-off periods for flow control. The transmitting device will hold-off sending a data message until it has received an acknowledgment or has waited for a long time-out period. This time-out period is used to allow the receiving device sufficient time -to process the data it has received. The receiving device processes the data thereby emptying its memory capacity so that it can receive additional data. If the acknowledgment is not received at the end of the long time out period, an error condition is recognized.
The use of the hold-off period eliminates the need to send the acknowledgment immediately after receipt because no time-out error occurs until after the time-out perio`d. Consequently, the receiving device has until the expiration of ~he time-out period to acknowledge receipt of a message.
The hold-off with long time-outs, in combination with multiple meaning control codes piggy-backed with data, increases the efficiency of the communicating devices. A receiving device only sends the acknowledgment a~ter it has processed previously received data. This acknowledgment can be piggy-backed with a ~0 data message and the acknowledgment can mean that the receiving device received the previously transmitted message and is ready to receive another message. Consequently, there are a minimum number of messages required and this improves the efficiency of the communicating devices.

~;Z365~

-6- ~157-158D

SUMMAR~
It is an object of the present invention to provide an effective and efficient method of transferring data between two communications devices across a data channel which is prone to errors. Another object of the present invention is to provide an effective and efficient meth.od of transferring data within a minimum set of protocol control codes which are transparent to high level application programs that use high level application protocols.
The two communications devices are connected together by the data channel, an electronic link that allows for the transfer of data, in message form, between the two devices.
Messages include protocol control codes, which enable the communicating devices to detect communications errors.
The protocol requires that a receiving device acknow-ledge messages which it receives correctly; in this way, the sender is in~ormed that the message has in fact been received correctly. In addition, acknowledgment is used as a form of flow control, in that the sending device will not transmit a new message until ~cknowledgment of the current message has been received. If acknowledgment has not been received by the sender within a predetermined timeout period, the original message is retransmitted, and acknowledgment awaited again. Unlike some protocols, which may require both an acknowledgment to tell the sender that the previous message was correctly received, and another message, to tell the sender that the receiver is ready-to-receive once again, thi:s protocol uses a single acknowledgment to accomplish both functions.

65~

-7- 4157-158D

Acknowledgments and data may be combined in-to a single message when possible; this is known as piggy-backing, because the acknowledgment "rides piggy-back" on the data message. By this means, the number of messages which must be transmitted may be reduced. This is desirable, because the efficiency of the communicating devices and the channel that connects them is improved when fewer messages are required to provide both data transfer and flow control.
The two communicating devices are differentiated into a master device, which controls the data path, and a slave device.
The master may initiate data transfer to the slave when it wishes, and thereafter may continue to transfer data taking into account acknowledgments received from the slave. The slave may initiate data transfer to the master only when the master enables this activity by means of a protocol message.
The efficiency of the communication channel is markedly improved when acknowledgment messages are used to effect both acknowledgment oE correct receipt and flow control; the ef-iciency is improved further still by means o~ piygy-backing acknowledgments on data messages. Efficiency is further improved by using a minimum set of control codes.
Thus, a message sent can mean that the sending device is ready to receive additional information, that it acknowledges the prior transmitted message, ana that data is included with the acknowledgment.

~;23~;5~

-8- ~157-15~D

The invention may be summarized as a method for trans-ferring messages over an error-prone channel, comprising the steps of : transmitting messages which may comprise protocol codes and data; retransmitting each said message a predetermined number of times until said message is acknowledged by an acknow-ledgement code; moni:toring input memory capacity for each device which. may receive said messages; delaying said acknowledgm~t .~ code until said input memory capacity is sufficient to receive ` ` a new message; and delaying transmitting said new message~ until after said acknowledgment code is received.
The invention will now ~e described in greater detail with reference to the accompanying drawings, in which:
Figure 1 is a diagram wherein two communicating devices are shown.
Figure 2 depicts the hardware architecture of the communicating devices.
Figure 3 depicts the format of data within a message.
Figure ~ is a Elow diagram with memory elements used during the transfer of data of a communicating device~
Figure 5 is a state diagram of the master communicating device.
Figure 6 is a state diagram of a slave communicating device.

PREFERRED EMBODIMEMT
Referring to Figure 1, a communication system comprises a master device 10, a slave device 12, and a data channel ;S~l

-9- 4157-15~D

connecting them, comprised of an output (relative to the mas-ter device) link 14, and an input (also relat ve to the master device) link 16. The data channel allows for data to be trans-ferred between the master device 10 and slave device 12.
Referring to Figure 2, the master device 10 communi-cates with the slave device 12 over the output data link 14 and the input data link 16. The architecture of the master device

10 is similar to the slave device 12.
Both the master and slave device have a microprocessor;
18b and 18a respectively, ROM (read-only memory), 24b and 24a respectively, RAM (random access memory), 26b and 26a, respect-ively, and ports, 20b and 20a, respectively. The microporcessors 18 execute program code stored in both ROM 24 and RAM 26, and transfer data in and out of RAM 26 through data busses 28 by use of address busses 30.
The port 20a of the slave device 12 comprises an A~LC
(Advanced Data Link Controller) 21a and a DMAC (Direct Memory Access Controller) 21b; the port 20b of the master device 10 comprises a BSCC (Bit Synchronous Communications Controller) 22a, an RXFIFO (Receive FirsteIn First-Out) 22b, a TXFIFO
(Transmit First-In First Out) 22c, a receive line 22d and a transmit line 22e.
The hardware architecture of the slave device 12 is a conventional one and is well known in the art. The ADLC 21a may be an industry standard Motorola part number 6854, the ~MAC

~23~S9~

21b may be an lndustry standard Motorola device part number 6844, -the microprocessor 18a may be an industry standard Motorola device part number 6809. The RAM 24a and ROM 26a are also standard conventional components. All of these devices are configured in a conventional manner.
The architecture of the master device 10 is a conven-tional one. The port 20b of the master device 10 uses the BSCC
22a to communicate data; the TXFIFO 22c and RXFIFO 22b are used for data buffering during transmission and reception, respect-ively. The BSCC 22a may be an industry standard conventionalcomponent 2652. The TXFIFO 22c and RXFIFO 22b comprise conven-tional discrete components. The microporcessor 18b may be an industry standard Motorola part number 6809. The RAM 24b and ROM 26b are also standard conventional components. All of these devices are configured in a conventional manner.
~ eferring to Figure 3, a message 32 of data is encoded into a predetermined format including flag fields 34a and 34b whlch mark the beginning and end oi the message 32. A CRC
(cyclic redundancy check) 36 is generated by a polynomial as is well known in the art; the CRC 36 is used for error detection.
The address 38b is the address of the slave device 12 which is to receive the master device`s 10 messaye, or of the slave device which is sending the message. The code 38a contains the control codes of the protocol. I'he data field 40 contains data being transferred between communicating devices 10 and 12, and may include high level application data. High le~el applications ~23~5~1 ~ 4157-158D

do no-t process the code 38a, consequently these pro-tocol codes 38a are transparent, i.e., invlsible, to high level application programs.
Referring to Figure 2 and Figure 3, the address 38b, code 38a and data 40 are transferred through the BSCC 22a for the master device 10 or the ADLC 21a for the slave device 12.
When transmitting, -the BSCC 22a or ADLC 21a, for master device 10 or slave device 12 respectively, is responsible for generat-ing the leading flag 34a, CRC 36 and trailing flag 34b When receiving, the BSCC 22a or ADLC 21a, for master device 10 or slave device 12 respectively, is responsible for detecting -the leading flag 34a, CRC 36 and trailing flag 34b. This technique of generation and recognition is well known in the art.
Referring to Figure 2 and Figure 4, the RAM 26 and ROM 24 are used to store an operating system proyram 42, high level application proyrams 44 and I/O (input/output) driver proyram 46. The I/O driver program 46 works in conjunction with the operating svstem proyram 42 to implement the present communica-tions method.

The operating system program 42 controls the transfer of data between the RAM 26 and the port 20 of the devices In particular, in the slave device 12, the operating system program 42 enables the DMAC 21b to automatically transfer data to or from the RAM 26a from or to the ADLC 21a in a manner well known in the art. The data which is either read from or written to the RAM 26a comprises the address 38b, the code 38a and the data 40.

~123~5~

In the case of the master device 10, the operating system program 42 enables the transfer of data between the port 20b and the microporcessor 18b, and then the microporcessor 18b and the RAM 26b in a two-step process. In more detail, when data is being received by the master device 10 on link 16, data is routed through BSCC 22a, through receive line 22d! through temporary RXFIFO buffer 22b into the mircroprocessor 18b by the use of data bus 28b/ and then out of the microprocessor 18b by use of the data bus 28b to the RAM 26b where it is stored.
When data is being transmitted by the master device 10 over link 14, data is transferred from the RAM 26b by use of the data bus 28b, into the microporcessor 18b, and then from the micro-processor 18b by use of the data bus 28b through the temporary TXFIFO buffer 22c, through transmit line 22e and through the BSCC 22a onto link 14.
It should now become apparent that the operating system programs 42 are dif~erent in the master device 10 and the slave device 12 due to the differences in the hardware implementation of the two devices. It should also be apparent that the ports 20 are used to transfer data to or from the RAM
26, the principal difference between the master device la and the slave device 12 beingthe mode of transfer between ports 20 and RAM 26.
The high level application programs 44 are pro~rams that perform "user" tasks, i.e., functions that make use of the communications method herein described, but which are not ~236~

directly a part of that method. On the other hand, the operating system programs 42 and the I/O driver programs 46 provide the mechanism for the execution of, and communica-tions between, high level application programs 44 executed in the master device 10 and slave device 12.
For example, suppose that a high level application program 44 in the master device 10 requires transfer of data from itself to a high level application program 44 in the slave device 12. In this instance, the high level application proyram 44 in the master device 10 readies the data, the operating system program 42 causes the I/O driver program 46 to be execu-ted, which causes the data to be transferred through interaction with the operating system program 42. In a sense, the I/O driver program may be considered an extension of the operating system program 42. The operating system program 42 and the I/O ~river program 4~ in a particular device are used in common by one or more high level application programs 44 in that device.
The I/O driver program 46 comprises a decode program 48, a state machine program 50, a plurality of action routine programs 52a, 52b through 52n, and an encode program 54.
In a sense, the state machine program 50 is the "heart"
of the I/O driver program. The function of the state machine, when invoke, is to "map" the current state and the current event into an action and a new current state. The current event is stored in the current event segment 62 and the current state is stored in the current state segment 66. The state table segment ~36~
~ 4157-158D

64 contains, in effect, a table of tables. The current state segment 66 "selects" one of those tables, and the current event segment 62 "selects" an entry within that table. Each entry contains an action value, which is stored in the action value segment 68, and a next state value which replaces the current state segment 66. ~ext, the action value segment 68 is used to select and execute one of the action routine programs 52. The state machine program 50 in device 10 or 12 operates consist-ently with a state table stored in state table segment 64; the state table is one of the two represented in Figure 5 and Figure 6 for the master device 10 and the slave device 12, respectively.
Since the state diagrams are different, it is clear that the communication method of the present invention is asymmetrical.
The func-tion of the decode program 43 is to determine the current event, stoxe it into the current event segment 62 and invoke the state machine program 50. The I/O driver program ~6, and in particular, the decode program 48 i8 invoked by the operating system program 42 when a message 32 has been received, a transfer request has been made by a high level application program 44, or a timeout has occurred.
When a message 32 has been received, the opexating system program 42 sets the code 38a and the data 40 into the input control code segment 56 and the input data segment 58 respectively; the operating system program 42 also stores a value into the CRC flag segment 55, indicating whether or not the message was received without error within the constraints ~3~

of the CRC polynomial used by both the ADLC 21a and the BSCC 22a.
Finally, the operating system program invokes the I/O driver program 46 after setting the I/O driver wakeup segment 60 to a value indicating that a message has been received. The decode program then examines the CRC flag segment 55; if the CRC flay segment 56 indicates that the message was received with error, the input control code segment ~6 and the input data segment 58 are cleared, i.e., -the message is discarded, and the~state machine program is not invoked. If the message was received without error, the decode program 48 places a value into the current event segment 62 in accordance with the input control code segment 56 value, and then invokes the state machine program 5Q.
When a high level application program 44 makes a transfer request, the operating system program 42 invokes the I/O driver program 46 after setting the I/O driver wakeup segment 60 to a value indicating that a message is to ~e sent.
In this case, the decode program 48 determines if the curren-t state segment 66 indicates that a high level application program request may be processed at this time, that is, in the current state; if not, the request is saved for later processing, i.e., the decode program 48 does not place a value into the current event segment 62 and the state machine program 50 is not invoked.
Otherwise, the decode program 48 places a value into the current event segment ~2 indicating that there is a high level application program 44 request to be processed, and invokes the sta-te machine program 50. The action routine programs 52 which are invoked by ~3~S41 the state machine program 50 in these cases will in turn activate the encode program 54 which. causes the output control code segment 70 to be set in accordance with the type of message to be sent, and the output data segment 72 to the message data 40 to be transferred. Then the encode program 54 will cause the operating system program 42 to initiate the actual transfer to the port 20, which in turn will appropriately append flag ch.ar-acters- 34 and CRC 36 as described above.
The operating s~stem program 42 provides timing services or the I~O driver program 46 by use of a hardware l~real time clock" as: is well known in the art~ When the I/O
drivex is doin~ a timed operation, ;~t sets a timer count value into the timer count segment 59; each. time the clock "ticks", the operating system counts down the value in the timer count segment 59. When the value in the timer count segment 5g xeaches 0, the operating s~stem program ~2 invokes the I/O
driver program after placing a value meaning "timer expired"
into the I/O driver wakeup seyment 6Q. In turn, the decode program 48 places a value into the current event segment 62 indicating that the operation timer has expired and invokes the state machine program 50.
The state diagram of the master device 10 is shown in Figure 5 and the state diagram of the slave device 12 i5 shown in Figure 6. Each box in the diagram represents a state; the master device lQ has fi~teen states and the slave device 12 has nine states.

~;Z365~`
-17~ 4157-15~D

A device 10 or 12 transitions from state to state when the device lQ or 12 receives a message, has a message ~rom a high level application program 44 to transfer out or a timer time out occurs. Incoming messages, high level application program requests for transfer and timer time outs cause the operating system program 42 to invoke the I/O driver program 46, and in particular, the decode program 48. The states of each device 10 or 12 represent the states between successive I/O driver program 46 executions.
The present preferred embodiment uses eight protocol codes to guarantee delivery between communicating devices 10 and 12. Messages transferred may be referred to by the code therein.
The eight codes are as follows:
The WD (write data~ code is used by the master device 10 to transfer data to the slave device 12. The slave de~ice 12, upon receipt, places the code 38a into the input code segment 56 and the data 40 into its input data segment 58. ThereaEter, the operating system program 42 transfers the data 40 to a high level application program 44, thereby making the input control code segment 56 and the input data segment 58 available ~or -the next message from the master dev.ice 10.. Next the slave device 12 acknowledges the message by transmitting either a WAK (write acknowledge) ~lessage or a RDWAK (read data write acknowledge) message as described below.
The WAK (write acknowledgel code is used by th.e slave device 12 to acknowledge the receipt of a WD, REN or RENRAR

~6S~
-18- 4157-:L58D

message. The slave device 12 ~ill only send a WAK message after reading data out of the input data segment 5 8, so th.e WAK
message also informs the master device 10 that the slave device 12 is ready -to receive another message.
The REN (read enablel code is used by the master device 10 to enable the slave device 12 to send data~ The master device 10 will only send a REN message when its input data segment 58 is clear.
The RENRAK (read enable read acknowledge~ code i5 used by the master device la to enable the slave device 12 to send data and at at the same time ackno~ledge receipt of a prior RD or RDWAK message from the slave device 12. The master device ].0 will only send a RENRAK message after it has transferred the data in its input data segment 58 to a high level application program 42.
The RD (read data) code is used by the 5 lave devlce 12 to t:ransmit data to the mas-ter device 10. The slave device 12 may only transmit a RD message when it has been previously enabled by the master device 10 by means of a REN or RENRAK
message. The master device 10, upon receipt of the RD message, places the data portion 4Q in i.ts input data segment 58. There-after, the operating system program 42 of the master devi,ce 10 transfers the data 40 -to a high level application program 44, thereby making the input data segment 58 available for the next message from the slave device 12. Next, the master device 10 acknowledges the message by transmitting a RENRAK (.read enable i23654i -19- 4t57-158D

read acknowledge) message to the slave device 12 to acknowledge receipt of the RD message and enable the slave device 12 to send its next message.
The RDWAK (,read data write acknowledge) code combines the effect of the RD and WAK codes. The slave device 12 uses RDWAK message when it must acknowledge a WD, REN or RENRAK
message, the slave device 12 has been enabled to transmi.t the data ~as described for RD~ and the slave device 12 h,as data to transfer from a high level application program 44 to the master device 10.

The FLSH (~lush) code is transmitted by the master device 10 when resynchronizati,on wi.th the slave device 12 is required; conditions under wh.ich this may occur are described later. When the slave device 12 receives a FLSH message, it is supposed to respond with a FLAK ~flush acknowledgel message~
The FLAK (.flush,acknowledge) code is transmitted by the slave device 12 in response to a FLSH message ~rom the master device 10.

Thus, the master device 10 sends WD, REN, RENRAK and FLSH messages; whereas, the slave device 12 sends WAK, RD, RDWAK

and FLAK messages.
Each of the REN, RENRAK, WD, FLSH, RD and RDWAK
messages expect a response from the receiver of the message.
Since messages may be lost or corrupted in an error prone data , ~6S~l -20- 4157-158~

channel, the arrival of an expected response is timed by the sender of the message~ If the response is not received within that time, the message is retransmitted, the timer is restarted, and the response awaited again. The present protocol uses four timers.
Timer TREN (timer read enablel is the amount of time the master device 10 will wait for a WAK message from the slave device 12 in response to a REN or RENRAK message. It should be more than the normal time, including transmission delay, required for the slave device 12 to respond to a REN or RENRAK
message The actual value used for this timer is Q.5 seconds.
If the slave device 12 does not respond to the master device 10's REN or RENRAK message with a WAK or RDWAK message within the TREN time, then a TREN time out occurs.
Timer TWD (timer write data~ is -the amount of time the master device 10 will wait for a WAK message from the slave device 12 in response to a WD message, It should be more than the normal time, including transmission delay, required for the slave device 12 to respond to a WD message. The actual value used for this timer is 0.5 seconds. If the slave device 12 does not respond to WD message of the master device 10 with a WAK or RDWAK message within the TWD time, then a TWD time out occurs.
Timer TRD (timer read data) is the amount of time the slave device 12 will wait for a RENRAK message from the master device 10 in response to a RD or RDWAK message. It should be more than the normal time, including transmission delay, required ;5~

for the master device 10 to respond to a RD message. The actual value used for this timer is 3 seconds. I~ the master device 10 does not respond to a RD or RDWAK message of the slave device 12 with a RENRAK message ~ithin the TRD time, then a TRD time out occurs.
Timer TFLSH (timer flush) is the amount of time the master device 10 will wait for a FLAK message from the slave device 10 in response to a FLSH message. It should be more than the normal time, including transmission delay, required for the slave device 12 to respond to a FLSH message. The actual value used for this timer is 0.5 seconds. If the slave device 12 does not respond to a FLSH me5sage of the master device 10 with a FLAK message within the TFLSH time, then a TFLSH time out occurs.
When a timeout occurs, the sending device 10 or 12 will re-transmit the message as originally sent with the following exceptions: a RENRAK message will be re-transmitted as a REN
message and a RDW~K messaye will be retransmitted as a RD
message, in other words, a piggybacked acknowledgment will only be sent once. This is important, because in the event of a timeout, there is uncertainty on the part of the sending device as to the state of the receiving device.
Timeouts may occur to a number of different causes.
The receiving device may be defective, such that it either cannot correctly receive the arriving message or cannot correctly send the response. The data channel may have experienced a transient 65~

error condition or it may have ~ailed~ Finally, the receiving device may merely be too busy performing its other tasks to respond in a timely manner. Therefore it may be seen that in the case of a timeout cond~tion, there is uncertainty on -the part of the sending device as to the s-tate of the receiving device.
The more important cases are described as follows. A
sent message may have been corrupted when it arrived at the receiyer, ~n which. cas-e the receiver will treat it as not having arrived at all, Th.e receiver may h.ave correctly received th.e mes,sage, but th.e recei:ver's response may h.ave been damaged when it arrived at the sender, in which case the sender will treat the response as not having arrived at all, but the receiver will h.ave handled the message normally. Finally, the message and response may have been sent and received properly, except that the response arrives late reIative to its associated timer.
To illustrate why piggy-backed acknowledgments are not re-transmitted on a -timeout, consider the :eollowing. Suppose that the maste~ device 10 sends a RENRAK message -to the slave device 12, whlch. correctly receives the RENRAK message and trans-mits a W~K messa~e, which is then lost. Since the slave device 12 has been enabled to send RD message by the RENRAK message, it may subsequently send a RD message, and in particular, may send it before the master device l~ determines th.at a TREN timeout has occurred due to the lost W~K message response to the RENRAK mes-sage. Further suppose that the RD message is bein~ trans-lZ365~

ferred when the master device 10 determine that the TREN timeout has occurred. It would then send another RENRAK message which would be incorrectly treated by the slave device 12 as acknoW-ledgment to the RD message. Worse, if the RD message was also corrupted, the data ass.ociated with the RD mes~sage would be lost, because the slave device 12 would believe that the acknowledgment of the master device lQ to the RD message was received, and the slave device 12 would not re-transmit the RD message.
The possiblity of late arrival of a response from a slave device 12 may cause the following situation to occur.
Suppose that the master device 10 sends a RENRAK message to the slave device 12, which for some reason returns the WAK message response delayed past the TREN time, and the master device 10 therefore retransmits a REN message; the delayed WAK message response to the i.nitial RENRAK message is treated as the response to the re-transmitted REN message by the master device 10. Now suppose that the master device 10 sends a WD message to the slave device 12 before the slave device 12 can send the WAK message to the re-transmitted REN message; in this situation, the WAK

message of the slave device 12 which was the intended response to the re-transmitted REN message, will be treated by the master device lQ as an acknowledgment to th.e WD message instead. Thus, it may be seen that the meaning of a WAK message may be ambiguous in an out-of-synchronization situation such as the one described.
Because the late response situation is indistinguish-able at the master device 10 from the situations in which either ~Z3654~

-24~ ~157-158D

the message or the response is lost due to an erxor, the FLS~I
and FLAK messages are included in the current invention. In the event the master device 10 must re-transmit, when it finally receives a WAK (or RDWAK) message, it will send a FLSH message.
All WAK messages received from the slave device 12, between the time the FLSH message is sent and a FLAK message is received from the slave device 12, will be discarded. Since the slave device 12 will generate responses in the order in which it correc-tly receives messages, once the FLAK message has been received by the master device 10, the master device 10 and slave device 12 are re-synchronized and the master device 10 may once again safely send messages which require WAK (or RDWAK) responses. In the event that a FLSH message must be re-trans-mitted, and FLAK messages arrive late, i.e., when they are not expected, they are discarded by the master device 10.
If a message 32 is xe-transmitted a large number oE
times without receiving a correct acknowledgment, the sender of the messaye, either the master device 10 or the slave device 12 will treat the data channel consisting of the links 14 and 16 as failed. The preferred embodiment of the present invention uses five for this large number of times.
The master device 10 uses a state machine of fifteen states as shown in Figure 5. When power is initially supplied to the device, it starts operation in state 1. The master device 10 will transition through the state diagram in response 1;~3~

to messages received from the s:lave device 12, timeout condi-tions when awaiting responses, and high level application program 44 requests to initiate WD messages and enable RD
messages, until power is lost, or until a link failure condi-tion exists. Link failure will be deemed to have occurred when a large number of re-transmissions ~as defined above) have been attempted for FLSH messages (states 18, 11 and 13 of Figure 5), REN messages (state 7 of Figure 5~ or WD messages (states 9 and 10 of Figure 5).
The slave device 12 uses a state machine of nine states as shown in Figure 6; note that to simplify the drawing, handling of a FLSH, which may be received in any state from 1 to 8, is shown as a separate part of the diagram. When power is initially supplied to the slave device 12, it starts opera-tion in state 1. ~n a manner analogous to the master device 10, the slave device 12 will transi-tion through the state table in response to messages received from the master device 10, timeout conditions when awaiting responses, and high level application program 44 requests to initiate RD messages, until it loses power once again, or until a link failure condition exists. Link failure will be deemed to have occurred when a large number of re~transmissions (as defined above). have been attempted for RD messages (state 4 of Figure 6).
As stated, the master device 10 will follo~ (transi-tion through) the state diagram of Figure 5, while the slave device 12 will follow the state di.agram of Figure 6~ By this means, communicating devices may ensure the delivery of messages 1~2365~1 except when either the link (data channel) or one of the devices has failed. An example of part of the communications method is as follows:
Assume that both devices 10 and 12 are in state 1 of their respective state diagrams Figures 5 and 6, and the master device 10 sends a WD message and enters sta-te 5 of Figure 5. The slave device 12 receives the WD message and enters state 5 of Figure 6. The slave device 12 will send a WAK message and enter state 1 of Figure 6 when a high level application program 44 has received the data in the WD message. The master device 10 will receive the WAK message and enter state 1 of Figure 5.
As another example, cnce again assume that both devices 10 and 12 are in state 1 of their respective state diagrams Figures 5 and 6, and the master device 10 sends a RENRAK message and enters state 2 of Figure 5. The slave device 12 receives the RENRAK message and enters state 6 of Figure 6. If the slave device 12 does not have data ready to be sent at that time, it will ~end a WAK message and enter state 2 of Figure 6~ The master device 12 will receive the WAK message and enter state 3 of Figure 5.
With the slave device 12 in state 2 of Figure 6 and the master device 10 in state 3 of Figure 5, the slave device 12 may send a RD message and enter state 3 of Figure 6; on receipt of the RD message, the master device 10 enters state 1 of Figure 5.

lZ36S4~L

It should now become apparent that each device trans-mits four protocol control codes which can be encoded into two bits, and that the entire protocol comprises eight codes. In this manner of sending and receiving messages, the master device 10 and slave device 12 are able to guarantee transfer of messages unless a device lO or 12 or a link 14 or 16 has failed. It should also now be apparent that this method is both efficient, due to the small set of codes and the piggy-backing capability, and effective, due to the detection and handling of error conditions.

Claims (7)

THE EMBODIMENTS OF THE INVENTION IN WHICH AN EXCLUSIVE
PROPERTY OR PRIVILEGE IS CLAIMED ARE DEFINED AS FOLLOWS:

1. A method for transferring messages over an error-prone channel, comprising the steps of:
(a) transmitting messages which may comprise protocol codes and data;
(b) retransmitting each said message a predetermined number of times until said message is acknowledged by an acknowledgement code;
(c) monitoring input memory capacity for each device which may receive said messages;
(d) delaying said acknowledgement code until said input memory capacity is sufficient to receive a new message; and (e) delaying transmitting said new message until after.
said acknowledgement code is received.

2. The method of Claim 1, further comprising the steps of:
(a) monitoring input memory capacity for each device which may receive said acknowledgement codes;
(b) transmitting an enablement code when said input memory capacity is sufficient to receive a response message;
(c) including said enablement code as part of said message; and (d) including said acknowledgement code as part of said response message when said enablement code has been received.

3. The method of Claim 2, further comprising the step of:
(a) delaying retransmitting said message for a predeter-mined amount of time, unless said acknowledgement code is received.

4. The method of Claim 3, wherein said predetermined amount of time (a) is an amount TREN when said message contains an enablement code REN;
(b) is an amount TRD when said message contains both an enablement and acknowledgement code RENRAK; and (c) is an amount TWD when said message contains a data code WD.

5. The method of Claim 2, further comprising the steps of:
(a) transmitting a message FLSH to synchronize the protocol state between each device which may send said messages and each device which may receive said messages;
(b) transmitting a message FLAK to acknowledge said message FLSH, whenever said FLSH message is received.

6. The method of Claim 5, further comprising the steps of:
(a) delaying retransmitting said message FLSH for a predetermined amount of time TFLSH, unless said message FLAK is received.

7. The method of Claim 2, wherein said devices are divided into a class of master devices and a class of slave devices; whereby only said master devices may transmit enablement codes.