Apparatus and methods to store data in a network device and perform longest prefix match (LPM) processing

Patent metadata

Field	Value
Publication number	US-9306851-B1
Application number	US-201314049696-A
Country	US
Kind code	B1
Filing date	Oct 9, 2013
Priority date	Oct 17, 2012
Publication date	Apr 5, 2016
Grant date	Apr 5, 2016

Abstract

The present disclosure describes systems and techniques relating to processing of network communications. According to an aspect of the described systems and techniques, a network device includes a random access memory (RAM); a buffer coupled with the RAM; circuitry configured to copy data from a location in the RAM to the buffer responsive to a received identifier corresponding to a search key corresponding to a received packet; and circuitry configured to compare the data copied to the buffer with the search key to provide a result for use in forwarding of the packet, wherein don't care bits for the comparison are determined from a count of don't care bits encoded in a portion of the location in the RAM indicated by the identifier.

First claim

What is claimed is:

1. A network device comprising:
a random access memory (RAM);
a buffer coupled with the RAM;
circuitry configured to copy data from a location in the RAM to the buffer responsive to a received identifier corresponding to a search key corresponding to a received packet; and
circuitry configured to compare the data copied to the buffer with the search key to provide a result for use in forwarding of the packet, wherein don't care bits for the comparison are determined from a count of don't care bits encoded in a portion of the location in the RAM indicated by the identifier, and wherein the circuitry configured to compare comprises (i) circuitry configured to generate a vector mask from the count, (ii) an XOR gate coupled to compare a predetermined bit of the search key with a corresponding predetermined bit of the data copied to the buffer, and (iii) an AND gate coupled to compare a predetermined bit of the vector mask with an output of the XOR gate.

2. The network device of claim 1 , wherein the search key comprises a network address included in the received packet, the count is encoded in n bits, and
(2 n −1) is declared illegal for the count of don't care bits found in the network address.

3. The network device of claim 1 , wherein the search key comprises a network address and virtual routing and forwarding (VRF) data.

4. The network device of claim 3 , wherein the circuitry configured to compare comprises circuitry configured to check a single bit to determine whether a VRF portion of the data copied to the buffer is all don't care bits or no don't care bits.

5. The network device of claim 3 , further comprising memory allocated for only VRF data, without network address data, for a default record of a virtual network.

6. The network device of claim 1 , further comprising:
multiple random access memories (RAMs) of a same type, wherein the multiple RAMs include the RAM; and
processing circuitry configured to
receive a record to be stored,
split the record among more than three of the multiple RAMs when the record is for access control list (ACL) processing,
divide the record among three of the multiple RAMs when the record includes a 128 bit address and is for longest prefix match (LPM) processing, and
store the record entirely in a single one of the multiple RAMs when the record includes a 32 bit address and is for LPM processing.

7. The network device of claim 1 , wherein the circuitry configured to generate the vector mask from the count comprises a read only memory (ROM).

8. The network device of claim 1 , further comprising multiple random access memories (RAMs), wherein the multiple RAMs include the RAM, wherein each of the RAMs has an associated buffer, and wherein the circuitry configured to compare comprises circuitry configured to compare data in the buffers with the search key in parallel.

9. A method comprising:
receiving, in a network device, a line identifier corresponding to a search key corresponding to a received packet;
copying data from a line in a random access memory to a buffer in accordance with the line identifier;
generating a vector mask from a count of don't care bits encoded in a portion of the line in the random access memory;
comparing the data copied to the buffer with the search key, wherein the comparing comprises (i) XORing the search key with the data in the buffer, and (ii) ANDing the vector mask with result bits of the XORing; and
providing a result of the comparing for use in forwarding of the packet by the network device.

10. The method of claim 9 , wherein the search key comprises a network address included in the received packet, the count is encoded in n bits of the line, and
(2 n −1) is declared illegal for the count of don't care bits found in the network address.

11. The method of claim 9 , wherein the search key comprises a network address and virtual routing and forwarding (VRF) data.

12. The method of 11 , further comprising checking a single bit to determine whether a VRF portion of the data copied to the buffer is all don't care bits or no don't care bits.

13. The method of 11 , further comprising allocating memory for only VRF data, without network address data, for a default record of a virtual network.

14. The method of claim 9 , wherein the random access memory (RAM) is one of multiple RAMs of a same type, the method comprising:
receiving a record to be stored;
splitting the record among more than three of the multiple RAMs when the record is for access control list (ACL) processing;
dividing the record among three of the multiple RAMs when the record includes a 128 bit address and is for longest prefix match (LPM) processing; and
storing the record entirely in a single one of the multiple RAMs when the record includes a 32 bit address and is for LPM processing.

15. The method of claim 9 , wherein the generating comprises using a read only memory (ROM) to produce the vector mask.

16. The method of claim 9 , wherein the comparing comprises:
NORing result bits of the ANDing with each other.

17. The method of claim 9 , wherein the copying comprises copying data from respective lines in respective random access memories to respective buffers in accordance with the line identifier, and the comparing comprises comparing the data in the buffers with the search key in parallel.

Assignees

• Marvell Int Ltd

Inventors

• Gazit Hillel
• Syed Sohail
• Torjyan Gevorg

Classifications

• H04L45/54

  Organization of routing tables · CPC title

• H04L45/7457

  Electricity · mapped topic

• H04L45/748 Primary

  using longest matching prefix · CPC title

• H04L29/0653

  Electricity · mapped topic

• G06F12/1027

  using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB] · CPC title