Methods and systems for processing network data

Methods and systems for processing data communicated over a network. In one aspect, an exemplary embodiment includes processing a first group of network packets in a first processor which executes a first network protocol stack, where the first group of network packets are communicated through a first network interface port, and processing a second group of network packets in a second processor which executes a second network protocol stack, where the second group of network packets is communicated through the first network interface port. Other methods and systems are also described.

FIELD OF THE INVENTION

The present invention relates to systems and methods for processing network data.

BACKGROUND OF THE INVENTION

In recent years, network bandwidth has been increasing much faster than the speed of processing systems, such as computer systems and other systems that communicate with such networks. Increases in network bandwidth have been a result of new technologies and standards for both wide area networks (WANs) as well as for local area networks (LANs). WAN technologies such as SONET (synchronous optical networks) using DWDM (dense wavelength division multiplexing) have resulted in several orders of magnitude increase in available bandwidth over the span of only a few years. Similarly, LAN technologies such as gigabit Ethernet and ten gigabit Ethernet on copper and optical fiber have increased available network bandwidth by two orders of magnitude relative to standard 10- and 100-megabit Ethernet standards. During the same time period, the computational power of computers and other systems has been doubling about every 18 months. Because of the disparity between the processing speed of communication chips and the bandwidth of underlying network technologies to which they connect, many devices attached to networks cannot exploit the full bandwidth because of the lack of processing power on these devices.

FIG. 1shows an example of a local area network. The devices on the local area network can include general purpose computers, such as computers12A,12B and12C, as well as storage devices such as network storage devices13A and13B, as well as appliances for performing specialized functions, such as data caching and load balancing or other custom processing (see specialized appliances14A and14B). The actual communication path, whether by copper wire, optical fiber or wireless, can be implemented in a variety of topologies, such as switches, rings, or buses such as the bus11shown for the local area network10. The local area network typically also includes a link15which may be a gateway system to other networks, such as the Internet.

The most common implementation of a local area network in use today is TCP/IP on Ethernet (or IEEE 802.3). TCP is a reliable, connection oriented stream protocol that runs on top of IP which is a packet based protocol. UDP is a datagram oriented protocol running on top of IP. Thus processing systems, such as computer systems in a computer network typically transmit information over the network in the form of packets. A number of different packet based protocols have been defined to enable interconnected network computers to communicate with each other. Generally, the network protocol requires each processing system connected to the network to check, process and route control information contained in each information packet.

An application program which is executing on a computer, such as a general purpose computer which is coupled to the network, may need to send data to another device on the network. In this situation, the application program makes a call to a network protocol stack socket interface, which calls the TCP/IP and the Ethernet drivers, in that order. Data is encapsulated first by a TCP (transmission control protocol) header, subsequently by an IP (Internet protocol) header, and lastly by an Ethernet header as shown inFIG. 2. The application data21may be text or graphics or a combination of text and graphics or video/motion pictures or other types of data. As shown inFIG. 2, the TCP header22is appended to the application data21and then the IP header23is appended to the combination of the application data21and the TCP header22. Finally, the Ethernet driver appends an Ethernet header24A and an Ethernet trailer24B. After the Ethernet driver has completed the encapsulation process, the entire packet (containing21,22,23, and24A and24B) is transmitted over the communication medium of the network, which may be a copper wire, optical fiber, or wireless or other communication media to another device which is coupled to the network. The receiving device goes through the reverse sequence as shown in the graphic20ofFIG. 2.

The processing of data through a network protocol stack is commonly done by processing systems, such as computer systems which are coupled to the Internet. For example, computer systems at a user's home process data through such a network protocol stack and web servers at web sites perform the same processing.FIG. 3shows an example of a web site31which is coupled to the Internet32. The web site may be considered to include three groups of processing systems33,34, and35as shown inFIG. 3. Information from the Internet32is received by the routers and processed by the firewall and load balancers and then distributed or transmitted to the web servers or other servers shown in block34or provided to the systems in block35through a further firewall. In this case, the computer systems must process incoming Internet packets through a network protocol stack such as that described above. Similarly, when a web server or other server or other system in blocks33,34or35intend to transmit data through the Internet, then the data must be processed through the network protocol stack such as the stack described above. The actual bandwidth in connection with the transmission of data is a function of the capacity of the communication media (e.g. the optical fiber or other transmission media) as well as the processing throughput of the network protocol stack of the sending and receiving devices.

Web servers and other devices coupled to the network typically have an architecture which is shown inFIG. 4. This architecture includes a bus53which is coupled to a host processor or processors55and which is also coupled to host DRAM and memory controller54. The host processor or processors55customarily perform the network protocol processing. Ethernet packets are received through the Ethernet interface and framed by an Ethernet MAC (media access controller) integrated circuit52. The Ethernet MAC integrated circuit transfers the framed Ethernet packets to the host DRAM (dynamic random access memory) generally by performing a direct memory access (DMA) under control of the memory controller and/or interrupting the memory controller. It will be appreciated that the computer system51typically also includes associated logic referred to as a “chipset” which performs control functions such as control of the bus53and the communication of data among the different components in the system such as peripherals (not shown). The host processor55is interrupted by the chipset, and the TCP/IP stack is invoked to examine the Ethernet packets for IP processing and subsequent TCP processing before passing the data to the application layer. An application which is sending data to the Ethernet interface invokes the TCP/IP stack, and the reverse sequence occurs. Thus, in the implementation shown inFIG. 4, the host processor55, which is typically a general purpose microprocessor or collection of general purpose microprocessors, is performing substantially all of the operations of the system51as well as performing the network protocol processing. As a result, the host processor55, in addition to running the application program which is processing the application data, must also process network packets to perform such operations as fragmenting, reassembly, reordering, retransmission, and verifying of checksums of the packets.

