Abstract:
A PCI (peripheral component interconnect) network adaptor manages read/write requests through the establishment of dynamic queues. The PCI network adaptor establishes a unique queue for each destination node that enables the requests for each node to be processed separately. The PCI network adaptor determines whether a remote read/write request should be added to the linked list for the destination node of the request or whether the request should be rejected. If the number of pending requests for the destination node is below a predetermined threshold and the entire buffer is not full, then the request is added to the linked list for the destination node. Otherwise, the request is rejected. For write requests, if the request is added to the linked list for the destination node, then any pending read requests for that node are aborted.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    1. Field of the Invention  
           [0002]    This invention relates generally to computer networking, and more particularly, to the dynamic buffering of read and write requests over a computer network.  
           [0003]    2. Description of the Related Art  
           [0004]    In a computer network, remote read and write requests are sent via a network router from input/output (I/O) devices to processors at various nodes. A node may be configured as a host processor in which case the I/O devices will be connected to a central processing unit (CPU). A node may alternatively be unintelligent with the I/O devices simply connected to a bus. Each read or write request is addressed to a particular node and each node has a unique amount of traffic at any given time. As a result, some nodes will have a greater latency period than others. If requests for all of the nodes are using the same buffer, then monopolization of the buffer by a slow node can increase the latency time for requests to fast nodes because there will be no remaining buffer space for any requests other than those to the slow node.  
           [0005]    Similarly, if the queuing system is a first-in-first-out (FIFO) system, then one request for a slow node could increase the latency time for all subsequent requests even if those requests are for substantially faster nodes.  
           [0006]    One method for decreasing latency time is to use context switching. Context switching, however, requires the use of complex logic and large amounts of memory to store the contexts.  
           [0007]    Thus, there is a need for a system of buffering read/write requests in a manner that minimizes the latency for each request. The buffering system allows for dynamic queuing such that requests for fast nodes are not affected by requests for slow nodes.  
         SUMMARY OF THE INVENTION  
         [0008]    The present invention includes a PCI (peripheral component interconnect) network adaptor that manages read/write requests through the establishment of dynamic queues. The PCI network adaptor establishes a unique queue for each destination node that enables the requests for each node to be processed separately. This separate processing minimizes the latency time for requests by processing requests for fast destination nodes without delaying for slow destination nodes.  
           [0009]    In one embodiment of the invention, a system includes a network router coupled to two or more PCI network adaptors. Each PCI network adaptor is coupled to a PCI bus and each PCI bus is coupled to one or more devices. The devices communicate remotely with each other using PCI protocols. The devices send read/write requests to various destination addresses via the PCI network adaptor. The PCI network adaptor determines whether each read/write request should be added to the linked list for the destination node of the request or whether the request should be rejected. The PCI network adaptor determines this based on various latency factors associated with the destination node. For instance, if the number of pending requests for the destination node is below a predetermined threshold and the entire buffer is not full, then the request is added to the linked list for the destination node. Otherwise, the request is rejected. For write requests, if the request is added to the linked list for the destination node, then any pending read requests for that node are aborted. Aborting read requests prevents the accessing of data before it has been updated by a pending write request. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0010]    [0010]FIG. 1 is a block diagram of a preferred embodiment of a system including the present invention;  
         [0011]    [0011]FIG. 2 is a block diagram of a preferred embodiment of the PCI network adaptor.  
         [0012]    [0012]FIG. 3 is a flow diagram of a preferred embodiment of a process for receiving and processing write requests.  
         [0013]    [0013]FIG. 4 is a flow diagram of a preferred embodiment of the process for determining whether the write request should be rejected or added to the buffer.  
         [0014]    [0014]FIG. 5 is a flow diagram of a preferred embodiment of a process for receiving and administering read requests.  
         [0015]    [0015]FIG. 6 is a flow diagram of a preferred embodiment of a process for determining whether the read request meets the required criteria.  
         [0016]    [0016]FIG. 7 is a flow diagram of a preferred embodiment of a process for adding a new request to the linked list for a destination node.  
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0017]    [0017]FIG. 1 is a block diagram of a preferred embodiment of a system  100  in accordance with the present invention. In this embodiment, system  100  includes a network router  103 , PCI network adaptors  130 A-C, PCI buses  120 A-C, and devices  110 A-H.  
         [0018]    Each of devices  110  is coupled to a conventional PCI bus  120 . Specifically, in this embodiment, devices A, C and D are connected to PCI bus  120 A, devices B and E are connected to PCI bus  120 B, and devices F, G and H are connected to PCI bus  120 C. Although two or three devices  100  are shown on each PCI bus, one skilled in the art will recognize that either fewer or more devices  100  can be connected to any one bus depending on the desired application and system performance. Each PCI bus  120  is coupled to a PCI network adaptor  130  that provides a PCI interface for implementing conventional PCI protocols and ordering rules. The PCI network adaptors  130 A through  130 C are further coupled to a network router  103 .  
         [0019]    Each of devices  110 A through  110 H may be conventional PCI devices such as displays, disk drives, sound cards or SCSI adapters. Device  110  can also represent a conventional workstation or personal computer on a network, or it can represent an entire network. Alternatively, device  110  can represent a specialized node. For example, device  110  can be a data vault comprising a Direct Memory Access (DMA) device or disk controller card coupled to one or more storage devices. Device  110  can represent either an unintelligent node, such as an I/O device or an intelligent node that has a resident central processing unit (CPU) or microcontroller unit of some kind. In short, device  110  can be any one of a number of devices or node configurations.  
         [0020]    The PCI bus may be a common expansion bus as used in the computer industry for connecting a processor with memory and/or peripheral devices. The PCI network adaptor  130  receives and processes remote read and write requests. The PCI network adaptor  130  is described in further detail below in the discussion of FIG. 2. The network router  103  may be any type of conventional router as used for data transfer over the Internet, an intranet, a local area network or any other networked environment. The various devices send remote read and/or write requests via the PCI bus  120  to the PCI network adaptor  130 . The network adaptor  130  processes the requests using the algorithms discussed below. The requests are then sent via a network router  103  to their respective destination addresses. The processing of the requests ensures that the requests sent to available destination addresses are not delayed by those requests that are sent to slower or unavailable destination addresses.  
         [0021]    [0021]FIG. 2 is a block diagram of a preferred embodiment of a PCI network adaptor  130 . The PCI network adaptor  130  includes a receiving module  202 , an algorithm engine  204 , a response module  206 , a sending module  208 , and a plurality of queues  210 . The receiving module  202  is connected to the algorithm engine  204 . The algorithm engine  204  is connected to both the response module  206  and the sending module  208 . The sending module  208  includes the multiple queues  210 . The receiving module  202  receives read and/or write requests from a requesting device  110  via the network router  103 . The receiving module  202  transfers these requests to the algorithm engine  204 . The algorithm engine  204  processes the requests using the algorithms discussed in FIGS.  3 - 6  below. The algorithm engine  204  generates a result based on these algorithms and sends that result to the response module  206 . The response module  206  may send a response to the requesting device  110  based on the result generated by the algorithm engine  204 . For instance, if the algorithm engine  204  decides to reject a write request, then the response module  206  would send a retry notice to the requesting device  110 . The response module  206  may also send a “request accepted” message or an “abort read request” message. These responses are discussed in further detail below. If the algorithm engine  204  decides to accept the read or write request, then it transfers the request to the sending module  208 . The sending module  208  adds the request to the linked list, or queue  210 , associated with the receiving device  110 . This process is discussed in greater detail in the description of FIG. 7 below. The sending module  208  then sends the request at the head of the queue  210  to the associated receiving device  110 . Note that the elements in the PCI network adaptor  130  may be implemented as hardware or as software stored on a computer readable medium such as a disk and executed by a processor.  
         [0022]    [0022]FIG. 3 is a flow diagram of a preferred embodiment of a process for receiving and processing remote write requests. In this embodiment, a write request includes a destination address and the data to be written to that address. Assume that device  110 A has data to be written to device  110 B. Before device  110 A sends the data to device  110 B, device  10 A must ensure that device  110 B is capable of accepting the data. Device  110 A accomplishes this task by sending a write request, in this case, for device  110 B. The PCI network adaptor  130 A receives  302  this write request and determines whether the request satisfies  304  the criteria for new write requests. These criteria are based on the present capability of device  110 B to receive the data and are discussed in greater detail in the description of FIG. 3, below. If the request does satisfy the criteria for new write requests, then the PCI network adaptor  130 A that is connected to device  110 A adds  306  the request to a linked list for its destination node, here the node containing device  110 B.  
         [0023]    If the request does not satisfy the criteria, then the PCI network adaptor  130 A rejects  310  the request. The PCI protocol used by the PCI network adaptor  130  supports retry functions, thus, a rejected request will be associated with a retry command for that request. The PCI network adaptor  130  may store the data to be written and wait a predetermined period of time before assessing anew whether the request satisfies the criteria for the receiving node. After a certain number of retries, the PCI network adaptor  130  will abort the write request. In this case, the sending device will have to resend the request, thus causing the above process to repeat.  
         [0024]    Once the write request satisfies the criteria for the destination node and the PCI network adaptor  130 A adds  306  the write request to the queue for the destination node, then the PCI network adaptor  130 A aborts  308  any conflicting read requests. For example, if device  110 A has a write request pending in the queue for device  110 B, then the PCI adaptor  130 A would abort any read request pending for device  110 B. Aborting conflicting read requests ensures that data in the pending write request is added to the requested file before it is read. Thus, the read request will access only the most current version of the requested files.  
         [0025]    [0025]FIG. 4 is a flow diagram of a preferred embodiment for the process  304  for determining whether PCI network adaptor  130  should reject a write request or add it to the buffer. Similar to the example discussed above, assume that device  110 A has data to be written to device  110 B. The PCI network adaptor  130 A receives a write request for this data from device  110 A and determines whether the request satisfies  304  the criteria for new write requests. These criteria are based on the present capability of device  110 B to receive the data. Once PCI network adaptor  130 A receives the write request from device  110 A, PCI network adaptor  130 A does an associative look-up  402  of all requests for the destination node. Alternatively, the PCI network adaptor  130 A can count the requests as they arrive and store the total number in memory. The number of requests for the destination node as determined by the associative look-up must be below a predetermined threshold in order to satisfy the criteria. By defining a maximum number of allowable requests for each node, the efficiency of the system can be maximized such that no particular node creates a backlog for the entire PCI bus. Thus, if the number of requests for the destination node is over the threshold, then the criteria is not satisfied  408  and the request is rejected. If the number of requests is not over the threshold, the PCI network adaptor  130 A then checks  406  to see whether there is free space remaining in the buffer. If the buffer is full, then the criteria are not satisfied  408  and the write request is rejected even though the number of requests for the destination node is below the given threshold. If there is space remaining in the buffer, then the write request is accepted.  
         [0026]    [0026]FIG. 5 is a flow diagram of a preferred embodiment of a process for receiving and administering read requests. Assume that device  110 A wants to access or read data stored at device  110 B. Device  110 A would then send a read request to device  110 B via the PCI network adaptor. In this embodiment, the PCI network adapter  130 A receives  502  the read request from device  110 A. If the read request satisfies  504  the required criteria then the PCI network adapter  130 A adds  306  the request to the linked list for the destination device  110 B. If the read request does not satisfy the criteria, then the PCI network adapter  130 A rejects  506  the read request and sends a retry command back to device  110 A. The required criteria for administering read requests are discussed in the following paragraph.  
         [0027]    [0027]FIG. 6 is a flow diagram of a preferred embodiment of a process for determining whether the read request meets the required criteria. If the read/write buffer is full  602 , then the PCI network adapter  130  rejects the read request. Otherwise, the request is added to the queue  210  for the destination device  110 . Since a buffer is required for each device  110  supported by the PCI bus  120 , the overall length of the queue for the destination device  110  is not a factor in the decision to reject the request.  
         [0028]    [0028]FIG. 7 is a flow diagram of a preferred embodiment of a process for adding a new request to the queue  210  for a given device  110 A. The PCI network adaptor  130  accesses  702  the last packet, L, in the queue for device  110 A. The PCI network adaptor  130 A then sets  704  the “next packet” address in the header of packet L to the address for the new request. In this manner, the new request is added to the queue  210  of requests for device  110 A. The new packet is then identified as the last packet in the list in order to enable future requests to be placed in the queue  210  in proper order.  
         [0029]    The foregoing description is offered for illustrative purposes only. Numerous modifications and variations will be apparent to those skilled in the art based upon the foregoing discussion, while still falling within the spirit and scope of the invention claimed below and its equivalents.