Methods and apparatus for determination of packet sizes when transferring packets via a network

Two timers are used to improve ingress throughput. Decisions to transfer the ingress packets are made based on when the two timers expire. A first timer is used to time how long a first ingress packet waits before it is transferred. When this first timer expires, the all received ingress packets including the first ingress packet are transferred. A second timer is used to time how long to wait for a new ingress packet to be received. The second timer is reset if a new ingress packet is received before expiration of the second timer. When the second timer expires and no new ingress packet is received during the wait, all received ingress packets including the first ingress packet are transferred.

FIELD OF THE INVENTION

The present invention relates to the field of computer networks, more particularly relating to methods and apparatuses for transmitting and/or receiving packets via a network.

BACKGROUND

A computing platform or device, e.g. a device that handles, stores, displays and/or processes data, such as a computer, may transmit and receive data and/or information in packet format between itself and another device over a communications network. The computing device may include a host memory as well as a local bus coupled to a network adapter.

A communications network may include a plurality of interconnected nodes, and may comprise, for example, without limitation, computers, set top boxes, peripherals, servers and/or terminals coupled by communications lines or other communications channels. A communications network may connect or couple nodes over a local area, such as, for example, a campus, or over a wide area, such as, for example, multiple campuses. A network adapter, also generally known as a network controller or network interface card (NIC), may be coupled to a computing device and used to process data received from and/or transmitted to a communications channel.

Such a network adapter may include its own local memory, an input/output (I/O) controller, and a network transceiver. High-speed I/O controllers are often throughput limited at least in part due to the local bus of the computing device. For example, the peripheral component interconnect (PCI) specification, rev. 2.1, issued Jun. 1, 1995, available from www.pcisig.com, describes, in part, associated overhead for memory transfers. A computing device may transfer signals in a manner that complies with this specification. In such a case, memory transfer operations, such as a, direct memory access (DMA) bus transaction, for example, may be inefficient small transfers, such as less than about 1K bytes of data.

Ethernet data packets typically vary from 64 to 1518 bytes in length. However, a majority of Ethernet data packets tends to be small. As previously indicated, memory transfers of these data packets may be inefficient where the signals employed comply with, for example, the PCI specification.

DETAILED DESCRIPTION

In accordance with one embodiment of the present invention, timers are used to determine if ingress packets received and stored in a buffer are to be transferred. The decisions to transfer the ingress packets are made based on the expiration of the timers. A first timer is used to determine a length of time a first ingress packet waits in the buffer before it is transferred. When the first timer expires, all ingress packets in the buffer including the first ingress packet are transferred. A second timer is used to determine a length of time to wait for a new ingress packet to be received into the buffer. The second timer is reset if a new ingress packet is received before expiration of the second timer. When the second timer expires, all ingress packets in the buffer including the first ingress packet are transferred.

FIG. 1is a block diagram illustrating an example of a communication network. The communication network110includes network nodes111and119. The network node111may include, for example, a computing device112coupled via an I/O bus113to a network adapter120. The computing device112may be any device, machine, computer or processor, such as one that handles, routes, or processes information. The network adapter120may be integrated into the network node111with the computing device112. Alternatively, the network adapter120may be separate from the computing device112. The network adapter120may comprise a single integrated circuit (IC), multiple ICs or may be integrated into circuitry within computing device112.

The network adapter120may be coupled to the network node119via network media114and one or more network infrastructure devices (NIDs), such as NID116. The NID116may comprise, for example, any device capable of routing, switching, repeating or passing data on a network, examples of which may include, without limitation, a router, server, switch and/or hub. The network media114refers to the medium or media through which signals are transferred or transmitted including, but not limited to, optical fiber, cables, and/or radio waves. The computing device112may include a host memory138that may have stored therein ingress packets and/or egress packets. As described above, egress packets are packets of data to be transferred or transmitted from the computing device112via the network media114to the NID116and to the network, and ingress packets are packets of data to be received by the computing device112via the network media114from the network.

