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

• US 6,384,750 B1
• Filed: 03/23/2000
• Issued: 05/07/2002
• Est. Priority Date: 03/23/2000
• Status: Expired due to Term

• Current Assignee: MOSAID Technologies Inc. (f/k/a Conversant Intellectual Property Management)
• Original Assignee: Mosaid Technologies Incorporated (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:
  US09/533,724
• Time in Patent Office: 775 Days
• Field of Search: 341/106, 341/138, 341/144, 341/118, 341/150, 340/347, 370/395
• 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 input 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. An apparatus for translating a first digital signal having a first number of bits to a second digital signal having a second number of bits, the first number of bits greater than the second number of bits, comprising:

portioning logic which portions the first number of bits into a portion of bits and a plurality of delta subsets of bits, the size of the portion of bits being at least the size of the second number of bits;

a lookup table coupled to the portioning logic, the lookup table including a plurality of memory elements, the number of memory elements dependent on the number of delta subsets of bits; and

memory access logic coupled to the lookup table which sequentially performs a lookup in each of the memory elements, a first lookup to a first memory element performed using a first index equal to a combination of the portion of bits and a first delta subset of bits, a next lookup to a next memory element performed using a next index equal to a combination of a result of a previous lookup and a next delta subset of bits and the second digital signal provided by the result of a last lookup to a last memory element.

2. An apparatus as claimed in claim 1 wherein the number of memory elements is two.

3. An apparatus as claimed in claim 1 wherein the number of memory elements is four.

4. An apparatus as claimed in claim 1 wherein the size of the memory element 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 delta subset of bits.

5. An apparatus claimed in claim 1 wherein the width of the memory element is dependent on the number of bits in the second digital signal.

6. An apparatus 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 delta subset of bits is two and the number of memory elements is two.

7. A method for translating a first digital signal having a first number of bits to a second digital signal having a second number of bits, the first number of bits is greater than the second number of bits, comprising the steps of:

portioning by portioning logic the first number of bits into a portion of bits and a plurality of delta subsets of bits, the size of the portion of bits being at least the size of the second number of bits;

providing a lookup table coupled to the portioning logic, the lookup table including a plurality of memory elements, the number of memory elements dependent on the number of delta subsets of bits; and

sequentially performing by memory access logic a lookup in each of the memory elements, the memory access logic coupled to the plurality of memory elements, a first lookup to a first memory element performed using a first index equal to a combination of the portion of bits and a first delta subset of bits, a next lookup to a next memory element performed using a second index equal to combination of a result of a previous lookup and a next delta subset of bits and the second digital signal provided by the result of a last lookup to a last memory element.

8. The method as claimed in claim 7 wherein the number of memory elements is two.

9. The method as claimed in claim 7 wherein the number of memory elements is four.

10. The method as claimed in claim 7 wherein the size of the memory element 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 delta subset of bits.

11. A method as claimed in claim 7 wherein the width of the memory element is dependent on the number of bits in the second digital signal.

12. A method as claimed in claim 7 wherein the first number of bits is twelve, the second number of bits is eight, the number of bits in the delta subset of bits is two and the number of memory elements is two.

13. An apparatus for translating a first digital signal having a first number of bits to a second digital signal having a second number of bits, the first number of bits greater than the second number of bits, comprising:

means for portioning which portions the first number of bits into a portion of bits and a plurality of delta subsets of bits, the size of the portion of bits being at least the size of the second number of bits;

a lookup table coupled to the means for portioning, the lookup table including a plurality of memory elements, the number of memory elements dependent on the number of delta subsets of bits; and

means for accessing memory coupled to the lookup table which sequentially performs a lookup in each of the memory elements, a first lookup to a first memory element performed using a first index equal to a combination of the portion of bits and a first delta subset of bits, a next lookup to a next memory element performed using a next index equal to a combination of a result of a previous lookup and a next delta subset of bits and the second digital signal provided by the result of a last lookup to a last memory element.

14. An apparatus as claimed in claim 13 wherein the number of memory elements is two.

15. An apparatus as claimed in claim 13 wherein the number of memory elements is four.

16. An apparatus as claimed in claim 13 wherein the size of the memory element 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 delta subset of bits.

17. An apparatus claimed in claim 13 wherein the width of the memory element is dependent on the number of bits in the second signal.

18. An apparatus as claimed in claim 13 wherein the first number of bits is twelve, the second number of bits is eight, the number of bits in the delta subset of bits is two and the number of memory elements is two.