Computer systems with connections to higher bandwidth networks are dedicating hardware to process parts of the network protocol stack.FIG. 5shows an example of such a computer system with acceleration hardware to offload the network protocol stack processing. The processing system61has an Ethernet interface port62which is coupled to an Ethernet MAC63, which in turn is coupled to a network offload accelerator64. Offload memory65is coupled to the network offload accelerator64. This memory is for storage and retrieval of network packets being transmitted to the Ethernet port62or being received from the Ethernet port62as part of the processing operation of the network offload accelerator64. The network accelerator64is coupled to the host bus67through the host bus bridge66. Host processor or processors68is also coupled to a host bus67. Host DRAM70is coupled to the bus67through the host chipset69which functions as a memory controller and bus controller for the system. The network offload accelerator64may be implemented as a general purpose embedded processor or a custom hardware implementation of a specific network protocol, or a combination of the two. The advantage of the general purpose embedded processor is that if network protocols change, software can be changed to reflect the new protocol and no hardware changes are required. The advantage of a custom ASIC implementation is that it may achieve higher performance or smaller die size. Current generation embedded processors may be used to offload the network protocol stack processing in the architecture shown inFIG. 5and can achieve a wire rate throughput for 100 megabit Ethernet connections. However, they cannot satisfy wire rate throughput for gigabit Ethernet processing demands.

SUMMARY OF THE INVENTION

Methods and apparatuses for processing data communicated through a network are described herein. In one aspect of the invention, an exemplary method includes processing a first group of network packets in a first processor which executes a first network protocol stack, where the first group of network packets are communicated through a first network interface port, and processing a second group of network packets in a second processor which executes a second network protocol stack, where the second group of network packets are communicated through the first network interface port.

In one particular exemplary embodiment, the first and second network protocol stacks are separate processing threads, and the first group of network packets are associated with a first network session between a host processing system and a first digital processing system, and the second group of network packets are associated with a second network session between the host processing system and a second digital processing system. Further, the first group of network packets is assigned to the first processor through a programmable hashing operation on the first group of network packets, and the second group of network packets is assigned to the second processor through the programmable hashing operation. In one exemplary embodiment, these network protocols are the same and include at least the Internet protocol (IP) and the transmission control protocol (TCP).

The present invention includes apparatuses which perform these methods, including data processing systems which perform these methods, and computer readable media which when executed on a data processing system, causes the system to perform these methods.

DETAILED DESCRIPTION

The subject invention will be described with reference to numerous details set forth below, and the accompanying drawings will illustrate the invention. The following description and drawings are illustrative of the invention and are not to be construed as limiting the invention. Numerous specific details are described to provide a thorough understanding of the present invention. However, in certain instances, well known or conventional details are not described in order to not unnecessarily obscure the present invention in detail.

FIG. 6Ashows one example of a network protocol processing system of the invention. The system101may be implemented on a single integrated circuit or on multiple integrated circuits; however, it is preferred that a single integrated circuit contain the entire processing logic shown in system101ofFIG. 6A. The system101contains multiple processors, each executing separate network processing stacks to manipulate and direct data between a network interface such as the Ethernet interface104and the interface to the host bus109. The system further includes memory such as DRAM memory111. One implementation of the invention contains four general purpose embedded processors on a single integrated circuit along with the logic105,106,107,108,110, and the bus103. Each processor, such as processor102A,102B, and102N runs a separate thread of the TCP/IP network protocol stack. Packets arriving from the network interface104are framed by the Ethernet MAC105and are sent to the Ethernet queue/dispatch logic106. The queue/dispatch logic106contains logic that examines the packet header information, including the IP header fields and the TCP header fields. The IP and TCP headers are hashed via a programmable set of mask and select registers and generate a target processor number which is used to select the particular processor to process the corresponding data in the IP and TCP fields. The Ethernet interface dispatch logic106then transfers the packet via a DMA operation to a preallocated memory buffer for the target processor; this memory buffer is typically in the offchip DRAM memory111which is controlled by the DRAM controller110. Once the packet is successfully copied to memory111, the queue/dispatch logic106interrupts the corresponding processor which was identified or selected as the target processor. The processor examines the packet header data and performs the appropriate TCP/IP processing without reading or copying the data portion (e.g. “application data”) of the datagram or packet. Once packet processing is complete, the processor inserts the addresses for the processed packets in a buffer of the queue/dispatch logic107, and the dispatch logic107then initiates a DMA operation to host memory through the host bus interface108.

Packets arriving from the host interface such as host bus109go through a similar sequence of steps. One difference, however, is that the assignment of packets from the host interface to a particular processor on the network protocol processing system101is based on a tag in the connection handle created between the host and the network processor system101. Once a packet arrives from the host and is assigned to a processor, the sequence is the reverse as that described above for packets arriving from the Ethernet interface. Further details concerning the operation of various embodiments of a network protocol processing system of the present invention are further described below.

Various embodiments of the present invention provide numerous advantages, although it will be appreciated that only some embodiments may provide all the advantages while other embodiments provide fewer advantages. One advantage of an architecture includes the scalability of processing throughput as a function of the speed and number of processors. Dispatch logic, such as dispatch logic106and107, assign packets to a specific processor. This allows each processor to run a separate thread of a TCP/IP network protocol stack. This eliminates most coherency and serialization normally seen in systems with multiple processors. An architecture of the invention also has the advantage that it supports future changes and enhancements to a network protocol stack such as the TCP/IP protocol stack. Since the network protocol stack processing is performed in software which is being executed by each processor, such as processor102A,102B, and102N, and since the fields used to generate the hash function to assign packets to target processors is programmable, enhancements and changes to the TCP/IP suite of protocols can be supported via software changes. Another advantage of an architecture of the invention is an improvement in memory bandwidth. Memory bandwidth is one of the main bottlenecks in network processing, both when processing the network protocol stack in the primary processor (e.g. a Pentium microprocessor) of a general purpose computer or when offloaded to a network protocol processing device such as the accelerator64shown inFIG. 5. Designating preallocated memory buffers for use by the dispatch and queue control logic within logic106and107allows the packets to be copied to their final memory location. Another advantage to an architecture of the present invention is the reduction of interrupts in the processing of network packets. Dedicated DMA engines and control queues in the logic106and107, which transfer packets to and from both the network (e.g. Ethernet) interface and the host interface, eliminate processor idle time during the DMA operations. That is, the processors such as processors102A,102B and102N, may perform network protocol processing with packets while other packets are undergoing DMA operations to and from interfaces104and109. Another advantage of an architecture of the present invention is that the efficiency of the host processor is increased, since the host processor does not execute the network protocol stack. Host processor cycles which were consumed by network protocol processing are now freed up for application data processing.

