Distributed computing system with dual independent communications paths between computers and employing split tokens

• US 4,933,936 A
• Filed: 08/17/1987
• Issued: 06/12/1990
• Est. Priority Date: 08/17/1987
• Status: Expired due to Fees

• Current Assignee: United States Department Of Health And Human Services
• Original Assignee: United States Of America As Represented By The Administrator Of The National Aeronautics And Space Administration
• Inventors: Manning, Robert M., Bolotin, Gary S., Ward, Richard S., Lewis, Blair F., Rasmussen, Robert D.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Jung, Min
• Application Number:
  US07/085,833
• Time in Patent Office: 1,030 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 340/825.5, 340/825.52, 370/85, 370/86, 370/60, 370/94, 370/89, 371/36
• US Class Current: 370/406
• CPC Class Codes: H04L 12/28 characterised by path configuration, e.g. LAN [Local Area Networks] or WAN [Wide Area Networks] wireless communication networks H04W ; arrangements for dividing the transmission path H04W40/00
• CPC Class Codes: H04L 12/4135 using bit-wise arbitration

Abstract

This is a distributed computing system providing flexible fault tolerance; ease of software design and concurrency specification; and dynamic balance of the loads. The system comprises a plurality of computers each having a first input/output interface and a second input/output interface for interfacing to communications networks each second input/output interface including a bypass for bypassing the associated computer. A global communications network interconnects the first input/output interfaces for providing each computer the ability to broadcast messages simultaneously to the remainder of the computers. A meshwork communications network interconnects the second input/output interfaces providing each computer with the ability to establish a communications link with another of the computers bypassing the remainder of computers. Each computer is controlled by a resident copy of a common operating system. Communications between respective ones of computers is by means of split tokens each having a moving first portion which is sent from computer to computer and a resident second portion which is disposed in the memory of at least one of computer and wherein the location of the second portion is part of the first portion. The split tokens represent both functions to be executed by the computers and data to be employed in the execution of the functions. The first input/output interfaces each include logic for detecting a collision between messages and for terminating the broadcasting of a message whereby collisions between messages are detected and avoided.

Claims

1. A computer system comprising:

(a) a plurality of computers, each said computer having first input/output interface means to a communicatiosn network and second input/output interface means for interfacing a communications network, each said second input/output interface means including bypass means for bypassing the associated said computer with a bit stream of data passing through said second input/output interface means;

(b) global communications network means interconnecting respective ones of said first input/output interface means for providing respective ones of said computers with the ability to broadcast messages simultaneously to the remainder of said computers; and

,

(c) meshwork communications network means interconnecting respective ones of said second input/output interface means for providing respective ones of said computers with the ability to establish a communications link with another of said computers through said bypass means of the remainder of said computers; and

wherein,

(d) communications between respective ones of said computers includes the use of split tokens each having a moving first portion which is sent from computer to computer and a resident second portion which is disposed in the memory of at least one of said computers and wherein the storage location address of said second portion is contained within said first portion.

2. The computer system of claim 1 wherein:

said split tokens represent both functions to be executed by said computers and data to be employed in the execution of said functions.

3. The computer system of claim 1 wherein:

said first input/output interface means each includes detecting and terminating means for detecting a collision between messages being broadcast over said global communications network means and for terminating the broadcasting of a message in favor of a message with superior right to the use of said global communications network means whereby collisions between messages from a plurality of said computers are detected and avoided, said detecting a terminating means comprising;

said messages broadcast by said computers over said global communications network means each including a leading module identifying portion, and

each said first input/output interface means including means for testing the last bit broadcast contents of said global communications network means as message from its associated said computer are being broadcast over said global communications network means on a bit-by-bit basis and for terminating the broadcasting of a message when said last bit broadcast contents of said global communications network means is not identical to the previous bit of the message just broadcast by said first input/output interface means indicating that another said computer was first in time on said global communications network means.

4. The computer system of claim 3 wherein additionally:

said messages broadcast by said computers over said global communications network means each include a priority code preceding a module identifying portion whereby another said computer which was first in time on said global communications network means will automatically relinquish said global communications network means to the message of another said computer which is of a higher priority.

5. The computer system of claim 3 wherein additionally:

(a) said messages broadcast by said computers over said global communications network means each include a reserved portion of fixed length and normally containing no data immediately following said module identifying portion;

(b) said first input/output interface means at each said computer includes first logic means for broadcasting a data bit over said global communications network means during said reserved portion when it has terminated the sending of a message as a result of a detected collision; and

,

(c) said first input/output interface means at each said computer further includes second logic means for testing said global communications network means during said reserved portion and for not immediately broadcasting a new message following the termination of a broadcast message when said data bit is detected during said reserved portion whereby a said computer which has control of said global communications network means will relinquish said global communications network means for a message of another said computer which has previously relinquished said global communications network means whereby computer lockout from access to said global communications network means is prevented and equal access to all said computers is guaranteed.