FIG. 2Ais a block diagram illustrating examples of packet buffers and associated descriptors. The ingress packets that are received may be stored in packet buffers244(within the memory138in FIG.1). The memory138may also contain buffer descriptors240, and packet descriptors242. The buffer descriptors240may be descriptors that indicate the locations of buffers in memory138allocated for ingress packet storage. The packet descriptors242, on the other hand, may be descriptors that indicate those locations within the allocated buffers that contain the stored ingress packets.

The network adapter120may read data from the host memory138via the bus113and transfer such data as egress packets across the network media114. Likewise, the network adapter120may receive data as ingress packets via network media114and may write the ingress packets into host memory138via the bus113. The computing device112may include program code, including, but not limited to, an operating system (OS) and a device driver, such as device driver137. Typically these instructions are stored in a memory, such as the host memory138. Typically, the computing device112, while executing the OS, may store data to be transmitted as egress packets in the host memory138. The OS may thus provide an indication that such data is available for transfer. Of course, this is a description of only one possible embodiment and the claimed subject matter is not limited in scope to this particular embodiment.

The network adapter120may comprise multiple operational units. For example, the network adapter120may include a controller128that is coupled to a bus interface124, a network adapter local memory126and a transceiver130. The transceiver130may include a media access controller (MAC) or MAC layer131and a physical device or physical layer133. The transceiver130may read egress packets stored in the local memory126and transmit the egress packets to the network via the network media114. The transceiver130may store or write into the local memory126ingress packets received from the network media114.

The controller128may include a computational device (not shown), such as, for example, but not limited to, a state machine, an arithmetic logic unit (ALU) or a processor that is capable of performing arithmetic computations. For one embodiment, the computational device may be employed to measure or estimate a volume of traffic passing through the network media114. The controller128may monitor the network media114via the transceiver130and measure or estimate the volume of network traffic being transmitted and/or received. In this context, network traffic or network signal traffic refers to a measure of the utilization of the network for signal transmission by the devices coupled to it relative to the available bandwidth capability of the network. For example, one measure of network traffic may include the number of data packets that are passed via the network media114to and from the computing device112in a predetermined period of time, although other measures may also or alternatively be employed and are within the scope of the claimed subject matter.

The controller128may include the capability to read scatter-gather descriptors stored in the host memory138of the computing device112. Scatter-gather descriptors, or, simply, descriptors, in this context, refer to data in stored in the host memory138that provides information about packets or data packets stored elsewhere in the host memory138that are to be transmitted to or that have been received from the network. These may be included in a table, although this is not necessary. The descriptors typically comprise details (e.g., address, length, control information, etc.) about the data packets. For example, a block of memory, referred to here as a buffer, may be allocated to store such data packets. These descriptors may thus include, for example, information about the location of the buffer in the host memory138.

The network adapter120may read the descriptors to determine what memory transfer operations such as, for example, direct memory access (DMA) bus transactions, to perform in order to complete the desired transmit (egress) and/or receive (ingress) operation or operations. For example, the device driver137on the computing device112may form the scatter-gather descriptors to include the address, length, and control information about a packet or packets to be transmitted. By one of many possible methods, the controller128may fetch these descriptors and may then initiate memory transfers of data packets within buffers referenced by these scatter-gather descriptors.

During a memory transfer, such as by a DMA device, the computing device112may request control of the bus113and read a sequence of data from a buffer in the host memory138and write this data into the local memory126within the network adapter120. After the data has been fetched, the controller128may then transfer the data packet or packets to the transceiver130for transmission to the network media114and to the network. For ingress operations, the device driver137may generate descriptors that indicate to the controller128available buffer locations within the host memory138of the computing device112. The controller128may write the ingress packets into these buffers. After the memory or DMA transfer operation is complete, the controller128may update the descriptors to indicate to the device driver137the status of the data packet or packets that now occupy the buffers.

