Arrangement for searching network addresses in a network switch using multiple tables based on subnet identifier

• US 7,103,035 B1
• Filed: 01/14/2000
• Issued: 09/05/2006
• Est. Priority Date: 01/14/2000
• Status: Expired due to Term

• Current Assignee: Advanced Micro Devices, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Kanuri, Mrudula
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): Jagannathan, Melanie
• Application Number:
  US09/482,956
• Time in Patent Office: 2,426 Days
• Field of Search: 370/218, 370/235, 370/236, 370/254, 370/255, 370352-356, 370/360, 370/395.3, 370/395.52, 370/395.63, 370/395.64, 370/389, 370/392, 370/396, 370/397, 370/469, 370/467, 370/902, 370/912, 370/400, 370/401, 709/238
• US Class Current: 370/356
• CPC Class Codes: H04L 2101/668 Internet protocol [IP] address subnets
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming
• CPC Class Codes: H04L 61/35 involving non-standard use of addresses for implementing network functionalities, e.g. coding subscription information within the address or functional addressing, i.e. assigning an address to a function

Abstract

A network switch, configured for performing layer 2 and layer 3 switching in an Ethernet (IEEE 802.3) network without blocking of incoming data packets, includes a switching module for performing layer 2 and layer 3 switching operations, and a plurality of network switch ports, each configured for connecting the network switch to a corresponding subnetwork. The switching module includes a plurality of address tables for storing address information (e.g., layer 2 and layer 3 address and switching information), where each table is configured for storing the address information of a corresponding one of the subnetworks. The use of multiple address tables within the switching module enables the time for looking up address information to be substantially reduced, especially since the multiple address tables can be accessed independently and simultaneously by the switching module. Moreover, the identification of each table by a corresponding subnetwork identifier enables the multiple address tables to be managed efficiently, merely by obtaining the subnetwork identifier from the received layer 2 packet. Hence, layer 3 address information for a given layer 2 packet can be obtained merely by searching the selected address table using the host identifier as a search key.

Claims

1. A method in an integrated network switch having a switching module, the integrated network switch configured for switching a layer 2 data packet within a network having a plurality of subnetworks, the method comprising:

obtaining, from the layer 2 packet, layer 3 packet information having a network identifier, a subnetwork identifier, and a host identifier, the subnetwork identifier identifying a corresponding one of the subnetworks and the host identifier identifying a transmitting node having transmitted the layer 3 packet information from within the one subnetwork; and

storing address information from the layer 2 packet, including the host identifier, in a selected one of a plurality of address tables within the switching module based on the corresponding subnetwork identifier, each of the address tables configured for storing the host identifiers of respective transmitting nodes of a corresponding one of the subnetworks.

2. The method of claim 1, wherein received data packet includes an Internet Protocol (IP) header, the storing step including storing the host identifier from the IP header and layer 2 address information from the layer 2 packet into a single table entry of the selected one address table.

3. The method of claim 2, wherein the network switch includes a plurality of network switch ports each connected to a corresponding one of the subnetworks, the storing step including selecting the one address table based on the one network switch port having received the layer 2 packet.

4. The method of claim 3, further comprising assigning each of the address tables to a corresponding one of the network switch ports.

5. The method of claim 2, wherein the obtaining step comprises:

obtaining an IP source address from the IP header;

obtaining the subnetwork identifier and the host identifier from the IP source address.

6. The method of claim 5, wherein the storing step comprises:

searching the selected one address table for a stored table entry having layer 3 switching information based solely on the host identifier; and

storing the address information from the layer 2 packet into the selected one address table based on a determined absence of the stored table entry.

7. The method of claim 6, wherein the searching step includes searching for the stored table entry by using the host identifier as a key according to a linked list search.

8. The method of claim 6, wherein the searching step includes:

generating a hash key based on the host identifier; and

searching for the stored table entry using the generated hash key.

9. The method of claim 6, wherein the network switch is an integrated circuit chip, the searching step including searching the selected one address table for switching of the layer 2 data packet according to a wire rate.

10. A method in an integrated network switch having a switching module, the integrated network switch configured for switching a layer 2 data packet within a network having a plurality of subnetworks, the method comprising:

obtaining, from the layer 2 packet, layer 3 packet information having a network identifier, a subnetwork identifier, and a host identifier, the subnetwork identifier identifying a corresponding one of the subnetworks and the host identifier identifying a transmitting node having transmitted the layer 3 packet information from within the one subnetwork;

selecting one of a plurality of address tables within the switching module based on the corresponding subnetwork identifier, each of the address tables configured for storing the host identifiers of respective transmitting nodes of a corresponding one of the subnetworks; and

searching the one selected address table for layer 3 switching information for the layer 2 packet based on the host identifier.

11. The method of claim 10, wherein the received data packet includes an Internet Protocol (IP) header, the obtaining step including obtaining the subnetwork identifier and the host identifier from the IP header.

12. The method of claim 11, wherein the network switch includes a plurality of network switch ports each connected to a corresponding one of the subnetworks, the selecting step including selecting the one address table based on the one network switch port having received the layer 2 packet.

13. The method of claim 12, further comprising assigning each of the address tables to a corresponding one of the network switch ports.

14. The method of claim 10, wherein the searching step includes searching for the stored table entry by using the host identifier as a key according to a linked list search.

15. The method of claim 10, wherein the searching step includes:

generating a hash key based on the host identifier; and

searching for the stored table entry using the generated hash key.

16. The method of claim 10, further comprising storing address information from the layer 2 packet, including the host identifier, in the one selected address table based on a determined absence of the host identifier in the one selected address table.

17. An integrated network switch configured for switching layer 2 data packets at a wire rate, the integrated network switch including:

a plurality of network switch ports, each configured for receiving a layer 2 data packet, having layer 3 packet information having a network identifier, a subnetwork identifier, and a host identifier, from a network node having the corresponding host identifier and belonging to a corresponding subnetwork having the corresponding subnetwork identifier; and

a switching module configured for switching the layer 2 data packets between the network switch ports according to layer 3 switching information, the switching module including a plurality of address tables for storing the layer 3 switching information for the respective subnetworks, the switching module accessing a selected one of the address tables based on the corresponding subnetwork identifer and searching for the layer 3 switching information of the received layer 2 data packet based on the corresponding host identifier.

18. The switch of claim 17, wherein the switching module is configured for independently and simultaneously accessing the address tables for the layer 3 switching information of the respective subnetworks.

19. The switch of claim 18, wherein the switching module is configured for searching each address table, based on the host identifier, using one of a linked list search and a hash key-based bin search.

20. The switch of claim 18, wherein each of the switch ports obtains the subnetwork identifier and the host identifier from the corresponding layer 2 packet.

21. The switch of claim 17, wherein each network switch port is connected to a corresponding one of the subnetworks, the switching module accessing the selected one address table based on the one network switch port having received the layer 2 packet.

22. The switch of claim 21, wherein each address table is assigned to a corresponding one of the network switch ports.