US 4,658,250 AGrant
Computer Network Operating Method and Apparatus for Detecting and Exploiting Data Collisions to Merge Read Transactions
Issue Date:1987-04-14
•17 Claims
•7 Drawing Sheets
Abstract
In a computer network including a plurality of processors coupled to a data bus, ones of the processors contending for the data bus to output data requests each output priority byes of their transmission header packets as a series of data bits. Every contending processor sequentially reads data present on the data bus. Each processor that reads a "one" on the bus corresponding to a "zero" output by that processor interprets this as a data collision yields the bus for data transmission purposes, but continues to read all data appearing on the data bus and compares it with corresponding bits of its own transmission header packet. Only the processor having highest priority detects no data collision, and continues to output its data request. If any other contending processor determines that the data request of the highest priority processor is identical or sufficiently similar to its own, it merges its request with that of the highest priority processor by reading the resulting data, thereby reducing waiting time especially in file-intensive operations.
Metadata
Inventors
- Douglas G. Nering
- James L. Bucanek
Application Information
Application Number:US 6210708
Filing Date:1984-06-15
Priority Date:1984-06-15
Art Unit:264
Classifications
IPC:
H04Q 900
Field of Search:
340370825.5;825.05;825.5185;94
Patent Drawings (7 sheets)
Description
Background of the Invention
The invention relates to computer networks, and especially to methods and apparatus for reducing the amounts of time that the various processors connected to the network have to spend waiting for access to the data bus and to various peripheral devices attached thereto.
As personal computers have decreased in price and increased in data processing capability, they have become widely used to meet the needs of serious professional, business, and educational users. In order to use low cost personal computers in such professional, business, and educational environments, computer networks have been used to link personal computers in a multi-user, multi-function system that shares mass storage, communication facilities and printers and yet allows each individual user to have his own work station. Such local networks typically include use of high bandwidth transmission cables for communication over rather long distances without significant deterioration of signals, as typified by the ERTHERNET system, where the host processors all listen to one data bus into which they transmit their messages, one host at a time. Another local network topology is typified by the RINGNET system in which all of the processors are connected directly to their immediately adjacent neighbors. In local networks such as the ETHERNET, more than one processor may attempt to transmit whenever the data bus is not busy, and as a result, "collision" of data signals occurs on the bus data. Such a data collision is detected by special analog circuitry associated with each processor, and when such a data collision is detected, it is considered to be "fatal". Each contending processor then "backs off" for a random amount of time before attempting to transmit again. When relatively few processors connected to the local network attempt to gain access to the data bus, access can be gained almost immediately. However, when "traffic" on the data bus is heavy, a great deal of time may be wasted retrying to avoid collisions, thereby increasing the average transmission delay and decreasing system throughout. For more background, see "Computer Networks" by Andrew S. Tanenbaum. Also see the article "Distributed Broadcast Channel Access" by A. K. Mok and Steve Ward, Computer Networks 3 (1979) pages 327-335.
The foregoing Mok and Ward article suggests a computer network system in which, at the end of a data transmission, each of the processors waiting for access to the bus has a distinct priority which is encoded in a binary representation. Each bus transmits its encoded priority onto the data bus. Conductors of the data bus are logically ORed. Each processor reads the information on the data bus and compares that information with its own priority. Because of the wire ORed gating configuration of the data bus, the logical "ones" override logical "zeros", and the priority code of the highest priority contending processor is the priority code that will appear on the data bus. The "losing" processors all recognize this and withdraw. The "winning" (i.e., highest priority) processor now has control of the data bus and continues its transmission. Each losing processor increments its priority code and the winning processor resets its priority code to the lowest priority level, resulting in roughly "linear" waiting times. This bus conflict resolution scheme avoids the long waiting period that can result in other local networking bus conflict resolution techniques if traffic is heavy on the bus.
However, in local network systems, many of the transactions are for the purpose of retrieving files from mass storage. These are very time-consuming operations frequently involving considerable "overhead" delay for search and location of data, and transmission of a great deal of data along the data bus, therefore resulting in very long waiting times if the bus traffic is heavy. It would be desirable to have a technique that, on the average, reduces the waiting times in local networks wherein transactions are file-intensive and there is a great deal of contention for the data bus.
Accordingly, it is an object of the invention to provide an improved computing method and apparatus for reducing the amount of waiting that individual processors connected to the network must undergo in order to obtain access to the data bus and/or associated storage devices and/or associated peripheral devices.
It is another object of the invention to provide an improved local computer networking method and apparatus which is very inexpensive and reduces the waiting times for access to the bus.
It is another object of the invention to provide a computer networking apparatus and method which allows processors that fail to gain access to the bus during a particular bus arbitration transaction to continue to monitor the data bus and obtain the benefit of information transmitted by the winning processor.
It is another object of the invention to provide a local computer networking apparatus and method which provides increased data management flexibility and reduced average waiting times for processors to gain access to the data bus at times when there is a high level of contention for the data bus.
Most, if not all of the known local computer networking systems are either very expensive systems requiring expensive wiring and bus arbitration circuitry, or else they are very slow systems which have limited performance capability.
Accordingly, it is an object of the invention to provide an improved local computer networking apparatus and method which provides both very low cost to the user and yet improves the data throughput rate over the minimum cost, minimum performance systems that are presently available.
Summary of the Invention
Briefly described and in accordance with one embodiment thereof, the invention provides a computer network apparatus and method for resolving bus contention conflicts by causing each processor needing to transmit a request to initially transmit a priority code onto a "wire-ORed type" of data bus, wherein each processor connected to the network is coupled in a logically ORed fashion to the bus, and by causing each contending processor to read each data item on the bus before any processor transmits more data on the bus, to compare the data read on the bus with the data transmitted by that processor on the bus, to determine if there has been a "data collision" of its output priority data with the priority data then actually appearing on the bus and, if that processor detects a data collision, then to go into a passive mode wherein that processor continues to read data on the bus conductor and compare the read data with corresponding portions of its own request to determine if its own request is mergeable with the request of the "winning" or highest priority processor.
In the described embodiment of the invention the data bus includes only one bi-directional conductor on which priority data, transaction request data, command data and other data is conducted in serial format. The network includes a "busy" signal conductor for indicating when a transaction is taking place on the data bus and a pair of "handshaking" conductors for indicating the level of a ready signal and an acknowledge signal. The ready signal indicates when data on the data bus is to be interpreted as valid. The acknowledge signal indicates when all processors that are contending for access to the data line are in a passive "bus monitoring mode" have read the valid data bit presently on the data bus. The data bus, busy, ready and acknowledge signal conductors each are connected or coupled to all processors in the computer network in a "wire ORed fashion" so that any processor can output a logical "one" level to a respective one of those conductors and if no other processor is pulling a particular one of these conductors to a logical "zero" level, a logical "one" will appear on that conductor. (Those skilled in the art recognize that the concept of logically ORing can apply to eigher positive or negative logic level definitions, and the term "logically ORed" as used herein encompasses either the positive or negative logic definitions. For example, for positive logic definitions, the logical OR of A and B is a "1" if either of them is a "1", and for negative logic definitions, the logical OR of A and B is a "0" if either of them is a "0".
Initially, when the busy (bus busy) signal indicates that the data bus is now available because no transaction is presently occurring on it, all local processors (i.e., processors coupled to the data bus, bus busy and handshaking conductors) waiting or "contending" for a turn to transmit requests via the data bus then transmit a transmission header packet of data that includes a binary priority code and several other codes including a source address which is the address of that processor, a destination address which is the address of the destination of the request that the processor needs to send, and a control block that specifies the transaction requested by that processor (including the needed operating system for that transaction). Each processor waiting to transmit on the data bus applies a logical "zero" to the ready signal conductor, and after a suitable delay, each receiving processor applies a logical "zero" to the acknowledge signal conductor. Each contending processor then outputs the most significant bit of its priority code onto the data bus. If any of the contending processors outputs, a logical "zero" a logical "zero" appears on the "wire ORed" data bus, but if all contending processors output a logical "one", a logical "one" then appears on the data bus. After all of the contending processors have output the most significant bits of their respective priority codes on the data bus, the last processor to do so releases the wire ORed ready signal conductor, which then goes to a logical "one" to indicate that the data presently on the data bus now can be considered to be valid. In response to this, each contending processor then reads the data presently on the data bus and then compares that data with the data which that processor last output onto the data bus. If the data presently on the data bus is identical to the data last output by that processor, that processor remains eligible to transmit another bit on the data bus. However, if the data presently on the data bus and read by the subject processor is not identical to that which the subject processor last output onto the data bus, then this mismatch is interpreted by the subject processor as a "data collision", and the subject processor does not have the highest priority code of any of the contending processors. The subject processor therefore is a "losing" processor in that it is no longer eligible to transmit another bit on the data bus. However, each losing processor continues to read and acknowledge in accordance with the handshaking procedure.
The foregoing procedure is repeated until all bits of the priority code have been transmitted on the data bus. At this point, only one of the contending processors, namely the one having the priority code with the highest binary value, has detected no data collisions and hence, remains eligible to transmit further bits of data on the data bus; that processor is the "winning" processor, and all of the remaining contending processors are "losing" processors. The winning processor continues to transmit the rest of its transmission header packet onto the data bus in accordance with the foregoing handshaking procedure. All losing processors, at least initially, go into a "passive" mode wherein they continue to read valid data output onto the data bus by the winning processor and compare that data with their own respective requests as long as the request transmitted by the winning processor is identical to the request of each particular losing processor. Such a losing processor continues its read and compare process to thereby determine if the data being requested by the winning processor includes the data specified by the request of that losing processor. If a particular losing processor determines that the data request by the winning processor is identical to or contains the data requested by that losing processor, that losing processor makes a determination that its request can be "merged" with the request of the winning processor. However, any time that a losing processor determines that its request cannot be merged with the request of the winning processor, that losing processor stops reading the data appearing on the data bus. The winning processor resets its priority code to a low value or otherwise adjusts its priority code in accordance with a suitable priority subroutine. (For example, the winning processor may execute a priority subroutine that allows it to maintain its high priority for a particular amount of computer time, so that it does not have to go to the "back of the line" each time it gains access to the data bus for a very short transaction). Each losing processor increments its priority code or otherwise adjusts its priority code. Each losing processor that succeeds in merging its request with the request transmitted by the winning processor resets its priority to a low value or otherwise adjusts its priority in accordance with a suitable priority subroutine. Each losing processor that merges its request with the request of the winning processor either determines that its request is identical to that of the winning processor or that the data requested by the losing processor is a subset of the data requested by the winning processor. In the latter case, that losing processor rejects the portion of the data appearing on the data bus in response to the request of the winning processor that is not within the subset defined by the losing processor's request.
In the described embodiments of the invention, all processors connected as local processors of the computer network execute the same software subroutines to effectuate the foregoing collision detection and passive bus monitoring and execute comparison operations. In one preferred described embodiment, all processors connected to the network have connected thereto a printed circuit interface circuit board that facilitates decoding and recognition of addresses received on the data bus and comparison of data appearing on the data bus which the priority code of that processor's request, for indicating data collision detection, and for effectuating the handshake synchronization of read and write operations. In another embodiment of the invention, most of the functions of the above interface circuit are performed by a software program. The advantages of the interface circuit is greatly increased operating speed.
The method and apparatus of the invention greatly reduce the amount of waiting time for each local processor in high traffic, file intensive local computer networks at a very low cost.
Brief Description of the Drawings
FIG. 1 is a block diagram of circuitry that can be used in conjunction with each processor connected to a local computer network of the present invention.
FIG. 2 is a schematic diagram illustrating a typical layout in a building of a local computer network.
FIG. 3A is a signal diagram useful in explaining the operation of the invention.
FIG. 3B is a diagram illustrating the configuration of the transmission header packet output onto the data bus by each contending local processor in the computer network of FIG. 2.
FIGS. 4A-4D are program flow charts of subroutines executed by each of the local processors in the network shown in FIG. 2.
FIGS. 5A-5C etc. constitute a detailed block diagram of the circuit shown in FIG. 1.
Description of the Invention
Referring now to FIG. 2, reference numeral 1 generally designates a local computer network, i.e., a plurality of separate but interconnected computers. Hereinafter, local computer network 1 will be referred to as a "local network". Local network 1 is located within a building 3 having a number of different rooms as indicated by dotted lines. A plurality of local processors 4, 5 and 6 etc. are all connected to a common bus 8.
In the presently described embodiments of the invention, bus 8 includes four conductors indicated by reference numeral 8 in FIG. 1. More specifically, bus 8 includes a single bidirectional serial data bus conductor 8-1, a Busy signal conductor 8-2, a Ready (RDY) signal conductor 8-3, and an Acknowledge (ACK) signal conductor 8-4.
Perhaps understanding of the present invention can be best facilitated by first describing the signals that appear on the four conductors of bus 8. A timing diagram that explains the basic operation of the local network 1 is shown in FIG. 3A. Referring now to FIG. 3A, the data signals appearing on serial data bus 8-1 are designated by reference numeral 10 to indicate when data states change on the data lines 10 and when they are held steady. (The logic level definitions of "1" and "0" are arbitrary at this point in the description.) Busy signal conductor 8.2 is designated by reference numeral 11 in FIG. 3A. A high voltage signal as indicated by level 11-1 represents the condition that the data bus 8-1 is not busy, i.e., is available for access by any waiting local processor, such as 4, 5 or 6, etc. that needs access to the data bus. A low level, such as 11-2 on Busy conductor 8-2 indicates that the Busy conductor 8-2 is not available, and is being used in a "data transfer mode" by one of the local processors. Usually, busy signal 11 (FIG. 3A) will be at a high level during the bus arbitration or bus contention process subsequently described herein, and will go to a low level after the one of the local processors having the highest priority has gained control of the bus and is beginning to effectuate a transfer of data.
Signal 13 in FIG. 3A designates the Ready signal RDY. When the Ready (RDY) signal voltage is high, it is a logical "1" and indicates that data presently on the data bus is now valid and can be read by the local processors. Level 13-1 represents a logical "1" and reference numeral 13-2 represents a logical "0" on the Ready conductor 13. Reference numeral 15 identifies the Acknowledge (ACK) signal, which is at a logical "1" when it is at the high voltage level indicated by reference numeral 15-1 and is a logical "0" when at the level indicated by reference numeral 15-2.
The data bus conductor 8 is connected in wire ORed fashion to each of the local processors 4, 5, 6 etc. so that if any of them outputs a logical "1" onto the data bus, that logical level appears on data bus 8-1. However, if all of the local processors output logical "0's" onto the data bus, then a logical "0" appears thereon. Similarly, the Busy conductor 11, Ready conductor 13 and Acknowledge signal conductor 15 each are similarly connected in a wire ORed fashion to the local processors.
More specifically, if any of the local processors is engaged in a data transfer via data bus 8-1, it can pull Busy conductor 8-2 to the low logical level indicated by 11-2 in FIG. 3A, but if all of the local processors are passive and not using the data bus at all, then the high voltage level designated by reference numeral 11-1 in FIG. 3A appears on Busy conductor 802. If any of the local processors tries to get access to the data bus 8-1, when it is not busy, that local processor will pull Ready conductor 8-3 to the level indicated by reference numeral 13-2 in FIG. 2A. However, if none of the local processors asserts a low level on Ready conductor 8-3, then it will assume the high voltage level designated by reference numeral 13-1. Similarly, if any of the local processors tries to assert the low logic voltage level designated by 15-2 on Acknowledge conductor 8-4, that level will appear on Acknowledge conductor 8-4; but if all of the local processors release Acknowledge conductor 8-4, then it will have the high voltage level indicated by reference numeral 15-1.
The Ready signal 13 and the Acknowledge signal 15 of FIG. 3A illustrate how all of the local processors in local network 1 in effect operate in a synchronized or "handshaking" manner to output data onto data bus 8-1 or read data thereon.
More specifically, the handshaking operation is as follows. If the data bus becomes available, then all of the local processors wishing to gain access to the data bus to transmit a request try to pull the voltage on Ready conductor 8-3 to the low or logical "0" level 13-2 of FIG. 3A. The first one of the local processors to attempt this succeeds. As soon as one of the local processors detects that the Ready signal has gone to this low level, it pulls the Acknowledge conductor 8-4 to the low level indicated by 15-2 in FIG. 3A. Then any of the "contending" local processors wanting to get control of the data bus then asserts either a logical "1" or a logical "0" on data bus 8-1 in accordance with the data each processor is to transmit.
At this point, it should be understood that the first piece of information that any contending local processor tries to output onto the data bus is its most significant priority bit. In order to understand this better, it will be helpful to now refer to FIG. 3B, which illustrates a string of information that is output by each local processor that wishes to gain control of the data bus. This string of information is referred to as a "transmission header packet" and contains data necessary to resolve bus contention "disputes" and to define the request of the processor having highest priority on to the data bus. The transmission header packet includes three levels, identified as level I, level II and level III. Level I includes 8 bytes, the first two of which are reserved to perform a "priority override" function, so that under certain circumstances, a particular local processor can obtain higher priority than the normal "rotating priority" information contained in bytes 3 and 4. Bytes 3 and 4 represent a 16 bit "rotating" priority word which is incremented or otherwise modified each time a local processor fails to gain access to the data bus or fails to "merge" its request with that of the highest priority local processor, as subsequently explained. Byte 5 is a presently unused byte which may also be used at some future time for resolving bus priority disputes. Byte number 6 contains the address of the "source" or contending local processor attempting to gain control of the data bus. Byte number 7 is reserved for an "external" destination address, which is an address of a device, such as a remote processor coupled by a modem to the local network but is not considered to be part of the local network 1. Byte 8 contains the "object" address, which is the address of another local processor connected to the network to which the "source" local processor wishes to address a message.
Level I of the transmission header packet is referred to as the access level or access header portion thereof. Level II of the transmission header packet is referred to as the transaction validation header and includes byte 1, which defines the operating system under which the request being made by the subject contending local processor can operate. Byte 2 of level II defines the particular transaction that is requested under the operating system defined by byte 1 of level II. As an example, byte 1 of level II could define whether the CP/M operating system or the popular MS/DOS operating system is the one under which the transaction of byte 2 is defined. The transaction could be a request to "boot" the processor via the bus or to read (or write into) a particular sector on a particular mass storage device, such as a disc. Or, as another example, byte 2 of level II could define the transaction being requested as a data storage or retrieval operation, or it could be a request to access or to sign off a particular operation system. Or it could be a request for connection of the local network to another network specified by the object address of byte 8 of level I.
Level III in FIG. 3B contains a number of bytes that represent a "transaction control block". The information in the transaction control block actually defines the request being made and will contain such information as the name of the file that is to be accessed, whether or not the operation is to be a read operation or a write operation, what device will be accessed, etc.
Once the entire transmission header packet has been transmitted by a partiuclar local processor, then the actual transaction takes place; either commands from the local processor having control of the bus or data outputted by that local processor or data produced by some other device in response to the request then appear in serial fasion on data bus conductor 8-1 to effectuate the transaction. Each of the local processors in local network 1 (FIG. 2) attempts to output its entire transmission header packet (FIG. 3B) when the local processor attempts to gain control of the data bus. However, if a plurality of local processors are waiting for access to the data bus when Busy signal 11 (FIG. 3A) goes high, only the local processor having the highest priority (bytes 1-4 of level I) will succeed in getting control of the data bus; that processor is referred to as the "winning" processor. Ordinarily, unless there is a priority override situation, bytes 1 and 2 of level I of the transmission header packet are all "zeros". Usually, each of the contending local processors has a priority determined by bytes 3 and 4 of the access header. The longer a particular local processor has been waiting for access to the bus, the higher will be its rotating priority code.
Turning to FIG. 3A, each of the contending local processors which are trying to get control of the data bus then asserts a "0" or "1" onto the data bus. If any of them assert a "1", a "1" appears on data bus 8-1 (due to the wire ORed connection thereto). Or, if all of the contending local processors output logical "0's", then a logical "0" appears on the data bus. After enough time has been allowed for the output data 10 (FIG. 3A) to settle on the data bus, each of the local processors releases the ready signal 13 on ready conductor 8-3. The last one to release it causes the Ready signal to rise to the high level indicated by reference numeral 16 in FIG. 3A. At this point, the data on data bus is "valid", and can be read. Each of the contending local processors reads the value of data presently on data bus 8-1 and compares it to the logic level which that same local processor last asserted onto the data bus; if it matches, that local processor remains eligible to transmit further priority data onto data bus 8-1, but if there is mismatch, that local processor does not have the highest priority of the contending processors and becomes a "losing" processor that is now ineligible to assert further priority bits onto the data bus. When all of the contending local processors have read the data presently on the data bus, they "release" the Acknowledge conductor 8-4. When the last contending processor releases the Acknowledge conductor 8-4, it rises, as indicated by reference numeral 17, to the high or "1" level designated by 15-1 in FIG. 3A.
Thus, any time a particular local processor detects a mismatch between the data that it reads on the data bus and the data that same local processor last asserted on the data bus 8-1, a "data collision" is said to have occurred. Such a data collision automatically means that processor is a "losing" processor because it does not have the highest present priority for gaining access to the data bus.
In accordance with the present invention, each losing processor continues in a passive "monitor and compare" mode, to read all valid data bits appearing on the data bus 8-1 and compares them with the corresponding bits in its own transmission header packet. However, the losing processor does not assert any more bits of its own transmission header packet on the data bus.
It can be seen that by the time the least significant bit of byte 5 of level I of the transmission header packet has been transmitted onto the data bus during a particular bus contention dispute, the highest priority processor has emerged as the winning processor. All of the other contending processors have become "losing processors". By the time the winning processor has transmitted all of leveI I of the transmission header packet illustrated in FIG. 3B, sufficient information has been received by each contending processor to allow any one of them to adjust byte 1 or byte 2 or byte 4 or byte 5 of level I of its transmission header packet in accordance with any priority modification algorithm that might be used.
All losing processors continue to passively monitor the data bus and compare bytes 1 and 2 of level II of the transmission header packet that is then transmitted by the winning processors. Data collisions, if any, are detected in the same manner as indicated above. Any time one of the losing processors does detect a data collision, it "withdraws" from monitoring of the data bus, since it can gain nothing by continuing to monitor. If any losing processor has detected no data collision during transmission of bytes 1 and 2 of level II of the transmission header packet of the winning processor, that losing processor continues to read data appearing on data bus and continues to compare with its own transmission control block the corresponding bits of the transmission control block (shown in FIG. 3B) as they are transmitted onto the data bus by the winning processor.
In accordance with the present invention, the purpose of this continued monitoring of the data bus in comparing corresponding bits of the "monitoring" local processors with the transaction control block of the winning processor is to determine if the requests by the losing processors are "mergeable" with the request output on the data bus by the winning processor. If no data collisions are detected by a particular losing processor by the end of transmission of the transaction control block, the request of that losing processor is identical to the request of the winning processor, so the request of that losing processor is mergeable with that of the winning processor; both want the same data from the same source, so both may as well get it at the same time. Therefore, the losing processor continues to monitor the data bus during the actual transaction. Any local processor that determines (by evaluating differences between corresponding bits of its own transmission header packet and the transmission header packet of the winning processor) that its request is not mergeable with the request of the winning processor then withdraws from further monitoring of the data bus.
In some instances, if comparison of the transaction control block of the winning processor by a losing processor (that has survived the collision detection process up to level 3) shows that a portion of the data requested by that losing processor falls within the range of (i.e., is a subset of) data requested by the winning processor, that losing processor may determine that its request is indeed mergeable with the request of the winning processor, even though the requests are not identical. In this case, that losing processor continues to passively monitor the data bus, reads the data appearing on the data bus as a result of the request by the winning processor, reads that data, and rejects the portion of it that falls outside of the range of the mergeable request.
Before describing the programs executed by each of the local processors, perhaps it will be helpful to first explain the basic details of an interface circuit that is added to each local processor that is included in the local network in the present invention. In the presently preferred embodiment of the invention, each of the local processors includes an APPLE II Personal Computer. An interface circuit 113 of FIG. 1 is implemented on a printed circuit card which is plugged into each respective APPLE II Computer 90 and is connected to bus 8 of local network 1. In the preferred embodiment of the invention, these printed circuit interface cards reduce complexity of the programs that are executed by the various APPLE II Personal Computers in order to implement the networking concept of the present invention with simpler software requirements, and greatly increase the data throughput rate.
Referring now to FIG. 1, reference numeral 113 designates one of the above-mentioned interface circuits, one of which is included in each of the respective local processors, such as local processor 4. Each local processor such as 4 also includes a computer 90. Note that the implementation of interface circuit 113 is shown in great detail in FIGS. 5A-5C. However, the exact operation of the circuit of FIGS. 5A-5C is not given because it is not necessary to a thorough understanding of the invention. The CPU interface circuitry in block 100 includes bus driver circuitry and address decoder circuitry (as subsequently explained with reference to FIGS. 5A-5C). Computer 90 has a 16 bit address line designated by reference numeral 91 and an 8 bit data bus designated by reference numeral 92. Computer 90 also includes a control bus 93 which includes several control lines, including several interrupt lines.
Interface circuit 113 includes seven normal local address switches, designated by reference numeral 104, which are preset by a technician at the time of installation of local network 1 to establish the address of local processor 4. After the local address switches 104 have been set, the "source" address or local station address can be read by computer 90 by means of conductors 105, which are coupled by means of CPU interface circuitry 100 to address bus 91, and data bus 92, and control bus 93.
Interface circuit 113 includes an 8 bit data latch and shift register circuitry in block 103, into which data from computer 90 is loaded, one byte at a time, before it is serially shifted out and asserted on data bus 8-1. Serial data on the data bus 8-1 being read by local processor 4 is also loaded into the 8 bit data latch and shift register circuitry in block 103.
Interface circuit 113 also includes comparator circuitry in block 102 which makes a direct, immediate comparison of a destination address (which has been loaded from data bus 8-1 into the 8-bit data latch and shift register circuit in block 103) with the permanent setting of the seven local station address switches 101. The outputs of the 8-bit data latch in block 103 are connected by conductors 116 to the comparator circuitry in block 102, as are the states of the local station address switches 101 by means of seven conductors 109. If they match, the comparator circuitry in block 102 sends a signal on conductor 106 via CPU interface circuitry in block 100 to the interrupt line of control bus 93, interrupting computer 90 to notify it that it is the destination of the request identified in levels 2 and 3 of the transmission header packet being output by the winning processor onto the network data bus 8-1. (Note that operation of the circuit is not dependent on interrupt capability, since the comparator state is also transmitted to block 104 wherefrom it may be read by the CPU).
The handshake and data counter circuitry in block 111 controls the sequence of the above-mentioned handshake operations (involving the Data Ready, and Acknowledge conductors) to accomplish "synchronization" of asserting and reading of each bit of data appearing on the data bus 8-1. The Data counter circuitry in block 111 controls the number of times a handshake sequence is carried out, i.e., eight times for each byte transmitted from personal computer 90 to network data bus 8-1 or received from data bus 8-1 before interrupting computer 90 to cause it to either load a new byte into the 8-bit data latch and shift register circuitry in block 108 for serial outputting onto data bus 8-1), or read the contents of the 8-bit data latch which has been serially loaded from data bus 8-1.
In the former operation, computer 90 writes 8 bits into the 8-bit data latch and shift register circuit in block 103, and at the same time resets the data counter in block 111. The handshake logic in block 111 effectuates eight sequential handshake operations shifting the data out of the shift register in block 103 into data comparator and collision status circuitry in block 112. From there, the data is moved via conductor 118 to bus driver circuitry in block 124 and from there to data bus 8-1. After the entire 8-bit byte has been transmitted to network data bus 8-1, the data counter circuitry in block 111 signals the computer 90 that all 8-bits have been output onto the network data bus 8-1. For reading operation, the above sequence is essentially reversed.
The logic state circuitry in block 104 includes a plurality of addressable latch circuits which either function as flags that can be read by computer 90 or as status bits that control the internal working of interface circuit 113. One of the logic states that is set by conductor 106 indicates whether or not local processor 4 is the destination of the request or message being output by the winning local processor. Another logic state of circuitry in block 104 indicates whether the present operation being carried out by local processor 4 is a reading operation or a writing operation. Another flag in block 104 indicates whether local processor 4 is operating in a data bus monitoring and comparison mode, i.e., whether local processor 4 is a "winner" or a "loser" in the bus contention dispute. Reference numeral 125A designates conductors by means of which block 104 responds to detection of a collision by block 112 to set the collision status flags in block 104 and by means of which a set collision status flag in block 104 communicates this status to block 112 to prevent outputting of further data by interface circuit 113 onto data bus 8-1, to allow continued monitoring of data bus 8-1, if the collision status flag has been set. Another flag indicates whether there was a collision detected during the last byte. One of the bits in logic state circuitry 104 is triggered at the same time that data is input to the 8-bit data latch and shift register circuit in block 103 in order to reset the data counter in block 111. Every time a new byte is loaded into the 8-bit data latch and shift register circuit, the collision state flag also has to be reset.
The data comparator and collision status circuitry in block 112 rapidly performs the comparisons between the data being transmitted by the winning processor and the request that local processor 4 would have made if it had been the winning processor. In other words, the transmission header packet of the winning processor actually appearing on network data bus 8-1 is compared, one bit at a time, against the corresponding bits of the transmission header packet of each respective losing processor that is still in the monitor and compare mode.
For the bus monitoring portion of the operation, the incoming data is input to data comparator circuitry in block 112, which is compared with the last bit that was output on data bus 8-1 and is still present in the 8 bit data latch. A comparison is automatically made by the data comparator in block 112, and if a data mismatch or collision is detected, the collision flag in block 104 is set by means of bus 127.
The detailed implementations of the various blocks shown in FIG. 1 are shown in detail in the block diagram of FIGS. 1 and 5A-5C. Referring now to these drawings, the logic state circuitry 104 is essentially that circuitry included within the dotted lines designated by reference numeral 104 in FIGS. 5A and 5B. This includes an integrated circuit LS 259 addressable latch (available from various manufacturers), two LS123 integrated circuit one-shot timers, and two LS74 integrated circuit flip flops, as shown. CPU interface circuitry 100 includes the circuitry within the dotted line block designated by 100 in FIGS. 5A and 5C, including an LS138 addressable decoder integrated circuit, an LS245 integrated circuitry bidirectional bus driver, and two LS367 integrated circuit three-state buffer circuits. The circuitry in block 103 of FIG. 1 is implemented by means of an LS299 integrated circuit 8 bit parallel access shift register.
The 7 bit local station address switches are implemented by means of any suitable commercially available eight position DIP switch, as indicated in the dotted line block 101 in FIG. 5C. The comparator function of block 102 in FIG. 1 is performed by seven exclusive OR circuits within dotted line block 102 in FIG. 5C. The remaining circuitry shown in FIGS. 5A and FIG. 5B is included in handshake logic data counter logic circuitry in block 111 of FIG. 1 and includes an LS93 integrated circuit 4-bit binary counter, two LS123 integrated circuit one-shot timers, and several LS74 integrated circuit flip-flops.
Now that the structure and basic operation of the interface circuit have been explained, it should be understood that there are two embodiments of the invention, one being a preferred "hardware version" which does include interface circuitry 113, and the other being a "software version" which does not use the interface circuit 113 and instead uses a much simpler interface circuit (not shown). In the "software version" the interface circuit consists of a set of addressable latches which directly control the state of the bus lines. These latches are driven by a computer program according to which the CPU examines the state of each incoming line and modifies the state of the latches so as to place a data signal on the bus and effectuate the handshaking process. Incoming signals are ORed with the latch states and retransmitted to the next card which performs the same function in concert with its CPU. No function is performed by the card alone other than ORing and retransmitting the signal; however, the sequence of events under software control performs essentially the same functions as the "hardware version".
The flow charts of FIGS. 4A-4D are helpful in understanding both the hardware version and the software version. Therefore, in the following explanation of the flow charts, the relevance of the operations of the flow charts to both the "software version" and "hardware version" of the invention will be set forth. FIG. 4A is a flow chart of a subroutine called SIMLWRITE, which is executed in the software version of the invention. Each time the computer outputs a byte of data for serial assertion on data bus 8-1, but it is also useful in understanding part of the operation of interface circuitry 113, and is therefore useful in understanding the basic method of the present invention. The method of the flow chart of FIG. 4A is repeated eight times for each byte of information that a particular local processor wishes to putput on the network data bus 8-1.
In the hardware version, interface circuit 113 simply receives one byte of data that computer 90 wishes to output onto data bus 8-1. That byte is loaded into the 8-bit data latch circuit in block 103; computer 90 has no further involvement with the transmission until the data counter circuit in block 111 of FIG. 1 indicates to computer 90 that all 8 bits have been shifted out of the data latch and shift register circuit in block 103, through the data comparator and collision status circuitry in block 112, through bus driver circuit 124, and serially onto data bus 8-1.
In FIG. 4A, before entering the label 210, computer 90 prepares a byte of data to transmit. This consists of computer 90 loading the next byte to be transmitted into one of the CPU registers. Another thing that is done by the processor before entering the routine of FIG. 4A is to establish that a transmit operation is what is desired. This corresponds to computer 90 setting a flip-flop in block 104 indicating that the interface circuit 113 is to operate in a WRITE (or transmit) mode. In block 211, one of the "initializing" operations referred to is to initialize a software bit counter. In interface circuit 113, this corresponds to setting the data counter in block 111, and occurs when the 8 bit data is placed in the 8 bit data latch and shift register circuit in block 103.
In interface circuit 113, when computer 90 writes the next byte to be transmitted into 8 bit data latch and shift register circuit 103, the data collision flag in block 104 is reset by means of the data counter in block 111 and is automatically reset by means of conductor 115. Computer operations involving setting or reading states in block 104 occur by means of bus 108 in FIG. 1.
In the software version of the invention, after initialization and resetting of the collision flag, the program of FIG. 4A then goes to decision block 212 and tests the collision flag to determine if it is set. In the hardware version of the invention, this function is automatically carried out by the data comparator and collision status circuitry in block 112. If the determination of decision block 212 is affirmative, and there has been a data collision, the program goes to block 214 and outputs a logical "0" on the data bus 8-1. (It should be appreciated that on entering the program of FIG. 4A, the computer would set the Ready signal conductor 8-3 and would already be a logical "0"). In block 214, in addition to outputting a logical "0" on the data bus 8-1, the computer sets the Ready signal to the logical "0" level indicated by 13-3 in FIG. 3A. The program then goes to block 215.
If the decision of block 212 is affirmative, the program goes to block 213 and causes the most significant bit of the present byte to be asserted on the network data bus 8-1. In the hardware version of the invention, this function is controlled by the state of the collision flag (which is a flip-flop in block 104 of FIG. 1) and a circuit in block 112 that allows only "0's" to be outputted to data bus 8-1 if the collision flag is set.
As soon as this is done, the program causes the Ready signal to be set to a logical "1".
In the software version of the invention, the program of FIG. 4A then goes to block 215, samples the state of the Acknowledge conductor 804, determines in decision block 216 whether the Acknowledge signal is set to a logical "1", and if it is not, the program continues looping back through block 215 until the last receiving local processor finally releases the Acknowledge conductor 8-4, at a point indicated by reference numeral 17 on the timing diagram of FIG. 3A. In the hardware version of the invention, the handshake logic and data counter circuitry of block 111 automatically performs this function.
In the software version of the invention, the program of FIG. 4A then goes to block 217. In block 217, once the Acknowledge signal 15 is set to a "1" level 15-3 in FIG. 3A, this means that the data on data bus 8-1 has been received. In the software version of the invention, the program, in block 217, reads the data that is presently on data bus 8-1, and then resets the Ready signal to the level indicated by reference numeral 13-4 in FIG. 3A concluding the tramission of that bit. In the hardware version of the invention this is automatically done by circuitry in block 112 that monitors the status of data bus 8-1. The program then goes to decision block 218 and compares the data previously read in block 217 to the last bit asserted onto data bus 8-1 by the subject local processor. In the hardware version of the invention, the data comparator circuitry in block 112 automatically performs the comparison corresponding to decision block 218. If there is a mismatch, a collision flag is set, in block 104 of interface circuit 113 (for the hardware version of the invention) or in a software register in a computer program represented by the flow chart of FIG. 3A (for the software version). In the software version of this invention, the program goes to block 220 and reads the state of the Acknowledge conductor 804, and in decision block 221 tests to see if the Acknowledge signal 15 has been reset. When the Acknowledge signal has been reset to the level indicated by reference 15-4 in FIG. 3A, the program goes to block 222 and shifts to the left (in a software register) the next bit to be serially asserted onto data bus 8-1. In the hardware version of the invention, these functions are automatically performed by the handshake logic in block 111 and the shift register in block 103 of FIG. 1. In the software version, a software bit counter keeps track of which bit in the present byte is to be shifted out next onto data bus 8-1 is incremented in block 222. Correspondingly, the data counter in block 111 in interface circuit 113 is automatically incremented each time data is shifted in the shift register in block 103.
Then, as indicated in decision block 223, the state of the software bit counter of the software program, or the hardware data counter in interface circuit 113, is tested to see if the entire present byte has yet been asserted onto data bus 8-1. If this has not yet been accomplished, the program of FIG. 4A returns to decision block 212 and continues repeating the process until the bit count does expire. When this finally happens, the subroutine of FIG. 4A exits to the calling program (which is shown by the flow chart of FIG. 4D) at label 224. In the hardware version of the invention, the handshake logic and data counter circuitry in block 111 send an interrupt signal to computer 90 informing it to output the next byte into the 8-bit data latch and shift register circuitry in block 103.
The next flow chart, shown in FIG. 4B, is a flow chart of a software program that can cause a computer such as the above-mentioned APPLE personal computer to perform essentially the same functions as interface circuit 113 when the local processor is functioning as a receiver, rather than as a transmitter of information. As previously mentioned, the program shown in FIG. 4B can be executed by a computer having a much simpler interface card than 113, i.e., which merely functions in response to the program instructions, as previously explained.
In the hardware version of the invention, computer 90 (in FIG. 1) is required to perform essentially no other function when local processor is in its receive mode than to check to determine when the 8-bit data latch and shift register circuit 103 has been filled up with the serially incoming data on data bus 8-1. Every time this happens, the data counter in block 111 so indicates (via a flag in block 104) to computer 90, alerting it to read that byte out of the 8-bit data latch in block 103.
In the software version of the invention, the program of FIG. 4B is entered when the local processor is set to its receive mode. In block 202, the program initializes its software bit counter. In the hardware version of the invention, circuitry in block 111 automatically initializes the data counter in block 111 every time the 8-bit data latch and shift register circuitry of block 103 has been read, removing the last complete byte of incoming data.
The program of FIG. 4B goes from block 202 to block 203 and senses the state of the Ready signal 13 on conductor 8-3, and if it is set to a logical "1", as determined by decision block 204, the program moves onto block 205. If the Ready signal is not a "1", the program loops back through block 203 until the Ready signal goes to a "1". This is how the program determines when the data is "valid". The Ready signal is set to the desired "1" state when it is at the level indicated by 13-3 in FIG. 3A.
In block 205, the program reads the least significant bit of the present byte which has been received from data bus 8-1, and then sets the Acknowledge signal 15 on conductor 8-3 to level 15-3 in FIG. 3A. In the hardware version of this invention, serially incoming data on data bus 8-1 is fed via conductor 119 through block 112 and into the least significant bit input of the data latch and shift register circuitry in block 103.
Next, the program of FIG. 4B goes to blocks 206 and 207 and keeps testing the state of the Ready conductor 8-3 until it is a logical "zero", at the level indicated by reference numeral 13-4 in FIG. 3A, concluding transmission of that bit.
Next, the program of FIG. 4B goes to block 208 and applies a logical "0" to the Acknowledge signal, bringing it to the level indicated by reference numeral 15-4 in FIG. 3A. In the hardware embodiment of the invention, the handshake logic in block 111 of interface circuit 113 in essence performs the foregoing function automatically. The interface circuit 113 automatically releases the Acknowledge line as the data is shifted into the shift register, and automatically resets the Acknowledge line to a "0" in response to data transmission by the Ready conductor.
The program of FIG. 4B then goes to block 209, shifts data left in a software register and increments a software bit counter that keeps track of which bit of the present byte was just received. In the hardware version of the invention, this is done automatically by the circuitry in block 111 and block 103 of FIG. 1.
The program then goes to decision block 209A and determines if the bit count has expired, that is, if the last bit of the present byte has been received. If this is true, the subroutine is exited but if it is false, the program returns to block 203 and repeats the sequence for the next incoming bit of the present byte. As previously explained, this function is automatically performed in the hardware version of the invention by the data counter circuitry in block 111 of interface circuit 112. In the "hardware" system of FIG. 1, all that computer 90 does while the present byte is incoming on data bus 8-1, is continually test a flag to see if the data counter has counted from 0 to 7, and when it has, computer 90 knows to read the contents of 8-bit data latch and shift register circuitry in block 103.
The "collision management" subroutine of FIG. 4C is entered at label 250A as a result of a decision by computer 90 that local processor 4 needs to gain access to the network. In block 251, the program waits until the Busy signal on conductor 8-2 goes high, as shown in FIG. 2A. At this point, all contending processors wanting access to the network bus 8-1 begin to send their access headers to the data bus 8-1, as indicated in block 252, by calling the SEND subroutine shown in FIG. 4D utilized to effectuate block 252 of FIG. 4C. Therefore, at this point it will be helpful to explain FIG. 4D.
Referring now to FIG. 4D, the SEND subroutine is entered at block 320 whenever it is called from block 252, 255, 256, 258, 259 or 261 of the collision management program of FIG. 4C. In block 321, the SEND subroutine resets a collision state flat called CSTATE to a "zero". The subroutine then goes to block 322 and causes the processor to output the next 8-bit byte of data to be transmitted.
This function is performed with interface circuit 113 interfacing between computer 90 and network bus 8. However, if less sophisticated interface circuitry (not shown) than that in interface circuit 113 is used, the subroutines of FIGS. 4A and 4B can instead be utilized to provide the send and receive "interface" functions. For example, in FIG. 4D, in the hardware embodiment of the invention, the function of block 324 is performed by means of interface circuit 113, whereas those functions are performed by calling the SIMLWRITE subroutine of FIG. 4A in the software embodiment of the invention.
Next, the SEND subroutine of FIG. 4D goes to decision block 323 and tests the first collision flag set in block 219 resulting from the SIMLWRITE routine of FIG. 4A. In the hardware version of the invention, CPU 90 simply tests a corresponding flag in block 104. If this flag has been set, the subroutine of FIG. 4D goes to block 324 and sets the first comparison state flag and the CSTATE flag to a logical "1" and then goes to block 325. If the determination of decision block 323 is negative, then the program goes to block 325. In block 325 the program increments the byte count. In decision block 326, the subroutine determines if all bytes that are to be output by the processor have been output, and if not, returns to block 322. If all bytes of the access header have been transmitted, the program goes to block 327 and sets a second collision flag to the same state as the CSTATE flag set in block 324. The SEND subroutine of FIG. 4D then returns to the program of FIG. 4C.
Returning now to the description of FIG. 4C, after the access header has been sent, the program goes to decision block 253 and tests the second collision flag (of block 327 has been set, this means that the local of FIG. 4D). If it processor executing the program of FIG. 4C is a "losing" processor, i.e., that local processor is not the highest priority contending processor. As a result, the program goes to block 254 and sets a flag that puts that contending processor in a "monitor and compare" mode. In the hardware version of the invention, the flag is in block 104. In the software version, the "monitor and compare" mode state would be stored in an appropriate software register. However, if the decision of block 253 is negative, there has been no data collision during transmission of the priority access header, so the subject contending processor is the highest priority or "winning" processor.
In this event, the winning processor simply goes to block 255, calls the SEND subroutine of FIG. 4D, and transmits the "transaction validation header" information, i.e., the level 2 portion of the transmission header packet shown in FIG. 3B. Then the program moves to block 258 and sends the input/output control block portion of the transmission header packet indicated by level 3 in FIG. 3B, again calling the SEND subroutine to effectuate transmission thereof. Next, the program goes to block 261 and performs whatever transmission and/or reading operations are necessary to carry out the transactions specified by the I/O control block portion of its transmission header packet. "Sending" portions of the transaction will be effectuated by calling the SEND subroutine of FIG. 4D and "RECEIVE" portions will be effectuated by calling the SIMLREAD subroutine of FIG. 4B. When the transaction is complete, the program of FIG. 4C is exited via block 264 and returns to the main control program of the winning processor.
If the particular processor executing the program of FIG. 4C is a losing processor, the program then is set to the "monitor and compare mode" as previously indicated with reference to block 254. The program then goes to block 256, but does not actually transmit its transaction validation header. Instead, it continues to read the data appearing on the data bus 8-1, which data will be the transaction validation header being transmitted in accordance with block 255 of the identical program being executed by the winning processor. (It should be noted that in blocks 252, 255, 256, 257, 258 and 261, the SEND and/or SIMLREAD subroutines are called only for the "software version" of the invention. If the interface circuit 113 of FIG. 1 is used, then the functions of the SEND and SIMLREAD subroutines are automatically carried out at very high speed by the circuitry contained in iterface circuit 113.)
The send block program of FIG. 4D will set the comparison mode flag in block 321 thereof, and then, when it calls SIMLWRITE in block 322, it will recognize in block 212 that a collision flag has been set and will only output logical "zeros" and will never output a logical "1", thereby effectively placing that local processor in a read or monitor mode.
If a collision or mismatch is detected in decision block 257 of FIG. 4C, this means that the subject local processor cannot merge its transaction with that of the winning processor, and therefore modifies its priority according to a suitable priority subroutine to improve its likelihood of success on the next try. It then goes back to block 251 and waits for the bus to become available again.
Next, the program moves to block 259, and calls the SEND routine of FIG. 4D which, in turn, calls SIMLWRITE, and compares its own I/O control block with the I/O control block being transmitted by the winning processor (which is executing block 258 of the program of FIG. 4C of its own collision management program). If no mismatch is detected, as indicated in decision block 260, then the losing local processor has determined that its entire transaction header is identical to that of the winning processor, and therefore its transaction can be merged with that of the winning processor. The losing processor then goes to block 261 and performs, in parallel with the winning processor, whatever send and receive operations are necessary to carry out the merge transactions and then exits its collision management program via block 264.
If the determination of decision block 260 is affirmative and there has been a mismatch, this does not necessarily means that the transaction desired by the losing processor is not mergeable with the transaction to be carried out by the winning processor. If the data which is to be conducted on the data bus when the transaction desired by the losing processor is actually carried out is contained as a subset of the transaction data for the winning processor, then the transaction of the losing processor is nevertheless mergeable with the transaction of the winning processor. This determination is made in decision block 262, and if the determination is negative, then the losing processor returns to block 251 and waits in line for its turn to gain access to the data bus when its priority byte finally has the highest value of any contending processor. If the determination of block 262 is affirmative, the program goes to block 262 and executes a very simple subroutine for extracting its subset of data from the transmissions that constitute the transaction carried out by the winning processor.
This consists of reading all of the transaction data while discarding all data (if any) preceding the desired block of data; reading the desired block of data; and finally, ignoring any additional data following the desired block of data.
Appendix A is a print-out of a computer program executed by an APPLE II personal computer corresponding to the flow charts of FIGS. 4A and 4B. Similarly, Appendix B is a print-out of the program subroutine of FIG. 4C, and Appendix C is a print-out corresponding to FIG. 4D.
While the invention has been described with reference to several particular embodiments thereof, those skilled in the art will be able to make various equivalent modifications thereto without departing from the true spirit and scope of the invention. For example, the definition of the various CPU buses may differ from that indicated above, since the signals present on the buses to control the function of the circuitry may be adopted in different ways to control the interface circuit 113. ##SPC1##
Claims
We claim:
1. A computer network comprising: (a) a bus, including a bus conductor; (b) a plurality of processors coupled to said bus, some or all of which processors contend for control of said bus in order to transmit transmission header information, including priority header information followed by transaction header information, via said bus to a destination address, said priority header information in each of said processors including a plurality of bits arranged as priority code; (c) data asserting means in each of said processors causing said contending processors to each concurrently assert corresponding bits of their respective priority codes on said bus in order of decreasing bit significance, such that if any of said corresponding priority code bits is at a first logic level, said first logic level appears on said bus conductor and otherwise a second logic level appears on said bus conductor; (d) priority bit reading means in each of said processors for causing each contending processor to read the priority bit logic levels appearing on said bus conductor; (e) priority bit comparing means in each of said processors for causing each contending processor to compare the logic levels of the bits of its priority code to corresponding logic levels of bits read on said bus conductor in order of decreasing bit significance to detect the occurrence of any data mismatches therebetween; (f) mismatch data gating means in each of said processors for causing any of said contending processors for which a data mismatch is detected to immediately stop asserting further bits of its transmission header information; (g) transaction data transmission means in each of said processors for causing a highest priority one of said contending processors which does not detect a data mismatch during transmission of its priority header information to transmit its transaction header information on said bus; (h) transaction header reading and comparing means for causing each other one of said contending processors to read the bits of data of said transaction header information transmitted by said highest priority contending processor on said data bus and compare those bits with respective corresponding bits of the transaction header information of that contending processor to detect any mismatches therebetween; and (i) mergeability determination means in each of said processors responsive to said transaction header reading and comparing means for causing each of said other ones of said contending processors to determine, in response to its comparing of its own transaction header information with that transmitted on said bus by said highest priority contending processor, whether a first transaction specified by the transaction header information of that contending processor can be merged with a second transaction specified by the transaction header information of said highest priority contending processor.
2. The computer network of claim 1 including merging means in each of said processors responsive to said mergeability determination means therein for causing that processor to read all of the data appearing on said data bus during said second transaction.
3. The computer network of claim 2 including priority modification means in each of said contending processors for modifying the priority code of that contending processor before that contending processor can contend for said bus.
4. The computer network of claim 3 wherein each of said processors includes a computer and an interface circuit coupling that couples that computer to said bus, said bus including a bidirectional serial data bus including said bus conductor, a ready signal conductor, and an acknowledge signal conductor, and a busy signal conductor.
5. The computer network of claim 4 wherein said interface circuit includes shift register circuit means for transferring data in parallel format between said interface circuit and said computer and for effectuating transfer of data in serial format between said bus conductor and said interface circuit.
6. The computer network of claim 5 wherein said interface circuit includes local station address means for storing a permanent local address code of said processor and address comparison means coupled to said shift register circuit means and said local address means for producing a predetermined signal if an address code that has been input into said shift register circuit means from said bus conductor matches said local address code.
7. The computer network of claim 6 wherein said interface circuit includes comparison circuit means for sequentially comparing corresponding bits of transmission header information written into said shift register circuit means by said computer and transmission header information appearing on said bus conductor and producing a mismatch signal in response to a mismatch between said corresponding bits, and storage means responsive to said comparison circuit means and coupled to said computer for storing information indicative of the occurrence of said mismatch and gating circuit means coupled to said storage means, said bus conductor and said shift register circuit means for preventing any data having said first logic level from being asserted by that contending processor onto said bus conductor.
8. The computer network of claim 7 wherein said interface circuit includes handshaking logic circuit means coupled to said bus conductor, said busy signal conductor, said Ready signal conductor, said Acknowledge signal conductor, said shift register circuit means, and said storage means for effectuating handshaking operations to synchronize transfer of said transmission header information on said bus conductor.
9. A method of operating a computer network including a bus and a plurality of processors, some or all of which contend for control of said bus in order to transmit transmission header information, including priority header information followed by transaction header information, via said bus to a destination address, said priority header information in each of said processors including a plurality of priority bits arranged as a priority code, said method comprising the steps of: (a) causing each of said contending processors to concurrently assert a most significant bit of its priority code on said bus such that if any of said most significant priority code bits is at a first logic level, said first logic level appears on a conductor of said bus and otherwise a second logic level appears on said bus conductor; (b) causing each contending processor to read the logic level appearing on said bus conductor; (c) causing each contending processor to compare the logic level of the most significant bit of its priority code to the logic level read in step (b) to determine if a data collision has occurred; (d) causing any of said contending processors detecting a data collision to stop asserting bits of its transmission header information; (e) repeating steps (a) through (d) for the remaining bits of said priority codes in order of decreasing bit significance; (f) causing a highest priority one of said contending processors which does not detect a data collision to transmit its transaction header information on said bus, and also causing each other one of said contending processors to read the bits of data appearing on the bus and compare those bits with respective corresponding bits of the transaction header information of that contending processor to detect any mismatches therewith; and (g) causing each of said other ones of said contending processors to determine, in response to said comparing of step (f), if a first transaction specified by the transaction header information of that contending processor can be merged with a second transaction specified by the transaction header information of said highest priority contending processor by determining if the data to be conducted on said bus in effectuating said first transaction is identical to or is a subset of the data that would be conducted on said bus in effectuating said second transaction.
10. The method of claim 9 further including the step of causing each of said other ones of said contending processors to determine, in response to said comparing of step (f), if a first transaction specified by the transaction header information of that contending processor is mergeable with a second transaction specified by the transaction header information of said highest priority contending processor by determining if the data to be conducted on said bus in effectuating said first transaction is identical to the data that would be conducted on said bus in effectuating said second transaction.
11. The method of claim 9 including causing said highest priority contending processor to write information onto said bus and read information from said bus as necessary to effectuate performing of said second transaction.
12. The method of claim 11 including causing each of said other ones of said contending processors for which said determining is affirmative to merge said first transaction with said second transaction by continuing to read data appearing on said bus during said second transaction.
13. The method of claim 12 including causing said highest priority contending processor to modify its priority code to a different value.
14. The method of claim 12 including causing each contending processor which does not merge its transaction with said second transaction to modify its priority code to a different value.
15. The method of claim 11 wherein the bits of said transaction header information are serially asserted on said bus conductor.
16. The method of claim 15 wherein said bus includes a pair of handshaking signal conductors for respectively conducting a ready signal responsive to any of said contending processors for indicating when data on said bus conductor is valid and an acknowledge signal generated by the last one of said other contending processors to read data on said bus conductor in response to said ready signal.
17. A method of operating a computer network including a bus and a plurality of processors, some of which are contending for control of said bus in order to transmit transmission header information, including priority header information followed by transaction header information, via said bus to a destination address, said priority header information in each of said processors including a predetermined number of priority bits arranged as a priority code, said method comprising the steps of: (a) causing each of said contending processors to concurrently assert the most significant bit of its priority code on said bus such that if any of said most significant priority code bits is a first logic level, said first logic level appears on a conductor of said bus, and otherwise a second logic level appears on said bus conductor; (b) causing each contending processor to read the logic level appearing on said bus conductor; (c) causing each contending processor to compare the logic level of the most significant bit of its priority code to the logic level read in step (b) to determine if a data collision has occurred; (d) causing any of said contending processors detecting a data collision to stop asserting bits of its transmission header information; (e) repeating steps (a) through (d) for the remaining bits of said priority codes in order of decreasing bit significance; (f) causing a highest priority one of said contending processors which does not detect a data collision to transmit its transaction header information on said data bus, and also causing each other one of said contending processors to read the bits of data appearing on the data bus and compare those bits with respective corresponding bits of the transaction header information of that contending processor to detect any mismatches therewith; (g) causing each of said other ones of said contending processors to determine, in response to said comparing of step (f) to determine whether a first transaction specified by the transaction header information of that contending processor can be merged with a second transaction specified by the transaction header information of said highest priority contending processor by determining if the data to be conducted on said bus in performing said first transaction is identical to or is a subset of the data that will be conducted on said bus in performing said second transaction; (h) causing said highest priority contending processor to write information onto said bus and read information from said bus as necessary to effectuate performing of said second transaction; (i) causing each of said other ones of said contending processors for which the determination of step (g) is affirmative to continue to read data appearing on said bus during said second transaction; and (j) causing said highest priority contending processor to modify its priority code to a different value, and causing each contending processor which does not merge its transaction with said second transaction to modify its priority code to a different value.