Cache entry selection method and apparatus

• US 20040146044A1
• Filed: 03/29/2004
• Published: 07/29/2004
• Est. Priority Date: 03/19/2001
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Luijten, Ronald P, Herkerdorf, Andreas
• Granted Patent: US 7,146,478 B2
• Time in Patent Office: Days
• US Class Current: 370/351
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/30 Routing of multiclass traffic
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric

Abstract

A method for selectively inserting cache entries into a cache memory is proposed in which incoming data packets are directed to output links according to address information. The method comprises the following steps: a) an evaluation step for evaluating for each incoming data packet classification information which is relevant to the type of traffic flow or to the traffic priority to which the data packet is associated; b) a selection step for selecting based on the result of the evaluation step whether for the data packet the cache entry is to be inserted into the cache memory; c) an entry step for inserting as the cache entry into the cache memory, in the case the result of the selection step is that the cache entry is to be inserted, for the data packet the address information and associated output link information.

Claims

1. A method for inserting cache entries into a cache memory (39), in a device in which incoming data packets are directed to output links according to address information, the method comprising the following steps:

a) an evaluation step for evaluating for each said incoming data packet classification information which is relevant to the type of flow or to the priority to which said data packet is associated,

b) a selection step for selecting based on the result of said evaluation step whether for said data packet said cache entry is to be inserted into said cache memory (39),

c) an entry step for inserting as said cache entry into said cache memory (39), in the case the result of said selection step is that said cache entry is to be inserted, for said data packet said address information and associated output link information.

2. Method according to claim 1, further comprising

a) a checking step for checking for each data packet, whether its address information or associated output link information is already contained in a cache entry,

b) a forwarding step for forwarding said data packet under use of output link information stored in that cache entry, if the address information or associated output link information is found in a cache entry,

wherein if the address information or associated output link information is not found in a cache entry, the evaluation step and the selection step are performed for said data packet.

3. Method according to claim 1 or 2, wherein in the case a cache entry is to be made, said output link information is obtained from a lookup step using a routing table.

4. Method according to claim 3, wherein said lookup step is started together with the checking step and is stopped if the address information or associated output link information is found in a cache entry.

5. Method in accordance with one of claims 1 to 4, wherein data packets associated with burst-type traffic are selected for inserting a corresponding cache entry into said cache memory (39).

6. Method in accordance with one of claims 1 to 5, wherein those data packets that have a data packet header field identifying said data packet as a starting or synchronizing data packet of a sequence of related data packets, are selected for inserting a corresponding cache entry into said cache memory (39).

7. Method in accordance with one of claims 1 to 6, wherein the selection for inserting a corresponding cache entry into said cache memory (39) is made on the basis of criteria contained in the header of the data packet.

8. Method in accordance with claim 7, wherein the criteria include address information and communication protocol information.

9. Method in accordance with one of claims 1 to 8, wherein the selection of a data packet for cache entry is made also in the same unit that determines the output link information.

10. Method in accordance with one of claims 1 to 9, further comprising a removal decision step wherein a decision whether to remove a cache entry from the cache memory (39) is made in dependence of the type of flow to which the respective cache entry is associated, and in dependence of the cache filling grade.

11. Apparatus for controlling the insertion of cache entries into a cache memory (39) in a device, in which incoming data packets are directed to output links according to address information, the apparatus comprising:

a) an evaluator (17) for evaluating for each said incoming data packet classification information which is relevant to the type of flow or to the priority to which said data packet is associated,

b) a selector (17) for selecting based on the result of said evaluation step whether for said data packet said cache entry is to be inserted into said cache memory (39),

c) a cache read/write unit (17) for inserting as said cache entry into said cache memory (39), in the case the result of said selection step is that said cache entry is to be inserted, for said data packet said address information and associated output link information.

12. Apparatus according to claim 11, further comprising an output unit (29) for forwarding said data packet under use of output link information stored in a cache entry, if the address information or associated output link information is found in that cache entry.

13. Apparatus according to claim 11 or 12, further comprising a routing table.