Scatter-gather descriptors may generally be placed in an array or linked list. The descriptors may typically be used in a circular fashion such as, for example, by reading a first descriptor, continuing to read the descriptors until a final one is read, then reading the first descriptor again. These groups of descriptors in this context are referred to as descriptor rings, although, of course, the claimed subject matter is not limited in scope to employing such rings. There may be separate rings for egress and ingress operations, although, again, the claimed subject matter is not limited in scope in this respect. An egress operation in this context refers to the data packet transmission process and an ingress operation in this context refers to the data packet reception process.

Referring toFIG. 1, the controller128may include a ring register, such as one that includes a buffer descriptor location register146aand a packet descriptor location register146b. The buffer descriptor location register146aand packet descriptor location register146bin this particular embodiment may include the length and address of buffer descriptors240and packet descriptors242within the memory138. During operation, in this embodiment, the controller128may retrieve the buffer descriptors240via the bus interface124. The buffer descriptors240here are retrieved from locations in the host memory138indicated by the buffer descriptor location register146a. The controller128may then, in this embodiment, with a single memory transfer operation, quickly transfer multiple ingress packets from the local memory126and transfer these ingress packets into locations within the packet buffers244indicated by buffer descriptors240. The controller128may then transfer, in this embodiment, using a single memory transfer operation, packet descriptors242into locations in the host memory138indicated by packet descriptor location register146bto reflect the ingress packets just transferred to the host memory138.

For one embodiment, the controller128may determine a “light” network traffic condition such as, for example, when the measured volume of network traffic is below a predetermined threshold. The controller128may also determine a “heavy” network traffic condition such as, for example, when the measured volume of network traffic exceeds such a predetermined threshold. The predetermined threshold may be set or determined by any one of a number of methods or techniques, such as by the user, at the factory, or computed by the network adapter or the computing device in real-time, for example. Again, this is intended simply as an example of a possible embodiment and the claimed subject matter is not limited in scope in this respect.

Although not limited in scope in this respect,FIG. 2Bis a flow diagram illustrating one embodiment of a method for reception of an ingress packet. In block250, the transceiver130may receive an ingress packet via the network media114. The controller128may transfer the received ingress packet into the local memory126. The controller128in block255may delay starting a memory transfer operation that transfers the received ingress packet located within the local memory126to the host memory138to allow several ingress packets to be received and stored in the local memory126. In block260, the controller128may determine the buffers in packet buffers244to store the received ingress packet(s). To do this, the controller128may determine the remaining space available in the memory locations indicated by the buffer descriptors240and how to accommodate the received packet(s). For example, the controller128may determine to either write a portion of an ingress packet to the current buffer and the remainder of the ingress packet to the next available buffer, or may determine to transfer a packet to the next available buffer within packet buffers244.

In block265, the controller128using a memory transfer operation may transfer one or more of the received ingress packets into packet buffers244. Subsequent ingress packets may not necessarily be received by the transceiver130immediately after the first ingress packet is received. The controller128may, therefore, use a memory transfer operation to transfer ingress packets in the local memory26to a buffer containing no ingress packets within packet buffers244before utilizing a buffer containing ingress packets within packet buffers244to store additional ingress packets, although the claimed subject matter is not limited in scope in this respect.

As indicated previously, for one embodiment, the controller128may monitor the quantity of network signal traffic via the network media114, such as via the MAC131, for example. The controller128may determine when the quantity of such network signal traffic falls below a predetermined threshold and, in response thereto, may limit to the number of ingress packets to be transferred from the network adapter120to the computing device112to the number of available buffers indicated by the buffer descriptors240.

Under light network traffic conditions, such as where a predetermined threshold is not exceeded, for example, the controller128may, using a memory transfer operation, transfer one ingress packet to one buffer within the packet buffers244. If the controller128determines that the measured volume of network traffic exceeds a predetermined threshold, such as in heavy network traffic conditions, it may group several ingress packets together in the local memory126and use a memory transfer operation to transfer multiple ingress packets to one buffer within the packet buffers244.

