Method and apparatus for table aging in a network switch

Patent metadata

Field	Value
Publication number	US-10216780-B2
Application number	US-201715675336-A
Country	US
Kind code	B2
Filing date	Aug 11, 2017
Priority date	May 28, 2014
Publication date	Feb 26, 2019
Grant date	Feb 26, 2019

Abstract

Embodiments of the present invention relate to a centralized table aging module that efficiently and flexibly utilizes an embedded memory resource, and that enables and facilitates separate network controllers. The centralized table aging module performs aging of tables in parallel using the embedded memory resource. The table aging module performs an age marking process and an age refreshing process. The memory resource includes age mark memory and age mask memory. Age marking is applied to the age mark memory. The age mask memory provides per-entry control granularity regarding the aging of table entries.

First claim

We claim:

1. A table aging module in a network switch, the table aging module comprising:
aging memory tiles including age mark memory including age memory bit values and age mask memory including mask bit values for each entry of a plurality of search tables, wherein each of the age memory bit values indicate whether a corresponding one of the entries has been subject to a search hit since a previous aging process; and
a processing circuit that determines if a request aging indicator of a table search request indicates that aging is disabled for the table search request, wherein at least one of the entries is hit by the table search request and refrains from updating the age memory bit values of the at least one of the entries when the request aging indicator indicates that aging is disabled for the table search request even if an aging configuration indicator value of the search table storing the at least one of the entries indicates that aging is enabled.

2. The table aging module of claim 1 , further comprising an input queue for buffering age marking inputs for table hits to the aging memory tiles in an age marking process performed by the processing circuit.

3. The table aging module of claim 2 , wherein the processing circuit performs an age refreshing process including a bit-wise OR operation of a read-out age mark data in the age mark memory with the inverse of a mask bit in the age mask memory.

4. The table aging module of claim 3 , further comprising an age interrupt queue.

5. The table aging module of claim 4 , wherein when the result of the operation is not all a same value, the result and memory tile address and row address for an aging memory row, which corresponds to a set of search table entries, are pushed into the age interrupt queue.

6. The table aging module of claim 3 , further comprising a refresh state machine for controlling the age refreshing process.

7. A non-transitory computer-readable medium storing a table aging module, the table aging module including both mask bit values and an age memory bit value for each entry of each of a plurality of search tables in a central aging memory pool, wherein each of the age memory bit values indicate whether a corresponding one of the entries has been subject to a search hit since a previous aging process, wherein the table aging module:
determines if a request aging indicator of a table search request indicates that aging is disabled for the table search request, wherein at least one of the entries is hit by the table search request; and
refrains from updating the age memory bit values of the at least one of the entries when the request aging indicator indicates that aging is disabled for the table search request even if an aging configuration indicator value of the search table storing the at least one of the entries indicates that aging is enabled.

8. The non-transitory computer-readable medium of claim 7 , wherein the table aging module includes aging memory tiles apportioned into age mark memory and age mask memory.

9. The non-transitory computer-readable medium of claim 8 , wherein the table aging module performs an age marking process using an input queue for buffering age marking inputs for table hits to the aging memory tiles.

10. The non-transitory computer-readable medium of claim 9 , wherein the table aging module performs an age refreshing process including a bit-wise OR operation of a read-out age mark data in the age mark memory with the inverse of a mask bit in the age mask memory.

11. The non-transitory computer-readable medium of claim 10 , wherein the table aging module includes an age interrupt queue.

12. The non-transitory computer-readable medium of claim 11 , wherein when a result of the bit-wise OR operation is not all a same value, the table aging module pushes the result and memory tile address and row address for an aging memory row that corresponds to a set of the entries, into the age interrupt queue.

13. The non-transitory computer-readable medium of claim 12 , wherein the table aging module includes a refresh state machine for controlling the age refreshing process.

14. The non-transitory computer-readable medium of claim 13 , wherein the age refreshing process examines all age memory bits corresponding to the plurality of search tables.

15. The non-transitory computer-readable medium of claim 14 , wherein the examination occurs periodically based on a configured cycle time or is specifically triggered by software.

16. The non-transitory computer-readable medium of claim 15 , wherein when an age memory bit is unmarked, software is notified that a respective table entry is stale, and when the age memory bit is marked, the age memory bit is reset as unmarked in preparation for next round of age marking and age refreshing.

17. The non-transitory computer-readable medium of claim 16 , wherein the table aging module identifies both the mask bit value of one or more of the entries and the aging configuration indicator value of the search table storing the one or more of the entries.

18. The non-transitory computer-readable medium of claim 17 , wherein the table aging module, based on both the aging configuration indicator value of the search table storing the one or more of the entries and the mask bit values of the one or more of the entries, refrains from aging the one or more of the entries, regardless of the age memory bit values of the one or more entries, if the aging configuration indicator value of the search table storing the one or more of the entries indicates that the search table storing the one or more of the entries should be aged, but the mask bit values indicate that the one or more of the entries should not be aged.

19. A table aging module in a network switch, the table aging module comprising:
mask bit values and an age memory bit value for each entry of each of a plurality of search tables in a central aging memory pool, wherein each of the age memory bit values indicate whether a corresponding one of the entries has been subject to a search hit since a previous aging process;
means for determining if a request aging indicator of a table search request indicates that aging is disabled for the table search request, wherein at least one of the entries is hit by the table search request; and
means for refraining from updating the age memory bit values of the at least one of the entries when the request aging indicator indicates that aging is disabled for the table search request even if an aging configuration indicator value of the search table storing the at least one of the entries indicates that aging is enabled.

20. The table aging module of claim 19 , further comprising aging memory tiles apportioned into age mark memory and age mask memory.

21. The table aging module of claim 20 , further comprising means for performing an age marking process using an input queue for buffering age marking inputs for table hits to the aging memory tiles.

22. The table aging module of claim 21 , further comprising means for performing an age refreshing process including a bit-wise OR operation of a read-out age mark data in the age mark memory with the inverse of a mask bit in the age mask memory.

23. The table aging module of claim 22 , further comprising an age interrupt queue.

24. The table aging module of claim 23 , wherein when a result of the bit-wise OR operation is not all a same value, further comprising means for pushing the result and memor

Assignees

• Cavium Inc
• Cavium Llc

Inventors

• Wang Weihuang
• Schmidt Gerald
• Daniel Tsahi
• Balan Mohan

Classifications

• H04L49/309

  Header conversion, routing tables or routing tags · CPC title

• H04L49/3009 Primary

  Header conversion, routing tables or routing tags · CPC title

• H04L49/252

  Store and forward routing · CPC title

• H04L49/00

  Packet switching elements · CPC title

• H04L45/02

  Topology update or discovery · CPC title