Multi-stage lookup for translating between signals of different bit lengths

• US 6,420,982 B1
• Filed: 12/18/2001
• Issued: 07/16/2002
• Est. Priority Date: 03/23/2000
• Status: Expired due to Term

• Current Assignee: Conversant Intellectual Property Management Inc (MOSAID Technologies Inc. (f/k/a Conversant Intellectual Property Management))
• Original Assignee: MOSAID Technologies Inc. (f/k/a Conversant Intellectual Property Management)
• Inventors: Brown, David A.
• Primary Examiner(s): JeanPierre, Peguy
• Assistant Examiner(s): LAUTURE, JOSEPH J
• Application Number:
  US10/022,932
• Publication Number:
  US 20020067296A1
• Time in Patent Office: 210 Days
• Field of Search: 341/120, 341/118
• US Class Current: 341/106
• CPC Class Codes: H04L 12/4641 Virtual LANs, VLANs, e.g. virtual private networks [VPN] LAN interconnection over a bridge based backbone H04L12/462; encapsulation techniques H04L12/4633; routing of packets H04L45/00; packet switches H04L49/00; virtual private networks for security H04L63/0272
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 45/7452 Multiple parallel or consecutive lookup operations lookup operation involving Bloom filters H04L45/7459
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches
• CPC Class Codes: H04L 49/354 for supporting virtual local area networks [VLAN]

Abstract

A method and apparatus is provided for translating an L-bit put signal to a W-bit output signal such as a virtual network identification signal to an internal virtual network signal. The translation is performed using a multi-stage lookup. The input signal is portioned into a plurality of subsets of bits. A first index to a first stage is provided by combining a portion of bits and a first delta subset of bits. A second index to a second stage is provided by combining data stored at the first index in the first stage and the a second delta subset of bits. The corresponding output signal is stored at the last index in the last stage. The use of the multi-stage lookup instead of a single-stage lookup reduces the memory required to perform the translation.

Claims

1. A method for translating an input digital data having a first number of bits to an output digital data having a second number of bits, the first number of bits greater than the second number of bits, comprising the steps of:

portioning the input digital data into a first subset and a plurality of equal size of second subsets, the number of bits of the first subset being at least the same as the number of bits of the output digital data;

providing a multi-stage lookup table comprising a same number of stages as a number of portioned second subsets, each stage lookup table storing indexed data having the same number of bits as the output digital data; and

sequentially performing by each stage lookup table, a lookup in each of the lookup tables, a first lookup to a first stage lookup table performed using a first index equal to a combination of the first subset and a first portioned second subset, a next lookup to a next stage lookup table performed using a second index equal to a combination of a result of a previous lookup and a next portioned second subset and the output digital data provided as a result of a last lookup to a last stage lookup table.

2. The method as claimed in claim 1 wherein the first subset stores the most significant bit of the input digital data.

3. The method as claimed in claim 1 wherein the number of stage lookup tables is two.

4. The method as claimed in claim 1 wherein the number of stage lookup tables is four.

5. The method as claimed in claim 1 wherein the size of the stage lookup tables is dependent on the size of an index equal to the combination of the result of a previous lookup and the number of bits in the second subset.

6. The method as claimed in claim 1 wherein the width of each stage lookup table is dependent on the number of bits in the output digital data.

7. The method as claimed in claim 1 wherein the first number of bits is twelve, the second number of bits is eight, the number of bits in the second subset is two and the number of stage lookup tables is two.

8. The method as claimed in claim 1 wherein the first number of bits includes a second subset.

9. A method for translating an input digital data having a first number of bits to an output digital data having a second number of bits, the first number of bits is greater than the second number of bits, comprising the steps of:

portioning the input digital data into a first subset and a plurality of equal size of second subsets, the number of bits of the first subset being the same as the number of bits of the output digital;

providing a multi-stage lookup table comprising a same number of stages as a number of portioned second subsets, each stage lookup table having a same width as the number of bits of the output digital data;

indexing to a first stage lookup table of the multi-stage lookup table using an index equal to a combination of the first subset and a first portioned second subset, and providing an indexed data to the next stage lookup table;

continuing indexing to the next stage lookup table using an index equal to a combination of the indexed data from previous stage lookup table and a following portioned second subset to provide an indexed data to the next stage lookup table until a last stage lookup table is indexed; and

providing the indexed data from the last stage lookup table as the output digital data.

10. The method as claimed in claim 9 wherein the first subset stores the most significant bit of the input digital data.

11. The method as claimed in claim 9 wherein the number of stage lookup tables is two.

12. The method as claimed in claim 9 wherein the number of stage lookup tables is four.

13. The method as claimed in claim 9 wherein the size of the stage lookup tables is dependent on the size of an index equal to the combination of the result of a previous lookup and the number of bits in the second subset.

14. The method as claimed in claim 9 wherein the width of each stage lookup table is dependent on the number of bits in the output digital data.

15. The method as claimed in claim 9 wherein the first number of bits is twelve, the second number of bits is eight, the number of bits in the second subset is two and the number of stage lookup tables is two.

16. The method as claimed in claim 9 wherein the first number of bits includes a second subset.