Method, system, and program for managing congestion in a network controller

[0001] U.S. patent application, entitled “Method, System and Program for Overrun Identification,” Ser. No. 10/745,774, filed Dec. 24, 2003.

[0002] In a network environment, a network adapter or controller such as an Ethernet controller, Fibre Channel controller, etc., will receive Input/Output (I/O) requests initiated by an application operating in the host computer in which the adapter resides. Often, the host computer operating system includes a device driver to communicate with the network adapter hardware to manage I/O requests to transmit or receive data over a network.

[0003] Many network controllers have a buffer to receive large bursts of incoming data traffic. Notwithstanding this buffering capacity, network controllers are subject to an “overflow” condition when the rate of incoming traffic exceeds the rate at which the data of the traffic can be processed. When an overflow condition occurs, the network controller typically drops some of the incoming data because the network controller is unable to store the data for processing.

[0004] These overflow conditions may occur as a result of a surge in incoming traffic. However, overflow conditions may also be artificially induced through malicious behavior such as a “denial-of-service” attack. In either case, data loss may occur.

[0005] The host computer may also employ a protocol which packages the data to be transmitted over the network into packets, each of which contains a destination address as well as a portion of the data to be transmitted. A protocol layer can also process the packets received by the network adapter that are stored in the packet buffer, and access any I/O commands or data embedded in the packet.

[0006] For instance, the computer may employ the TCP/IP (Transmission Control Protocol and Internet Protocol) to encode and address data for transmission, and to decode and access the payload data in the TCP/IP packets received at the network adapter. IP specifies the format of packets, also called datagrams, and the addressing scheme. TCP is a higher level protocol which establishes a network connection between a destination and a source according to the TCP protocol.

[0007] In accordance with the TCP protocol, a TCP stack hosted by the host computer may advertise a TCP “receive window” which the data packet sender can utilize to restrict the transmission of data to the data recipient host computer. Typically, the size of the TCP receive window is set by the host computer in accordance with the buffer space set aside for data packet reception.

[0008] A device driver, application or operating system can utilize significant host processor resources to handle network transmission requests to the network adapter. One technique to reduce the load on the host processor is the use of a TCP/IP Offload Engine (TOE) in which TCP/IP protocol related operations are embodied in the network adapter hardware as opposed to the device driver or other host software. As a-result, the host processor can be relieved from performing some or all of the TCP/IP protocol related operations.

[0009] A TOE or other offload engine can speed the processing of incoming traffic and thereby alleviate some overflow conditions. However, because a TOE may utilize a network controller buffer for a number of tasks in addition to those typically handled by a network controller lacking a TOE, additional opportunities for packet loss may occur. For example, a TOE device may retain packets or segments of data in a buffer for reassembly, defragmentation or retransmission processing. In a network controller lacking a TOE, such data may be immediately forwarded to the host computer for processing rather than being retained in the network controller for processing. Hence, buffer space which may otherwise be available for incoming data may be consumed by TOE processing. Furthermore, buffer space may be used for non-TCP traffic such as the User Datagram Protocol (UDP), Internet Control Message Protocol (ICMP), non-IP traffic as well as non-offloaded TCP flows. Hence, these non-TCP traffic flows can consume buffer space which may have been advertised as available to TCP flows. Still further, a host based TCP stack may have significantly greater buffer space residing in the host system memory as compared to that typically available to the TOE in local memory.

[0010] As previously mentioned, output buffers can fill during periods of congestion. When the buffers are full, “tail drop” is likely to occur, that is, additional packets are likely to be dropped. In accordance with the known TCP protocol, dropping packets can cause the packet sender to reduce the rate of transmission to reduce congestion. Since the packets are often dropped all at once, global synchronization of TCP hosts can occur as multiple TCP hosts reduce their transmission rates. Once the congestion clears, the TCP hosts can increase their transmissions rates, resulting in waves of congestion followed by periods where the transmission link is not fully used.

[0011] There are known techniques for reducing or avoiding overflow conditions. The Random Early Detection (RED) technique randomly selects one or more “victim” packets and drops them to reduce traffic flow. RED can reduce the chances of tail drop by selectively dropping packets when the interface begins to show signs of congestion. By dropping some packets early rather than waiting until the buffer is full, RED can, in some instances, avoid dropping large numbers of packets at once and can reduce chances of global synchronization. In addition, RED statistically tends to drop more packets from large users than small. Therefore, traffic sources that generate the most traffic may, in some applications, be more likely to be slowed down than traffic sources that generate little traffic.

[0012] Another known technique is the Weighted Random Early Detection (WRED) technique in which packets having a high IP precedence are less likely to dropped than packets with a lower precedence. In accordance with the known TCP protocol, packet header bits can define IP precedence factors such as minimum delay, maximum throughput, maximum reliability or minimum cost. These factors may be utilized to assign an IP precedence. A “Distributed Weighted Random Early Detection” technique can run on Versatile Interface Processor (VIP)-distributed processors and may provide additional functionality such as minimum and maximum queue depth thresholds and drop capabilities for each class of service.

