Speculative prefetch of a protocol control block from an external memory unit

According to some embodiments, a protocol control block is speculatively pre-fetched from an external memory unit.

BACKGROUND

Devices may exchange information via a communication network. For example, a server may exchange packets of information with a user device, such as a Personal Computer (PC), via the Internet. Moreover, a single device, such as a server, may exchange information with a number of different devices through a number of different connections. In this case, the device may need to manage the connections and associate each packet that is received (or that is to be transmitted) with an appropriate connection. These operations may be time-consuming and might require a significant amount of memory (which can increase the cost of the device)—especially for relatively high-speed networks and/or when a relatively large number of connections can be supported.

DETAILED DESCRIPTION

According to some embodiments, information is exchanged via a communication network. For example,FIG. 1is a block diagram of a communication network100in which “packets” of information are exchanged between a user device110and a server200. As used herein, a “packet” of information may be exchanged, for example, using Internet Protocol (IP), such as the one defined by the Internet Engineering Task Force (IETF) RFC 2460 entitled “Internet Protocol, Version 6” (December 1998). Moreover, the packets may be exchanged in accordance with Transmission Control Protocol (TCP) as defined by the IETF Request For Comment (RFC)793entitled “Transmission Control Protocol” (September 1981).

FIG. 2is a block diagram of a server200. The server200includes a host processor210(e.g., one or more INTEL® PENTIUM® 4 processors) coupled to a memory unit230and an Input Output Controller Hub (ICH)240through a Memory Controller Hub (MCH)220, such as the Intel® 82875P. The server200also includes a Network Interface Card (NIC)250that may exchange packets of information in accordance with TCP/IP via a communication network, such as the Internet or a Local Area Network (LAN).

In accordance with TCP/IP, the server200may exchange packets with a number if different devices by establishing one or more “connections” with each device. When a packet is received by (or is to be sent from) the server200, TCP processing is performed on the packet (e.g., to associate the packet with the appropriate connection). The maintenance of TCP connections and the processing of packets may require the use of several variables, referred to as a TCP Protocol control block (TCB). For example, the TCB may include local and remote socket numbers, the security and precedence of a connection, pointers to send and receive buffers, and/or pointers to a retransmit queue and to a current segment. In addition, variables relating to send and receive sequence numbers may be stored in the TCB.

The TCB information232may be stored in the memory unit230. Moreover, the host processor210may perform TCP processing (e.g., when a packet is received or is to be sent). It may be impractical, however, to have the host processor210perform the TCP processing, especially for relatively high-bandwidth networks and/or when a significant number of connections need to be managed (e.g., the server200may be capable of managing tens of thousands of connections).

To reduce the burden on the host processor210, a TCP/IP offload engine270may be provided on the NIC250. In this case, the TCP/IP offload engine270may perform TCP processing when a packet is received or when a packet is ready to be sent. For example, after TCP processing is performed on a received packet, the appropriate information can be stored in the memory unit230for use by the host processor210(e.g., by an application executing on the host processor210).

To perform the TCP/IP processing, the offload engine270may need to fetch from the “external” memory unit230(e.g., external to the NIC250) the TCB information232associated with the appropriate connection. Note, however, that the NIC250may access information from the external memory unit230via a relatively slow interface260(e.g., as compared to the other MCH220interfaces), such as one that operates in accordance with the Peripheral Component Interconnect (PCI) Standards Industry Group (SIG) standards entitled “Conventional PCI 2.2” or “PCI Express 1.0.” Note that according to some embodiments, the PCI interface260may receive information directly from the ICH240.

To avoid frequent and time-consuming accesses to the external memory unit230, the NIC250may include a local TCB cache280that stores TCB information. When the server200is capable of managing a large number of connections, however, it might be impractical to store all of the TCB information232in the TCB cache280(e.g., because of the cost associated with providing the large amount of memory that would be required). Thus, even with a local TCB cache280the NIC250may need to frequently access the external memory unit230.

FIG. 3is a timeline300that illustrates packet processing. After one packet (packet0) is processed by the TCP/IP offload engine270, the next packet (packet1) needs to be processed. Before packet1can be processed, however, the offload engine270may need to fetch from the external memory unit230the TCB associated with packet1's connection. After the TCB for the appropriate connection is received by the offload engine270(e.g., after TLATENCY), the packet can be processed (e.g., and, in the case of a received packet, be provided to the host processor210). Thus, there may be periods of time when the offload engine270is idle (e.g., while the fetch is being performed).

FIG. 4is a flow chart of a method according to some embodiments. The flow charts described herein do not necessarily imply a fixed order to the actions, and embodiments may be performed in any order that is practicable. The method ofFIG. 4may be associated with, for example, the server200described with respect toFIG. 2. Note that any of the methods described herein may be performed by hardware, software (including microcode), or a combination of hardware and software. For example, a storage medium may store thereon instructions that when executed by a machine result in performance according to any of the embodiments described herein.

At402, a device predicts or “speculates” that a connection will subsequently have a packet to be processed in accordance with a transmission control protocol (e.g., TCP). For example, the offload engine270or host processor210may speculate that a particular connection will subsequently have a packet that will be received by (or that will be sent from) the server200.

