Method and device for storing an IP header in a cache memory of a network node

[0002] The present invention relates to data communication networks wherein data messages are routed from node to node and particularly to a method and a device for storing an IP header in the cache memory of a data communication network node.

[0003] One way to improve processing performance in a network node is to add a fast cache memory to the node to work jointly with the node's main memory.

[0004] When a node having a cache memory generates a request for data stored at a particular main memory address, the request is directed first to the cache memory. The cache memory controller checks to see if the requested data is already stored in the cache memory. If it is (a cache hit), the data is supplied from cache memory instead of main memory, which reduces the memory fetch time. If the cache memory does not include the requested data (a cache miss), the request is forwarded to main memory which returns the addressed data to the node's data processing logic. Where data must be retrieved from main memory, the the data and its associated address are written into the cache memory during the retrieval step so that future requests for the data may be filled from cache memory, rather than main memory.

[0005] A node in a data communication network that handles Internet Protocol (IP) data traffic generally includes a cache memory associated with the main memory. When a message is received by the node, the following steps are conventionally performed:

[0006] 1. The whole message, comprising an IP header and the data, is stored in the main memory.

[0007] 2. Assuming the IP header is not already stored in cache memory, the node processor reads the IP header from the main memory and computes the IP routing algorithm. The cache memory controller uses this memory access to write the IP header into a cache memory cell.

[0008] 3. Then the node processor writes the new IP header to the main memory and the cache memory updates the matching cache memory cell.

[0009] 4. Finally, the complete message, that is, data retrieved from main memory and the related IP header retrieved from the cache memory is sent over the network.

[0010] An object of the invention is to provide a method and a device for writing an IP if header in a received message into cache memory of a network node concurrently with the first main memory write operation.

[0011] The invention relates to a method of storing a message header such as a IP header in a cache memory, this method being implemented in a data transmission network having a plurality of nodes wherein messages including a header and data are routed from node to node along a transmission route and wherein each node includes processing means for computing a routing algorithm by using the header of a message received by the node and routing the message to another node by using the resulting information, a main memory for storing the message and a cache memory. Such a method comprises the steps of storing the header in the cache memory while it is being stored in the main memory, reading the header from the cache memory in order to compute the routing algorithm, writing a new header resulting from the routing algorithm into the cache memory, and reading the new header from the cache memory and the message data stored in the main memory to enable the routing of a message including the header and the message data over the network.

[0012] According to another aspect, the invention relates to a device for storing in a cache memory of a node the IP header of a message routed from node to node in a data transmission network wherein each node includes a processor for computing a routing algorithm by using the header and routing the message by using the resulting information, a main memory for storing the message, a cache memory; and header a detector logic for checking whether the message conforms to a predetermined protocol such as IP protocol and cache control logic for storing the header in the cache memory concurrently with its storage in the main memory.

[0013] The objects, features and other characteristics of the invention will become more evident from the following detailed description with reference to the accompanying drawings, in which:

[0014] FIG. 1 shows a block diagram of an apparatus for implementing the present invention, and

[0015] FIG. 2 shows a block diagram of the IP header detection logic included in the apparatus shown on FIG. 1.

[0016] The system shown in FIG. 1 comprises a cache memory 10 divided into a number of cache memory cells and a cache tag RAM 12 used for addressing the cache memory 10. In a preferred embodiment of the invention, cache memory 10 has a capacity of 256 kilobytes and is divided into 2¹³or 8192 cells, each capable of storing bytes of information as eight 4-byte words.

[0017] Since the cache memory has 2¹³separate cells, it follows that cache tag RAM 12 can uniquely identify any one of those cells if provided with 13 bits of address information. The cache tag RAM 12 itself does not actually store the address bits used to identify the cache memory cells. When a cache memory cell is being used to cache information, an associated cell in cache tag RAM 12 is used to store a “VALID” bit plus a 4-bit word that contains the four most significant bits of a complete main memory address which has the 13 bits of address information used to identify the cache memory cell.

[0018] Specifically, a node's address bus 14 normally comprises 20 bits A19-A00 of address information, which would permit addressing of 2²⁰separate memory locations or cells in main memory. Since the cache memory has only 2¹³separate memory locations, it is not necessary to use all 20 bits of available addressing information in addressing the cache memory. The least significant three bits A02-A00 on the address bus 14 are ignored in addressing the cache memory locations. The most significant four bits A19-A16 of a given 20 bit address are not used in addressing the cache tag RAM, but instead may be stored along with a “VALID” bit value in the cache tag RAM location identified from address bits A15-A03.

[0019] The system shown in FIG. 1 further includes a cache tag control 18 to control read and write operations in cache tag RAM 12, an address comparator 20 to compare the most significant bits (A19-A16) of an address provided on an address sub-bus 22 with four bits of the contents of a cache tag RAM 12 location identified by bits A15-A03 of an address, a data cache control 24 to control read and write operations in cache memory and IP header detection logic 26, a significant element of the invention.

[0020] Every time a new message is received from the network, it is stored in the main memory using a complete 20 bit address (A19-A00). Simultaneously, a series of operations are initiated to determine whether the message is an IP header which may also be written into an available cache memory cell identified by 13 bits (A15-A03) of the complete 20 bit message address.

