Enhanced internet packet routing lookup

• US 6,512,766 B2
• Filed: 08/22/1997
• Issued: 01/28/2003
• Est. Priority Date: 08/22/1997
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Systems, Inc.
• Inventors: Wilford, Bruce A.
• Primary Examiner(s): NGUYEN, STEVEN H D
• Application Number:
  US08/918,506
• Publication Number:
  US 20010012295A1
• Time in Patent Office: 1,985 Days
• Field of Search: 370/389, 370/392, 370/352, 370/395, 370/396, 370/397, 370/899, 370/404, 370/469, 370/475, 370/400-402, 370/395.1, 370/399, 370/395.3, 370/395.32, 370/395-2-3, 370/409, 707/382, 707/252, 707/104, 707/1, 707/6, 711/216-217, 711/321, 711/211, 709/217-219
• US Class Current: 370/389
• 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/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

The invention provides a method and system for routing information lookup for packets using routing protocols such as IP or IP multicast (IGMP), or MPLS (multiprotocol label switching, also known as tag switching or label switching) or MPLS multicast, in which both the destination address and the length of that destination address are matched using a lookup table having separate entries for selected addresses and their lengths, which can be accessed in parallel for multiple representations of destination addresses, and in which the input interface associated with the packet is included in the information used for matching.

Claims

1. A method including:

receiving a packet header and an input interface identifier;

coupling said packet header to plural encapsulation recognizers configured to produce header information from said packet header, said plural encapsulation recognizers recognizing packet headers for multiple protocols, said header information including said input interface identifier;

coupling said header information to plural longest match recognizers so as to produce routing information, said plural longest match recognizers operating in parallel, said routing information determined responsive to a longest match recognized for said header information including said input interface identifier; and

using said routing information to index to one or more routing lookup tables having treatment information regarding treatment of packets, said treatment information being responsive to said routing information and therefore to said input interface identifier.

2. A method as in claim 1, wherein said one or more routing lookup tables include a plurality of entries corresponding to said packet header and differing with regard to said input interface identifier.

3. A method as in claim 2, wherein said one or more routing lookup tables include a plurality of entries corresponding to said packet header and responsive to a multicast packet.

4. A method as in claim 3, wherein said multicast packet is encapsulated using an multiprotocol lable switching protocol.

5. An apparatus for use in packet routing, comprising:

an input interface that receives a packet header, said input interface having an input interface identifier;

plural encapsulation recognizers configured to produce header information from said packet header, said plural encapsulation recognizers recognizing packet headers for multiple protocols, said header information including said input interface identifier;

plural longest match recognizers that produce routing information from said header information, said plural longest match recognizers operating in parallel, said routing information determined responsive to a longest match recognized for said header information including said input interface identifier; and

one or more routing lookup tables having treatment information regarding treatment of packets, said treatment information being responsive to said routing information and therefore to said input interface identifier.

6. An apparatus as in claim 5, wherein said one or more routing lookup tables include a plurality of entries corresponding to said packet header and differing with regard to said input interface identifier.

7. An apparatus as in claim 6, wherein said one or more routing lookup tables include a plurality of entries corresponding to said packet header and responsive to a multicast packet.

8. An apparatus as in claim 7, wherein said multicast packet is encapsulated using an multiprotocol lable switching protocol.

9. A memory storing information including instructions, the instructions executable by a processor, the instructions comprising:

code to receive a packet header and an input interface identifier;

code to couple said packet header to plural encapsulation recognizers configured to produce header information from said packet header, said plural encapsulation recognizers recognizing packet headers for multiple protocols, said header information including said input interface identifier;

code to couple said header information to plural longest match recognizers so as to produce routing information, said plural longest match recognizers operating in parallel, said routing information determined responsive to a longest match recognized for said header information including said input interface identifier; and

code to use said routing information to index to one or more routing lookup tables having treatment information regarding treatment of packets, said treatment information being responsive to said routing information and therefore to said input interface identifier.

10. A memory as in claim 9, wherein said one or more routing lookup tables include a plurality of entries corresponding to said packet header and differing with regard to said input interface identifier.

11. A memory as in claim 10, wherein said one or more routing lookup tables include a plurality of entries corresponding to said packet header and responsive to a multicast packet.

12. A memory as in claims 11, wherein said multicast packet is encapsulated using an multiprotocol lable switching protocol.