6. The computer system of claim 1 wherein:

(a) said messages broadcast by said computers over said global communications network means each include a cyclic redundancy check code for the preceding bits and a trailing portion of fixed length and normally containing no data;

(b) said first input/output interface means at each said computer includes third logic means for testing each said message as received by means of said cyclic redundancy check code and for broadcasting a data bit over said global communications network means during said trailing portion if a said received message is in error; and

,

(c) said first input/output interface means at each said computer further includes fourth logic means for testing said global communications network means during said trailing portion and for rebroadcasting its last broadcast message as not having been received if it senses said data bit during said trailing portion.

7. The computer system of claim 1 wherein:

(a) said bypass means of said second input/output interface means at each said computer includes a receiver for receiving inputs to the associated said computer, a transmitter for transmitting outputs from the associated said computer, a plurality of inputs and outputs connected to respective ones of said inputs and outputs of others of said computers interconnected by said meshwork communications network means, and crossbar switch means interconnecting said inputs and said outputs for bypassing said receiver and said transmitter at the associated said computer and for interconnecting one of said plurality of inputs to one of said plurality of outputs whereby a bypass link between said ones of said plurality of inputs and outputs is established.

8. The computer system of claim 7 wherein:

said bypass means of said second input/output interface means at each said computer includes means for sensing a unique signal on said meshwork communications network means indicating that said bypass link is to be terminated and for causing said crossbar switch means to open said bypass link when said unique signal is sensed.

9. The computer system of claim 7 wherein:

said bypass means of said second input/output interface means at each said computer includes repeater means for inverting the clock pulses passing through said crossbar switch means and for resampling data passing therethrough with said inverted clock pulses whereby narrowing of data pulses and loss of synchronization between data passing therethrough and the clock pulses associated therewith is eliminated.

10. A communications network system with the capability of sensing and avoiding message collisions for interconnecting a plurality of computers comprising:

(a) each computer having input/output interface means for interfacing to a communications network;

(b) global communications network means interconnecting respective ones of said input/output interface means for providing respective ones of said computers with the ability to broadcast messages simultaneously to the remainder of said computers; and

,

(c) detecting and terminating means included as part of each said input/output interface means for detecting a collision between messages being broadcast over said global communications network means and for terminating the broadcasting of a message in favor of a message with superior right to use of said global communications network means whereby collisions between simultaneous messages from a plurality of the computers are detected and avoided; and

wherein,

(d) the messages broadcast by the computers over said global communications network means each includes a leading module identifying portion;

(e) said first input/output interface means each includes means for testing the last bit broadcast contents of said global communications network means as messages from its associated computer are being broadcast serially over said global communications network means on a bit-by-bit basis and for terminating the broadcasting of a message when said last bit broadcast contents of said global communications network means is not identical to the previous bit of the message just broadcast by said first input/output interface means thus indicating that another computer was first in time on said global communications network means; and

,

(f) the messages broadcast by the computers over said global communications network means each include a leading priority code preceding said module identifying portion whereby another computer which was first in time on said global communications network means will relinquish said global communications network means to the message of another computer which is of a higher priority.

11. The computer system of claim 10 wherein additionally:

(a) the messages broadcast by the computers over said global communications network means each include a fixed length non-data portion immediately following said module identifying portion;

(b) said first input/output interface means at each computer includes first logic means for broadcasting a data bit over said global communications network means during said fixed length immediately following non-data portion when it has terminated the sending of a message as a result of a detected collision; and

,

(c) said first input/output interface means at each computer further includes second logic means for testing said global communications network means during said fixed length immediately following non-data portion and for not immediately broadcasting a new message following the termination of a broadcast message when said data bit is detected during said fixed length immediately following non-data portion whereby a computer which has control of said global communications network means will relinquish said global communications network means to the message of another computer which has previously relinquished said global communications network means whereby computer lockout from access to said global communications network means is prevented and equal access to all the computers is guaranteed.

12. The computer system of claim 10 wherein:

(a) the messages broadcast by the computers over said global communications network means each include a cyclic redundancy check code for the preceding bits and a fixed length trailing non-data portion;

(b) said first input/output interface means at each computer includes third logic means for testing each message as received by means of said cyclic redundancy check code and for broadcasting a data bit over said global communications network means during said fixed length trailing non-data portion; and

,

(c) said first input/output interface means at each computer further includes fourth logic means for testing said global communications network means during said fixed length trailing non-data portion and for rebroadcasting its last broadcast message as not having been received if it senses said data bit during said fixed length trailing non-data portion.

