Abstract:
An apparatus and method are provided for scheduling transmit network events in a multiprocessing environment. Each processing node handles its own linked list of transmit object queues and linked list of transport queues. Therefore efficient handling of the transmit network events is enabled. Queues may be added, made inactive, or removed depending on the status of a specific transmit event the queue handles. By maintaining queues in memory, the apparatus is easily scalable, in linear relationship with the size of the memory made available.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    1. Field of the Invention  
           [0002]    The present invention relates to the management of network transmission events handled by a multiprocessing system. More specifically, the invention relates to a highly scalable apparatus for managing termination of transmission transport via a plurality of transmit transport queues (TTQs).  
           [0003]    2. Background of the Related Art  
           [0004]    In the related art, operation in multiprocessing environments can handle tasks requiring a significant amount of computing power, which is best achieved by a plurality of processors operating in parallel. Over time, it has become easier in the related art to integrate more than one processing node on a single chip and thus create a more powerful related art parallel processing unit. While the foregoing related art parallel processing unit is highly effective in general processing applications, there exist other areas where it would be advantageous to employ multiprocessing, such as network processing.  
           [0005]    In network processing, many events occur in parallel over short periods of time, and are generally independent of one another. For example, a file transfer protocol (FTP) session initiated by one user may be handled in parallel to another FTP session initiated by that same user or by another user. Also, other types of protocols may be handled in parallel.  
           [0006]    In the above related art example, each FTP session generates its own events that follow FTP requirements, but are independent of each other. To achieve higher throughput for FTP in the related art system, these FTP sessions should be handled in parallel.  
           [0007]    Network traffic is transported over the related art network using transmission control protocol (TCP) or user datagram protocol (UDP). TCP is used when a reliable transport medium is required, and is applied in the related art as described below.  
           [0008]    TCP is a connection-oriented transport protocol that sends data as unstructured streams of bytes by sending a sequence of segments (i.e., a collection of data bytes sent as a single message) individually through the network. By using a sequence number and acknowledgment messages, TCP provides the source node with status of the bytes transmitted to the destination node. When data is lost during transmission, TCP can resend lost data, thereby ensuring reliable connectivity.  
           [0009]    The related art TCP data transport process is as follows. First, the data (i.e., a file or a message) is broken into segments. To properly break up the data, the TCP must be notified of the size of the segments that the network is capable of handling, which may vary over time depending on network conditions.  
           [0010]    Next, a header is affixed to the beginning of each segment. The header includes information related to the transmission of the segment, such as the source address, the destination address, the source port and destination port numbers, checksum information, segment length and a byte sequence number. In the header information, the checksum field contains a digest of the header and the payload, and confirms correct reception of data. The segment length field of the header specifies the number of payload bytes contained in the segment, and the sequence number of the header indicates the position of the last byte of the segment in the continuous byte stream.  
           [0011]    After affixing the header, TCP sends the datagram to the destination and waits for an acknowledgement indicating successful transmission. The acknowledgment message may be piggybacked on an incoming segment directed to the source. If the sender (i.e., the source node) does not receive the acknowledgement message within a defined amount of time, the source node resends the unacknowledged bytes.  
           [0012]    At the destination node, TCP receives the segment and performs a checksum test. If checksum test passes and no data bytes were lost, the destination TCP acknowledges the source TCP, as described above. Thus, the transmission process is complete.  
           [0013]    In the related art, scaling software-based solutions for higher performance is considered a significant challenge, because the related art system usually correlates the number of bits per second to be transferred with the number of instructions per second to be processed. Accordingly, at the TCP level, it would be necessary for processors to be capable of providing performance of 10 giga instructions per second for a 10 Gbps network, resulting in a very high related art system cost.  
           [0014]    With the advent of related art high speed network systems capable of transmission at speeds of over one gigabit per second (e.g., related art 1 Gbps and 10 Gbps systems) it would be advantageous to move the related art software based activities for TCP to a hardware environment. However, the related art does not include such a solution for TCP.  
           [0015]    Therefore, the related art system has various problems and disadvantages. For example, but not by way of limitation, the related art system cannot produce the aforementioned desired high performance, because of the above-noted deficiencies of the related art software TCP system. As noted above, attempting such a high performance software solution would have a tremendously high cost due to its complexity.  
           [0016]    Further, the challenges that require addressing in a multiprocessing environment for termination of transmit transport in a computer network are substantially different from the challenges of general application multiprocessing. For example, but not by way of limitation, traffic flowing over the network must be handled efficiently without impacting overall system performance.  
         SUMMARY OF THE INVENTION  
         [0017]    It is an object of the present invention to overcome the various problems and disadvantages of the related art.  
           [0018]    It is also an object of the present invention to provide an easily scalable hardware solution for processing TCP level activities.  
           [0019]    It is another object of the present invention to provide a plurality of processing nodes, in hardware that operate in parallel for TCP processing activities.  
           [0020]    To achieve at least the foregoing objects, an apparatus for managing a host event of transmission between a first node and a second node is provided, comprising a queue manager and scheduler (QMS), coupled between a first memory and at least one processor, and a data manager coupled between a second memory and the at least one processor, wherein the QMS and the data manager are configured to communicate with one another via an interface.  
           [0021]    Additionally, a method of handling a transmit transport protocol termination of a host event between a source to a destination is provided, comprising the steps of (a) receiving a host event request by a source coupled to a destination, and placing the host event request in a first queue, (b) identifying the host event and transferring handling of the identified host event to a second queue, and (c) prefetching and forwarding control information corresponding to the host event from the source to a processing node allocated to handle the second queue. The method also comprises (d) handling the identified host event in the processing node, and (e) receiving an acknowledgement from the destination indicative of one of: (i) successful completion of the host event and subsequently releasing the second queue from further handling of the identified host event, and (ii) unsuccessful completion of the host event and subsequently maintaining control of the second queue to complete the host event, wherein the first queue and the second queue correspond to the host event.  
           [0022]    Further, a queue management system is also provided, comprising An apparatus for handling transmit transport protocol termination of a host event of a connections between a source and a destination, comprising a queue manager and scheduler (QMS) that receives the host event and schedules the host event for handling by an object queue. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0023]    The accompanying drawings, which are included to provide a further understanding of preferred embodiments of the present invention and are incorporated in and constitute a part of this specification, illustrate embodiments of the invention and together with the description serve to explain the principles of the drawings.  
         [0024]    [0024]FIG. 1 illustrates a schematic block diagram of an apparatus according to an exemplary description of the present invention;  
         [0025]    [0025]FIG. 2 illustrates a schematic block diagram of the functionality of the queues according to the present invention;  
         [0026]    FIGS.  3 (A)- 3 (D) illustrate exemplary descriptions of data transmission over an open connection link according to the present invention; and  
         [0027]    [0027]FIG. 4 illustrates an exemplary method according to the preferred embodiment of the present invention. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0028]    Reference will now be made in detail to the preferred embodiment of the present invention, examples of which are illustrated in the accompanying drawings. In the present invention, the terms are meant to have the definition provided in the specification, and are otherwise not limited by the specification. Further, advantages of these and the stated objects reside in the details of construction and operation as more fully hereinafter described and claimed, reference being made to the accompanying drawings forming a part hereof, wherein like numerals refer to like parts throughout.  
         [0029]    For purposes of the present invention, the following definitions are provided.  
         [0030]    However, the definitions are merely exemplary, and are not intended to limit the scope of those terms as would be understood by one of ordinary skill in the art. For example, but not by way of limitation, “network event” may be defined as an event where information is passed over a network, either downstream (i.e., source to destination) or upstream (i.e., destination to source); “network connection” may be defined as a connection between a source node and a destination node opened on a network. Further, “host event” may be defined as a network event where information is sent from a host to the system of the present invention for TCP level processing (e.g., a transmit event, including, but not limited to, the receipt of commands from a host and protocol time-out events). Also, “queue event” may be defined as sending a work item descriptor (WID), as defined in more detail below, from a queue to a processing node.  
         [0031]    [0031]FIG. 1 illustrates a non-limiting exemplary block diagram of a hardware apparatus  100  for scheduling network events, and specifically host events, in a multiprocessing environment according to the present invention. The apparatus  100  includes a queue manager and scheduler (QMS)  110 , one or more processing nodes (PN)  120 - 1  . . .  120 - n , a data manager (DM)  130 , a first memory  140  coupled to the DM  140  via an interface  160 , and a second memory  150  coupled to the QMS  110  via an interface  155 . Typically the first memory  140  is implemented using dynamic random access memory (DRAM), and the second memory  150  is implemented using static random access memory (SRAM).  
         [0032]    Information on host events is received over an interface  151 , where control information is transferred to the QMS  110  and data is transferred to the DM  130 . Data is transferred between the DM  130  and the first memory  140  as each PN  120  has one or more direct memory access (DMA) engines that enable the PN  120  to pre-fetch data relevant to its activity prior to the PN  120  commencing work on a scheduled queue event.  
         [0033]    The first memory  140  stores information related to host events, packets received from the network, and data products that are the result of PN  120  processing. However, the first memory  140  is not limited thereto, and may also store other data.  
         [0034]    The second memory  150  is used for the implementation of a plurality of queues, wherein each queue is associated with a single PN  120 . Each queue may also include pointers, including (but not limited to) pointers to the first and last memory object descriptor (MOD) associated with the queue, and offset fields, as described in greater detail below.  
         [0035]    Queues may be opened, closed, or made inactive, all per network connection and as may be necessary for the processing of host events, as further explained below.  
         [0036]    Each PN  120  has a local memory for local processing and a code memory  115  that can be loaded with instructions (e.g., code) to perform tasks relative to the processing required by a host event or queue event. Each PN  120  is also capable of handling multiple queues.  
         [0037]    [0037]FIG. 2 illustrates an exemplary diagram of the operation of the queues according to the present invention. For example, but not by way of limitation, two groups of queues are shown. Queues “0”, “1” and “2” belong to a first linked queue group, and queues “3” and “4” belong to a second linked group. Each queue may have a plurality of memory object descriptors (MODs). The queues and MODs are located in the second memory  150 , and the MODs are added to the queue as new host events.  
         [0038]    The MOD according to the present invention has pointers, including, but not limited to, a pointer to a memory location, such as a memory location where a control data block (CDB) is stored, or a pointer to another MOD. If the MOD is the last MOD in the series, then the next MOD pointer may be set to null.  
         [0039]    To efficiently handle a host event such as transmit events, information for a next transmit event is placed in a local memory of the PN  120 - 1  prior to processing of the transmit event to ensure that PN  120 - 1  is efficiently used, and to ensure that time is not wasted fetching information from remote memory locations. However, blocks of data requiring transfer from one location to another are not moved at this time, as they are not necessary for the processing itself and are simply to be moved from the source node to the destination node. Once a PN  120 - 1  is ready to handle its next task, it can do so with minimal task switching time.  
         [0040]    [0040]FIG. 3A illustrates an exemplary transmission of two kilobytes of data according to the present invention. It is assumed that a connection is established and the necessary queues are available and opened upon the detection of the connection type. An object queue  320  associated with PN  120 - 1 , and a TCP transmit queue (TTQ)  330  associated with PN  120 - 2 , are made available for the connection, and reside in the second memory  150 . Both the object queue  320  and the TTQ  330  may be associated with a single PN, for example PN  120 - 1 , or may be associated with different PNs, as illustrated in FIG. 3A.  
         [0041]    Data is transmitted from a host memory  300  to a destination node as follows. The host memory  300  sends the command data block (CDB) to apparatus  100 , hence initiating a host event. The CDB includes (but is not limited to) a pointer to the data in host memory  300 , a place holder pointer to a protocol data unit (PDU) header to be created by the PN  120 - 1  based on information contained in the CDB, and control information.  
         [0042]    The apparatus  100  stores the received CDB in the first memory  140 . Upon receiving the CDB, object queue  320  allocates a single MOD  310 , which is located in the second memory  150  and includes a pointer to the received CDB. A PN (e.g., PN  120 - 1 ) creates the PDU header based on the control information in the CDB that is pointed to by MOD  310 . The PDU header is stored in the first memory  140 .  
         [0043]    [0043]FIG. 3B illustrates an exemplary association of the TTQ  330  to the object queue  320  according to the present invention. PN  120 - 1  allocates and subsequently links new MODs  340  and  350  to the TTQ  330 . TTQ  330  includes several pointers, such as an MOD identification (MODID) pointer, an offset pointer, and a metadata pointer (MDP). The pointers are described below. MODs  340  and  350  are necessary so as to handle data in two separate memories, memory  140  and host memory  300  respectively.  
         [0044]    The MODID points to the next MOD to be used, e.g., MOD  340 . The offset pointer is used as an offset value to the pointer of the MOD pointed to by MODID pointer and the offset pointer is used in conjunction with pointers  345  and  355 , as explained below. The MDP points to the last transmitted byte that has received an acknowledgement message from the destination. MOD  340 , in the second memory  150 , includes the pointer  345  that points to the beginning of the PDU header located at the first memory  140 , and MOD  350  includes the pointer  355  that points to the beginning of the data  400  (e.g., the two kilobytes of data in host memory  300  to be transmitted to a destination).  
         [0045]    [0045]FIG. 3C illustrates an exemplary process of transmitting data according to the present invention. Once the MOD  340  and the MOD  350  are initialized, the TTQ  330  sends a work item descriptor (WID) to PN  120 - 2 . The WID includes the number of bytes in host memory and the size of the PDU header. After execution of the task corresponding to the sent WID, PN  120 - 2  sends TTQ  300  an acknowledge message (PN_ACK). The PN_ACK includes the number of bytes that PN  120 - 2  actually transmitted. For example, but not by way of limitation, if host memory  300  has 2 KB (i.e., 2048 bytes) to transmit and the PDU header size is 48 bytes, then TTQ  330  sends a WID with the value of  2096  bytes, i.e., 2048+48. Subsequently, PN  120 - 2  will send PN_ACK with the number of bytes actually transmitted. For example, but not by way of limitation, the PN_ACK value may be lower than the WID value.  
         [0046]    Next, the PDU header is transmitted by PN  120 - 2 , and the MOD  340  is used as the MODID in the TTQ  330  and initially points to the MOD  340 . The offset value begins as zero, and is added to the pointer value in MOD  340 . Thus, the content of the PDU header is transmitted.  
         [0047]    As the data pointed to by MOD  340  is processed, the pointer to the next MOD, pointed to by MOD  340 , is used by TTQ  330  to update the value of MODID. The MOD  350  is pointed to by the TTQ  330 . In addition, the value of the offset pointer is again set to zero.  
         [0048]    It should be noted that the corresponding MDP is not updated at this time, and is only updated on receipt of an acknowledgement message from the destination to indicate that the respective bytes have been received. If PN  120 - 2  sends a PN_ACK with a value of 1072 bytes, i.e. 1024+48, indicative of half of the transmissions being completed, TTQ  330  updates the offset pointer value to 1024. As a result, the value of the MOD  350  pointer plus the offset pointer at TTQ  330  (i.e., the pointer  355 ) points to the middle  405  of the 2 KB data block at host memory  300 . Hence, the last 1024 bytes at host memory  300  are pointed to for subsequent transmission, as shown by the broken line in FIG. 3C.  
         [0049]    After the first 1 KB (i.e., 1024 bytes) of data is transferred to the destination, the following steps occur. Because not all of the data has been sent, first, TTQ  330  sends a new WID to PN  120 - 2  indicative of the remaining data to be transferred, e.g., 1 KB. A process substantially similar to the process described above takes place once more, to ensure transmission of the remaining data to its designated destination. MDP is changed only when the destination node sends an acknowledgement message, indicative of the number of bytes received by the destination node (e.g., at a user&#39;s computer).  
         [0050]    The status of the pointers after the completion of the transmission is shown in FIG. 3D. In contrast to FIG. 3C, pointer  355  in FIG. 3D, which is the combination of the pointer value from MOD  350  and the offset value residing in TTQ  330 , points from the host to the end  410  of data in memory  300 . In this non-limiting, exemplary embodiment, FIG. 3C illustrates that only 1 KB of data has been sent. However, once this sequence has been repeated, the pointer is updated as illustrated in FIG. 3D to indicate that all of the 2 KB of data has been sent. However, it is also possible that not all of the data would be sent after the 1 KB had been sent such that multiple iterations of the process would be required to complete the data transmission. In such a case, the pointer  355  would be updated accordingly to point to the next byte to be sent, and the sequence is repeated until all bytes are sent. The offset value enabling this resides in TTQ  330  as mentioned above.  
         [0051]    Accordingly, the pointers are invalidated, or released, only when the destination node acknowledges that substantially all of the data was received are the pointers removed (i.e., the MODs are invalidated from their reference to the TTQ  330 ). The pointers are invalidated, or released, at this point to ensure that the system according to the present invention retains the ability to re-transmit if a part of the data was not received by the destination node. The above-described process performed by PN  120 - 2  may be performed in various time slots allowing PN  120 - 2  the opportunity to handle other processes or tasks.  
         [0052]    [0052]FIG. 4 illustrates an exemplary method according to the present invention. The details of the steps of the method are described above with respect to FIGS.  3 A- 3 D. However, that description is not intended to be limited thereto. In step S 410 , a network request, in the form of a CDB, is received from the source (i.e., first node).  
         [0053]    As noted above, the source is coupled to a destination (i.e., second node).  
         [0054]    Next, at step S 420 , the host event request is placed in the object queue, which is located in memory  150 , and queue management is performed by the QMS  110 . The respective CDB, handled by the object queue and pointed to by an MOD associated with that object queue, is stored in memory  140 .  
         [0055]    Then, at step S 430 , the PDU is created by the processing node that is handling the respective object queue, and is placed in memory  140 . At step S 440 , handling of the host event is transferred to a TTQ designated to handle the host event of the identified type. The MOD that handled the CDB in conjunction with the object queue is then released, and MODs, respective of the designated TTQ pointing to the PDU header in memory  140  and to the data in memory  300 , are enabled.  
         [0056]    At step S 450 , the TTQ sends a WID (e.g., information on the number of bytes to be transmitted and the PDU header size) to processing node  120 - 1 . In the preferred embodiment of the present invention, the data necessary for the operation of the processing node is pre-fetched to the local memory of the processing node. At the processing node, the initiation of data transfer from memory  300  to destination, the update of MODs, pointers and offsets, is handled at step S 460 .  
         [0057]    Once the host, event has been handled as described above, an acknowledgement message is expected at step S 470 . At step S 480 , it is determined whether all the data from memory  300  has been sent. If all the data was not sent, the execution continues with step S 450 .  
         [0058]    However, if all the data has been sent, execution continues with step S 490 , where it is determined whether all the data sent has received an acknowledgment. If the answer is affirmative, then execution ends with step S 495 , where the MODs respective of the TTQ are released. However, if not all the data has been acknowledged as received by the destination, execution continues with step S 470  to allow, if necessary, retransmission of unacknowledged data as would be detected by step S 480 .  
         [0059]    In the foregoing exemplary method, the object queue and the TTQ are allocated in the second memory  150 . In one embodiment of the invention, both queues are configured to share the same processing node  120 - 1 , based on a queue prioritization process. The processes may include, but are not limited to, round robin, weighted round robin, random and least recently prioritized. In another embodiment, each queue is handled by a different processing node. An object queue may point to another object queue, while a TTQ may point to another object queue. Linked queues may be handled by a single processing node.  
         [0060]    The processing nodes can include a local memory and the code memory  115 -n. The code memory can include downloadable memory. Additionally, the code memory can be a direct memory access controller (DMAC) that interfaces with the second memory  150 , the local memory and the host (i.e., source node) memory.  
         [0061]    Additionally, each of the queues points to the MOD, and as noted above, the MOD may point to another MOD, which points to a third MOD. The MOD can also point to the CDB, which stores control information as well as information on the location of data in the first node (i.e., host). As discussed above, the second queue comprises the MODID pointer, the offset pointer and the metadata pointer.  
         [0062]    The present invention has various advantages. For example, but not by way of limitation, the present invention is easily scalable, in linear relationship with the size of the memory made available. Additionally, the invention overcome at least the aforementioned problems and disadvantages of the related art.  
         [0063]    It will be apparent to those skilled in the art that various modifications and variations can be made to the described preferred embodiments of the present invention without departing from the spirit or scope of the invention. Thus, it is intended that the present invention cover all modifications and variations of this invention consistent with the scope of the appended claims and their equivalents.