FIG. 6Bshows an example of a system114which uses a network processor of the present invention. The network processor115may be similar to the network processor101ofFIG. 6Aand includes multiple processors, each executing a separate network protocol stack. The processors are coupled through a network connection118, which in the case ofFIG. 6B, is shown as an Ethernet input/output which in turn is coupled to the Ethernet MAC105. On the host side, the network processing system115is coupled through a host interface117to a host bus119. A host processor or processors, such as an Intel Pentium microprocessor120, is coupled to the host bus119and is coupled to the host memory121through the host bus119. It will be appreciated that other components, such as host chipset components for providing memory control and bus control and control of peripherals, may also be part of the system shown inFIG. 6B. It will be appreciated thatFIG. 6Bshows one example of a typical computer system which may be used with the present invention. WhileFIG. 6Billustrates the various components of a computer system, it is not intended to represent any particular architecture or manner of interconnecting the components, as such details are not germane to the present invention. For example, a system may include multiple buses such as a system bus, a processor bus, and peripheral bus or buses. It will also be appreciated that network computers and other data processing systems which have fewer components or perhaps more components may also be used with the present invention. Additional components not shown inFIG. 6Bmay include display controllers and display devices, and input/output devices such as mice, keyboards, backup storage devices, and printers. It will be appreciated that if the system shown inFIG. 6Bincludes multiple buses, these will typically be interconnected to each other through various bridges, controllers, and/or adapters as is well known in the art.

The network protocol processing system115shown inFIG. 6Bmay include N processors; in one embodiment, N is equal to 4. Each processor executes its own TCP/IP protocol stack and also executes a socket ISM set of computer programming code in order to communicate with the host processor120as is further described below. As shown inFIG. 6B, processor1executes a stack of software code116A which includes software for processing the IP protocol and software for processing the TCP or UDP protocols as well as processing the socket ISM software for allowing processor1to communicate with host processor120and the host memory121. Similarly, processor N includes a similar set of computer software which is being executed as a separate network protocol stack and communication control. The network protocol processor115may be implemented in multiple integrated circuits or a single integrated circuit.

FIG. 6Cshows an alternative network protocol processing system101A which contains many of the same logic blocks as the system101ofFIG. 6A. However, the network protocol processing system101A further includes data transform engines106A and107A along with DMA/dispatch logic106B and107B and control logic106C and107C. These data transform engines may be used to process the data before it is stored in the offchip memory111or after it is retrieved from the offchip memory111.

FIG. 7shows a detailed block diagram view of a particular implementation of a network protocol processing system which is similar to the system shown inFIG. 6A. In the embodiment ofFIG. 7, there are 4 separate processors,102A,102B,102C, and102N, each of which process their own separate threads of network protocol stacks as well as a net kernel operating system software shown as software176,178,180, and182for their respective processors. Each processor includes an instruction and data cache and each processor is coupled to the local bus or processor local bus103A. As noted above, the system101B may be implemented on a single integrated circuit or it may be implemented as multiple integrated circuits. The system101B has three main input and output interfaces; the first is interface104, which is a connection to the network communication medium such as an Ethernet communication medium. The interface109is a connection to the host bus such as the host bus119ofFIG. 6B. The third interface is the interface to offchip DRAM111which may be a conventional interface to DRAM which is controlled by the SDRAM or DDR RAM controller110A, which in turn is coupled to the processor local bus103A. The interface to the host109is controlled by a PCI-X bridge108A in one embodiment where the host bus, which is coupled to this interface109, is a PCI bus. The network protocol processing system101B also includes an onchip peripheral bus bridge103B which allows optional devices103C, such as a JTAG or UART port, to be included in the system101B. The system101B further includes control and processing logic151which serves to provide the function of the control logic106and107ofFIG. 6A. Control logic151includes checksum engines152which may be used to perform checksum operations on data which is being transmitted into or from the network protocol processing system101B. Performance monitors154may be used to monitor the performance of the various processors and may provide input to the load balancer170which attempts to balance the queue of packets which are to be processed by each processor102A,102B,102C, and102N. Timers158may be used to implement TCP timers. Each processor102A,102B,102C, and102N may have a dedicated set of TCP timers. Locks156provide a means of ensuring exclusive access to system resources by the processors102A,102B,102C, and102N. The interprocessor communication160acts as a manager and a buffer for interprocessor communication between the processors102A,102B,102C, and102N. Messages between the processors are managed through the interprocessor communication control160. The input/output queues164maintain a list of packet data which is being processed either for input or for output by the system. Internet protocol (IP) routing table168is used as part of the conventional routing process according to the IP protocol. An address resolution protocol cache166is used for the conventional Ethernet address resolution protocol.

One aspect of the multiple network protocol processors in the invention is the memory coherence model provided to the software and applications running on the processors. There are two basic models, a hardware-managed coherent memory system, or a software-managed coherent memory system. This invention applies equally well to either model.