[0021] As the message is being received on lines D31-D00 of a data bus 32, IP header detection logic 26 checks to see whether the message may be an IP header by comparing the value of the most significant byte of the message to a known hexadecimal value (45 hex) always found in the most significant byte position in a valid IP header. For messages conforming to protocols other than an IP protocol, the most significant byte position would have a different value. As is noted below, a successful byte comparison only tentatively identifies the message as an IP header. Final identification of a message as an IP header requires further tests, which will be described in detail.

[0022] If the byte comparison tentatively indicates the message is an IP header, detection logic 26 sends an enabling signal to cache tag control 18 through line 28. The cache tag control 18 activates its read line CS,WE, which results in interrogation of the cache tag RAM location identified by simultaneously applied address bits A15-A03. As a result of this interrogation, the binary number (0 or 1) stored at the “VALID” bit position of the interrogated location is returned to the cache tag control 18.

[0023] A returned VALID bit value of 1 indicates that the cache memory cell identified by address bits A15-A03 is already in use and no further attempt is made to cache the current message tentatively identified as an IP header. If, on the other hand, the returned value of the VALID bit position in the interrogated cache tag RAM location is zero, then the corresponding cache memory cell is available. In such a case, cache tag control 18 sends an enabling signal to the IP header detection logic 26. This enabling signal causes detection logic 26 to perform checksum operations on the header for the purpose of finally confirming the message is an IP header.

[0024] If the checksum result matches the value of predetermined header bytes, the message is confirmed as an IP header and the IP header detection logic 26 orders cache tag control 18, to write the content of the most significant bits A19-A16 of the address on the address sub-bus 34 to the cache tag RAM location identified by address bits A15-A03 on sub-bus 16 and to change the VALID bit content in that location to 1. At the same time, the IP header detection logic 26 sends a signal over output line 30 to activate data cache control 24 so as to write the header data located on data bus 32 to the cache memory cell identified by the address bits A15-A03.

[0025] If, on the other hand, the checksum value does not match the value of the predetermined bytes, the message is assumed not to be an IP header. In such a case, IP header detection logic 26 orders cache tag control 18 to maintain a zero value for the VALID bit, disabling the content of the related cache memory cell.

[0026] When the node processor computes the routing algorithm for a received lit message, it first seeks the IP header for the message in cache memory without accessing the main memory. To this end, cache tag control 18 activates its CS,WE line to retrieve the four bit word stored in cache tag RAM 12 at the 13 bit address provided on address sub-bus 16. The 4 bit word returned from cache tag RAM 12 is compared (in address comparator 20) to the most significant bits A19-A16 appearing on address sub-bus 22. If this comparison is successful, address comparator 20 activates data cache control 24 causing it to send a read signal for data located in the cell of cache memory 10 addressed by bits A15-A03 of the address located on address bus 14.

[0027] When the routing algorithm has been computed, a new IP header is written at the same location in the cache memory to replace the former IP header previously written. As with the read operation described above, the write operation is performed with no need to access the main memory.

[0028] A preferred implementation of IP header detection logic 26 is described below reference to FIG. 2. In this embodiment, the header is composed of 20 bytes, but it could consist of up to 32 bytes since cache memory 10 comprises 32-byte cache lines.

[0029] An IP header usually comprises a first byte whose value is 45 hex and 2 checksum bytes, that are bytes 10 and 11. The checksum to be tested is the sum of all the header's bytes, except bytes 10 and 11 that are replaced with FFFF hex.

[0030] The twenty bytes in the header are sent to an input register 38 in four byte packets over five cycles. As previously seen, the first task performed in logic 26 is to compare the first byte to 45 hex in a comparator 40. If the comparison succeeds, an to enabling signal is sent over comparator output line 42 to,activate a finite state machine 44 (FSM) and to enable cache tag control 18 through line 28. The finite state machine 44 also receives clock signals through line 46 and (through line 48) the signal provided by cache tag control 18 when the value of the VALID bit in cache tag RAM is 0.

[0031] During each cycle, the data received in each packet is added in groups of two bytes in an adder 50. The resulting sum is added, in an adder 52, to a previously produced partial sum retrieved from a register 51. The resulting output from adder 52 is added to the carry generated by the adder in an adder 54. The output of adder 54 is sent to a comparator 56 where it is compared to the checksum bytes (bytes 10 and 11) during the third packet cycle.

[0032] A multiplexer 58 controlled by the finite state machine 44 enables the two least significant bytes from each group of 4 bytes to be sent to adder 50 (channel A) except during the third cycle when the multiplexer receives the value FFFF hex (channel B) instead of the two checksum bytes 10 and 11. Likewise, a multiplexer 60 also controlled by the finite state machine 44 is used to provide the value 0000 (channel B) during the first cycle and the partial sum (channel A) during the following cycles.

[0033] The value of the bytes 10 and 11 loaded in a register 62 is compared to the sum of the header bytes computed as described above. If the latter matches the checksum located in register 62, comparator 56 sends a positive signal to a gate 64. Upon receiving an enabling signal from finite state machine 44 through line 66 at the end of packet cycle 5, gate 64 sends a signal over line 30 to the data cache control to control the writing of the header in the cache memory, as described earlier.

[0034] By making use of the IP header detection logic, the apparatus described with reference to FIG. 1 and FIG. 2 permits an IP header to be written into cache memory as it is first being written into main memory.

[0035] While a preferred embodiment of the invention is described, variations and modifications will occur to those skilled in the art once they become aware of the invention. Therefore, it is intended that the appended claims shall be construed to include both the preferred embodiment and all such variations and modifications as fall within the true spirit and scope of the invention.