High-speed flexible longest match retrieval

• US 6,570,866 B1
• Filed: 03/11/1999
• Issued: 05/27/2003
• Est. Priority Date: 03/12/1998
• Status: Expired due to Term

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Ogura, Naoyuki, Murase, Tutomu
• Primary Examiner(s): CANGIALOSI, SALVATORE A
• Application Number:
  US09/266,466
• Time in Patent Office: 1,538 Days
• Field of Search: 370/351, 370/392, 711/108, 711/100
• US Class Current: 370/351
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A router having a high-speed and flexible longest match retrieval device is disclosed. A plurality of entries are divided into a plurality of primary retrieving circuits each retrieving a primary match mask and a primary match entry depending on a given address. The primary match masks and entries obtained by the primary retrieving circuits are used to determine the longest match routing information.

Claims

1. A device for retrieving a longest routing match to a given address from a plurality of entries containing routing information in a router, the device comprising:

a plurality of primary retrieving circuits each of which comprises a memory storing at least one first entry and a mask associated therewith, wherein each of the primary retrieving circuits retrieves a primary match entry which is a longest match to the given address and outputs a primary match mask associated with the primary match entry;

a selector performing a logical OR operation for selecting a longest match mask from the primary match masks output by the primary retrieving circuits, the longest match mask having a longest non-masking bit length among the primary match masks; and

at least one associative memory storing a plurality of second entries, each of which is formed by coupling a first entry with a corresponding mask together, wherein the associative memory compares a combination of the given address and the longest match mask to the plurality of second entries and outputs corresponding to a first entry included in a second entry accessed as the longest routing match.

4. The device according to claim 1, wherein the logic circuit comprises a maximum value detector for detecting a maximum value as the longest match mask to the given address from the primary match masks.

5. The device according to claim 1, wherein a single associative memory stores the plurality of second entries corresponding to the plurality of entries stored in the primary retrieving circuits.

6. The device according to claim 1 further comprising,

a plurality of associative memories each storing at least one second entry, each of which is formed by coupling an entry with a corresponding mask, wherein each of the associative memories outputs an entry of a second entry associated with the combination of the given address and the longest match mask; and

a combiner for combining entries output from the associative memories to produce the longest routing match.

7. The device according to claim 6, wherein the number of associative memories correspond to the number of primary retrieving circuits.

2. A device for retrieving a longest routing match to a given address from a plurality of entries containing information in a router, the device comprising:

a plurality of primary retrieving circuits each of which comprises a memory storing at least one first entry and a mask associated therewith, wherein each of the primary retrieving circuits retrieves a primary match entry which is a longest match to the given address and outputs a primary match mask associated with the primary match entry;

a logic circuit for selecting a longest match mask from the primary match masks output by the primary retrieving circuits, the longest match mask having a longest non-masking bit length among the primary match masks;

wherein the logic circuit comprises an OR circuit performing a logical OR function on the primary match masks to produce the longest match mask;

at least one associative memory storing a plurality of second entries, each of which is formed by coupling a first entry with a corresponding mask together, wherein the associative memory compares a combination of the given address and the longest match mask to the plurality of second entries and outputs corresponding to a first entry included in a second entry accessed as the longest routing match.

3. The device according to claim 2, wherein the OR circuit is a wired-OR circuit.

8. A device for retrieving a longest routing match to a given address from a plurality of entries corresponding to routing information in a router, the device comprising:

a plurality of primary retrieving circuits each of which comprises a memory storing at least one first entry and a mask associated therewith so that the primary retrieving circuits store the plurality of first entries, wherein each of the primary retrieving circuits retrieves a primary match entry which is a longest match to the given address and outputs the mask associated with the primary match entry;

a plurality of associative memories each corresponding to a respective primary retrieving circuit, each of the associative memories storing said at least one first entry from the respective primary retrieving circuit, wherein each of the associative memories outputs data corresponding to the entry associated with the given address;

a selector performing a logical OR operation for selectively enabling the associative memories depending on which primary match mask output by the primary retrieving circuits has a longest non-masking bit length; and