There are many commercial implementations of hardware-managed coherent multiprocessors (MP) available from manufacturers such as IBM, Hewlett-Packard, Sun Microsystems, and Compaq. This model places a minimal burden on programmers to achieve correct program operation, but requires complex hardware to synchronize the contents of memory and processor caches in the presence of simultaneous accesses to a given memory location by multiple processors. Furthermore, as is well-known to those practiced in the art, hardware-coherent MP systems suffer from an inherent scaling problem. Overall systems performance does not scale linearly as the number of processors is increased due to contention for memory access and cache coherence. Thus, while writing application programs (such as the ISM) to run correctly on a hardware-coherent MP is easier than a software-coherent MP, achieving high performance on these applications may be more difficult. This difficulty is magnified if the application is inherently serial, or was not coded with parallelism in mind. Thus, a multiprocessor whose caches and memory are managed via software has an important advantage because it forces the software to be coded with parallelism in mind from the outset. This can frequently lead to higher performance than a corresponding application which was ported to a hardware coherent MP.

Given that packet protocol processing is inherently parallel, and therefore amenable to parallel processing, a preferred embodiment uses multiple network processors whose caches and memory are kept coherent by software (software-managed coherent memory system). This simplifies the hardware design and provides the equally desirable property of forcing the software to be written with parallelism in mind from the beginning.

However, a means of synchronizing multiple processor access to memory should still be provided. The lock hardware (156inFIG. 7) provides this function by allowing atomic access to a subset of the memory space. Each lock is implemented as a well-known test-and-set primitive (but may have other semantics in other embodiments of the invention, such as compare-and-swap, fetch-and-add, etc.) to allow software to coordinate multiple access to critical sections of code to enable only one processor to access a given memory location. Thus, along with the other aspects of this invention, the lock hardware enables parallel processing of packets with minimal hardware complexity, and minimal software effort.

Various methods of the present invention will now be described by referring toFIGS. 8A,8B and8C. The network protocol processing system which may be used with these methods includes the system shown inFIG. 6Aor6B, for example. The method ofFIG. 8Adescribes a process flow upon the receipt of network packets from the network communication medium, such as an Ethernet network. The network packets are received at a single network interface port in operation201. Typically these network packets will include header data and application data. In operation203, a first group of network packets is distributed from the single network interface to a first processor which is executing a first network protocol stack in order to process the first group of network packets. In operation205, a second group of network packets is distributed from the single network interface port, to a second processor which is executing a second network protocol stack in order to process the second group of network packets. In this case, the first and second network protocol stacks are separate processing threads such as the processing threads116A and116N ofFIG. 6B. As shown in operation207, after the first processor processes the first group by executing the first network protocol stack, first data associated with the first group is transmitted to a host bus interface and, through a DMA operation, this first data is written to host memory. In the system shown inFIG. 6Bthis occurs by transferring this first data through the interface117onto the bus119and into host memory121. In operation209, after the second processor processes the second group by executing the second network protocol stack, second data associated with the second group is transmitted to the host bus interface and, through a DMA operation, this second data is written to the host memory. The foregoing description andFIG. 8Aassume a certain sequence of operations. It will be appreciated that a different sequence may also occur (e.g. the second processor may complete the processing of the second group before the first processor completes the processing of the first group). These alternative sequences of the operations will be recognized to be merely alternatives of the present invention, as the exact sequence, such as when the first group is processed relative to the second group or when the first group is distributed relative to when the second group is distributed, depend upon the particular circumstances in which the system of the present invention is operating.

FIG. 8Billustrates an exemplary method in which a network protocol processing system of the present invention transmits data from a host system onto a network communication medium, such as an Ethernet communication medium. In operation231, first and second application data is received. This may occur through a DMA operation from the host memory to network processing system memory such as memory111shown inFIG. 6A. In operation233, tags which are associated with the first and second application data are examined to determine which processor processes headers for both groups. The determination of these tags is controlled by the execution of OSM software on a host processor which is part of an I2O system which consists of the host processor or processors and the network processor; this I2O system is further described in conjunction withFIG. 13below. In operation235, a first packet header data associated with the first application data is prepared in a first processor which is executing a first network protocol stack. In operation237, a second packet header data which is associated with a second application data is prepared in a second processor which is executing a second network protocol stack. In operation239, the first application data and its associated first packet header data are then transmitted through a single network interface port, and in operation241, second application data and its associated second packet header data are transmitted through the single network interface port.

As was noted relative toFIG. 8A, the various operations shown inFIG. 8Bmay be performed in a different order than that shown inFIG. 8B.

FIG. 8Cshows another aspect of the present invention in which packets are directed to various processors based upon a hashing operation, which in one embodiment is programmable. In operation261, a packet with application data and associated packet header data is received. This would typically occur by receiving the packet through a network interface such as the interface104ofFIG. 6A. Then in operation263, a field in the packet header data is examined. Typically this involves performing a hashing operation on the packet header data. Normally for non-fragmented packets, the hashing function looks at the IP source address and the TCP source port number and the TCP port destination number when performing the hashing operation; the output of the hashing operation or function determines the appropriate processor which is the target processor and which will perform the processing on the packet according to the network protocol processing stack. Thus, gas shown in operation265, the packet header data is directed to one of a group of processors based on the output of the hashing function. In operation267, the application data which is associated with the packet header data is stored, typically through a DMA operation in dedicated network processor memory such as memory111ofFIG. 6A. This application data is typically stored in either of a first or second portion of a network processor memory such as memory111, which is preallocated, respectively, to the first or second processors. It will be appreciated that if the network processing system includes more than two processors that there will be more than two preallocated portions of the memory. That is, each processor in the network protocol processing system has, in one embodiment, its own preallocated portion of the network processor memory such as memory111. For fragmented packets, the IP identification for the session is used to determine the target processor. In particular, if a packet has the same IP identification as another packet previously received, then it is part of the same fragment and it is directed to the same target processor as the prior portion of this packet.

