Tuple-based lookup scheme for packet switching node

• US 6,944,162 B1
• Filed: 10/03/2000
• Issued: 09/13/2005
• Est. Priority Date: 10/03/2000
• Status: Expired due to Fees

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel SA (Nokia Corporation)
• Inventors: Bailey, John, Dietz, Bryan, Hill, Rex A.
• Primary Examiner(s): Phunkulh, Bob
• Assistant Examiner(s): KADING, JOSHUA A
• Application Number:
  US09/679,138
• Time in Patent Office: 1,806 Days
• Field of Search: 370/229, 370/241, 370/252, 370/254, 370/392, 370/902, 370/912, 370/395.31, 370/395.32, 707/3, 707/6
• US Class Current: 370/395.31
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/54 Organization of routing tables

Abstract

Lookup scheme in which a tuple representing a plurality of flow properties is parsed into multiple subtuples for application in recursive lookups. A first subtuple including a first subset of bits from the tuple is applied to the flow information database and returns a result including a nickname having a smaller bit count than the first subtuple. A second subtuple including a second subset of bits from the tuple and the nickname are combined and applied to the flow information database. The lookups continue until a result indicates that no recursion is required. The final lookup result includes flow information applicable to one or more of modifying, enqueuing or forwarding the packet. A truncated lookup capability enables common processing across a group of distinct flows having common flow properties.

Claims

1. A method for determining packet processing data, comprising the steps of:

inputting a first lookup key including a first portion of a tuple;

determining a nickname in response to the first lookup key, the nickname having a lower bit count than the first lookup key;

outputting the nickname;

inputting a second lookup key including a second portion of the tuple and the nickname; and

outputting packet processing data in response to the second lookup key.

2. The method according to claim 1, wherein the ones of outputting steps further include outputting respective ones of recursion indicators sufficient to indicate a need for inputting an additional lookup key.

3. The method according to claim 1, wherein the ones of outputting steps further include outputting ones of indicators, respectively, sufficient to indicate an absence and presence, respectively, of packet processing data.

4. The method according to claim 1, wherein the ones of outputting steps further include outputting ones of indicators, respectively, sufficient to indicate a presence and absence, respectively, of a nickname.

5. A switching interface for a data communication switch, comprising:

means for inputting a first lookup key including a first portion of a tuple;

means for determining a nickname in response to the first lookup key, the nickname having a lower bit count than the first lookup key;

means for outputting the nickname;

means for inputting a second lookup key including a second portion of the tuple and the nickname; and

means for outputting packet processing data in response to the second lookup key.

6. The switching interface according to claim 5, further comprising means for outputting respective ones of recursion indicators sufficient to indicate a need for inputting an additional lookup key.

7. The switching interface according to claim 5, further comprising means for outputting ones of indicators, respectively, sufficient to indicate an absence and presence, respectively, of packet processing data.

8. The switching interface according to claim 5, further comprising means for outputting ones of indicators, respectively, sufficient to indicate a presence and absence, respectively, of a nickname.