Accelerated hierarchical address filtering and translation using binary and ternary CAMs

A method for translating a hierarchical address, the method comprising:

• storing a plurality of ternary table entries in a ternary content addressable memory, each table entry comprising an address and a priority field, the priority field representing a hierarchical level of the entry;
• searching the memory for one or more entries matching an address;
• routing a priority field of entries matching the address to a priority encoding circuitry;
• determining in the priority encoding circuitry that a priority field of an entry has a lowest hierarchical level of the entries matching the address;
• searching the memory for the address and the priority field of the entry having the lowest hierarchical level of the entries matching the address;
• and
• retrieving an entry matching the address.

An apparatus for translating a hierarchical address comprising:

• a binary content addressable memory storing a plurality of table entries, the memory receiving as inputs an address and a priority mask and generating as output a value of one or more data entries stored in the memory;
• circuitry for storing a value of a plurality of priority masks, wherein each value of a priority mask is individually addressable;
• circuitry for addressing a value of a priority mask;
• and
• a controller causing different priority fields to be routed to the memory for a search depending on a result of a previous search;
• wherein a search of the table entries stored in the memory is performed by performing a binary search of the priority masks used in searching the memory.

An apparatus for translating a hierarchical address comprising:

• a ternary content addressable memory storing a plurality of table entries, each entry comprising an address and a priority field, the ternary content addressable memory receiving a search address as an input and generating a value of one or more data entries stored in the ternary content addressable memory as an output;
• a memory for storing a value of the entries generated by the ternary content addressable memory;
• a priority encoder receiving as an input a priority field of one or more table entries stored in the ternary content addressable memory and generating as an output a highest priority field of the input priority fields;
• and
• an address encoder receiving as an input an address of one or more table entries stored in the ternary content addressable memory and generating as an output a value of an entry having the highest priority field of the priority fields received as inputs by the priority encoder.

A method for filtering a hierarchical address, the method comprising:

• converting a plurality of ternary table entries into a plurality of binary table entries, wherein each binary entry comprises a binary address and a binary priority mask, the binary priority mask representing a hierarchical level of the entry;
• storing the binary addresses of the plurality of binary table entries in a binary content addressable memory so that a first binary address having a first number of trailing zeros is retrieved from the memory before a second binary address having a second number of trailing zeros, wherein the first number is greater than the second number;
• and
• searching the memory for one or more entries matching an address to determine whether the address is stored in the memory by performing a binary search of the priority masks used in searching the memory.

A method for filtering a hierarchical address, the method comprising:

• storing a plurality of ternary table entries in a ternary content addressable memory, each table entry comprising an address and a priority field, the priority field representing a hierarchical level of the entry;
• searching the memory for one or more entries matching an address;
• routing a priority field of entries matching the address to a priority encoding circuitry;
• determining in the priority encoding circuitry that a priority field of an entry has a lowest hierarchical level of the entries routed to the priority encoding circuitry;
• and
• searching the memory for the address and the priority field of the entry having the lowest hierarchical level of the entries routed to the priority encoding circuitry to determine whether the address is stored in the memory.