Although the network protocol processing systems of some embodiments of the invention contain multiple processors running multiple operating system kernels and protocol stacks, the system appears as a single network interface to the host processor or processors. This can be seen fromFIG. 6Bin which there is one Ethernet interface and one host interface. The parallel processing capability of the network protocol processing system, such as the system115, is effectively transparent to the host processor or processors and allows for processing of network packets at speeds that match the network transmission speeds, such as 10 gigabit Ethernet. The host processors and the external network environment perceive the network protocol processing system of the invention, such as system115, as a single network interface with an assigned IP address. The network protocol processing system processes all the network packets that have the IP address as the destination address, even though the load balancer of the network protocol processing system of the invention may distribute network packets among different processors.

From the perspective of the host processor or processors, this single interface is created by replicating listening sockets on the various processors, such as processors102A,102B, and102N ofFIG. 6A, in the network protocol processing system of the invention. In the example shown inFIG. 9A, four listening sockets at port80are created when the host, in this case a host http server303, starts. The communication between the host system and the processors in the network protocol processing system is through an OSM/ISM system which follows the I2O architecture, which is described further below. As shown inFIG. 9A, each processor (in this case 4 processors in the network protocol processing system) includes a socket ISM software module and a listening socket at port80.

FIG. 9Bshows an exemplary method of replicating sockets to create the architecture shown inFIG. 9A. Operation312ofFIG. 9Binitializes the OSM system on the host and the ISM systems on the processors (IOPs) on the network protocol processing system such as processors102A,102B, . . .102N ofFIG. 6A. Each ISM, as part of this initialization in operation312, transmits a number representing its IOP and transmits a format of an IOP-specific handle to the OSM software executing on a host. Each ISM preallocates a number of handles for its associated IOP (processor) on which it is executing. In operation314, a host application establishes a socket connection using socket API calls after initialization. This typically involves the OSM informing each ISM that a new host application is bound to a new socket in the listening state by sending an I2O message (in a process described generally below) to each IOP. The message contains an OSM handle which identifies the host socket, and each IOP's ISM causes this association message (socket, host OSM handle) to be recorded in an internal table in memory for the particular IOP. In operation316, a client application connects to the socket that the server application is listening on. This typically involves a given IOP receiving a connection request, and the ISM executing on this given IOP looks up the socket in its internal memory table to identify the host OSM handle. The ISM then allocates a handle from its pool of available handles and records the association (having a data structure representing: socket, OSM, and ISM handle) in an internal memory table. The ISM sends an I2O message to the OSM which contains the data (OSM handle, ISM handle, IOP number). In operation318, the OSM then receives the client request, invoking the proper server application by identifying it from the OSM handle it allocated previously, and recording the associated ISM handle and IOP number in a table. The server application also builds a response to the client in the exemplary manner shown in operation318ofFIG. 9B.

FIG. 10Ashows the paths taken in sending data from the host through a network protocol processing system of the invention. In the embodiment shown inFIG. 10A, the network protocol processing system includes 4 separate processors, each executing their own separate network protocol stacks; they are labeled as IOP0, IOP1, IOP2, and IOP3. FIFOs or other buffers are also shown in the data paths such as FIFOs333A,337A, and341A. Further, these data paths include a checksum operation such as checksum operation335A for processor IOP0. The processing of packets is pipelined through the protocol layers as shown inFIG. 10Afor each processor. When the host process attempts to send a message, a socket level message send command is posted to the socket ISM module of the particular processor which is usually, as described below, identified by the OSM module on the host processor or processors. The socket ISM module transfers the message from the host memory into the particular preallocated memory of the particular processor, such as processor IOP0. In the example shown inFIG. 6B, this may involve a DMA operation from the host memory121to dedicated memory which is coupled to the system115, such as memory111. The socket ISM module of the particular processor designated as the target processor also invokes the transfer protocol processing such as TCP. The transport processes form datagrams in compliance to the protocol requirements and checksum operations are performed as shown by operations335A,335B,335C, and335N for the respective processors331A,331B,331C, and331N. Typically at the same time as the checksum operation, the transport process in the transport layer makes a request for route selection and for the resolution of the link address if hardware assisted routing table168and the ARP cache166are supported. The process continues in the IP layer to processing operations339in the case of processor IOP0. After the processing in the IP layer, the datagrams are passed to the Ethernet controller where Ethernet frames are formed and passed through the Ethernet interface105A as shown inFIG. 10A.

FIG. 10Bshows the processing of packets received from the network through the various layers ofFIG. 10B. As withFIG. 10A, the embodiment shown inFIG. 10Bof a network protocol processing system of the invention includes 4 processors, such as processors102A,102B,102C, and102N ofFIG. 7, each of which is executing separate network protocol stacks. These processors are shown inFIG. 10Bas processors IOP0, IOP1,10P2, and IOP3. The processors are executing different software modules in the two different layers (IP layer and transport layer). As shown inFIG. 10B, the network protocol processing system processes the received packets by pipelining the packets through protocol layers. When a network packet is received from the network medium interface, such as the MAC interface105A, the interface validates the packet and filters out packets that are corrupted or have wrong addresses. The validation process may include the computation of the IP header checksum. The interface then allocates a data buffer through a buffer manager361and then the data is stored typically through a DMA operation into memory which is typically dedicated offchip memory such as memory111ofFIG. 6A. A simple dispatching algorithm is used to pass the packet to one of the processors for IP layer processing. This dispatch algorithm has been described above relative toFIG. 8C. After processing in the IP layer, the packet is passed up to the transport layer. As noted above, for connection oriented protocols such as TCP, all packets belonging to the same session are dedicated to the same processor where the session was started. Even though different processors may process IP packets belonging to the same TCP session, they are typically directed to the same processor for TCP processing. After the TCP layer has completed its operations, the packet is passed to the socket ISM module for the particular processor which then sets up the DMA operations for delivering the packet data to host memory for processing by the host processor.

