Management of entries in a network element forwarding memory

• US 6,118,760 A
• Filed: 06/30/1997
• Issued: 09/12/2000
• Est. Priority Date: 06/30/1997
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Hoffman, Donald L., Murthy, Shree, Zaumen, William T.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): HOM, SHICK C
• Application Number:
  US08/884,946
• Time in Patent Office: 1,170 Days
• Field of Search: 370/229, 370/330, 370/381, 370/386, 370/428, 370/469, 370/475, 370/237, 370/254, 370/389, 370/396, 370/397, 370/401, 370/402, 370/468, 365/49, 395/180, 395/182.03
• US Class Current: 370/229
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 69/28 Timers or timing mechanisms used in protocols
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

The invention generally provides for a network element and methods in the network element for allowing a matching entry in a forwarding memory to be found in a single search of the memory, for determining when an entry should be placed in the memory, and for determining when an entry should be removed from the memory, in order to make more efficient use of the fixed space available in the memory. The invention is particularly useful in making more efficient use of a Content Addressable Memory (CAM) for storing flow entries, and configuring the CAM to index an associated memory that stores forwarding and quality of service information for each CAM entry.

Claims

1. In a network element having a forwarding memory for storing a plurality of entries used for forwarding received packets, a method of managing the storage of the entries comprising the steps of:

making a first entry in the forwarding memory based upon a header of a first received packet; and

one of

marking the first entry for removal if a second packet having a header matching the first entry is not received before a first time has elapsed, and

waiting a second time not equal to the first time before marking the first entry for removal if the second packet having the header matching the first entry is received before the first time has elapsed.

2. The method as in claim 1 wherein the second time is longer than the first time.

3. The method as in claim 2 where the first time is approximately one second and the second time is approximately three seconds.

4. The method as in claim 1 further comprising the step of

marking the first entry for removal if a third packet having a third header matching the first entry is not received before the second time has elapsed.

5. The method as in claim 1 further comprising the step of waiting a third time before marking the first entry for removal if a third packet having a third header matching the first entry is received before the second time has elapsed.

6. The method as in claim 1 prior to the step of making the first entry, further comprising the step of

searching the forwarding memory for a match between the header of the first received packet and an entry in the forwarding memory,

and wherein the step of making the first entry is performed in response to not finding the match.

7. The method as in claim 5 wherein the third time is different than the second time.

8. The method as in claim 6 further comprising the step of selecting a most specific one of a number of matching entries.

9. The method as in claim 1 further comprising the step of

ordering the plurality of entries in the forwarding memory from most specific to least specific, the most specific having the fewest wildcard characters of any of the plurality of entries.

10. The method as in claim 1 wherein the header further comprises a Layer 4 address.

11. The method as in claim 10 wherein the header further comprises a Layer 4 address.

12. The method as in claim 1 wherein at least one of the first time and the second time is selected based on predefined network layer addresses.

13. In a network element having an address table for storing a plurality of entries used for forwarding received packets, and a timer associated with each entry, a method of managing the entries in the address table comprising the steps of:

receiving a first packet;

making a first entry in the address table based upon a header of the first packet;

setting a first timer to a first time; and

setting a second timer to a second time not equal to the first time if a second packet matching the first entry is received before the first time has elapsed.

14. The method as in claim 13 wherein the second time is longer than the first time.

15. The method as in claim 14 wherein the first time is approximately one second and the second time is approximately three seconds.

16. The method as in claim 13 further comprising the step of

deleting the first entry if the second packet matching the first entry is not received before the first time has elapsed.

17. The method as in claim 13 wherein the first timer is the second timer.

18. The method as in claim 13

wherein the first entry comprises an activity field for indicating that the first entry has matched a received second packet.

19. The method as in claim 13 prior to setting the second timer further comprising the steps of:

searching the address table to find a matching entry in response to receiving the second packet, the first entry being a most specific one of a plurality of matching entries.

20. The method as in claim 13 further comprising the steps of:

ordering the plurality of entries in the forwarding memory from most specific to least specific, the most specific having the fewest wildcard characters of any of the plurality of entries; and

searching the address table to find a matching entry.

21. The method as in claim 20 wherein the step of searching the address table to find the matching entry includes searching based on Layer 3 and Layer 4 headers of a received packet.

22. A network element for managing a plurality of entries in a forwarding memory, comprising:

means for initiating a search of the forwarding memory for an entry matching a portion of a first header of a received first packet;

means for making a first entry in the forwarding memory in response to finding no entry matching the portion of the first header of the received first packet, the first entry having an activity field indicating whether the first entry has matched a received second packet;

means for setting a first timer to a first time;

means for checking the activity field in response to the first timer running out; and

means for setting a second timer to a second time not equal to the first time in response to the activity field indicating that the first entry has matched the received second packet.

23. The network element as in claim 22 wherein the second time is longer than the first time.

24. The network element as in claim 23 wherein the first time is approximately one second and the second time is approximately three seconds.

25. The network element as in claim 22 further comprising

means for invalidating the first entry in response to the activity field indicating that the first entry has not matched the received second packet.

26. The network element as in claim 22 further comprising means for setting a third timer to a third time in response to the activity field indicating that the first entry has matched a received third packet before expiration of the second time.

27. The network element as in claim 22 wherein the first header is a Layer 3 header.

28. The network element as in claim 26 wherein the third time is approximately equal to the second time.

29. The network element as in claim 22 wherein the first entry comprises Layer 4 information.

30. The network element as in claim 22 wherein the second timer is the first timer.

31. The network element as in claim 22 further comprising

memory configured for storing the forwarding memory and the plurality of entries;

and

means for ordering the plurality of entries in the memory from most specific to least specific.

32. The network element as in claim 31 wherein the memory is a content addressable memory.

33. The network element as in claim 22 wherein at least one of the means for making the first entry, means for setting the first timer, means for checking the activity field, and means for setting the second timer is a programmed processor.

34. The network element as in claim 22 wherein the first timer is a software timer.

35. The network element as in claim 22 wherein the means for initiating the search is a header matching logic circuit.

36. The network element as in claim 22 further comprising means for updating the activity field in response to the first entry matching the received second packet prior to the first timer running out.