Electrical computers and digital data processing systems: input/ – Input/output data processing – Input/output access regulation
Reexamination Certificate
1998-12-04
2001-03-06
Luu, Le Hien (Department: 2152)
Electrical computers and digital data processing systems: input/
Input/output data processing
Input/output access regulation
C710S022000, C710S039000, C710S028000
Reexamination Certificate
active
06199124
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to computer systems and arbitration for a shared data transfer resource, and specifically to transfer of data between a host memory and a network adapter through a shared bus.
BACKGROUND
In computer networks, network adapters are used to connect host computer systems to external computer networks. A network adapter is typically coupled with the host computer system through a shared data transfer resource, such as a peripheral bus or system bus. Also normally accessible through the shared bus is a host memory, in which data structures that are shared between the adapter and the host computer system are stored. The host memory typically contains data in the form of cells or packets that are to be transferred to the network adapter and subsequently transmitted onto the computer network. Further, the host memory is used to store cells and packets written by the network adapter after the cells and packets are received from the computer network.
The shared bus that is used to couple the network adapter with the host computer system is shared among multiple competing processes within the network adapter. These processes must be granted access to the shared bus in a manner that is fair and which guarantees minimal service levels negotiated for virtual circuits created by the host computer system through the network adapter. Access to the bus by requesters within the network adapter is effectuated by granting access to a set of logic that operates the bus for the network adapter, such as a Direct Memory Access (DMA) logic.
For example, in computer networking technologies such as Asynchronous Transfer Mode (ATM), virtual circuits are established having several negotiated performance parameters. These performance parameters are known as Quality of Service (QoS) parameters. Quality of Service parameters include average throughput, peak throughput, and latency tolerance. In order that the level of performance guaranteed by the QoS parameters not be compromised, access to any shared resources must be allocated among multiple requesters associated with multiple virtual circuits in accordance with the negotiated quality of service parameters for each virtual circuit. This problem is exacerbated by the large number of virtual circuits permitted in computer network technologies such as ATM.
In an alternative example of modern networking technology, there is also the concept of “flows” for a negotiated service level. In such systems, the service level may be defined on a packet by packet basis, without necessarily setting up virtual circuits, and without creating cells from packets. In this type of system, access to the shared resource must be allocated such that the negotiated service level is similarly maintained, albeit on a packet by packet basis.
A further problem exists in communication of status information from the network adapter to the host computer system. Such information is often passed through the same shared bus resource over which packet or cell data is passed. If this information is not communicated in a timely manner between the network adapter and the host computer system, any efficiencies in moving data between the host and the network adapter will be negated. It is therefore further required that the shared bus be used to communicate status information in a manner that does not adversely effect the transmit or receive performance of the network adapter.
In existing systems, there are a relatively small number of requesters. For example, in a system having only one transmit queue and one receive queue in the host, there can be only a proportionally small number of competing requests for any shared data transfer resource, since the processing within each of the two queues is typically sequential. However, when a large number of independent transmit and receive queues are used, many concurrent requests for access to the shared data transfer resource may be simultaneously present. These multiple concurrent requests must be processed correctly, and with consideration of the relative priority or negotiated service level of each request.
The contents of transmit and receive queues in host memory are generally some number of descriptors, each descriptor identifying an area of host memory in which data is or may be stored. In existing systems, the networking adapter has obtained decriptors and data from the host in a strictly sequential fashion. For example on transmit, the adapter first reads one or more descriptors, followed by the data indicated by those descriptors. When multiple independent queues are used, it is desirable to interleave different types of requests from different data flows, such as requests to move descriptors from a first host queue and requests to move data indicated by descriptors already fetched from a second host queue.
Also in systems using multiple transmit queues within the host computer system, it is impracticable to use a large FIFO in the adapter to store data for each transmit queue. Therefore a system of arbitrating for requests to move data from the multiple transmit queues into the FIFOs within the adapter must efficiently allocate access to any shared data transfer resource. Otherwise a FIFO may be underrun, potentially resulting in the QoS parameters for a connection being violated. This problem is particularly difficult because the future availability of the shared resource may be difficult to predict. Each request for the shared data transfer resource must therefore be processed in a way that avoids underrunning any of the FIFOs such that they do not become empty.
In addition to the above design issues there is also a well known problem of maintaining fairness between transmit and receive operations. Thus it is required that neither transmit nor receive data be given excessive priority over the other.
It is therefore desirable to have a new system for arbitrating between multiple requesters for a shared resource such as a peripheral bus. The new system should be tailored to meet the needs of a network adapter for networking technologies such as ATM. Such a new system should also provide support for Quality of Service requirements of a multiple virtual circuit system such as ATM. And further the system should provide service for a large number of potential requesters. An acceptable degree of fairness must be guaranteed between transmit and receive operations. And the new design should be flexible enough so that parameters may be adjusted to control the eventual service provided to different parts of the system in the network adapter so that fairness is perceived by the eventual users of the network.
SUMMARY
In accordance with principles of the invention, there is provided an arbitration system for multiple requesters of a shared data transfer resource, such as a system bus or a peripheral bus. The disclosed system arbitrates among a large number of request classes which are divided into multiple levels of a request hierarchy. In the example embodiment, the multiple requesters include logic for processing received data from the network, logic for processing data to be transmitted onto the network, logic for moving transmit and receive descriptors between the host memory and the adapter, logic for reporting non-error and maintenance status information from the adapter to the host, and logic for generating error and maintenance status information from the adapter to the host.
In the disclosed embodiment, non-error and maintenance status updates provide information to the host memory such as consumer pointers within the adapter. Error and maintenance status updates provide information to the host memory such as the value of error counters.
The new system ensures fairness between transmit and receive processes, that FIFOs associated with transmit queues are not underrun, and further that notifications of non-error and maintenance status information are processed quickly. Also, latency of delivering received data to the host is minimized.
In a disclosed example embodiment, there is described a
Ben-Nun Michael
Ramakrishnan Kadangode K.
Roman Peter John
Compaq Computer Corporation
Hamilton Brook Smith & Reynolds P.C.
Luu Le Hien
LandOfFree
Arbitration system based on requester class and relative... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Arbitration system based on requester class and relative..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arbitration system based on requester class and relative... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2447642