At404, it is arranged for a packet processing engine to pre-fetch from an external memory unit a protocol control block associated with the connection. For example, it may be arranged for the offload engine270pre-fetch the appropriate TCB from the external memory unit230.

By pre-fetching the appropriate protocol control block before a packet is received (or before a packet needs to be sent), the amount of idle time associated with the packet processing engine may be reduced—and the performance of a server may be improved. For example,FIG. 5is a timeline500that illustrates packet processing when a TCB is pre-fetched according to some embodiments.

While one packet (packet0) is still being processed by the TCP/IP offload engine270, the offload engine270pre-fetches the TCB associated with another packet's connection from the external memory unit230(e.g., another connection for which it has been predicted that another packet, namely packet1, will subsequently be received or sent). In this way, the offload engine270can continue to process packet0while the pre-fetch is being performed (e.g., via a relatively slow interface). Thus, periods of time during which the offload engine270is idle may be reduced.

Several different techniques may be used to speculate which connections will subsequently have a packet that is received (or is to be sent). For example, the server200may exchange Hyper-Text Transfer Protocol (HTTP) information as defined by the Word Wide Web Consortium (W3C) RFC 2068 entitled “HTTP 1.1” (January 1997). In this case, when the server200receives a packet for a particular connection (e.g., an HTTP “get” from a particular client), it can be predicted that the server200will subsequently respond with one or more packets through that same connection (e.g., when sending packets associated with an HTTP “send” to that client). Similar predictions may be made when information is exchanged in accordance with the IETF RFC 3347 entitled “Small Computer Systems Interface Protocol Over the Internet (iSCSI) Requirements and Design Considerations” (July 2002)—namely an iSCSI “request” packet through a particular connection may subsequently result in one or more iSCSI “send” packets through that connection.

Note that the offload engine270may process a large number of packets for a large number of connections, but the size of the TCB cache280on the NIC250may be limited. As a result, TCB information that is pre-fetched too soon (e.g., too long before it is needed) could be lost because it has been overwritten with information for other connections.

For example,FIG. 6is a timeline600that illustrates receive packet processing. After an iSCSI request packet is received through a particular connection and is processed by the offload engine270, the information is passed to the host processor210. An application executing on the host processor210processes the information (e.g., for a period of time equal to TPROCESS) and provides an iSCSI response packet to the offload engine270for delivery through the same connection.

If the offload engine270had pre-fetched the appropriate TCB information for that connection too soon before the iSCSI response packet was ready, the information in the TCB cache280may have already been overwritten with information for other connections. The TCB information would then need to be re-fetched for that connection in order to process the iSCSI response packet, resulting in a total turnaround time (TTURNAROUND) of TPROCESS+TLATENCY. Note also that if the offload engine270waits too long before starting to pre-fetch the TCB information for a connection, it may need to remain idle until the pre-fetch from the external memory unit230is completed.

FIG. 7is a flow chart of a method of receive packet processing according to some embodiments. At702, a packet is received. For example, the server200may receive the packet at the offload engine270or the host processor210.

Based on the receive packet, it is predicted at704that a connection will subsequently have a send packet to be processed. For example, the offload engine270may predict that the connection associated with the receive packet will subsequently have a send packet. According to other embodiments, the host processor210predicts that the connection will subsequently have a send packet.

A processing time associated with the receive packet is estimated at706. For example, the offload engine270or host processor210might estimated how long will take for an application to respond to the receive packet (e.g., TPROCESS).

At708, a latency associated with pre-fetching the protocol control block from external memory is estimated. For example, the offload engine270or host processor210may estimate how long will take for a TCB pre-fetch to be performed via the PCI interface260, MCH220, and/or external memory unit230(e.g., TLATENCY).

A pre-fetch for the predicted send packet is then scheduled at710based on the estimated processing time and latency of the pre-fetch. For example, the pre-fetch may be scheduled based on TPROCESS−TLATENCY. In this way, the pre-fetch should complete just as the send packet for that connection is ready.

At712, the pre-fetch is performed. For example, the offload engine270might pre-fetch the TCB information and store it in the TCB cache280as scheduled. When the send packet is provided from the host processor210to the offload engine270, it can then be processed without waiting for the TCB information to be received from the external memory unit230(or without waiting for a significant period of time).

FIG. 8is a timeline that illustrates receive packet processing when a protocol control block is pre-fetched according to some embodiments. After the receive packet is processed by the offload engine270and is provided to the host processor210, a pre-fetch for that connection is scheduled at a pre-fetch time (TPF) equal to the estimated TPROCESSreduced by the estimated TLATENCY. In this way, the pre-fetch may be completed at substantially the same time as associated send packet through that connection is provided from the host processor210to the offload engine270. The offload engine270may then process and transmit the send packet without unneeded idling (e.g., during TLATENCY).