In block270, the controller128may transfer, using a memory transfer operation, the descriptors for the stored ingress packets, including ingress packet length and location within the packet buffers244, into the packet descriptors242. Likewise, for one embodiment, the controller128may include within the status information of a packet descriptor an indication of usage of the packet buffers244. An example of such an indication of buffer usage may include a packet buffer flag that indicates that a following ingress packet was placed in a next buffer within the packet buffers244, although the claimed subject matter is not limited in scope in this respect.

In block275, the controller128may send an interrupt to the computing device112via the bus113to inform the computing device112that the received ingress packets have been transferred into the packet buffers244. The computing device112may respond to the interrupt by reading an interrupt register on the controller128to determine the cause of the interrupt. Alternately, the computing device112may periodically poll the host memory138to determine that the received ingress packets have been transferred into the packet buffers244.

In block280, the computing device112may examine the packet descriptors242. In block285, the computing device112may provide the locations of the ingress packets in the packet buffers244to its OS. The OS may then provide an indication to the device driver137that one or more of buffers within the packet buffers244are available for storage of more ingress packets. The device driver137may wait for an indication that all the buffers in the packet buffers244are available for transfer of more ingress packets before providing an indication to the controller128that buffers are available for use by subsequent ingress packets. Alternatively, the device driver137may track how many ingress packets are transferred to the packet buffers244and which buffers within the packet buffers244are available to receive more ingress packets.

For one embodiment, the controller128may determine a number of ingress packets received condition such as, for example, when the number of ingress packets received in the local memory126is at a packet threshold, the controller initiates a single transfer operation to transfer the ingress packets from the local memory126to the host memory138. Alternatively, instead of determining the number of ingress packets, the controller128may determine a number of bytes associated with the ingress packets such as, for example, when the number of bytes is at a byte threshold, the transfer operation is performed.

For another embodiment, the controller128may use dual timers to determine when to initiate the transfer operation such as, for example, when the traffic condition is light that the time between receiving ingress packets is so long that it may be preferable to perform the transfer operation rather than waiting for other condition to occur. For example, a first timer may be started when a first ingress packet is received by the controller128. The first timer is not restarted until a transfer operation is performed by the controller128. A second timer may be started when the first ingress packet is received by the controller. The second timer is restarted each time another ingress packet is received. The second timer may expire earlier than the first timer.

The first timer is also referred to as an absolute timer because it protects the first packet from having to wait for an excessively long time before being transferred. Expiration of the first timer triggers the controller128to perform the transfer operation. The second timer is also referred to as a packet timer because it is restarted by the reception of a new ingress packet. When the traffic condition results in periods of little or no ingress packets, the second timer protects the ingress packets in the buffer from having to wait excessively for another ingress packet or for the first timer to expire. For one embodiment, the absolute timer, the packet timer, and the packet threshold may be used together to determine when the transfer operation is to occur.

FIG. 3is a block diagram illustrating an example of expiration of the absolute timer and triggering the controller to perform a transfer operation in accordance with one embodiment of the present invention. In this example, the ingress packet threshold may be set at five (5), although, of course, other threshold may also be used. At time t6, four (4) ingress packets have been received into the buffer305, and both the absolute timer (or timer1)310and the packet timer (or timer2)315have not expired. At time t7, no new ingress packet is received into the buffer305and, therefore, the number of ingress packets received has not reached the threshold. Also, at the time t7, expiration of the packet timer315has not occurred and, therefore, the controller128may not perform a transfer operation based on the expiration of the packet timer315. However, at the time t7, the absolute timer310expires. The expiration of the absolute timer310triggers the controller128to transfer the four (4) ingress packets waiting in the buffer305, even though the threshold has not been reached. The absolute timer310protects the first ingress packet320from waiting in the buffer305, for example, for longer than the time it takes for the absolute timer310to expire. The absolute timer310may, for example, be set so that it may expire after the threshold is reached in heavy traffic condition.