FIGS. 11A and 11Bshow exemplary architectures for the “net kernel” software which is executing on each processor, such as processors102A,102B, and102N of a network protocol processing system such as the system101ofFIG. 6A. The software and associated data structure for each processor is represented by blocks401A,401B, and401N respectively, for the processors102A,102B, and102N of the system101ofFIG. 6A. The executing software in each processor may communicate through the bus103with other executing software in order to perform load balancing and memory management. Each of the processors runs its own instance of net kernel which includes an operating system and the protocol stack. Each instance of net kernel has its private resources such as memory (e.g. a preallocated portion of the memory111which is coupled to the system101as shown inFIG. 6A). However, the processors share resources such as the interface to the host and the interface to the communication medium such as an Ethernet communication medium. As shown inFIG. 11A, each instance of the net kernel executing on each processor includes its own network protocol stack403A or403B or403N. Further, each instance of the net kernel includes its own copy of an interprocessor communication module409A, or409B, or409N which facilitates communication among processors. A variety of services can be supported on top of the interprocessor communication module such as distributed lock management407A, or407B, or407N, or load balancing, such as load balancing411A,411B, or411N, and/or global memory management such as GMM405A,405B, or405N. The operating system portion of the net kernel also includes an I2O ISM module which facilitates the communication with the host processor or processors as is described further below (e.g. see the discussion associated withFIG. 13). This ISM module in each net kernel of each processor communicates with the OSM module operating on the host processor in order to communicate messages and commands between each processor and the host processor in order to perform various operations such as DMA operations between the network protocol processing system's memory (e.g. memory111ofFIG. 6A) and the host's memory (e.g. memory121as shown inFIG. 6B). The protocol stack in one embodiment which is being executed by each processor in the network protocol processing system may, in one embodiment, be a TCP/IP protocol stack which is a conventional TCP/IP protocol stack which runs on top of the net kernel's operating system and interoperates with the I2O ISM software module of each processor.

FIG. 11Bshows in further detail the net kernel software being executed by each processor, such as processor102A ofFIG. 6A. The net kernel software431includes a scheduler module445as well as the processor's socket ISM module449for communication with the host439. The net kernel software431also includes a messaging queue manager447which manages the interprocessor messages441as part of the interprocessor communication through bus103as shown inFIG. 11A. The software431further includes, in this embodiment, TCP processing software as well as IP processing software451and453, respectively. The network protocol processing software is in communication with, in this case, a network communication port which is an Ethernet port437. The software431also maintains interrupt status registers443which receive interrupts from the interrupt controller433which concentrates interrupts435from various interrupt sources including the timeout timers, socket calls from the host and outgoing packets from the host, interrupts from other processors for interprocessor communication, and interrupts generated by the dispatch logic (e.g. dispatch logic106in the case of packet reception from the network). The operating system portion of the net kernel software431provides basic functions such as scheduling and dispatching, memory management, timing services, thread management, synchronization, and system initialization. It supports execution at two levels, interrupts and threads, and the execution priorities are such that interrupts, unless disabled, are processed with the highest priority. High priority threads have the second highest priority and such threads are not destroyed. Instead they are blocked on return and reentered when subsequently resumed. Normal or low priority threads may be preempted by either the interrupts or the higher priority threads. Normal or low priority threads are terminated when they complete and thus, if necessary, should be written as a function that runs forever. In one embodiment, the net kernel performs all network protocol processing at the interrupt level in order to minimize context switching. The net kernel also polls the Ethernet MAC interface (or other network communication medium interface) as well as the DMA interface to the processor's memory (e.g. memory111ofFIG. 6A) or to the host's memory.

FIG. 12Ashows an example of a method of load balancing of the packet flows through 4 processors of a network protocol processing system such as the system101. The host OSM module503controls the distribution of outgoing packets501to one of the four processors, each of which are shown inFIG. 12Aas having separate sockets (as in the case ofFIG. 9); the sockets ofFIG. 12Aare shown as505A,505B,505C, and505N. The host OSM module remembers for a session the particular processor which processed the incoming packets which are being responded to by the outgoing packets501. The host OSM will recall for this session the identification of the particular processor and forward the outgoing packets to that processor. The host OSM typically employs a tag for each session which identifies the particular processor in the network protocol processing system. If there is no tag (e.g. in the case where the server initiates a session) then the host OSM will provide a tag to identify the particular processor in the network protocol processing system to process the outgoing packet. However, processing at the IP layer (blocks511A,511B,511C, or511N) may be performed by any one of the available processors in the network protocol processing system. Furthermore, datagrams originating from connectionless protocols such as UDP and IGMP can be processed by any one of the executing network protocol stacks. Incoming packets515are hashed in a hashing operation513which may be performed by simple programmable hardware logic that dispatches received IP packets to one of the 4 processors for processing of the IP protocol in blocks511A,511B,511C, or511N. After the IP layer processing, the transport protocol header of the IP packet is examined. If the datagram belongs to connection oriented protocol such as a TCP protocol, a software hash function may route the datagram to the correct processor507for transport protocol processing. Thus all datagrams belonging to a TCP session are restricted to be handled by the same processor where the session was initiated or opened. On the other hand, if the datagram is not specific to a connection (e.g. a connectionless protocol) then the datagram may be rerouted in order to balance the load by the load balancing module509.

FIG. 12Bshows a further example of the direction of packets based on address hashing and load balancing. The hash function533examines the source IP and source port number531and determines, in the case of non-fragmented packets, the proper processor which is selected to process the packet pursuant to a network protocol. In the case shown inFIG. 12B, the processor selected by the hash function533is the processor P0, but as shown inFIG. 12B, the processor P0determines in operation535that its processing queue is too large and forwards an interprocessor communication request to another processor, in this case P2539, to process the packet. Message queues are maintained between the processors, such as message queue537between processor P0and processor P2and message queue547between processor P1545and processor P0. The hash function533is typically an exclusive OR which produces two bits to select a processor in the case where the network processing system includes 4 processors such as processors102A,102B,102C and102N as shown inFIG. 7. The hash function543is a different hash function which is employed for fragmented packets. In this case the IP identifier which identifies the session causes, through the hash function543, the packet fragment to be directed to the same processor as prior fragmented packets having the same IP identifier. It can be seen fromFIG. 12Bthat fragmented packets541are processed through the hash function543and forwarded to processor P1for processing. The processor P1may indicate through its software message queue547that it is busy, which causes the processor P0to forward packets it receives to processor P2instead of processor P1.

