Coded data generation or conversion – Digital code to digital code converters – Coding by table look-up techniques
Reexamination Certificate
2001-12-18
2002-07-16
JeanPierre, Peguy (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
Coding by table look-up techniques
C341S120000, C341S118000
Reexamination Certificate
active
06420982
ABSTRACT:
BACKGROUND OF THE INVENTION
A networking switch receives data packets from a number of ingress ports connected to the switch and forwards the data packets to one or more egress ports connected to the switch. The switch determines the egress port to which the data packets are forwarded dependent on a destination address and other fields included in the data packet.
The data packet received at an ingress port includes network protocols encoded in one or more headers included in the data packet. The headers are a standard length specified by the network protocols.
FIG. 1A
illustrates a prior art data packet
100
. The data packet includes a physical layer (L
1
) header
102
, a data link layer (L
2
) header
104
, a network layer (L
3
) header
106
and a transport layer (L
4
) header. A payload for the data packet is stored in a data field
110
and the data packet
100
also includes a checksum
112
.
FIG. 1B
illustrates a prior art Ethernet protocol header stored in the data link (L
2
) header
104
shown in FIG.
1
A. The length of the Ethernet protocol header is a fixed number of bits which is specified by the standard Ethernet protocol. The data link (L
2
) header
104
includes a 6-byte L
2
destination address
114
, a 12-bit Virtual Local Area Network Identifier (“VLAN ID”)
118
and a 2-byte length/type field
120
.
The network switch forwards data packets from one Local Area Network (“LAN”) segment connected to the switch to another LAN segment connected to the switch. The switch determines whether a data packet received from one LAN segment is to be forwarded to another LAN segment. A broadcast data packet received at an ingress port in the switch is forwarded to all members of the LAN and thus consumes a large proportion of the LAN's bandwidth. In order to reduce the number of broadcast data packets forwarded on a LAN, members of a physical LAN are added to logical groups called Virtual LANs. A broadcast data packet is only forwarded to members of the Virtual LAN from which it originated. The virtual LAN is encoded in the VLAN ID
118
included in the Ethernet protocol header stored in the data link (L
2
) header
104
in the received data packet.
The 12-bit VLAN ID
118
allows a physical LAN to have up to 2
12
(4096) VLANS. Typically, not all 2
12
VLANS are used, but a 12-bit VLAN ID
118
is forwarded in the data link layer (L
2
) header
104
included in each Ethernet protocol data packet received by the switch. If the switch supports a subset of the 2
12
VLANS per physical LAN, for example, 2
8
(256) VLANS, the switch may translate the 12-bits received in the VLAN ID to an 8-bit Internal VID (“IVID”). The use of an 8-bit IVID in the switch reduces the memory required in the switch for forwarding a VLAN ID with each data packet internally in the switch.
The translation of a relatively small number of bits (12-bit VLAN) to a smaller number of bits (8-bit IVID) is typically performed using a lookup table. An example of one such prior art lookup table is shown in FIG.
1
C. The prior art lookup table includes an entry for each possible VLAN; that is, 2
12
(4096) IVID entries. Each IVID entry is eight-bits wide, thus the size of the lookup table is 32K-bits (4096×8). There are a maximum of 2
8
(256) possible IVID values stored in 256 of the 4096 IVID entries in the lookup table. Thus, the use of a 32K lookup table to translate a 12-bit VLAN ID to an 8-bit IVID consumes more memory than is necessary to store the 256 possible IVID entries by providing a location for each of the 4096 possible VLAN IDs.
An alternative method for translating one number of bits to a smaller number of bits is to use a hash function. A hash function is typically used to convert a large memory space to a small memory space, such as to map a 48-bit (6 bytes) L
2
destination address
114
to a smaller number of bits. Hash function logic performs a hash function on the L
2
destination address
114
and uses the result of the hash function to search an address space smaller than the 2
48
entries dependent on the smaller number of bits which is required for the original number of bits.
However, the use of a hashing function to translate a relatively small number (12-bit VLAN ID) to a smaller number (8-bit IVID) does not significantly reduce the memory requirements in order to justify adding the complex logic required to perform the hash function.
SUMMARY OF THE INVENTION
We present a multi-stage lookup table for translating a first signal having a first number of bits to a second signal having a second number of bits less than the first number of bits. Portioning logic portions the first number of bits into a portion of bits and a delta subset of bits. The size of the portion of bits is at least the size of the second number of bits. Memory access logic sequentially performs a lookup in each of a plurality of memory elements. The number of memory elements is dependent on the number of delta subsets. The memory access logic performs a first lookup to a first memory element using a first index equal to the portion of bits. The memory access logic performs a next lookup to a next memory element using a next index equal to a combination of a result of the previous lookup and a next delta subset of bits. The second signal results from a last lookup to a last memory element.
Preferably, the number of memory elements is two or four. The size of the memory element is dependent on the size of an index equal to the number of bits in the subset of bits and the number of bits in the delta subset of bits. The width of the memory element is dependent on the number of bits in the second signal.
In one embodiment, the number of memory elements is two and the number of bits in the delta subset is two to provide a 2-stage lookup to translate a first set of 12-bits to a second set of 8.
REFERENCES:
patent: 5504743 (1996-04-01), Drefenstedt
patent: 5852607 (1998-12-01), Chin
patent: 0 594 196 (1994-04-01), None
Hamilton, Brook, Smith and Reynolds, P.C.
MOSAID Technologies Inc.
LandOfFree
Multi-stage lookup for translating between signals of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multi-stage lookup for translating between signals of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-stage lookup for translating between signals of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2871236