 |
Description  |
|
|
FIELD OF THE INVENTION
This invention relates to transfer of data between a master and a slave,
and more particularly relates to reduction of the acknowledgment message
traffic transmitted from the slave to the master.
BACKGROUND OF THE INVENTION
When a number of terminals access at least one slave computer using a
communications system, as for example, a Local Area Network (LAN) having a
communications protocol, total message traffic on the LAN may grow to
exceed the capacity of the LAN. Total message traffic on the LAN may be
particularly heavy when the terminals are small computers capable of
up-loading files to the slave, and also when the terminals are capable of
supporting a windows protocol. For example, a "mouse" input device is
usually supported by a windows protocol, and motion of the mouse may
generate a large number of messages to the slave (host) containing mouse
position information. Also, in a windows protocol a terminal occasionally
must transfer large amounts of data, for example the values of each pixel
in the screen display, to the slave computer. In any event, the LAN may be
overwhelmed by the amount of data being transferred from the terminal to
the slave computer.
Communications protocols frequently require that each message sent from the
terminal be acknowledged by the slave. The acknowledgment requirement is
instituted in order to keep track of messages which are corrupted by noise
on the communications circuits, or otherwise lost. A protocol having a
terminal server as a master and a host computer as a slave is disclosed in
U.S. Pat. No. 4,975,905, "Message Transmission Control Arrangement for
Node in Local Area Network", issued Dec. 4, 1990, to Mann, Duffy, Lauck,
and Strecker, and this protocol requires an acknowledgment by the slave to
the master.
As a consequence of the acknowledgment requirement, each message from the
terminal to the slave generates an acknowledgment message, and
additionally usually generates one or more further response messages
created by the slave in response to processing the received message.
Congestion on the LAN therefore arises not only from the messages sent by
the master to the slave computer, but also from the acknowledgment traffic
sent from the slave to the master.
Delayed acknowledgment protocols have been used in the past in order to
reduce ACK traffic on a local area network. However, a traditional
implementation of delayed acknowledgment, as for example described in the
textbook "Computer Networks" Second Edition, by A. S. Tanenbaum, published
by Prentice Hall, Englewood Cliffs, N.J., in 1988, at Section 4.4 "Sliding
Windows Protocol", pages 233-239, will not work optimally with a
master--slave protocol.
It is desirable for the slave computer to both acknowledge the receipt of
message packets from the master, and to reduce the number of messages
carried by the local area network.
SUMMARY OF THE INVENTION
The slave computer acknowledges messages from the master and also reduces
the number of acknowledgment messages transmitted on the local area
network by use of a delay acknowledgment protocol.
There is provided an apparatus for communicating between a master and a
slave computer. A computer communications system has a means for
controlling a master with a circuit timer, the circuit timer is capable of
aggregating data produced during a circuit timer interval into a single
master message, and the data is produced by a plurality of users, where
each user is capable of establishing a plurality of sessions. There is a
means, responsive to expiration of the circuit timer interval, for sending
the aggregated data to a slave. Also there is a means for the slave to
send an acknowledge message to the master upon expiration of a delay ACK
time interval, the delay ACK time interval is greater than the circuit
timer interval, and the circuit timer is capable of initiating sending of
a plurality of master messages during one delay ACK time interval.
Further, there is a means, responsive to receipt of the plurality of
master messages, for the slave to acknowledge the plurality of master
messages in one aggregated acknowledge message.
The apparatus has a means for the master to send a message packet to the
slave computer; a means for the slave computer to send an acknowledgment
to the master, the acknowledgment capable of indicating that the message
packet was received by the slave computer; a means for the master and the
slave computer to select a delay ACK time interval; and, a means for the
slave computer to delay sending the acknowledgment to the master by a time
interval of the delay ACK time interval. Also the apparatus has a means
for the master to override the means for the slave computer to delay
sending the acknowledgment by setting a response requested flag in a
message, and in response to receiving the message with the response
requested flag set the slave computer sends an acknowledgment to the
master without delay.
Also the apparatus has a means for the master to send a plurality of
messages to the slave computer without receiving an acknowledgment; and, a
means for the slave computer to delay sending a group acknowledgment that
at least a first group of the plurality of messages were received, where
the slave computer delays by a time interval of the delay ACK time
interval in sending the group acknowledgment.
The apparatus also has a means for the master to send a proposed delay ACK
time interval to the slave computer; and, means for the slave computer to
accept the proposed delay ACK time interval. The means for the slave
computer to accept the proposed delay ACK time interval is for the slave
computer to transmit a RUN message. Also, the slave computer may reject
using a delay ACK time interval.
Further, the apparatus has a means for the master to send a proposed delay
ACK time interval to the slave computer; a means for the slave computer to
propose an alternative delay ACK time interval; and, a means for the
master to accept the alternative delay ACK time interval. The means for
the master to accept the proposed alternative delay ACK time interval is
for the master to send a RUN message to the slave computer. Alternatively,
the master may reject the proposed alternative delay ACK time interval.
Other and further aspects of the present invention will become apparent
during the course of the following description and by reference to the
accompanying drawings.
BRIEF DESCRIPTION OF THE DRAWINGS
Referring now to the drawings, in which like numerals represent like parts
in the several drawings:
FIG. 1 is a block diagram of a communications system in accordance with the
present invention.
FIG. 2 is a field diagram of a message in accordance with the present
invention.
FIG. 3 is a field diagram of a message header of the message shown in FIG.
2.
FIG. 4 is a field diagram of a Message Specification field shown in FIG. 3.
FIG. 5 is a START message field diagram in accordance with the invention.
FIG. 6 is a protocol timing diagram in accordance with the present
invention.
FIG. 7 is a is a protocol timing diagram used in the prior art.
FIG. 8 is a field diagram of a START slot message,
FIG. 9 is a field diagram of a DATA slot message,
FIG. 10 is a protocol timing diagram in accordance with the invention.
DETAILED DESCRIPTION
Referring now to FIG. 1, there is shown generally communication system 100.
Communications pathway 110 provides a communications pathway for computers
and associated equipment connected to the communication system 100. For
example, communications pathway 110 may be an Ethernet CSMA/CD local area
network. Alternatively, communications pathway 110 may be any convenient
local area network such as those defined under IEEE 802 local area network
standards.
In FIG. 1, the following representative equipment is connected to
communications pathway 110, master 120, high speed terminal 122 with
keyboard 124, high-speed terminal 126 with keyboard 128, and master 130.
Dots 121 and dots 131 indicate that a further plurality of masters may be
connected to communications pathway 110. Also mouse 125 provides input to
high-speed terminal 122, and each position increment of the mouse may
generate a data message on communications pathway 110.
Master 120 provides a fan-in for terminal 140, personal computer 142, and
printer 144. Dots 146 indicate that a plurality of additional units may be
connected through master 120 to communications pathway 110.
High-speed terminal 122 and high-speed terminal 126 are connected as
individual masters to communications pathway 110. For example, high-speed
terminals 122 and 126 may use a windows protocol. In a windows protocol a
terminal may be required to transfer large quantities of data from the
terminals onto the communications pathway 110. For example, the terminal
may be required to send a full screen display, with a plurality of bits
for each pixel, to a slave computer.
Master 130 serves as a fan-in connection for a number of individual units,
as shown, for example, in FIG. 1. The individual units comprise a printer
150, a terminal 152, a workstation 154, and another printer 156. Dots 158
indicate that a further plurality of devices may be connected through
master 130 to communications pathway 110.
Also connected to communications pathway 110 are slave computers 160, 162,
164, and 166. Dots 168 and dots 170 indicate that a further plurality of
slave computers may be connected to communications pathway 110.
The slave computers, slave computer 160, 162, 164, 166, may operate using a
variety of operating systems. For example, slave computer 162, 164 are
shown connected through hub 180 as a cluster of computers. Also connected
to hub 180 are various mass storage devices such as tape drive 182, disk
drive 184, disk drive 186, and tape drive 188. For example, slave
computers 160, 162, 164 may operate using the VMS operating system sold by
Digital Equipment Corporation. Slave computer 166, may for example, use a
UNIX operating system. As a further example, slave computer 166 may use an
IBM operating system.
Master 120, in an exemplary embodiment, may be referred to as a server.
Slave device 160, in an exemplary embodiment, may be referred to as a host
computer. For example, master 120 may be an Ethernet server,
communications pathway 110 may be an Ethernet local area network, and
slave computer 160, 162, etc. may each be a VAX computer, all manufactured
by Digital Equipment Corporation.
Personal computer 142 may use a Microsoft MS-DOS operating system. Also, as
a further example, personal computer 142 may use an Apple operating
system, as for example, personal computer 142 may be a Macintosh personal
computer.
Terminals 140, 152, may, for example, be "dumb" terminals, of a type not
having stand alone processing capability. Printers 144, 150, and 156 may,
for example, be printers utilized by the various terminals connected to
the communications pathway 110, and may print queues developed by any of
the terminals or personal computers connected to communications pathway
110 through the slave computers 160, 162, 164, 166. Further, high speed
terminals 122 and 126 may be workstations requiring a large band-width.
For example, the band-width normally required by a personal computer 142,
154 is frequently sufficiently small that such a device may be multiplexed
using master 120, 130 for its connection to communications pathway 110. In
contrast, high speed terminals 122, 126 may require a much larger
band-width because of large data transfers, for example, generated by
operation of a windows protocol on the terminals, and so require a direct
master connection to the communications pathway 110.
Referring now to FIG. 2, there is shown a typical message format for use by
communications pathway 110 in communicating information between masters
120, 122, 126, 130 and slave computers 160, 162, 164, 166. Message packet
200 has a Message Header field 202, a user data slot 204, and another user
data slot 206. Dots 208 indicate the possibility of a further plurality of
user data slots in message 200. User data slots 204, 206, 208 are optional
in the message 200. A message may comprise a Message Header field 202
only, for management purposes for communication system 100. Examples of
management purposes are the transmission of an acknowledgment message, the
transmission of a START message, the transmission of a STOP message, and
other management type operations.
Message packet 200 has cyclic redundancy check data (CRC) in field 209 at
the end of the packet. For any packet length, CRC data is contained in
field 209. For example, in an Ethernet embodiment, CRC field 209 may be
four bytes long. CRC field 209 provides data for a receiving station to
test an incoming message packet, where the test is to determine if the
bits making up the packet meet a criterion for successful transmission. In
a receiving station, the sequence of events is: first the station detects
that the incoming message packet is addressed to the receiving station;
then the station performs a CRC test on the incoming packet; and if the
packet passes the CRC test, then the station receives the packet. In the
event that the packet fails the CRC test, then the receiving station
simply discards the incoming packet and does not receive the incoming
packet.
Capitalization, as follows, will be used in this document in order to
improve the readability of the document. Message field names will have the
initial letter of a word capitalized. Values of logical variables, such as
SET and CLEAR will be fully capitalized. Also, specific message
designations such as START, RUN, and STOP will be fully capitalized.
Referring now to FIG. 3, there is shown a field diagram for a Message
Header field 202. Fields of Message Header field 202 comprise the
following: Destination Address field 210; Source Address field 212;
Protocol Type field 214; Number of Slots field 216; Message Specification
field 218; Destination Circuit Identification field 220; Source Circuit
Identification field 222; Acknowledge field 224; and Acknowledge Sequence
Number field 226. Destination Address field 210 gives the data link
destination address of the receiving station. Source Address field 212
gives the data link address of the transmitting station. By the term
"station", there is meant a computer, master or slave, connected to
communications pathway 110, and capable of sending or receiving messages
from data pathway 110. An example of stations are masters 120, 122, 126
and 130. Further examples of stations are slave computers 160, 162, 164
and 166. Protocol Type field 214 contains bits that represent the type of
protocol utilized by message 200. For example, Destination Address field
210, Source Address field 212, and Protocol Type field 214 may be defined
by a standard communications system 100 definition. For example, fields
210, 212, 214 may be defined as an Ethernet header.
The contents of Protocol Type field 214 may, for example, indicate to a
receiving station the protocol of the received message is a message
transmission control protocol of the type further discussed hereinbelow,
or as, for example, disclosed in U.S. Pat. No. 4,975,905 disclosed
hereinabove. Number of slots field 216 gives the number of user data slots
204, 206, 208 appended after Message Header field 202. Message
Specification field 218 is further described hereinbelow in reference to
FIG. 4.
Destination Circuit Identification field 220 is a virtual circuit
identification utilized by the receiving station in setting up a virtual
circuit for communication on communications pathway 110. Source Circuit
Identification field 222 gives an identification number for the virtual
circuit identified by the transmitting station for the communications
session set up on communications pathway 110.
Acknowledge field 224 gives the sequence number of the last "in sequence"
message packet received with a valid cyclic redundancy check. An "in
sequence" message packet is a packet where it, and all earlier packets,
had valid cyclic redundancy checks. Acknowledge Sequence number field 226
gives the sequence number of the present message packet 200.
Referring now to FIG. 4, there is shown a field diagram of Message
Specification field 218. Message Type field 230 contains a flag showing
whether the message is a START message; a RUN message; or a STOP message.
Master Bit field 232 indicates, if the bit is SET, that the message is
from a "master" station. The bit in Master Bit field 232, if "CLEAR",
indicates that message 200 was transmitted by a slave station.
In the event that in a message 200 the Response Requested bit 234 is SET,
the SET bit pattern indicates that the transmitting station requires an
immediate acknowledgment of receipt of the message 200. In an exemplary
embodiment of the invention, the field 234 contains only one bit, called
the Response Requested bit. In the event that a master station transmits a
message 200 with the Response Requested bit 234 CLEAR, then the CLEAR bit
indicates that a delayed acknowledgment to receipt of message 200 is
satisfactory for the transmitting master station. In the event that a
slave station transmits a message 200 with the Response Requested bit
CLEAR, then in some protocols the master does not transmit an
acknowledgment.
Referring now to FIG. 5, there is shown START message 240. START message
240 has Message Header field 202. When Message Type field 230 indicates
that the message is a START message, then the message packet takes the
field form of START message 240. START message 240, in addition to Message
Header field 202, has the following fields: Parameter Code 242; Length
field 244; and Delay Acknowledge Value field 246, and Termination field
247.
Parameter Code field 242 may, for example, be one byte in length. Parameter
Code field 242 has the following meanings: in the event, in a preferred
embodiment of the invention, that Parameter Code field 242 contains eight
bits, all set to zero, then the START message 240 contains no further
fields; and, in the event, in a preferred embodiment of the invention,
that Parameter Code field 242 has a designated bit set to ONE, then the
START message 240 contains Length Field 244 and Delay Acknowledge Value
field 246. Alternatively, there can be a sequence of parameter values,
where the sequence is terminated by Termination field 247 containing, for
example, a zero "0", or null. Fields 242, 244, 246, 247 may each be coded
as one byte, or for example, as an eight bit integer. Alternatively, a bit
mask could be used to code the fields. START message 240 may be terminated
by a Termination field 247 containing a zero or null.
Length field 244 may, for example in a preferred embodiment of the
invention, designate the number of bytes in the length of Delay
Acknowledge Value field 246.
For example, Length field 244 may be contain a "2", indicating that Delay
Acknowledge Value field 246 is two bytes in length.
Delay Acknowledge Value field 246, in a preferred embodiment of the
invention, contains a number representing the amount of delay, in units of
ten milliseconds, that an acknowledgment may be delayed by a receiving
station. The protocol of delayed acknowledgment will be further described
hereinbelow.
Referring now to FIG. 6, there is shown a message protocol timing diagram.
A master station 250 is indicated on the left of the diagram, and slave
station 252 is indicated on the right of the diagram. For example, the
communications protocol utilized for transferring messages between masters
120, 122, 126, 130 on the communications pathway 110 to slaves 160, 162,
164, 166 may be an asymmetric protocol where one class of stations is a
"master" station, and the other class of stations is "slave" station. For
example, in a preferred embodiment of the invention, for the purpose of
the communications protocol, the master stations 120, 122, 126, 130 are
master stations. The computer stations 160, 162, 164, 166 are slave
stations.
Master stations may be distinguished from slave stations by, for example,
master stations being the only stations usually permitted to initiate a
communications activity onto communications pathway 110, where slave
stations usually only respond to initiated activity by the master station.
Further, master stations may operate with a transmission timer, requiring
a specified delay time between transmissions. In contrast, a slave station
may be required to transmit information, as soon as it is prepared into
form for transmission.
"Start up and Run" sequence 254, is shown in FIG. 6. START message 260 is
transmitted, at time 253A, from master station 250, for example, a master
120, 122, 126, 130, to a slave station 252, for example, slave computer
160, 162, 164, 166. START message 260 may optionally include a request for
the slave station 252 to practice delayed acknowledgment in accordance
with the present invention. In the event that master station 250 requests
that slave station 252 practice delayed acknowledgment, then Parameter
Code field 242 will have the designated bit SET, indicating that delayed
acknowledgment is requested. Other fields of START message 260 will
contain the following: Message Specification field 218, will contain in
Message Type field 230 and indication that START message 260 is a START
message; the bit in Master Bit field 232 will be SET, indicating that the
message is from a master station; and, Parameter Code field 242, as shown
in FIG. 5, will have a designated bit SET; length field 244 will contain
"2"; and Delay Acknowledge Value field 246 will contain a suggested value
for a delayed acknowledge timer in the receiving slave station, where the
receiving slave station is designated by Destination Address field 210. In
an exemplary embodiment of the invention it has been found satisfactory to
code various fields as eight bit integers.
The receiving slave station may negotiate an alternate value for the value
of the delayed acknowledge timer, as described hereinbelow.
The receiving slave station 252, at a later time 253B as shown in FIG. 6,
transmits START message 262, where the Destination Address field 210 of
START message 262 contains the data link address of the initiating master
station 250. START message 262 has the field structure of START message
240, FIG. 5. In the event that receiving slave station 252 has the ability
to support delayed acknowledgment, then START message 240 will have the
fields: Parameter Code field 242 will have a designated bit SET; Length
field 244 of START message 262 will have the value of "2"; and, Delay
Acknowledge Value field 246 will have a value suggested by slave station
252 for the delayed acknowledge timer to be used by slave station 252.
Slave station 252 may suggest a delay time in Delayed Acknowledge Value
field 246 of START message 262 which is the same as the value transmitted
by master station 250 in START message 260, or alternatively, slave
station 252 may suggest a different value for the delay timer. In the
event that slave station 252 is not capable of supporting delayed
acknowledgment, START message 262 will indicate this fact, by for example,
having a zero value in Delay Ack field 246, or by for example, following
Message Header field 202 by Termination field 247.
A reason for a slave station 252 suggesting a different value for the
delayed acknowledgment timer than the one received in START message 260
may be found in different timer granularity between the master and the
slave stations. Both the master and the slave utilize a clock having a
certain granularity, where that granularity may be normally expressed in
terms of milliseconds.
That is, granularity of the computer timer in slave computers 160, 162,
164, 166 may each be different, and may each be different from the
granularity of the timer of the initiating master station, for example,
master station 120, or master station 122, or master station 126, or
master station 130, and so forth.
For example, the master may be operating under a VMS operating system, as
supplied by Digital Equipment Corporation. The slave computer may be
operating under a UNIX operating system, and have a totally different
clocking structure from the master 120. Further, slave computer 164, for
example, may be a Cray super computer, or it may be an IBM main frame
computer, or it may be VAX Computer manufactured by Digital Equipment
Corporation, or it may be a MicroVax Computer, manufactured by Digital
Equipment Corporation, or it may be any of a number of other types of
computers. Accordingly, it is reasonable to expect that the time
granularity in a master 120, 122, 126, 130 will differ from the time
granularity in a slave computer 160, 162, 164, 166.
Upon receipt of START message 262 by master station 250, for example,
master 120, 122, 126, 130, master station 250 decides whether or not it
can support the delayed acknowledgment timer value contained in START
message 262 at Delay Acknowledge Value field 246. In the event that master
station 250 decides that the delayed acknowledgment timer value contained
in START message 262 at Delayed Acknowledge Value field 246 is acceptable,
then master station 250 transmits a RUN message 264. RUN message 264 has
the form of message 200, where Message Header field 202, at Message
Specification field 218, at Message Type field 230 indicates that the
message is a RUN message. For example, Message Type field 230 may contain
a zero, "0" to indicate a RUN message. The RUN message 264, at Number of
Slots field 216 may indicate user data slots containing data, or may
optionally have the value "0" to indicate that the RUN message 264
contains no user data slots 204, 206, 208.
In the event that master station 250 decides that the delayed
acknowledgment | | |