[0013] A “Flow-based Weighted Random Early Detection” technique can provide a feature of WRED that forces a WRED policy to afford greater fairness to all flows on an interface in regard to how packets are dropped. More specifically it is believed that when a flow exceeds a per-flow limit, the probability that a packet from that flow will be dropped increases.

[0014] Notwithstanding, there is a continued need in the art to improve the performance of data reception and other operations.

[0026] In the following description, reference is made to the accompanying drawings which form a part hereof and which illustrate several embodiments of the present disclosure. It is understood that other embodiments may be utilized and structural and operational changes may be made without departing from the scope of the present description.

[0027] FIG. 1 illustrates an example of a computing environment in which aspects of described embodiments may be employed. A computer 102 includes one or more central processing units (CPU) 104 (only one is shown), a memory 106, non-volatile storage 108, a storage controller 109, an operating system 110, and a network adapter 112. An application 114 further executes in memory 106 and is capable of transmitting and receiving packets from a remote computer. The computer 102 may comprise any computing device known in the art, such as a mainframe, server, personal computer, workstation, laptop, handheld computer, telephony device, network appliance, virtualization device, storage controller, storage controller, etc. Any CPU 104 and operating system 110 known in the art may be used. Programs and data in memory 106 may be swapped into storage 108 as part of memory management operations.

[0028] The storage controller 109 controls the reading of data from and the writing of data to the storage 108 in accordance with a storage protocol layer 111. The storage protocol of the layer 111 may be any of a number of known storage protocols including Redundant Array of Independent Disks (RAID), High Speed Serialized Advanced Technology Attachment (SATA), parallel Small Computer System Interface (SCSI), serial attached SCSI, etc. Data being written to or read from the storage 108 may be cached in accordance with known caching techniques. The storage controller may be integrated into the CPU chipset, which can include various controllers including a system controller, peripheral controller, memory controller, hub controller, I/O bus controller, etc.

[0029] The network adapter 112 includes a network protocol layer 116 to send and receive network packets to and from remote devices over a network 118. The network 118 may comprise a Local Area Network (LAN), the Internet, a Wide Area Network (WAN), Storage Area Network (SAN), etc. Embodiments may be configured to transmit data over a wireless network or connection, such as wireless LAN, Bluetooth, etc. In certain embodiments, the network adapter 112 and various protocol layers may employ the Ethernet protocol over unshielded twisted pair cable, token ring protocol, Fibre. Channel protocol, Infiniband, etc., or any other network communication protocol known in the art. The network adapter controller may be integrated into the CPU chipset, which can include various controllers including a system controller, peripheral controller, memory controller, hub controller, I/O bus controller, etc.

[0030] A device driver 120 executes in memory 106 and includes network adapter 112 specific commands to communicate with a network controller of the network adapter 112 and interface between the operating system 110, applications 114 and the network adapter 112. As used herein, an application 114 can include a driver which is at a higher level than the device driver 120 for the network adapter 112, and can also include portions of the operating system 110. The network controller can include the network protocol layer 116 and can control other protocol layers including a data link layer and a physical layer which includes hardware such as a data transceiver.

[0031] In certain embodiments, the network controller of the network adapter 112 includes a transport protocol layer 121 as well as the network protocol layer 116. For example, the network controller of the network adapter 112 can include a transport protocol controller such as a TOE, in which many transport layer operations can be performed within the network adapter 112 hardware or firmware, as opposed to the device driver 120 or other host software.

[0032] The transport protocol operations include obtaining transmit data placed in an application buffer residing in the system memory 106, temporarily storing the transmit data in a buffer such as a network controller buffer 125, packaging the transmit data in TCP/IP packets with checksum and other information and sending the packets. These sending operations are performed by an agent which may be embodied in a TOE, a network interface card or integrated circuit, a driver, TCP/IP stack, a host processor or a combination of these elements. The transport protocol operations also include receiving a TCP/IP packet from over the network, temporarily storing the received packets in a buffer such as the network controller buffer 125, and unpacking the TCP/IP packet to access the payload data. These receiving operations are performed by an agent which again, may be embodied in a TOE, a driver, a host processor or a combination of these elements.

[0033] The network layer 116 handles network communication and provides received TCP/IP packets to the transport protocol layer 121. The transport protocol layer 121 interfaces with the device driver 120 or operating system 110 or an application 114, and performs additional transport protocol layer operations, such as processing the content of messages included in the packets received at the network adapter 112 that are wrapped in a transport layer, such as TCP and/or IP, the Internet Small Computer System Interface (iSCSI), Fibre Channel SCSI, parallel SCSI transport, or any transport layer protocol known in the art. The transport protocol layer 121 can unpack the payload from the received TCP/IP packet and transfer the data to the device driver 120, an application 114 or the operating system 110.