13. A computer system comprising:

(a) a plurality of computers wherein each said computer is controlled by a resident copy of a common operating system; and

,

(b) communications network means interconnecting respective ones of said computers for allowing respective ones of said computers to broadcast messages to all others of said computers simultaneously and for allowing respective ones of said computers to transmit and receive data and functions to and from others of said computers;

wherein,

(c) the initiation of functions within respective ones of the computers is accomplished by the broadcasting of function tokens as messages on said communications network means; and

,

(d) communication and transfer of both functions and data between respective ones of said computers is by means of split tokens each having a moving first portion which is moved from computer to computer and a resident second portion which is disposed in the memory of at least one of said computers and wherein the location of said second portion is part of said first portion.

14. The computer system of claim 13 wherein:

(a) selected ones of said function tokens are duplicate tokens which cause the associated function to be accomplished on at least two separate ones of said computers; and

,

(b) said common operating system at each said computer includes logic for sensing duplicate tokens, for voting on the results produced by the associated function at each of said at least two separate ones of said computers, and for selecting the said results with the highest probability of being correct for use as the results of said associated function.

15. The computer system of claim 13 wherein:

said broadcasting of said function tokens is initiated by the broadcasting of data tokens required for the performance of a function as messages on said communications network means.

16. The computer system of claim 13 wherein:

ones of said function tokens have a time of execution associated with them and said broadcasting of said function tokens is initiated by the associated said time of execution being reached.

17. The computer system of claim 16 wherein:

said communications network means maintains a common system time employed by said computers connected thereto for time based activities and the time stamping of said tokens.

18. The computer system of claim 13 wherein:

