Method and apparatus for table aging in a network switch

Patent metadata

Field	Value
Publication number	US-9773036-B2
Application number	US-201414289548-A
Country	US
Kind code	B2
Filing date	May 28, 2014
Priority date	May 28, 2014
Publication date	Sep 26, 2017
Grant date	Sep 26, 2017

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 network switch comprising:
at least one core including a plurality of processing units;
an on-chip memory storing a plurality of search tables, wherein the plurality of processing units communicates with the on-chip memory to perform table searching;
an aging configurations set including an aging configuration indicator value for each of the plurality of search tables and a mask bit value for each entry of each of the plurality of search tables; and
a table aging module including an embedded memory and stores both the mask bit values and an age memory bit value for each entry of each of the 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;
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 the aging configuration indicator value of the search table storing the at least one of the entries indicates that aging is enabled;
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; and
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.

2. The network switch of claim 1 , wherein once there is a search table hit, the table aging module receives a Table ID and a hit address from a corresponding search request.

3. The network switch of claim 1 , wherein the table aging module performs an age marking process and an age refreshing process.

4. The network switch of claim 3 , wherein the age refreshing process examines all age memory bits corresponding to the plurality of search tables.

5. The network switch of claim 4 , wherein the examination occurs periodically based on a configured cycle time or is specifically triggered by software.

6. The network switch of claim 4 , 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.

7. The network switch of claim 1 , wherein the aging configurations set includes configurations and age profiles.

8. The network switch of claim 7 , wherein each of the plurality of search tables is in one of the aging configurations and includes an aging enable bit storing the aging configuration indicator value and a pointer into one of the age profiles.

9. The network switch of claim 7 , wherein each of the age profiles specifies a refresh time period for a search table and specifies an aging memory allocation in the central aging memory pool.

10. The network switch of claim 8 , wherein the central aging memory pool is a part of the on-chip memory.

11. The network switch of claim 7 , wherein the central aging memory pool includes age mark memory and age mask memory.

12. The network switch of claim 11 , wherein each of the age mark memory and the age mask memory contains multiple physical memory tiles, wherein memories of the central aging memory pool are group into tiles.

13. The network switch of claim 11 , wherein age marking is applied to the age mark memory.

14. The network switch of claim 11 , wherein the age mask memory provides per-entry control granularity, when the mast bit value of a mask bit is set to 0, a corresponding table entry does not participate in an aging process.

15. A method of operating a network switch, the method comprising:
parallel processing multiple table search requests to a plurality of tables each having plurality of entries;
upon a table hit of one of the entries, generating information for processing by a table aging module including a memory bit value for the one of the entries, wherein the information indicates an aging configuration indicator value of the table storing the one of the entries that was hit and a mask bit value of the one of the entries, and further wherein one of the memory bits indicates whether the one of the entries has been subject to a search hit since a previous aging process;
determining if a request aging indicator of one of the table search requests that caused the table hit indicates that aging is disabled for the one of the table search requests;
refraining from updating the age memory bit value of the one of the entries when the request aging indicator indicates that aging is disabled for the one of the table search requests even if the aging configuration indicator value of the table storing the at least one of the entries indicates that aging is enabled; and
the table aging module performing aging of tables in parallel using a central aging memory pool, wherein the aging of the tables comprises:
identifying the mask bit value of the entry and the aging configuration indicator value of the search table storing the entry; and
based on both the aging configuration indicator value of the search table storing the entry and the mask bit value, refraining from aging the entry, regardless of the memory bit value of the entry, if the aging configuration indicator value of the search table storing the entry indicates that the search table storing the entry should be aged, but the mask bit value indicates that the entry should not be aged;

wherein the memory bit values and the mask bit values are stored in the central aging memory pool.

16. The method of claim 15 , wherein the table aging module uses the generated information to perform the aging of tables.

17. The method of claim 16 , wherein the aging of tables involves two separate processes including an age marking process and an age refreshing process.

18. The method of claim 17 , further comprising pausing the age refreshing process.

19. The method of claim 17 , further comprising, prior to parallel processing multiple table search requests:
programmably assigning a first subset of tiles as an age mark memory;
programmably assigning a second subset of the tiles as an age mask memory; and
programmably configuring the table aging module.

20. The network switch of claim 1 , wherein the table aging module further determines which one or more of the plurality of search tables to age based on the aging configuration indicator value associated with the one or more of the plurality of search tables such that the table aging module is able to selectively age only a subset of the plurality of search tables based on the aging configurations set.

21. The network switch of claim 1 , wherein the embedded memory is separate from the search tables.

22. The method of claim 15 , wherein the memory bit

Assignees

• Cavium Inc

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