a combiner for combining the output data of each enabled associative memory to produce the longest routing match.

9. A device for retrieving a longest routing match to a given address from a plurality of entries corresponding to routing information in a router, the device comprising:

a plurality of primary retrieving circuits each of which comprises a memory storing at least one first entry and a mask associated therewith so that the primary retrieving circuits store the plurality of first entries, wherein each of the primary retrieving circuits retrieves a primary match entry which is a longest match to the given address and outputs the mask associated with the primary match entry;

a plurality of associative memories each corresponding to a respective primary retrieving circuit, each of the associative memories storing said at least one first entry from the respective primary retrieving circuit, wherein each of the associative memories outputs data corresponding to the entry associated with the given address;

a logic circuit for selectively enabling the associative memories depending on which primary match mask output by the primary retrieving circuits has a longest non-masking bit length;

wherein the logic circuit comprises;

an OR circuit performing a logical OR function on the primary match masks to produce a combined mask, a coincidence detector for detecting coincidence between the combined mask and each of the primary match masks to produce an enabling signal which is used to enable a corresponding associative memory; and

a combiner for combining the output data of each enabled associative memory to produce the longest routing match.

10. A device for retrieving a longest routing match to a given address from a plurality of entries which are routing information in a router, the device comprising:

a plurality of primary retrieving circuits each comprising;

a memory storing at least one entry and a mask associated therewith; and

a searcher searching the memory for an entry which is a longest match to the given address and outputting the mask associated with the entry which is the longest match and further searching the memory for a primary match entry matching the output mask;

a selector performing a logical OR operation selecting a longest match mask from the masks input from the primary retrieving circuits, the longest match mask having a longest non-masking bit length among the masks; and

a second logic circuit selecting a longest match entry from the primary match entries input from the primary retrieving circuits based on the longest match mash and outputting the longest match entry as the longest routing match.

12. The device according to claim 10, wherein the second logic circuit comprises:

a coincidence detector for each of the primary retrieving circuits, each coincidence detector detecting a coincidence between the longest match mask and each of the primary match entries; and

a gate for each of the primary retrieving circuits, each gate outputting a corresponding primary match entry input from the primary retrieving circuit as the longest routing match when the coincidence is detected.

11. A device for retrieving a longest routing match to a given address from a plurality of entries which are routing information in a router, the device comprising:

a plurality of primary retrieving circuits each comprising;

a memory storing at least one entry and a mask associated therewith;

a searcher searching the memory for an entry which is a longest match to the given address and outputting the mask associated with the entry which is the longest match and further searching the memory for a primary match entry matching the output mask;

a first logic circuit selecting a longest match mask from the masks input from the primary retrieving circuits, the longest match mask having a longest non-masking bit length among the masks, wherein;

the first logic circuit is an OR circuit performing a logical OR function on the primary match masks input from the primary retrieving circuits; and

a second logic circuit selecting a longest match entry from the primary match entries input from the primary retrieving circuits based on the longest match mash and outputting the longest match entry as the longest routing match.

13. A device for retrieving a longest routing match to a given address from a plurality of entries corresponding to routing information in a router, the device comprising:

a plurality of primary retrieving circuits each comprising;

a memory storing at least one entry and a mask associated therewith; and

a searcher searching the memory for an entry which is a longest match to the given address and outputting the mask associated with the entry which is the longest match and further searching the memory for a primary match entry matching the output mask;

a selector performing a logical OR operation selecting a longest match mask from the masks input from the primary retrieving circuits and outputting the longest match mask as the mask input to the primary retrieving circuits so that each of the primary retrieving circuits outputs the primary match entry associated with the longest match mask, the longest match mask having a longest non-making bit length among the masks; and

a second logic circuit selecting a longest match entry from the primary match entries input from the primary retrieving circuits based on the longest match mask and outputting the longest match entry as the longest routing match.

15. The device according to claim 13, wherein the second logic circuit comprises:

a maximum value detector for detecting a maximum value from the primary match masks to produce a selection signal indicating which primary match mask has the maximum value; and

a selector for selecting one of the primary match entries input from the primary retrieving circuits based on the selection signal to produce the longest match entry as the longest routing match.

