Network address filter including random access memory

• US 20060193328A1
• Filed: 02/25/2005
• Published: 08/31/2006
• Est. Priority Date: 02/25/2005
• Status: Abandoned Application

• Current Assignee: Exar Corporation (Maxlinear Incorporated)
• Original Assignee: Exar Corporation (Maxlinear Incorporated)
• Inventors: Rao, Ramana, Krall, Donald, Homer, Russell
• Application Number:
  US11/066,692
• Publication Number:
  US 20060193328A1
• Time in Patent Office: Days
• US Class Current: 370/395.32
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 12/437 Ring fault isolation or reconfiguration for SDH/SONET ring networks H04J3/085
• CPC Class Codes: H04L 45/7453 using hashing

Abstract

A network address filter that includes a random access memory configured to store network address data, a processor, and a comparator. The processor is configured to execute a hash function on input data to obtain a random access memory address that is applied to the random access memory to obtain network address data from the random access memory address. The comparator is configured to compare the input data to the network address data and indicate a match between the input data and the network address data.

Claims

1. A network address filter, comprising:

a random access memory configured to store network address data;

a processor configured to execute a hash function on input data to obtain a random access memory address that is applied to the random access memory to obtain network address data from the random access memory address; and

a comparator configured to compare the input data to the network address data and indicate a match between the input data and the network address data.

2. The network address filter of claim 1, wherein the processor is configured to execute the hash function to obtain an index that is used to obtain the random access memory address.

3. The network address filter of claim 1, wherein the hash function is a minimal perfect hash function and the processor is configured to execute the minimal perfect hash function to obtain the random access memory address.

4. The network address filter of claim 1, wherein the processor is configured to read the network address data from the random access memory and generate the hash function based on the network address data in the random access memory.

5. The network address filter of claim 4, wherein the processor is configured to generate a new hash function that replaces the hash function if the network address data in the random access memory is modified.

6. The network address filter of claim 4, wherein the processor is configured to update the hash function if the network address data in the random access memory is modified.

7. The network address filter of claim 1, wherein the processor is configured to change the network address data stored in the random access memory to delete the network address data from the random access memory.

8. The network address filter of claim 1, wherein the processor is configured to maintain an auxiliary table that indicates valid network address data in the random access memory.

9. The network address filter of claim 1, wherein the processor is configured to maintain flags that indicate valid network address data in the random access memory.

10. The network address filter of claim 1, wherein the comparator is a hardware comparator.

11. A network system comprising:

a network node configured to receive a packet that includes multicast address data, the network node comprising;

a random access memory configured to store multicast address entries; and

a processor configured to execute a hash function on the multicast address data to obtain a random access memory address that is applied to the random access memory to obtain the multicast address entry stored at the random access memory address as an output that is compared to the multicast address data to obtain a match result.

12. The network system of claim 11, wherein the network node is configured to replicate and route the packet to one or more serviced network elements in the event the match result is a hit.

13. The network system of claim 11, comprising:

a hardware comparator that compares the output to the multicast address data to obtain the match result.

14. The network system of claim 11, wherein the network node is coupled to a resilient packet ring network to receive the packet that includes the multicast address data.

15. An address filter, comprising:

means for storing address data;

means for obtaining address data from the means for storing address data;

means for comparing input data to the address data to indicate a match between the input data and the address data.

16. The address filter of claim 15, wherein the means for obtaining address data comprises;

means for executing a hash function to obtain an index that is used to obtain an address.

17. The address filter of claim 15, wherein the means for obtaining address data comprises;

means for executing a minimal perfect hash function to obtain an address.

18. The address filter of claim 15, comprising:

means for reading the address data from the means for storing address data; and

means for generating a hash function based on the address data in the means for storing address data.

19. The address filter of claim 15, comprising:

means for revising a hash function if the address data in the means for storing address data is modified.

20. A method of network address filtering comprising:

receiving a packet that includes network address data;

executing a hash function on the network address data to obtain a random access memory address;

reading a network address data entry at the random access memory address of a random access memory; and

comparing the network address data entry read from the random access memory to the network address data to obtain a match result.

21. The method of claim 20, wherein executing a hash function comprises;

executing a minimal perfect hash function with a processor to obtain an index; and

obtaining a random access memory address using the index.

22. The method of claim 20, comprising:

reading the random access memory to obtain network address data entries;

executing a hash function generator to obtain the hash function for the network address data entries.

23. The method of claim 22, comprising:

re-executing the hash function generator to generate a new hash function that replaces the hash function if the network address data in the random access memory is modified.

24. The method of claim 22, comprising:

executing a hash function update program to update the hash function if the network address data in the random access memory is modified.

25. The method of claim 20, comprising deleting a selected network address data entry from the random access memory by at least one of:

changing the selected network address data entry in the random access memory;

maintaining an auxiliary table that indicates the selected network address data entry is invalid; and

maintaining a flag that indicates the selected network address data entry is invalid.