Method for performing a medium access control address lookup in a network switch of an ethernet network

• US 6,615,336 B1
• Filed: 01/12/2000
• Issued: 09/02/2003
• Est. Priority Date: 07/16/1999
• Status: Expired due to Term

• Current Assignee: VIA Technologies Incorporated (VIA Technologies)
• Original Assignee: VIA Technologies Incorporated (VIA Technologies)
• Inventors: Chen, Jen-Kai, Chen, Wei-Pin, Liou, Jiann-Hwa
• Primary Examiner(s): Nguyen, Hiep T.
• Application Number:
  US09/481,713
• Time in Patent Office: 1,329 Days
• Field of Search: 711/202, 711/171, 370/351
• US Class Current: 711/202
• CPC Class Codes: H04L 12/413 with random access, e.g. carrier-sense multiple-access with collision detection [CSMA-CD]
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches
• CPC Class Codes: H04L 49/90 Buffering arrangements

Abstract

A method for performing a MAC address lookup in a network switch of an Ethernet network is provided, using a memory structure including a number of multi-slot buckets. Each of the multi-slot buckets is mapped to a hash key derived from a MAC Address. Each of the multi-slot buckets has a number of forwarding table section, each storing a number of the forwarding table entries. 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.

Claims

1. A memory structure for storing a forwarding table in a memory of a network switch of an Ethernet network so as to facilitate a medium access control (MAC) address lookup in the network switch, the memory structure comprising:

a plurality of multi-slot buckets, wherein each of the multi-slot buckets is mapped to a hash key which is formed by partial bits in a MAC address that is used for data transmission, wherein each of the multi-slot buckets comprises;

a first forwarding table section for storing a first forwarding table entry and a second forwarding table entry;

a second forwarding table section for storing a third forwarding table entry and a fourth forwarding table entry; and

a third forwarding table section for storing port masks associated with the first, second, third, and fourth forwarding table entries;

wherein the first, second, third, and fourth forwarding table entries each have respective data fields for MAC content, source port, and static flag, excluding the associated port masks;

wherein the first, second, and third forwarding table sections are separately read from the multi-slot bucket in a burst mode via a data bus whose bus width is less than a data length of each of the first, second, and third forwarding table sections;

wherein the port masks stored in the third forwarding table section are read from the multi-slot bucket only when the data transmission is multicast; and

whereby the MAC address lookup is completed within at most three times of reading the memory of the network switch.

2. A memory structure according to claim 1, wherein the data length of the first, second, and third forwarding table sections is 128-bit and the bus width is 64-bit.

3. A memory structure according to claim 2, wherein the memory is connected to a switch integrated circuit (IC) chip by the 64-bit data bus.

4. 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, the method comprising the steps of:

mapping a hash key of a MAC address to a four-slot bucket of a forwarding table stored in a static random access memory (SRAM) of the network switch, wherein the four-slot bucket has first, second, and third forwarding table sections, the first forwarding table-section has first and second forwarding table entries, the second forwarding table section has third and fourth forwarding table entries, and the third forwarding table section has four corresponding port masks of the first, second, third, and fourth forwarding table entries;

reading the first forwarding table section of the four-slot bucket from the SRAM in a burst read mode and receiving the first forwarding table section at a switch integrated circuit connected to the SRAM via a 64-bit data bus;

determining, at the switch integrated circuit, whether an entry obtained from the first forwarding table section matches the hash key and, if not, reading the second forwarding table section of the four-slot bucket from the SRAM in the burst read mode and receiving the second forwarding table section at the switch integrated circuit connected to the SRAM via the 64-bit data bus; and

determining, at the switch integrated circuit, whether the data transmission is multicast and, if so, reading the third forwarding table section from the four-slot bucket from the SRAM in a burst read mode and receiving the first forwarding table section at the switch integrated circuit connected to the SRAM via the 64-bit data bus.

5. A method according to claim 4, wherein each of the first, second, third, and fourth forwarding table entries has a data length of not larger than 64 bits, including data items for corresponding MAC content, source port, and static flag but not including the corresponding port masks.

6. 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, the method comprising the steps of:

(a) mapping a hash key of a MAC address to a multi-slot bucket of a forwarding table stored in a memory of the network switch, wherein the multi-slot bucket has first, second, and third forwarding table sections;

the first and second forwarding table section each include respective forwarding table entries; and

the third forwarding table section has corresponding port masks of the forwarding table entries;

(b) reading the first forwarding table section of the multi-slot bucket;

(c) determining whether an entry obtained from the first forwarding table section matches the hash key and, if not, reading the second forwarding table section of the multi-slot bucket; and

(d) determining whether the data transmission is multicast and, if so, reading the third forwarding table section from the multi-slot bucket.

7. A method according to claim 6, wherein each of the forwarding table entries has a data length of not larger than 64 bits, including data items for corresponding MAC content, source port, and static flag but not including the corresponding port masks.

8. A method according to claim 6, wherein the multi-slot bucket is a four-slot bucket of the forwarding table, the first forwarding table section has first and second forwarding table entries, the second forwarding table section has third and fourth forwarding table entries, and the third forwarding table section has four corresponding port masks of the first, second, third, and fourth forwarding table entries.

9. A method according to claim 8, wherein each of the first, second, third, and fourth forwarding table entries has a data length of not larger than 64 bits, including data items for corresponding MAC content, source port, and static flag but not including the corresponding port masks.

10. A method according to claim 6, wherein said step (b) comprises the step of:

reading the first forwarding table section of the multi-slot bucket from the memory in a burst read mode and receiving the first forwarding table section at a switch integrated circuit connected to the memory via a 64-bit data bus.

11. A method according to claim 10, wherein said step (c) comprises the step of:

if an entry obtained from the first forwarding table section does not match the hash key, reading the second forwarding table section of the four-slot bucket from the memory in the burst read mode and receiving the second forwarding table section at the switch integrated circuit which is connected to the memory via the 64-bit data bus.