14. A device for retrieving a longest routing match to a given address from a plurality of entries corresponding to routing information in a router, the device comprising:

a plurality of primary retrieving circuits each comprising;

a memory storing at least one entry and a mask associated therewith;

a searcher searching the memory for an entry which is a longest match to the given address and outputting the mask associated with the entry which is the longest match and further searching the memory for a primary match entry matching the output mask;

a first logic circuit selecting a longest match mask from the masks input from the primary retrieving circuits and outputting the longest match mask as the mask input to the primary retrieving circuits so that each of the primary retrieving circuits outputs the primary match entry associated with the longest match mask, the longest match mask having a longest non-making bit length among the masks;

a second logic circuit selecting a longest match entry from the primary match entries input from the primary retrieving circuits based on the longest match mask and outputting the longest match entry as the longest routing match; and

the first logic circuit is an OR circuit performing a logical OR circuit performing a logical OR function on the primary match masks to produce the longest match mask.

16. A device for retrieving a longest routing match to a given address from a plurality of entries corresponding to routing information in a router, the device comprising:

a plurality of primary retrieving circuits each comprising;

a memory storing at least one entry and a mask associated therewith;

a searcher searching the memory for an entry which is a longest match to the given address and outputting the mask associated with the entry which is the longest match and further searching the memory for a primary match entry matching the output mask;

a first logic circuit selecting a longest match mask from the masks input from the primary retrieving circuits and outputting the longest match mask as the mask input to the primary retrieving circuits so that each of the primary retrieving circuits outputs the primary match entry associated with the longest match mask, the longest match mask having a longest non-making bit length among the masks, wherein;

the first logic circuit is an OR circuit performing a logical OR function on the primary match masks to produce the longest match masks;

a second logic circuit selecting a longest match entry from the primary match entries input from the primary retrieving circuits based on the longest match mask and outputting the longest match entry as the longest routing match; and

, wherein

the second logic circuit is an OR circuit performing a logical OR function on the primary match entries to produce the longest match entry.

17. A device for retrieving a longest routing match to a given address from a plurality of entries corresponding to routing information in a router, the device comprising:

a plurality of primary retrieving circuits each comprising;

a memory storing at least one first entry and a mask associated therewith; and

a searcher searching the memory for an entry which is a longest match to the given address and outputting the primary match mask associated with the first entry which is the longest match when a selection clock signal is in a first state and searching the memory for a primary match entry matching to an input mask when the selection clock signal is in a second state; and

a selector performing a logical OR operation selecting a longest match mask from the primary match masks input from the primary retrieving circuits when the selection clock signal is in the first state and outputting the longest mask as the mask input to the primary retrieving circuits so that each of the primary retrieving circuits outputs the primary match entry associated with the longest match mask, the longest match mask having a longest non-masking bit length among the masks and, when the selection clock signal is in the second state, selecting a longest match entry from primary match entries input from the primary retrieving circuits based on the longest match mask and outputting the longest match entry as the longest routing match.

18. A device for retrieving a longest routing match to a given address from a plurality of entries corresponding to routing information in a router, the device comprising:

a plurality of primary retrieving circuits each comprising;

a memory storing at least one first entry and a mask associated therewith;

a searcher searching the memory for an entry which is a longest match to the given address and outputting the primary match mask associated with the first entry which is the longest match when a selection clock signal is in a first state and searching the memory for a primary match entry matching to an input mask when the selection clock signal is in a second state;

a logic circuit selecting a longest match mask from the primary match masks input from the primary retrieving circuits when the selection clock signal is in the first state and outputting the longest match mask as the mask input to the primary retrieving circuits so that each of the primary retrieving circuits outputs the primary match entry associated with the longest match mask, the longest mask having a longest non-masking bit length among the masks and, when the selection clock signal is in the second state, selecting a longest match entry from primary match entries input from the primary retrieving circuits based on the longest match mask and outputting the longest match entry as the longest routing match, wherein the logic circuit comprises;

an OR circuit performing a logical OR function on outputs of the primary retrieving circuits to produce combined outputs; and