A description of the OSM and ISM modules in the I2O architecture will now be provided while referring toFIG. 13. In the following discussion, it is assumed that the I2O architecture with OSM and ISM modules are used to control the communication between the network protocol processing system, such as system101, and a host processor561; it will be appreciated, however, that alternative architectures may be employed. Communication between a network protocol processing system such as system101which includes multiple processors, each executing a separate network protocol stack as a separate thread, and a host processor or processors is based on the I2O socket architecture which defines a messaging framework for two systems to exchange information with each other. This architecture is well known and was developed by the I2O special interest group. Detailed information regarding this architecture can be found at the I2O web site which is www.intelligent-IO.com. To support the I2O socket architecture, a socket ISM module is running at the top of the protocol stack on each processor. The ISM module interacts with a host OSM module, intercepts all the socket calls, maintains and manages data structures for socket operations, and controls the data moving into and from the host. A socket layer in each ISM of each processor in a network protocol processing system provides an interface (API—application program interface) used by applications running on the host processor to access TCP/IP services. The OSM and ISM provide the communication between the socket API and the network protocol stack. TCP or UDP sockets are maintained and synchronized between the host and each processor. A set of message queues is managed by the ISM modules and the host OSM module as shown inFIG. 13. For each processor in a network protocol processing system, there is a corresponding inbound free queue and an inbound post queue. In the case shown inFIG. 13, there are 4 processors in the network protocol processing system (and thus the system ofFIG. 13resembles the embodiment shown inFIG. 7which includes 4 processors102A,102B,102C, and102N). ISM module567A is executing on processor P0while ISM modules567B,567C, and567D are executing respectively on processors P1, P2, and P3. The ISM's of the 4 processors jointly control, as represented by the block569, the outbound free queue571and the outbound post queue573which allows for the transmission of messages to the host OSM from any one of the ISMs executing on one of the processors. Processor P0has its corresponding inbound free queues and inbound post queues563A and565A, and each of the processors P1, P2, and P3have their respective inbound free queues and inbound post queues (563B,565B,563C,565C,563N, and565N). Each queue may contain a plurality of message frame addresses which are pointers to a memory address that contains a message that needs to be processed. In the case of the outbound free queue571and the outbound post queue573, these message frame addresses are pointers to locations in the host's memory. In the case of the other queues shown inFIG. 13(563A,563B,563C,563N,565A,565B,565C, and565N), these message frame addresses are pointers to memory locations of the corresponding processor's memory such as preallocated memory portions of the memory111ofFIG. 6A. When the OSM host has a message to communicate to a particular processor, such as processor P0, the OSM host determines whether the processor's corresponding inbound free queue (e.g. queue563A in the case of processor P0) has a free entry, and if so the inbound free queue provides a free MFA (message frame address) to the OSM host and the OSM host then causes a DMA operation to occur, typically from the host's memory (e.g. memory121ofFIG. 6B) to a preallocated portion of the network protocol processing system's memory, such as the memory111. When the DMA operation is complete, the OSM host posts the MFA address in the corresponding inbound post queue for that processor (e.g. queue565A for processor P0) and this queue can then interrupt its corresponding processor or its processor can poll the queue to see if there are any messages to process. A similar sequence of operations occurs in the reverse direction when an ISM module on a particular processor seeks to send a message or communicate data to the host OSM. In this case, the particular ISM module asks the outbound free queue whether there are any available MFAs, and if so, the outbound free queue571provides an available MFA to the requesting ISM, which in turn causes a DMA operation to transmit data from the processor's memory (e.g. a preallocated portion of the memory111) to the host's memory. After the DMA operation is complete, the particular ISM posts the MFA in the outbound post queue573which can cause an interrupt of the host processor or the host processor can poll the queue to see if there are messages to process. It will be appreciated that the information which is exchanged in this architecture can include either data or commands which can be interpreted upon receipt to cause a particular action or a combination of data and commands.

The OSM typically intercepts all socket API calls and converts them into messages for an ISM module. For example, as a result of a send call, the OSM would buffer the data to be sent and send a message to the appropriate ISM and wait for the appropriate ISM to confirm that the DMA data transfer for its corresponding processor has been completed. The OSM module on the host also receives all messages arriving from any one of the ISMs and acts upon them. For example, a message may indicate that there is data for socket X in buffers B1and B2, and the OSM would deliver the data to the application waiting on socket X, and then notify the ISM module that buffers B1and B2are now free. The ISM on a particular processor processes incoming messages from the OSM and converts them into actions. For example, upon receiving a send message from the OSM, the ISM would set up a DMA operation to pull the data into the processor or the processor's memory and route the data to the appropriate socket for subsequent processing by the TCP/IP protocol stack, and on completion, inform the OSM accordingly. When incoming data arrives for socket X, the ISM transfers the data, via DMA, into a free receive buffer on the host. The ISM then notifies the OSM that the new data for socket X is available in a particular buffer.

FIG. 14shows an example of, in one case, a server farm which includes two dual processing systems603and605, each of which has two network processors of the present invention coupled to it. In particular, the system601has a dual processor host system603which is coupled to two network protocol processing systems of the present invention. Each of these network protocol processors607and609may have the architecture shown inFIG. 6Aand include dedicated off-chip memory such as memory111for each network processor. Similarly, the dual processor host system605has two separate network protocol processors611and613which may each be similar to the architecture shown inFIG. 6A. Each processor of the dual processor host system may be dedicated to one of the two network processors which is coupled to the dual processor system. In this case, the network processor interfaces with only a single host and the architecture is similar to that shown inFIG. 6B. Each network processor is coupled to a particular Ethernet network, either network615or617as shown inFIG. 14. This provides for potentially increased bandwidth and also increased reliability should one of the networks fail for some period of time. It will be appreciated that the system601may function as a web server or other type of server when the Ethernet network615and617are coupled to another network, such as the Internet665.

