Fast classless inter-domain routing (CIDR) lookups

• US 20020143787A1
• Filed: 03/31/2001
• Published: 10/03/2002
• Est. Priority Date: 03/31/2001
• Status: Abandoned Application

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Knee, Simon, Perloff, Ronald S.
• Application Number:
  US09/823,616
• Publication Number:
  US 20020143787A1
• Time in Patent Office: Days
• US Class Current: 707/102
• CPC Class Codes: G06F 7/02 Comparing digital values G06F7/06, G06F7/22, G06F7/38 take precedence
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/54 Organization of routing tables

Abstract

A method and apparatus for efficiently performing a longest match search are provided. According to one embodiment of the present invention, a longest match search of a routing table is initiated in response to receiving a search key (typically a destination IP address of a received packet). To avoid performing fruitless searches, a set of masks are determined that are known to have a potential for matching an entry in the routing table when applied to the search key. A routing table query is formed based upon the search key and the longest mask of the set of masks. Then, the routing table query is applied to the routing table. If subsequent iterations are required, the longest mask is removed from the set of masks and the next routing table query is formed based upon the search key and the longest mask of the updated set of masks.

Claims

1. A method of performing a longest match search comprising:

receiving a search key;

determining a set of masks that when applied to the search key are known to have a potential for matching an entry in a routing table;

forming a routing table query based upon the search key and a longest mask of the set of masks; and

applying the routing table query to the routing table.

2. The method of claim 1, further comprising:

removing the longest mask from the set of masks; and

continuing to apply additional routing table queries until either the set of masks is empty or a matching entry is found in the routing table.

3. The method of claim 1, wherein the search key comprises an Internet Protocol (IP) address.

4. The method of claim 3, wherein the IP address comprises a destination address.

5. The method of claim 3, wherein the IP address comprises a source address.

6. The method of claim 1, wherein said determining a set of masks comprises retrieving an encoded mask vector from a mask table based upon the search key, the encoded mask vector having N bits and capable of identifying N different length masks.

7. The method of claim 1, wherein the longest mask of the set of masks is determined by the following equation:

Mask=(0−

MaskWord)|MaskWord, where;

MaskWord is an encoded mask vector, and

Mask is the longest mask identified by MaskWord.

8. A packet forwarding device comprising:

a plurality of ports upon which packets are received and transmitted;

a routing processor coupled to the plurality of ports to determine an egress port of the plurality of ports for a packet received on an ingress port of the plurality of ports by performing a longest match search comprising one or more routing table queries;

a routing table, coupled to the routing processor, to provide the routing processor with a match indication and information regarding a matching routing table entry, if any, of a plurality of routing table entries stored therein in response to a routing table query; and

a mask table, coupled to the routing processor, to maintain encoded mask vectors identifying mask lengths of the plurality of routing table entries.

9. The packet forwarding device of claim 8, the encoded mask vectors comprise N-bits and are capable of representing N different masks.

10. The packet forwarding device of claim 8, wherein the routing table comprises a Content Addressable Memory (CAM).

11. The packet forwarding device of claim 8, wherein the one or more routing table queries are formed by applying a series of masks determined with reference to the mask table to a search key extracted from the received packet.

13. The method of claim 12, wherein the portion of the destination IP address comprises the most significant N bits of the destination IP address.

14. The method of claim 12, wherein the encoded mask vector includes a plurality of mask length indicator bits that each indicate a mask length by virtue of their position within the encoded mask vector.

15. The method of claim 12, further comprising updating the mask table to include a new encoded mask vector in response to receiving a new routing table entry.

17. The machine-readable medium of claim 16, wherein the longest mask of the set of masks is determined by the following equation:

Mask=(0−

MaskWord)|MaskWord,

where;

MaskWord is an encoded mask vector, and

Mask is the longest mask identified by MaskWord.

18. The machine-readable medium of claim 16, wherein the set of masks is determined by retrieving an encoded mask vector from a mask table based upon the search key, the encoded mask vector having N bits and capable of identifying N different length masks.

12. A method of forwarding a packet comprising:

receiving a packet on an ingress port of a plurality of ports;

extracting a destination Internet Protocol (IP) address from a header of the packet;

using a portion of the destination IP address to index into a mask table to retrieve an encoded mask vector that identifies a series of masks to be applied to the destination IP address during a longest match search of a routing table, the series of masks representing those masks that are known to have a potential for matching an entry in the routing table when applied to the destination IP address;

identifying a longest matching entry in the routing table by performing the longest match search based upon the destination IP address and one or more of the series of masks; and

forwarding the packet to a network device associated with the destination IP address via an egress port of the plurality of ports identified by the longest matching entry.

16. A machine-readable medium having stored thereon data representing sequences of instructions, the sequences of instructions which, when executed by a processor, cause the processor to:

receive a search key;

determine a set of masks that when applied to the search key are known to have a potential for matching an entry in a routing table;

form a routing table query based upon the search key and a longest mask of the set of masks; and

apply the routing table query to the routing table.