a selector switch switching a destination of the combined outputs depending on the selection clock signal such that the combined outputs are transferred to the primary retrieving circuits when the selection clock signal is in the first state and are output as the longest match entry when the selection clock signal is in the second state.

19. A method for retrieving a longest routing match to a given address from a plurality of entries each entry being routing information in a router, the method comprising:

dividing the plurality of entries into a plurality of primary retrieving circuits, each comprising a memory storing at least one first entry with a mask associated therewith;

retrieving a primary match entry which is a longest match to the given address to produce a primary match mask associated with the primary match entry;

performing a logical OR function to select a longest match mask from primary match masks obtained by the primary retrieving circuits, the longest match mask having a longest non-masking bit length among the primary match masks;

storing a plurality of second entries in at least one associative memory, each of the second entries being formed by coupling an entry with a corresponding mask together; and

accessing a second entry associated with a combination of the given address and the longest mask and outputting an entry included in the second entry accessed as the longest match.

20. A method for retrieving a longest routing match to a given address from a plurality of entries corresponding to routing information in a router, the method comprising:

dividing the plurality of entries into a plurality of primary retrieving circuits each comprising a memory storing at least one entry and a mask associated therewith;

retrieving an entry which is a longest match to the given address and outputting the mask associated with the entry;

performing a logical OR function to select a longest match mask from the output masks, the longest match mask having a longest non-masking bit length among the output masks;

storing a plurality of coupled records in a plurality of associative memories, each of the coupled records being formed by coupling the entry and a corresponding mask;

selectively enabling the associative memories based on the mask having the longest non-masking bit length among the output masks; and

combining a coupled record output from each enabled associative memory to produce the longest routing match.

21. A method for retrieving a longest routing match to a given address from a plurality of entries corresponding to routing information in a router, the method comprising:

storing the plurality of entries in a plurality of primary retrieving circuits each of the primary retrieving circuits having a memory storing at least one entry with a corresponding mask;

searching the memory for an entry which is a longest routing match to the given address and outputting a primary mask match;

performing a logical OR function to select a longest match mask from the primary match masks input from the primary retrieving circuits, the longest match mask having the longest non-masking bit length among the primary match masks; and

selecting a longest match mask from the primary match masks input from the primary retrieving circuits, depending on which primary mask is the longest match mask to output the longest match entry as the longest match.

22. A method for retrieving a longest routing match to a given address from a plurality of entries corresponding to routing information in a router, the method comprising:

storing the plurality of entries in a plurality of primary retrieving circuits each primary retrieving circuit including a memory storing at least one entry and a corresponding;

searching the memory for an entry which is a longest match to the given address and further searching the memory for a primary match entry matching the primary match mask;

performing a logical OR function to select a longest match mask from the primary match masks input from the primary retrieving circuits to output the longest match mask as the input mask to the primary retrieving circuits so that each of the primary retrieving circuits outputs the primary match entry associated with the longest match mask, the longest match mask having longest non-masking bit length among the primary match masks; and

selecting a longest match entry from primary match entries inputted from the primary retrieving circuits depending on which primary match mask is the longest match mask to output the longest match entry as the longest match.

23. A router for determining a next hop destination of an input packet by retrieving a longest routing match to an ultimate destination address of the input packet from a plurality of entries, comprising:

an address extractor for extracting the ultimate destination address from the input packet;

a plurality of primary retrieving circuits each comprising a memory storing at least one first entry with a corresponding mask so that the primary retrieving circuits store the plurality of entries, wherein each of the primary retrieving circuits retrieves a primary match entry which is a longest match to the ultimate destination address to produce a primary match mask associated with the primary match entry;

a selector performing a logical OR operation for selecting a longest match mask from primary match masks obtained by the primary retrieving circuits, the longest match mask having a longest non-masking bit length among the primary match masks;

at least one associative memory storing a plurality of second entries each formed by coupling an entry and corresponding mask, wherein the associative memory accesses a second entry associated with a combination of the ultimate destination address and the longest match mask to output an entry included in the secondary entry accessed as the longest match; and

