Abstract:
A system and method are provided for using multiple transmit descriptor rings to transmit packets from a computer system. A device driver for a communication interface (e.g., a NIC) receives a packet (e.g., from an upper layer protocol), selects one of the multiple rings and places the packet on the ring. Because the rings are managed in a mutually exclusive manner, packets can be placed on more than one ring at the same time (e.g., by different processors), thus allowing them to be populated in parallel, rather than serially. To select a ring, a packet&#39;s destination address, destination port or other characteristic may be hashed, or a modulo of that characteristic over the number of rings may be calculated. Illustratively, all packets in one connection or flow are transmitted through the same ring.

Description:
BACKGROUND  
         [0001]    This invention relates to the field of computer systems. More particularly, a system and methods are provided for load balancing the transmission of packets through a communication interface among multiple transmit descriptor rings.  
           [0002]    In traditional computing systems, an outgoing packet is formatted according to one or more higher layer protocols (e.g., IP—Internet Protocol, TCP—Transport Control Protocol) and then passed to a communication interface (e.g., a network interface card or NIC) by an interface device driver.  
           [0003]    However, the transition from software handling (e.g., by upper layer protocols and the device driver) to hardware processing (e.g., in the communication interface) forms a chokepoint in the transmission process. In particular, typically only one packet at a time could be passed to the communication interface. This limitation is the result of having only one transmit descriptor ring for transferring packets to the interface. Regardless of how many packets the device driver may have to pass to the interface, only one descriptor, representing one packet, could be configured at a time.  
           [0004]    Therefore, regardless of the number of processors in a computer system, or the data rate at which a communication interface could transmit packets, data transmission could be limited by the rate at which descriptors could be configured in the transmit descriptor ring. The communication interface may be able to transmit packets from a descriptor ring faster than packets could be placed on the ring.  
           [0005]    Thus, there is a need for a system and method of passing multiple packets from a device driver to a communication interface at substantially the same time (e.g., in parallel).  
         SUMMARY  
         [0006]    In one embodiment of the invention, a system and method are provided for using multiple transmit descriptor rings to transfer packets from a computer system to a communication interface for transmission. In this embodiment, a device driver for a communication interface (e.g., a NIC) receives a packet (e.g., from an upper layer protocol), selects one of the rings and places the packet on the ring. Because the rings are managed in a mutually exclusive manner, packets can be placed on more than one ring at the same time (e.g., by different processors), thus allowing them to be populated in parallel, rather than serially.  
           [0007]    In an embodiment of the invention, all packets in one communication connection (e.g., TCP flow) or all packets directed to one destination address or port may be placed on the same transmit ring. 
       
    
    
     DESCRIPTION OF THE FIGURES  
       [0008]    [0008]FIG. 1 is a block diagram depicting a system for passing packets to a communication interface via multiple transmit rings, in accordance with an embodiment of the present invention.  
         [0009]    [0009]FIG. 2 is a block diagram demonstrating the management of multiple transmit descriptor rings, according to one embodiment of the invention.  
         [0010]    [0010]FIG. 3 is a flowchart illustrating one method of load balancing outgoing packets among multiple transmit rings, in accordance with an embodiment of the invention. 
     
    
     DETAILED DESCRIPTION  
       [0011]    The following description is presented to enable any person skilled in the art to make and use the invention, and is provided in the context of particular applications of the invention and their requirements. Various modifications to the disclosed embodiments will be readily apparent to those skilled in the art and the general principles defined herein may be applied to other embodiments and applications without departing from the scope of the present invention. Thus, the present invention is not intended to be limited to the embodiments shown, but is to be accorded the widest scope consistent with the principles and features disclosed herein.  
         [0012]    The program environment in which a present embodiment of the invention is executed illustratively incorporates a general-purpose computer or a special purpose device such as a hand-held computer. Details of such devices (e.g., processor, memory, data storage, display) may be omitted for the sake of clarity.  
         [0013]    It should also be understood that the techniques of the present invention may be implemented using a variety of technologies. For example, the methods described herein may be implemented in software executing on a computer system, or implemented in hardware utilizing either a combination of microprocessors or other specially designed application specific integrated circuits, programmable logic devices, or various combinations thereof. In particular, the methods described herein may be implemented by a series of computer-executable instructions residing on a suitable computer-readable medium. Suitable computer-readable media may include volatile (e.g., RAM) and/or non-volatile (e.g., ROM, disk) memory, carrier waves and transmission media (e.g., copper wire, coaxial cable, fiber optic media). Exemplary carrier waves may take the form of electrical, electromagnetic or optical signals conveying digital data streams along a local network, a publicly accessible network such as the Internet or some other communication link.  
         [0014]    In one embodiment of the invention, a system and method are provided for load balancing the transfer of packets to a communication interface among multiple transmit descriptor rings. In this embodiment, a communication interface device driver is configured to place outbound packets having different destination addresses onto different transmit rings, for transmission by the interface, at substantially the same time. For example, in a computer system having multiple processors, each processor may simultaneously execute a thread or process for placing a packet onto a different transmit ring.  
         [0015]    In different embodiments of the invention, outbound packets may be distributed among the multiple transmit rings based on different factors. In illustrative embodiments, the IP (Internet Protocol) address or TCP (Transmit Control Protocol) port of the destination of the packet may be used. More specifically, the device driver may calculate the modulo of a destination address or port over the number of transmit rings. Thus, all packets within a particular communication connection, or all packets to a particular destination, may be sent through the same transmit ring. This may help ensure that the packets are transmitted in the correct order.  
         [0016]    One skilled in the art will appreciate that embodiments of the invention described herein eliminate congestion and delay that may occur from having all packets passed to a communication interface through a single transmit descriptor ring. In particular, the serial nature of populating one ring is replaced with the ability to populate multiple rings in parallel.  
         [0017]    [0017]FIG. 1 is a block diagram of a computer system in which an embodiment of the invention may be implemented. The computer system of FIG. 1 includes communication interface  102 , which may be a NIC (network interface card), HCA or TCA (Host Channel Adapter or Target Channel Adapter) or some other hardware device configured to transmit a packet onto a communication link. The communication link may be wired or wireless, and may be dedicated (e.g., point-to-point) or shared (e.g., a network, such as the Internet).  
         [0018]    The computer system also includes one or more processors  104 . Thus, the computer system may be an SMP (Symmetric Multi-Processor) computer. Communication interface  102  and processor(s)  104  are coupled to memory  106  (e.g., main memory).  
         [0019]    Memory  106  comprises device driver  112  and two or more transmit descriptor rings—such as rings  114 ,  116 . Device driver  112  is configured to be executed by processor(s)  104  to manage or control operation of communication interface  102 . As described above, transmit rings  114 ,  116  facilitate the passage of outbound packets to communication interface  102  for transmission over a communication link. In different embodiments of the invention, different numbers of transmit rings may be employed.  
         [0020]    When a packet is to be placed on either of rings  114 ,  116 , only that ring needs to be locked. Thus, one processor or thread may be placing a packet on ring  114  while a different processor or thread places a different packet on ring  116 . Parallel population of the rings may allow the communication interface to remove and transmit packets at a more efficient rate.  
         [0021]    Management and scheduling of processes or threads for placing packets onto the rings may be handled by an operating system executed by processor(s)  112 , such as Solaris® by Sun Microsystems, Inc. Illustratively, any thread may place a packet on any transmit ring or, alternatively, a thread may be limited to using a subset of all rings.  
         [0022]    In one embodiment of the invention, the device driver or operating system includes a sequence of programming instructions for creating or instantiating a transmit descriptor ring. Thus, the process of preparing multiple rings is modular and differs from traditional systems in which a monolithic function or procedure was executed to allocate and map memory to set up both transmit and receive descriptor rings at one time.  
         [0023]    [0023]FIG. 2 depicts a structure for managing multiple transmit descriptor rings, according to one embodiment of the invention. In FIG. 2, device information structure  202  is maintained by a device driver for a communication interface, and may store various status and configuration information regarding the interface.  
         [0024]    Device information structure  202  includes a pointer to TX ring pointer array  210 , which contains an element or cell for each transmit descriptor ring established for transferring communications (e.g., packets) to the communication interface for transmission.  
         [0025]    For each ring, a separate ring management structure  220  is instantiated and accessed through TX ring pointer array  210 . Thus, for N rings, N management structures are created. As shown in FIG. 2, management of each ring can be performed independently of the other rings. As a result, when transmission processes or threads are being simultaneously executed on two processors, neither will interfere with the other.  
         [0026]    In an embodiment of the invention, a mapping or initialization function for creating the rings is invoked during initialization of the communication interface&#39;s device driver. Illustratively, the mapping function allocates and initializes an individual transmit descriptor ring and therefore may be called once for each ring to be instantiated.  
         [0027]    Another function for unmapping or tearing down a ring may be invoked during removal or reconfiguration of the device driver. This function would reverse the allocation (e.g., of memory) and initialization performed during the map function.  
         [0028]    The following pseudo-code demonstrates an illustrative procedure for placing a packet onto one of a plurality of transmit descriptor rings:  
         [0029]    ring_index=0/* assign default ring */  
         [0030]    if (ip_packet)  
         [0031]    {get tcp_port /* identify destination port */ ring_index=tcp_port% num_rings /* get ring index */ } 
         [0032]    ring=device→tx_ring[ring_index]/* identify ring */  
         [0033]    start(device, ring, mp) /* put packet on ring */  
         [0034]    In this pseudo-code, the ring_ndex is an index into an array of pointers to, or identifiers of, the multiple transmit rings (e.g., TX ring pointer array  210  of FIG. 2). For each communication interface, a data structure is maintained by the device driver and includes or provides access to the array (e.g., device information structure  202  of FIG. 2). This structure is called “device” in the pseudo-code. The “start” function identifies the communication interface the packet is being provided to (e.g., via its device information data structure), the selected transmit ring (“ring”) and the packet (e.g., “mp” includes a pointer to the buffer containing the packet).  
         [0035]    [0035]FIG. 3 demonstrates a method of using multiple transmit rings for the transmission of packets, according to one embodiment of the invention.  
         [0036]    In operation  302 , an outbound packet is formatted according to TCP and IP. In other embodiments of the invention, a packet may be formatted according one or more different upper layer protocols.  
         [0037]    In operation  304 , the packet is received at a device driver for a communication interface (e.g., a NIC) that will transmit the packet over a communication link (e.g., the Internet). The device driver may also receive other information, such as a destination address or a communication connection that includes the packet.  
         [0038]    In operation  306 , the device driver identifies a destination address/port of the packet. This identification may be made based on other information provided to the device driver in operation  304 . Or, the device driver may parse the packet to access the desired address (or port). In this embodiment, the destination address corresponds to a protocol at layer three or higher of the packet&#39;s protocol stack.  
         [0039]    In operation  308  the device driver selects one of multiple transmit rings, based on the destination address of the packet or the connection or flow that it belongs to. Illustratively, the driver calculates a hash of the destination address or computes the modulo of the packet&#39;s destination address over the number of transmit rings (e.g., destination address MOD number of rings). Therefore, in this embodiment of the invention, the same transmit ring may be selected for all packets sent to the same destination address, or all packets within one communication connection.  
         [0040]    For any packet not formatted according to a predetermined set of protocols (e.g., TCP and IP), a default ring may be selected.  
         [0041]    In operation  310 , the packet is placed on the selected ring. This may entail configuring a descriptor within the ring to identify a buffer in which the packet is stored. This may also involve the translation or mapping of the buffer from a virtual address to an input/output (e.g., physical) address understood by the communication interface. Because there are multiple transmit rings, different packets may be placed on different rings simultaneously or nearly simultaneously.  
         [0042]    In operation  312 , the communication interface takes the packet and transmits it over a communication link. The illustrated method then ends.  
         [0043]    In the embodiment of the invention depicted in FIG. 3, the communication interface treats each transmit ring with the same priority. Thus, it may transmit packets from the rings in a round-robin or other fair scheme. Similarly, the device driver may view each transmit ring as having the same priority, so that packets (or communication connections) may be relatively evenly distributed among the rings.  
         [0044]    Although packets or connections are distributed among the multiple transmit rings on the basis of their destination addresses in the embodiment of FIG. 3, in other embodiments of the invention, other means of selecting a ring may be used. For example, a timestamp, checksum or other characteristic of a connection or the first packet of a connection may be hashed to identify a ring for all packets within the connection.  
         [0045]    The foregoing embodiments of the invention have been presented for purposes of illustration and description only. They are not intended to be exhaustive or to limit the invention to the forms disclosed. Accordingly, the scope of the invention is defined by the appended claims, not the preceding disclosure.