[0034] In certain embodiments, the network controller and network adapter 112 can further include an RDMA (Remote Direct Memory Access) protocol layer 122 as well as the transport protocol layer 121. For example, the network controller of the network adapter 112 can include a Remote Direct Memory Access (RDMA) enabled Network Interface Card (RNIC), in which RDMA layer operations are performed within the network adapter 112 hardware, as opposed to the device driver 120 or other host software. Thus, for example, the system 102 can receive messages over an RDMA connection through the device driver 120, the transport protocol layer 121, the RDMA protocol layer 122 and the other protocol layers of the network adapter 112 including the data link and physical protocol layers.

[0035] The memory 106 further includes file objects 124, which also may be referred to as socket objects, which include information on a connection to a remote computer over the network 118. The application 114 uses the information in the file object 124 to identify the connection. The application 114 uses the file object 124 to communicate with a remote system. The file object 124 may indicate the local port or socket that will be used to communicate with a remote system, a local network (IP) address of the computer 102 in which the application 114 executes, how much data has been sent and received by the application 114, and the remote port and network address, e.g., IP address, with which the application 114 communicates. Context information 126 comprises a data structure including information the device driver 120, operating system 110 or an application 114, maintains to manage requests sent to the network adapter 112 as described below.

[0036] In the illustrated embodiment, the CPU 104 programmed to operate by the software of memory 106 including one or more of the operating system 110, applications 114, and device drivers 120 provides a host which interacts with the network adapter 112. A host may be embodied in a variety of devices such as a host computer 102 or other devices. In the illustrated embodiment, a data send and receive agent includes the transport protocol layer 121 and the network protocol layer 116 of the network interface 112. However, the data send and receive agent may be embodied in a TOE, a network interface card or integrated circuit, a driver, TCP/IP stack, a host processor or a combination of these elements. The network controller may comprise hardware, software, firmware or any combination of these elements.

[0037] FIG. 2 illustrates a format of a network packet received at or transmitted by the network adapter 112. A data link frame 148 uses a format understood by the data link layer, such as 802.11 Ethernet. Details on this Ethernet protocol are described in “IEEE std. 802.11,” published 1999-2003. An Ethernet frame includes additional Ethernet components, such as a header and an error checking code (not shown). The data link frame 148 includes a network packet 150, such as an IP datagram. The network packet 150 uses a format understood by the network protocol layer 116, such as such as the IP protocol. A transport packet 152 is included in the network packet 150. The transport packet 152 is capable of being processed by the transport protocol layer 121, such as the TCP. The packet may be processed by other layers in accordance with other protocols including iSCSI protocol, Fibre Channel SCSI, parallel SCSI transport, etc. The transport packet 152 includes payload data 154 as well as other transport layer fields, such as a header and an error checking code. The payload data 152 includes the underlying content being transmitted, e.g., commands, status and/or data. The driver 120, operating system 110 or an application 114 may include a layer, such as a SCSI driver or layer, to process the content of the payload data 154 and access any status, commands and/or data therein.

[0038] In accordance with one aspect of the description provided herein, the likelihood of an overflow condition may be reduced or eliminated by culling low priority traffic when overflow is imminent. The culled low priority traffic may be queued for later processing or discarded entirely. In one embodiment, different types of packets may be recognized and assigned various priority values. The method of priority assignment may be dynamic or programmable. When the protocol layer, embodied in hardware, software or both, detects a potential overrun situation, a priority scheme may be used to discard (or queue) all or substantially all low-priority traffic automatically. As a consequence, resources may be freed for higher-priority connections, allowing them to continue operating with little or no degradation.

[0039] FIG. 3 illustrates one example of operations of a network controller for managing data traffic to reduce or eliminate overflow conditions. In the illustrated embodiment, the network controller is embodied in the network adapter 112 which includes a TOE which provides protocol layer processing including the TCP protocol. It is appreciated that the functions of one or both of the network controller and the TCP stack may be embodied in one or more of hardware, software or firmware, residing in one or more of the network adapter 112, CPU 104, operating system 110 or device driver 120 or other hardware or software modules.

[0040] The network controller determines (block 200) the level of the traffic flowing through the network adapter 112. These levels may include two levels such as light or heavy, for example, or may include several levels such as low, moderate, heavy or very heavy, for example. Other traffic levels may be utilized as well. The traffic levels may be based on a variety of criteria including the space remaining in a TOE buffer 125, the rate of data flow into the network adapter 112 from the network 108 versus the rate of data flow out of the network adapter 112 to the host computer, as well as other factors.

[0041] A priority discrimination level is selected (block 202) as a function of the determined traffic level. The priority discrimination levels which may be selected include two levels such as low or high priority discrimination levels or may include several priority discrimination levels such as low, medium, high or critical priority discrimination levels.

[0042] Packets of incoming traffic may each be assigned (block 204) priority values based upon a variety of criteria as described below. The priority values which may be assigned may include two values such as low or high priority values or may include several priority values such as low, medium, high or critical priority values, for example.