a switch for switching a next hop destination of the packet depending on the longest match.

24. A router for determining a next hop destination of an input packet by retrieving a longest routing match to an ultimate destination address from a plurality of entries, the router comprising:

an address extractor for extracting the ultimate destination address from the input packet;

a plurality of primary retrieving circuits each comprising a memory storing at least one entry and a mask associated therewith, wherein each of the primary retrieving circuits retrieves an entry which is a longest match to the ultimate destination address and outputs the mask associated with that entry;

a plurality of associative memories each corresponding to a respective primary retrieving circuits, each of the associative memories storing said at least one entry from the respective primary retrieving circuit, wherein each of the associative memories outputs the entry associated with the ultimate destination address;

a selector performing a logical OR operation selectively enabling the associative memories depending on which mask output by the primary retrieving circuits has a longest non-masking bit length;

a combiner for combining the output entries of each enabled associative memory to produce the longest routing match; and

a switch for switching a next hop destination of the packet depending on the longest routing match.

25. A router for determining a next hop destination of an input packet by retrieving a longest routing match to ultimate destination address from a plurality of entries, comprising:

an address extractor for extracting the ultimate destination address from the input packet;

a plurality of primary retrieving circuits each comprising;

a memory storing at least one first entry with a corresponding mask so that the primary retrieving circuits store the plurality of entries; and

a searcher for searching the memory for an entry which is a longest match to the ultimate destination address to output a primary match mask associated with the entry and further searching the memory for a primary match entry matching to the primary match mask;

a selector performing a logical OR operation for selecting a longest match mask from primary match masks inputted from the primary retrieving circuits, the longest routing match mask having a longest non-masking bit length among the primary match masks;

a second logic circuit for selecting a longest match entry from primary match entries inputted from the primary retrieving circuits depending on which primary match mask is the longest match mask to output the longest match entry as the longest match; and

a switch for switching a next hop destination of the packet depending on the longest match.

26. A router for determining a next hop destination of an input packet by retrieving a longest routing match to ultimate destination address from a plurality of entries, comprising:

an address extractor for extracting the ultimate destination address from the input packet;

a plurality of primary retrieving circuits each comprising;

a memory storing at least one entry with a corresponding mask so that the primary retrieving circuits store the plurality of entries; and

a searcher for searching the memory for an entry which is a longest routing match to the ultimate destination address to output a primary match mask associated with the entry and further searching the memory for a primary match entry matching an input mask;

a selector performing a logical OR operation for selecting a longest match mask from primary match masks inputted from the primary retrieving circuits to output the longest match mask as the input mask to the primary retrieving circuits so that each of the primary retrieving circuits outputs the primary match entry associated with the longest match mask, the longest match mask having a longest non-masking bit length among the primary match mask;

a second logic circuit for selecting a longest match entry from primary match entries inputted from the primary retrieving circuits depending on which primary match mask is the longest match mask to output the longest match entry as the longest match; and

a switch for switching a next hop destination of the packet depending on the longest match.

27. A router for determining a next hop destination of an input packet by retrieving a longest routing match to an ultimate destination address from a plurality of entries, the router comprising:

an address extractor for extracting the ultimate destination address from the input packet;

a plurality of primary retrieving circuits each comprising;

a memory storing at least one first entry and a mask associated therewith; and

a searcher searching the memory for an entry which is a longest match to the ultimate destination address and outputting the mask associated with the entry when a selection clock signal is in a first state and searching the memory for a primary match entry matching the output mask when the selection clock signal is in a second state;

a selector performing a logical OR operation selecting a longest match mask from the masks input from the primary retrieving circuits when the selection clock signal is in the first state and outputting the longest match mask as the mask input to the primary retrieving circuits so that each of the primary retrieving circuits outputs the primary match entry associated with the longest match mask, the longest match mask having a longest non-masking bit length among the masks and, when the selection clock signal is in the second state, selecting a longest match entry from primary match entries input from the primary retrieving circuits based on the longest match mask and outputting the longest match entry as the longest routing match; and

a switch for switching a next hop destination of the packet depending on the longest routing match.