`said moving firs portion of said split tokens is broadcast over said communications network means to all said computers simultaneously and said resident second portion is transferred over said communications network means from one said computer to another.

19. The computer system of claim 13 wherein:

(a) each said computer has first input/output interface means for interfacing to a communications network and second input/output interface means for interacting to a communications network, each said second input/output interface means including bypass means for bypassing the associated said computer with a bit stream passing through said second input/output interface means; and

wherein said communications network means comprises;

(b) global communications network means interconnecting respective ones of said first input/output interface means for providing respective ones of said computers with the ability to broadcast messages simultaneously to the remainder of said computers; and

,

(c) meshwork communications network means interconnecting respective ones of said second input/output interface means for providing respective ones of said computers with the ability to establish a communications link with another of said computers through said bypass means of the remainder of said computers.

20. The computer system of claim 19 wherein:

said first input/output interface means each includes detecting and terminating means for detecting a collision between messages being broadcast over said global communications network means and for terminating the broadcasting of a message in favor of a message with superior right to use of said global communications network means whereby collisions between messages form a plurality of said computers are detected and avoided, said detecting and terminating means comprising,

said messages broadcast by said computers over said global communications network means each including a leading module identifying portion; and

,

said first input/output interface means each including means for testing the last bit broadcast contents of said global communications network means as messages from its associated said computer are being broadcast over said global communications network means on a bit-by-bit basis and for terminating the broadcasting of a message when said last bit broadcast contents of said global communications network means is not identical to the previous bit indicating that another said computer was first in time on said global communications network means.

21. The computer system of claim 20 wherein additionally:

said messages broadcast by said computers over said global communications network means each include a priority code preceding said module identifying portion whereby another said computer which was first in time on said global communications network means will automatically relinquish said global communications network means to the message of another said computer which is of a higher priority.

22. The computer system of claim 20 wherein additionally:

(a) said messages broadcast by said computers over said global communications network means each include a fixed length non-data portion immediately following said module identifying portion;

(b) said first input/output interface means at each said computer includes first logic means for broadcasting a data bit over said global communications network means during said fixed length immediately following non-data portion when it has terminated the sending of a message as a result of a detected collision; and

,

(c) said first input/output interface means at each said computer further includes second logic means for testing said global communications network means during said fixed length immediately following non-data portion and for not immediately broadcasting a new message following the termination of a broadcast message when said data bit is detected during said fixed length immediately following non-data portion whereby a said computer which has control of said global communications network means will relinquish said global communications network means for the message of another said computer which has previously relinquished said global communications network means whereby computer lockout from access to said global communications network means is prevented and equal access to all said computers is guaranteed.

23. The computer system of claim 19 wherein:

(a) said messages broadcast by said computers over said global communications network means each include a cyclic redundancy check code for the preceding bits and a fixed length trailing non-data portion;

(b) said first input/output interface means at each said computer includes third logic means for testing each said message as received by means of said cyclic redundancy check code and for broadcasting a data bit over said global communications network means during said fixed length trailing non-data portion as a result of messages received with errors; and

,

(c) said first input/output interface means at each said computer further includes fourth logic means for testing said global communications network means during said fixed length trailing non-data portion and for rebroadcasting its last broadcast message as not having been received if it senses said data bit during said fixed length trailing non-data portion.

24. The computer system of claim 20 wherein:

(a) said bypass means of said second input/output interface means at each said computer includes a receiver for receiving inputs to the associated said computer, a transmitter for transmitting outputs from the associated said computer, a plurality of inputs and outputs connected to respective ones of said inputs and outputs of others of said computers interconnected by said meshwork communications network means, and crossbar switch means interconnecting said inputs and said outputs for bypassing said receiver and said transmitter at the associated said computer and for interconnecting one of said plurality of inputs to one of said plurality of outputs whereby a bypass link between said ones of said plurality of inputs and outputs is established.

25. The computer system of claim 24 wherein:

said bypass means of said second input/output interface means at each said computer includes means for sensing a unique signal on said meshwork communications network means indicating that said bypass link is to be terminated and for causing said crossbar switch means to open said bypass link when said unique signal is sensed.

26. The computer system of claim 24 wherein:

said bypass means of said second input/output interface means at each said computer includes repeater means for inverting the clock pulses passing through said crossbar switch means and for resampling data passing therethrough with said inverted clock pulses whereby narrowing of data pulses and loss of synchronization between data passing therethrough and the clock pulses associated therewith is eliminated.

27. A computer interconnecting system for interconnecting a plurality of computers for the transfer of data systems therebetween comprising:

(a) each computer having input/output interface means for interfacing to a communications network, each said input/output interface means including bypass means for bypassing the associated computer with a bit stream passing through said input/output interface means;

(b) meshwork communications network means interconnecting respective ones of said input/output interface means for providing respective ones of the computers with the ability to establish a communications link with another of the computers through said bypass means of the remainder of the computers;

(c) said bypass means of said input/output interface means at each computer including a receiver for receiving inputs to the associated computer, a transmitter for transmitting outputs from the associated computer, a plurality of inputs and outputs connected to respective ones of said inputs and outputs of others of the computers interconnected by said meshwork communications network means, crossbar switch means interconnecting said inputs and said outputs for bypassing said receiver and said transmitter at the associated computer and for interconnecting one of said plurality of inputs to one of said plurality of outputs whereby a bypass link between said ones of said plurality of inputs and outputs is established;

(d) said bypass means of said input/output interface maens at each computer includnig means for sensing a unique signal on said meshwork communications network means indicating that said bypass link is to be terminated and for causing said crossbar switch means to open said bypass link when said unique signal is sensed; and

,

(e) said bypass means of said input/output interface means at each computer further including repeater means for inverting the clock pulses passing through said crossbar switch means and for resampling data passing therethrough with said inverted clock whereby narrowing of data pulses and loss of synchronization between data passing therethrough and the clock pulses associated therewith is eliminated.

28. In a computer system comprising a plurality of computers and a communications network interconnecting respective ones of the computers for allowing respective ones of the computers to broadcast messages to all the computers simultaneously and for allowing respective ones of the computers to transmit and receive data and function initiations to and from others of the computers, the improvement comprising:

(a) each computer being controlled by a resident copy of a common operating system; and

,

(b) the initiation of functions within respective ones of the computers being accomplished by the broadcasting of function tokens as messages on the communications network means; and

wherein,

(c) communication and transfer of both function tokens and data between respective ones of the computers is by means of split tokens each having a moving first portion which is transmitted as a message from computer to computer and a resident second portion which is disposed in the memory of at least one of said computers and wherein the location address of said second portion is contained in said first portion.

29. The improvement to a computer system of claim 28 wherein:

(a) selected ones of said function tokens are duplicate tokens which cause the associated function to be executed in at least two separate ones of the computers; and

,

(b) said common operating system at each computer includes logic for sensing duplicate tokens, for voting on the results produced by the associated function at each computer, and for selecting for use the said results with the highest probability of being correct.

30. The improvement to a computer system of claim 28 wherein:

said broadcasting of said function tokens is initiated by the broadcasting as messages on the communications network of data tokens required for the performance of a function.

31. The improvement to a computer system of claim 28 wherein:

selected ones of said function tokens have a time of execution associated with them and said broadcasting of said function tokens is initiated by the associated said time of execution being reached.

32. The improvement to a computer system of claim 31 wherein:

the communications network includes means for maintaining a common system time employed by the computers for time based activities and the time stamping of said tokens.

33. The improvement to a computer system of claim 28 wherein:

said moving first portion of said split tokens is broadcast over said communications network means to all said computers simultaneously and said resident second portion is transferred over the communications network only between a computer wherein it is resident and a computer requiring it to execute a function.