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.
USPTO Backgrounds
USPTO Backgrounds