Lookup engine for network devices

• US 20020116527A1
• Filed: 12/21/2000
• Published: 08/22/2002
• Est. Priority Date: 12/21/2000
• Status: Abandoned Application

• Current Assignee: Acute Communications Corporation
• Original Assignee: Acute Communications Corporation
• Inventors: Wang, Yao-Tzung, Chen, Jin-Ru
• Application Number:
  US09/740,819
• Publication Number:
  US 20020116527A1
• Time in Patent Office: Days
• US Class Current: 709/245
• 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/742 Route cache; Operation thereof

Abstract

A lookup engine for a network device is provided to lookup an address table. The lookup engine includes a parser for getting address information of an incoming packet. A predetermined number of shift control logic is provided for generating an I.I.D hash index for the incoming packet in response to the address information of the incoming packet. The output of each shift control logic is selected by a selector for looking up an address table, thereby to generate a forwarding information. With the implementation of the shift control logic, the lookup engine can construct each flow entry and classify the incoming packets belonging to this flow in wire-speed.

Claims

1. A lookup engine for a network device, comprising the steps of:

a parser for getting address information of an incoming packet;

a predetermined number of shift control logic each for generating an Identity Independent Distribution (I.I.D) hash index for said incoming packet in response to said address information of said incoming packet; and

a selector for selecting an I.I.D. hash index from said predetermined number of shift control logic, and said selected I.I.D. hash index causes an address table to output forwarding information for said incoming packet.

2. The lookup engine as claimed in claim 1, further comprising:

a central process unit for processing said incoming packet when said I.I.D. hash indexes find no hit in said address table.

3. The lookup engine as claimed in claim 1, wherein said network address is a destination MAC address.

4. The lookup engine as claimed in claim 1, wherein said network address is a destination IP address.

5. The lookup engine as claimed in claim 1, wherein said network address is a flow address.

6. The lookup engine as claimed in claim 1, wherein said shift control logic comprises:

a shift register having a plurality of segments for shifting said plurality of segments in response to a predetermined key number; and

means for performing XOR operations on said plurality of segments.

7. A method for generating lookup information for a network device, comprising the steps of:

getting address information from a header portion of an incoming packet;

partitioning said network address of m bits into a plurality of segments S_i each having n bits,

$0\le <br><br>i<<br><br>\lceil <br><br>\frac{m}{n}\rceil <br><br>-1;<br><br>$

generating an I.I.D. hash index by performing XOR operation on a segment S_base and a segment S_extend, where said segment S_base is formed by performing XOR operation on each of said plurality of segments, and said segment S_extend is formed by Rotating S₀ a number of bits determined by a predetermined key number; and

searching an address table by using said I.I.D. hash index to generate forwarding information.

8. The method as claimed in claim 7, further comprising the step of:

obtaining said segment

$S_{\lceil <br><br>\frac{m}{n}\rceil <br><br>}$

to have the same length with said segment S₀ by filling binary zeros.

9. The method as claimed in claim 7, wherein said address information is a flow address and said address table is a flow table.

10. The method as claimed in claim 7, wherein said address information is a destination IP address and said address table is a routing table.

11. The method as claimed in claim 7, wherein said address information is a MAC address and said address table is a filtering table.

12. The method as claimed in claim 7, further comprising the step of:

forwarding said incoming packet to a processor when said I.I.D. hash index having no hit in said address table.