Method for accessing a non-symmetric dual-slot address table and switching apparatus using same

• US 20020165985A1
• Filed: 04/25/2002
• Published: 11/07/2002
• Est. Priority Date: 05/03/2001
• Status: Active Grant

• Current Assignee: VIA Technologies Incorporated (VIA Technologies)
• Original Assignee: VIA Technologies Incorporated (VIA Technologies)
• Inventors: Chen, Jen-Kai, Chao, Yun-Fei
• Granted Patent: US 7,085,275 B2
• Time in Patent Office: Days
• US Class Current: 709/245
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: H04L 2101/604 Address structures or formats
• CPC Class Codes: H04L 2101/622 Layer-2 addresses, e.g. medium access control [MAC] addresses
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering

Abstract

A method and apparatus for accessing a non-symmetric dual-slot address table having two entries 0, 1 that are different in size. When writing data, the data is hashed to generate a hash value. Then, the data is written to a slot corresponding to the hash value in the entry 0. When there was data in the slot 0, the hash value is mapped to a sub-address and a share value, and then a slot 1 corresponding to the sub-address is selected from the entry 1. Afterwards, the SMAC tag, the share value and the source port are written to the slot 1. In addition, when transmitting the packet, a hash value is generated according to the DMAC address. Then, a SMAC tag, the share value and the source port are read according to the hash value. After compared, the packet is transmitted.

Claims

1. A data writing method for a non-symmetric dual-slot address table, wherein the non-symmetric dual-slot address table has a first entry with m slots and a second entry with n slots, m and n are integers and m is an integer multiple of n, the method comprising steps of:

generating a hash value according to a SMAC address;

selecting an address corresponding to the hash value for the non-symmetric dual-slot address table;

writing a tag and a source port for the SMAC address to a slot corresponding to the selected address in the first entry, when the slot corresponding to the selected address in the first entry is empty; and

mapping the hash value to a sub-address and a share value when the slot corresponding to the address in the first entry is not empty, and then selecting a slot corresponding to the sub-address in the second entry, and writing the tag, the share value and the source port for the SMAC address to the slot corresponding to the sub-address in the second entry.

2. The method of claim 1, wherein the mapping step comprises dividing the hash vale by an integer to obtain a quotient and a remainder, wherein the corresponding sub-address is obtained according to the quotient, and the remainder is the corresponding share value.

3. The method of claim 1, wherein m is 4K and n is 2K, K=2¹⁰.

4. The method of claim 3, wherein the share value is one bit.

5. The method of claim 1, wherein m is 8K and n is 2K, K=2¹⁰.

6. The method of claim 3, wherein the share value has two bits.

7. The method of claim 1, wherein the slot corresponding to the address in the first entry is defined to be associated with the slot corresponding to the sub-address, when the two associated slots have stored data, the SMAC tag, the share value and the source port are selectively written to one of the slots where data has not been accessed for a long time.

8. The method of claim 1, further comprising when both the slot corresponding to the address and the slot corresponding to the sub-address have stored data, and if the data stored in the slot corresponding to the address has not been accessed for a predetermined time, the data stored in the slot corresponding to the sub-address is moved to overwrite the slot corresponding to the address, and the slot corresponding to the sub-address is emptied.

9. A method for looking up a non-symmetric dual-slot address table to transmit a packet, wherein the packet comprises a SMAC address and a DMAC address, and the non-symmetric dual-slot address table has a first entry with m slots and a second entry with n slots, m and n are integers and m is an integer multiple of n, the method comprising steps of:

generating a hash value according to the DMAC address;

selecting an address corresponding to the hash value for the non-symmetric dual-slot address table;

transmitting the packet according to a destination port specified in a slot corresponding to the selected address in the first entry, when a tag of the MAC address is consistent with a tag of the SMAC address in a slot corresponding to the said selected address in the first entry; and

transmitting the packet according to a source port specified in a slot corresponding to a corresponding sub-address in the second entry, when the tag and a share value of the DMAC address is consistent with a tag and a share value of a SMAC address stored in a slot corresponding to the sub-address.

10. The method of claim 9, wherein the mapping step comprising dividing the hash vale by an integer to obtain a quotient and a remainder, wherein the corresponding sub-address is obtained according to the quotient, and the remainder is the corresponding share value.

11. The method of claim 9, further comprising step of:

broadcasting the packet when the SMAC tags stored in the slot corresponding to the address and the slot corresponding to the sub-address are different from the DMAC tag.

13. The apparatus of claim 12, wherein the mapping step comprising dividing the first or the second hash vale by an integer multiple to obtain a quotient and a remainder, wherein the corresponding first or second sub-address is obtained according to the quotient, and the remainder is the corresponding first or second share value.

14. The apparatus claim 12, wherein m is 4K and n is 2K, K=2¹⁰.

15. The apparatus of claim 14, wherein the share value has one bit.

16. The apparatus of claim 12, wherein a length of the hash value has twelve bits.

17. The apparatus of claim 12, wherein the slot corresponding to the first address in the first entry is defined to be associated with the slot corresponding to the first sub-address, when the two associated slots have stored data, the SMAC tag, the share value and the source port are selectively written to one of the slots where data has not been accessed for a longer time.

18. The apparatus of claim 12, further comprising when both the slot corresponding to the first address and the slot corresponding to the first sub-address have stored data, and if the data stored in the slot corresponding to the first address has not been accessed for a predetermined time, the data stored in the slot corresponding to the first sub-address is moved to overwrite the slot corresponding to the first address, and the slot corresponding to the first sub-address is emptied.

19. The apparatus of claim 12, wherein when the SMAC tags stored in the slot corresponding to the second address and the slot corresponding to the second sub-address are different from the DMAC tag, the packet is broadcasted.

20. The apparatus of claim 12, wherein the memory is a static random access memory.

12. A switching apparatus having a plurality of ports, for transmitting a packet having a SMAC address and a DMAC address from a source port of said plurality of ports, the switching apparatus comprising:

a memory, having a non-symmetric dual-slot address table, wherein the non-symmetric dual-slot address table has a first entry with m slots and a second entry with n slots, m and n are integers and m is an integer multiple of n, and is used for accessing a plurality of MAC addresses;

a writing device, for writing the SMAC address to the non-symmetric dual-slot address table, wherein a first hash value is generated according to the SMAC address;

an first address corresponding to the first hash value from the non-symmetric dual-slot address table is selected;

a tag and the source port for the SMAC address are written to a slot corresponding to the first address in the first entry, when the slot corresponding to the first address in the first entry is empty; and

the first hash value is mapped to a first sub-address and a first share value when the slot corresponding to the first address in the first entry is not empty, and then a slot corresponding to the first sub-address in the second entry is selected, and the tag, the first share value and the source port of the SMAC address are written to the slot corresponding to the first sub-address in the second entry; and

a transmitting device, for transmitting the packet to a destination port, wherein a second hash value is generated according to the DMAC address;

an second address corresponding to the second hash value is selected for the non-symmetric dual-slot address table;

the packet is transmitted according to the destination port in a slot corresponding the second address in the first entry, when a tag of the MAC address is consistent with a tag of the SMAC address in a slot corresponding to the second address in the first entry; and

the packet is transmitted according to a source port stored in a slot corresponding to a second sub-address in the second entry, when the tag and the second share value of the DMAC address is consistent with a tag and a share value of a SMAC address stored in a slot corresponding to the second sub-address.