FIG. 15shows an alternative architecture for a web site651which includes two host systems which are serving as web servers655and653, each of which includes a network accelerator657and659respectively. The host systems are coupled through the network accelerators to a local network661which in one embodiment may be an Ethernet network. In turn, this network661is coupled to the Internet665. Each network accelerator657and659may be of the architecture shown inFIG. 6Aand have multiple processors, each processing separate network protocol processing stacks. This would allow the same network accelerator to process web sessions between two different “client” computers, such as computers671and673, which are coupled to the Internet665through two different Internet service providers667and669. It will be appreciated that the combination of the host system655and the network accelerator657may resemble the architecture shown inFIG. 6Bwhich allows for the different sessions to be processed by the same network accelerator through two different network protocol stacks for the same network interface105.

It will be appreciated that various modifications may be made to the concepts of the present invention to produce alternative embodiments. One such alternative embodiment is shown inFIGS. 16A,16B,16C, and16D. In this alternative embodiment, a network protocol processing system includes more than one host bus interface which allows the network protocol processing system to communicate with more than one host. In the embodiment shown in these figures, a single network interface, such as an Ethernet interface, may be used with multiple host bus interfaces. Alternatively, more than one network interface may be used in combination with more than one host bus interface.FIG. 16Ashows an example, in block diagram form, of a network protocol processing system with more than one host bus interface. This architecture is a variation of the system shown inFIG. 6Awhich has a single host bus interface. The architecture ofFIG. 16Aincludes a host bus interface703for communicating with a host1and a host bus interface705for communicating with a host2. The system701shown inFIG. 16Amay be implemented as a multiple integrated circuit system or on a single integrated circuit. The architecture ofFIG. 16Aallows a single network protocol processing system, such as system701, to be connected to more than one host system as is shown inFIG. 16B. It will be appreciated that the architecture shown inFIG. 16Bis similar to the architecture shown inFIG. 6Bexcept that the host system115A has several host interfaces, such as host interface117and117N coupled to 2 different host systems, each having their own host bus119and119N. As is shown inFIG. 16B, each host bus includes a host processor and host memory, such as host processor120N and host memory121N. This capability to allow communication with more than one host can be useful when the processing throughput of a single network protocol processing system is more than the capacity of a single host system to respond, and thus a single network protocol processing system can be connected to two or more host systems. This ability to connect a single network protocol processing system to multiple host systems, such as computer systems, can also be used for achieving high availability through the use of redundant host systems. In the event of a failure by one host, a second host is used to take over the operation of the first host which failed. The multiple host architecture ofFIG. 16Acan also be used in conjunction with the data transform engines that are placed serially in the data flow to the host, such as the data transform engines shown inFIG. 6Cand described in conjunction withFIG. 6C.FIG. 16Cshows an example of such a multiple host architecture which uses data transform engines. The benefits of eliminating a pair of memory accesses for transformations apply equally well to the multiple host interface architecture ofFIG. 16C.FIG. 16Dshows an implementation of a web site or other processing site which uses a network accelerator, such as the accelerator701(alternatively referred to as the network protocol processing system701). In particular, the network accelerator657A may use the architecture shown inFIG. 16Ato provide connectivity for multiple hosts through a local area network661as shown inFIG. 16D. It will be appreciated that the architecture shown inFIG. 16Dis similar to the architecture shown inFIG. 15.

In one particular embodiment of a multiple host bus interface, such as the system shown inFIG. 16A, each host bus interface would replicate the logic shown inFIG. 13in order to provide sufficient functionality in an I2O system. The software and operating system required to support a network protocol processing system which communicates with multiple hosts will be similar to the software and operating system of a comparable device with a single host interface, with an additional handle on the ISM to identify the host. The flowchart inFIG. 9Bwhich explains socket replication shows the assignment of a message (socket, host OSM handle) for a network protocol processing system with a single host interface. For a network protocol processing system with multiple host interfaces, such as the system shown inFIG. 16A, the (host OSM handle) message will include the host number. Host (e.g. server) initiated transfers are done in the same way for both the single and multiple host architectures (e.g. the architecture ofFIG. 6Aand the architecture ofFIG. 16A). Remote (e.g. client) initiated transfers are received by the appropriate processor and sent to the appropriate host based on the host number field in the (host OSM handle) data structure.

FIGS. 17A,17B and17C show yet another embodiment of the present invention. In particular,FIG. 17Ashows a network protocol processing system751which is similar to the system shown inFIG. 6Aexcept that two network interfaces are provided by the system751. In particular, in the example shown inFIG. 17A, an Ethernet interface105A and an Ethernet interface105B are included in the system751in order to allow the system751to communicate with two Ethernet networks. An example of two Ethernet networks is shown inFIG. 17Bin which network processor607A, which may be of the architecture shown inFIG. 17A, and network processor613A, which may also be of the architecture shown inFIG. 17A, are coupled to 2 Ethernet networks615and617. It will be appreciated that the system601A shown inFIG. 17Bis similar to the system shown inFIG. 14.FIG. 17Cshows a particular example of the use of an architecture such as that shown inFIG. 17Aand a processing site, such as a web site651, which includes a network accelerator657A and another network accelerator659A, each of which may have the architecture shown inFIG. 17A. It will be appreciated thatFIG. 17Cin other respects resembles the system shown inFIG. 15. The software and operating system required to support a network protocol processing system with multiple network interfaces, such as multiple Ethernet interfaces, may be similar to the software and operating system of a comparable device with a single host interface, such as the system shown inFIG. 6A. Inputs to the system are handled by the same software that is used in architecture such as that shown inFIG. 6A. Data outputs require the addition of an interface number to the data structure in the TCP connection session, and this technique is similar to that used on general purpose computers with multiple network interface cards.