Note that TPROCESScould vary for any number of reasons (e.g., due to the number of connections being handled by the host processor). Similarly, TLATENCYmight change over a period of time (e.g., because of memory accesses being performed for other reasons). As a result, according to some embodiments these estimated values are dynamically tuned or adjusted (e.g., by the offload engine270and/or the host processor210) to improve the performance of the server200. For example, prior actual values could be used to adjust future estimate values.

FIG. 9is a flow chart of a method of send packet processing according to some embodiments. At902, a packet is ready to be sent. For example, the server900may be ready to send the packet from the offload engine270or the host processor210.

Based on the send packet, it is predicted at904that a connection will subsequently have a receive packet to be processed. For example, the offload engine270might predict that the connection associated with the send packet will subsequently have a receive packet. According to other embodiments, the host processor210predicts that the connection will subsequently have a receive packet.

A “round-trip” time associated with the send packet is estimated at906. For example, the offload engine270or host processor210might estimated how long it will take for the send packet to reach a user device through a network, be processed by the user device, and result in a receive packet being received by the server200(e.g., TROUND-TRIP).

At908, a latency associated with pre-fetching the protocol control block from external memory is estimated. For example, the offload engine270or host processor210might estimate how long will take for a TCB pre-fetch to be performed via the PCI interface260, MCH220, and/or external memory unit230(e.g., TLATENCY).

A pre-fetch for the predicted receive packet is then scheduled at910based on the estimated round-trip time and latency of the pre-fetch. For example, the pre-fetch may be scheduled based on TROUND-TRIP−TLATENCY. In this way, the pre-fetch should complete at substantially the same time as the send packet for that connection is received from the network.

At912, the pre-fetch is performed. For example, the offload engine270may pre-fetch the TCB information and store it in the TCB cache280as scheduled. When the receive packet is then received at the offload engine270(from the network), it may be processed without waiting (or without waiting too long) for the TCB information to be received from the external memory unit230.

FIG. 10is a timeline that illustrates send packet processing when a protocol control block is pre-fetched according to some embodiments. After the send packet is processed and sent through a network, a pre-fetch for that connection is scheduled at a pre-fetch time (TPF) equal to the estimated TROUND-TRIPreduced by the estimated TLATENCY. In this way, the pre-fetch may be completed at substantially the same time as associated receive packet through that connection is received from the network. The offload engine270may then process and provide the receive packet to the host processor210without an unnecessary delay (e.g., during TLATENCY).

Note that TROUND-TRIPcould vary for any number of reasons (e.g., due to network congestion). Similarly, TLATENCYmight change over a period of time (e.g., because of memory accesses being performed for other reasons). As a result, these estimated values might be dynamically adjusted (e.g., by the offload engine270and/or the host processor210) to improve the performance of the server200. For example, information from the TCP/IP stack might be used to dynamically adjust the estimated TROUND-TRIPfor a connection.

FIG. 11is a block diagram of a system1100according to some embodiments. The system1100includes a Dynamic Random Access Memory (DRAM)1130storing protocol control block information1132. The system1100also includes a packet processing engine1170to process packets in accordance with any network protocol (e.g., TCP). The packet processing engine1170may process a packet, for example, in accordance with a locally stored protocol control block1180associated with the connection through which the packet was (or will be) exchanged.

According to some embodiments, the locally stored protocol control blocks1180are pre-fetched from the protocol control block information1132in the external DRAM1130. For example, a pre-fetched protocol control block for a connection predicted to subsequently have a packet to be processed by the packet processing engine1170may be received (e.g., via an input path) from the DRAM1130.

Note that the packet processing engine1170might predict the connection and calculate a time when the protocol control block should be pre-fetched from the DRAM1130. This could be achieved, for example, by keeping timers at the packet processing engine1170(or on an associated NIC) with entries for all of the TCB entries that will need to be pre-fetched. This, however, might increase the complexity of the NIC hardware and/or software.

According to other embodiments, a host processor predicts the connection and calculates a time when the pre-fetched protocol control block should be “pushed” to the packet processing engine1170from the DRAM1130. For example, the host processor may read the TCB and then push the TCB down through a MCH to the packet processing engine1170or the push might be performed through un-cached writes to a NIC followed by a NIC initiated Direct Memory Access (DMA) operation.

The following illustrates various additional embodiments. These do not constitute a definition of all possible embodiments, and those skilled in the art will understand that many other embodiments are possible. Further, although the following embodiments are briefly described for clarity, those skilled in the art will understand how to make any changes, if necessary, to the above description to accommodate these and other embodiments and applications.

For example, although same embodiments have been described with respect to TCP packet processing, embodiments may be used in connection with other network protocols, such as User Datagram Protocol (UDP), Transactional TCP (T/TCP), and/or Stream Control Transmission Protocol (SCTP). Moreover, the term “protocol control block” may refer to any information used when processing a packet in accordance with any network protocol (e.g., not just TCB information for TCP).

In addition, although some embodiments have been described with respect to servers, embodiments may be used in connection with other devices, such as a workstation or any other type of network device.

The several embodiments described herein are solely for the purpose of illustration. Persons skilled in the art will recognize from this description other embodiments may be practiced with modifications and alterations limited only by the claims.