Apparatus and method for fast search table update in a network switch

Patent metadata

Field	Value
Publication number	US-9553829-B2
Application number	US-201414540927-A
Country	US
Kind code	B2
Filing date	Nov 13, 2014
Priority date	Nov 13, 2014
Publication date	Jan 24, 2017
Grant date	Jan 24, 2017

Abstract

A network switch comprises a plurality of packet processing units configured to process a received packet through multiple packet processing stages based on search result of a table. The network switch further comprises one or more memory units configured to maintain the table to be searched and provide the search result to the packet processing units. The network switch further comprises a table managing unit configured to accept a plurality of rules on bulk update to the table specified by a control unit, and perform the bulk update on the table based on the rules specified by the control unit without the control unit accessing the table directly for the bulk update.

First claim

What is claimed is:

1. A system to support bulk search table update for a network switch, comprising:
said network switch, which comprises:
a plurality of packet processing units configured to process a received packet through multiple packet processing stages based on search result of a table;
one or more memory units configured to:
maintain and search the table to be searched, wherein each memory row in the memory units is configured to store a plurality of entries in the table, wherein each entry in the table is in a pair of (key, result) sections;
provide the search result to the packet processing units;

a table managing unit configured to:
accept a plurality of rules on bulk update to the table specified by a control unit;
perform the bulk update on the table based on the specified rules by
retrieving the entries in the table from each memory row within a table update range of the memory units specified in the rules;
matching a matching pattern and a matching mask specified in the rules with the key and result sections of each of the retrieved entries, respectively, wherein the matching mask indicates an element of the network switch to be updated and the matching pattern represents the matching value for the element identified;
updating the key and result sections of each of the table entries via a substitution pattern and a substitution mask specified in the rules, respectively if a matching is found;
committing the updated table entries back to the memory row within the table update range of the memory units;

said control unit configured to provide the plurality of rules on bulk update to the table managing unit without the control unit accessing the table directly for the bulk update.

2. The system of claim 1 , further comprising:
an interface module configured to:
accept instructions from the packet processing units and/or the table managing unit;
generate commands specific to the memory units based on the instructions;
collect and return the results of executing the commands back to the packet processing units and/or the table managing unit.

3. The system of claim 1 , wherein:
each of the memory units is a static random-access memory (SRAM) or ternary content-addressable memory.

4. The system of claim 1 , wherein:
one of the packet processing units has its own dedicated memory unit that can only be accessed by the packet processing unit.

5. The system of claim 1 , wherein:
more than one of the packet processing units share one of the memory units.

6. The system of claim 1 , wherein:
one of the packet processing units is configured to access more than one of the memory units in parallel.

7. The system of claim 1 , wherein:
each memory line in one of the memory units is configured to store only one entry in the table.

8. The system of claim 1 , wherein:
all entries in the table have the same storage configuration in each memory line in the memory units.

9. The system of claim 1 , wherein:
the control unit is another component on a same chip as the network switch.

10. The system of claim 1 , wherein:
the control unit is configured to interact with the network switch remotely over a communication network following a communication protocol.

11. The system of claim 1 , wherein:
the control unit is configured to offload the bulk update of the table to the network switch.

12. The system of claim 1 , wherein:
the rules include parameters on priority of the bulk update with respect to the packet being processed, indicating that all tabled-based processing and routing is paused pending the completion of the bulk table update.

13. The system of claim 1 , wherein:
each memory unit has an associated bitmap having the same width as the memory lines of the memory unit, wherein the bitmap represents configuration of the table entries in the memory unit.

14. The system of claim 1 , wherein:
the substitution mask and the matching mask specified by the rules are the same, indicating that the same element of the network switch is being updated.

15. The system of claim 1 , wherein:
the substitution mask and the matching mask specified by the rules are different, indicating that a current element of the network switch is being replaced by another element of the network switch.

16. The system of claim 1 , wherein:
the table managing unit is configured to report result of the bulk update to the control unit.

17. A network switch to support bulk search table update, comprising:
a plurality of packet processing units configured to process a received packet through multiple packet processing stages based on search result of a table;
one or more memory units configured to:
maintain and search the table to be searched, wherein each memory row in the memory units is configured to store a plurality of entries in the table, wherein each entry in the table is in a pair of (key, result) sections;
process and provide the search result to the packet processing units;

a table managing unit configured to:
accept a plurality of rules on bulk update to the table specified by a control unit;
perform the bulk update on the table based on the specified rules without the control unit accessing the table directly for the bulk update by
retrieving the entries in the table from each memory row within a table update range of the memory units specified in the rules;
matching a matching pattern and a matching mask specified in the rules with the key and result sections of each of the retrieved entries, respectively, wherein the matching mask indicates an element of the network switch to be updated and the matching pattern represents the matching value for the element identified;
updating the key and result sections of each of the table entries via a substitution pattern and a substitution mask specified in the rules, respectively if a matching is found;
committing the updated table entries back to the memory row within the table update range of the memory units.

18. A method to support bulk search table update for a network switch, comprising:
maintaining a table used to process a received packet through multiple packet processing stages in one or more memory units of the network switch, wherein each memory row in the memory units is configured to store a plurality of entries in the table, wherein each entry in the table is in a pair of (key, result) sections;
providing to the switch a plurality of rules on bulk update to the table via a control unit;
accepting the plurality of rules on the bulk update to the table by the network switch;
performing the bulk update on the table based on the specified rules without the control unit accessing the table directly for the bulk update by
retrieving the entries in the table from each memory row within a table update range of the memory units specified in the rules;
matching a matching pattern and a matching mask specified in the rules with the key and result sections of each of the retrieved entries, respectively, wherein the matching mask indicates an element of the network switch to be updated and the matching pattern represents the matching value for the element identified;
updating the key and result sections of each of the table entries via a substitution pattern and a substitution mask specified in the rules, respectively if a matching is found;
committing the updated table entries back to the memory row within the table update range of the memory units.

19. The method of claim 18 , further comprising:
accessing more than one of the

Assignees

• Xpliant Inc
• Cavium Inc

Inventors

• Wang Weihuang
• Balan Mohan
• Atluri Srinath

Classifications

• H04L45/60

  Router architectures · CPC title

• H04L45/742

  Route cache; Operation thereof · CPC title

• H04L45/563

  Software download or update · CPC title

• H04L45/54

  Organization of routing tables · CPC title

• H04L49/65 Primary

  Re-configuration of fast packet switches · CPC title