[0043] A determination is made (block 206) as to whether a particular packet has an assigned priority value which is above the selected priority discrimination level. If so, the packet is accepted (block 208) and processed in the usual fashion. On the other hand, if the packet has an assigned priority value which is lower than the selected priority discrimination level, the packet is culled (block 210) and the processing of that packet is deferred or dropped altogether. Such a processing deferment may take the form of placing the packet in a queue to await further processing if resources become available or may include discarding the packet. A discarded packet may then be subsequently processed if resent by the sender and accepted by the network adapter 112 should the priority discrimination level be decreased to permit acceptance of the packet. By processing packets in this manner as traffic levels rise, overflow conditions may be reduced or eliminated.

[0044] As previously mentioned, packets of incoming traffic may each be assigned (block 204) priority values based upon a variety of criteria. Different applications may assign different priority values to different types of traffic. For example, TCP segments carrying large quantities of data may be assigned a high priority value since loss of such a packet may cause the retransmission of all of the data of the lost segment, further adding to congestion problems.

[0045] As another example, IP fragments may be assigned a high priority value. Loss of an IP fragment can reduce or eliminate the value of sibling fragments which have already been retained or processed. In addition, loss of an IP fragment can cause re-fragmentation of the original data and retransmission of each fragment, again possibly aggravating congestion problems.

[0046] Also, TCP acknowledgment packets, referred to as “ACK,” may also be assigned a high priority value in some applications. Loss of an ACK packet can cause data retransmission and interfere with TCP congestion management. Thus, for example zero-length ACK packets may not be dropped in many applications.

[0047] Yet another example of packets which may be assigned a high priority value could include traffic initiated by interactive applications such as, for example, multi-media streams, remote login, etc., in which a user is actively waiting for this traffic. Significant delays or data loss can degrade the “user experience.”

[0048] Conversely, ICMP packets may be assigned a low priority value in some applications. ICMP packets in the IP protocol contain error, control and informational messages. For example, the “ping” command uses ICMP to test an Internet connection. ICMP traffic is often unreliable; therefore the loss of a few ICMP packets may not have significant consequences. Furthermore, it is believed that discarding ICMP traffic during overflow situations can prevent certain types of denial of service attacks such as “smurf” denial of service attacks, for example.

[0049] As another example, real-time or isochronous multi-media traffic may be assigned a low priority value. These types of protocols may elect to ignore lost data, since the delay incurred in retransmitting the data may make the retransmitted data effectively of little or no value to the receiver. For example, resending a portion of audio commentary may not be helpful if the listener has already advanced past that segment of the audio.

[0050] Also, in some applications, Address Resolution Protocol (ARP) or TCP SYN packets may be assigned a low priority value. These packets typically precede the establishment of a network connection to the local host computer. If the controller is already overloaded with traffic, establishing a new connection can aggravate the condition. Furthermore, it is believed that discarding these types of packets in an overload or incipient overload condition can ameliorate or prevent other types of denial of service attacks such as TCP SYN flooding and IP spoofing attacks. It is appreciated that other criteria may be used to assign various priority values to different types of packets.

[0051] FIG. 4 illustrates another example of operations of a network controller for managing data traffic to reduce or eliminate overflow conditions. In this embodiment, incoming packets are examined (block 300) and a priority value is assigned (block 302) each incoming packet. In this example, a packet may be assigned one of four priority values, low, medium, high or critical priority as represented by the four categories, 304a, 304b, 304c or 304d, respectively, in FIG. 5. As previously mentioned, there may be a greater or lesser number of possible priority values, depending upon the particular application.

[0052] Also in this example, the traffic level may be determined to have one of four different possible levels, low, moderate, heavy or very heavy. A traffic level may be assigned a “heavy” designation when overflow conditions become possible, for example. A traffic level may be assigned a “very heavy” designation when overflow conditions are more than possible but are more likely to be imminent. Again, there may be a greater or lesser number of different possible traffic levels, based on these or other criteria, depending upon the particular application.

[0053] If the traffic level is determined (block 308) to be “low”, a first priority discrimination level 310a is selected as shown in FIG. 5. At this level 310a, all packets including low, medium, high and critical priority packets are accepted (block 312) and processed.

[0054] If the traffic level is determined (block 314) to be moderate, a second, higher priority discrimination level 310b is selected. At this priority discrimination level 310b, a determination is made (block 316) as to whether the incoming packet has been assigned a low priority. If not, that is, the incoming packet has a medium, high or critical priority as shown in FIG. 5, the incoming packet is accepted (block 312) and processed.

[0055] If it is determined (block 316) that the incoming packet is a low priority packet, a determination is made (block 320) as to whether a queue for the assigned packet priority is fill. In the illustrated embodiment, four queues, 330a, 330b, 330c, 330d (FIG. 6), are provided for the four packet priority values low, medium, high and critical, respectively.

