Abstract:
Method and device for caching the IP header of a message being routed through a data transmission network wherein each node includes a route processor for computing a routing algorithm, a main memory for storing the message, a cache memory; and an IP header detection logic circuit for storing the header in the cache memory as the message is being stored in the main memory. Once the header has been stored in the cache memory, it can be read from the cache memory in order to compute the routing algorithm. The new header resulting from the routing computation is written into the cache memory and is then read from the cache memory when the message including the header and the message data is sent over the network.

Description:
TECHNICAL FIELD 
     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. 
     BACKGROUND OF THE INVENTION 
     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&#39;s main memory. 
     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&#39;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. 
     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: 
     1. The whole message, comprising an IP header and the data, is stored in the main memory. 
     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. 
     3. Then the node processor writes the new IP header to the main memory and the cache memory updates the matching cache memory cell. 
     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. 
     SUMMARY OF THE INVENTION 
     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. 
     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. 
     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. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     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: 
     FIG. 1 shows a block diagram of an apparatus for implementing the present invention, and 
     FIG. 2 shows a block diagram of the IP header detection logic included in the apparatus shown on FIG.  1 . 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     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 13  or 8192 cells, each capable of storing bytes of information as eight 4-byte words. 
     Since the cache memory has 2 13  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. 
     Specifically, a node&#39;s address bus  14  normally comprises 20 bits A 19 -A 00  of address information, which would permit addressing of 2 20  separate memory locations or cells in main memory. Since the cache memory has only 2 13  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 A 02 -A 00  on the address bus  14  are ignored in addressing the cache memory locations. The most significant four bits A 19 -A 16  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 A 15 -A 03 . 
     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 (A 19 -A 16 ) 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 A 15 -A 03  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. 
     Every time a new message is received from the network, it is stored in the main memory using a complete 20 bit address (A 19 -A 00 ). 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 (A 15 -A 03 ) of the complete 20 bit message address. 
     As the message is being received on lines D 31 -D 00  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. 
     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 A 15 -A 03 . 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 . 
     A returned VALID bit value of 1 indicates that the cache memory cell identified by address bits A 15 -A 03  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. 
     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 A 19 -A 16  of the address on the address sub-bus  34  to the cache tag RAM location identified by address bits A 15 -A 03  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 A 15 -A 03 . 
     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. 
     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 A 19 -A 16  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 A 15 -A 03  of the address located on address bus  14 . 
     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. 
     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. 
     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&#39;s bytes, except bytes  10  and  11  that are replaced with FFFF hex. 
     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. 
     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. 
     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. 
     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. 
     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. 
     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.