Electrical computers and digital processing systems: memory – Address formation – Address mapping
Reexamination Certificate
2000-01-12
2003-09-02
Nguyen, Hiep T. (Department: 2187)
Electrical computers and digital processing systems: memory
Address formation
Address mapping
C711S171000, C370S351000
Reexamination Certificate
active
06615336
ABSTRACT:
BACKGROUND OF THE INVENTION
This application incorporates by reference Taiwanese application Serial No. 88112055, Filed Jul. 16, 1999.
1. Field of the Invention
The invention relates in general to a memory access in the Ethernet, and more particularly to an improved hashing scheme where the original entries in the multi-slot bucket are separated as entries and port masks in different location.
2. Description of the Related Art
Lookup of the forwarding table for destination medium access control (MAC) addresses is a basic operation in the Ethernet switch integrated circuit (IC). In the Ethernet, a server is provided with a switch hub for transmitting data among different hosts. A switch IC chip deposed in the switch hub connects the hosts according to the forwarding table. Conventionally, the forwarding table is established in a static random access memory (SRAM) in order to reduce system cost.
Referring to
FIG. 1
, a transmitter (computer)
10
is coupled to a port
12
of the switch hub
11
while a receiver (computer)
16
is connected to the switch hub
11
via a port
15
. The data, forwarded from the transmitter
10
, is received by a switch IC chip
14
of the switch hub II, and then passed on to the receiver
16
.
In
FIG. 1
, the data of the transmitter
10
can be received by the receiver
16
because the MAC address of the receiver
16
is also sent out along with the data. The MAC address, including the address of the port
15
connected by the receiver
16
, is received by the switch IC chip
14
, and then transmitted to a SRAM
18
for the forwarding table lookup by a 128-bit data bus
17
. Lookup for the forwarding table according to the MAC address decides the destination where the data is to be transmitted.
The size of the MAC address is 48 bits and the total number of computers in a local area network (LAN) usually comes to tens or hundreds. Conventionally, a hashing algorithm is employed to map the MAC address to a hash key for lookup of the forwarding table. The hash key is composed of 11 bits in the 48-bit MAC address so that the required memory is not costly.
However, owing to the fact that MAC addresses of different computers may have the same corresponding hash key, the above-mentioned hashing algorithm may result in a problem that the hash keys of different computers may conflict with each other. For example, an 11-bit hash key can correspond to 2
11
different MAC addresses in total. In a company, if there are 400 clients in the Ethernet, the probability that all hash keys are different with each other is (2
11
−1)/2
11
×(2
11
−2)/ 2
11
×(2
11
−3)/2
11
×(2
11
−4)/2
11
×. . . (2
11
−397)/2
11
×(2
11
−398)/ 2
11
×(2
11
−399)/2
11
≈0. That is to say, it is very possible that at least two of these hash keys are the same in this case.
In the prior art, a multi-slot bucket scheme is employed to reduce the probability of hash key conflict. The forwarding table is composed of continuous multi-slot buckets, each bucket corresponding to a unique hash key and having multi-slots to store individual forwarding table entries. Given a MAC address, a hash key can be derived and mapped to the corresponding multi-slot bucket.
The 4-slot bucket is taken for example as shown in FIG.
2
. The lookup for the forwarding table is performed as follows. The hash key, derived from a given MAC address, is mapped to the corresponding kth 4-slot bucket. Then, the MAC address is used to compare with the first forwarding table entry (k,
0
) of the kth 4-slot bucket. If the MAC field of this entry (k,
0
) is not consistent with the content of the MAC address, the next entry (k,
1
) will be tried again. The forwarding table entries (k,
2
) and (k,
3
) will be tried successively if the former entries (k,
0
) and (k,
1
) are not identical with the MAC address. Therefore, there are up to 4 tries for a lookup. In practice, the probability of lookup miss will be very small. However, it requires four table entry accesses to SRAM in the worst case.
The memory space and the access time are usually considered to be the most important aspects in the IC design. Therefore, if the memory space used for lookup of the forwarding table and the access time of memory can be effectively reduced, the efficiency of the conventional hashing algorithm can be greatly improved.
SUMMARY OF THE INVENTION
It is therefore an object of the invention to provide a method for performing a MAC address lookup in a network switch to enable data transmission to a network node associated with the MAC address in an Ethernet network. This method is an improved hashing scheme in the Ethernet where the rarely used field is separated from each forwarding table entry so that memory space can be saved for storing more forwarding table entries, and thus the access time of memory can be effectively reduced.
The invention achieves the above-identified objects by providing a memory structure in the Ethernet. The memory structure includes a plurality of multi-slot buckets. Each of the multi-slot buckets is mapped to a hash key that is formed by partial bits in a MAC address. Besides, each of the multi-slot buckets has a number of forwarding table sections, each storing a number of forwarding table entries. If two forwarding table entries are stored and read by a burst read mode in each forwarding table section of a 4-slot bucket, ¼ memory space and ½ access time can be saved.
The invention achieves another object by providing a memory access method. First, a hash key of a MAC address is mapped to a multi-slot bucket of a forwarding table in a memory. Then, a number of forwarding table entries are read from a forwarding table section of the multi-slot bucket by a burst read mode. If two forwarding table entries are stored in each forwarding table section of a 4-slot bucket, ¼ memory space and ½ access time can be saved. Thus, the lookup for the forwarding table according to the MAC address in the Ethernet switch IC can be effectively performed.
REFERENCES:
patent: 5649109 (1997-07-01), Griesmer et al.
patent: 5914938 (1999-06-01), Brady et al.
patent: 6192051 (2001-02-01), Lipman et al.
patent: 6266705 (2001-07-01), Ullum et al.
patent: 6343078 (2002-01-01), Bronstein et al.
patent: 6366617 (2002-04-01), Ryan
Chen Jen-Kai
Chen Wei-Pin
Liou Jiann-Hwa
Nguyen Hiep T.
Rabin & Berdo P.C.
Via Technologies Inc.
LandOfFree
Method for performing a medium access control address lookup... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for performing a medium access control address lookup..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for performing a medium access control address lookup... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3087111