[0056] Thus, if it is determined (block 316) that the incoming packet is a low priority packet, a determination is made (block 320) as to whether the queue 330a for the packets assigned a low priority value is full. If not, the low priority packet may be queued (block 332) in the queue 330a as shown by a low priority packet 340a. In the illustrated embodiment, the queues 330a, 330b, 330c, 330d may be first in first out (FIFO) queues such that the first packets placed in the queue are the first packets processed should resources permit. It is appreciated, however, that other types of queues may be used as well, depending upon the particular application. In this manner, processing of the low priority packets may be deferred until resource availability permits.

[0057] If it is determined (block 316) that the incoming packet is a low priority packet, and it is determined (block 320) that the queue 330a for low priority packets is full, the low priority packets may be discarded (block 342) until additional space in the queue 330a becomes available as the queued packets are subsequently processed.

[0058] If the traffic level is determined (block 350) to be heavy, a third, still higher priority discrimination level 310c is selected. At this priority discrimination level 310c, a determination is made (block 352) as to whether the incoming packet has been assigned a low or medium priority. If not, that is, the incoming packet has a high or critical priority as shown in FIG. 5, the incoming packet is accepted (block 312) and processed.

[0059] If it is determined (block 352) that the incoming packet is a low or medium priority packet, a determination is made (block 320) as to whether the queue for the assigned packet priority is full. Thus, if it is determined (block 352) that the incoming packet is a low priority packet, a determination is made (block 320) as to whether the queue 330a for the packets assigned a low priority value is full. Alternatively, if it is determined (block 352) that the incoming packet is a medium priority packet, a determination is made (block 320) as to whether the queue 330b for the packets assigned a medium priority value is full. If queue of the assigned priority is not full, an incoming low priority packet may be queued (block 332) in the queue 330a as shown by the packet 340a, for example. Similarly an incoming medium priority packet may be queued (block 332) in the queue 330b for medium priority packets as shown by the packet 340b, for example. In this manner, processing of the low and medium priority packets may be deferred until resource availability permits.

[0060] If it is determined (block 352) that the incoming packet is a low or medium priority packet, and it is determined (block 320) that the associated queue 330a or 330b for packets of the assigned priority is full, the packets of that priority may be discarded (block 342) until additional space in the associated queue 330a or 330b becomes available as the queued packets are subsequently processed.

[0061] If the traffic level is determined (block 350) to be greater than heavy, that is, very heavy, a fourth, still higher priority discrimination level 310d is selected. At this priority discrimination level 310d, a determination is made (block 360) as to whether the incoming packet has been assigned a low, medium, or high priority. If not, that is, the incoming packet has a critical priority as shown in FIG. 5, the incoming packet is accepted (block 312) and processed.

[0062] If it is determined (block 360) that the incoming packet is a low, medium or high priority packet, a determination is made (block 320) as to whether the queue for the assigned packet priority is fill. Thus, if it is determined (block 360) that the incoming packet is a low priority packet, a determination is made (block 320) as to whether the queue 330a for the packets assigned a low priority value is fall. Alternatively, if it is determined (block 360) that the incoming packet is a medium priority packet, a determination is made (block 320) as to whether the queue 330b for the packets assigned a medium priority value is full. Alternatively, if it is determined (block 360) that the incoming packet is a high priority packet, a determination is made (block 320) as to whether the queue 330c for the packets assigned a high priority value is full. If the queue of the assigned priority is not full, an incoming low priority packet may be queued (block 332) in the queue 330a as shown by the packet 340a, for example. Similarly an incoming medium priority packet may be queued (block 332) in the queue 330b for medium priority packets as shown by the packet 340b, for example. Similarly an incoming high priority packet may be queued (block 332) in the queue 330c for high priority packets as shown by the packet 340c, for example. In this manner, processing of the low, medium and high priority packets may be deferred until resource availability permits.

[0063] If it is determined (block 360) that the incoming packet is a low, medium or high priority packet, and it is determined (block 320) that the associated queue 330a, 330b or 330c for packets of the assigned priority is full, the packets of that priority may be discarded (block 342) until additional space in the associated queue 330a, 330b or 330c becomes available as the queued packets are subsequently processed. A queue 330d may be provided for critical priority packets 340d as well.

[0064] In this example, all incoming packets having an assigned priority value below the selected priority level are culled. It is appreciated that in other applications substantially all incoming packets having an assigned priority value below the selected priority level could be culled. For example, 75-100% of the incoming packets having an assigned priority value below the selected priority level could be may be discarded or queued.

[0065] In accordance with another aspect, individual traffic flows may be identified by the controller and packet culling rates may be selected for each traffic flow to reduce or avoid traffic congestion. As a consequence, the rate at which packets are culled from any one flow may be limited to a predetermined maximum, as appropriate. Still further, one or more selected flows may be culled at a high rate which can significantly reduce or eliminate the bandwidth available to those flows, providing substantially greater bandwidth for the remaining flows. Still further, one or more of these techniques may be employed alone or in various combinations as conditions warrant.