FIG. 4is a block diagram illustrating an example of expiration of the packet timer and triggering the controller to perform a transfer operation in accordance with one embodiment of the present invention. In this example, the threshold may be set at five (5). At time t4, two (2) ingress packets have been received into the buffer305, and both the absolute timer310and the packet timer315have not expired. At time t5, no new ingress packet is received into the buffer305and, therefore, the number of ingress packets received has not reached the threshold. Also, at the time t5, expiration of the absolute timer310has not occurred and, therefore, the controller128may not perform a transfer operation based on the expiration of the absolute timer310. However, at the time t5, the packet timer315expires. The expiration of the packet timer315triggers the controller128to transfer the two (2) ingress packets waiting in the buffer305, even though the threshold has not been reached. The packet timer315may protect the first ingress packet320and the second ingress packet425from waiting in the buffer305, for example, for longer than the time it takes for the packet timer315to expire. The packet timer315may be set, for example, so that it may expire, before the expiration of the absolute timer310. The packet timer315may also be set, for example, so that it may expire after a length of time that a new ingress packet is expected to be received into the buffer305in normal traffic condition.

FIG. 5is a block diagram illustrating an example of reaching the packet threshold and triggering the controller to perform a transfer operation in accordance with one embodiment of the present invention. In this example, the threshold may be set at five (5). At time t4, two (2) ingress packets have been received into the buffer305, and both the absolute timer310and the packet timer315have not expired. At time t5, expiration of the absolute timer310has not occurred and, therefore, the controller128may not perform a transfer operation based on the expiration of the absolute timer310. Also, at the time t5, expiration of the packet timer315has not occurred and, therefore, the controller128may not perform a transfer operation based on the expiration of the packet timer315. However, at the timer t5, the number of ingress packets received into the buffer is at five (5), the same as the packet threshold. Because the packet threshold is reached, this triggers the controller128to transfer the five (5) ingress packets waiting in the buffer305, even though the expiration of the absolute timer310and the packet timer315have not occurred. The packet threshold may allow the ingress packets in the buffer to be transferred quickly in heavy traffic condition.

FIG. 6is a flow diagram illustrating a transfer operation decision process in accordance with one embodiment of the present invention. The process assumes that the buffer305is empty and is waiting to receive a first ingress packet, as shown in block605. If the first ingress packet is received, the absolute timer310is started, as shown in block610. The packet threshold may be set at this time, although it may also be set before starting the absolute timer310. At block615, the packet timer315is started. Note that, as described above, the packet timer315is restarted each time a new ingress packet is received into the buffer305.

At block620, a determination is made to find out if expiration of either of the absolute timer310or the packet timer315has occurred. If yes, the process flows from block620to block635where the ingress packets in the buffer305are transferred. The process then flows back to block605to prepare for a next transfer operation. From block620, if neither one of the absolute timer310or the packet timer315has expired, the process flows to block625. At block625, a determination is made to find out if the packet threshold has been met. If yes, the process flows from block620to block635where the ingress packets in the buffer305are transferred. The process then flows back to block605to prepare for a next transfer operation. From block625, if the packet threshold has not been met, the process flows to block630. At block630, a determination is made to find out if a new ingress packet has been received. If yes, the process flows from block630to block615where the packet timer315is restarted. If no new ingress packet has been received, the process flows from block630back to block620to check for the expiration of the absolute timer310and the packet timer315, as described above.

The operations of these various methods may be implemented by a processor in a computer system, which executes sequences of computer program instructions which are stored in a memory which may be considered to be a machine-readable storage media. For example, the computer system may be the network-adapter120illustrated in FIG.1. The memory may be random access memory (RAM), read only memory (ROM), a persistent storage memory, such as mass storage device or any combination of these devices. Execution of the sequences of instruction causes the processor to perform operations according to one embodiment the present invention such as, for example, the operations described in FIG.6.

In the preceding description, various aspects of the claimed subject matter have been described. For purposes of explanation, specific numbers, systems and configurations were set forth in order to provide a thorough understanding of the claimed subject matter. However, it is apparent to one skilled in the art having the benefit of this disclosure that the claimed subject matter may be practiced without the specific details. In other instances, well-known features were omitted or simplified in order not to obscure the claimed subject matter.