[0066] FIG. 7 illustrates another example of operations of a network controller for managing data traffic to reduce or eliminate overflow conditions. In this example, the network controller determines (block 400) the level of the traffic flowing through the network adapter 112. Again, these levels may include two levels such as light or heavy, for example, or may include several levels such as low, moderate, heavy or very heavy, for example. Other traffic levels may be utilized as well. The determination of the traffic levels may be based on a variety of criteria including the space remaining in a TOE buffer, the rate of data flow into the network adapter 112 from the network 108 versus the rate of data flow out of the network adapter 112 to the host computer, as well as other factors.

[0067] The controller also selects (block 402) one or more flows for culling, as a function of the determined traffic level. In a network controller having an offload engine such as a TOE, individual flows of packets may be readily identified by the network protocol connection through which each flows, depending upon the operations being performed at the controller level. In the illustrated embodiment, each individual traffic flow has a separate network protocol connection between a source and a destination. For an incoming flow of packets, the flow of packets can be from a source external to the host computer 102, through a separate network protocol connection, to a destination within the host computer. For example, in the TCP, each packet of a flow of packets in a TCP network connection between a source and a destination has identifier information in the packet header which identifies the TCP network connection to which it belongs and the TCP connection sequence numbers of each byte of the packet flowing through the TCP network connection. Other protocols may be used to establish a separate network protocol connection through which an individual flow of packets may flow.

[0068] Several factors may be used to determine which flow is selected. The factors to be weighed could include the particular protocol, such as TCP, UDP or others, being utilized by the network connection of the flow. Additional weight factors could include the payload or application such as a multimedia application, a backup application etc. Still other weight factors could include IP precedence factors such as minimum delay, maximum throughput, maximum reliability or minimum cost.

[0069] In accordance with another aspect, weight factors could include information which may not be available to a network controller lacking an offload engine such as a TOE. For example, TCP window size, TCP window utilization by a given flow and whether or not a flow is currently offloaded to the TOE device may be considered as well.

[0070] Upon selecting some or all of the flows for culling, a culling rate may be selected (block 404) for each selected flow, as a function of the traffic level. The selected culling rates may be applied (block 406) to toe selected culling rates. For example, as traffic becomes relatively heavy, packets could be culled from each of the traffic flows passing through the network controller. However, a ceiling or maximum culling rate may be selected for each flow. Since packet culling can have a greater impact on smaller flows such as on a percentage of flow basis, for example, imposing such a maximum can ensure that no one flow is disproportionately affected in terms of packet loss.

[0071] As another example, if traffic levels continue to rise, another culling technique may be imposed instead of or in combination with the previously described techniques. For example, one or more flows may be selected for significant or even drastic culling. As a consequence, the effects of congestion may be, in some applications, isolated to a relative few flows while the remaining flows experience little or no degradation due to packet loss.

[0072] FIG. 8 illustrates yet another example of operations of a network controller for managing data traffic to reduce or eliminate overflow conditions. In this embodiment, each incoming flow of packets is identified and assigned (block 430) a priority value. In this example, a flow may be assigned a priority value of high or low. It is appreciated that other priority values may be assigned as well. As previously mentioned, a variety of factors may be utilized to select flows. These and other factors may be weighed to assign priority levels to individual flows of packets from each source to each destination through the network adapter 112.

[0073] Also in this example, the traffic level may be determined to have one of five different possible levels, low, moderate, heavy, very heavy or extremely heavy. Again, there may be a greater or lesser number of different possible traffic levels, based on various criteria for measuring traffic, depending upon the particular application.

[0074] If the traffic level is determined (block 432) to be “low”, all flows of packets may, in this example, be passed (block 434) for processing with no culling from any flow. A “low” traffic level may correspond, for example, with a traffic level in which no congestion is occurring. Similarly, in this example, if the traffic level is determined (block 436) to be moderate, all flows of packets may, in this example, be passed (block 434) for processing with no culling from any flow. A “moderate” traffic level may correspond, for example, with a traffic level in which buffers contain a minor backlog of packets to be processed.

[0075] If the traffic level is determined (block 440) to be “heavy”, culling may be performed (block 442) on one or more flows, such as low priority flows, for example, at relatively low rates for limited periods of time. A “heavy” traffic level may correspond, for example, with a traffic level in which in which significant buffer usage is occurring.

[0076] FIG. 9a illustrates one technique in which a packet flow is culled in culling periods 450a which alternate with non-culling periods 450b in while little or no culling takes place. In this example, a level 452 indicates the maximum number of culled packets, expressed as a percentage of the flow, which are culled in each culling period 450a from each flow selected for culling. The percentage represented by the maximum level 452 will vary, depending upon the particular application.

[0077] Also in the example, the non-culling periods 450b are relatively long as compared to the culling periods 450a. Should the traffic level be determined (block 460) to be “very heavy,” the proportionate lengths of the culling periods 450a relative to the no culling periods 450b may be lengthened (block 462) as shown for example in FIG. 9b. A “very heavy” traffic level may correspond, for example, with a traffic level in which packet loss is imminent.

[0078] In the example of FIG. 9b, the maximum culling level 452 expressed as a percentage may remain the same as the example of FIG. 9a. As a consequence, culling of packets can be increased as traffic levels increase while the maximum percentage being culled from any one flow at a time can remain the same. It is appreciated however, that the maximum culling levels 452 and the lengths of the culling and non-culling periods 450a, 450b may vary, depending upon the particular application as well as upon the particular traffic levels.

[0079] In yet another example, the non-culling periods 450b may eliminated such that a culling period 450a continues uninterrupted as long as traffic conditions warrant. Also, in this example, the culling techniques illustrated in FIGS. 9a, 9b may be applied to all flows, or just the low or lower priority flows or to one or more selected flows, depending upon the particular application.

[0080] If the traffic level is determined (block 470) to be extremely heavy, then, in addition to culling (block 472) one or more flows at a relatively low rate in a manner similar to that illustrated in FIG. 9a, for example, at least one flow, such as a low priority flow, may be selected for culling (block 474) at a substantially higher rate. Such a higher rate may include for example, drastic culling in which all or substantially all packets of the selected flow are culled.

[0081] An “extremely heavy” traffic level may correspond, for example, with a traffic level in which a minor sustained rate of packet loss is encountered. If it is determined (block 470) that the traffic is even higher than extremely heavy, then, in addition to culling (block 476) one or more flows at a relatively low rate but more frequently in a manner similar to that illustrated in FIG. 9b, for example, at least one flow, such as a low priority flow, may be selected for culling (block 478) at a substantially higher rate. A traffic level beyond “extremely heavy” may correspond, for example, with a traffic level in which a significant sustained rate of packet loss is encountered.

[0082] As set forth above, several factors may be used to determine which flow or flows are selected for relatively low rates of culling and which flow or flows are selected for more drastic rates of culling. Furthermore, once a flow is selected to have restricted bandwidth availability, choices may be made as to which packets to drop and which packets to process from the selected flow. For example, in many applications, a primary function of an acknowledgment packet is to update TCP state information. An acknowledgement packet often does not undergo any additional buffering once it is processed in this manner. Accordingly, the network controller may choose to accept acknowledgment packets rather than drop or queue them. Similarly, a packet that completes a set of packets which had been fragmented or completes a partially full receive buffer, may permit the contents of a buffer to be transferred to the host memory. As a consequence, additional buffer space may be freed. Hence, such a packet may also be a candidate for acceptance rather than being dropped.

[0083] By comparison, packets of a flow selected for restriction which may start a new set of defragmented packets to be reassembled, or may be placed in a receive buffer that is not already partially populated, may be candidates for being dropped or queued rather than being processed. It is appreciated that a single packet could both complete a receive buffer and start filling in another buffer. In such a situation, the network controller could drop or queue part of the packet which fills in another buffer, and process the part of the packet which completes a buffer. Because of the byte stream nature of TCP and the acknowledgment mechanism of TCP, it is believed that dropping part of a packet and processing part of a packet is consistent with the protocol specification.

[0084] In another aspect, packets may be dropped which have been buffered but not yet acknowledged as received. For example, fragmented IP datagrams or UDP packets of a selected flow which have been stored in the network controller buffers may be discarded. Accordingly, buffer space freed by discarding unacknowledged packets of the selected flow may be used for the packets of other flows. These weight factors including the identity of the protocol of the flow and the buffer space used by the flow, may be considered in the flow selection process, particularly when a more drastic culling technique is invoked.

[0085] As traffic flow ebbs, culling techniques may be made less restrictive. For example, as traffic flow drops back to extremely heavy, a switch may be made from frequent culling periods 450a as shown in FIG. 9b to less frequent culling periods 450a as shown in FIG. 9a, for example. Also, culling techniques may be dropped as traffic flow drops. For example, as traffic drops from extremely heavy to very heavy, a drastic culling technique (block 474) which substantially reduces or eliminates the bandwidth available to a particular flow may be dropped such that only a less restrictive technique (block 462) such as those shown in FIG. 9b is applied. Once traffic drops even further such as to moderate or low, for example, culling may be dropped altogether until congestion increases again.

[0086] The described techniques for managing memory may be embodied as a method, apparatus or article of manufacture using standard programming and/or engineering techniques to produce software, firmware, hardware, or any combination thereof. The term “article of manufacture” as used herein refers to code or logic embodied in hardware logic (e.g., an integrated circuit chip, Programmable Gate Array (PGA), Application Specific Integrated Circuit (ASIC), etc.) or a computer readable medium, such as magnetic storage medium (e.g., hard disk drives, floppy disks, tape, etc.), optical storage (CD-ROMs, optical disks, etc.), volatile and nonvolatile memory devices (e.g., EEPROMs, ROMs, PROMs, RAMs, DRAMs, SRAMs, firmware, programmable logic, etc.). Code in the computer readable medium is accessed and executed by a processor. The code in which preferred embodiments are employed may further be accessible through a transmission media or from a file server over a network. In such cases, the article of manufacture in which the code is embodied may comprise a transmission media, such as a network transmission line, wireless transmission media, signals propagating through space, radio waves, infrared signals, etc. Thus, the “article of manufacture” may comprise the medium in which the code is embodied. Additionally, the “article of manufacture” may comprise a combination of hardware and software components in which the code is embodied, processed, and executed. Of course, those skilled in the art will recognize that many modifications may be made to this configuration without departing from the scope of the present descriptions, and that the article of manufacture may comprise any information bearing medium known in the art.

[0087] In the described embodiments, certain operations were described as being performed by the operating system 110, system host computer, device driver 120, or the network interface 112. In alterative embodiments, operations described as performed by one of these may be performed by one or more of the operating system 110, system host computer, device driver 120, or the network interface 112. For example, culling operations described as being performed by the network adapter 112 may be performed by the host computer.

[0088] In the described embodiments, a transport protocol layer 121 was embodied in the network adapter 112 hardware. In alternative embodiments, the transport protocol layer may be embodied in the device driver or host memory 106.

[0089] In certain embodiments, the device driver and network adapter embodiments may be included in a computer system including a storage controller, such as a SCSI, Integrated Drive Electronics (IDE), RAID, etc., controller, that manages access to a non volatile storage device, such as a magnetic disk drive, tape media, optical disk, etc. In alternative embodiments, the network adapter embodiments may be included in a system that does not include a storage controller, such as certain hubs and switches.

[0090] In certain embodiments, the device driver and network adapter embodiments may be employed in a computer system including a video controller to render information to display on a monitor coupled to the computer system including the device driver and network adapter, such as a computer system comprising a desktop, workstation, server, mainframe, laptop, handheld computer, etc. Alternatively, the network adapter and device driver embodiments may be employed in a computing device that does not include a video controller, such as a switch, router, etc.

[0091] In certain embodiments, the network adapter may be configured to transmit data across a cable connected to a port on the network adapter. Alternatively, the network adapter embodiments may be configured to transmit data over a wireless network or connection, such as wireless LAN, Bluetooth, etc.

[0092] The illustrated logics of FIGS. 3,4, 7 and 8 show certain events occurring in a certain order. In alternative embodiments, certain operations may be performed in a different order, modified or removed. Moreover, operations may be added to the above described logic and still conform to the described embodiments. Further, operations described herein may occur sequentially or certain operations may be processed in parallel. Yet further, operations may be performed by a single processing unit or by distributed processing units.

[0093] FIG. 10 illustrates one embodiment of a computer architecture 500 of the network components, such as the host computers and storage devices shown in FIG. 4. The architecture 500 may include a processor 502 (e.g., a microprocessor), a memory 504 (e.g., a volatile memory device), and storage 506 (e.g., a non-volatile storage, such as magnetic disk drives, optical disk drives, a tape drive, etc.). The storage 506 may comprise an internal storage device or an attached or network accessible storage. Programs in the storage 506 are loaded into the memory 504 and executed by the processor 502 in a manner known in the art. The architecture further includes a network adapter 508 to enable communication with a network, such as an Ethernet, a Fibre Channel Arbitrated Loop, etc. Further, the architecture may, in certain embodiments, include a video controller 509 to render information on a display monitor, where the video controller 509 may be employed on a video card or integrated on integrated circuit components mounted on the motherboard. As discussed, certain of the network devices may have multiple network cards or controllers. An input device 510 is used to provide user input to the processor 502, and may include a keyboard, mouse, pen-stylus, microphone, touch sensitive display screen, or any other activation or input mechanism known in the art. An output device 512 is capable of rendering information transmitted from the processor 502, or other component, such as a display monitor, printer, storage, etc.

[0094] The network adapter 508 may be embodied on a network card, such as a Peripheral Component Interconnect (PCI) card or some other I/O expansion card coupled to a motherboard, or on integrated circuit components mounted on the motherboard. The host interface may employ any of a number of protocols including PCI EXPRESS.

[0095] Details on the PCI architecture are described in “PCI Local Bus, Rev. 2.3”, published by the PCI-SIG. Details on the TCP protocol are described in “Internet Engineering Task Force (IETF) Request for Comments (RFC) 793,” published September 1981 and details on the IP protocol are described in “Internet Engineering Task Force Request for Comments (RFC) 791, published September 1981. Details on the UDP protocol are described in “Internet Engineering Task Force Request for Comments (RFC) 798, published August, 1980. Details on the Fibre Channel architecture are described in the technology specification “Fibre Channel Framing and Signaling Interface”, document no. ISO/IEC AWI 14165-25. Details on the Ethernet protocol are described in “IEEE std. 802.3,” published Mar. 8, 2002. Details on the RDMA protocol are described in the technology specification “Architectural Specifications for RDMA over TCP/IP” Version 1.0 (October 2003).

[0096] The foregoing description of various embodiments has been presented for the purposes of illustration and description. It is not intended to be exhaustive or to limit to the precise form disclosed. Many modifications and variations are possible in light of the above teaching. It is intended that the scope not be limited by this detailed description.